引言-线性表

线性表：

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构，也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上存储时，通常以数组和链式结构的形式存储。

我们今天的主角，顺序表和链表，其实都是线性表，当然线性表不止包含这两个

线性表：

• 顺序表
• 链表
• 栈
• 队列
• 字符串
• ……

再次声明：线性表的逻辑结构是线性的，物理结构不一定是线性

顺序表

概念及结构

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

顺序表一般可以分为：

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

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

来跟我一起手搓个顺序表吧

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

我们先写一个头文件，里面写好我们维护的动态顺序表以及要实现的接口函数

结构及接口Sqlist.h

//Sqlist.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<assert.h>
#define INIT_CAPACITY 4
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
    SLDataType* a;//指向动态开辟数组
    int size;     // 有效数据个数
    int capacity; // 空间容量
}SL;

//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
//顺序表打印
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
//顺序表查找数据
int SLFind(SL* ps,SLDataType x);

往下就可以开始实现我们的顺序表内容了，下面对于接口的实现放在 Sqlist.c 中

初始化和销毁

void SLInit(SL* ps)
{
    ps->a = NULL; //开始时，给一个空指针
    ps->capacity = ps->size = 0;
}

void SLDestroy(SL* ps)
{
    assert(ps); //断言，防止ps为空指针
    ps->capacity = ps->size = 0;
    free(ps->a);
    ps->a = NULL;
}

顺序表打印

void SLPrint(SL* ps)
{
    assert(ps);
    for (int i = 0; i < ps->size; i++) {
        printf("%d\n",ps->a[i]);
    }
    printf("\n");
}

 这里需要注意的是，在打印过程中，往顺序表中放置的数据类型不同，所打印的方式也会有所不同，在头文件Sqlist.h中

typedef int SLDataType;

这句代码说明放入的数据类型是int，所以我这里就使用int的打印方式了。

扩容

void SLCheckCapacity(SL* ps)
{
    if (ps->size == ps->capacity) {
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
        //防止开辟空间失败返回空指针
        if (tmp == NULL) {
            perror("malloc fail:");
            exit(1);
        }
        ps->a = tmp;
        //更新容量
        ps->capacity = newCapacity;
    }
}

扩容的部分在整个动态顺序表中占据非常重要的地位，关系到堆中空间的开辟，保证后续数据操作的顺利进行。

头部插入删除和尾部插入删除数据

//头部插入删除
void SLPushFront(SL* ps, SLDataType x)
{
    assert(ps);
    SLCheckCapacity(ps);//保证插入时不会越界
    for (int i = ps->size; i > 0; i--) {
        ps->a[i] = ps->a[i - 1];
    }
    ps->a[0] = x;
    ps->size++;
}
void SLPopFront(SL* ps)
{
    assert(ps);
    assert(ps->size);
    for (int i = 0; i < ps->size - 1; i++) {
        ps->a[i] = ps->a[i + 1];
    }
    ps->size--;
}
//尾部插入删除
void SLPushBack(SL* ps, SLDataType x)
{
    assert(ps);
    SLCheckCapacity(ps);
    ps->a[ps->size++] = x;
}

void SLPopBack(SL* ps)
{
    assert(ps);
    assert(ps->size != 0);
    ps->size--;
}

这里要注意的是，头部插入删除的实现方式，是将整个后面的数据做了一个移动操作，时间耗费比较大，所以顺序表在实际应用当中，尽量避免使用头插头删。

指定位置之前插入数据和指定位置删除数据

void SLInsert(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    SLCheckCapacity(ps);
    for (int i = ps->size; i > pos; i--) {
        ps->a[i] = ps->a[i - 1];
    }
    ps->a[pos] = x;
    ps->size++;
}

void SLErase(SL* ps, int pos)
{
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    for (int i = pos; i < ps->size - 1; i++) {
        ps->a[i] = ps->a[i + 1];
    }
    ps->size--;
}

这里的插入和删除操作在顺序表中其实也避免不了数据的移动，这也体现了顺序表的一个缺陷，中间部分数据的插入删除的时间复杂度较高。

查找数据

最后就是查找列表中数据，返回找到的下标

int SLFind(SL* ps,SLDataType x)
{
    assert(ps);
    for (int i = 0; i < ps->size; i++) {
        if (ps->a[i] == x)return i;
    }
    return -1;
}

这里注意一下，数据的匹配查找其实也要匹配 a 动态数组中的的数据类型，这里我们定义的数据类型为int，就以int的查找方式查找。

体验体验手搓的动态顺序表

以下是体验码

