数据结构_线性表、顺序表、单链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构_线性表、顺序表、单链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构_线性表、顺序表、单链表

1. 线性表的定义和基本操作

1.1 线性表的定义

1.2 线性表的特点

1.3 线性表的基本操作

2. 线性表的顺序表示

2.1 顺序表的定义

2.2 顺序表上基本操作的实现

2.2.1 插入操作

2.2.2 删除操作

2.2.3 按值查找

2.3 相关练习巩固

3. 线性表的链式表示

3.1 单链表的定义

3.2 单链表上基本操作的实现

3.2.1 头插法建立单链表

3.2.2 尾插法建立单链表

3.2.3 按位（序号）查找结点值

3.2.4 按值查找表结点

3.2.5 插入结点操作

3.2.6 删除结点操作

3.2.7 求表长操作

数据结构_线性表、顺序表、单链表

1. 线性表的定义和基本操作

1.1 线性表的定义

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n表示表长，当n=0时，线性表是一个空表。若用L命名线性表，则一般表示为：

L=（a1,a2,a3,a4,a5,a6,a7……an）

式中：

a1是唯一的第一个数据元素，又称表头元素；

an是唯一的最后一个数据元素，又称表尾元素；

除了第一个元素外，每个元素有且仅有一个直接前驱。除了最后一个元素外，每个元素有且仅有一个直接后继。

1.2 线性表的特点

1. 由线性表的定义可得：线性表中元素是有限的。

2. 线性表中的元素具有逻辑上的顺序性，表中的元素有其先后顺序。

3. 表中的元素都是数据元素，每个元素都是单个元素。

4. 表中元素的数据类型都相同，意味着每个元素占有相同大小的存储空间。

5. 表中元素具有抽象性；也就是线性表只考虑元素间的逻辑关系，而不考虑线性表中的元素究竟表示什么内容。

注意：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。而顺序表和链表指的是存储结构，两者属于不同层次的概念。

1.3 线性表的基本操作

根据对程序时间复杂度和空间复杂度的学习；我们已经了解到了一个数据结构的基本操作是指其最核心、最基本的操作。其他复杂的操作均可以通过基本操作来实现。

InitList(&L)：初始化表。构造一个空的线性表。&L：引用符号在C++环境支持。

Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。

GetElem(L,i)：按位查找操作。获取表L中的第i个位置的元素的值。

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。

Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

总结：数据结构的基本操作无非就是数据进行创建、销毁以及增删查改；类似于C语言程序下的通讯录，创建通讯录、销毁通讯录、增删查改通讯录。

2. 线性表的顺序表示

2.1 顺序表的定义

线性表的顺序存储称为顺序表。它是用一组地址连续的存储单元依次去存储线性表中的数据元素。从而使得逻辑上相邻的两个元素在物理位置上也相邻。物理位置指的就是存储元素的地址。第一个元素存储在线性表的起始位置，第 i 个元素的存储位置后面紧接着存储第 i+1 个元素，称 i 为元素在线性表中的位序。

顺序表的特点是：

1. 表中元素的逻辑顺序与其物理顺序相同。也就是和内存地址是一一对应的。

2. 最主要的特点是随机访问，通过首地址和元素序号可在O(1)时间内找到指定的元素。

3. 顺序表的存储密度高，每个节点只存储数据元素。

4. 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量的元素。

数据结构_线性表、顺序表、单链表

线性表的元素类型为ElemType，线性表的顺序存储类型可以定义为：

1. 静态分配

#define MaxSize 50            //静态存储下线性表的最大长度
typedef struct
{
	ElemType data[Maxsize];   //顺序表的元素
	int length;           //顺序表当前长度
}sqList;      //顺序表的类型定义

2. malloc动态开辟空间分配

#define InitSize  100    //因为是动态开辟，所以只需要定义一个够用的空间即可
typedef struct
{
	ElemType *data;   //指示动态分配数组的指针
	int MaxSize, length;   //数组的最大容量和当前个数
}seqList;    //动态分配数组顺序表的类型定义

注意：动态分配并不是链式存储，他同样属于顺序存储结构，物理结构没有改变，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定。

2.2 顺序表上基本操作的实现

2.2.1 插入操作

