@TOC
一、双向带头循环链表
构成
在这里插入图片描述
二、双向带头循环链表的实现
1.函数的定义和结构体的创建——list.h
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int datatype; struct listNode { datatype val; struct listNode* prev; struct listNode* next; }; struct listNode* stackinit(); void stackpushback(struct listNode* phead, datatype x); void stackprint(struct listNode* phead); void stackpopback(struct listNode* phead); void stackpushfront(struct listNode* phead, datatype x); void stackpopfront(struct listNode* phead); struct listNode*stackfind (struct listNode* phead,datatype x); void stackinsert(struct listNode* pos, datatype x); void stackdestroy(struct listNode* phead);
2.函数的调用——list.c
#include"list.h" int main() { struct listNode* phead= stackinit();//这里为了不使用二级指针，将结构体指针返回 stackpushback(phead, 1); stackpushback(phead, 2); stackpushback(phead, 3); stackpushback(phead, 4); stackpopback(phead); stackpushfront(phead,5); stackpopfront(phead); stackprint(phead); struct listNode*pos=stackfind(phead, 2); stackinsert(pos, 4); stackprint(phead); struct listNode* pos2 = stackfind(phead, 2); stackerase(pos2); stackprint(phead); stackdestroy(phead); phead = NULL; return 0; }
3. 双向带头循环链表与单链表的传递参数区别
1.单链表：
单链表因为没有头节点的存在，导致在尾插时会改变链表的头节点
所以需要传递二级指针的地址即二级指针。
2.双向带头循环链表：
初始化头指针时，是需要传递二级指针，只不过用函数传回结构体指针的方式代替了，
而在后续接口则不需要传递二级指针，因为后来都是在头指针的基础上进行的，而头节点本身不会存储有效数据，并不会改变头节点本身。
4.双向带头循环链表的接口
1.初始化
struct listNode* stackinit()//初始化头节点 { struct listNode* phead = (struct listNode*)malloc(sizeof(struct listNode)); phead->next = phead;//带哨兵位的头节点 phead->prev = phead; }
在这里插入图片描述
2.尾插
void stackpushback(struct listNode* phead, datatype x)//尾插 { struct listNode* tail = phead->prev;//tail为最后一个节点 struct listNode* newnode = (struct listNode*)malloc(sizeof(struct listNode)); newnode->val = x; tail->next = newnode; newnode->prev=tail; newnode->next = phead; phead->prev = newnode; }
在这里插入图片描述
3.尾删
void stackpopback(struct listNode* phead)//尾删 { assert(phead); assert(phead->next != phead);//当只剩下头节点时 phead->next才会指向phead struct listNode* tail = phead->prev; struct listNode* cur = tail->prev;//rur为最后一个节点的前一个节点 cur->next = phead; phead->prev = cur; free(tail); tail = NULL; }
在这里插入图片描述
4.头插
void stackpushfront(struct listNode* phead, datatype x)//头插 { struct listNode* newnode = (struct listNode*)malloc(sizeof(struct listNode)); newnode->val = x; struct listNode* cur = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = cur; cur->prev = newnode; }
在这里插入图片描述
### 5.头删
void stackpopfront(struct listNode* phead)//头删 { assert(phead); assert(phead->next != phead);//链表为空时 struct listNode* prev = phead->next; struct listNode* next = phead->next->next;//找到第一个节点后的一个节点 phead->next = next; next->prev = phead; free(prev); prev = NULL; }
在这里插入图片描述
6.查找位置
struct listNode* stackfind(struct listNode* phead, datatype x)//查找位置 { struct listNode* cur = phead->next; while (cur != phead) { if (cur->val == x) { return cur;//如果找到了返回结构体 } cur = cur->next; } return NULL;//如果找不到就返回NULL }
7.指定 在pos之前插入
void stackinsert(struct listNode* pos, datatype x)//指定插 在pos之前插入 { assert(pos); struct listNode* prev = pos->prev; struct listNode* newnode = (struct listNode*)malloc(sizeof(struct listNode)); newnode->val = x; prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }
在这里插入图片描述
8.指定删
void stackerase(struct listNode* pos)//指定删 { assert(pos); struct listNode* prev = pos->prev; struct listNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); pos = NULL; }
在这里插入图片描述
9.内存销毁
void stackdestroy(struct listNode* phead)//内存销毁 { struct listNode* cur = phead->next; while (cur != phead) { struct listNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL;//因为此时传过来是一级指针不能影响会传回去的phead 所以可以手动在外面置NULL }
10.打印
void stackprint(struct listNode* phead)//打印 { struct listNode* cur = phead->next; while (cur != phead)//此时因为是循环链表 ，所以不要写成NULL { printf("%d ", cur->val); cur = cur->next; } printf("\n"); }
三、链表与顺序表的不同点
1.顺序表：
在物理上是连续的
优点： 支持随机访问。
缺点：(1)任意位置插入或者删除时，可能需要挪动元素，效率低。
(2)在动态开辟空间时，会造成一定的浪费。
2.链表：
逻辑上是来连续的，物理上的不连续。
优点:(1)任意位置插入或者删除，不会挪动元素，只会改变指针指向，(2)没有容量的概念，不会造成空间浪费。
缺点：不支持随机访问
