双向链表的存储设计与实现(C语言版本)

╰半夏微凉° 2022-05-24 01:06 147阅读 0赞

双向链表的插入操作：

![70][]

双向链表的删除操作：

![70 1][]

//DLinkList.h
    #ifndef _DLINKLIST_H_
    #define _DLINKLIST_H_
    
    //双向链表的存储结构
    //结点中包含后继结点的地址的指针域可以理解为指向下一个结构体(结点)
    //(这里不包含数据域,是实现了 链表的api(链表的算法) 和 具体的数据分离)
    typedef struct _tag_DLinkListNode
    {
    	struct _tag_DLinkListNode *next;//指向后继的next指针
    	struct _tag_DLinkListNode *pre;//指向前驱的pre指针
    }DLinkListNode;
    
    //为void 再重新多取一个名字，DLinkList等价于void
    //typedef + 已有的数据类型+新的数据类型(自己取的新名字)
    typedef void DLinkList;
    
    
    //创建并且返回一个空的双向链表
    DLinkList* DLinkList_Create();
    
    //销毁一个双向链表list 
    void DLinkList_Destroy(DLinkList* list);
    
    //将一个双向链表list中的所有元素清空, 循环链表回到创建时的初始状态  
    void DLinkList_Clear(DLinkList* list);
    
    //返回一个双向链表list中的元素个数
    int DLinkList_Length(DLinkList* list);
    
    //向一个双向链表list的pos位置处插入元素
    int DLinkList_Insert(DLinkList* list, DLinkList* node, int pos);
    
    //获取一个双向链表list中pos位置处的元素
    DLinkListNode* DLinkList_Get(DLinkList* list, int pos);
    
    //删除一个双向链表list中pos位置处的元素,返回值为被删除的元素,NULL表示删除失败
    DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);
    
    //add
    
    //直接指定删除双向链表中的某个数据元素
    DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);
    
    //将游标重置指向双向链表中的第一个数据元素
    DLinkListNode* DLinkList_SliderReset(DLinkList* list);
    
    //双向链表 获取当前游标指向的数据元素
    DLinkListNode* DLinkList_SliderCurrent(DLinkList* list);
    
    //将游标移动指向到双向链表中的下一个数据元素
    DLinkListNode* DLinkList_SliderNext(DLinkList* list);
    
    //将游标移动指向双向链表中的前一个数据元素
    DLinkListNode* DLinkList_SliderPre(DLinkList *list);
    
    #endif

