2.6尾删节点
没什么好说的，和之前的一样关键点在链接上，自己画了图什么都知道
void list_popback(listnode*phead) { assert(phead); if (phead->next == phead) { printf("链表为空，操作失败\n");//为空就别删了 return; } listnode* tail = phead->prev;//找到尾节点 phead->prev = tail->prev; tail->prev->next = phead; free(tail); }
测试代码：
void test4() { listnode* plist = NULL; plist = init_listnode(plist); list_pushfront(plist, 1); list_pushfront(plist, 2); list_pushfront(plist, 10086); print_list(plist); list_popback(plist); print_list(plist); list_popback(plist); print_list(plist); list_popback(plist); print_list(plist); list_popback(plist); print_list(plist); } int main() { test4(); }
测试效果：
2.7查找节点
遍历一遍，找不到就返回NULL即可
listnode* list_find(listnode* phead, LTDateType x) //哨兵节点和目标 { assert(phead); listnode* head = phead->next;//找到头节点 while (head!=phead)//相等意味着已经遍历完了 { if (head->data == x) //找到目标，直接返回 { return head; } head = head->next; } return NULL;//遍历完还找不到，返回空指针 }
2.8在指定位置前插入节点
根据目标进行链接即可
void list_insert(listnode*pos,LTDateType x) //目标位置，和在其前面插入数据为x的节点 { if (pos == NULL)//传空意味着没找到目标 { printf("目标不存在，操作失败\n"); return; } listnode*newnode=buy_listnode(x);//创建新节点 newnode->next = pos; newnode->prev= pos->prev; pos->prev->next = newnode; pos->prev = newnode; }
测试代码：
void test5() { listnode* plist = NULL; plist = init_listnode(plist); list_pushfront(plist, 1); list_pushfront(plist, 2); list_pushfront(plist, 10086); print_list(plist); listnode*pos=list_find(plist,2); list_insert(pos, 888);//在2之前插入888 print_list(plist); list_insert(plist->next, 666); //在头节点前插入666，与头插效用一致 //可以在头插中复用这个函数 print_list(plist); list_insert(plist, 520); //在哨兵节点前插入520，与尾插效用一致 //可以在尾插中复用这个函数 print_list(plist); } int main() { test5(); }
测试效果：
2.9删除指定位置节点.
void list_erase(listnode* pos) { assert(pos && pos->next != pos); //pos为空意味着不存在，pos->next==pos意味着为哨兵节点 pos->next->prev = pos->prev; pos->prev->next = pos->next; free(pos); }
测试代码：
void test6() { listnode* plist = NULL; plist = init_listnode(plist); //list_erase(plist->prev);//尾删,测试报错 list_pushfront(plist, 1); list_pushfront(plist, 2); list_pushfront(plist, 3); list_pushfront(plist, 4); list_pushfront(plist, 5); print_list(plist); listnode* pos = list_find(plist, 2); list_erase(pos);//把2删除 print_list(plist); list_erase(plist->next);//头删 print_list(plist); list_erase(plist->prev);//尾删 print_list(plist); } int main() { test6(); }
测试效果：
2.10摧毁链表
void destory_list(listnode* phead) { listnode* tail = phead->prev; while (tail != phead) { listnode* tmp = tail;//存储尾 tail = tail->prev;//从后往前遍历 free(tmp); //不需要管什么链接了，直接摧毁就行 } free(phead);//单独摧毁 }
测试代码：
void test7() { listnode* plist = NULL; plist = init_listnode(plist); //list_erase(plist->prev);//尾删,测试报错 list_pushfront(plist, 1); list_pushfront(plist, 2); list_pushfront(plist, 3); list_pushfront(plist, 4); list_pushfront(plist, 5); destory_list(plist); } int main() { test7(); }
测试效果：
从监视来看，确实全部释放
三、全部代码
1.接口头文件
#pragma once//防止头文件二次引用 #include<stdio.h> #include<assert.h> #include<stdlib.h> typedef int LTDateType; //这样创建结构体数据类型，不仅是为了和int做区分 //也是为了到时更好的替换，想换直接把int改了就行 typedef struct listnode { struct listnode* prev;//存放上一个节点的地址 struct listnode* next;//存放下一个节点的地址 LTDateType data;//该节点存放的数据 }listnode; listnode* buy_listnode(LTDateType x); listnode* init_listnode(listnode* phead); void print_list(listnode* phead); void list_pushback(listnode* phead, LTDateType x); void list_pushfront(listnode* phead, LTDateType x); void list_popfront(listnode* phead); void list_popback(listnode* phead); listnode* list_find(listnode* phead, LTDateType x); void list_insert(listnode* pos, LTDateType x); void list_erase(listnode* pos); void destory_list(listnode* phead);
2.接口实现
#define _CRT_SECURE_NO_WARNINGS 1 #include"list.h" listnode* buy_listnode(LTDateType x) { listnode*newnode=(listnode*)malloc(sizeof(listnode)); if (newnode == NULL) { perror("buy_listnode");//错误提示 exit(-1);//节点都没创建出来，直接退出程序 } newnode->data = x;//将新节点的数据初始化成我们需要的 newnode->next = NULL;//不清楚插入的方式，先初始化成空 newnode->prev = NULL; } listnode* init_listnode(listnode* phead) { phead = buy_listnode(-1); //-1是随便给的，初始化哨兵节点中的数据为-1,代表着没意义的数据 phead->next = phead;//初始化哨兵节点，自己指向自己 phead->prev = phead; return phead; } void print_list(listnode* phead) { assert(phead);//哨兵节点地址不可能为空 listnode* head = phead->next; //哨兵位节点不存储有效数据，因此phead->next才是头节点 printf("head<=>");//纯属美观 while (head != phead)//当head和phead相等意味着已经遍历完一遍链表 { printf("%d<=>", head->data); head = head->next; } printf("\n"); } void list_pushback(listnode*phead,LTDateType x) //尾插一个新节点，此节点存储x { listnode* newnode = buy_listnode(x); //创建一个我们需要的新节点 listnode* tail = phead->prev; //先找尾，尾很显然是哨兵位节点的上一个节点 tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } void list_pushfront(listnode* phead, LTDateType x) { listnode* head = phead->next;//找到头节点 listnode* newnode = buy_listnode(x);//创建新节点 head->prev = newnode; newnode->next = head; phead->next = newnode; newnode->prev = phead; } void list_popfront(listnode*phead) { assert(phead); if (phead->next == phead) { printf("链表为空，操作失败\n");//为空就别删了 return; } listnode* head = phead->next;//找到头节点 phead->next = head->next; head->next->prev = phead; free(head);//链接完成，彻底删除 } void list_popback(listnode*phead) { assert(phead); if (phead->next == phead) { printf("链表为空，操作失败\n");//为空就别删了 return; } listnode* tail = phead->prev;//找到尾节点 phead->prev = tail->prev; tail->prev->next = phead; free(tail); } listnode* list_find(listnode* phead, LTDateType x) //哨兵节点和目标 { assert(phead); listnode* head = phead->next;//找到头节点 while (head!=phead)//相等意味着已经遍历完了 { if (head->data == x) //找到目标，直接返回 { return head; } head = head->next; } return NULL;//遍历完还找不到，返回空指针 } void list_insert(listnode*pos,LTDateType x) //目标位置，和在其前面插入数据为x的节点 { if (pos == NULL)//传空意味着没找到目标 { printf("目标不存在，操作失败\n"); return; } listnode*newnode=buy_listnode(x);//创建新节点 newnode->next = pos; newnode->prev= pos->prev; pos->prev->next = newnode; pos->prev = newnode; } void list_erase(listnode* pos) { assert(pos && pos->next != pos); pos->next->prev = pos->prev; pos->prev->next = pos->next; free(pos); } void destory_list(listnode* phead) { listnode* tail = phead->prev; while (tail != phead) { listnode* tmp = tail;//存储尾 tail = tail->prev;//从后往前遍历 free(tmp); //不需要管什么链接了，直接摧毁就行 } free(phead);//单独摧毁 }
3.测试文件
#define _CRT_SECURE_NO_WARNINGS 1 #include"list.h" void test1() { listnode* plist=NULL; plist=init_listnode(plist); list_pushback(plist,1); list_pushback(plist,2); list_pushback(plist,3); list_pushback(plist,4); print_list(plist); } void test2() { listnode* plist = NULL; plist = init_listnode(plist); list_pushfront(plist, 1); list_pushfront(plist, 2); print_list(plist); list_pushfront(plist, 10086); print_list(plist); } void test3() { listnode* plist = NULL; plist = init_listnode(plist); list_pushfront(plist, 1); list_pushfront(plist, 2); print_list(plist); list_pushfront(plist, 10086); print_list(plist); list_popfront(plist); print_list(plist); list_popfront(plist); print_list(plist); list_popfront(plist); print_list(plist); list_popfront(plist); print_list(plist); } void test4() { listnode* plist = NULL; plist = init_listnode(plist); list_pushfront(plist, 1); list_pushfront(plist, 2); list_pushfront(plist, 10086); print_list(plist); list_popback(plist); print_list(plist); list_popback(plist); print_list(plist); list_popback(plist); print_list(plist); list_popback(plist); print_list(plist); } void test5() { listnode* plist = NULL; plist = init_listnode(plist); list_pushfront(plist, 1); list_pushfront(plist, 2); list_pushfront(plist, 10086); print_list(plist); listnode*pos=list_find(plist,2); list_insert(pos, 888);//在2之前插入888 print_list(plist); list_insert(plist->next, 666); //在头节点前插入666，与头插效用一致 //可以在头插中复用这个函数 print_list(plist); list_insert(plist, 520); //在哨兵节点前插入520，与尾插效用一致 //可以在尾插中复用这个函数 print_list(plist); } void test6() { listnode* plist = NULL; plist = init_listnode(plist); //list_erase(plist->prev);//尾删,测试报错 list_pushfront(plist, 1); list_pushfront(plist, 2); list_pushfront(plist, 3); list_pushfront(plist, 4); list_pushfront(plist, 5); print_list(plist); listnode* pos = list_find(plist, 2); list_erase(pos);//把2删除 print_list(plist); list_erase(plist->next);//头删 print_list(plist); list_erase(plist->prev);//尾删 print_list(plist); } void test7() { listnode* plist = NULL; plist = init_listnode(plist); //list_erase(plist->prev);//尾删,测试报错 list_pushfront(plist, 1); list_pushfront(plist, 2); list_pushfront(plist, 3); list_pushfront(plist, 4); list_pushfront(plist, 5); destory_list(plist); } int main() { test7(); }
好了，今天的分享到这里就结束了，感谢各位友友来访，祝各位友友前程似锦O(∩_∩)O
