2.1 线性表的定义和基础操作
简单介绍
易错：线性表是 逻辑 结构，顺序表和链表是它具体实现的 存储 结构，选择题容易在此混淆。
线性表：具有 相同数据类型 （表示每个数据元素所占空间一样大，这使计算机方便的快速查找指定下标的元素）、有次序、有限序列。
注意：位序从1开始，数组下标从0开始。
除第一个元素外，每个元素有且仅有一个直接前驱（前驱）；除最后一个元素外，每个元素有且仅有一个直接后继（后继）。
几个基本操作
InitList(&L)：构造一个空的线性表
DestroyList(&L)：销毁表并释放内存空间
ListInsert(&L,i,e)：在表L的第i个位置插入元素e
ListDelete(&L,i,&e)：删除表L中第i个位置的元素，通过变量e返回删除元素值
LocateElem(L,e)：在表L中查找具有给定关键字值的元素
GetElem(L,i)：获取表L中第i个位置的元素的值
Length(L)：求表长
PrintList(L)：前后顺序输出表中所有元素值
Empty(L)：若表空则为true，否则为false
- 函数命名不必跟上面一模一样，只需具有可读性即可
&理解为对参数的修改结果需要带回来
2.2 顺序表的定义
顺序表——用顺序存储的方式实现线性表
顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。
顺序表的实现——静态分配
#define MaxSize 10 // 定义最大长度
typeof struct{
ElemType date[MaxSize]; // 用静态的“数组”存放数据元素
int length; // 顺序表的当前长度
}SqList; // 顺序表的类型定义（静态分配方式）
void InitList(SqList &L){
L.length = 0; //顺序表初始长度为0
}
int main(){
SqList L; // 声明一个顺序表
InitList(L); // 初始化顺序表
for(int i = 0;i < L.length;i++){
printf("data[%d] = %d\n", i, L.data[i]);
};
return 0;
}
注： 顺序表的表长刚开始确定后就无法更改（存储空间是静态的）
顺序表的实现——动态分配
#include <stdlib.h>
#define InitSize 10 // 默认的最大长度
typedef struct{
int *data; // 指示动态分配数组的指针
int MaxSize; // 顺序表的最大容量
int length; // 顺序表的当前长度
}
void InitList(SeqList &L){
// 用malloc函数申请一片连续的存储空间
L.data=(int *)malloc(InitSIze*sizeof(int));
L.length=0;
L.MaxSize=InitSize;
}
//增加动态数组的长度
void IncreaseSize(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; // 顺序表最大长度增加len
free(p) // 释放原来的内存空间
}
int main(){
SeqList L; //声明一个顺序表
InitList(L); //初始化顺序表
IncreaseSize(L,5); //往顺序表增加5个单位长度
return 0;
}
顺序表的特点
- 随机访问，可以在O（1）时间内找到第i个元素
- 存储密度高，每个节点只存储数据元素（链表存储方式还需存储下一个节点的指针，密度相对低）
- 拓展容量时间复杂度高
- 插入删除操作需移动大量元素
2.3 顺序表的插入删除
顺序表的基本操作——插入
#define MaxSize 10 // 定义最大长度
typedef struct{
int data[MaxSize]; // 用静态的“数组”存放数据元素
int length; // 顺序表的当前长度
}SqList; // 顺序表的类型定义
bool ListInsert(SqList &L, int i, int e){
if(i<1 || i>L.length+1) // 判断i的范围是否有效
return false;
if (L.length>=MaxSize) // 当前存储空间已满，不能插入
return false;
for(int j=L.length;j>=i;j--) // 将第i个元素及之后的元素后移
L.data[j]=L.data[j-1];
L.data[i-1]=e; // 在位置i处放入e
L.length++; // 长度加1
return true;
}
时间复杂度
最好情况：新元素插入到表尾，不需要移动元素
i = n + 1，循环0次；最好时间复杂度=O（1）
最坏情况：新元素插入到表头，将原有的n个元素全都向后移动
i = 1，循环n次；最坏时间复杂度=O（n）
平均情况：假设新元素插入到任何一个位置的概率相同，即i=1,2,3,…,length+1的概率都是p=1/n+1
i=1，循环n次；i=2时，循环n-1次；i=3，循环n-2次…i=n+1时，循环0次
平均循环次数=np+(n-1)p+(x-2)p+…+p=n/2
所以平均时间复杂度为=O（n）
顺序表的基本操作——删除
bool ListDelete(SqList &L, int i, int &e){
if(i<1 || i>L.length) // 判断i的范围是否有效
return false;
e=L.data[i-1]; // 将被删除的元素赋值给e，然后带回去
for(int j=i;j<L.length;j++) // 将第i个位置后的元素前移
L.data[j-1]=L.data[j];
L.length--; // 线性表长度减1
return true;
}
时间复杂度
最好情况：删除表尾元素，不需要移动其他元素
i=n，循环0次；最好时间复杂度=O（1）
最坏情况：删除表头元素，需要将后续的n-1个元素全都向前移动
i=1，循环n-1次；最坏时间复杂度=O（n）
平均情况：假设删除任何一个元素的概率相同，即i=1,2,3,…,length的概率都是p=1/n
i=1，循环n-1次；i=2，循环n-2次；i=3，循环n-3次…i=n时，循环0次
平均循环次数=（n-1）p+(n-2)p+…+p=(n-1)/2
所以平均时间复杂度为O(n)
2.4 顺序表的查找
顺序表按位查找
ElemType GetElem(SeqList L, int i){
return L.data[i-1];
} // 无论静态分配还是动态分配都是这种写法
时间复杂度
由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素——“随机存取”特性，因此时间复杂度为O(1)
顺序表按值查找
// 在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L, int e){
for(int i=0;i<L.length;i++)
if(L.data[i]==e)
return i+1;
return 0;
}
注意：c语言中结构体的比较不能直接用"=="，需要依次对比各个分量来判断两个结构体是否相等
时间复杂度
最好情况：目标元素在表头
循环1次，O（1）
最坏情况：目标元素在表尾
循环n次，O（n）
平均情况：假设目标元素出现在任何一个位置的概率相同，都是1/n
平均循环次数1·1/n+2·1/n+…+n·1/n=(n+1)/2
平均时间复杂度=O（n）
2.5 单链表的定义
用链式存储的方式实现线性表
优点：不要求大片连续空间，改变容量方便
缺点：不可随机存取，要耗费一定空间存放指针
typedef <数据类型> <别名>
typedef int zhengshu;
typedef int* zhengshuzhizhen
int x=1; 等价于zhengshu x=1
int *p; 等价于zhengshuzhizhen p;
struct LNode{ // 定义单链表结点类型
ElemType data; // 每个节点存放一个数据元素
struct LNode *next; // 指针指向下一个节点
}
struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode));
// 用typedef关键字来简化
typedef struct LNode{
ElemType data;
struct LNode *next
}LNode, *LinkList;
// 写法等价于
typedef struct LNode LNode;
typedef struct LNode *LinkList;
不带头结点的单链表
bool InitList(LinkList &L){
L=NULL; // 空表，暂时还没有任何节点（置空是防止脏数据）
return true;
}
void test(){
LinkList L; // 声明一个指向单链表的指针
InitList(L);
}
// 判断单链表是否为空
bool Empty(LinkList L){
return (L==NULL);
}
带头结点的单链表
bool InitList(LinkList &L){
L=(LNode *)malloc(sizeof(LNode)); // 分配一个头结点
if(L==NULL) // 内存不足，分配失败
return false;
L->next=NULL; // 头结点之后暂时还没有节点
return true;
}
void test(){
LinkList L; // 声明一个指向单链表的指针
InitList(L);
}
// 判断单链表是否为空
bool Empty(LinkList L){
return (L->next==NULL)
}
注意：“LinkList”等价于“LNode ”，前者强调链表，后者强调结点。
2.6 单链表的插入删除
按位序插入（带头结点）
// 在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
if (i<1)
return false;
LNode *p; // 指针p指向当前扫描到的结点
int j=0; // 当前p指向的是第几个结点
p=L; // 指向头结点，头结点是第0个结点（不存数据）
while (p!=NULL && j<i-1){ // 循环找到第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 true; // 插入成功
}
时间复杂度为O(n)
按位序插入（不带头结点）
bool ListInsert(LinkList &L, int i, ElemType e){
if (i<1)
return false;
if (i==1){ // 插入第1个结点的操作与其他结点操作不同
LNode *s=(LNode *)malloc(sizeof(LNode));
s->data=2;
s->next=L;
L=s; // 头指针指向新结点
return true;
}
LNode *p; // 指针p指向当前扫描到的结点
int j=1; // 当前p指向的是第几个结点
p=L; // p指向第1个结点（注意：不是头结点）
while (p!=NULL && j<i-1){ // 循环找到第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;
return true // 插入成功
}
指定结点的后插操作
bool InsertNextNode(LNode *p, ElemType e){
if (p==NULL)
return false;
LNode *s=(LNode *)malloc(sizeof(LNode));
if (s==NULL) // 内存分配失败
return false;
s->data=e; // 用结点s保存数据元素e
s->next=p->next;
p->next=s; // 将结点s连到p之后
return true;
}
指定结点的前插操作
bool InsertPriorNode(LNode *p, ElemType e){
if (p==NULL)
return false;
LNode *s=(LNode *)malloc(sizeof(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中元素覆盖为e
return true;
}
按位序删除（带头结点）
bool ListDelete(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-1个结点
p=p->next;
j++;
}
if (p==NULL) // i值不合法
return false;
if (p->next==NULL) // 第i-1个结点之后已无其他结点
return false;
LNode *q=p->next; // 令q指向被删除结点
e=q->data; // 用e返回元素的值
p->next=q->next; // 将*q结点从链中断开
free(q); // 释放结点的存储空间
return true; // 删除成功
}
指定结点的删除
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(q); // 释放后继结点的存储空间
return true;
}
注意： 如果要删除的是最后一个结点，则不存在下一个结点的数据域，因此只能从表头开始依次寻找p的前驱，时间复杂度为O(n)
2.7 单链表的查找
按位查找
// 返回第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;
}
按值查找
// 找到数据域==e的结点(带头结点)
LNode * LocateElem(LinkList L, ElemType e){
LNode *p=L->next;
while (p!=NULL && p->data!=e)
p=p->next;
return p; // 找到后返回该结点指针，否则返回NULL
}
求表长
int Length(LinkList L){
int len=0;
LNode *p=L;
while (p->next!=NULL){
p=p->next;
len++;
}
return len;
}
2.8 单链表的建立
尾插法建立单链表
LinkList List_Tailsert(LinkList &L){ // 正向建立单链表
int x;
L=(LinkList)malloc(sizeof(LNode)); // 建立头结点
LNode *s, *r=L; // r为表尾指针
scanf("%d", &x); // 输入结点的值
while(x!=9999){
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s;
scanf("%d", &x);
}
r->next=NULL; // 尾结点指针置空
return L;
}
头插法建立单链表
LinkList List_HeadInsert(LinkList &L){ // 逆向建立单链表
LNode *s;
int x;
L=(LinkList)malloc(sizeof(LNode)); // 创建头结点
L->next=NULL; // 初始为空链表
scanf("%d", &x); // 输入结点的值
while(x!=9999){
s=(LNode*)malloc(sizeof(LNode); // 创建新结点
s->data=x;
s->next=L->next;
L->next=s; // 将新结点插入表中，L为头指针
scanf("%d", &x);
}
return L;
}
应用：链表的逆置
2.9 双链表
双链表的初始化（带头结点）
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永远指向NULL
L->next=NULL; // 头结点之后暂时还没有节点
return true;
}
// 判断双链表是否为空（带头结点）
bool Empty(DLinklist L){
return (L->next==NULL)
}
双链表的插入
// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
if (p==NULL || s==NULL) // 非法参数
return false;
s->next=p->next;
if (p->next!=NULL) // 避免p是最后一个结点的情况
p->next->prior=s;
s->prior=p;
p->next=s;
return true;
}
双链表的删除
// 删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
if (p==NULL)
return false;
DNode *q=p->next; // 找到p的后继结点q
if (q->next!=NULL) // q结点不是最后一个结点
q->next->prior=p;
free(q); // 释放结点空间
return true;
}
2.10 循环链表
循环单链表
表尾结点的next指针指向头结点，从一个结点出发可以找到任何一个结点。
// 初始化一个循环单链表
bool InitList(LinkList &L){
L=(LNode *)malloc(sizeof(LNode)); // 分配一个头结点
if (L==NULL) // 内存不足，分配失败
return false;
L->next=L; // 头结点next指向头结点
return true;
}
// 判断循环单链表是否为空
bool Empty(LinkList L){
return (L->next==L)
}
// 判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode *p){
return (p->next==L)
}
循环双链表
// 初始化空的循环双链表
bool InitDLinkList(DLinklist &L){
L=(DNode *)malloc(sizeof(DNode)); // 分配一个头结点
if (L==NULL)
return false;
L->prior=L;
L->next=L;
return true;
}
// 判断循环双链表是否为空
bool Empty(DLinklist L){
return (L->next==L)
}
// 判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode *p){
return (p->next==L)
}
// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
s->next=p->next;
p->next->prior=s; // 不用特判p是最后一个结点
s->prior=p;
p->next=s;
return true;
}
// 删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
DNode *q=p->next; // 找到p的后继结点q
q->next->prior=p; // 这里也不用特判最后一个结点
free(q); // 释放结点空间
return true;
}
2.11 静态链表
什么是静态链表
分配一整片连续的内存空间，各个结点集中安置。
#define MaxSize 10 // 静态链表的最大长度
typedef struct{ // 静态链表结构类型的定义
ElemType data; // 存储数据元素
int next; // 下一个元素的数组下标
}SLinkList[MaxSize];
SLinkList表示一个长度为MaxSize的Node型数组
初始化静态链表：把a[0]的next设为-1，把其他结点的next设为一个特殊值用来表示结点空闲，如-2
插入位序为i的结点：
- 找到一个空的结点，存入数据元素
- 从头结点出发找到位序为i-1的结点
- 修改新结点的next
- 修改i-1号结点的next
删除某个结点：
- 从头结点出发找到前驱结点
- 修改前驱结点的游标
- 被删除结点next设为-2
缺点：容量固定不可变
2.12 顺序表和链表的比较
逻辑结构：都属于线性表，都是线性结构
存储结构：
顺序表：顺序存储
优点：支持随机存取，存储密度高
缺点： 大片连续空间分配不方便，改变容量不方便
链表：链式存储
优点：离散的小空间分配方便，改变容量方便
缺点：不可随机存取，存储密度低
基本操作
创：
顺序表：需预分配大片连续空间
链表：只需声明一个头指针即可
销：
顺序表：静态分配的数组系统自动回收，动态分配需要手动free
链表：依次删除各个结点
增、删：
顺序表移动元素的时间开销较大，链表只需移动指针即可
查：
顺序表按位查找的时间复杂度为O(1)，按值查找的时间复杂度为O(n)
链表按位查找与按值查找的时间复杂度都为O(n)
