怎样解析网站域名,成都科技网站建设电话多少钱,seo建站淘客,建设网站要服务器吗各位读者老爷好#xff0c;很高兴你又来读本鼠鼠的博客。鼠鼠我呀基于C语言实现一下双向链表#xff0c;有兴趣的读者老爷可以瞅瞅哈#xff01; 目录
1.定义双向链表节点
2.初始化哨兵位
3.双向链表销毁
4.双向链表打印
5.双向链表在pos的前面进行插入
6.双向链表删除…各位读者老爷好很高兴你又来读本鼠鼠的博客。鼠鼠我呀基于C语言实现一下双向链表有兴趣的读者老爷可以瞅瞅哈 目录
1.定义双向链表节点
2.初始化哨兵位
3.双向链表销毁
4.双向链表打印
5.双向链表在pos的前面进行插入
6.双向链表删除pos位置的节点
7.双向链表尾插
8.双向链表尾删
9.双向链表头插
10.双向链表头删
11.双向链表查找
12.双向链表的小应用
12.1.list.h
12.2.list.c
12.3.test.c:
13.ending
好哈我们上篇文章浅谈过链表的分类其中讲到 虽然有这么多的链表的结构但是我们实际中最常用还是两种结构 1. 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2. 带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了。 那咱们上篇文章实现过了无头单向非循环链表 那这篇博客自然要实现带头双向循环链表了。
对于带头双向循环链表好像听起来挺难的但其实实现起来比无头单向非循环链表简单不是一星半点儿咱们可以在接下来的代码中体会到我们可以先来看看带头双向循环链表的逻辑结构如下图 咱们可以看到有一个指针plist指向哨兵位也就是头所有节点均有三个数据域分别存储所需存储的数据、前一个节点的地址和后一个节点的地址我们通过地址即可找到想要的节点。这里讲的前后节点只是逻辑上的“前后”实际上在内存中这些个节点通过保存的地址形成了循环没有所谓的前后之分那这个链表改重哪里开始呢 其实就是从哨兵位开始的让plist指向哨兵位让哨兵位当“头”也就在逻辑上形成了“前后”。 带头双向循环链表带哨兵位是有优势的虽然哨兵位不存储有效数据好似浪费了一个节点的空间但是因为无论什么时候该链表都不可能为空对于该链表的增删改等操作不用另外考虑空链表的情况 。带头双向循环链表的哨兵位是不能删除的。 以下带头双向循环链表简称双向链表。我们实现双向链表以下功能
typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;//初始化哨兵位
ListNode* LTInit(void);// 双向链表销毁
void ListDestory(ListNode* pHead);// 双向链表打印
void ListPrint(ListNode* pHead);// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);// 双向链表尾删
void ListPopBack(ListNode* pHead);// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);// 双向链表头删
void ListPopFront(ListNode* pHead);// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
1.定义双向链表节点
typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;
由上分析可知该链表节点需要包含三个数据域所以我们定义结构体结构体成员data用来存储需存储数据、结构体成员next用来存储后一个节点地址、结构体成员prev用来存储前一个节点地址。至于为什么要把int重命名成LTDataType那是因为如果需存储数据的类型如果有所变化的话我们只需更改此处的int更改成需存储数据的类型即可极大方便后续的代码维护。
2.初始化哨兵位
//创建双向链表节点
ListNode* ListCreate(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL){perror(malloc fail-);exit(-1);}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}//初始化哨兵位
ListNode* LTInit(void)
{ListNode* head ListCreate(-1);head-next head;head-prev head;return head;
}
创建双向链表的时候我们需要初始化哨兵位初始化哨兵位就需要创建节点所以我们需要调用ListCreate函数LIstCreate函数参数是需存储数据动态申请一个节点返回这个节点地址。将哨兵位的next和prev存储哨兵位自己的地址才符合双向带头循环链表的特点哨兵位的data随便赋值即可。 大概这样式的啦 3.双向链表销毁
//双向链表销毁
void ListDestory(ListNode*pHead)
{ListNode* cur pHead-next;while (cur ! pHead){ListNode* next cur-next;free(cur);cur next;}free(pHead);pHead NULL;cur NULL;
}
当我们不在使用双向链表的时候好习惯是主动释放双向链表的空间。我们从哨兵位后一个节点开始遍历释放节点空间最后再单独释放哨兵位空间。
4.双向链表打印
//双向链表打印
void ListPrint(ListNode* pHead)
{ListNode* cur pHead-next;printf(哨兵位——);while (cur ! pHead){printf(%d——, cur-data);cur cur-next;}printf(\n);
}
大概思想是从哨兵位后一个节点开始遍历打印节点中需存储的数据即可无需打印哨兵位的数据因为那是无效数据上面的写法很完美打印出了所有有效数据当cur等于pHead时不进入循环内自然不打印哨兵位的数据了。。
5.双向链表在pos的前面进行插入
//创建双向链表节点
ListNode* ListCreate(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL){perror(malloc fail-);exit(-1);}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode ListCreate(x);newnode-prev pos-prev;pos-prev-next newnode;newnode-next pos;pos-prev newnode;
}
好好好这个功能的实现来说只需要通过pos-prev找到pos指向节点的前一个节点并让新申请节点调用ListCreate函数的prev存储前一个节点的地址让前一个节点的next存储新申请节点的地址让新申请节点的next存储pos指向节点的地址让pos指向节点的prev存储新申请节点的地址即可。
读者老爷请看图 6.双向链表删除pos位置的节点
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);if (pos-next pos){printf(不可删除哨兵位\n);}//防止删除哨兵位assert(pos-next ! pos);ListNode* posnext pos-next;ListNode* posprev pos-prev;posnext-prev posprev;posprev-next posnext;free(pos);pos NULL;
}
这个功能的实现也不难我们只要分别通过pos-next和pos-prev找到pos指向节点的后一个节点和前一个节点让后一个节点的prev存储前一个节点的地址让前一个节点的next存储后一个节点的地址再释放掉pos指向节点的空间。注意要断言防止删除哨兵位当pos指向哨兵位时pos-next等于pos所以assert条件为假就报错了。
读者老爷请看图 7.双向链表尾插
//创建双向链表节点
ListNode* ListCreate(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL){perror(malloc fail-);exit(-1);}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);//法一ListNode* tail pHead-prev;ListNode* newnode ListCreate(x);tail-next newnode;newnode-prev tail;newnode-next pHead;pHead-prev newnode;//法二//ListInsert(pHead, x);
}
对于尾插因为pHead指向哨兵位所以通过pHead-prev找到双向链表尾节点调用ListCreate函数申请一个新节点让尾节点的next存储新申请节点的地址让新申请节点的prev存储尾节点地址让新申请节点的next存储pHead让pHead的prev存储新申请节点地址即可。
也可以直接调用前面实现过的“双向链表再pos的前面进行插入”函数将哨兵位的地址(pHead)和所需存储数据传参进去即可。
8.双向链表尾删
//双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);if (pHead-next pHead){printf(不可删除哨兵位\n);}//防止删除哨兵位assert(pHead-next ! pHead);//法一/*ListNode* tail pHead-prev;ListNode* tailprev tail-prev;tailprev-next pHead;pHead-prev tailprev;free(tail);tail NULL;*///法二ListErase(pHead-prev);
}
对于双向链表尾删要注意断言防止删除哨兵位对于这个功能实现的思想大致来说就是通过pHead-prev找到尾节点再通过尾节点的prev找到尾节点的前一个节点让尾节点的前一个节点的next存储pHead让pHead指向的节点哨兵位的prev存储位节点的前一个节点的地址再释放掉pos指向的节点的空间即可。
也可以直接调用前面实现的“双向链表删除pos位置的节点”函数传入pHead-prev(尾节点的地址)即可。
9.双向链表头插
//创建双向链表节点
ListNode* ListCreate(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL){perror(malloc fail-);exit(-1);}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);//法一ListNode* newnode ListCreate(x);ListNode* head pHead-next;newnode-next head;head-prev newnode;newnode-prev pHead;pHead-next newnode;//法二//ListInsert(pHead-next, x);
}
对于双向链表头插我们是往哨兵位的后一个节点的前面插入使得插入的新申请节点成为哨兵位后一个节点。具体分析鼠鼠我就不分析了很简单啦也可以直接调用前面实现过的“双向链表再pos的前面进行插入”函数哈
10.双向链表头删
// 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);if (pHead-next pHead){printf(不可删除哨兵位\n);}//防止删除哨兵位assert(pHead-prev ! pHead);//法一ListNode* head pHead-next;pHead-next head-next;head-next-prev pHead;free(head);head NULL;//法二//ListErase(pHead-next);
}
头删的含义也是删除哨兵位后一个节点啦我们只要做好相应节点的链接再释放哨兵位后一个节点就行了。也可以直接调用前面实现过的“双向链表删除pos位置的节点”函数。很简单鼠鼠我偷个懒就不分析了。
11.双向链表查找
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{ListNode* cur pHead-next;while (cur ! pHead){if (cur-data x){return cur;}cur cur-next;}return NULL;
}
我们只要遍历查找除了哨兵位之外的所有节点的需存储数据即可如果有需存储数据与需查找数据一致我们就返回该节点的地址找不到就返回空指针。简简单单啦对了哨兵位的需存储数据本身是无效数据当然不用查找了。
12.双向链表的小应用
老样子了鼠鼠我呀写了三个文件有兴趣的读者老爷可以将这三个文件放到同一个工程下面玩玩可以更加深刻的理解上面代码的功能
12.1.list.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.htypedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;//初始化哨兵位
ListNode* LTInit(void);// 双向链表销毁
void ListDestory(ListNode* pHead);// 双向链表打印
void ListPrint(ListNode* pHead);// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);// 双向链表尾删
void ListPopBack(ListNode* pHead);// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);// 双向链表头删
void ListPopFront(ListNode* pHead);// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);12.2.list.c
#define _CRT_SECURE_NO_WARNINGS
#includelist.h//创建双向链表节点
ListNode* ListCreate(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (newnode NULL){perror(malloc fail-);exit(-1);}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}//初始化哨兵位
ListNode* LTInit(void)
{ListNode* head ListCreate(-1);head-next head;head-prev head;return head;
}//双向链表销毁
void ListDestory(ListNode*pHead)
{ListNode* cur pHead-next;while (cur ! pHead){ListNode* next cur-next;free(cur);cur next;}free(pHead);pHead NULL;cur NULL;
}//双向链表打印
void ListPrint(ListNode* pHead)
{ListNode* cur pHead-next;printf(哨兵位——);while (cur ! pHead){printf(%d——, cur-data);cur cur-next;}printf(\n);
}// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);//法一ListNode* tail pHead-prev;ListNode* newnode ListCreate(x);tail-next newnode;newnode-prev tail;newnode-next pHead;pHead-prev newnode;//法二//ListInsert(pHead, x);
}//双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);if (pHead-next pHead){printf(不可删除哨兵位\n);}//防止删除哨兵位assert(pHead-next ! pHead);//法一/*ListNode* tail pHead-prev;ListNode* tailprev tail-prev;tailprev-next pHead;pHead-prev tailprev;free(tail);tail NULL;*///法二ListErase(pHead-prev);
}// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);//法一ListNode* newnode ListCreate(x);ListNode* head pHead-next;newnode-next head;head-prev newnode;newnode-prev pHead;pHead-next newnode;//法二//ListInsert(pHead-next, x);
}// 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);if (pHead-next pHead){printf(不可删除哨兵位\n);}//防止删除哨兵位assert(pHead-prev ! pHead);//法一ListNode* head pHead-next;pHead-next head-next;head-next-prev pHead;free(head);head NULL;//法二//ListErase(pHead-next);
}// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{ListNode* cur pHead-next;while (cur ! pHead){if (cur-data x){return cur;}cur cur-next;}return NULL;
}// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode ListCreate(x);newnode-prev pos-prev;pos-prev-next newnode;newnode-next pos;pos-prev newnode;
}// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);if (pos-next pos){printf(不可删除哨兵位\n);}//防止删除哨兵位assert(pos-next ! pos);ListNode* posnext pos-next;ListNode* posprev pos-prev;posnext-prev posprev;posprev-next posnext;free(pos);pos NULL;
}
12.3.test.c:
#define _CRT_SECURE_NO_WARNINGS
#includelist.h
void menu()
{printf(******************************\n);printf(************0.退出************\n);printf(*******1.头插****2.尾插*******\n);printf(*******3.头删****4.尾删*******\n);printf(*******5.查找****6.打印*******\n);printf(*7.双向链表在pos的前面进行插入\n);printf(**8.双向链表删除pos位置的节点*\n);
}
int main()
{ListNode* plist LTInit();int input 0;do{menu();printf(请输入你想要的操作的代表数字-);scanf(%d, input);printf(\n);switch (input){case 0:{ListDestory(plist);plist NULL;printf(\n);break;}case 1:{int i 0;printf(请输入你想头插的数据个数-);scanf(%d, i);int j 0;printf(请输入你想头插的数据-);for (j 0; j i; j){LTDataType x 0;scanf(%d, x);ListPushFront(plist, x);}printf(\n);break;}case 2:{int i 0;printf(请输入你想尾插的数据个数-);scanf(%d, i);int j 0;printf(请输入你想尾插的数据-);for (j 0; j i; j){LTDataType x 0;scanf(%d, x);ListPushBack(plist, x);}printf(\n);break;}case 3:{ListPopFront(plist);printf(\n);break;}case 4:{ListPopBack(plist);printf(\n);break;}case 5:{LTDataType x 0;printf(请输入你想查找的数据-);scanf(%d, x);ListNode* ret ListFind(plist, x);if (ret ! NULL){printf(找到了该节点地址是%p\n, ret);}else{printf(找不到\n);}printf(\n);break;}case 6:{ListPrint(plist);printf(\n);break;}case 7:{LTDataType n 0, x 0;printf(请分别输入你想插入的数据和pos指向节点的数据-);scanf(%d %d, x, n);ListInsert(ListFind(plist,n), x);printf(\n);break;}case 8:{LTDataType x 0;printf(请输入pos指向节点的数据-);scanf(%d, x);ListErase(ListFind(plist,x));printf(\n);break;}}} while (input);return 0;
}
13.ending
好好好看到这里的话读者老爷如果觉得文章有不好的地方恳请斧正谢谢
