C语言数据结构线性表教程示例详解

线性表

数据结构里我们时常看到什么什么表，线性表是最基本、最简单、也是最常用的一种数据结构，其他各种表的万恶之源就是这个线性表，他是个啥其实顾名思义：

一个线性表是n个具有相同特性的数据元素的有限序列。数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

说的这么复杂其实就是下面这个模型，线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。

而我们说的线性是指他的连续性，并非是内存上连续，而是逻辑上连续，什么又是逻辑上连续？我们说数据结构有两种结构，一是物理结构即在内存中怎么存，二是逻辑结构是我们假想的。物理结构其实非数组即链表，基本都逃不开这俩，但数组有个致命的缺陷就是不知道咱要存多少，我开辟10个空间，若想存第11个就是放屁，那直接给他1000个空间呢？那剩下989个空间直接浪费掉，一句话就是他不能按需所取。

这时链表就应运而生，我们有几个数据就开辟几个空间，众所周知数组我们得到首元素地址，直接遍历就能得到全部成员，那它怎么去串联这些独立零散的空间来建立联系？我们按需所取首先就会选择去堆区申请空间，去堆区不是一定是最好，因为 malloc 函数嘛， 满足要就拿不要就释放。我们对数据寻踪觅迹是通过其对应的地址对吧，不难想到应用指针吧，这样那我们就可以“有备而来”，在开辟数据空间时多开辟4到8个字节来存放指针，最后一个数据我们不需要指针了，直接放一个空指针就行。

顺序表

线性表主要由顺序表示或链式表示。在实际应用中，常以栈、队列、字符串等特殊形式使用。

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。

我们说过线性表中结构不是物理就是逻辑，我们的顺序表其实就是使用数组来存储数据，本质上来说顺序表就是一个数组。

抛开实际的代码谈概念就是耍流氓,我们采用工程化方式来写一组代码，在.h文件中进行定义：

typedef int type;//便于随时修改类型
#define n 10 //方便定义数组大小
struct SeqList
{
	type a[n];
	int size;
};
void PushBack(struct SeqList* p, type x);
void PopBack(struct SeqList* p, type x);
……
//后面这些为尾插，尾删等接口来处理他们之间的关系

以上的代码就是很多教材上的静态顺序表设计结构，咱跳出来看看就会秒感很low，他是固定大小不能按需所取，其实就是封装了一个数组，我们要变成动态顺序表很简单，增设一个capacity成员即可：

typedef int type;
#define n 10 
struct SeqList
{
	type a[n];
	int size;   //有效数据的个数
	int capacity;   //容量，即空间的大小
};
void PushBack(struct SeqList* p, type x);
void PopBack(struct SeqList* p, type x);
……

扩容操作我们手动操作，只需引入 realloc 函数即可，如果是将分配的内存扩大，则有以下情况：

如果当前内存段后面有需要的内存空间，则直接扩展这段内存空间，realloc函数将返回原指针。如果当前内存段后面的空闲字节不够，那么就使用堆中的第一个能够满足这一要求的内存块，将目前的数据复制到新的位置，并将原来的数据块释放掉，返回新的内存块位置。如果申请失败，将返回NULL，此时，原来的指针仍然有效。