目录
1.双链表的增删查改
逻辑图
双链表概述
双链表即双向链表，结构体成员开两个指针,一个指针用来存放前一个结点的地址，另一个用来存放后一个结点的地址。
带头双向循环链表，即带哨兵位头结点且循环的双链表，是更为复杂的链表。
链表分为8种：单链表、循环单链表、带头单链表、带头循环单链表、双链表、循环双链表、带头双链表、带头循环双链表。
其中最为复杂的是带头循环双链表，也是更容易实现代码，使代码变得简单，常用的链表。
双链表增删查改各个接口的实现
双链表框架(双链表头文件Dlist.h)
#pragma once #include <stdio.h> #include <assert.h>/*assert*/ #include <stdlib.h>/*malloc*/ #include <stdbool.h>/*bool类型返回值为true真或false假*/ // 带头+双向+循环链表增删查改实现 typedef int LTDataType;/*类型可以任意转换*/ typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }ListNode; // 创建返回链表的头结点. ListNode* ListCreate(); // 双向链表销毁 void ListDestory(ListNode* pHead); // 双向链表打印 void ListPrint(ListNode* pHead); // 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x); // 双向链表尾删 void ListPopBack(ListNode* pHead); // 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x); // 双向链表头删 void ListPopFront(ListNode* pHead); // 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(ListNode* pos);
双链表各个接口的实现(Dlist.c源文件)
链表哨兵位头结点创建、初始化
// 可以传二级，内部置空头结点 // 建议：也可以考虑用一级指针，让调用ListDestory的人置空 （保持接口一致性） ListNode* ListCreate() { ListNode* plist = (ListNode*)malloc(sizeof(ListNode)); if (plist == NULL) { perror("malloc fail"); exit(-1); } plist->next = plist; plist->prev = plist; return plist; }
创建一个结点
ListNode* BuyNode(LTDataType x) { ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); if (newNode == NULL) { perror("BuyNode malloc fail"); return NULL; } newNode->next = NULL; newNode->prev = NULL; newNode->data = x; return newNode; }
尾插
void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead); /*第1种写法*/ //ListNode* tail = pHead->prev; //ListNode* newNode = BuyNode(x); //tail->next = newNode; //newNode->prev = tail; //newNode->next = pHead; //pHead->prev = newNode; /*第2种写法，灵活运用双向链表的特性*/ ListInsert(pHead, x);/*pHead的前方插入，即尾部*/ }
尾删
void ListPopBack(ListNode* pHead) { assert(pHead); assert(pHead->next != pHead);/*只有哨兵位的头节点*/ /*第二种断言是否为空:assert(!ListEmpty(phead));*/ ListNode* tail = pHead->prev;/*老尾*/ ListNode* newtail = tail->prev;/*新尾*/ free(tail); newtail->next = pHead; pHead->prev = newtail; /*第二种尾删写法*/ /*ListErase(pHead->prev);*/ }
头插
void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* newNode = BuyNode(x); ListNode* oldNode = pHead->next;/*因为pHead是哨兵头*/ pHead->next = newNode; newNode->prev = pHead; newNode->next = oldNode; oldNode->prev = newNode; /*第2种*/ /*ListInsert(pHead->next, x);*/ }
头删
void ListPopFront(ListNode* pHead) { assert(pHead); /*第一种断言是否为空*/ if (pHead->next == pHead) { return;/*除了哨兵位，没有头结点*/ } /*第二种断言是否为空:assert(!ListEmpty(phead));*/ ListNode* oldHead = pHead->next; ListNode* newHead = oldHead->next; pHead->next = newHead; newHead->prev = pHead; free(oldHead); oldHead = NULL;/*置空不置空都可以，临时变量出栈销毁*/ /*第二种头删写法*/ /*ListErase(pHead->next);*/ }
判断链表是否为空
bool ListEmpty(ListNode* phead) { assert(phead); /*第一种*/ /*if (phead->next == phead) return true; else return false;*/ /*第二种*/ return phead->next == phead; }
查找
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; }
在pos节点前插入
void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* prev = pos->prev;/*pos节点的原前者,利用prev前，next后链接就可以了*/ ListNode* newNode = BuyNode(x); newNode->next = pos; pos->prev = newNode; prev->next = newNode; newNode->prev = prev; }
在pos节点处删除
void ListErase(ListNode* pos) { assert(pos); ListNode* next = pos->next; ListNode* prev = pos->prev; next->prev = prev; prev->next = next; 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); }
打印
void ListPrint(ListNode* pHead) { assert(pHead); ListNode* cur = pHead->next; printf("head<=>"); while (cur != pHead) { printf("%d<=>", cur->data); cur = cur->next; } printf("\n"); }
测试用的主函数所在的头文件(test.c)
#define _CRT_SECURE_NO_WARNINGS #include "DList.h"; void test() { ListNode* head = ListCreate(); /*尾插*/ ListPushBack(head, 1); ListPushBack(head, 2); ListPushBack(head, 3); ListPushBack(head, 4); ListPrint(head); /*尾删*/ ListPopBack(head); ListPopBack(head); ListPrint(head); /*头插*/ ListPushFront(head, 5); ListPushFront(head, 6); ListPushFront(head, 7); ListPushFront(head, 8); ListPrint(head); /*头删*/ ListPopFront(head); ListPopFront(head); ListPrint(head); /*查找与插入连用*/ ListNode* FindNode = ListFind(head, 5); if (FindNode != NULL) { ListInsert(FindNode, 5*100); ListPrint(head); } /*查找与删除连用*/ FindNode = ListFind(head, 500); if (FindNode != NULL) { ListErase(FindNode); } ListPrint(head); ListDestory(head); } int main() { test(); return 0; }
2.链表与顺序表的区别
顺序表优点
·尾插尾删效率很高
·随机访问(用下标)
·相比链表结构，顺序表cpu高速缓存命中率更高。(可以了解的知识范畴)
缺点
·头部和中部插入删除效率低,时间复杂度O(N)
·扩容，性能消耗和空间浪费
链表优点
·任意位置插入删除效率很高，时间复杂度O(1)
·按需申请释放
缺点
·不支持随机访问
计算机存储层次三角形(关于cpu高速缓存)
由下至上，成本越来越高，速度越来越快，存储越来越小。
数据结构是在主存中，vs代码经过编译后生成可执行文件，再由cpu访问，通过一定的接口，把执行的信息实现在终端窗口上
cpu执行指令不会直接访问内存
1.先看数据在不在三级缓存中，在(则命中)，直接访问
2.不在(不命中)，先加载到缓存，再访问
为什么顺序表比链表效率更高？
cpu看缓存中不命中（找不到）第一个数据，先加载到缓存，由于加载具有局部原理性，一次性可能会加载16个字节(依照电脑硬件，不唯一)，顺序表的效率比链表的效率更高，由于链表的地址不是连续的，所以会加载一些不用的数据，存在缓存污染，所以顺序表的高速缓存命中率更高。
关于计算机cpu缓存，陈皓专家大佬的博客可以看看：与程序员相关的CPU缓存知识 | 酷 壳 - CoolShell