线性表的链式存储方式

忘是亡心i 2022-08-23 00:55 141阅读 0赞

之前实现了线性表的顺序存储方式发现顺序存储方式是存在缺陷的，就是插入和删除时需要移动大量的元素，显而易见这种顺序存储的方式需要耗费大量的时间，那仫我们有没有办法解决它呢？这就是我今天要实现的线性表的链式存储结构...

我们知道在顺序表中它的物理存储位置是连续的所以当我们以顺序表的形式实现线性表的插入和删除时我们需要移动大量的元素； 假设线性表中的每个数据存储的位置存在间隙我们是不是就可以不用移动大量的元素了呢？此时我们只需要让这个元素知道它的下一个元素的位置就可以了. 这就是链式表的存储思路.

要理解链式表首先我们需要理解头指针和头结点

头指针:我们通常把链表中第一个节点的存储位置叫头指针， 整个链表的存取就是从头指针开始的.

头结点: 通常我们在单链表的第一个节点前附设一个结点叫头结点， 头结点的数据域可以不存储任何信息指针域用来存储指向第一个节点的指针.

![Center][]

因此我们实现链式表是可以有两种方式：一种是通过头结点的方式访问后续链表，一种是通过头指针的方式访问后续链表在这里我只实现用头指针的方式.下面就让我们来看链式表的存储结构

typedef int DataType;
    
    typedef struct LinkNode
    {
    	DataType data;
    	struct LinkNode *next;
    }LinkNode,*pLinkNode;    
    
    typedef struct LinkList
    {
    	LinkNode *phead;
    }LinkList,*pLinkList;

从链式表的存储结构可知链表中的一个结点包括数据域和指针域，而定义结构LinkList则是可以在函数传参时不需要再添加指针的标志符号'\*'而已本身并没有什仫实际的意义。

好了说了这仫多也该进入我们的正题了-实现线性表的链式存储方式，先让我们来看看这个链式结构有什仫功能吧！

void Init_LinkList(pLinkList plist);          //初始化
    void Free_LinkList(pLinkList plist);          //释放空间
    void Push_back(pLinkList plist,DataType x);   //尾插
    void Pop_back(pLinkList plist);               //尾删
    void Push_Front(pLinkList plist,DataType x);  //头插
    void Pop_Front(pLinkList plist);              //头删
    void Print_LinkList(pLinkList plist);         //打印结点
    pLinkNode Find_NUM(pLinkList plist,DataType x); //找结点
    void Insert_Back(pLinkList plist,pLinkNode pos,DataType x);   //指定位置pos后插入
    void Insert_Front(pLinkList plist,pLinkNode pos,DataType x);  //指定位置pos前插入
    void Remove_LinkList(pLinkList plist,DataType x);             //删除指定元素
    void RemoveAll_LinkList(pLinkList plist,DataType x);          //删除所有指定元素
    void Bubble_Sort(pLinkList plist);                            //对链表排序
    void Erase_LinkList(pLinkList plist,pLinkNode pos);

<尾插和尾删>

@尾插

此时我们需要考虑两种情况的链式表

(1).链表为空，此时只需要将新开辟的结点赋给头指针所指向的下一个结点就可以了；

(2).存在元素，此时我们需要找到最后一个元素并把最后一个元素的指针域修改为指向新开辟的结点就可以了；

@尾删

此时我们需要考虑的有三种情况

(1).链表为空，直接返回；

(2).链表只有一个结点，只需要free第一个节点就可以了；

(3).链表存在不止一个结点，在这里提供两种思路一种是：在找最后一个结点的时候将它的前一个结点也保存下来，因为我们需要将倒数第二个结点的指针域置为空；另一种思路就是不需要记录它的前一个结点，我们只需要让cur指针找到链表的倒数第二个结点就可以了，我们可以通过倒数第二个结点的指针域找到最后一个结点；

尾插和尾删的代码实现如下：

