超详细讲解数据结构之顺序表

顺序表

概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。

顺序表一般分为静态顺序表和动态顺序表。

静态顺序表

静态顺序表是使用定长数组存储元素。

简单静态顺序表结构体的初始化：

#define N 7
typedef int SLDataType;
struct Seqlist
{
   
	SLDataType a[N];
	int size;//记录数据个数
};
1
2
3
4
5
6
7
8

代码中数组a是用来存储要存入到顺序表中，很明显，该数组开辟的空间大小是固定的，所以有着无法优化的缺点——最大容量是固定的：
最大容量开小了，可能会导致元素存储不下，最大容量开大了会导致空间浪费严重。

故一般情况下顺序表一般都是使用动态顺序表。

动态顺序表

动态循序表的概念及构造

动态顺序表是利用动态开辟来存储元素。

typedef int SLDataType;
typedef struct Seqlist
{
   
	SLDataType* a;//指向动态开辟的数组
	int size;  //存储数据的个数
	int capacity; //存储空间的大小
}SL;
1
2
3
4
5
6
7
8

动态顺序表的优点在于需要多少空间来存储数据我就能开辟多少空间，不会出现大规模空间浪费和空间不足的情况。

动态顺序表接口的实现

动态顺序表接口的实现主要要完成以下几个功能：增删查找改

// 顺序表初始化
void SeqlistInit(SL* psl);

 检查空间，如果满了，进行增容
void SeqlistCheckCapacity(SL* psl);

//顺序表尾插
void SeqlistPushBack(SL* psl, SLDataType x);
//顺序表尾删
void SeqlistPopBack(SL* psl);

//顺序表头插
void SeqlistPushFront(SL* psl, SLDataType x);
//顺序表头删
void SeqlistPopFront(SL* psl);

//顺序表在pos位置插入x
void SeqlistInsert(SL* psl, size_t pos, SLDataType x);
//顺序表删除pos位置的值
void SeqlistErase(SL* psl, size_t pos);

//查找顺序表中的x的位置
int SeqlistFind(SL* psl, SLDataType x);

//修改顺序表中pos位置的值
void 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26