在顺序表 L 的第 i（1<=i<=L.length+1）个位置插入新元素 e。若 i 输入不合法，则返回 false，表示插入失败。否则，将第 i 个元素及其后所有元素依次向后移动一个位置，腾出空位置插入新元素e，顺序表长度增加1，插入成功，返回 true。

bool ListInsert(SqList &L, int i, ElemType e)   //把e插入到顺序表上 i 的位置上
{
	if (i<1 || i>L.length + 1)  // 判断 i 的范围是否有效
		return false;
	if (L.length >= MaxSize)  // 存储空间已满，无法插入
		return false;
	for (int j = L.length; j >= 1; j--) 
	{
		L.data[j] = L.data[j - 1];//把前一个元素向后移一个单位
	}
	L.data[i - 1] = e;// 把e放到位置 i 上
	L.length++; //线性表长度+1
	return true;
}

最好情况：在表尾插入，元素后移语句不执行，时间复杂度为O(1)；

最坏情况：在表头插入，元素后移语句执行n次，时间复杂度为O(n)；

平均情况：移动的平均次数是n/2；平均时间复杂度是O(n)；

2.2.2 删除操作

删除顺序表L中第 i （1<=i<=L.length）个位置的元素，用引用变量e返回。若 i 的输入不合法，则返回false；否则，将被删元素赋给引用变量e，并将第 i + 1 个元素及其后的所有元素依次往前移动一个位置，返回 true。

bool ListDelete(SqList &L, int i, ElemType &e)   
{
	if (i<1 || i>L.length + 1)  // 判断 i 的范围是否有效
		return false;
	e = L.data[i - 1];    //将被删除的元素赋值给e
	for (int j = i; j < L.length;j++)
	{
		L.data[j-1] = L.data[j];   //把第i个位置后的元素前移
	}
	L.length--; //线性表长度--
	return true;
}

最好情况：删除表尾元素，无需移动元素，时间复杂度为O(1)。

最坏情况：删除表头元素，移动除表头以外的所有元素，时间复杂度为O(n)。

平均情况：所需移动结点的平均次数为(n-1)/2。平均时间复杂度为O(n)。

2.2.3 按值查找

在顺序表L 中查找第一个元素值等于 e 的元素，并返回其位序。

int LocationElem(sqList L, ElemType e)
{
	int i;
	for (i = 0; i < L.length; i++)
	{
		if (L.data[i] == e)
			return i + 1;   // 注意数组和顺序表下标的区别；数组下标为 i 的元素对应的位序是 i+1
	}
	return 0;
}

最好情况：找的元素就在表头，仅需比较一次，时间复杂度为 O（1）。

最坏情况：查找的元素在表尾，需要比较n次，时间复杂度为O（n）；

平均情况：需要比较的平均次数为（n+1）/2；平均时间复杂度为O（n）；

2.3 相关练习巩固

1. 从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并且退出运行。

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

思想：查找整个顺序表，找到最小值的元素，记住其位置，查找结束后用最后一个元素填补空出的原最小值的元素位置。
bool Del_Min(Sqlist &L, ElemType &value)
{
	if (L.length==0) //顺序表为空，返回false
		return false;
	value = L.data[0];  //不妨假设数组中下角标为0的数最小
	int pos = 0;//用pos来记忆最小元素的下角标
	for (int i = 1; i < L.length; i++) //for循环找到最小值
	{
		if (L.data[i] < value)//前面已经假设value是数组中的最小值，拿数组中其他的最小值去和我们假设的最小值进行比较
		{
			value = L.data[i];//如果if语句正确，那么就证明数组中还存在元素比我们假设的最小值还要小，那么将更小的值赋值给value，使得value具有记忆功能，永远循环数组中的更小值
			pos = i;//pos记忆最小值value的下角标i
		}
		L.data[pos] = L.data[L.length - 1];//将数组中最后一个元素赋值给下角标value最小的元素
		L.length--;//数组-1，会自动舍去最后一个元素
		return true;	
	}
}

2. 设计一个高效的算法。将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。