void Push_back(pLinkList plist,DataType x)    //尾插
    {
    	//1.是空链表 2.有结点
    	pLinkNode cur=NULL;
    	pLinkNode newNode=NULL;
    	assert(plist);
    	cur=plist->phead;
    	newNode=Create_Node(x);
    	if(NULL == cur)           //是空链表
    	{
    		plist->phead=newNode;
    	}
    	else                      //有结点
    	{
    		while(cur->next != NULL)    //找到最后一个结点
    		{
    			cur=cur->next;
    		}
    		cur->next=newNode;
    	}
    }
    
    void Pop_back(pLinkList plist)          //尾删
    {
    	//1.空链表 2.只有一个结点 3.大于1个结点
    	pLinkNode tmp=NULL;
    	pLinkNode cur=plist->phead;
    	assert(plist);
    	if(NULL == plist->phead)         //空链表
    	{	
    		return ;
    	}
    	else if(NULL == plist->phead->next)   //只有一个结点
    	{
    		free(plist->phead);
    		plist->phead=NULL;
    	}
    	else
    	{
    		while(cur->next != NULL)         //方法二:存储最后一个结点的前一个结点
    		{
    			tmp=cur;
    			cur=cur->next;
    		}
    		free(cur);
    		cur=NULL;
    		tmp->next=NULL;
    		//while(cur->next->next != NULL)    方法一
    		//{
    		//	cur=cur->next;
    		//}
    		//free(cur->next);
    		//cur->next=NULL;
    	}
    }

![Center 1][]

<头插和头删>

@头插

@头删

这两个功能都是需要考虑空链表和有结点的情况，但是在头插中我们可以先将新开辟结点的指针域指向原链表的第一个元素也就是首元结点，再将头指针指向新开辟的结点就可以简化代码了；因为当是空链表时上述解决思路可以将空指针赋给新开辟的结点满足题意，头插和头删的实现代码如下：

void Push_Front(pLinkList plist,DataType x)  //头插
    {
    	//1.空链表 2.有结点
    	pLinkNode newNode=NULL;
    	assert(plist);
    	newNode=Create_Node(x);
    	newNode->next=plist->phead;
    	plist->phead=newNode;
    }
    
    void Pop_Front(pLinkList plist)              //头删
    {
    	//1.空链表 2.有元素的结点
    	pLinkNode tmp=NULL;
    	if(NULL == plist->phead)         //空链表
    	{	
    		return ;
    	}
    	else           //有元素的结点
    	{
    		tmp=plist->phead;
    		plist->phead=tmp->next;
    		free(tmp);
    		tmp=NULL;
    	}
    }

![Center 2][]

![Center 3][]

<指定位置pos前插入和指定位置后插入>

这两种情况都需要考虑两种情况，空链表则直接调用头插函数，如果有结点且在指定位置后插入我们需要记录该指定位置然后利用该位置的指针域访问下一个结点修改其指针指向关系；如果在指定位置前插入我们可以不需要找到该pos结点只需要找到该pos结点的前一个结点，可以通过前一个结点访问该pos结点并修改其指针指向关系;

@指定位置pos前插入

@指定位置后插入

void Insert_Back(pLinkList plist,pLinkNode pos,DataType x)  //指定位置pos后插入
    {
    	//1.空链表 2.有结点的链表
    	pLinkNode newNode=NULL;
    	pLinkNode cur=plist->phead;
    	assert(plist);
    	newNode=Create_Node(x);
    	if(NULL == plist->phead->next)   //空链表直接头插
    	{
    		Push_Front(plist,x);
    	}
    	else            //有结点的链表
    	{
    		while(cur != pos)
    		{
    			cur=cur->next;
    		}
    		newNode->next=cur->next;
    		cur->next=newNode;
    	}
    }
    
    void Insert_Front(pLinkList plist,pLinkNode pos,DataType x)  //指定位置pos前插入
    {
    	pLinkNode newNode=NULL;
    	pLinkNode cur=plist->phead;
    	assert(plist);
    	newNode=Create_Node(x);
    	if(NULL == plist->phead->next)   //空链表直接头插
    	{
    		Push_Front(plist,x);
    	}
    	else
    	{
    		while(cur->next != pos)
    		{
    			cur=cur->next;
    		}
    		newNode->next=cur->next;
    		cur->next=newNode;
    	}
    }

![Center 4][]

在这里原链表有三个结点，他们的数据域分别为1,2,3,通过上述两个函数将结点数据域为5的结点插入到数据域为2的结点的前面和后面，结果如上图.

<删除指定元素和删除所有指定元素>

@删除指定元素

@删除所有指定元素

两个函数的实现方法基本类似，在删除指定元素时我们只删除了第一个找到的指定元素的结点，在这里我们需要将该删除结点的前一个结点保存下来，之后将它的指针域指向该删除结点的下一个结点；在删除所有指定元素时我们可以仿照删除指定元素的方法先将第一个找到的指定元素删除再从该位置往后继续查找指定元素的结点找到并删除；