//DLinkList.c
 #include <stdlib.h> 
 #include <string.h> 
 #include <stdio.h> 
 #include "DLinkList.h"
 
 //定义双向链表的头结点 双向链表头结点：表示链表中第一个节点,包含指向第一个数据元素的指针以及链表自身的一些信息
 //这样能把所有结点串起来
 typedef struct _tag_DLinkList
 {
 	DLinkListNode header; //要有个头指针---指向头结点的指针
 	DLinkListNode *slider;//在双向链表中可以定义一个“当前指针”，这个指针通常称为游标，可以通过游标来遍历链表中所有元素
 	int length;//链表的长度
 }TDLinkList;
 //创建并且返回一个空的双向链表
 DLinkList* DLinkList_Create()
 {
 	//1 申请动态内存空间
 	TDLinkList *tmp = (TDLinkList *)malloc(sizeof(TDLinkList));
 	if (NULL == tmp)
 	{
 		printf("func err malloc:%d\n");
 		return NULL;
 	}
 	//2 让开辟的内存 完成链式线性表初始化 
 	memset(tmp, 0, sizeof(TDLinkList));
 	//3 链表的初始化
 	tmp->header.next = NULL;
 	tmp->header.pre = NULL;
 	tmp->slider = NULL;
 	tmp->length = 0;
 	return tmp;
 }
 
 //销毁一个双向链表list 
 //由于数据元素节点的生命周期不是由链表算法管理的，所以只需要销毁申请的头节点元素即可
 void DLinkList_Destroy(DLinkList* list)
 {
 	//1 缓存下来 进行操作
 	TDLinkList *tmp = NULL;
 	tmp = (TDLinkList *)list;
 	if (NULL == list)
 	{
 		printf("func err DLinkList_Destroy()\n");
 	}
 	//2 释放头结点空间 
 	if (tmp != NULL)
 	{
 		free(tmp);
 	}
 }
 
 
 //将一个双向链表list中的所有元素清空, 双向链表回到创建时的初始状态 
 void DLinkList_Clear(DLinkList* list)
 {
 	//1 缓存下来 进行操作
 	TDLinkList *tmp = NULL;
 	tmp = (TDLinkList *)list;
 	if (NULL == list)
 	{
 		printf("func err DLinkList_Clear()\n");
 	}
 	//2 清空链表
 	tmp->header.next = NULL;
 	tmp->header.pre = NULL;
 	tmp->slider = NULL;
 	tmp->length = 0;
 }
 
 
 //返回一个双向链表list中的元素个数
 int DLinkList_Length(DLinkList* list)
 {
 	int ret = 0;
 	//1 缓存下来 进行操作
 	TDLinkList *tmp = NULL;
 	tmp = (TDLinkList *)list;
 	if (NULL == list)
 	{
 		ret = -1;
 		printf("func err DLinkList_Length():%d\n", ret);
 		return ret;
 	}
 	ret = tmp->length;
 	return ret;
 }
 
 
 //向一个双向链表list的pos位置处插入元素
 int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos)
 {
 	int ret = 0;
 	//1 缓存下来 进行操作
 	TDLinkList *tmp = NULL;
 	tmp = (TDLinkList *)list;
 	//辅助指针 用来遍历当前指针位置
 	DLinkListNode *pCur = NULL;
 	//辅助指针 用来缓存当前指针下移位置
 	DLinkListNode *pNext = NULL;
 	if (NULL == list || NULL == node || pos < 0)
 	{
 		ret = -1;
 		printf("func err (NULL == list || NULL == node || pos < 0):%d\n", ret);
 		return ret;
 	}
 	//注意：容错修正,假如链表当前长度为5,你插入pos位置是10,这个时候可以做容错修正,直接修正为尾插法 
 	if (pos > tmp->length)
 	{
 		pos = tmp->length;
 	}
 	//1 当前指针 初始化 指向 头结点
 	pCur = &(tmp->header);
 	//2 进行遍历 找到插入位置
 	for (int i = 0; i < pos; i++)
 	{
 		pCur = pCur->next;
 	}
 	//3 进行插入操作
 	//进行缓存pCur next域
 	pNext = pCur->next;
 	//插入操作
 	pCur->next = node;//1
 	node->next = pNext;//2
 
 	if (pNext != NULL)
 	{
 		pNext->pre = node;//3 若是尾插法,就不需要这部操作
 	}
 	node->pre = NULL;//若是头插法,需要这部操作,如图1 4
 	if (pCur !=(DLinkListNode *)tmp)//若不是头插法,普通插入如图2 3情况 
 	{
 		node->pre = pCur;//4
 	}
 	//若第一次插入结点 让游标指向0号结点
 	if (tmp->length == 0)
 	{
 		tmp->slider = node;
 	}
 
 	//4 链表长度++
 	tmp->length++;
 	return ret;
 }
 
 
 //获取一个双向链表list中pos位置处的元素
 DLinkListNode* DLinkList_Get(DLinkList* list, int pos)
 {
 	//1 缓存下来 进行操作
 	TDLinkList *tmp = (TDLinkList *)list;
 	//辅助指针 用来遍历当前指针位置
 	DLinkListNode *pCur = NULL;
 	if (NULL == list || pos < 0)
 	{
 		printf("func err DLinkList_Get\n");
 		return NULL;
 	}
 	//2 当前指针 初始化 指向 头结点
 	pCur = &(tmp->header);
 	//3 搜索要获得的结点
 	for (int i = 0; i < pos; i++)
 	{
 		pCur = pCur->next;
 	}
 	return pCur->next;
 }
 
 
 //删除一个循环链表list中pos位置处的元素,返回值为被删除的元素,NULL表示删除失败
 DLinkListNode* DLinkList_Delete(DLinkList* list, int pos)
 {
 	//1 缓存下来 进行操作
 	TDLinkList *tmp = (TDLinkList *)list;
 	//辅助指针 用来遍历当前指针位置
 	DLinkListNode *pCur = NULL;
 	//辅助指针 用来缓存删除结点下一元素
 	DLinkListNode *pAfter = NULL;
 	//辅助指针 用来缓存删除元素
 	DLinkListNode *DeletNode = NULL;
 	if (NULL == list || pos < 0)
 	{
 		printf("func err DLinkList_Delete\n");
 		return NULL;
 	}
 	//删除位置的pos点不能大于链表长度 做一个容错修正 
 	//当删除位置pos大于双向链表长度,就尾部删除
 	if (pos > DLinkList_Length(tmp))
 	{
 		pos = tmp->length;
 	}
 	//2 当前指针 初始化 指向 头结点
 	pCur = &(tmp->header);
 	//3 搜索要获得的结点
 	for (int i = 0; i < pos; i++)
 	{
 		pCur = pCur->next;
 	}
 	//4 缓存结点位置
 	DeletNode = pCur->next;
 	pAfter = DeletNode->next;
 	//5 开启删除操作 分三种情况
 	pCur->next = pAfter;//普通情况1
 	if (pAfter !=NULL)
 	{
 		pAfter->pre = pCur;//普通情况2
 	}
 	DeletNode->pre = NULL;//第三种情况需要置空 第二种已经自己置空
 
 	//6 链表长度--
 	tmp->length--;
 
 	//7 若删除元素为游标所指元素 需要后移
 	if (tmp->slider == DeletNode)
 	{
 		tmp->slider = pAfter;
 	}
 
 	//8 若删除元素后链表长度为0 
 	if (tmp->length == 0)
 	{
 		tmp->header.next = NULL;
 		tmp->header.pre = NULL;
 		tmp->slider = NULL;
 	}
 	return DeletNode;
 }
 
 
 //add
 
 //根据结点 直接指定删除链表中的某个数据元素
 DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node)
 {
 	//1 缓存下来 进行操作
 	TDLinkList *tmp = (TDLinkList *)list;
 	//辅助指针 用来遍历当前指针位置
 	DLinkListNode *pCur = NULL;
 	//辅助指针 用来缓存删除元素
 	DLinkListNode *DeletNode = NULL;
 	if (NULL == list || 0 == node)
 	{
 		printf("func err DLinkList_DeleteNode\n");
 		return NULL;
 	}
 	//2 当前指针 初始化 指向 头结点
 	pCur = &(tmp->header);
 	//3 搜索要获得的结点
 	int i;
 	for ( i = 0; i < tmp->length; i++)
 	{
 		if (pCur->next == node)//根据删除结点搜索到要删除位置
 		{
 			DeletNode = pCur->next;//缓存删除元素
 			break;//这里搜索到要删除的结点,结束循环,否则会报错
 		}
 		pCur = pCur->next;
 	}
 	//4 根据pos位置删除元素
 	if (DeletNode != NULL)
 	{
 		DLinkList_Delete(tmp,i);
 	}
 	return DeletNode;
 }
 
 
 //将游标重置指向链表中的第一个数据元素
 DLinkListNode* DLinkList_SliderReset(DLinkList* list)
 {
 	//1 缓存下来 进行操作
 	TDLinkList *tmp = (TDLinkList *)list;
 	//辅助指针 用来缓存重置游标位置
 	DLinkListNode *tmpReset = NULL;
 	if (NULL == list)
 	{
 		printf("func err DLinkList_SliderReset\n");
 		return NULL;
 	}
 	if (tmp!=NULL)
 	{
 		tmp->slider = tmp->header.next;//重置指向第一个数据元素
 		tmpReset = tmp->slider;//缓存游标位置
 	}
 	return tmpReset;
 }
 
 
 //获取当前游标指向的数据元素
 DLinkListNode* DLinkList_SliderCurrent(DLinkList* list)
 {
 	//1 缓存下来 进行操作
 	TDLinkList *tmp = (TDLinkList *)list;
 	//辅助指针 用来缓存当前游标位置
 	DLinkListNode *tmpCur = NULL;
 	if (NULL == list)
 	{
 		printf("func err DLinkList_SliderCurrent\n");
 		return NULL;
 	}
 	if (tmp!=NULL)
 	{
 		tmpCur = tmp->slider;//缓存当前游标位置
 	}
 	return tmpCur;
 }
 
 
 //将游标移动指向到链表中的下一个数据元素
 DLinkListNode* DLinkList_SliderNext(DLinkList* list)
 {
 	//1 缓存下来 进行操作
 	TDLinkList *tmp = (TDLinkList *)list;
 	//辅助指针 用来缓存游标位置
 	DLinkListNode *tmpNext = NULL;
 	if (NULL == list)
 	{
 		printf("func err DLinkList_SliderNext\n");
 		return NULL;
 	}
 	if (tmp != NULL)
 	{
 		tmpNext = tmp->slider;//缓存当前游标位置
 		tmp->slider = tmpNext->next;//将游标下移
 	}
 	return tmpNext;
 }
 
 //将游标移动指向双向链表中的前一个数据元素
 DLinkListNode* DLinkList_SliderPre(DLinkList *list)
 {
 	//1 缓存下来 进行操作
 	TDLinkList *tmp = (TDLinkList *)list;
 	//辅助指针 用来缓存游标位置
 	DLinkListNode *tmpPre = NULL;
 	if (NULL == list)
 	{
 		printf("func err DLinkList_SliderPre\n");
 		return NULL;
 	}
 	if (tmp != NULL)
 	{
 		tmpPre = tmp->slider;//缓存当前游标位置
 		tmp->slider = tmpPre->pre;//将游标上移
 	}
 	return tmpPre;
 }

