//线性双向链表 #ifndef _MY_DLINKLIST_H_ #define _MY_DLINKLIST_H_ typedef void DLinkList; typedef struct _tag_DLinkListNode { struct _tag_DLinkListNode* next; struct _tag_DLinkListNode * pre; }DLinkListNode; //创建双向链表 DLinkList* DLinkList_Create(); //销毁双向链表 int DLinkList_Destroy(DLinkList ** list); //清空双向链表 int DLinkList_Clear(DLinkList* list); //获取双向链表长度 int DLinkList_Length(DLinkList* list); //双向链表指定位置插入元素 int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos); //获取双向链表指定位置的元素 DLinkListNode* DLinkList_Get(DLinkList* list, int pos); //删除双向链表指定位置的元素 DLinkListNode* DLinkList_Delete(DLinkList* list, int pos); //-- add //删除双线链表的一个节点 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); #endif
//线性双向链表代码实现 #include<stdio.h> #include<stdlib.h> #include<string.h> #include"dlinklist.h" /* 双向链表 第0个节点没有前驱，最后一个节点没有后继 */ typedef struct _TDlinkList{ //定义头结点 DLinkListNode node; //定义游标 DLinkListNode * slider; //定义链表长度 int length; }TDlinkList; //创建双向链表 _declspec(dllexport) DLinkList * DLinkList_Create(){ TDlinkList * tlist = (TDlinkList *)malloc(sizeof(TDlinkList)); if (tlist==NULL) { printf("分配内存失败！ "); return NULL; } //初始化双向链表结构体参数 tlist->length = 0; tlist->node.pre = NULL; tlist->node.next = NULL; tlist->slider = NULL; return (DLinkList *)tlist; } //销毁链表 _declspec(dllexport) int DLinkList_Destroy(DLinkList ** list){ int ERRO_MSG = 0; if (list==NULL) { ERRO_MSG = -1; printf("传入参数不可以为空！ ", ERRO_MSG); return ERRO_MSG; } TDlinkList * tlist = (TDlinkList *)*list; if (tlist!=NULL) { free(tlist); tlist = NULL; *list = NULL; } return ERRO_MSG; } //清空双向链表 _declspec(dllexport) int DLinkList_Clear(DLinkList* list){ int ERRO_MSG = 0; if (list == NULL) { ERRO_MSG = -1; printf("传入参数不可以为空！ ", ERRO_MSG); return ERRO_MSG; } TDlinkList * tlist = (TDlinkList *)list; tlist->length = 0; tlist->slider = NULL; tlist->node.pre = NULL; tlist->node.next = NULL; return ERRO_MSG; } //获取双向链表长度 _declspec(dllexport) int DLinkList_Length(DLinkList* list){ int ERRO_MSG = 0; if (list == NULL) { ERRO_MSG = -1; printf("传入参数不可以为空！ ", ERRO_MSG); return ERRO_MSG; } TDlinkList * tlist = (TDlinkList *)list; return tlist->length; } //双向链表指定位置插入元素 _declspec(dllexport) int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos){ int ERRO_MSG = 0,i=0; if (list == NULL || node==NULL) { ERRO_MSG = -1; printf("传入参数不可以为空！ ", ERRO_MSG); return ERRO_MSG; } TDlinkList * tlist = (TDlinkList *)list; //位置判断 if (pos<0 || pos>tlist->length) { //进行容错处理 pos = tlist->length; } //定义两个变量 DLinkListNode * pPrior = &tlist->node, *pCurrent = tlist->node.next; //普通情况实现 //遍历链表 for (i = 0; i < pos ; i++) { //变量后移 pPrior = pCurrent; pCurrent = pCurrent->next; } node->next = pCurrent; pPrior->next = node; if (pCurrent!=NULL) { pCurrent->pre = node; } node->pre = pPrior; //判断是不是第0个节点 if (pPrior == &tlist->node) { node->pre = NULL; } //游标指向第0个节点 if (tlist->length==0) { tlist->slider = node; } //双向链表个数+1 tlist->length++; /* 特殊情况处理 ①：第0个位置插入--下一个节点没问题 但是前一个节点必须是NULL if (pPrior == &tlist->node) { node->pre = NULL; } ②：原来是个空链表 此时pCurrent=NULL node->next = pCurrent;执行没有问题 pPrior->next = node;执行没有问题 pCurrent->pre = node;执行报错 pCurrent为NULL 无法对内存0位置赋值 修正 加上非空判断 if (pCurrent!=NULL) { pCurrent->pre = node; } node->pre = pPrior;执行逻辑有问题 此时第0个元素没有前驱节点 修正 if (pPrior == &tlist->node) { node->pre = NULL; } else{ node->pre = pPrior; } ③：在末尾插入节点 上述逻辑已经满足条件 */ return ERRO_MSG; } //获取双向链表指定位置的元素 _declspec(dllexport) DLinkListNode* DLinkList_Get(DLinkList* list, int pos){ int ERRO_MSG = 0, i = 0; if (list == NULL) { ERRO_MSG = -1; printf("传入参数不可以为空！ ", ERRO_MSG); return NULL; } TDlinkList * tlist = (TDlinkList *)list; //位置判断 if (pos<0 || pos>tlist->length) { ERRO_MSG = -2; printf("该位置没有元素！ ", ERRO_MSG); return NULL; } DLinkListNode * current = tlist->node.next; for (i = 0; i < pos; i++) { current = current->next; } return current; } //删除双向链表指定位置的元素 _declspec(dllexport) DLinkListNode* DLinkList_Delete(DLinkList* list, int pos){ int ERRO_MSG = 0, i = 0; if (list == NULL) { ERRO_MSG = -1; printf("传入参数不可以为空！ ", ERRO_MSG); return NULL; } TDlinkList * tlist = (TDlinkList *)list; //位置判断 if (pos<0 || pos>tlist->length) { ERRO_MSG = -2; printf("该位置没有元素！ ", ERRO_MSG); return NULL; } //普通情况处理 //定义两个变量 DLinkListNode * pPrior = &tlist->node, *pCurrent = tlist->node.next,*pNext=NULL; for (i = 0; i < pos; i++) { pPrior = pCurrent; pCurrent = pCurrent->next; } pNext = pCurrent->next; pPrior->next = pNext; if (pNext!=NULL) { pNext->pre = pPrior; //判断删除的是否是第0个元素 if (pPrior == &tlist->node) { pNext->pre = NULL; } } /* 特殊情况处理 ①：删除第0个元素 pNext = pCurrent->next; 正确 pNext指向下一个元素 pPrior->next = pNext; 正确 头结点指向下一个节点 if (pNext!=NULL) { pNext->pre = pPrior; } 错误 此时 下一个节点的上一个节点应该指向NULL 所以 应该追加对第0个元素的处理 if (pPrior == &tlist->node) { pNext->pre = NULL; } ②：只有一个元素删除 pNext = pCurrent->next; 正确 此时 pNext=NULL pPrior->next = pNext; 正确 头结点指向NULL pNext->pre = pPrior; 错误 此时pNext为NULL 不可以赋值 修正 if (pNext!=NULL) { pNext->pre = pPrior; } ③：删除最后一个元素 pNext = pCurrent->next; 正确 此时pNext=NULL pPrior->next = pNext; 正确 if (pNext!=NULL) { pNext->pre = pPrior; //判断删除的是否是第0个元素 if (pPrior == &tlist->node) { pNext->pre = NULL; } } 正确 pNext=NULL 此时应该不作处理 */ return pCurrent; } //删除双线链表的一个节点 _declspec(dllexport) DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node){ int ERRO_MSG = 0, i = 0; if (list == NULL || node==NULL) { ERRO_MSG = -1; printf("传入参数不可以为空！ ", ERRO_MSG); return NULL; } TDlinkList * tlist = (TDlinkList *)list; DLinkListNode * pCurrent = &tlist->node; for (i = 0; i < tlist->length; i++) { pCurrent = pCurrent->next; if (pCurrent == node) { break; } } return DLinkList_Delete(list, i); } //游标重置 _declspec(dllexport) DLinkListNode* DLinkList_Reset(DLinkList* list){ int ERRO_MSG = 0; if (list == NULL) { ERRO_MSG = -1; printf("传入参数不可以为空！ ", ERRO_MSG); return NULL; } TDlinkList * tlist = (TDlinkList *)list; tlist->slider = tlist->node.next; return tlist->slider; } //获取当前游标 _declspec(dllexport) DLinkListNode* DLinkList_Current(DLinkList* list){ int ERRO_MSG = 0; if (list == NULL) { ERRO_MSG = -1; printf("传入参数不可以为空！ ", ERRO_MSG); return NULL; } TDlinkList * tlist = (TDlinkList *)list; return tlist->slider; } //游标后移 返回下一个位置的元素 _declspec(dllexport) DLinkListNode* DLinkList_Next(DLinkList* list){ int ERRO_MSG = 0; if (list == NULL) { ERRO_MSG = -1; printf("传入参数不可以为空！ ", ERRO_MSG); return NULL; } TDlinkList * tlist = (TDlinkList *)list; if (tlist->slider==NULL) { ERRO_MSG = -2; printf("游标不可以为空！ ", ERRO_MSG); return NULL; } tlist->slider = tlist->slider->next; return tlist->slider; } //游标前移 返回上一个位置的元素 _declspec(dllexport) DLinkListNode* DLinkList_Pre(DLinkList* list){ int ERRO_MSG = 0; if (list == NULL) { ERRO_MSG = -1; printf("传入参数不可以为空！ ", ERRO_MSG); return NULL; } TDlinkList * tlist = (TDlinkList *)list; if (tlist->slider == NULL) { ERRO_MSG = -2; printf("游标不可以为空！ ", ERRO_MSG); return NULL; } tlist->slider = tlist->slider->pre; return tlist->slider; }
//线性双向链表测试代码 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<string.h> #include"dlinklist.h" typedef struct _Student{ //必须加一个DLinkListNode节点 DLinkListNode node; char name[30]; int age; }Student; void Test(){ Student s1, s2, s3, s4, s5, s6, s7, s8; int numx = 0, i = 0, ret = 0; strcpy(s1.name, "小米"); s1.age = 11; strcpy(s2.name, "小刚"); s2.age = 12; strcpy(s3.name, "小红"); s3.age = 10; strcpy(s4.name, "啸天"); s4.age = 13; strcpy(s5.name, "莲华"); s5.age = 12; s4.age = 13; strcpy(s6.name, "夏利"); s6.age = 11; strcpy(s7.name, "小李"); s7.age = 13; strcpy(s8.name, "阿凯"); s8.age = 12; //线性表指针 DLinkList *list = NULL; //创建线性链表 list = DLinkList_Create(); //插入元素 DLinkList_Insert(list, (DLinkList *)&s1, DLinkList_Length(list)); DLinkList_Insert(list, (DLinkList *)&s2, DLinkList_Length(list)); DLinkList_Insert(list, (DLinkList *)&s3, DLinkList_Length(list)); DLinkList_Insert(list, (DLinkList *)&s4, DLinkList_Length(list)); DLinkList_Insert(list, (DLinkList *)&s5, DLinkList_Length(list)); DLinkList_Insert(list, (DLinkList *)&s6, DLinkList_Length(list)); DLinkList_Insert(list, (DLinkList *)&s7, DLinkList_Length(list)); DLinkList_Insert(list, (DLinkList *)&s8, DLinkList_Length(list)); //获取元素个数 numx = DLinkList_Length(list); //逆序打印元素--游标的使用 //重置游标 Student *temp = (Student *)DLinkList_Reset(list); while (--numx) { temp = (Student *)DLinkList_Next(list); } while (temp != NULL){ printf("我的名字是%s；我的年龄是%d ", temp->name, temp->age); temp = (Student *)DLinkList_Pre(list); } //删除线性表中的数据 Student *delem = (Student *)DLinkList_Delete(list, 2); printf("我被删除了,我的名字是%s；我的年龄是%d ", delem->name, delem->age); //销毁线性表 ret = DLinkList_Destroy(&list); if (ret == 0)printf("线性双向链表销毁成功！ "); } void main(){ Test(); system("pause"); }