void Remove_LinkList(pLinkList plist,DataType x)   //删除指定元素
    {
    	pLinkNode ret=NULL;
    	pLinkNode cur=plist->phead;
    	assert(plist);
    	if(NULL == plist->phead)     //空链表
    	{
    		return ;
    	}
    	else
    	{
    		ret=Find_NUM(plist,x);
    		while(cur->next != ret)  //cur保存的是要删除结点的前一个结点
    		{
    			cur=cur->next;
    		}
    		cur->next=ret->next;
    		free(ret);
    		ret=NULL;
    	}
    }
    
    void RemoveAll_LinkList(pLinkList plist,DataType x)//删除所有指定元素
    {
    	pLinkNode ret=NULL;
    	pLinkNode cur=plist->phead;
    	assert(plist);
    	if(NULL == plist->phead)
    	{
    		return ;
    	}
    	else
    	{
    		while(cur->next != NULL)
    		{
    			ret=Find_NUM(plist,x);
    			while(cur->next != ret)
    			{
    				cur=cur++;
    			}
    			cur->next=ret->next;
    			free(ret);
    			ret=NULL;
    			cur=cur->next;
    		}
    	}
    }

![Center 5][]

其他的函数就不在这里一一分析了，程序源代码如下：

text.c

#include"LinkList.h"
    
    void text1()  
    {
    	LinkList plist;
    	Init_LinkList(&plist);
    	Push_back(&plist,1);
    	Push_back(&plist,2);
    	Push_back(&plist,3);
    	Push_back(&plist,4);
    	Push_back(&plist,5);
    	Print_LinkList(&plist);   //1->2->3->4->5->over
    	Pop_back(&plist);
    	Print_LinkList(&plist);   //1->2->3->4->over
    	Pop_back(&plist);
    	Print_LinkList(&plist);   //1->2->3->over
    	Pop_back(&plist);
    	Print_LinkList(&plist);   //1->2->over
    	Pop_back(&plist);
    	Print_LinkList(&plist);   //1->over
    	Pop_back(&plist);
    	Print_LinkList(&plist);    //over
    	Free_LinkList(&plist);
    }
    
    void text2()
    {
    	LinkList plist;
    	Init_LinkList(&plist);
    	Push_Front(&plist,1);
    	Push_Front(&plist,2);
    	Push_Front(&plist,3);
    	Push_Front(&plist,4);
    	Push_Front(&plist,5);
    	Print_LinkList(&plist);   //5->4->3->2->1->over
    	Pop_Front(&plist);
    	Print_LinkList(&plist);   //4->3->2->1->over
    	Pop_Front(&plist);
    	Print_LinkList(&plist);   //3->2->1->over
    	Pop_Front(&plist);
    	Print_LinkList(&plist);   //2->1->over
    	Pop_Front(&plist);
    	Print_LinkList(&plist);   //1->over
    	Pop_Front(&plist);
    	Print_LinkList(&plist);   //over
    	Free_LinkList(&plist);
    }
    
    void text3()
    {
    	LinkList plist;
    	Init_LinkList(&plist);
    	Push_back(&plist,1);
    	Push_back(&plist,2);
    	Push_back(&plist,3);
    	Print_LinkList(&plist);   //1->2->3->over
    	Insert_Back(&plist,Find_NUM(&plist,2),5);
    	Print_LinkList(&plist);   //1->2->5->3->over
    	Insert_Front(&plist,Find_NUM(&plist,2),5);
    	Print_LinkList(&plist);  //1->5->2->5->3->over
    	Remove_LinkList(&plist,5);
    	Print_LinkList(&plist);  //1->5->5->3->over
    	Free_LinkList(&plist);
    }
    
    void text4()
    {
    	LinkList plist;
    	Init_LinkList(&plist);
    	Push_back(&plist,1);
    	Push_back(&plist,2);
    	Push_back(&plist,3);
    	Print_LinkList(&plist);   //1->2->3->over
    	Insert_Back(&plist,Find_NUM(&plist,2),5);
    	Insert_Front(&plist,Find_NUM(&plist,2),5);
    	Print_LinkList(&plist);   //1->5->2->5->3->over
    	RemoveAll_LinkList(&plist,5);
    	Print_LinkList(&plist);  //1->2->3->over
    	Push_back(&plist,6);
    	Push_back(&plist,5);
    	Bubble_Sort(&plist);
    	Print_LinkList(&plist);  //1->2->3->5->6->over 
    	Erase_LinkList(&plist,Find_NUM(&plist,3)); 
    	Print_LinkList(&plist);    //1->2->5->6->over 
    	Free_LinkList(&plist);
    }
    int main()
    {
    	//text1();
    	//text2();
    	//text3();
    	text4();
    	system("pause");
    	return 0;
    }

LinkList.h