//双向链表的设计与实现测试框架
 //text.c
 #include <stdlib.h> 
 #include <string.h> 
 #include <stdio.h> 
 #include "DLinkList.h"//c里面.h和.cpp没有差别 但是c++里如果模块化编程，两个头文件都必须包含进来
 
 
 //业务结点
 typedef struct _tag_Teacher
 {
 	DLinkListNode node;//包含底层结点
 	//业务域
 	int age;
 
 }Teacher;
 
 
 int main()
 {
 	int ret = 0;
 	DLinkList *dlist = NULL;
 	Teacher t1, t2, t3, t4;
 	t1.age = 1;
 	t2.age = 2;
 	t3.age = 3;
 	t4.age = 4;
 	//1 创建并且返回一个空的双向链表
 	dlist = DLinkList_Create();
 	if (NULL == dlist)
 	{
 		ret = -1;
 		printf("func err DLinkList_Create:%d\n", ret);
 		return ret;
 	}
 	//2 向一个双向链表list的pos位置处插入元素
 	ret = DLinkList_Insert(dlist, (DLinkListNode *)&t1, DLinkList_Length(dlist));
 	if (ret != 0)
 	{
 		ret = -2;
 		printf("func err DLinkList_Insert:%d\n", ret);
 		return ret;
 	}
 	ret = DLinkList_Insert(dlist, (DLinkListNode *)&t2, DLinkList_Length(dlist));
 	ret = DLinkList_Insert(dlist, (DLinkListNode *)&t3, DLinkList_Length(dlist));
 	ret = DLinkList_Insert(dlist, (DLinkListNode *)&t4, DLinkList_Length(dlist));
 
 	//返回一个双向链表list中的元素个数
 	ret = DLinkList_Length(dlist);
 	printf("%d ",ret);
 	printf("\n========================我是分界线====================\n");
 	//遍历双向链表
 	for (int i = 0; i < DLinkList_Length(dlist); i++)
 	{
 		//获取游标所指元素,然后游标下移
 		//双向链表 获取当前游标指向的数据元素
 		Teacher *tmp = (Teacher *)DLinkList_SliderNext(dlist);
 		if (NULL == tmp)
 		{
 			ret = -3;
 			printf("func err DLinkList_SliderNext:%d\n", ret);
 			return ret;
 		}
 		printf("%d ",tmp->age);
 	}
 	printf("\n========================我是分界线====================\n");
 	将一个双向链表list中的所有元素清空, 循环链表回到创建时的初始状态 
 	//DLinkList_Clear(dlist);
 	返回一个双向链表list中的元素个数
 	//ret = DLinkList_Length(dlist);
 	//printf("%d ", ret);
 
 	//再一次 遍历双向链表
 	for (int i = 0; i < DLinkList_Length(dlist); i++)
 	{
 		//获取一个双向链表list中pos位置处的元素
 		//DLinkListNode* DLinkList_Get(DLinkList* list, int pos);
 		Teacher *tmp = (Teacher *)DLinkList_Get(dlist,i);
 		if (NULL == tmp)
 		{
 			ret = -4;
 			printf("func err DLinkList_SliderCurrent:%d\n", ret);
 			return ret;
 		}
 		printf("%d ", tmp->age);
 	}
 	printf("\n========================我是分界线====================\n");
 	//将游标重置指向双向链表中的第一个数据元素
 	//DLinkListNode* DLinkList_SliderReset(DLinkList* list);
 
 	Teacher *tmp1 = (Teacher *)DLinkList_SliderReset(dlist);
 	printf("%d ", tmp1->age);
 
 	Teacher *tmp2 = (Teacher *)DLinkList_SliderNext(dlist);
 	printf("%d ", tmp2->age);
 
 	//直接指定删除双向链表中的某个数据元素
 	//DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);
 	tmp2 = (Teacher *)DLinkList_DeleteNode(dlist, (DLinkListNode*)tmp2);
 	printf("%d ", tmp2->age);
 
 	//删除一个双向链表list中pos位置处的元素,返回值为被删除的元素,NULL表示删除失败
 	//DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);
 	tmp2 = (Teacher *)DLinkList_Delete(dlist, 1);
 	printf("%d ", tmp2->age);
 
 
 	//将游标移动指向双向链表中的前一个数据元素
 	//DLinkListNode* DLinkList_SliderPre(DLinkList *list);
 	tmp2 = (Teacher *)DLinkList_SliderPre(dlist);
 	printf("%d ", tmp2->age);
 
 	DLinkList_Destroy(dlist);
 
 	system("pause");
 	return 0;
 }

