目录

1.双链表的增删查改

逻辑图​

双链表概述

双链表增删查改各个接口的实现

双链表框架(双链表头文件Dlist.h)

双链表各个接口的实现(Dlist.c源文件)

链表哨兵位头结点创建、初始化

创建一个结点

尾插

尾删

头插

头删

判断链表是否为空

查找

在pos节点前插入

在pos节点处删除

链表销毁

打印

测试用的主函数所在的头文件(test.c)

2.链表与顺序表的区别

顺序表优点

缺点

链表优点

缺点

计算机存储层次三角形(关于cpu高速缓存)

---

1.双链表的增删查改

逻辑图

双链表概述

双链表即双向链表，结构体成员开两个指针,一个指针用来存放前一个结点的地址，另一个用来存放后一个结点的地址。

带头双向循环链表，即带哨兵位头结点且循环的双链表，是更为复杂的链表。

链表分为8种：单链表、循环单链表、带头单链表、带头循环单链表、双链表、循环双链表、带头双链表、带头循环双链表。

其中最为复杂的是带头循环双链表，也是更容易实现代码，使代码变得简单，常用的链表。

双链表增删查改各个接口的实现

双链表框架(双链表头文件Dlist.h)

#pragma once
#include 
#include /*assert*/
#include /*malloc*/
#include /*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