网站开发图标,网络推广优化服务,兽装定制网站,广州越秀区口腔医院数据结构——带头双向循环链表 一、带头双向循环链表的定义二、带头双向循环链表的实现2.1初始化创建带头双向循环链表的节点2.2申请新节点2.3节点的初始化2.4带头双向循环链表的尾插2.5带头双向循环链表的头插2.6判空函数2.7带头双向循环链表的打印函数2.8带头双向循环链表的尾… 数据结构——带头双向循环链表 一、带头双向循环链表的定义二、带头双向循环链表的实现2.1初始化创建带头双向循环链表的节点2.2申请新节点2.3节点的初始化2.4带头双向循环链表的尾插2.5带头双向循环链表的头插2.6判空函数2.7带头双向循环链表的打印函数2.8带头双向循环链表的尾删2.9带头双向循环链表的头删2.11带头双向循环链表的在pos之前插入2.12带头双向循环链表的在pos位置删除2.14带头双向循环链表的销毁 三、完整代码3.1LIst.h3.2List.c3.3test.c 一、带头双向循环链表的定义
带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势。
带头双向循环链表包括一个带有哨兵位的头节点该节点既可以作为链表的第一个节点也可以作为链表的最后一个节点.
这种链表的特点是每个节点都有两个指针一个指向前一个节点一个指向后一个节点这样就可以实现双向遍历。
同时链表的最后一个节点的后继指针指向头节点形成了循环的结构。这样我们可以在任意一个节点上进行前后移动插入和删除操作而不需要像单链表那样遍历整个链表去找到前一个节点。
需要注意的是带头双向循环链表为空并不意味着没有一个节点而是只有一个带哨兵位的头节点所以在使用之前需要对链表进行初始化。二、带头双向循环链表的实现
2.1初始化创建带头双向循环链表的节点
typedef struct ListNode
{Listdatatype data;struct ListNode* next;struct ListNode* prev;
}LTNode;在创建带头双向循环链表的节点中比之前单链表节点的创建多了一个struct ListNode* prev;结构体指针目的在与存储前一个节点的地址便于将整个链表连在一起。
2.2申请新节点
//创建新节点
LTNode* BuyLTNode(Listdatatype x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}动态申请内存结点函数返回的是一个指针类型用malloc开辟一个LTNode大小的空间并用node指向这个空间再判断是否为空如为空就perror显示错误信息。反之则把需要存储的数据x存到newnode指向的空间里面并且把newnode-next,newnode-prev置为空。
2.3节点的初始化
LTNode* LTInit()
{LTNode* phead BuyLTNode(-1);phead-next phead;phead-prev phead;return phead;
}通过动态内存申请节点申请了一个头节点。并且将它的phead-next phead-prev 都置为phead,得到如下图的头节点。
2.4带头双向循环链表的尾插
void LTPushBack(LTNode* phead, Listdatatype x)
{assert(phead);LTNode* tail phead-prev;LTNode* newnode BuyLTNode(x);tail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;
}尾插节点的方法首先通过内存申请一个节点 然后改变四个指针的指向便可以完成带头双向循环链表的尾插。
2.5带头双向循环链表的头插
void LTFrontBack(LTNode* phead, Listdatatype x)
{assert(phead);LTNode* newnode BuyLTNode(x);newnode-next phead-next;phead-next-prev newnode;phead-next newnode;newnode-prev phead;
} 2.6判空函数
bool LTEmpty(LTNode* phead)
{assert(phead);return phead-next phead;
}2.7带头双向循环链表的打印函数
//打印
void LTPrint(LTNode* phead)
{LTNode* cur phead-next;printf(guard-);while (cur ! phead){printf(%d-, cur-data);cur cur-next;}printf(\n);
}2.8带头双向循环链表的尾删
//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(! LTEmpty(phead));LTNode* tail phead-prev;LTNode* tailprev tail-prev;//改变指针的指向free(tail);tailprev-next phead;phead-prev tailprev;
}2.9带头双向循环链表的头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* first phead-next;LTNode* firstnext first-next;free(first);phead-next firstnext;firstnext-prev phead;
}2.11带头双向循环链表的在pos之前插入
void LTInsert(LTNode* pos, Listdatatype x)
{assert(pos);LTNode* newnode BuyLTNode(x);LTNode* posprev pos-prev;posprev-next newnode;newnode-prev posprev;newnode-next pos;pos-prev newnode;
}2.12带头双向循环链表的在pos位置删除
void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev pos-prev;LTNode* posnext pos-next;posprev-next posnext;posnext-prev posprev;free(pos);
}2.14带头双向循环链表的销毁
//销毁
LTNode* LTDestory(LTNode* phead)
{LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);
}三、完整代码
3.1LIst.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
typedef int Listdatatype;
typedef struct ListNode
{Listdatatype data;struct ListNode* next;struct ListNode* prev;
}LTNode;//初始化
LTNode* LTInit();//尾插
void LTPushBack(LTNode* phead, Listdatatype x);//尾删
void LTPopBack(LTNode* phead);//头插
void LTFrontBack(LTNode* phead, Listdatatype x);//头删
void LTPopFront(LTNode* phead);//打印
void LTPrint(LTNode* phead);//判空
bool LTEmpty(LTNode* phead);//在pos之前插入
void LTInsert(LTNode* pos, Listdatatype x);//在pos之前删除
void LTErase(LTNode* pos);//寻找
LTNode* LTFind(LTNode* phead, Listdatatype x);//销毁
LTNode* LTDestory(LTNode* phead);3.2List.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeList.h
//创建新节点
LTNode* BuyLTNode(Listdatatype x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}LTNode* LTInit()
{LTNode* phead BuyLTNode(-1);phead-next phead;phead-prev phead;return phead;
}
//尾插
void LTPushBack(LTNode* phead, Listdatatype x)
{assert(phead);LTNode* tail phead-prev;LTNode* newnode BuyLTNode(x);tail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;
}//头插
void LTFrontBack(LTNode* phead, Listdatatype x)
{assert(phead);LTNode* newnode BuyLTNode(x);newnode-next phead-next;phead-next-prev newnode;phead-next newnode;newnode-prev phead;
}//判空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead-next phead;
}//打印
void LTPrint(LTNode* phead)
{LTNode* cur phead-next;printf(guard-);while (cur ! phead){printf(%d-, cur-data);cur cur-next;}printf(\n);
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(! LTEmpty(phead));LTNode* tail phead-prev;LTNode* tailprev tail-prev;//改变指针的指向free(tail);tailprev-next phead;phead-prev tailprev;
}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* first phead-next;LTNode* firstnext first-next;free(first);phead-next firstnext;firstnext-prev phead;
}//寻找
LTNode* LTFind(LTNode* phead, Listdatatype x)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){if (cur-data x){return cur;}cur cur-next;}return NULL;
}//在pos之前插入
void LTInsert(LTNode* pos, Listdatatype x)
{assert(pos);LTNode* newnode BuyLTNode(x);LTNode* posprev pos-prev;posprev-next newnode;newnode-prev posprev;newnode-next pos;pos-prev newnode;
}在pos之前删除
//void LTErase(LTNode* pos)
//{
// assert(pos);
// LTNode* posprev pos-prev;
// free(posprev);
// posprev-prev-next pos;
// pos-prev posprev-prev;
//
//}//在pos位置删除
void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev pos-prev;LTNode* posnext pos-next;posprev-next posnext;posnext-prev posprev;free(pos);
}//销毁
LTNode* LTDestory(LTNode* phead)
{LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);
}3.3test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeList.h
//void test1()
//{
// LTNode* plist LTInit();
// LTPushBack(plist, 1);
// LTPushBack(plist, 2);
// LTPushBack(plist, 3);
// LTPushBack(plist, 4);
// LTPrint(plist);
// LTPopBack(plist);
// LTPrint(plist);//}
void test2()
{LTNode* plist LTInit();LTFrontBack(plist, 1);LTFrontBack(plist, 2);LTFrontBack(plist, 3);LTFrontBack(plist, 4);LTPrint(plist);LTErase(3);LTPrint(plist);
}
int main()
{//test1();test2();return 0;
}
