线性表的链式存储结构

╰半夏微凉° 2022-10-01 04:56 169阅读 0赞

**一、解析**

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。

![Center][]

在顺序结构中，每个数据元素只需要存数据元素信息就可以了。现在链式结构中，除了要存数据元素信息外，还要存储他的后继元素的存储地址。

为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为节点（Node）。

n个节点（ai的存储映像）链结成一个链表，即为线性表（a1,a2,a3,……,ai-1,ai,ai+1,……,an）的链式存储结构，因为此链表的每个节点中只包含一个指针域，所以叫做**单链表**。

我们把链表的第一个节点的存储位置叫做头指针，最后一个节点的指针指向空。若链表为空则头节点的指针域为空。

![Center 1][]

头指针与头节点

<table> 
 <tbody> 
 <tr> 
 <td> 头指针 </td> 
 <td> 头节点 </td> 
 </tr> 
 <tr> 
 <td> 头指针是指链表指向第一个节点的指针，若链表有头节点，则是指向头节点的指针； 头指针具有标识作用，所以常用头指针冠以链表的名字； 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。 </td> 
 <td> 头节点是为了操作的统一和方便而设立的，放在第一元素的节点之前，其数据域一般无意义（也可以存放链表的长度）； 有了头节点，对在第一元素节点前插入节点和删除第一节点，其操作与其他操作就统一了； 头节点不一定是链表必要素 </td> 
 </tr> 
 </tbody> 
</table>

**二、结构设计**

typedef int ElemType;//此处可能是个结构体，练习使用int型足够了
    /*线性表的单链表存储结构*/
    typedef struct Node
    {
    	ElemType data;
    	struct Node *next;
    }Node;
    typedef struct Node *LinkList;//定义LinkList

**结点由存放数据元素的数据域和存放后继结点地址的指针域组成。**

例如：P是指向线性表第i个元素的指针，则该结点ai的数据域我们可以使用p->data来表示，p->data的值是一个数据元素，结点ai的指针域可以用p->next来表示，p->next的值是一个指针。p->next指向谁呢？当然是指向第i+1个元素，即指向ai+1的指针。也就是说如果p->data=ai，那么p->nex->data=ai+1。如图所示：

![Center 2][]

**三、单链表的读取**

获得链表第i个数据的算法思路：

1.声明一个节点P指向链表第一个结点，初始化j从1开始；

2.当j<i是，就遍历链表，让P的指针向后移动，不断指向下一个结点，j累加1；

3.若道链表末尾P为空，则说明第i个元素不存在；

4.否则查找成功，返回结点P的数据。

直观理解，就是从头开始找，知道第i个元素为止。由于i不确定因此i=n则需要遍历n-1次才可以找到数据，因此最坏情况的时间复杂度是O(n)。因为单链表的长度不固定，查找的时候并不知道需要循环多少次，使用for循环显然不合适，因此查找的核心思想是“工作指针后移”。

**四、单链表的插入删除**

**(一)、插入**

单链表第i个数据插入结点的算法思路：

1.声明一个结点P指向链表第一个结点，初始化j从1开始；

2.当j<i时，就遍历链表，让P的指针向后移动，不断指向下一个结点，j累加1；

3.若道链表末尾P为空，则说明第i个元素不存在；

4.否则查找成功，在系统中生成一个空结点s；

5.将数据元素e赋值给s->data;

6.单链表的插入标准语句s->nest=p->next;p->next=s;

7.返回成功。

**(二)、删除**

单链表第i个数据删除结点的算法思路：

1.声明一个结点P指向链表第一个结点，初始化j从1开始；

2.当j<i时，就遍历链表，让P的指针向后移动，不断指向下一个结点，j累加1；

3.若道链表末尾P为空，则说明第i个元素不存在；

4.否则查找成功，将欲删除的结点p->next赋值给q；

5.单链表的删除标准语句p->nest=q->next;

6.将q结点中的数据赋值给e，作为返回;

7.释放q结点；

8.返回成功。

**(三)、分析**

如上分析单链表插入和删除操作都是有两部分组成：

第一部分：遍历查找第i个元素；

第二部分：插入或者删除元素。

