哈喽,今天阿紫姐姐召集各位武林侠士,有什么事情了???

众人所答:当然是阿紫姐姐又来带领我们学习新的功夫啦!!!

首先,练功夫之前得热身(小声告诉你们哦,阿紫姐姐说的热身是心灵鸡汤哦)

* 坚持就是胜利,每当我们坚持不下去的时候,我们都要告诉自己,胜利就在不远方,要是放弃之前的努力都将会功亏一篑。
* 一定要坚持、坚持 、坚持哦!!!
* 坚持才是做任何事情的秘诀。
回顾:

首先我们来看看单链表有哪些缺点了???

单链表主要缺点:①不能从后往前遍历 ②找不到前驱

单链表缺陷解决方案-》双链表:

有八种链表结构:

 带头双向循环链表代码实现:

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; }

尾插
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;
} void ListPushBack(ListNode* phead, LTDataType x) { ListNode* tail =
phead->prev; ListNode* newnode = BuyListNode(x); tail->next = newnode;
newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }

 尾删
void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next !=
phead); ListNode* tail = phead->prev; ListNode* prev = tail->prev; prev->next =
phead; phead->prev = prev; free(tail); tail = NULL; }

 头插:
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;
} void ListPushFront(ListNode* phead, LTDataType x) { assert(phead); ListNode*
first = phead->next; ListNode* newnode = BuyListNode(x); phead->next = newnode;
newnode->prev = phead; newnode->next = first; first->prev = newnode; }

 头删:
void ListPopFront(ListNode* phead) { assert(phead); assert(phead->next !=
phead); ListNode* first = phead->next; ListNode* second = first->next;
phead->next = second; second->prev = phead; free(first); first = NULL; }

打印:
void ListPrint(ListNode* phead) { ListNode* cur = phead->next; while (cur !=
phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }

 查找:
ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead); ListNode*
cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; }
cur = cur->next; } return NULL; }
cur指向第一个结点,当结点的数据域不等于x,就去看下一个结点,要是最后找到phead都没有找到,就说明没有.

在某个结点前插入一个结点:
void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode
= BuyListNode(x); ListNode* prev = pos->prev; prev->next = newnode;
newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }

 删除某个结点:
void ListErase(ListNode* pos) { assert(pos); ListNode* prev = pos->prev;
ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos);
pos = NULL; }

 销毁链表:
void ListDestory(ListNode* phead) { assert(phead); ListNode* cur =
phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur
= next; } free(phead); phead = NULL; }

今天的双链表武功大家学会了吗???

好了今天就到这里!!!

技术
©2019-2020 Toolsou All rights reserved,
在算法研究过程中如何进行算法创新七大排序算法(java代码)MYSQL中的索引与事务———javaweb(8)(面试必考)2022蓝桥杯JavaB组省赛试题网络安全-wifi攻防网络层协议——ICMP协议MySQL查询表中指定条件下的最新记录JavaSE笔记(一)Java基础语法mysql 查询条件之外的数据_mysql 查询符合条件的数据qt使用数据库sqlite