# 双向链表 #

## 1、基本概念 ##

<table> 
 <tbody> 
 <tr> 
 <td>单链表的结点都只有一个指向下一个结点的指针 单链表的数据元素无法直接访问其前驱元素 逆序访问单链表中的元素是极其耗时的操作！</td> 
 </tr> 
 <tr> 
 <td>len = LinkList_Length(list); for (i=len-1; len&gt;=0; i++) //O(n) { LinkListNode *p = LinkList_Get(list, i); //O(n) //访问数据元素p中的元素 // }</td> 
 </tr> 
 <tr> 
 <td>双向链表的定义 在单链表的结点中增加一个指向其前驱的pre指针</td> 
 </tr> 
 <tr> 
 <td><img src="https://img-blog.csdn.net/20180517164942198?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" alt=""></td> 
 </tr> 
 <tr> 
 <td>双向链表拥有单链表的所有操作 创建链表 销毁链表 获取链表长度 清空链表 获取第pos个元素操作 插入元素到位置pos 删除位置pos处的元素</td> 
 </tr> 
 </tbody> 
</table>

## 2、设计与实现 ##

<table> 
 <tbody> 
 <tr> 
 <td>插入操作</td> 
 </tr> 
 <tr> 
 <td> <img src="https://img-blog.csdn.net/20180517165008807?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" alt=""> </td> 
 </tr> 
 <tr> 
 <td>删除操作</td> 
 </tr> 
 <tr> 
 <td><img src="https://img-blog.csdn.net/20180517165019817?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70" alt=""></td> 
 </tr> 
 <tr> 
 <td>双向链表的新操作</td> 
 </tr> 
 <tr> 
 <td>获取当前游标指向的数据元素 将游标重置指向链表中的第一个数据元素 将游标移动指向到链表中的下一个数据元素 将游标移动指向到链表中的上一个数据元素 直接指定删除链表中的某个数据元素</td> 
 </tr> 
 <tr> 
 <td>DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node); DLinkListNode* DLinkList_Reset(DLinkList* list); DLinkListNode* DLinkList_Current(DLinkList* list); DLinkListNode* DLinkList_Next(DLinkList* list); DLinkListNode* DLinkList_Pre(DLinkList* list);</td> 
 </tr> 
 <tr> 
 <td>//大家一定要注意：教科书不会告诉你项目上如何用；哪些点是项目的重点； 做一个企业级的财富库，完成你人生开发经验的积累，是我们的学习重点，要注意！</td> 
 </tr> 
 </tbody> 
</table>

## 3、优点和缺点 ##

<table> 
 <tbody> 
 <tr> 
 <td>优点：双向链表在单链表的基础上增加了指向前驱的指针 功能上双向链表可以完全取代单链表的使用 循环链表的Next，Pre和Current操作可以高效的遍历链表中的所有元素</td> 
 </tr> 
 <tr> 
 <td>缺点：代码复杂</td> 
 </tr> 
 </tbody> 
</table>

[70]: /images/20220524/dd6aff1f38c446249f947843207d15f5.png
[70 1]: /images/20220524/70692d60483241f8ab18875b0068a64b.png