结点结构与头结点的创建
创建两个源文件和一个头文件
test.c
linked_list.c
linked_list.h
带头双向循环链表，那么，结点的结构就要有两个指针域，分别指向前一个结点和后一个结点。
整个链表大概就是这样一个结构。
#define TYPE int typedef struct Linked_list//结点的内部结构 { struct Linked_list* prev;//前指针 struct Linked_list* next;//后指针 TYPE data; }LL;
创建头结点时要注意，我们要的时循环结构，所以也要让头结点的前指针和后指针都指向自己才符合循环结构。（在后面的操作也是比较方便的）
LL* ListCreate()//创建头结点 { LL* head = (LL*)malloc(sizeof(LL)); if (head == NULL) { perror("malloc fail"); exit(-1); } head->next = head; head->prev = head; return head; }
头插尾插
因为有头结点的关系，就不需要判断是否是第一个结点的问题了。
这里尾插就很方便了，不像之前需要遍历找尾，因为是循环链表，尾的next就是头结点。
当然这里要先写一个创建新结点的函数。
//linked_list.c LL* BuyLisNode(TYPE x) { LL* newnode = (LL*)malloc(sizeof(LL)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL;//因为是要链接进链表的结点，所以指向空就可以了 newnode->prev = NULL; return newnode;//返回新结点的地址 }
尾插
void ListPushBack(LL* phead, TYPE x)//尾插 { assert(phead); LL* newnode = BuyLisNode(x); LL* tail = phead->prev;//储存尾结点 tail->next = newnode;//让尾的next指向新节点 newnode->prev = tail;//新结点的prev指向尾 newnode->next = phead;//新节点的next指向头结点 phead->prev = newnode;//头结点的prev指向新结点 }
头插
void ListPushFront(LL* phead, TYPE x)//头插 { assert(phead); LL* newnode = BuyLisNode(x); LL* head = phead->next;//储存头结点的下一个结点 phead->next = newnode;//让头结点的next指向新结点 newnode->prev = phead;//新结点的prev指向头结点 newnode->next = head;//新结点next指向头结点的下一个结点 head->prev = newnode;//头结点的下一个结点指向新结点 }
打印链表
这里就要遍历链表了，因为是循环结构，所以结尾就不用空指针进行判断了。
void ListPrint(LL* phead)//打印链表 { assert(phead); LL* cur = phead->next; while (cur != phead)//遍历链表，结尾是cur指向的的如果是phead就说明上一个结点就是尾 { printf("%d ", cur->data);//打印 cur = cur->next; } printf("\n"); }
头删与尾删
删除的话，我们需要写一个函数判断链表中是否还有数据，如果只剩一个头结点就不能继续删除了。
bool estimate(LL* phead)//判断是否还有数据 { return phead->next == phead;//这里要注意，相等返回1，不相同返回0 }
尾删
删除尾结点的时候要将倒数第二个结点与头结点进行连接。
void ListPopBack(LL* phead)// 尾删 { assert(phead); assert(!estimate(phead));//判断是否还有数据，这里别忘记用!号 LL* cur = phead->prev;//储存要删除的尾结点 phead->prev = cur->prev;//让头结点的prev指向倒数第二个结点 cur->prev->next = phead;//让倒是第二个结点的next指向头结点 free(cur);//释放 }
头删
删除第一个结点也要注意判断是否还有数据和第二个结点与头结点的连接。
void ListPopFront(LL* phead)//头删 { assert(phead); assert(!estimate(phead)); LL* cur = phead->next;//储存要删除的第一个结点 phead->next = cur->next;//头结点的next指向第二个结点 cur->next->prev = phead;//第二个结点的prev指向头结点 free(cur);//释放 }
链表的查找
LL* ListFind(LL* phead, TYPE x)//查找 { assert(phead); LL* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur;//找到返回当前地址 } cur = cur->next; } return NULL;//找不到返回空指针 }
在pos的前面进行插入与删除pos位置的结点
pos是配合查找的，如果pos传错了也没办法。
插入
void ListInsert(LL* pos, TYPE x)//在pos的前面进行插入 { LL* cur = BuyLisNode(x);// 创建新结点 LL* prev = pos->prev;//找到pos前面的结点 pos->prev = cur;//下面四步是新节点与pos前面结点和pos结点建立联系 cur->next = pos; cur->prev = prev; prev->next = cur; }
删除
void ListErase(LL* pos)//删除pos位置的结点 { LL* prev = pos->prev;//储存pos前面的结点 LL* next = pos->next;//储存pos后面的结点 prev->next = next;//让pos前后结点建立联系 next->prev = prev; free(pos);//释放 }
销毁链表
这里注意，头结点也要释放掉。
void ListDestory(LL* phead)//销毁链表 { assert(phead); LL* cur = phead->next; while (cur != phead)//释放除了头结点以外的结点 { LL* next = cur->next; free(cur); cur = next; } free(phead);//释放头结点 }
完整代码
linked_list.h
#include <stdio.h> #include <assert.h> #include <stdlib.h> #include <stdbool.h> typedef int TYPE; typedef struct Linked_list//结点的内部结构 { struct Linked_list* prev;//前指针 struct Linked_list* next;//后指针 TYPE data; }LL; LL* ListCreate();//创建头结点 void ListPushBack(LL* phead, TYPE x);//尾插 void ListPushFront(LL* phead, TYPE x);//头插 void ListPrint(LL* phead);//打印链表 void ListPopBack(LL* phead);// 尾删 void ListPopFront(LL* phead);//头删 LL* ListFind(LL* phead, TYPE x);//查找 void ListInsert(LL* pos, TYPE x);//在pos的前面进行插入 void ListErase(LL* pos);//删除pos位置的结点 void ListDestory(LL* phead);//销毁链表
linked_list.c
#include "linked_list.h" LL* ListCreate()//创建头结点 { LL* head = (LL*)malloc(sizeof(LL)); if (head==NULL) { perror("malloc fail"); exit(-1); } head->next = head; head->prev = head; return head; } LL* BuyLisNode(TYPE x)//创建新结点 { LL* newnode = (LL*)malloc(sizeof(LL)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL;//因为是链接进链表的结点，所以指向空就可以了 newnode->prev = NULL; return newnode; } void ListPushBack(LL* phead, TYPE x)//尾插 { assert(phead); LL* newnode = BuyLisNode(x);//创建新结点 LL* tail = phead->prev;//储存尾结点 tail->next = newnode;//让尾的next指向新节点 newnode->prev = tail;//新结点的prev指向尾 newnode->next = phead;//新节点的next指向头结点 phead->prev = newnode;//头结点的prev指向新结点 } void ListPushFront(LL* phead, TYPE x)//头插 { assert(phead); LL* newnode = BuyLisNode(x); LL* head = phead->next;//储存头结点的下一个结点 phead->next = newnode;//让头结点的next指向新结点 newnode->prev = phead;//新结点的prev指向头结点 newnode->next = head;//新结点next指向头结点的下一个结点 head->prev = newnode;//头结点的下一个结点指向新结点 } bool estimate(LL* phead)//判断是否还有数据 { return phead->next == phead;//这里要注意，相等返回0，不相同返回1 } void ListPrint(LL* phead)//打印链表 { assert(phead); LL* cur = phead->next; while (cur != phead)//遍历链表 { printf("%d ", cur->data);//打印 cur = cur->next; } printf("\n"); } void ListPopBack(LL* phead)// 尾删 { assert(phead); assert(!estimate(phead));//判断是否还有数据 LL* cur = phead->prev;//储存要删除的尾结点 phead->prev = cur->prev;//让头结点的prev指向倒数第二个结点 cur->prev->next = phead;//让倒是第二个结点的next指向头结点 free(cur);//释放 } void ListPopFront(LL* phead)//头删 { assert(phead); assert(!estimate(phead)); LL* cur = phead->next;//储存要删除的第一个结点 phead->next = cur->next;//头结点的next指向第二个结点 cur->next->prev = phead;//第二个结点的prev指向头结点 free(cur);//释放 } LL* ListFind(LL* phead, TYPE x)//查找 { assert(phead); LL* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur;//找到返回当前地址 } cur = cur->next; } return NULL;//找不到返回空指针 } void ListInsert(LL* pos, TYPE x)//在pos的前面进行插入 { LL* cur = BuyLisNode(x);// 创建新结点 LL* prev = pos->prev;//找到pos前面的结点 pos->prev = cur;//下面四步是新节点与pos前面结点和pos结点建立联系 cur->next = pos; cur->prev = prev; prev->next = cur; } void ListErase(LL* pos)//删除pos位置的结点 { LL* prev = pos->prev;//储存pos前面的结点 LL* next = pos->next;//储存pos后面的结点 prev->next = next;//让pos前后结点建立联系 next->prev = prev; free(pos);//释放 } void ListDestory(LL* phead)//销毁链表 { assert(phead); LL* cur = phead->next; while (cur != phead)//释放除了头结点以外的结点 { LL* next = cur->next; free(cur); cur = next; } free(phead);//释放头结点 }
test.c
#include "linked_list.h" void test() { LL* head = NULL; head = ListCreate();//创建头结点 ListPushBack(head, 5);//尾插 ListPushBack(head, 7);//尾插 ListPushFront(head, 8);//头插 ListPushFront(head, 6);//头插 ListPopBack(head);//尾删 ListPopFront(head);//头删 ListPrint(head);//打印链表 LL* pos = ListFind(head, 5);//查找 if (pos != NULL) { printf("YES\n"); } else { printf("NO\n"); } ListInsert(pos, 3);//在pos的前面进行插入 ListPrint(head);//打印链表 ListErase(pos);//删除pos位置的结点 ListPrint(head);//打印链表 ListDestory(head);//销毁链表 ListPrint(head);//打印链表 } int main() { test(); return 0; }
运行结果：
