第二章线性表
1.1线性表的定义和基本操作
定义：线性表时具有\textcolor{blue}{相同数据类型}的n（n≥0）个数据元素的\textcolor{blue}{有限序列}，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为：L=(a_1,a_2,...,a_i,a_{i+1},...,a_n).
涉及概念：
1.a_i是线性表的“第i个”元素线性表中的位序。（位序是从一开始，但是数组是从0开始的）
2.a_1是表头元素，a_n是表尾元素。
3.除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。
线性表的基本操作：
当需要将参数修改结构带回来时。加上“&”。
InitList(&L)：初始化表。构造一个新的空线性表L，分配内存空间。
DestroyList(&L):销毁操作。
ListInsert(&L,i,e):插入操作。在第i个位置插入元素e。
ListDetele(&L,i,&e):删除操作。在第i个位置删除元素e。
LocateElem(L,e):按值查找元素。
GetElem(L,i):按位查找元素。
其他操作：
Length(L):求表长。返回线性表长度。
PrintList(L):输出操作。
Empty(L):判空操作。如果L为空表，返回true。
注：为什么要使用这些封装函数？
1.定义的数据结构方便别人使用；2.避免重复工作，降低出错风险。
1.2线性表的顺序存储
顺序表定义：用顺序存储的方式实现线性表的顺序存储。
顺序表操作的实现：
顺序表的实现——静态分配：
//静态的大小一旦生成就不可变了
#define MaxSize = 10
typedef struct{
int data[MaxSize]; //用静态的数组存放数据元素
int length; //顺序表当前的长度
}SqList; //顺序表的类型定义初始化函数：
void InitList(SqList &L){
for(int i=0;i<MaxSize;i++)
L.data[i]=0;
L.length=0;
}插入函数：
bool ListInsert(SqList &L,int i,int e){
if(i<1||i>L.length+1) 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]=e; //给第i个赋值
L.length++; //长度+1
return true;
}这个函数的的最好情况是0，最坏情况是n，因此平均时间复杂度为。
删除函数：
bool ListDelete(SqList &L,int i,int &e){ //这里的e是用来存储删除的那个元素的值的
if(i<1||i>L.length) return false;
e=L.data[i-1]; //位序跟数组不一样
for(int j=i;j<L.length;j++) //注意这里是＜，不是≤.
L.data[j-1]=L.data[j];
L.length--;
return true;
}这个函数的的最好情况是0，最坏情况是n-1，因此平均时间复杂度为。
按位序查找元素函数：
int GetElem(SqList L,int i){
return L.data[i-1];
}按值查找元素函数
int Locate(SqList L,int e){
for(int i=0;i<L.length-1;i++)
if(L.data[i]==e)
return i+1;
return 0;
}顺序表的实现——动态分配：
#define InitSize = 10
typedef struct{
ElemType *data; //指示动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表当前的长度
}SqList; //顺序表的类型定这里面就涉及了怎么申请空间，并让data指过去，在C/C++中动态申请和释放内存空间的函数
C —— malloc、free函数
L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize) //后面的*是乘号的意思
C++ —— new、delete关键字
初始化函数：
void InitList(SqList &L){
L.data=(int *)malloc(InitSize*sizeof(int));
L.length=0;
L.MaxSize=InitSize;
}
//增加动态数组长度的函数
void IncreaseSize(SqList &L,int len){
int* p=L.data;
L.data=(int *)malloc((L.Maxsize+len))*sizeof(int)); //data指向新产生的空间
for(int i=0;i<L.length;i++){
L.data[i]=p[i]; //将数据复制到新区域
}
L.MaxSize=L.MaxSize+len;
free(p);
}顺序表的特点：
1.随机访问，可以在O(1)时间内找到第i个元素。
2.存储密度高，每个节点只存储数据元素。
3.拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
4.插入、删除操作不方便，需要移动大量的数据
本章节有个关于结构类型的知识点：
即在C语言中两个结构类型的变量是不是直接用“==”来比较是否相等的，需要另外定义一个函数逐项比较结构体中每一个元素。在C++中可以定义一个重载来实现。
1.3线性表的链式存储
优点：不要求大片连续空间，改变容量方便；缺点：不能随机存取。
单链表的定义：
typedef struct LNode{
ElemType data; //每个节点存放一个数据元素
struct LNode *next; //指针域，指向下一个节点
}LNode,*LinkList;
//要表示一个链表时，只需要声明一个头指针L，指向单链表的第一个结点。
LNode * L;或LinkList L; //都是声明一个指向单链表第一个结点的指针
//需要说明的是:LNode * L强调的是这是一个结点，LinkList L强调的是这是一个单链表。
不带头结点的单链表：
初始化函数：
bool InitList(LinkList &L){
L = NULL; //空表，暂时还没有任何结点
return true;
}判断链表是否为空：
bool Empty(LinkList L){
return (L==NULL);
}按位序插入函数： //根据这个可以知道，不带头结点的单链表，当i=1的时候需要重新设定一个头结点.
bool ListInsert(LinkList &L,int i,ElemType e){
if(i<1) return false;
if(i==1){
LNode *s = (LNode*)malloc(sizeof(LNode));
s->data=e;
s->next=L;
L=s; //头指针指向新结点
return true;
}
LNode *p;
int j=1;
p = L;
while(p!=NULL && j<i+1){
p=p->next;
j++;
}
if(p=NULL) return false;
LNode *s = (LNode*)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s; //头指针指向新结点
return true;
}带头结点的单链表： //更方便
尾插法建立单链表： //建立表尾结点
LinkList List_TailInsert(LinkList &L){
int x;
L = (LinkList)malloc(sizeof(LNode)); //建立头结点
LNode *s,*r = L; //r为表尾指针
scanf("%d",&x); //输入插入结点的值
while(x != '#'){
s=(LNode*)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s; //r指向新的表尾结点
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!='#'){
s = (LinkList)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d",&x);
}
return L;
}初始化函数：
bool InitList(LinkList &L){
L = (LNode *)malloc(sizeof(LNode));
if(L == NULL)
return false;
L->next = NULL;
return true;
}判断链表是否为空：
bool Empty(LinkList L){
return (L->next==NULL);
}按位序查找函数：
LNode* GetElem(LinkList L,int i){
if(i<0) return NULL;
LNode *p;
int j=0;
p = L;
while(p!=NULL && j<i){
p = p->next;
j++;
}
return p;
}按值查找函数：
LNode* LocateElem(LinkList L,ElemType e){
LNode *p = L->next;
while(p!=NULL && p->data != e)
p = p->next;
return p;
}按位序插入函数：
bool ListInsert(LinkList &L,int i,ElemType e){ //在第i个位置插入元素e
if(i<1) return false;
LNode *p; //指针p指向当前扫描到的结点
int j = 0;
p = L;
while(p!=NULL && j < i-1){ //循环找到第i-1个结点
p = p->next;
j++;
}
if(p==NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode)); //s结点为新加的代码
s->data = e;
s->next=p->next;
p->next=s;
return true;
}后插操作： //在p结点后插入元素e
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->next = p->next;
p->next = s;
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->data = p->data;
p->data = e;
return true;
}删除操作：
//删除指定位置的结点
bool ListDelete(LinkList &L,int i,ElemType &e){
if(i<1) return false;
LNode *p;
int j = 0;
p = L;
while(p!=NULL && j < i-1){ //循环找到第i-1个结点
p = p->next;
j++;
}
if(p==NULL)
return false;
if(p->next==NULL) return false;
LNode *q=p->next;
e = q->data;
p->next=q->next;
free(q);
return true;
}
//删除指定结点
bool DeleteNode(LNode *p){
if(p == NULL) return false;
LNode *q=p->next;
p->data = p->next->data;//这段代码是有问题的，没有考虑到p是最后一个结点的情况，但这是单链表的局限性。
p->next = q->next;
free(q);
return true;
}删除指定结点的代码受限于单链表的局限是有问题，需要注意。
双链表：
//增加了前驱结点
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;
L->next = NULL;
return true;
}双链表的插入（后插）： //如何前插，只需要从该结点找到前驱结点，对前驱结点执行后插操作
bool InsertNextDNode(DNode *p,DNode *s){
if(p == NULL||s == NULL) return false;
s->next = p->next;
if(p->next != NULL) p->next->prior = s;
s->prior = p;
p->next = s;
return true;
}双链表的删除：
void DeleteNextDNode(DNode *p){
if(p == NULL) return false;
DNode *q = p->next;
if(q == NULL) return false;
p->next = q->next;
if(q->next!=NULL) q->next->prior = p;
free(q);
return true;
}LNode,*LinkList;循环单链表：
typedef struct LNode{
ElemType data;
struct LNode *next;
}初始化循环单链表：
bool InitLinkList(LinkList &L){
L = (LNode *)malloc(sizeof(LNode));
if(L == NULL) return false;
L->next = L; //在最后要指向头指针
return true;
}循环单链表是否为空：
bool EmptyLinkList(LinkList L){
return(L->next == L);
}循环双链表：
初始化循环双链表：
bool InitLinkList(LinkList &L){
L = (LNode *)malloc(sizeof(LNode));
if(L == NULL) return false;
L->next = L; //后继在最后要指向头指针
L->prior = L; //前驱在最后要指向头指针
return true;
}静态链表：
定义：分配一整片连续的内存空间，各个结点集中安置。
#define MaxSize 10
typedef struct{
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLikList[MaxSize];在物理上相邻但是地址空间里面的数值不一定相邻，其容量是固定不可变的。
总结：
顺序表和链表比较：
1.逻辑结构：都是一对一的线性结构；
2.存储结构：顺序表是连续空间，存储密度高；链表空间分散，但是存储密度略低。
3.应用场景：顺序表适用于表长可估计、查询操作较多的场景；链表适用于表长难以估计、插入/删除频繁的场景。
4.基本操作：顺序表插入/删除需要移动元素，时间复杂度高，但是查找方便；链表反之。
# 声明
以上内容时根据现有最新的课程学习总结而成，包含必要的代码，适合基础复习使用。