#define _CRT_SECURE_NO_WARNINGS
    
    #ifndef __LINKLIST_H__
    #define __LINKLIST_H__
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    
    typedef int DataType;
    
    typedef struct LinkNode
    {
    	DataType data;
    	struct LinkNode *next;
    }LinkNode,*pLinkNode;    
    
    typedef struct LinkList
    {
    	LinkNode *phead;
    }LinkList,*pLinkList;    
    
    void Init_LinkList(pLinkList plist);          //初始化
    void Free_LinkList(pLinkList plist);          //释放空间
    void Push_back(pLinkList plist,DataType x);   //尾插
    void Pop_back(pLinkList plist);               //尾删
    void Push_Front(pLinkList plist,DataType x);  //头插
    void Pop_Front(pLinkList plist);              //头删
    void Print_LinkList(pLinkList plist);         //打印结点
    pLinkNode Find_NUM(pLinkList plist,DataType x); //找结点
    void Insert_Back(pLinkList plist,pLinkNode pos,DataType x);   //指定位置pos后插入
    void Insert_Front(pLinkList plist,pLinkNode pos,DataType x);  //指定位置pos前插入
    void Remove_LinkList(pLinkList plist,DataType x);             //删除指定元素
    void RemoveAll_LinkList(pLinkList plist,DataType x);          //删除所有指定元素
    void Bubble_Sort(pLinkList plist);                            //对链表排序
    void Erase_LinkList(pLinkList plist,pLinkNode pos);
    
    #endif __LINKLIST_H__

LinkList.c