算法思想：扫描顺序表L的前半部分元素，对于元素L.data[i]（0<=i<L.length/2），将其与后半部分元素进行交换L.data[L.length-i-1]
void Reverse(Sqlist &L)
{
	Elemtype temp;  //给一个中间变量
	for (i = 0; i < L.length / 2; i++)
	{
		temp = L.data[i];     //用中间变量temp进行逆序的交换
		L.data[i] = L.data[L.length - i - 1];
		L.data[L.length - i - 1] = temp;
	}
}

3. 对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。

算法思想一：用k记录顺序表中不等于x的数据个数（也可以说是需要保留下来的数据），扫描时将不等于x的元素移动到下角标为k的位置，更新顺序表L的长度，以此来删除不等于x的元素。
void del_x(Sqlist &L, Elemtype x)
{
	int k = 0;//k表示顺序表中不等于x的元素个数
	int i = 0;
	for (i = 0; i < L.length; i++)
	{
		if (L.data[i] != x)//循环判断下角标为i的数组元素是否等于x
		{
			L.data[k] = L.data[i];//一旦进入循环则需要将等于x的赋值给下角标为0 1 2 3 4 的
			k++;//0 1 2 3 4是因为k是从初始值0开始++的，每当找到一个不等于x的，k++，会依次锁定下角标为0 1 2 3 4 5……的
		}
	}
	L.length = k;//既然已经跳出循环，那么就意味着找到了所有的不等于x的元素，k表示元素个数，那么这个时候设置数组长度为k，那么就意味着间接删除了数组中等于x的元素
}
算法思想二：用k记录顺序表L中等于x的元素个数，一边扫描L一边统计k，将不等于x的元素前移k个位置。扫描结束后修改L的长度。
void del_x(Sqlist &L, Elemtype x)
{
	int k = 0;//用k表示顺序表中等于x的元素个数
	int i = 0;
	while (i < L.length)
	{
		if (L.data[i] == x)//扫描只要有元素等于x，k++
			k++;
		else   //进入else语句，此时找到的元素一定不等于x
			L.data[i - k] = L.data[i];//把不等于x的元素根据k的变化向前移动，这样程序循环结束后，会使得数组前元素全部是不等于x的数字
		i++;
	}
	L.length = L.length - k;//该程序的作用会删除数组后面等于x的数字
}

4. 从有序顺序表中删除其值在给定值s与t之间（要求s<t）的所有元素，若s或t不合理或顺序表为空，则显示出错误信息并退出运行。

算法思想：因为是有序顺序表，所以删除的必定是相连的整体。先去寻找值大于等于s的第一个元素（也就是第一个要删除的元素），然后寻找大于t的第一个元素（也就是从后往前搬运的第一个元素），将这段元素删除，只需要将后面的元素前移即可。
bool del_s_t(Sqlist &L, Elemtype s, Elemtype t)
{
	int i, j;
	if (s >= t || L.length == 0)//违反s<t，并且顺序表总长度为0时返回false
		return false;
	for (i = 0; i < L.length&&L.data[i] <= s; i++);//该for循环内容为空，循环语句为i小于顺序表总长度，并且数据小于s，那么离开该循环时数字对应于大于s的后一个元素
	if (i > L.length)
		return false;
	for (j = i; j < L.length&&L.data[j] < t; j++);//该for循环的内容也为空，初始条件是从i开始的，循环语句为数据小于等于t，那么离开该循环时数字一定是大于t的第一个元素
	//这里注意：之所以是大于等于，是因为从t以后向前移动，是把大于t的元素依次搬到删除元素的位置
	for (; j < L.length; i++, j++)//开始搬运
	{
		L.data[i] = L.data[j];
	}
	L.length = i + 1;//改变顺序表的总长度
	return true;
}

5. 从顺序表中删除其值在给定值s与t之间（包含s和t，要求s<t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。

算法思想：该算法思想和上一题的思想相同，只是在上一题的循环体范围上进行了更改。

