提升网站建设品质信息,设计软件排行,中企动力登录,网页游戏大厅免费前言 带头双向循环链表是一种重要的数据结构#xff0c;它的结构是很完美的#xff0c;它弥补了单链表的许多不足#xff0c;让我们一起来了解一下它是如何实现的吧#xff01;
1.节点的结构 它的节点中存储着数据和两个指针#xff0c;一个指针_prev用来记录前一个节点…前言 带头双向循环链表是一种重要的数据结构它的结构是很完美的它弥补了单链表的许多不足让我们一起来了解一下它是如何实现的吧
1.节点的结构 它的节点中存储着数据和两个指针一个指针_prev用来记录前一个节点的地址另一个指针_next 用来记录后一个节点的地址。 typedef int LTDataType;
typedef struct ListNode
{struct ListNode* _next;struct ListNode* _prev;LTDataType _data;
}ListNode;2.尾部的插入和删除的实现 由于这是带头循环的双向链表所以尾插只需要在它的头结点的_prev 处进行插入然后重新链接就可以了。如图 如果只有一个头结点插入也是一样的。
void ListPushBack(ListNode* phead, LTDataType data)//尾插
{assert(phead);ListNode* newNode BuyListNode(data);//申请新节点ListNode* tail phead-_prev;//找尾结点//链接新节点和尾结点tail-_next newNode;newNode-_prev tail;//与头结点进行链接phead-_prev newNode;newNode-_next phead;
} 尾部的删除首先需要找到链表的尾和尾的前一个节点删除尾结点之后将前一个节点进与头结点进行链接如图 void ListPopBack(ListNode* phead)//尾删除
{//确保指针不为空assert(phead);assert(phead-_next ! phead);//保留头结点//找尾ListNode* tail phead-_prev;ListNode* newTail tail-_prev;//找到新的尾结点//删除旧的尾结点free(tail);//重新链接头尾节点newTail-_next phead;phead-_prev newTail;
}
3.头部插入和删除的实现 头部的插入删除和尾部的插入删除类似需要注意的是删除的不是 头结点是存储有效数据的第一个节点插入数据也是在第一个有效数据节点和头结点之间插入。如图 void ListPushFront(ListNode* phead, LTDataType data)//头插
{//确保指针不为空assert(phead);//申请新的节点ListNode* newNode BuyListNode(data);//进行链接ListNode* realHead phead-_next;realHead-_prev newNode;newNode-_next realHead;phead-_next newNode;newNode-_prev phead;
}
void ListPopFront(ListNode* phead)//头删插
{//指针存在assert(phead);//并且确保不能删除头结点assert(phead-_next ! phead);//找到真正的头ListNode* realHead phead-_next;ListNode* realHeadNext realHead-_next;//删除头节点free(realHead);//重新链接phead-_next realHeadNext;realHeadNext-_prev phead;
}
4.任意位置的插入和删除 在任意位置进行插入和删除需要知道节点的指针插入或者删除节点之后需要 更新节点的链接关系。如图 void ListInsert(ListNode* pos, LTDataType data)//pos位置之前的插入
{assert(pos);//确保指针有效ListNode* newNode BuyListNode(data);//申请节点//进行链接ListNode* prev pos-_prev;ListNode* next pos;prev-_next newNode;newNode-_prev prev;newNode-_next next;next-_prev newNode;
}
void ListErase(ListNode* pos)//pos位置的删除
{//确保指针有效assert(pos);ListNode* next pos-_next;ListNode* prev pos-_prev;//删除pos所指向的节点free(pos);//进行重新链接prev-_next next;next-_prev prev;
} 对任意位置的插入和删除进行测试时可以通过复用接口来实现头插尾插头删尾删都可以调用这两个接口来实现如下
void ListPushBack(ListNode* phead, LTDataType data)//尾插
{ListInsert(phead, data);
}
void ListPopBack(ListNode* phead)//尾删除
{ListErase(phead-_prev);
}
void ListPushFront(ListNode* phead, LTDataType data)//头插
{ListInsert(phead-_next,data);
}
void ListPopFront(ListNode* phead)//头删插
{ListErase(phead-_next);
}
5.链表的初始化和删除 带头的双向循环链表初始化的时候就需要申请内存给头节点。
ListNode* BuyListNode(LTDataType data)//申请节点
{ListNode* newNode (ListNode*)malloc(sizeof(ListNode));if (newNode NULL){printf(申请空间失败\n);exit(-1);}newNode-_data data;return newNode;
}
void ListInit(ListNode** pphead)//初始化链表
{*pphead BuyListNode(0);//申请头结点//并且初始化(*pphead)-_next *pphead;(*pphead)-_prev *pphead;
}
//清理链表
void ListClear(ListNode* phead)
{assert(phead);//确保链表不为空assert(phead-_next ! phead);//除了确保不清理头结点ListNode* cur phead-_next;while (cur ! phead){ListNode* clearNode cur;cur cur-_next;free(clearNode);}
}
void ListDestory(ListNode** ppHead)//摧毁链表
{assert(*ppHead);//确保指针不为空ListClear(*ppHead);free(*ppHead);//释放头结点
}
6.查找并修改链表的节点的数据 查找和修改是一起的实现查找就可以实现 修改链表的值。
ListNode* ListFind(ListNode* phead, LTDataType data)//查找链表
{assert(phead);ListNode* cur phead-_next;while (cur ! phead){if (cur-_data data)return cur;cur cur-_next;}return NULL;//找不到返回NULL
}
void ListTest4()
{//查找和修改的测试ListNode* pHead NULL;ListInit(pHead);ListPushFront(pHead, 1);ListPushFront(pHead, 2);ListPushFront(pHead, 3);ListPushFront(pHead, 4);ListPushFront(pHead, 5);ListPushFront(pHead, 6);ListNode* node ListFind(pHead, 3);//在链表中查找if (node){//修改链表的值node-_data 90;}ListPrint(pHead);ListDestory(pHead);
}
7.全部代码
//List.h
#includestdio.h
#includestdlib.h
#includeassert.h
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* _next;struct ListNode* _prev;LTDataType _data;
}ListNode;void ListPushBack(ListNode* phead, LTDataType data);//尾插void ListPopBack(ListNode* phead);//尾删除
void ListPushFront(ListNode* phead,LTDataType data);//头插
void ListPopFront(ListNode* phead);//头删插
ListNode* BuyListNode(LTDataType data);//申请节点
void ListInit(ListNode** pphead);//初始化链表void ListInsert(ListNode* pos, LTDataType data);//pos位置之前的插入void ListErase(ListNode* pos);//pos位置的删除
//清理链表
void ListClear(ListNode* phead);void ListDestory(ListNode** ppHead);//摧毁链表void ListPrint(ListNode* phead);//打印链表
ListNode* ListFind(ListNode* phead, LTDataType data);//查找链表//List.c
#includeList.h
void ListPushBack(ListNode* phead, LTDataType data)//尾插
{assert(phead);ListNode* newNode BuyListNode(data);//申请新节点ListNode* tail phead-_prev;//找尾结点//链接新节点和尾结点tail-_next newNode;newNode-_prev tail;//与头结点进行链接phead-_prev newNode;newNode-_next phead;
}
void ListPopBack(ListNode* phead)//尾删除
{//确保指针不为空assert(phead);assert(phead-_next ! phead);//保留头结点//找尾ListNode* tail phead-_prev;ListNode* newTail tail-_prev;//找到新的尾结点//删除旧的尾结点free(tail);//重新链接头尾节点newTail-_next phead;phead-_prev newTail;
}
void ListPushFront(ListNode* phead, LTDataType data)//头插
{//确保指针不为空assert(phead);//申请新的节点ListNode* newNode BuyListNode(data);//进行链接ListNode* realHead phead-_next;realHead-_prev newNode;newNode-_next realHead;phead-_next newNode;newNode-_prev phead;
}
void ListPopFront(ListNode* phead)//头删插
{//指针存在assert(phead);//并且确保不能删除头结点assert(phead-_next ! phead);//找到真正的头ListNode* realHead phead-_next;ListNode* realHeadNext realHead-_next;//删除头节点free(realHead);//重新链接phead-_next realHeadNext;realHeadNext-_prev phead;
}
ListNode* BuyListNode(LTDataType data)//申请节点
{ListNode* newNode (ListNode*)malloc(sizeof(ListNode));if (newNode NULL){printf(申请空间失败\n);exit(-1);}newNode-_data data;return newNode;
}
void ListInit(ListNode** pphead)//初始化链表
{*pphead BuyListNode(0);//申请头结点//并且初始化(*pphead)-_next *pphead;(*pphead)-_prev *pphead;
}
void ListPrint(ListNode* phead)//打印链表
{assert(phead);ListNode* cur phead-_next;while (cur ! phead){printf(%d , cur-_data);cur cur-_next;}printf(\n);
}
void ListInsert(ListNode* pos, LTDataType data)//pos位置之前的插入
{assert(pos);//确保指针有效ListNode* newNode BuyListNode(data);//申请节点//进行链接ListNode* prev pos-_prev;ListNode* next pos;prev-_next newNode;newNode-_prev prev;newNode-_next next;next-_prev newNode;
}
void ListErase(ListNode* pos)//pos位置的删除
{//确保指针有效assert(pos);ListNode* next pos-_next;ListNode* prev pos-_prev;//删除pos所指向的节点free(pos);//进行重新链接prev-_next next;next-_prev prev;
}
//清理链表
void ListClear(ListNode* phead)
{assert(phead);//确保链表不为空assert(phead-_next ! phead);//除了确保不清理头结点ListNode* cur phead-_next;while (cur ! phead){ListNode* clearNode cur;cur cur-_next;free(clearNode);}
}
void ListDestory(ListNode** ppHead)//摧毁链表
{assert(*ppHead);//确保指针不为空ListClear(*ppHead);free(*ppHead);//释放头结点
}
ListNode* ListFind(ListNode* phead, LTDataType data)//查找链表
{assert(phead);ListNode* cur phead-_next;while (cur ! phead){if (cur-_data data)return cur;cur cur-_next;}return NULL;//找不到返回NULL
}
//test.c
#includeList.h
void ListTest1()
{//尾插尾删的测试代码ListNode* pHead NULL;ListInit(pHead);ListPushBack(pHead, 1);ListPushBack(pHead, 2);ListPushBack(pHead, 3);ListPushBack(pHead, 4);ListPushBack(pHead, 5);ListPushBack(pHead, 6);ListPrint(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);//ListPopBack(pHead);}
void ListTest2()
{//头插头删的测试ListNode* pHead NULL;ListInit(pHead);ListPushFront(pHead, 1);ListPushFront(pHead, 2);ListPushFront(pHead, 3);ListPushFront(pHead, 4);ListPushFront(pHead, 5);ListPushFront(pHead, 6);ListPrint(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);}
void ListTest3()
{//Destory和Clear的测试ListNode* pHead NULL;ListInit(pHead);ListPushFront(pHead, 1);ListPushFront(pHead, 2);ListPushFront(pHead, 3);ListPushFront(pHead, 4);ListPushFront(pHead, 5);ListPushFront(pHead, 6);ListDestory(pHead);
}
int main()
{ListTest3();return 0;
} 8.测试代码
void ListTest1()
{//尾插尾删的测试代码ListNode* pHead NULL;ListInit(pHead);ListPushBack(pHead, 1);ListPushBack(pHead, 2);ListPushBack(pHead, 3);ListPushBack(pHead, 4);ListPushBack(pHead, 5);ListPushBack(pHead, 6);ListPrint(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);ListPopBack(pHead);//ListPopBack(pHead);}
void ListTest2()
{//头插头删的测试ListNode* pHead NULL;ListInit(pHead);ListPushFront(pHead, 1);ListPushFront(pHead, 2);ListPushFront(pHead, 3);ListPushFront(pHead, 4);ListPushFront(pHead, 5);ListPushFront(pHead, 6);ListPrint(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);ListPopFront(pHead);}
void ListTest3()
{//Destory和Clear的测试ListNode* pHead NULL;ListInit(pHead);ListPushFront(pHead, 1);ListPushFront(pHead, 2);ListPushFront(pHead, 3);ListPushFront(pHead, 4);ListPushFront(pHead, 5);ListPushFront(pHead, 6);ListDestory(pHead);
}
