双向循环链表
结构
包含数据域,指针域(前驱节点prev和后继节点next)
介绍
结构最复杂，一般用在单独存储数据。
实际中使用的链表数据结构，都是带头双向循环链表。
另外这个结构虽然结构复杂，
但是使用代码实现以后会发现结构会带来很多优势，但实现简单
图示
双向链表的实现
在List.h中
定义双向链表的结构
typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* prev; struct ListNode* next; }LTNode;
实现双向链表的接口/方法
//初始化 LTNode* LTInit(); //销毁链表 void LTDestroy(LTNode* phead); //打印链表 void LTPrint(LTNode* phead); //判断链表是否为空 bool LTEmpty(LTNode* phead); //尾插 void LTPushBack(LTNode* phead, LTDataType x); //头插 void LTPushFront(LTNode* phead, LTDataType x); //尾删 void LTPopBack(LTNode* phead); //头删 void LTPopFront(LTNode* phead); //在pos位置之后插入数据 void LTInsert(LTNode* pos, LTDataType x); //删除pos指定节点 void LTErase(LTNode* pos); //查找链表的指定元素 LTNode* LTFind(LTNode* phead, LTDataType x);
在List.c中
初始化
//初始化 LTNode* LTInit() { LTNode* phead = LTBuyNode(-1); return phead; }
销毁链表
//销毁 void LTDestroy(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; while (pcur != phead) { LTNode* next = pcur->next; free(pcur); pcur = next; } //最后释放头节点的内存并置空 free(phead); phead = NULL; }
打印链表
//打印双向链表 void LTPrint(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; while (pcur != phead) { printf("%d->", pcur->data); pcur = pcur->next; } printf("\n"); }
判断链表是否为空
bool LTEmpty(LTNode* phead) { if (phead->next == phead) { return true; } else { return false; } }
尾插
//尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTBuyNode(x); newnode->next = phead; newnode->prev = phead->prev; phead->prev->next = newnode; phead->prev = newnode; }
后四行的方向和赋值问题
有新开节点newnode
测试
头插
//头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTBuyNode(x); LTNode* pcur = phead->next; newnode->next = pcur; newnode->prev = phead; phead->next = newnode; pcur->prev = newnode; }
测试
尾删
//尾删 void LTPopBack(LTNode* phead) { assert(phead); LTNode* p1 = phead->prev; LTNode* pcur = p1->prev; pcur->next = phead; phead->prev = pcur; free(p1); p1 = NULL; }
测试
头删
//头删 void LTPopFront(LTNode* phead) { assert(phead); LTNode* pcur = phead->next->next; LTNode* p1 = phead->next; phead->next = pcur; pcur->prev = phead; free(p1); p1 = NULL; }
测试
在pos位置之后插入数据
//在pos位置之后插入数据 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTBuyNode(x); newnode->next = pos->next; newnode->prev = pos; //如果pos是最后一个节点 if (pos->next == NULL) { newnode->next = NULL; } else { pos->next->prev = newnode; } pos->next = newnode; }
测试
删除pos指定节点
//删除pos节点 void LTErase(LTNode* pos) { assert(pos); LTNode* p1 = pos->prev; LTNode* pcur = pos->next; p1->next = pcur; pcur->prev = p1; free(pos); pos = NULL; }
测试
查找链表的指定元素
//查找元素 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* pcur = phead->next; while (pcur != phead) //注意循环条件! { if (pcur->data == x) { return pcur; } else { pcur = pcur->next; } } return NULL; }