bool del_s_t(Sqlist &L, Elemtype s, Elemtype t)
{
	int i, j;
	if (s >= t || L.length == 0)//违反s<t，并且顺序表总长度为0时返回false
		return false;
	for (i = 0; i < L.length&&L.data[i] < s; i++);//该for循环内容为空，循环语句为i小于顺序表总长度，并且数据小于s，那么离开该循环时数字对应于大于s的后一个元素
	if (i > L.length)
		return false;
	for (j = i; j < L.length&&L.data[j] <= t; j++);//该for循环的内容也为空，初始条件是从i开始的，循环语句为数据小于等于t，那么离开该循环时数字一定是大于t的第一个元素
	//这里注意：之所以是大于等于，是因为从t以后向前移动，是把大于t的元素依次搬到删除元素的位置
	for (; j < L.length; i++, j++)//开始搬运
	{
		L.data[i] = L.data[j];
	}
	L.length = i + 1;//改变顺序表的总长度
	return true;
}

数据结构_线性表、顺序表、单链表

6. 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

算法思想：题目要求是有序顺序表，那么值相同的元素一定在连续的位置上，用类似于直接插入排序的思想，初始时将第一个元素视为非重复的有序表。之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同，若相同，则继续向后判断，若不同，则插入前面的非重复有序表的最后，直至判断到表尾为止。
bool Delete_Same(Sqlist &L)
{
	if (L.length == 0)
		return false;
	int i, j; //该程序最重要的就是区分 i 和 j 的功能
	for (i = 0, j = 1; j < L.length; j++)  // i 表示第一个不重复的元素下角标，j 表示循环指针，用 j定义的下角标去寻找和 i定义下角标不同的元素
	{
		if (L.data[i] != L.data[j])
			L.data[++i] = L.data[j];//每循环一次，i 后的元素就要进行++，所以是前置++
	}
	L.length = i + 1;
	return true;
}

7. 将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

算法思想：首先，按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后，看哪个表还有剩余，将剩下的部分加到新的顺序表后面。

bool Merge(Sqlist A, Sqlist B, Sqlist &C)
//将有序顺序表A与B合并为一个新的有序顺序表C
{
	if (A.length + B.length > C.maxSize) //大于顺序表的最大长度
		return false;
	int i = 0, j = 0, k = 0;
	while (i < A.length&&j<B.length)//A和B顺序表进行两两比较，小的存放到合并的顺序表C中
	{
		if (A.data[i] <= B.data[j])
			C.data[k++] = A.data[i++];//A中的更小，那么把A中最小的放入到合并顺序表C中
		else
			C.data[k++] = B.data[j++];//否则把B中更小的放入到合并顺序表C中
	}
	while (i < A.length)//如果比较完以后A或者B中还有剩余的，因为是有序的顺序表，直接将剩余的放到合并顺序表C中即可
		C.data[k++] = A.data[i++];
	while (j < B.length)
		C.data[k++] = B.data[j++];
	C.length = k;//改变顺序表长度
	return true;
}

int main()
{
	int arr1[] = { 1, 3, 5, 7, 9 };
	int sz1 = sizeof(arr1) / sizeof(arr1[0]);
	int arr2[] = { 2, 4, 6, 8, 10 };
	int sz2 = sizeof(arr2) / sizeof(arr2[0]);
	int arr3[10] = { 0 };  //数组arr3必须有足够的容量去存放数组1和数组2合并的结果
	int sz3 = sizeof(arr3) / sizeof(arr3[0]);
	int i = 0;
	int j = 0;
	int k = 0;
	while (i < sz1&&j < sz2)
	{
		if (arr1[i] <= arr2[j])
		{
			arr3[k++] = arr1[i++];
		}
		else
			arr3[k++] = arr2[j++];
	}
	while (i<sz1)
		arr3[k++] = arr1[i++];
	while (j<sz2)
		arr3[k++] = arr2[j++];
	for (k = 0; k < sz3; k++)
	{
		printf("%d ", arr3[k]);
	}
	return 0;
}

数据结构_线性表、顺序表、单链表

3. 线性表的链式表示

顺序表的优越性在于可以随时存取表中的任意一个元素，它的存储位置可以用一个简单直观的公式去表示，其缺点在于插入和删除操作需要移动大量元素。

链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过 “链” 建立起数据元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需要修改指针，但相应的也会失去顺序表可随机存取的优点。

3.1 单链表的定义

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对于每个链表的结点，除了存放元素自身的信息外，还需要存放一个指向后继的指针。