#include"Sqlist.h"
int main()
{
	struct SeqList sq;
	SLInit(&sq);
	SLPushBack(&sq, 1);
	SLPushBack(&sq, 2);
	SLPushBack(&sq, 5);
	SLPushBack(&sq, 6);
	SLPushBack(&sq, 3);
	SLPushFront(&sq, 4);
	SLPrint(&sq);//4 1 2 5 6 3 

	SLPopBack(&sq);
	SLPrint(&sq);//4 1 2 5 6

	SLPopFront(&sq);
	SLPrint(&sq);//1 2 5 6

	int pos1 = SLFind(&sq, 5);
	SLErase(&sq, pos1);
	SLPrint(&sq);//1 2 6

	int pos2 = SLFind(&sq, 6);
	SLInsert(&sq, pos2, 100);
	SLPrint(&sq);//1 2 100 6
    SLDestroy(&sq);
	return 0;
}

 以上就是手搓的动态顺序表以及使用了。

链表

链表的概念及结构

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

大概是这样一个东西

注：

1. 从图上可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
2. 现实中的结点一般都是从堆上申请出来的
3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

链表的分类

其实链表不止我刚刚展示的一种，以下情况组合起来就有8种链表结构

1.单像或者双向

图中，上面的是单向，下面为双向

2.带头或者不带头

图中，上面是不带头，下面是带头

3.循环或者非循环

图中，上面是，不循环，下面是循环

它们两两排列组合 2 * 2 * 2 刚好就为8

虽然有这么多结构，但是实际上最常用的只有两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
   构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了

这次手搓个单链表怎样

这里的单链表当然指的是无头单项非循环链表喽。

SList.h存放了单链表结点结构和函数声明

//SList.h
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//打印单向链表内容
void SLTPrint(SLTNode* phead);
//创建新节点
SLTNode* CreatNewNode(SLTDataType x);
//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

下面来实现函数声明的源代码

链表打印

void SLTPrint(SLTNode* phead)
{
	assert(phead);
	SLTNode* pcur = phead;
	while (pcur != NULL) {
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

动态申请一个结点

SLTNode* CreatNewNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL) {
		perror("malloc fail:");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

这里创建新结点的重要性不亚于顺序表中的扩容，结点的内存也是开辟在堆上的。

头部的插入删除和尾部的插入删除

//头部插入删除
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = CreatNewNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* prev = *pphead;
	*pphead = (*pphead)->next;
	free(prev);
	prev = NULL;
}
//尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = CreatNewNode(x);
	if (*pphead == NULL) {
		*pphead = newnode;
		return;
	}
	SLTNode* ptail = *pphead;
	while (ptail->next) {
		ptail = ptail->next;
	}
	ptail->next = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead == NULL;
		return;
	}
	SListNode* ptail = *pphead;
	SListNode* prev = NULL;
	while (ptail->next) {
		prev = ptail;
		ptail = ptail->next;
	}
	prev->next = NULL;
	free(ptail);
	ptail = NULL;
}

这里链表头插头删的时间复杂度相比顺序表就大大降低了，可是尾插尾删还是有一定缺陷的，其操作必须走到链表末尾才能进行。

查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	assert(phead);
	SLTNode* pcur = phead;
	while (pcur) {
		if (pcur->data == x) {
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

这里查找的逻辑非常简单，就是遍历链表匹配元素，如果没找到返回一个空指针。

删除pos结点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);
	if (*pphead == pos) {
		SLTNode* del = *pphead;
		*pphead = (*pphead)->next;
		free(del);
		del = NULL;
	}
	SLTNode* pcur = *pphead;
	while (pcur&&pcur->next != pos) {
		pcur = pcur->next;
	}
	pcur->next = pos->next;
	free(pos);
	pos = NULL;
}

这里稍微注意传入的pos是一个指针，指向链表中的元素

这里你是否注意到pphead是一个二级指针，是的，当pos指向头结点时，需要改变外部phead结点的指向，改变phead指针指向就需要使用二级指针pphead了。

指定位置之后插入数据

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = CreatNewNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

为什么不提供在指定数据之前插入数据呢？是由于此单链表的无头和单向性，使其很难确定前驱节点的位置和情况，不过硬要提供其实也是可实现的。

同时这里的pos也是一个指针

删除pos之后的结点

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

删除链表释放空间

