C语言数据结构：线性表！_c语言线性表

知识总览

目录

一、线性表的定义

二、线性表的基本操作

三、顺序表的定义

四、顺序表的实现——静态分配

五、顺序表的实现——动态分配

六、顺序表的操作（插入和删除）

 1、插入操作

 2、删除操作 

七、顺序表查找

八、单链表定义

九、单链表的 插入 和 删除

1、按位序插入操作（带头结点）

2、按位序插入操作（不带头结点）

​3、指定位置插入操作（前插 和 后插）

4、删除结点（带头结点）

十、单链表查找

十一、单链表建立

十二、双链表 

十三、循环链表

十四、静态链表

十五、顺序表 VS 链表 

---

一、线性表的定义

        线性表是具有相同(每个元素所占空间一样大)数据类型的 n（n>=0）个数据元素的有限序列（有次序），其中 n 为表长，当 n = 0 时，线性表是一个空表。若用 L 命名线性表。则一般表示为

L = （a1,a2, ... ,ai,ai+1, ... ,an）

        

 相关概念：

1、ai 是线性表中的 “第 i 个” 元素线性表中的 位序 （注意：位序从 1 开始，但是数组下标从 0 开始）。

2、a1 是 表头元素；an 是 表尾元素。

3、除了第一个元素外，每个元素有且仅有一个 直接前驱；

4、除去最后一个元素外，每个元素有且仅有一个 直接后继。

二、线性表的基本操作

---

InitList（&L）：初始化 表。构造一个空的线性表L，分配内存空间。

DestroyList（&L）：销毁 操作。销毁线性表，并 释放 线性表L所占用的 内存空间。

ClearList（&L）：置空 操作。如果线性表 L 已经存在，将 L 重置为空表。

---

ListInsert（&L，i，e）：插入 操作。在表 L 中的第 i 个位置上，插入指定元素 e。

ListDelete（&L，i，&e） ：删除 操作。删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值。

---

LocateElem（L，e）：按值查找 操作。在表 L 中查找具有给定关键字值的元素。

GetElem（L，i）：按位查找 操作。获取表 L 中第 i 个位置的元素值。

PriorElem（L，e，&pre_e）：前驱查找 操作。如果线性表 L 已经存在，且 e 不是 L 的第一个数据元素，则用 pre_e 返回他的前驱，否则，操作失败，pre_e无定义。

NextElem（L，e，&next_e）：后继查找 操作。如果线性表 L 已经存在，且 e 不是 L 的最后一个数据元素，则用 next_e 返回他的后继，否则，操作失败，next_e 无定义。

---

其它常用操作：

Length（L）：求 表长 。返回线性表 L 的长度，即 L 表中的数据元素的个数。

PrintList（L）：输出 操作。按前后顺序，输出线性表 L 的所有元素值。

Empty（L）：判空 操作。若 L 为空表，则返回 true，否则，返回 false。

【注意】 ：什么时候需要参数的引用 “ & ” ——对参数的修改结果需要 “ 带回来 ”

总结：

三、顺序表的定义

顺序表 —— 用 顺序存储 的方式实现的线性表顺序存储。把 逻辑上相邻 的元素存储在 物理位置上也相邻 的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

 tip：如何知道一个数据元素的大小。C语言 sizeof（ElemType）

sizeof（int ） = 4B

注意：如果是自定义的结构体类型，那么需要根据结构体当中的参数类型来确定一个数据元素的大小。比如：

typedef struct {
    int num；
    int age；
}Student
 
sizeof（Student）= 8B

四、顺序表的实现——静态分配

#define MaxSize 10                //定义最大长度
typeof struct {
    ElemType data[MaxSize];       //用静态的 “数组”存放数据元素
    int length;                   //顺序表的当前长度
}SqList;                          //顺序表的类型定义（静态分配方式）
 
Sq：sequence —— 顺序，序列

【注意】：

1、必须将顺序表的 Length 值设为 0。

2、内存当中会存在脏数据，不初始化就去违规的访问，就会看到这些脏数据，规范的方法是使用L.Length;

3、如果“数组”存满了，可以放弃治疗了，因为顺序表的表长刚开始确定后就无法更改（存储空间是静态的），如果刚开始设置的存储空间非常大，那么，只能说你是不怕浪费的富哥