从算法可以导出插入或者删除的时间复杂度是O(n).如果不知道第i个元素的指针位置，单链表数据结构在插入和删除上，与线性表顺序存储结构是没有太大优势的。但是如果需要从第i个位置连续插入10个或者更多的元素，对于顺序表就意味着，每插入一次都需要移动n-i个元素，每次都是O(n)。而单链表，只需要在第一次时找到第i个位置的指针，此时为O(n),接下来只是简单地通过赋值移动指针而已，时间复杂度都是O(1)。显然，对于插入或者删除数据越频繁的操作，单链表的效率优势就越是明显。

**五、单链表的整表创建**

单链表和顺序存储结构不同，顺序存储结构是事先已知表大小并且分配好了空间，说的直白一些就是对一个数组的初始化工作，相对于顺序存储结构，单链表很散，是一种动态结构，它所占用的空间大小和位置不需要预先分配划定，可以根据系统的情况和实际需求即时生成。创建单链表的过程就是一个动态生成链表。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。

单链表整表创建算法：

1.声明一个结点P和计数器变量I;

2.初始化一个空链表L；

3.让L的头结点的指针指向NULL，即建立一个带头结点的单链表；

4.循环：

◆生成一个新结点赋值给P；

◆随机生成一数字赋值给P的数据域p->data；(给结点赋值)

◆将P插入到头结点与前一新结点之间。（头插法，尾插法更好）

**六、单链表的整表删除**

就是将链表在内存中释放掉。

单链表整表删除算法：

1.声明一个结点p和q;

2.将第一个结点赋值给p；

3.循环：

◆将下一个结点赋值给q；

◆释放p;

◆将q赋值给p.

**七、单链表结构与顺序存储结构的优缺点**

<table> 
 <tbody> 
 <tr> 
 <td> 存储分配方式 </td> 
 <td> 时间性能 </td> 
 <td> 空间性能 </td> 
 </tr> 
 <tr> 
 <td> 1.顺序存储结构用一段连续的存储单元依次存储线性表的数据元素 2.单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素 </td> 
 <td> 1.查找： 顺序存储结构O(1)； 单链表O(n)； 2.插入和删除： 顺序存储结构需要平均移动表长一半的元素，时间为O(n)； 单链表在线出某位置的指针后，插入和删除时间仅为O(1) </td> 
 <td> 1.顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢； 2.单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。 </td> 
 </tr> 
 </tbody> 
</table>

通过上表对比，可以总结：

1.若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。

2.当线性表中的元素个数变化较大或者根本不知道有多大时，最好采用单链表结构，这样可由不需要考虑存储空间的大小问题。而如果事先知道线性表大大致长度，这种用顺序存储结构效率会高很多。

代码示例：

