目录

一、线性表

二、顺序表

1.顺序表的概念

2.静态与动态顺序表

3.动态顺序表的代码实现

三、链表

1.概念及结构概念

2.链表的种类

4.特殊链表的实现

（1）无头单向非循环链表

C语言代码实现：(1条消息) 无头单向非循环链表_聪明的骑士的博客-CSDN博客

（2）带头双向循环链表

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

一、线性表

线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构。

常见的线性表：顺序表、链表、栈、队列、字符串…

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

二、顺序表

1.顺序表的概念

简单地说，顺序表就是数组。

2.静态与动态顺序表

//顺序表的静态存储#define N 100typedef int SLDataType;typedef struct SeqList{SLDataType array[N]; //一个定长数组size_t size; //有效数据的个数}SeqList;// 顺序表的动态存储typedef struct SeqList{SLDataType* array; //指向动态开辟的数组size_t size; //有效数据个数size_t capicity;//容量空间的大小}SeqList;

静态的顺序表一次性开辟空间，不可扩容；动态顺序表可以根据数据的储存在堆区扩容。

3.动态顺序表的代码实现

#define TYPE intstruct SeqList{TYPE* SL;int volume;int size;};typedef struct SeqList SList;//初始化void InitSeqlist(SList* p);//扩容void enlarge(SList* p);//打印void print(SList* p);//销毁void destory(SList* p);//对顺序表实现增删查改的函数//增加元素void Seqlist_front_push(SList* p, TYPE a);//前增void Seqlist_back_push(SList* p, TYPE a); //后增//减少元素void Seqlist_front_pop(SList* p); //前减void Seqlist_back_pop(SList* p);//后减//查找对应下标的元素，没有找到就返回-1int Seqlist_search_element(SList* p,TYPE a);//修改对应下标的元素void Seqlist_modify_element(SList* p, size_t pos, TYPE b);// 顺序表在pos位置插入avoid SLInsert(SList* p, size_t pos, TYPE a);// 顺序表删除pos位置的值void SLErase(SList* p, size_t pos);

包括了顺序表的增删查改的操作，下面是代码实现：

(4条消息) 动态顺序表的代码实现_聪明的骑士的博客-CSDN博客

三、链表

1.概念及结构概念

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

就像寻宝游戏中的线索一样，你有了一条线索，然后沿着这条线索寻找，你会找到下一条线索，沿着找到的条线索寻找，你又会找到下一条线索，这样层层递进最后就能找到宝物，所有的线索也都被串联起来了。

你如果在上一层的数据中存放下一层的信息，那么这一层层的信息就可以不断向下寻找，我们的数据就也被串联起来了，这就是一种链表的简单概括。

链表的思想，就是结构体的自引用的应用。

2.链表的种类

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

（1）单向、双向

单向链表只存在一个next指针，只支持向后访问。

双向链表有prev和next指针，可以向后或向前访问。

（2）带头、不带头

带头指带哨兵卫的头节点，此时我们的头节点不再存储有效数据，只存储地址下一个位置作为头节点。通过哨兵卫就可以避免二级指针并简化代码。

（3）循环、非循环

循环的链表尾节点指向头节点，反之亦然，这样就做到了头部和尾部的快速访问。

这三个二选一的选择题经过组合就是一种类型。

4.特殊链表的实现

我们实际中最常用还是两种结构：无头单向非循环链表和带头双向循环链表

（1）无头单向非循环链表

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

#define TYPE inttypedef struct SListNode{TYPE data;struct SListNode* next;}SLNode;//动态申请一个节点SLNode* BuySListNode(TYPE x);// 单链表打印void SListPrint(SLNode* plist);// 单链表尾插void SListPushBack(SLNode** pplist,TYPE x);// 单链表的头插void SListPushFront(SLNode** pplist, TYPE x);// 单链表的尾删void SListPopBack(SLNode** pplist);// 单链表头删void SListPopFront(SLNode** pplist);// 单链表查找SLNode* SListFind(SLNode* plist, TYPE x);

C语言代码实现：(1条消息) 无头单向非循环链表_聪明的骑士的博客-CSDN博客

（2）带头双向循环链表

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

#define TYPE inttypedef struct DoubleList{TYPE* data;struct DoubleList* prev;struct DoubleList* next;}DList;//初始化双向链表DList* InitDList(DList* p);//初始化节点DList* Buylistnode(TYPE x);//头插void DListfrontpush(DList* p, TYPE x);//尾插void DListbackpush(DList* p, TYPE x);//头删void DListfrontpop(DList* p);//尾删void DListbackpop(DList* p);//判读链表是否为空bool ListEmpty(DList* p);//计算大小size_t ListSize(DList* p);//寻找元素DList* ListFind(DList* p, TYPE x);// 在pos之前插入void ListInsert(DList* pos, TYPE x);// 删除pos位置void ListErase(DList* pos);//考虑用一级指针，让调用ListDestory的人置空（保持接口一致性）void ListDestory(DList* p);//打印链表void print(DList* p);

C语言代码实现：带头双向循环链表_聪明的骑士的博客-CSDN博客

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

1.顺序表

优势：空间连续、支持随机访问

劣势：

（1）中间或前面部分的插入删除时间复杂度O(N)

（2）增容的代价比较大。

2.链表

劣势：以节点为单位存储，不支持随机访问

优势：

（1）任意位置插入删除时间复杂度为O(1)

（2）没有增容问题，插入一个开辟一个空间。