数据结构2（初）：顺序表和链表

目录

1、线性表

2、顺序表

2.1、概念及结构

2.2、顺序表的实现

2.3、顺序表的问题及思考

3、链表

3.1、链表的概念及结构

3.2、链表的分类

3.3、无头单向非循环链表的实现

3.4、带头双向循环链表的实现

4、顺序表和链表的区别和联系

---

1、线性表

线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

2、顺序表

2.1、概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存 储。在数组上完成数据的增删查改。

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。

2. 动态顺序表：使用动态开辟的数组存储。

2.2、顺序表的实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空 间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间 大小，所以下面我们实现动态顺序表。

头文件：

//头文件h.h
//动态的顺序表
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
 
typedef int type;
 
typedef struct list
{
	type* a;//指向动态内存开辟的空间
	size_t capacity;//容量空间的大小
	size_t size;//存储的内容大小
}LT;
 
//顺序表的的初始化
void LTinit(LT* p);
 
//检查空间，如果满了就进行增容
void LTcheckcapacity(LT* p);
 
//尾插
void LTtailpush(LT* p,type x);
 
//头插
void LTfrontpush(LT* p, type x);
 
//尾删
void LTtailpop(LT* p);
 
//头删
void LTfrontpop(LT* p);
 
//查找
int LTfind(LT ph,type x);
 
//pos位置前插入
void LTinsert(LT* p,size_t pos, type x);
 
//删除pos位置的值
void LTdelete(LT* p, size_t pos);
 
//顺序表的销毁
void LTdestory(LT* p);
 
//顺序表的打印
void LTprint(LT ph);

实现：

//实现f.c
#include"h.h"
//顺序表的的初始化
void LTinit(LT* p)//传一级指针就可以改变一个结构体内部的成员。
{
	assert(p);
 
	p->a = NULL;
	p->capacity = 0;
	p->size = 0;
}
 
//检查空间
bool LTcheck(LT* p)
{
	assert(p);
 
	if (p->capacity == p->size)
	{
		return true;
	}
	else
		return false;
}
 
//检查空间，如果满了就进行增容
void LTcheckcapacity(LT* p)
{
	assert(p);
	
	if (LTcheck(p) == true)
	{
		int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;           
		LT* newlist = (LT*)realloc(p->a, sizeof(type) * newcapacity);            
 
		if (newlist == NULL)//开完容量不要忘记还要判断容量是否开辟成功
		{
			perror("fail realloc");
			return;
		}
 
		p->a = newlist;
		p->capacity = newcapacity;
	}
}
 
//尾插
void LTtailpush(LT* p,type x)
{
	assert(p);
 
	LTcheckcapacity(p);
 
	p->a[p->size] = x;
 
	p->size++;
 
}
 
//头插
void LTfrontpush(LT* p, type x)
{
	assert(p);
 
	LTcheckcapacity(p);
 
	int i = 0;
	for (i = p->size; i > 0; i--)
	{
		p->a[i] = p->a[i - 1];
	}
 
	p->a[0] = x;
	p->size++;
}
 
//顺序表的打印   
void LTprint(LT ph)
{
	int i = 0;
	for (i = 0; i < ph.size; i++)
	{
		printf("%d->", ph.a[i]);
	}
	printf("NULL\n");
}
 
//尾删
void LTtailpop(LT* p)  
{
	assert(p);
 
	p->size = p->size - 1;
}
 
//头删
void LTfrontpop(LT* p)
{
	assert(p);
 
	for (int i = 0; i < p->size-1; i++)
	{
		p->a[i] = p->a[i + 1];
	}
	p->size = p->size - 1;
}
 
//查找
int LTfind(LT ph,type x)
{
	int i = 0;
	while (i<ph.size)
	{
		if (ph.a[i] == x)
		{
			return i;
		}
		i++;
	}
	return -1;
}
 
 
//pos位置前插入（这里的pos位置表示下标）
void LTinsert(LT* p, size_t pos, type x)
{
	assert(p);
	assert(pos >= 0 && pos < p->size);                
 
	int i = 0;
	for (i = p->size; i > pos; i--)
	{
		p->a[i] = p->a[i - 1];
	}
	p->a[pos] = x;
	p->size++;
}
 
