前言

线性表是实际中广泛应用的重要数据结构，本文用通俗易懂的方法讲解它。

一、什么是线性表？

首先，我们了解下“线性表”的基本概念：

全名为“线性存储结构”，使用线性表存储数据的方式可以这样理解，即“把所有数据用一根线儿串起来，再存储到物理空间中”。
是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、队列…

二、顺序表：

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
在这里插入图片描述
顺序表一般可以分为：

静态顺序表：使用定长数组存储数据。
动态顺序表：使用动态开辟的数组存储。

扩容方法：动态开辟一块新的空间（一般为原空间的两倍），将原空间的数据拷贝到新的空间，然后让array指针指向新的空间并且释放旧空间。

对比以上两者：

区别：

静态顺序表和动态顺序表唯一不同的是，静态顺序表在创建顺序表的时候容量已经确定，不可以更改，而动态顺序表的容量是由malloc函数动态开辟，当容量不够用时可以增加容量capacity。

优缺点：

静态顺序表创建空间时为静态开辟，不用malloc函数，代码相对简单（一点点），不存在内存泄露问题。
动态顺序表，动态开辟空间，使用相对灵活，相比于静态开辟空间也可以少空间浪费。

动态顺序表代码演示：初始化、插入数据和检查容量

//初始化顺序表
void SeqList_Init(SeqList* ps)
{SLDataType* tmp = (SLDataType*)malloc(5 * sizeof(SLDataType));if (tmp == NULL){perror(malloc);exit(-1);}ps->arr = tmp;ps->size = 0;ps->capacity = 5;
}
//检查容量
void Check_Capacity(SeqList* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->arr, 2*ps->capacity* sizeof(SLDataType));if (tmp == NULL){perror(realloc);exit(-1);}ps->arr = tmp;ps->capacity = 2 * ps->capacity;printf("扩容成功\n");}
}
//插入数据
void SeqList_Insert(SeqList* ps, SLDataType pos)
{assert(ps);Check_Capacity(ps);//检查容量SLDataType num = 0;printf("请输入需要写入的值:>");scanf("%d", &num);if (ps->size == 0 || pos == ps->size){ps->arr[pos] = num;}	SLDataType end = ps->size - 1;while (end >= pos){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[pos] = num;ps->size++;
}
//头部插入数据
void SeqList_PushFront(SeqList* ps)
{SeqList_Insert(ps, 0);
}
//尾部插入数据
void SeqList_PushBack(SeqList* ps)
{SeqList_Insert(ps, ps->size);
}

三、链表：

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

下图为单链表的逻辑结构类型：
在这里插入图片描述
注意：

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

链表的分类

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

单向或者双向：

在这里插入图片描述

带头和不带头：
循环和不循环：

经过以上三种可以有2^3=8种类型。

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

无头单向链表和带头双向循环链表：

这边通过单链表头部和尾部插入数据代码帮大家理解过程：

//创建结点
SListNode* BuySListNode(SLTDataType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;
}
//头插数据
void SListPushFront(SListNode** pphead, SLTDataType x)
{SListNode* newnode = BuySListNode(x);//读取新建的结点newnode->next = *pphead;*pphead = newnode;
}
//尾插数据
void SListPushBack(SListNode** pphead, SLTDataType x)
{SListNode* newnode = BuySListNode(x);//读取新建的结点if (*pphead == NULL){*pphead = newnode;return;}SListNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;
}

四、顺序表和链表对比：

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