单链表只能实现单方向从头到尾的操作，这对我们进行某项基本操作是有一定限制的，也可以说是有一定麻烦的；通过以后的学习，可以发现双链表是可以双向操作的，可以解决这一问题。

数据结构_线性表、顺序表、单链表

//定义一个结点

typedef struct LNode     //定义单链表结点类型
{
    ElemType data;   //每个结点存放一个数据元素
    struct LNode *next;   //指针指向下一个结点
}LNode,*LinkList;

利用单链表可以解决顺序表需要大量连续存储单元的缺点，但是单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取的存储结构，不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。

通常用头指针来标识一个单链表，如单链表L，头指针为NULL时表示一个空表。为了操作上的方便，在单链表的第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。

数据结构_线性表、顺序表、单链表

头结点和头指针的区分：

不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带有头结点的链表中的第一个结点，结点内通常不存储信息。

如果不带头结点，那么头指针L指向的下一个结点就是存储数据的结点；而如果带头结点的话，那么头指针L指向的下一个结点就是头结点，头结点是不存储数据的。

数据结构_线性表、顺序表、单链表

3.2 单链表上基本操作的实现

数据结构_线性表、顺序表、单链表

3.2.1 头插法建立单链表

数据结构_线性表、顺序表、单链表

所谓建立单链表就是给你一堆数据元素（ElemType），需要把它们存到一个单链表里面。首先需要初始化一个单链表，每次取一个数据元素，插到表头或者表尾。

头插法从一个空表（头指针为NULL时）开始，生成新结点，并且将读取到的数据存放到新结点的数据域中，将新结点插入到当前链表的表头（头结点之后）。头插法就是说我每次取到一个数据元素时，都从最前面插入动态开辟空间来存放。因此头插法形成的链表顺序是倒着的。

数据结构_线性表、顺序表、单链表

采用头插法建立单链表时，读入数据的顺序和生成链表中的顺序是相反的。每个结点的插入时间为O(1)，设单链表长为n，则总的时间复杂度为O(n)；

LinkList List_HeadInsert(LinkList &L)
{
	LNode *s;
	int x;
	L = (LinkList)malloc(sizeof(LNode));   //创建头结点
	L->next = NULL;    //初始为空链表
	scanf("%d", &x);   //输入结点的值
	while (x != 9999)
	{
		s = (LNode*)malloc(sizeof(LNode));  //只要有结点数据输入，就动态开辟一块内存s来存储
		s->data = x; //将给定的结点数值x存放到动态开辟空间的数据域中
		s->next = L->next; //L->next指针原本指向下一个结点，此时将其赋值给s->next，那么动态开辟的内存指针就会指向下一个结点
		L->next = s;   //将新结点插入到表中，L为头指针，头结点指向动态开辟空间的结点
		scanf("%d", &x); //安置好一个结点，准备安置下一个结点
	}
	return L; //所有结点都安置好以后，返回最终整理好的链表
}

注意：因为头插法建立的单链表元素数据是倒过来的，所以头插法建立单链表很重要的应用就是逆置操作。

3.2.2 尾插法建立单链表

数据结构_线性表、顺序表、单链表

尾插法生成链表中的结点次序和输入数据的顺序一致。该方法将新结点插入到当前链表的表尾，为此必须增加一个尾指针 r，尾指针 r 始终指向当前链表的尾结点。

数据结构_线性表、顺序表、单链表

LinkList List_TailInsert(LinkList &L)
{
	int x;
	L = (LinkList)malloc(sizeof(LNode));//动态开辟一个头结点
	LNode *s, *r = L;  //r为表尾指针
	scanf("%d", &x); //输入结点的值
	while (x != 9999) //输入9999时表示结束
	{
		s = (LNode*)malloc(sizeof(LNode));//只要输入结点的数据值，就动态开辟一块空间
		s->data = x;//将给的结点的数据值给到动态开辟的空间
		r->next = s;//将开辟空间的地址给到表尾指针
		r = s;   //r指向新的表尾结点  一定保证r指针永远指向表尾
		scanf("%d", &x);//安置好一个结点后，准备安置下一个结点
	}
	r->next = NULL;  //尾结点指针置空
	return L;
}

3.2.3 按位（序号）查找结点值

数据结构_线性表、顺序表、单链表