#include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
 
 #define MAXSIZE 20
 #define OK 1
 #define ERROR 0
 
 typedef int ElemType;//此处可能是个结构体，练习使用int型足够了
 /*线性表的单链表存储结构*/
 typedef struct Node
 {
 	ElemType data;
 	struct Node *next;
 }Node;
 typedef struct Node *LinkList;//定义LinkList
 
 //初始条件：顺序表L已经存在，1=<i=<ListLength(L)
 //操作结果：用e返回L中第i个数据元素的值
 int GetElem(LinkListL,int i,ElemType *e)
 {
 	int j = 0;
 	LinkList p;//声明一个节点p
 	p = L->next;//让p指向链表L的第一个节点
 	j = 1;//j为计数器
 	while(p && j <i)//p不为空或者计数器j还没有等于i时，循环继续
 	{
 		p = p->next;//让p指向下一个节点
 		++j;
 	}
 	if(!p || j >i)
 	{
 		return ERROR;//第i个元素不存在
 	}
 	*e = p->data;//取第i个元素的数据
 	return OK;
 }
 
 //初始条件：顺序表L已经存在，1=<i=<ListLength(L)
 //操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
 int ListInsert(LinkList *L,int i,ElemType e)
 {
 	int j = 0;
 	LinkListp,s;
 	p = *L;
 	j = 1;
 	while(p && j <i)//p不为空或者计数器j还没有等于i时，循环继续
 	{
 		p = p->next;//让p指向下一个节点
 		++j;
 	}
 	if(!p || j >i)
 	{
 		return ERROR;//第i个元素不存在
 	}
 	s = (LinkList)malloc(sizeof(LinkList));//分配内存
 	s->data = e;
 	s->next = p->next;//将p的后继节点赋值给s的后继
 	p->next = s;//将s赋值给p的后继
 	return OK;
 }
 
 //初始条件：顺序表L已经存在，1=<i=<ListLength(L)
 //操作结果：删除L中第i个位置的数据元素，并用e返回其值，L的长度减1
 int ListDelete(LinkList *L,int i,ElemType *e)
 {
 	int j = 0;
 	LinkListp,q;
 	p = *L;
 	j = 1;
 	while(p && j <i)//p不为空或者计数器j还没有等于i时，循环继续
 	{
 		p = p->next;//让p指向下一个节点
 		++j;
 	}
 	if(!(p->next) || j >i)
 	{
 		return ERROR;//第i个元素不存在
 	}
 	q = p->next;
 	p->next = q->next;//将q的后继赋值给p的后继
 	*e = q->data;//将p结点中的数据给e
 	free(q);//将系统回收此结点，释放内存
 	return OK;
 }
 /*随机产生n个元素的值，建立带表头结点的单链表L（头插法）*/
 void CreateListHead(LinkList *L,int n)
 {
 	LinkList p;
 	inti = 0;
 	//srand(time(0));//初始化随机数种子
 	*L = (LinkList)malloc(sizeof(LinkList));
 	(*L)->next = NULL;//先建立一个带头结点的单链表
 	for(i = 0;i <n;i++)
 	{
 		p = (LinkList)malloc(sizeof(Node));//生成新结点
 		//p->data = rand()%100+1;//随机生成100以内的数字
 		p->data = i;//随机生成100以内的数字
 		printf("[%s %d]元素:%d\n",__FUNCTION__,__LINE__,p->data);
 		p->next = (*L)->next;
 		(*L)->next = p;//插入到表头
 	}
 }
 
 /*随机产生n个元素的值，建立带表头结点的单链表L（尾插法）*/
 void CreateListTail(LinkList *L,int n)
 {
 	LinkListp,r;
 	inti = 0;
 	//srand(time(0));//初始化随机数种子
 	*L = (LinkList)malloc(sizeof(Node));//为整个线性表
 	r = *L;//r为指向尾部的结点
 	for(i = 0;i <n;i++)
 	{
 		p = (LinkList)malloc(sizeof(LinkList));//生成新结点
 		//p->data = rand()%100+1;//随机生成100以内的数字
 		p->data = i*10;//随机生成100以内的数字
 		r->next = p;//将表尾终端结点的指针指向新结点
 		r = p;//将当前的新结点定义为表尾终端结点
 	}
 	r->next = NULL;//表示当前链表结束
 }
 
 //初始条件：顺序表L已经存在，操作结果：将L重置为空表
 int ClearList(LinkList *L)
 {
 	LinkListp,q;
 	p = (*L)->next;//p指向第一个结点
 	while(p)//没到表尾
 	{
 		q = p->next;
 		free(p);
 		p = q;
 	}
 	(*L)->next = NULL;
 	return OK;
 }
 
 //若线性表为空返回TRUE，否则返回FALSE
 int ListEmpty(LinkList L)
 {
 	LinkList p;
 	p = L->next;//p指向第一个结点
 	if(!p)
 	{
 		return ERROR;
 	}
 	return OK;
 }
 
 /*在线性表L中查找给定值e相等的元素，
 *如果查找成功返回OK
 *表示成功；否则，返回0表示失败。
 */
 int LocateElem(LinkList L,ElemType e)
 {
 	LinkList p;
 	inti = 0;
 	p = L->next;//p指向第一个结点
 	while(p)//没到表尾
 	{
 		if(p)
 		{
 			i++;
 		}
 		if(e == p->data)
 		{
 			returni;
 		}
 		p = p->next;
 	}
 	return ERROR;
 }
 
 //返回线性表L的元素个数
 int ListLength(LinkList L)
 {
 	int j = 0;
 	LinkList p;
 	p = L;
 	while(p)//p不为空或者计数器j还没有等于i时，循环继续
 	{
 		p = p->next;//让p指向下一个节点,计数应该从下个开始计数，头节点不算
 		if(p)
 		{
 			j++;
 		}
 	}
 	return j;
 }
 
 
 int ListPrint(LinkList L)
 {
 	LinkList p;
 	p = L->next;//p指向第一个结点
 	if(!p)//线性表为空
 	{
 		printf("[%s %d]链表为空\n",__FUNCTION__,__LINE__);
 		return ERROR;
 	}
 	while(p)//没到表尾
 	{
 		printf("[%s %d]元素:%d\n",__FUNCTION__,__LINE__,p->data);
 		p = p->next;
 	}
 	return OK;
 }
 
 
 int main()
 {
 LinkList L;
 	int i = 0;
 	int ret = ERROR;
 	ElemType e = 0;
 	printf("[%s %d]------------头插创建整表数据------------------\n",__FUNCTION__,__LINE__);
 	CreateListHead(&L,5);
 	ret = ListPrint(L);
 	if(ERROR == ret)
 	{
 		printf("[%s %d]打印链表失败\n",__FUNCTION__,__LINE__);
 	}
 
 	printf("[%s %d]------------尾插创建整表数据------------------\n",__FUNCTION__,__LINE__);
 	CreateListTail(&L,15);
 	ret = ListPrint(L);
 	if(ERROR == ret)
 	{
 		printf("[%s %d]打印链表失败\n",__FUNCTION__,__LINE__);
 	}
 	//插入数据
 	printf("[%s %d]------------插入数据------------------\n",__FUNCTION__,__LINE__);
 	ret = ListInsert(&L,5,22);
 	if(ERROR == ret)
 	{
 		printf("[%s %d]插入数据失败，位置:%d,元素:%d\n",__FUNCTION__,__LINE__,i,i);
 	}
 
 	//打印链表
 	ret = ListPrint(L);
 	if(ERROR == ret)
 	{
 		printf("[%s %d]打印链表失败\n",__FUNCTION__,__LINE__);
 	}
 
 	//获取单个元素
 	printf("[%s %d]------------获取单个元素------------------\n",__FUNCTION__,__LINE__);
 	ret = GetElem(L,5,&e);
 	if(ERROR == ret)
 	{
 		printf("[%s %d]获取位置5的数据失败\n",__FUNCTION__,__LINE__);
 	}
 	else
 	{
 		printf("[%s %d]e:%d\n",__FUNCTION__,__LINE__,e);
 	}
 	//获取长度
 	printf("[%s %d]------------获取长度------------------\n",__FUNCTION__,__LINE__);
 	ret = ListLength(L);
 	printf("[%s %d]链表长度:%d\n",__FUNCTION__,__LINE__,ret);
 
 	printf("[%s %d]------------检查元素------------------\n",__FUNCTION__,__LINE__);
 	ret = LocateElem(L,22);
 	if(ERROR != ret)
 	{
 		printf("[%s %d]22是链表中元素，位置:%d\n",__FUNCTION__,__LINE__,ret);
 	}
 	else
 	{
 		printf("[%s %d]22不是链表中元素\n",__FUNCTION__,__LINE__);
 	}
 
 	//删除数据
 	printf("[%s %d]------------删除数据------------------\n",__FUNCTION__,__LINE__);
 	ret = ListDelete(&L,5,&e);
 	if(ERROR == ret)
 	{
 		printf("[%s %d]删除失败\n",__FUNCTION__,__LINE__);
 	}
 	else
 	{
 		printf("[%s %d]删除成功e:%d\n",__FUNCTION__,__LINE__,e);
 	}
 
 	//打印链表
 	ret = ListPrint(L);
 	if(ERROR == ret)
 	{
 		printf("[%s %d]打印链表失败\n",__FUNCTION__,__LINE__);
 	}
 	printf("[%s %d]------------清空链表------------------\n",__FUNCTION__,__LINE__);
 	if(ListEmpty(L))
 	{
 		printf("[%s %d]链表不为空\n",__FUNCTION__,__LINE__);
 	}
 	else
 	{
 		printf("[%s %d]链表为空\n",__FUNCTION__,__LINE__);
 	}
 	ClearList(&L);
 	if(ListEmpty(L))
 	{
 		printf("[%s %d]链表不为空\n",__FUNCTION__,__LINE__);
 	}
 	else
 	{
 		printf("[%s %d]链表为空\n",__FUNCTION__,__LINE__);
 	}
 
 	return OK;
 }

[Center]: /images/20220705/0428b132f0b544e7a343213418e98949.png
[Center 1]: /images/20220705/72ef146328e3471f8b3f94552bab4eaa.png
[Center 2]: /images/20220705/f324b4a490fb4f70b1dfef07e22ecd10.png