回顾：
首先我们来看看单链表有哪些缺点了？？？
单链表主要缺点：①不能从后往前遍历 ②找不到前驱
单链表缺陷解决方案-》双链表：
有八种链表结构：
带头双向循环链表代码实现：
list.h：头文件
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<assert.h> #pragma once typedef int LTDataType; //带头双向循环---最有链表结构，任意位置插入删除数据都是O（1） typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }ListNode; //初始化 ListNode* ListInit(ListNode* phead); //尾插 void ListPushBack(ListNode* phead,LTDataType x); //头插 void ListPushFront(ListNode* phead, LTDataType x); //打印 void ListPrint(ListNode* phead); //头删 void ListPopFront(ListNode* phead); //尾删 void ListPopBack(ListNode* phead); //查找 ListNode* ListFind(ListNode* phead, LTDataType x); //pos位置之前插入x void ListInsert(ListNode* pos, LTDataType x); //删除pos位置的值 void ListErase(ListNode* pos); //销毁链表 void ListDestory(ListNode* phead);
在头文件里面进行了库函数的头文件包含、结构体声明、类型重定义、自定义函数声明
test.c：测试文件
#define _CRT_SECURE_NO_WARNINGS 1 #include"list.h" void TestList1() { ListNode* plist = NULL; plist = ListInit(plist); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPushBack(plist, 5); ListPushBack(plist, 6); ListPrint(plist); ListPushFront(plist, 0); ListPrint(plist); ListPopFront(plist); ListPrint(plist); ListPopBack(plist); ListPrint(plist); ListNode* pos = ListFind(plist, 3); if (pos) { //查找附带修改作用 pos->data *= 10; printf("找到了,并且*10\n"); } else { printf("没有找到\n"); } ListPrint(plist); ListInsert(pos, 300); ListPrint(plist); ListErase(pos); ListPrint(plist); ListDestory(plist); } int main() { TestList1(); return 0; }
主要测试我们双链表的功能
接下来我们一个一个看自定义函数的实现：
链表初始化：
ListNode* BuyListNode(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { return; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } ListNode* ListInit(ListNode* phead) { phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead; }