GetElem(L，i)：按位查找操作。获取表 L 中第 i 个位置的元素的值。

数据结构_线性表、顺序表、单链表

//带头结点的情况下，按位查找，返回第 i 个元素
LNode *GetElem(LinkList L, int i)
{
	if (i < 0)
		return NULL; //因为是带头结点，头结点可以认为是第0个位置，头结点本身不存储数据
	LNode *p; //指针p指向当前扫描的结点
	int j = 0; //j表示当前p指向的是第几个结点
	p = L;  //初始化时，将头指针L指向的地址赋值给我们定义的指针p，表示初始化时指针p指向头结点
	while (p != NULL&&j < i)//表示遍历循环找到第 i 个结点
	{
		p = p->next;//从头结点依次遍历找到我们想要的结点
		j++;
	}
	return p;//通过以上的while循环p指针已经指向我们想要的结点，将p指针指向的结点返回即可。
}

时间复杂度：O（n）；

3.2.4 按值查找表结点

数据结构_线性表、顺序表、单链表

LocateElem(L，e)：按值查找操作。在表L中查找具有给定关键字值的元素。

数据结构_线性表、顺序表、单链表

按值查找就是给定一个值，看看在这个链表里有没有哪个结点对应的值和被查找的值一致。

//按值查找，查找数据域中值==e的结点，不妨假设此时e等于8
//链表假设是L->5->8->10->2->NULL
LNode *LocateElem(LinkList L, ElemType e)
{
	LNode *p = L->next; //将头指针的指针域赋给指针p，头指针的指针域指向的是下一个结点，也就是第一个结点，该结点的数据域内容为5
	while (p != NULL&&p->data != e)//该循环的判断条件是指针p指向的结点不是空结点并且结点对应的数据域内容不等于我们想要查找的元素e
	{
		p = p->next;//既然进入循环，那么此时p指向的结点数据内容一定不是想要查找的元素域
		//该程序会使得指针p不断进行遍历，直到找到我们想要的元素e，跳出循环
	}
	return p;//既然已经跳出循环，那么就意味着此时指针p指向了我们想要查找的元素，返回指向该元素的指针p即可
}

3.2.5 插入结点操作

LinkList(&L，i，e)：插入操作。在表L中的第 i 个位置上插入指定元素e。

如果是带头结点的情况，那么在第i个位置上插入需要找到第 i-1 个结点，将新结点插在其后。

比如说：我想在第二位置上插入指定元素e，那么就需要找到第一个位置，此时通过malloc函数动态申请一块空间，将指定元素e放在这块动态申请的空间中的数据域上，这个时候修改第一个位置上的指针next指向动态申请的这块空间，再讲动态申请的这块空间的指针指向第三块位置上；就可以实现插入结点操作。

此时如果想在第一个位置之前插入一个结点（也就是上图中红色箭头指的位置），这个时候就体会到了拥有头结点的优越性，可以将头结点看做是第0个位置，按照上述的过程插入结点即可。

bool ListInsert(LinkList &L, int i, ElemType e)
{
	if (i < 1)
		return false;
	LNode *p;  //指针p当前扫描的结点，如下图所示
	int j = 0;// j表示当前p指向的是第几个结点，如图所示，初始化p为0
	p = L; //L指向头结点，头结点是第0个结点（不存放数据）
	while (p != NULL&&j < i - 1)//循环找到第i-1个结点
	{
		p = p->next; //将第i-1个结点对应的指针域指向p，使p具有记忆功能，始终指向扫描的结点
		j++;
	}//循环体中的内容实现依次寻找下一个结点
	if (p == NULL)  //不合法
		return false;
	LNode *s = (LNode*)malloc(sizeof(LNode)); //动态开辟一块内存来存储要插入的数据
	s->data = e; //将要插入的数据e存放到动态开辟的内存s的数据域上
	s->next = p->next; //如图所示，原本头结点的指针域是指向第一个元素a1的
	//将指向a1的指针赋值给s的指针域，会使得新开辟的空间s的指针指向第一个结点a1
	p->next = s; //该指令把s地址给到了p，那么头结点p指向的地址就会指向新开辟的空间s
	return true;
}