#include"LinkList.h"
    
    void Init_LinkList(pLinkList plist)       //初始化
    {
    	assert(plist);
    	plist->phead=NULL;
    }
    
    pLinkNode Create_Node(DataType x)     //创建新结点
    {
    	pLinkNode newNode=(pLinkNode)malloc(sizeof(LinkNode));
    	if(NULL == newNode)
    	{
    		printf("out of memory\n");
    		exit(EXIT_FAILURE);
    	}
    	newNode->data=x;
    	newNode->next=NULL;
    	return newNode;
    }
    
    void Free_LinkList(pLinkList plist)      //释放空间
    {
    	pLinkNode cur=plist->phead;
    	assert(plist);
    	while(cur != NULL)
    	{
    		pLinkNode tmp=cur;
    		cur=cur->next;
    		free(tmp);
    		tmp=NULL;       
    	}
    	plist->phead=NULL;
    }
    
    void Push_back(pLinkList plist,DataType x)    //尾插
    {
    	//1.是空链表 2.有结点
    	pLinkNode cur=NULL;
    	pLinkNode newNode=NULL;
    	assert(plist);
    	cur=plist->phead;
    	newNode=Create_Node(x);
    	if(NULL == cur)           //是空链表
    	{
    		plist->phead=newNode;
    	}
    	else                      //有结点
    	{
    		while(cur->next != NULL)    //找到最后一个结点
    		{
    			cur=cur->next;
    		}
    		cur->next=newNode;
    	}
    }
    
    void Pop_back(pLinkList plist)          //尾删
    {
    	//1.空链表 2.只有一个结点 3.大于1个结点
    	pLinkNode tmp=NULL;
    	pLinkNode cur=plist->phead;
    	assert(plist);
    	if(NULL == plist->phead)         //空链表
    	{	
    		return ;
    	}
    	else if(NULL == plist->phead->next)   //只有一个结点
    	{
    		free(plist->phead);
    		plist->phead=NULL;
    	}
    	else
    	{
    		while(cur->next != NULL)         //方法二:存储最后一个结点的前一个结点
    		{
    			tmp=cur;
    			cur=cur->next;
    		}
    		free(cur);
    		cur=NULL;
    		tmp->next=NULL;
    		//while(cur->next->next != NULL)    方法一
    		//{
    		//	cur=cur->next;
    		//}
    		//free(cur->next);
    		//cur->next=NULL;
    	}
    }
    
    void Push_Front(pLinkList plist,DataType x)  //头插
    {
    	//1.空链表 2.有结点
    	pLinkNode newNode=NULL;
    	assert(plist);
    	newNode=Create_Node(x);
    	newNode->next=plist->phead;
    	plist->phead=newNode;
    }
    
    void Pop_Front(pLinkList plist)              //头删
    {
    	//1.空链表 2.有元素的结点
    	pLinkNode tmp=NULL;
    	if(NULL == plist->phead)         //空链表
    	{	
    		return ;
    	}
    	else           //有元素的结点
    	{
    		tmp=plist->phead;
    		plist->phead=tmp->next;
    		free(tmp);
    		tmp=NULL;
    	}
    }
    
    void Print_LinkList(pLinkList plist)    //打印结点
    {
    	pLinkNode cur=plist->phead;
    	while(cur != NULL)
    	{
    		printf("%d->",cur->data);
    		cur=cur->next;
    	}
    	printf("over\n");
    }
    
    pLinkNode Find_NUM(pLinkList plist,DataType x) //找结点
    {
    	pLinkNode cur=plist->phead;
    	assert(plist);
    	while(cur != NULL)
    	{
    		if(cur->data == x)
    		{
    			return cur;
    		}
    		cur=cur->next;
    	}
    	return NULL;
    }
    
    void Insert_Back(pLinkList plist,pLinkNode pos,DataType x)  //指定位置pos后插入
    {
    	//1.空链表 2.有结点的链表
    	pLinkNode newNode=NULL;
    	pLinkNode cur=plist->phead;
    	assert(plist);
    	newNode=Create_Node(x);
    	if(NULL == plist->phead->next)   //空链表直接头插
    	{
    		Push_Front(plist,x);
    	}
    	else            //有结点的链表
    	{
    		while(cur != pos)
    		{
    			cur=cur->next;
    		}
    		newNode->next=cur->next;
    		cur->next=newNode;
    	}
    }
    
    void Insert_Front(pLinkList plist,pLinkNode pos,DataType x)  //指定位置pos前插入
    {
    	pLinkNode newNode=NULL;
    	pLinkNode cur=plist->phead;
    	assert(plist);
    	newNode=Create_Node(x);
    	if(NULL == plist->phead->next)   //空链表直接头插
    	{
    		Push_Front(plist,x);
    	}
    	else
    	{
    		while(cur->next != pos)
    		{
    			cur=cur->next;
    		}
    		newNode->next=cur->next;
    		cur->next=newNode;
    	}
    }
    
    void Remove_LinkList(pLinkList plist,DataType x)   //删除指定元素
    {
    	pLinkNode ret=NULL;
    	pLinkNode cur=plist->phead;
    	assert(plist);
    	if(NULL == plist->phead)     //空链表
    	{
    		return ;
    	}
    	else
    	{
    		ret=Find_NUM(plist,x);
    		while(cur->next != ret)  //cur保存的是要删除结点的前一个结点
    		{
    			cur=cur->next;
    		}
    		cur->next=ret->next;
    		free(ret);
    		ret=NULL;
    	}
    }
    
    void RemoveAll_LinkList(pLinkList plist,DataType x)//删除所有指定元素
    {
    	pLinkNode ret=NULL;
    	pLinkNode cur=plist->phead;
    	assert(plist);
    	if(NULL == plist->phead)
    	{
    		return ;
    	}
    	else
    	{
    		while(cur->next != NULL)
    		{
    			ret=Find_NUM(plist,x);
    			while(cur->next != ret)
    			{
    				cur=cur++;
    			}
    			cur->next=ret->next;
    			free(ret);
    			ret=NULL;
    			cur=cur->next;
    		}
    	}
    }
    
    void Bubble_Sort(pLinkList plist)       //对链表排序
    {
    	pLinkNode cur=plist->phead;
    	pLinkNode cmp=plist->phead;
    	DataType flag=0;
    	while(cur->next != NULL)
    	{
    		flag=0;
    		while(cmp->next != NULL)
    		{
    			if(cmp->data > cmp->next->data)   //升序排列
    			{
    				DataType tmp=cmp->data;
    				cmp->data=cmp->next->data;
    				cmp->next->data=tmp;
    				flag=1;
    			}
    			cmp=cmp->next;
    		}
    		cur=cur->next;
    		if(flag == 0)
    			break;
    	}
    }
    
    void Erase_LinkList(pLinkList plist,pLinkNode pos)
    {
    	pLinkNode cur=plist->phead;                                            
    	assert(plist);
    	while(cur->next != pos)
    	{
    		cur=cur->next;
    	}
    	cur->next=pos->next;
    	free(pos);
    	pos=NULL;
    }

困难就是纸老虎它永远只会吓唬胆小的人，所以做一个胆大的人面对困难迎面而上，或许坦途就在前方.

[Center]: /images/20220722/b984584bb18d42f7b49b5faaafac8ec0.png
[Center 1]: /images/20220722/b301eef0a95d476e845ed5f487e4cc9a.png
[Center 2]: /images/20220722/9fc3b91dfa8a49f4b289ed65924e2b11.png
[Center 3]: /images/20220722/045b632079de4b5492cb22d962e3ade9.png
[Center 4]: /images/20220722/3e4bdd81f8194dae9852a0b883ac36d0.png
[Center 5]: /images/20220722/4113c49d6fda4362a8866ce62b67766e.png