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；}Studentsizeof（Student）= 8B

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

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

【注意】：

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

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

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

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

#define InitSize 10； //顺序表的初始长度typeof struct { ElemType *data； //指示动态分配数组的指针int MaxSize； //顺序表的最大容量int length； //顺序表的当前长度} SeqList； //顺序表的类型定义（动态分配方式）

Key：动态申请 和 释放内存 空间。

动态申请：malloc 函数 L.data = （ElemType *）malloc（sizeof（ElemType ）* Initsize）

申请一整块连续的存储空间，返回开始处的指针。注意返回的指针类型要以需要的类型进行转换

释放内存：free 函数。

增加动态数组的长度

void IncreaseSzie（SeqList &L，int len）{int *p = L.data;L.data = （int *）malloc（（L.MaxSize + len）*sizeof（int））;for（int i = 0;i<L.length;i++）{ //复制数据到新的内存空间L.data[i] = p[i];}L.MaxSize = L.MaxSize + len; //顺序表最大长度增加 lenfree（p）;//释放原来的内存空间}

顺序表的特点：

（1）随机访问，即可以在O（1）时间内找到第 i 个元素。

（2）存储密度高，每个节点只存储数据元素。

（3）拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）

总结

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

知识总览

1、插入操作

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

#define MaxSize 10 //定义最大长度typedef struct {ElemType data[MaxSize]; //用静态的“数组”存放数据int length; //顺序表当前的长度} SqList //顺序表的类型定义

【注意】此处的代码基于顺序表的“静态分配” 实现。“动态分配”也基本上一样。

插入操作代码

//插入方法void ListInsert (SqList &L,int i,int e){for(int j = L.length;j >= i;j--) //将第 i 个元素及之后的元素后移L.data[j] = L.data[j-1];L.data[i-1] = e; //在位置 i 处放入 eL.length++; //长度加1}

插入操作的时间复杂度：

（1）最好情况：新元素插入到表尾，不需要移动元素，i = n+1，循环0次；最好的时间复杂度 = O(1)。

（2）最坏情况：新元素插入到表头，所有元素都要移动 i = 1，循环 n 次；最坏时间复杂度 = O(n)

（3）平均情况：假设插入的 任何一个位置的概率相同，即 i = 1，2，3... ，length+1 的概率都是 P= 1 /（n+1）；平均循环次数 = np + (n-1)p + (n-2)p +......+ 1*p = n(n+1)/2 * 1/(n+1) = n/2;平均时间复杂度 = O（n）。

2、删除操作

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

void ListDelete(SqList &L,int i,int &e){ //引用型 e，带回删除元素的值for(int j = i;j<L.length;j++) //将第 i 个位置后的元素前移L.data[j-1] = L.data[j];L.length--; //线性表长度减1}

【注意】位序、数组下标的关系，并从前面的元素以此移动。

删除操作的时间复杂度：

（1）最好情况：删除最后元素，不需要移动 i = n，循环0次；最好时间复杂度 = O(1)

（2）最坏情况：删除表头元素，后续的 n-1 个元素都要移动 i = 1，循环 n -1次；最坏时间复杂度 = O(n)

（3）平均情况：假设删除的任何一个位置的概率相同，即 i = 1，2，3... ，length+1 的概率都是 P= 1 / n；平均循环次数 = (n-1)p + (n-2)p +......+ 1*p = n(n-1)/2 * 1/(n+1) = (n-1) / 2;平均时间复杂度 = O（n）。

顺序表的 插入 删除 操作小结

七、顺序表查找

知识总览

1、按位查找

GetElem(L,i)：按位查找。按位查找 L 表当中 第 i 个位置的元素的值。

（1）基于静态分配实现

//基于静态分配#define MaxSize 10 //定义最大长度typedef strcut {ElemType data[MaxSize]; //用静态的“数组”存放数据元素int length; //顺序表当前的长度}SqList; //顺序表的类型定义（静态分配方式）ElemType GetElem(SqList L,int i){return L.data[i - 1];}

（2）基于动态分配实现

//基于动态分配#define InitSize 10 //顺序表的初始长度typedef strcut {ElemType *data; //用动态的“数组”存放数据元素int length; //顺序表当前的长度int MaxSize；//顺序表的最大容量}SeqList; //顺序表的类型定义（动态分配方式）ElemType GetElem(SeqList L, int i){ //和访问普通数组的方式语言return L.data[i - 1];}

动态分配的内存操作流程

按位查找的时间复杂度：O（1）。由于顺序表的各个元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第 i 个元素——“随机存取”特性。

2、按值查找

LocateElem(L,e)：按值查找 操作。在表 L 当中查找具有给定关键字的元素。

//基于动态分配#define InitSize 10 //顺序表的初始长度typedef strcut {ElemType *data; //用动态的“数组”存放数据元素int length; //顺序表当前的长度int MaxSize；//顺序表的最大容量}SeqList; //顺序表的类型定义（动态分配方式）//在顺序表 L 中查找第一个元素值等于 e 的元素，并返回其位序int LocateElem(SeqList L, ElemType e){ for(int i = 0;i<L.length;i++)if(L.data[i] == e)return i+1; //数组小标为 i 的元素值等于 e ，返回其位序 i+1retrun 0; //退出循环，说明查找失败}

基本数据类型：int、char、double、float 等都可以直接使用运算符 “ == ” 来比较。但是结构体类型就不能直接用 “ == ”，需要依次对比各个分量来判断是否相等。

Tips：《数据结构》考研初试当中，手写代码可以直接使用 “ == ”，无论 ElemType是基本数据类型还是结构体类型，《C语言程序设计》那么...也许语法要求就比较严格，参考历年真题。

按值查找的时间复杂度：

（1）最好情况：目标元素在表头，循环1次，最好时间复杂度 = O（1）

（2）最坏情况：目标元素在表尾，循环n次，最坏时间复杂度 = O（n）

（3）平均情况：假设目标元素出现在任何一个位置的概率相同，都是 1/n ，平均循环次数 = 1*1/n + 2*1/n +3*1/n +...+n*1/n =n(n+1)/2*1/n = (n+1)/2;平均时间复杂度 = O（n）

总结

八、单链表定义

知识总览

定义

什么是单链表

使用代码定义个单链表，并新增：

//结点定义struct LNode{ //结点ElemType data; //数据域，每个节点存放一个数据元素struct LNode *next; //指针域。指向下一个节点}LNode,*LinkList;//新增节点,在内存当中申请一个结点所需空间，并用指针 p 指向这个结点struct LNode *p = (struct LNode *) malloc(sizeof(struct LNode))

取别名：

//typedef关键字——取别名typedef <数据类型> <别名>例子：typedef int zhengshu; 把int类型取别名叫zhengshu

初始化单链表

(1)不带头结点bool InitList(LinkList &L){L = NULL; //空表，暂时还没有任何结点，防止脏数据retuen true;}(2)带头结点bool InitList(LinkList &L){L = (LNode *) malloc(sizeof(LNode)); //分配一个头结点if(L == NULL) //内存不足，分配失败return false；L->next = NULL; //头结点之后暂时还没有结点retuen true;}

总结

九、单链表的 插入 和 删除

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

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

//定义结点typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;//在第i个位置插入元素e（带头结点）bool LisyInsert(LinkList &L,int i,Elemtype e){if(i<1)return false;LNode *p; //指针p指向当前扫描到的结点int j = 0; //当前指针p指向的是第几个结点p = L; //L指向头结点，头结点是第0个结点（不存放数据）while(p! = NULL && j < i-1){p = p->next;j++;}if(p == NULL) //i值不合法return false;LNode *s = (LNode *)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s; //将结点s连到p之后return ture; //插入成功}

最好时间复杂度 = O（1）；

最坏时间复杂度 = O（n）；

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

【注意】因为不存在 “ 第 0 个 ”结点，因此 i=1 时需要特殊处理

//定义结点typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;//在第i个位置插入元素e（不带头结点）bool LisyInsert(LinkList &L,int i,Elemtype e){if(i == 1){LNode *s = (LNode *)malloc(sizeof(LNode));s->data = e;s->next = L;L = s; //头指针指向新结点return true;}LNode *p; //指针p指向当前扫描到的结点int j = 1; //当前指针p指向的是第几个结点p = L; //p指向第一个结点（不是头结点）while(p! = NULL && j < i-1){p = p->next;j++;}if(p == NULL) //i值不合法return false;LNode *s = (LNode *)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s; //将结点s连到p之后return ture; //插入成功}

结论：不带头结点写代码不方便，推荐使用带头结点

注意：考试中带头、不带头都有可能，注意审题。

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

1、指定结点的后插操作：

//定义结点typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;//后插操作：在 p 结点之后插入元素 ebool InsertNextNode(LNode *p,ElemType e){if(p == NULL)return false;LNode *s = (LNode *)malloc(siezof(LNode));if(s ==NULL) //内存分配失败return false;s->data = e; //用结点s保存数据元素 es->next = p->next;p->next = s; //将结点 s 连接到 p 之后return true;}

2、指定结点的前插操作：

//定义结点typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;//前插操作：在 p 结点之前插入元素 ebool InsertNextNode(LNode *p,ElemType e){if(p == NULL)return false;LNode *s = (LNode *)malloc(siezof(LNode));if(s ==NULL) //内存分配失败return false;s->next = p->next;p->next = s; //将结点 s 连接到 p 之后s->data = p->data; //将p的元素复制到s中p->data = e; //p中元素覆盖为ereturn true;}

时间复杂度 = O（1）

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

1、按位序删除

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

//定义结点typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;//在第i个位置删除元素e（带头结点）bool LisyInsert(LinkList &L,int i,Elemtype e){if(i < 1){return false;}LNode *p; //指针p指向当前扫描到的结点int j = 0; //当前指针p指向的是第几个结点p = L; //p指向第一个结点（不是头结点）while(p! = NULL && j < i-1){p = p->next;j++;}if(p == NULL) //i值不合法return false;if(p->next == NULL) //i-1个结点之后已无其他结点return false;LNode *p = p->next; //令q指向被删除的元素结点e = q->data; //用 e 返回元素的值p->next = q->next; //将*q结点从链中断开free(q); //释放结点的存储空间return ture; //插入成功}

2、指定结点删除

bool DeleteNode(LNode *p){if(p == NULL)return false;LNode *q = p->next; //令q 指向 *p的后继结点p->data = p->next->data //和后继结点交换数据域p->next = q->next; //将 *q结点从链中断开free(p); //释放后继结点的存储空间return true;}

总结

十、单链表查找

知识总览

1、按位查找

//按位查找。返回第i个元素（带头结点）LNode * GetElem(LinkList L,int i){if(i < 0)return NULL;LNode *p; //指针p指向当前扫描到的结点int j = 0; //当前p指向的是第几个结点p = L; //L指向头结点，头结点是第0个结点（不存放数据）while(P != NULL && j < i){ //循环找到 i 个结点p = p->next;j++;}return p;}

平均时间复杂度：O（n）

2、按值查找

//按值查找，找到的数据域==e 的结点LNode * LocateElem(LinkList L,ElemType e){LNode *p = L->next;//从第一个结点开始查找数据域为e的结点while(p != NULL && p->data != e)p = p->next;return p; //找到返回该结点指针，否则返回NULL}

平均时间复杂度：O（n）

3、求表的长度

int Length(LinkList L){int len = 0; //统计表长LNode *p = L;while(p->next != NULL){p = p->next;len++;}return len;}

时间复杂度：O（n）

重要考点和知识回顾

十一、单链表建立

知识总览

1、尾插法建立单链表

bool ListInset(LinkList &L,int i,ElemType e){if(i < 1)return false;LNode *p; //指针p指向当前扫描到的结点int j = 0; //当前p指向的是第几个结点p = L; //L指向头结点，头结点是第0个结点（不存数据）while(p != NULL && j < i - 1){ //循环找到第 i 个结点p = p->next;j++;}if(P == NULL) //i值不合法return false;LNode *s = (LNode *)malloc(sizeof(LNode));s -> data = e;s ->next = p->next;p->next = s; //将结点s连接到p之后return true; //插入成功}

解决办法：设置一个表尾指针

LinkList List_TailInsert(LinkList &L){ //正向建立单链表int x; //设ElemType为整型L = (LinkList)malloc(sizeof(LNode)); //建立头结点LNode *s,*r = L; //r为表尾指针scanf("%d",&x); //输入结点的值while(x!=9999){ //输入 9999 表示结束s = (LNode *)malloc(sizeof(LNode)); s->data = x;r->next = s; //在r结点之后插入元素xr = s; //r指向新的表尾结点scanf("%d",&x);}r->next = NULL; //尾结点指针置空return L;}

时间复杂度：O（n）

2、头插法建立单链表（重要应用！！！链表的逆置）

LinkList List_HeadInsert(LinkList &L){ //逆向建立单链表LNode *s;int x;L = (LinkList)malloc(sizeof(LNode)); //创建头结点L->next=NULL; //初始为空链表scanf("%d",&x);//输入结点的值while(x != 9999){ //输入9999表示结束 s = (LNode *)malloc(sizeof(LNode));//创建新结点s->data = x;s->next = L->next;L->next = s; //将新结点插入表中，L为头指针scanf("%d",&x);}retrun L;}

知识回顾与重要考点

头插法、尾插法：核心就是初始化操作、指定结点的后插操作

十二、双链表

知识总览

1、双链表的初始化（带头结点）

typedef struct DNode{ElemType data;struct DNode *prior,*next;}DNode,*DLinklist;bool InitDLinkList(DLinklist &L){L = (DNode *)malloc(sizeof(DNode)); //分配一个头结点if(L == NULL)return false;L->prior = NULL; //头结点的prior永远指向NULLL->next = NULL; //头结点之后暂时没有结点return true;}void testDLinkList(){//初始化双链表DLinklist L; //指向头结点的指针InitDLinkList(L);}

2、双链表的插入

bool InsertNextDNode(DNode *p,DNode *s){if(p == NULL || s == NULL)return false;s->next = p ->next; //双结点*s插入到结点*p之后if(p->next != NULL)p->next->prior = s;s->prior = p;p->next = s;return true;}

3、双链表的删除

bool DeleteNextDNode(DNode *p){if(p == NULL)DNode *q = p->next; //找到p的后继结点if(q == NULL) //p没有后继结点p->next =q->next;if(q->next != NULL) //q结点不是最后一个结点q->next->prior = p;free(p); //释放结点空间return true;

4、双链表的遍历

//后向遍历while(p != NULL){p = p->next;}//前向遍历while(p != NULL){p = p->prior;}//前向遍历(跳过头结点)while(p->prior != NULL){p = p->prior;}

双链表不可随机存取，按位查找、按值查找都只能使用遍历的方式实现。时间复杂度=O（n）

知识回顾与重要考点

十三、循环链表

知识总览

1、循环单链表

typedef struct DNode{ElemType data;struct DNode *next;}DNode,*DLinklist;bool InitList(DLinklist &L){L = (DNode *)malloc(sizeof(DNode)); //分配一个头结点if(L == NULL)return false;L->next = L; //头结点next指向头结点return true;}

2、循环双链表

typedef struct DNode{ElemType data;struct DNode *prior,*next;}DNode,*DLinklist;bool InitList(DLinklist &L){L = (DNode *)malloc(sizeof(DNode)); //分配一个头结点if(L == NULL)return false;L->prior = L; //头结点的prior指向头节点L->next = L; //头结点next指向头结点return true;}

知识回顾和重要考点

十四、静态链表

知识总览

1、什么是静态链表

分配一整片连续的内存空间，各个结点集中安置。

静态链表的创建

#define MaxSize 10 //静态链表的最大长度struct Node{ //静态链表结构类型定义ElemType data;//存储数据元素int next; //下一个元素的数组下标};void testSLinkList(){struct Node a[MaxSzie];//后续代码...}

查找：

从头结点出发挨个往后遍历，时间复杂度O（n）。

插入位序为 i 的结点：

1.找到一个空结点，存入数据元素；

2.从头结点出发找到位序为 i - 1 的结点；

3.修改新结点的next；

4.修改 i - 1 号结点的next；

删除某个结点：

1.从头结点出发找到前驱结点

2.修改前驱结点的游标

3.被删除节点的next 设置为 -2（此处的值找特殊值就行了，不是特别要求）

十五、顺序表 VS 链表

知识总览

1、逻辑结构

2、存储结构

3、基本操作（创建、销毁、增删改查）

（1）创建

（2）销毁

（3）增加、删除

（4）查找

总结

表长难以预估、经常要增加、删除元素 —— 链表

表长可以预估、查询（搜索）操作较多 —— 顺序表

线性表到此结束