如果是不带头结点的情况：则不存在第0个位置这种特殊情况，插入第一个结点的操作与其他结点的操作不同

数据结构_线性表、顺序表、单链表

bool ListInsert(LinkList &L, int i, ElemType e)//往位置i上插入结点，结点的数据域为e
{
	if (i < 1)
	{
		return false;
	}
	//处理在a1之间插入结点的情况
	if (i == 1)//因为是不带头结点的，所以不存在位置0这种说法，也可以说往a1之前插入结点这种特殊情况需要特殊注明
	{
		LNode *s = (LNode *)malloc(sizeof(LNode));//动态开辟一块内存，用于存储数据e
		s->data = e;//把元素e放到新开辟的动态内存s上的数据域中
		s->next = L;//L原本的指针域是指向a1的，把L赋值给新开辟的动态内存s，则原本指向a1的指针会变成动态内存s指向a1的指针
		L = s;//把s的地址给到指针L，那么原本L指向a1的指针会变成L指向动态开辟的内存s
		return true;
	}
	LNode *p;//指针p指向当前扫描的结点
	int j = 1;//因为没有位置0这种说法，所以有头结点和没有头结点的情况很大的区别也在于：指向第几个结点的初始值发生了变化
	p = L;//初始时L指向第一个结点，则p也指向第一个结点
	while (p != NULL&&j < i - 1)
	{
		p = p->next;//使指针p依次扫描每一个结点
		j++;
	}
	if (p == NULL)
	{
		return false;
	}
	//处理在a1之后插入结点的情况
	LNode *s = (LNode *)malloc(sizeof(LNode));//动态开辟一块内存用来存放数据e
	s->data = e;//把数据e存放到动态开辟的内存的数据域中
	s->next = p->next;//原本p->next是指向下一个结点的指针域，将其赋值给新开辟内存的指针域，则会使新开辟内存的指针域指向下一个结点的指针域
	p->next = s;//该程序的作用会使得原本指向下一个结点的指针域指向新开辟的内存（注意该指针的指向是从上一个结点的指针域指出的）
	return true; //插入成功
}

数据结构_线性表、顺序表、单链表

指定结点的后插操作：

//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p, ElemType e)
{
	if (p == NULL)//指针p指向的空间为空结点
	{
		return false;
	}
	LNode *s = (LNode*)malloc(sizeof(LNode));//动态开辟一块空间用来存储数据e
	if (s == NULL)//判断动态开辟的内存是否开辟成功
		return false;
	s->data = e;//把数据元素e存储到新开辟的空间s的数据域中
	s->next = p->next;//把原本指向下一个结点的指针赋值给动态开辟空间s的指针域，表示把原本指向下一个结点的指针变为由新开辟空间指向下一个结点的指针
	p->next = s;//把s的地址赋值给原本指向下一个结点的指针，就会使得原本指向下一个结点的指针变为指向新开辟空间s的指针
	return true;
}

数据结构_线性表、顺序表、单链表

指定结点的前插操作：

数据结构_线性表、顺序表、单链表

前插操作是指在给定结点的情况下，在结点之前插入元素e；但是，因为我们不清楚给定元素之前的结点情况，也可以说链表的指针都是指向下一个结点的，因此我们可以通过引入头结点的方法，对整个链表进行遍历，那么整个链表的内容就会一览无余。这种方法显然需要遍历整个链表，时间复杂度为O(n)；因此，考虑下述的方法：（细细斟酌）

//前插操作：在p结点之前插入元素e  
//虽然我们不知道p结点之前的结点情况，但可以通过改变数据域来实现前插操作
bool InsertPriorNode(LNode *p, ElemType e)
{
	if (p == NULL)
	{
		return false;
	}
	LNode *s = (LNode *)malloc(sizeof(LNode)); //动态开辟一块内存
	if (s == NULL)  //判断动态内存的空间是否开辟成功
		return false;
	s->next = p->next;
	p->next = s;//以上两句代码实现在给定结点之后插入数据e，也可以说是后插操作，这样结果会在给定结点以后插入一个动态开辟的内存空间，空间中存储的数据元素是e
	s->data = p->data;//把给定结点的数据域中元素给到新开辟空间的数据域中
	p->data = e;//把需要插入的数据元素e给到给定结点的数据域，这么一来一回就间接的实现了在给定结点之前插入元素e，只不过给定的结点变成了我们理想的插入结点
	//我们动态开辟的空间s变成了给定的结点p；
	return ture;
}