//删除pos位置的值(注意这里的pos表示下标)
void LTdelete(LT* p, size_t pos)
{
	assert(p);
	assert(pos >= 0 && pos < p->size);                                               
 
	int i = pos;
	while (i < p->size-1)
	{
		p->a[i] = p->a[i + 1];
		i++;
	}
	p->size--;
}
 
//顺序表的销毁
void LTdestory(LT* p)
{
	assert(p);
	if (p->a != NULL)              //要注意进行判断一下。
	{
		free(p->a);
		p->a = NULL;
		p->capacity = 0;
		p->size = 0;
	}
}

2.3、顺序表的问题及思考

问题：

1. 中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？下面给出了链表的结构来看看。

3、链表

3.1、链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。

这种结构就像小火车一样

注意：

1、从图上也可以看出，链式结构在逻辑上是连续的，但是在物理上不一定是连续的。

2、链表上的节点一般是从堆上申请的。

3、从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续也可能不连续。

3.2、链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：

结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：

结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

3.3、无头单向非循环链表的实现

头文件：

//头文件head.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int type;
 
typedef struct ChainList
{
	type data;
	struct ChainList* next;
}CList;
 
//动态申请一个节点;
CList* CListApply(type x);
 
//遍历链表
void CListPrint(CList* p);
 
//单链表头插
void CListpushfront(CList** pf, type x);
 
//单链表尾插
void CListpushback(CList** pf, type x);
 
//单链表的头删
void CListpopfront(CList** pf);
 
//单链表的尾删
void CListpopback(CList** pf);
 
//单链表pos之前插入
void CListpush(CList** pf, CList* pos, type x);
 
//单链表的pos删除
void CListpop(CList** pf, CList* pos);
 
//单链表的销毁
void CListdestory(CList** pf);
 
//单链表的查找
CList* CListfind(CList* p, type x);

源文件：

