线性表详细讲述（带图）

线性表—顺序表和链表

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。

线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，

线性表在物理上存储时，通常以数组和链式结构的形式存储

2.顺序表

2.1概念

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

2.2 静态顺序表与动态顺序表

静态顺序表

这样定义的顺序表是静态的，也就是在程序运行时他所开辟的空间就是固定的，不可以在改变，只有改变代码中的MAX才可以改变数组大小。

这种方法：直接将空间写“死”，并不是一个好的方法。

好方法在下面

动态顺序表

这便是动态顺序表，当表满了之后会自动扩容（扩容函数实现）

相对于静态顺序表，它的空间在程序运行期间，并不是固定的，而是随着数据的增多而扩大表的容量。

2.3接口的实现

这里是对动态顺序表的实现。

typedef int SLTDataType;
typedef struct SeqList
{
	SLTDataType *arr;
	int sz;       //当前表中数据个数
	int capacity; //当前表的最大容量
}SeqList;

//顺序表的初始化
void SeqListInit(SeqList* sl);
//扩容函数
void Capacity(SeqList* sl);
//顺序表的尾插
void SeqListPushBack(SeqList* sl, SLTDataType x);
//顺序表的尾删
void SeqListPopBack(SeqList* sl);
//顺序表的头插
void SeqListPushFront(SeqList* sl, SLTDataType x);
//顺序表的头删
void SeqListPopFront(SeqList* sl);
//顺序表的查找
int SeqListFind(SeqList* sl, SLTDataType x);
//顺序表的任意位置插入
void SeqListInsert(SeqList* sl,int pos, SLTDataType x);
//顺序表的任意位置删除
void SeqListErase(SeqList* sl, int pos);
//顺序表的打印
void SeqListPrint(SeqList* sl);
//顺序表的销毁
void SeqListDestroy(SeqList* sl);
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
27
28
29
30

这些就是顺序表的基本功能

2.3.1顺表的初始化

//顺序表的初始化
void SeqListInit(SeqList* sl)
{
	assert(sl); //判断sl是否为NULL

	sl->arr = NULL;  // 初始化可以开辟空间也可以不开辟，这个是不开辟的
	//sl->arr = (SLTDataType*)malloc(sizeof(SLTDataType)*4);   这个是开辟空间的
	sl->sz = 0;

	sl->capacity = 0;
	//sl->capacity = 4    开辟空间了，容量就要初始化
}
1
2
3
4
5
6
7
8
9
10
11
12

2.3.2扩容

//扩容函数
void Capacity(SeqList* sl)
{
	assert(sl);

	//判断容量是否为0
	//如果是0的话使容量变为4
	//如果不为0的话使容量扩大2倍
	sl->capacity = (sl->capacity == 0 ? 4 : sl->capacity * 2);

	//通过realloc函数进行扩容
	SLTDataType* tmp = (SLTDataType*)realloc(sl->arr,sl->capacity * sizeof(SLTDataType));
	if (tmp == NULL)//判断是否开辟成功
	{
		//开辟不成功
		perror("Capacity::realloc:");
		exit(-1);
	}
	//开辟成功，将地址赋给sl->arr
	sl->arr = tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.3.3顺序表尾插

//顺序表的尾插
void SeqListPushBack(SeqList* sl, SLTDataType x)
{
	assert(sl); 

	//判断顺序表容量是否够
	//如果空间不够就扩容
	if (sl->capacity == sl->sz)
	{
		Capacity(sl);
	}

	//空间够了就开始写入数据
	sl->arr[sl->sz] = x;
	//写入后使sz++
	sl->sz++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.3.4顺序表的尾删

//顺序表的尾删
void SeqListPopBack(SeqList* sl)
{
	assert(sl);
	
	//如果顺序表中没有数据就不能再删除
	assert(sl->sz);

	//如果有数据开始删除
	sl->sz--;
}
1
2
3
4
5
6
7
8
9
10
11

有人肯定觉得删除数据后要将顺序表删除位置的数据置为0

sl->arr[sz-1] = 0

sl->sz--

其实写这一步的意义不打，你下次再次写的时候你直接就将原来数据覆盖了，再者说，如果你删除的数据要是0的话，你将它置为0不就多次一举

置与不置都可以，不会产生任何影响，我觉得没有必要取多写那一步。如果你有强迫症的话，你可以写那一步，反正都不影响结果，代码自己看着舒服就好 本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】