void SListDesTroy(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* next = (*pphead)->next;
	SLTNode* pcur = (*pphead);
	while (pcur) {
		next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

注：这里的链表是一个结点一个结点释放的。

体验下手搓的单链表

int main()
{
	SLTNode* phead = NULL;
	SLTPushBack(&phead, 1);
	SLTPushBack(&phead, 2);
	SLTPushBack(&phead, 3);
	SLTPushBack(&phead, 4);
	SLTPushFront(&phead, 5);
	SLTPrint(phead);//5->1->2->3->4->NULL

	SLTPopBack(&phead);
	SLTPopFront(&phead);
	SLTPrint(phead);//1->2->3->NULL

	SLTNode* ret1 = SLTFind(phead, 3);
	SLTInsert(&phead, ret1, 100);
	SLTPrint(phead);//1->2->100->3->NULL

	SLTNode* ret2 = SLTFind(phead, 2);
	SLTErase(&phead, ret2);
	SLTPrint(phead);//1->100->3->NULL

    SLTDestroy(phead);
	return 0;
}

以上就是单项不循环链表的内容了。

来来来，再手搓个双向链表可否？

这里的双向链表便是带头循环双向链表，复杂了些，但用起来确实不知道比单链表爽多少倍。

下面放到LTList.h中

//LTList.h
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

//创建双向链表结点
LTNode* LTBuyNode(LTDataType x);
//下面有两种初始化方式，这里我们选择第二种，两个其实差别不大
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//销毁链表
void LTDestroy(LTNode* phead);
//打印链表
void LTPrint(LTNode* phead);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//双向链表的尾插和尾删
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
//双向链表的头插和头删
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
//在pos位置之后插入和删除数据
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

然后就可以实现我们函数声明的源代码了，放到LTList.c中

创建双向链表结点

LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}

初始化链表

LTNode* LTInit()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	if (phead == NULL) {
		perror("malloc phead fail:");
		exit(1);
	}
	phead->data = -1;
	phead->next = phead->prev = phead;
	return phead;
}

头节点data里其实放什么值都无所谓

销毁链表

void LTDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	LTNode* pnext = pcur->next;
	while (pcur != phead) {
		free(pcur);
		pcur = pnext;
		pnext = pnext->next;
	}
	free(phead);
	pcur = pnext = phead = NULL;
}

这里和单链表销毁同理

打印链表

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead) {
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

判断链表是否为空

bool LTEmpty(LTNode* phead)
{
	assert(phead);
	if (phead->next == phead)
		return true;
	else
		return false;
}

链表头和链表末尾的插入删除

//链表头的插入和删除
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}
void LTPopFront(LTNode* phead)
{
	assert(phead);
	LTNode* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	free(del);
	del = NULL;
}
//链表末尾的插入和删除
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;
	phead->prev = newnode;
}

void LTPopBack(LTNode* phead)
{
	assert(phead);
	LTNode* del = phead->prev;
	phead->prev = del->prev;
	del->prev->next = phead;
	free(del);
	del = NULL;
}

这里链表尾的插入删除就和单链表尾的插入删除不一样了，双向链表可以直接通过head->prev直接找到链表末尾，因此时间复杂度大大降低。

在pos元素之后插入和删除结点

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	newnode->prev = pos;
	newnode->next = pos->next;
	pos->next->prev = newnode;
	pos->next = newnode;
}
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

查找

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead) {
		if (pcur->data == x) {
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

以上便是双向链表源代码实现的全部内容了

 再来试试我们写的双向链表

int main()
{
	LTNode* phead = LTInit();
	LTPushBack(phead, 1);
	LTPushBack(phead, 2);
	LTPushBack(phead, 3);
	LTPushFront(phead, 4);
	LTPushFront(phead, 100);
	LTPrint(phead);//100->4->1->2->3->

	LTPopFront(phead);
	LTPopBack(phead);
	LTPrint(phead);//4->1->2->

	LTNode* ret = LTFind(phead, 2);
	LTInsert(ret, 120);
	LTPrint(phead);//4->1->2->120->

	LTErase(ret->next);
	LTPrint(phead);//4->1->2->
	LTDestroy(phead);
	return 0;
}

很好，到这里，双向链表的内容也就差不多了。

顺序表和链表小结

顺序表和链表虽然在物理上都是线性的，在实际包装好使用时差别也不大，但是底层却天差地别

合理运用顺序表和链表各自的优势很有利于一些项目的开发，下面是对顺序表和链表的对比总结

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持：O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低：O(N)	只需修改指针指向
插入	动态顺序表，空间不够需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	让人难以位置插入和删除频繁
缓存利用率	高	低

如果你想了解缓存利用率相关的知识，可以看看下面博客

  ​​​​​ 与程序员相关的CPU缓存知识

结语

今天的内容到这里就结束了，本来想着把这篇博客分成三部分的，不知咋回事一口气给写完了，一万多字其实很多一部分是代码。后续博主还会继续产出数据结构系列的内容。如果本篇博客对你有帮助的话，还请多多支持博主，感谢大家♥