简单理解就是 我首先在AC之间插入一个B，实际上是实现了在A之后的后插操作，ABC
接下来我将A的数据域给到B，B的数据域给到A，现在的B才是链表中原本存在的元素
A就相当于在B之前实现了前插操作

数据结构_线性表、顺序表、单链表

3.2.6 删除结点操作

带头结点的删除结点操作：

ListDelete(&L，i，&e)：删除操作。删除表L中的第 i 个位置的元素，并用e返回删除元素的值。

数据结构_线性表、顺序表、单链表

//带头结点的情况下实现按位删除
bool ListDelete(LinkList &L, int i, ElemType &e)
{
	if (i < 1)
		return false;
	LNode *p;//指针p指向当前扫描的结点
	int j = 0;//j表示当前p指向的是第几个结点
	p = L;//L指向头结点
	while (p != NULL&&j < i - 1)//假设我们要删除第四个结点，那么必须先找到第三个结点的指针域p，使指针p指向第四个结点
	{
		p = p->next;//该while循环就是实现遍历整个链表，这样才能实现删除某个结点的操作
		j++;
	}
	if (p == NULL)//结点的 i 值不合法
		return false;
	if (p->next == NULL)//while循环找到第i-1个结点的地址，也就是指针域，但是该指针域指向的下一个结点为空
		return false;
	LNode *q = p->next;//定义一个新的指针q，将while循环找到的i-1个结点的指针p赋值给指针q，那么此时指针q就指向被删除的结点
	e = q->data;//将所要删除的结点的数据域内容赋值给e
	p->next = q->next;//原本q指向被删除结点的下一个结点，将该指针赋值给p，也就是被删除结点的前一个结点，那么结果会变成被删除结点的前一个结点指向被删除结点的后一个结点
	free(q);//malloc动态开辟空间函数和free释放空间函数是一同使用的，既然要删除，那么将删除结点所占用的空间通过free释放掉即可，指针q指向被删除的结点
	return true;   //删除成功
}

数据结构_线性表、顺序表、单链表

删除给定结点p：

因为我们无法通过链表找到前驱结点，所以我们需要使用和上述前增数据e一样的方法来实现。

//删除指定结点p
bool DeleteNode(LNode *p)
{
	if (p == NULL)
		return false;
	LNode *q = p->next; //定义新的指针q，将p的后继指针赋值给q，那么此时q指向被删除结点的下一个结点
	p->data = p->next->data;//将被删除结点p指向的下一个结点的数据域内容赋值给被删除结点p，如图，那么被删除结点p和其后一个结点的数据域内容都将是y
	p->next = q->next;//将被删除结点的下一个结点的指针赋值给被删除结点，此时，被删除结点原本指向下一个结点，会变成指向下下个结点，跳过被删除结点的下一个结点
	free(q);//之所以释放掉结点q就等同于删除了结点p，是因为，结点是由数据域和指针域组成的，指针域已经指向下下个结点，数据域的内容已经和下一个结点相同，结点的两个主要组成都已经被更改了
	return true;
}

数据结构_线性表、顺序表、单链表

注意：该代码是有限制条件的，如果要删除的结点恰好是最后一个结点，那么结点的指针域指向的就是空指针NULL了，因此这种情况只能从头结点依次遍历实现删除操作了。

3.2.7 求表长操作

求表长也就是计算链表的长度。

数据结构_线性表、顺序表、单链表文章来源地址https://www.toymoban.com/news/detail-430896.html

int length(LinkList L)
{
	int len = 0;//用len去统计表长
	LNode *p = L;//把头指针赋值给指针p
	while (p->next != NULL)//因为链表的最后一个结点一定是NULL，所以只要不是NULL，我就len++
	{
		p = p->next;//依次遍历整个链表，使得指针p从头结点依次遍历
		len++;//表长++
	}
	return len;  //只要跳出循环，就表示找到了链表最后的空指针，返回最后len++的值
}

到了这里，关于数据结构_线性表、顺序表、单链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！