贵州省建设监理协会官方网站,直播软件有哪些,企业建网站选中企动力,网站开发工程师有证书考试吗目录
1、双向带头循环链表的介绍
2、双向带头循环链表的接口
3、接口实现
3.1 开辟结点
3.2 创建返回链表的头结点
3.3 判断链表是否为空
3.4 打印
3.5 双向链表查找
3.6 双向链表在pos的前面进行插入
3.6.1 头插
3.6.2 尾插
3.6.3 更新头插、尾插写法
3.7 双向链…目录
1、双向带头循环链表的介绍
2、双向带头循环链表的接口
3、接口实现
3.1 开辟结点
3.2 创建返回链表的头结点
3.3 判断链表是否为空
3.4 打印
3.5 双向链表查找
3.6 双向链表在pos的前面进行插入
3.6.1 头插
3.6.2 尾插
3.6.3 更新头插、尾插写法
3.7 双向链表删除pos位置的节点
3.7.1 头删
3.7.2 尾删
3.7.3 更新头删、尾删写法
3.8 双向链表销毁
4、完整代码
5、功能测试 1、双向带头循环链表的介绍
我们将这个题目拆分开来可以提取三个关键字双向带头循环。我们就以这三个关键字来展开介绍一下
首先是双向双向就说明了这个结点可以找到自己的前驱和后继这一点与单链表存在本质的区别
其次是带头带头说明链表有一个头结点这个头结点也可以称为哨兵位的头结点此结点与其他结点是一样的只是它的 data 域放的是随机值有的会存放链表的长度
最后是循环循环说明了它的结构是一个环装头结点的前驱结点存放着尾结点尾结点的后继结点存放着头结点。 2、双向带头循环链表的接口
双向带头循环链表与单链表的功能是一样的都是可以增删查改的但是双向带头循环链表的特性让这么功能写的时候大大提高了我们的效率。
// 带头双向循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;// 创建返回链表的头结点
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
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);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
3、接口实现
3.1 开辟结点
我们的链表是动态的链表因此每次在插入的时候我们都需要 malloc 一个结点我们将其封装成一个函数方便后面的代码复用。
ListNode* BuyListNode(LTDataType x)
{ListNode* newnode (ListNode*)malloc(sizeof(ListNode));if (NULL newnode){perror(malloc fail:);return NULL;}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}
3.2 创建返回链表的头结点
这一步是我们给链表创建一个哨兵位的头结点。因为是双向带头循环链表因此我们让 prev 和 next 指针都指向自己这样就算是只有一个头结点我们也是双向循环的结构。
ListNode* ListCreate()
{ListNode* phead BuyListNode(-1);phead-next phead;phead-prev phead;return phead;
}
3.3 判断链表是否为空
这一步是我们为后面的删除时封装的一个判空功能函数当链表存在的时候不排除链表为空的情况因此我们封装此函数以便后面的接口复用。
bool ListEmpty(ListNode* pHead)
{assert(pHead);return pHead-next pHead;
}
3.4 打印
打印函数我们已经很熟悉了但是双向带头循环链表的打印终止条件要注意这里不再是以前的 cur NULL而是 cur ! pHead 当 cur 走到 pHead 时就说明我们已经遍历完整个链表了。
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-next;printf(guard);while (cur ! pHead){printf(%d, cur-data);cur cur-next;}printf(\n);
}
3.5 双向链表查找
查找不难但是这里要注意双向带头链表的第一个结点是哨兵位结点因此我们要从哨兵位的下一个结点开始遍历查找cur pHead-next循环的终止条件依然是 cur ! pHead。
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur pHead-next;while (cur ! pHead){if (cur-data x)return cur;cur cur-next;}return NULL;
}
3.6 双向链表在pos的前面进行插入
我们在找到pos位置后在 pos 位置前进行插入我们按下面的流程执行
1、假如我们要在 data3 前插入一个 data4我们先用定义一个结构体指针变量 prev先将data3-prev (data2)结点保存在 prev 变量中
2、再将 prev-next 改为 data4 然后将 data4-prev 改为 prev
3、最后把 data4-next data3再把 data3-prev data4。 void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* prev pos-prev;ListNode* newnode BuyListNode(x);prev-next newnode;newnode-prev prev;newnode-next pos;pos-prev newnode;
}
3.6.1 头插
头插的话我们与在pos位置前插入一致先将第一个结点保存起来然后进行插入。
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode BuyListNode(x);ListNode* first pHead-next;//多写这一个变量下面的插入语句就可以无序写pHead-next newnode;newnode-next first;newnode-prev pHead;first-prev newnode;
}
3.6.2 尾插
尾插的话先将链表的尾结点保存起来然后进行插入还是与在pos位置前插入一样。
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* tail pHead-prev;ListNode* newnode BuyListNode(x);tail-next newnode;newnode-prev tail;newnode-next pHead;pHead-prev newnode;
}
3.6.3 更新头插、尾插写法
对比插入代码我们其实不难发现头插、尾插与在pos位置前插入的代码逻辑是一样的实现的功能根本上也没有变那我们就在头插、尾插时直接复用 ListInsert 接口就可以实现。
1 头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListInsert(pHead-next, x);
}
2 尾插
因为是 pos 位置前插入链表是双向循环的所以传的第一个参数就是 pHead 哨兵位结点前一个结点就是尾结点。
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListInsert(pHead, x);
}
3.7 双向链表删除pos位置的节点
我们在找到 pos 结点后再将 pos 结点删除我们按下面的流程执行
1、定义两个结构体指针变量 posPrev与posNext将 pos 位置前后结点分别保存在 posPrev与posNext 指针变量中
2、将posPrev-next posNext再将 posNext-prev posPrev
3、释放掉 pos 结点free(pos)。 void ListErase(ListNode* pos)
{assert(pos);ListNode* posPrev pos-prev;ListNode* posNext pos-next;posPrev-next posNext;posNext-prev posPrev;free(pos);
}
3.7.1 头删
头删的话我们先将 pHead-next结点与pHead-next-next结点保存下来将哨兵位结点与头结点的下一个结点连接起来再将头结点释放掉。
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(!ListEmpty(pHead));ListNode* first pHead-next;ListNode* second first-next;pHead-next second;first-prev pHead;free(first);
}
3.7.2 尾删
尾删的话我们先将 pHead-prev结点与pHead-prev-prev结点保存下来将哨兵位结点与尾结点的前一个结点连接起来再将尾结点释放掉。
void ListPopBack(ListNode* pHead)
{assert(pHead);assert(!ListEmpty(pHead));ListNode* tail pHead-prev;ListNode* tailPrev tail-prev;tailPrev-next pHead;pHead-prev tailPrev;free(tail);
}
总结在头删与尾删前要判断链表是否为空。
3.7.3 更新头删、尾删写法
对比删除代码我们其实不难发现头删、尾删与删除pos位置结点的代码逻辑是一样的实现的功能根本上也没有变那我们就在头删、尾删时直接复用 ListErase 接口就可以实现。
1 头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(!ListEmpty(pHead));ListErase(pHead-next);
}
2 尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);assert(!ListEmpty(pHead));ListErase(pHead-prev);
}
3.8 双向链表销毁
链表的销毁主要是遍历一遍链表从 cur pHead-next 开始循环终止的条件为 cur ! pHead遍历完再将哨兵位结点释放掉整个链表就被释放掉了。
void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur pHead-next;while (cur ! pHead){ListNode* next cur-next;free(cur);cur next;}free(pHead);
}
4、完整代码
完整代码在代码仓库入口C语言: C语言学习的代码多复习 - Gitee.com
5、功能测试
