名人说:一花独放不是春,百花齐放花满园。——《增广贤文》
作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊)以下代码个人分享出来,仅供学习交流,且仅在CSDN平台发布,未经授权禁止二次转发。
〇、线性表是什么?
1、定义
线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列,其中n为表长,当n=0时线性表是一个空表。
L=(a1,a2,a3…,an) a1为表头元素,an为表尾元素,除第一个元素外,每个元素有且仅有一个直接前驱,除最后一个元素,每个元素有且仅有一个直接后继。
2、特点
- ①同类型
- ②有限
- ③有序
3、基本操作
那么该怎么用代码实现基本操作呢?请往下看(以顺序表为例)
一、代码实现
#include <iostream>
using namespace std;
#define MaxSize 50
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int length;
}SqList;
// 初始化线性表
void InitList(SqList &L) {
L.length = 0;
}
// 销毁线性表
void DestroyList(SqList &L) {
L.length = 0;
}
// 在第i个位置插入元素e
bool ListInsert(SqList &L, int i, ElemType e) {
if (i < 1 || i > L.length + 1) return false;
if (L.length >= MaxSize) return false;
for (int j = L.length; j >= i; j--)
L.data[j] = L.data[j - 1];
L.data[i - 1] = e;
L.length++;
return true;
}
// 删除第i个位置的元素,并用e返回其值
bool ListDelete(SqList &L, int i, ElemType &e) {
if (i < 1 || i > L.length) return false;
e = L.data[i - 1];
for (int j = i; j < L.length; j++)
L.data[j - 1] = L.data[j];
L.length--;
return true;
}
// 按值查找,返回元素e的位序
int LocateElem(SqList L, ElemType e) {
for (int i = 0; i < L.length; i++)
if (L.data[i] == e) return i + 1;
return 0;
}
// 按位查找,返回第i个位置的元素值
bool GetElem(SqList L, int i, ElemType &e) {
if (i < 1 || i > L.length) return false;
e = L.data[i - 1];
return true;
}
// 返回线性表的长度
int Length(SqList L) {
return L.length;
}
// 输出线性表
void PrintList(SqList L) {
for (int i = 0; i < L.length; i++)
cout << L.data[i] << " ";
cout << endl;
}
// 判断线性表是否为空
bool Empty(SqList L) {
return L.length == 0;
}
int main() {
SqList L;
InitList(L);
ListInsert(L, 1, 3);
ListInsert(L, 2, 4);
ListInsert(L, 3, 5);
PrintList(L);
int e = -1;
ListDelete(L, 2, e);
cout << "删除的元素为:" << e << endl;
PrintList(L);
cout << "线性表长度为:" << Length(L) << endl;
cout << "元素4的位置为:" << LocateElem(L,4) << endl;
}
十万个为什么:代码中为什么要传入参数的引用“&”?
因为想要将 对参数的修改结果 “带回来”
二、思路阐明
顺序表是一种线性表的存储结构。顺序表使用一段连续的存储单元来存储数据,每个数据元素占用一个存储单元。
在实现上述代码的过程中,首先使用了一个结构体来定义顺序表,其中又用了一个数组data
来存储数据元素,一个整型变量length
用来记录线性表的长度。
之后实现了多种对顺序表的操作,包括初始化、销毁、插入、删除、按值查找、按位查找、求长度、输出和判空。
- InitList(&L)函数:初始化线性表,将长度设为0。
- DestroyList(&L)函数:销毁线性表,将长度设为0。
- ListInsert(&L,i,e)函数:在第i个位置插入元素e。首先判断插入位置是否合法,然后将第i个位置及之后的元素后移一位,腾出空间插入新元素,最后将线性表长度加1。
- ListDelete(&L,i,&e)函数:删除第i个位置的元素,并用e返回其值。首先判断删除位置是否合法,然后将被删除元素的值赋给e,再将第i个位置之后的元素前移一位,最后将线性表长度减1。
- LocateElem(L,e)函数:按值查找,返回元素e的位序。遍历线性表,找到第一个值等于e的元素并返回其位序。
- GetElem(L,i)函数:按位查找,返回第i个位置的元素值。首先判断查找位置是否合法,然后返回第i个位置的元素值。
- Length(L)函数:返回线性表的长度。
- PrintList(L)函数:输出线性表。
- Empty(L)函数:判断线性表是否为空。
最终按照顺序表的操作顺序,在main函数中进行调用测试即可,具体测试见下方样例测试,以上就是这段代码的简要实现思路。
三、样例测试
首先在1、2、3位置插入3、4、5的值,长度为3,之后删除值为4的元素,接着计算线性表的长度,由一开始的3变为了2,也表明了删除成功,在查找元素4的位置时,由于元素4已经被删除了,所以在查找函数中返回了0。文章来源:https://www.toymoban.com/news/detail-520035.html
3 4 5
删除的元素为:4
3 5
线性表长度为:2
元素4的位置为:0
--------------------------------
Process exited after 0.06322 seconds with return value 0
请按任意键继续. . .
✔ 部分内容参考:王道数据结构(B站/MOOC 咸鱼学长主讲)
Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊)
如果对大家有帮助的话,希望大家能多多点赞+关注!这样我动力会更足哦! ღ( ´・ᴗ・` )比心文章来源地址https://www.toymoban.com/news/detail-520035.html
到了这里,关于数据结构 线性表的定义和基本操作(以顺序表为例)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!