//实现funtion.c
#include"head.h"
//动态申请一个节点;
CList* CListApply(type x)
{
	CList* newapply = (CList*)malloc(sizeof(CList));
	if (newapply == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newapply->data = x;
	newapply->next = NULL;
 
	return newapply;
}
 
//单链表打印
void CListPrint(CList* p)
{
	CList* cur = p;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
 
//单链表头插
void CListpushfront(CList** pf,type x)
{
	assert(pf);
	CList* newfront = CListApply(x);
	newfront->next = *pf;
	*pf = newfront;
}
 
 
//单链表尾插
void CListpushback(CList** pf, type x)
{
	assert(pf);
	CList* newback= CListApply(x);
	//空链表
	if (*pf == NULL)
	{
		*pf = newback;
	}
	//非空链表
	else
	{
		CList* tail = *pf;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newback;
	}
}
 
//单链表的尾删
void CListpopback(CList** pf)
{
	assert(pf);
	assert(*pf);
	//一个节点
	
	if ((*pf)->next == NULL)      //要注意要用上括号包起来*pf
	{
		free(*pf);
		*pf = NULL;
	}
	//多个节点
	else
	{
		CList* p = *pf;
		while (p->next->next != NULL)
		{
			p = p->next;
		}
		free(p->next);
		p->next = NULL;
	}
}
 
//单链表的头删
void CListpopfront(CList** pf)
{
	assert(*pf);
	assert(pf);
	CList* p = *pf;
	*pf=(*pf)->next;
	free(p);
}
 
 
//单链表的查找
CList* CListfind(CList* p,type x)
{
	//assert(p);
	CList* test = p;
	while (test)
	{
		if (test->data == x)
		{
			//printf("找到了");
			return test;
		}
		else
		{
			test = test->next;
		}          
	}
	return NULL;
}
 
//单链表pos之前插入
void CListpush(CList** pf,CList* pos, type x)
{
	assert(*pf);
	assert(pos);
	assert(pf);
	//第一个节点
	if (*pf==pos)
	{
		CListpushfront(pf,x);
	}
	//多个节点
	else
	{
		CList* p = *pf;
		while (p->next != pos)
		{
			p = p->next;
		}
		CList* exchange = CListApply(x);
		p->next = exchange;
		exchange->next = pos;
	}
}
 
//单链表的pos删除
void CListpop(CList** pf, CList* pos)
{
	assert(*pf);
	assert(pos);
	assert(pf);
	//一个节点
	if (*pf == pos)
	{
		free(pos);        
		pos = NULL;
	}
	//多个节点时
	else
	{
		CList* p = *pf;
		while (p->next != pos)
		{
			p = p->next;
		}
		p->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
 
//单链表的销毁
void CListdestory(CList** pf)
{
	assert(pf);
	CList* p = *pf;
	while (p)
	{
		CList* next = p->next;
		free(p);
		p = next;
	}
	*pf = NULL;
}

3.4、带头双向循环链表的实现

头文件：

//头文件head.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
typedef int LTDataNode;
 
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataNode data;
}LTNode;
 
LTNode* LTInit();
 
void LTPrint(LTNode* phead);
 
bool LTEmpty(LTNode* phead);
 
void LTPushBack(LTNode* phead, LTDataNode x);
 
void LTPushFront(LTNode* phead, LTDataNode x);
 
void LTPopBack(LTNode* phead);
 
void LTPopFront(LTNode* phead);
 
LTNode* LTFind(LTNode* phead, LTDataNode x);
 
//在pos之前插入
void LTInsert(LTNode* pos, LTDataNode x);
 
//删除pos处的值
void LTErase(LTNode* pos);
 
void LTDestory(LTNode* phead);

实现：

//实现funtion.c
#include"head.h"
LTNode* BuyLTNode(LTDataNode x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
 
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
}
 
LTNode* LTInit()
{
	LTNode* phead= BuyLTNode(-1);
	phead->prev = phead;
	phead->next=phead;
 
	return phead;
}
 
void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	printf("guard<==>");
	while (cur != phead)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
 
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead == phead->next;
}
 
 
void LTPushBack(LTNode* phead, LTDataNode x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);
 
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
 
void LTPushFront(LTNode* phead, LTDataNode x)
{
	assert(phead);
	LTNode* newnode= BuyLTNode(x);
 
 
 
	newnode->next = phead->next;
	phead->next->prev = newnode;
 
	phead->next = newnode;
	newnode->prev = phead;
}
 
 
 
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTNode* tail = phead->next;
	LTNode* tailprev = tail->prev;
 
	free(tail);
	tailprev->next = phead;
	phead->prev = tailprev;
}
 
 
void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTNode* next = phead->next;
	phead->next = next->next;
	phead->next->prev = phead;
 
	free(next);
}
 
 
LTNode* LTFind(LTNode* phead, LTDataNode x)
{
	assert(phead);
 
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
 
 
//
void LTInsert(LTNode* pos, LTDataNode x)
{
	assert(pos);
 
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyLTNode(x);
 
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
 
void LTErase(LTNode* pos)
{
	assert(pos);
 
	LTNode* posprev = pos->prev;
	LTNode* posnext = pos->next;
 
	posprev->next = posnext;
	posnext->prev = posprev;
 
	free(pos);
}
 
 
void LTDestory(LTNode* phead)
{
	assert(phead);
 
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

4、顺序表和链表的区别和联系

不同点                                       顺序表                                           链表

存储空间上 ：                       物理上一定连续                             逻辑上连续，但物理上不一定连续

随机访问  ：                                    支持O(1)                                         不支持：O(N)

任意位置插入或者删除元素：   可能需要搬移元素，效率低 O(N)        只需修改指针指向

插入 ：                                    动态顺序表，空间不够时需要扩容                没有容量的概念

应用场景 ：                              元素高效存储+频繁访问                      任意位置插入和删除频繁

缓存利用率：                        高 （物理地址连续，CPU高速缓存命中率高）                   低

备注：缓存利用率参考存储体系结构以及局部原理性。

上面的主存也就是内存，是带电存储信息的。本地二级存储，也就是硬盘，是不带电存储的。

CPU是不会直接访问内存的，因为CPU很快，内存比较慢。

在CPU和内存之间还有三级缓存（L1，L2，L3）以及寄存器。

数据较少时就会将数据直接放入寄存器中，数据较大就会放入到三级缓存中，一级一级放。

1、先看数据是否在缓存中，在就叫缓存命中，则直接进行访问。

2、不在就不命中，先加载数据到缓存，然后再访问。

对于CPU来讲，它是不会一个一个字节去加载数据的，一般来讲都是要一块一块的加载数据的。

对于更多关于CPU缓存的知识，请自行搜索。

另外本篇文章还没有结束，因为太长了，换到了下一篇来讲。

另外，欢迎各位读者到评论区进行交流。