线性表
3.1 线性表的定义：
线性表（LIst） ：零个或多个数据元素的==有限序列==
1.除了最开头的和最末尾的数据元素，其他的数据元素都有一个前驱和后继
2.线性表中的数据元素是相同的类型的数据
补充插入说明:
1.1一元多项式计算
Rn(x)=Pn(x)+Qm(x)
线性表R=(p0+q0,p1+q1,p2+q2,p3+q3.....pn)
1.2稀疏多项式的运算
多项式非零项的数组表示
（a） A(x) =7+3x+9x^8+ 5x^17 (b) B(x)=8x+22x^7 -9x^8
| 下标i | 0 | 1 | 2 | 3 | 0 | 1 | 2 |
|---|---|---|---|---|---|---|---|
| 系数[i] | 7 | 3 | 9 | 5 | 8 | 22 | -9 |
| 指数 | 0 | 1 | 8 | 17 | 1 | 7 | 8 |
Pn(x)=p1x^e1 + p2x^e2 + ... +pmx^em
线性表A=((7,0),(3,1),(9,8),(5,17)) 线性表B=((8,1),(22,7),(-9,8))
新数组c：
0 1 7 17
7 11 22 5
1.创建一个==新数组c==
2.分别从头遍历比较a和b的每一项
==指数相同== 对应系数相加，若其和不为零，则在c中增加一个新项，若为零，则不添加新项
==指数不相同== 则将指数较小的项复制到c中
3.2 线性表的抽象数据类型
1.抽象数据类型定义：
补：
DestroyList(&L) : 销毁线性表L
ListTraverse(&L,visited()): 遍历，依次对线性表中每个元素调用visited()
同时注意：
当你传递一个参数给函数的时候，这个参数会不会在函数内被改动决定了使用什么参数形式
如果需要被改动，则需要传递指向这个参数的指针
如果不用被改动，可以直接传递这个参数
3.3 线性表的顺序存储结构
3.3.1 顺序储存定义
线性表的顺序储存结构，指的是用一段地址连续的存储单元依次线性表的数据元素
例：
[a1] [a2] [...] [a3] [a4] [...] [an]
3.3.2 顺序储存方式
1.在内存中找了一块地，通过占位的形式，把一定的内存给占了，然后把相同数据类型的数据元素依次存储在这块空地中
代码的实现：
#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
ElemType date[MAXSIZE];
int length;
}SqList;
3.3.3 数据长度与线性表长度的区别
线性表会进行插入和删除等操作，所以线性表的长度会发生变化
因此，线性表的长度小于等于数组的长度
3.3.4 地址计算方法
LOC(ai)=LOC(a1)+(i-1)*c
c所表示的是一个数据元素所占的字节；
时间复杂度表示为O(1),通常将具有这种特性的存储结构称为随机存储结构
3.4 顺序存储结构的插入和删除
3.4.1 获取元素操作
返回线性表中第i个位置元素值返回
代码操作：
#define OK 1
#define ERROR 0
typedef int Status;
/* 初始条件：顺序线性表L已存在，1<=i<=ListLength(L)*/
/* 操作结果：用e返回L中第i个数据元素的值，注意i是指位置，第1个位置的数组是从0开始*/
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0 || i<1 || i>L.length)
return ERROR;
*e=L.data[i-1];
return ok;
}
注意插入和删除的位置之分
3.4.2 插入操作
插入思路：
- 如果插入位置不合理，抛出异常、
- 如果线性表长度大于等于数长度，则抛出异常或动态增加容量
- 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置
- 将要插入元素填入位置i处
- 表长加1
代码实现如下：
/* 初始条件：顺序线性表L已存在，1小于等于i小于等于ListLength(L)*/
/* 操作结果：在L中第i个位置之前插入新的数据元素额，L的长度加1*/
Status ListInset(SqList *L,int i,ElemType e)
{
int k;
if(L->length==MAXSIZE)
return ERROR;]
if(i<1 ||i>L->length+1)
return ERROR; /*此处的作用是判断i的位置是否满足条件*/
if(i<=L->length)
{
for(k=L->length-1;k>=-1;k--)
L->data[k+1]=L->data[k]; /*将线性表i的数据元素都后移*/
}
L->data[i-1]=e;
L->length++;
return OK;
}
3.4.3 删除操作
删除算法的思路：
- 如果删除位置不合理，抛出异常
- 取出删除元素
- 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置
- 表长减1
代码实现如下:
/* 初始条件：顺序线性表L已存在，1<=i<=ListLength(L)*/
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1*/
Status ListDelete(SqList *L,int i,ElemType e)
{
int k;
if(L->length==0)
return ERROR;
if(i<1 || i>L->length)
return ERROR;
*e=L->data[i-1]; /*判断i的位置是否满足条件*/
if(1<=i<L->length）
{
for(k=i;k<=L->length;k++)
L->data[k-1]=L->length[k]; /*将删除的元素向前移动*、
}
L-length--;
return OK;
}
线性表的插入和删除的时间复杂度分析；
如果插入/删除的是最后一个元素，则时间复杂度为O(1），最复杂的情况为O(n）
3.4.4 线性表顺序存储结构的优缺点
补充，类c语言有关操作
1 多项式的顺序储存结构类型定义
#define MAXSIZE 1000 //多项式可能达到的最大长度
typedef struct { //多项式非零项的定义
float p; //系数
int e; //指数
}Polynomial;
typedef struct{
Polynomial *elem //储存空间的基地址
int length; //多项式中当前项的个数
}SqList; //多项式的顺序储存结构类型为SqList
2 数组定义
数组静态分配： 数组动态分配：
typedef struct { typedef struct {
ElemType data[MaxSize]; ElemType *data'
int length; int length;
}SqList; //顺序表类型 }SqList; //顺序表类型
SqList L;
L.data=(ElemType )malloc(sizeof(ElemType) * MaxSize);
3 动态内存分配
1.c语言的内存动态分配
SqList L;
L.data=(ElemType )malloc(sizeof(ElemType) * MaxSize);
1.malloc(m)函数 开辟m字节长度的地址空间，并返回这段空间的首地址
2.sizeof(x)运算 计算变量x的长度
3.free(p)函数 释放指针p所指变量的储存空间，即彻底删除一个变量
需要加载头文件：
2.C++的动态储存分配
new 类型名T （初值列表） 例：int *p1= new int ;
功能： 或 int *p1 = new int (10)
申请用于存在T类型对象的内存空间，并依初值列表赋以初值结果值；
成功：T类型的指针，指向新分配的内存
失败：0(NULL)
delete 指针P
功能： 例：delete P1
释放指针p所指向的内存，P必须是new操作的返回值
3.C++z中的参数传递
1.函数调用时传送给形参表的实参必须与形参三个一致：
类型 个数 顺序
2.参数传递有两种方式：
==传值方式==（参数为整型，实型，字符型等）
==传地址==
· 参数为指针变量
· 参数为引用类型
· 参数为数组名
A 指针变量做参数
1.形参变化影响实参
2.形参变化不影响实参
例：
B 数组名做参数
传递的是数组的首地址
对形参数组所做的任何改变都将反映到实参数组中
==注意==
在传递过去的形参数组中，例 char b[ ] 方括号中不能指明大小，，因为传递过来的是数组的首地址。
C 引用类型作参数
3.5线性表的链式储存结构
3.5.1线性表链式储存结构定义
n个结点(ai的储存映像)链结成一个链表，即为线性表的链式储存结构
我们把链表中第一个结点的储存位置叫做头指针，在单链表的第一个结点==(首元结点)==前附设一个结点，称为头结点。
头结点的数据域可以不存任何信息，也可储存线性表的长度等附加信息。
注意:==在统计表长的时候，头结点不能计入链表长度值==
一个结点是由数据域和指针域构成的，数据域储存数据元素，指针域储存的是下一个结点的地址，因为是通过地址来连接，所以链式线性表储存单元可以连续，也可以不连续。
首元结点:是指链表中存储第一个数据元素a1的结点
3.5.2头指针与头结点的异同
头指针 头结点
- 头指针是指链表指向第一个结点的指针，若链表有头结点 1.头结点是为了操作的统一和方便而设立的，放在第一
则是指向头结点的指针 元素结点之前，其数据域一般无意义(也可储存表长)
2.头指针具有标志作用，所以常用头指针冠以链表名字 2.有了头结点，对在第一元素结点前插入结点和删除第
3.无论链表是否为空，头指针均不为空，头指针是链表的必要元素 一结点，其操作与其他结点的操作就统一了
3.头结点不一定是链表必需要素
3.5.3线性表链式存储结构代码描述
图片插入一
代码实现
/* 线性表的单链表存储结构 */
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定义LinkList*/ 注意:这里的定义形式 Node *L=LinlList L;
这里的Node通常指向的是结点，而LinkList一般指向的是地址
3.6单链表的读取
读取单链表的思路
- 声明一个指针p指向链表第一个结点，初始化j从1开始；
- 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
- 若到链表末尾p为空，则说明第i个结点不存在；
- 否则查找成功，返回结点p的数据
代码的实现如下：
/* 初始条件：链式线性表L已存在，1<=i<=ListLength(L)*/
/* 操作条件：用e返回L中第i个数据元素的值*/
Status GetElem(LinkList L ,int i , Elemtype *e)
{
int j;
LinkList p;
p=L->next;
j=1;
while(p&&j<i)
{
p=p->next;
++j;
}
if(!p||j>i)
return ERROR;
*e=p->data;
return OK;
}
3.7单链表的插入和删除
3.7.1单链表的插入
插入2
这俩个代码的顺序不能发生变化，如果1和2发生了交换，则断掉了后面的连续
单链表第i个数据插入结点的算法思路：
- 声明一指针p指向链表头结点，初始化j从1开始；
- 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
- 若到链表末尾p为空，则说明第i个结点不存在；
- 否则查找成功，在系统中生存一个空结点s；
- 将数据元素e赋值给s->data;
- 单链表的插入标准语句s->next=p->next; p->next=s;
- 返回成功。
代码实现如下：
/* 初始条件:链式线性表L已存在，1<=i<=ListLength(L)*/
/* 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1*/
Status ListInsert(LinkList *L,int i ,ElemType e)
{
int j;
LinkList p,s;
p=L->next;
j=1;
while(p&&j<i) /*寻找第i个结点*/
{
p=p->next;
++j;
}
if(!p||j>i)
return ERROR; /*第i个结点不存在*/
s=(LinkList)malloc(sizeof(Node)); a /*生成新结点（C语言）*/
s->data=e; a
s-next=p->next; /*连接的过程*/
p-next=s;
return OK;
}
3.7.2单链表的删除
插入图片三
单链表第i个数据删除结点的算法思路：
- 声明一指针p指向链表头结点，初始化j从1开始；
- 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
- 若到链表末尾p为空，则说明第i个结点不存在；
- 否则查找成功，将预删除的结点p->next赋值给q；
- 单链表的删除标准语句p-next=q-next；
- 将q结点中的数据赋值给e，作为返回；
- 释放q结点；
- 返回成功；
实现代码算法如下：
/* 初始条件：链式线性表L已存在，1<=i<=LisrLength(L)*/
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减一*/
Status ListDelete(LinkList *L,int i,ElemType *e)
{
int j；
LinkList p,q;
p=L->next；
j=1;
while(p-next&&j<i)
{
p=p->next； /* 遍历寻找第i个元素*/
++j;
}
if(!(p->next)||j>i)
return ERROR;
q=p->next;
p-next=q->next; /* 将q的后继赋值给p的后继*/
*e=q->data;
free(q); /* 让系统回收此结点，释放内存*/
return OK;
}
==注意==
为什么这里的是p->next是因为确保p的后继结点不是空的，要有数据元素的存在，不然无意义，不像前面的插入！！！！
对于插入或删除数据越频繁的操作，单链表的效率优势越明显。
3.8单链表的整表创建
单链表整表创建的算法思路：
声明一指针p和计数变量i；
初始化一空链表L；
让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
循环：
a.生成一新结点赋值给p；
b.随机生成一数字赋值给p的数据域p->data;
c.将p插入到头结点与前一新结点之间
实现代码算法如下
/* 随机产生n个元素的值，建立带头结点的单链线性表L (头插法)*/
void CreateListHead(LinkList *L ,int n)
{
LinkList p;
int i;
srand(time(A)); /* 初始化随机数种子*/
*L=(LinKList )malloc(sizeof(Node));
(*L)->nexy=NULL; /* 先建立一个带头结点的单链表*/
for(i=0;i<n;i++)
{
p =(LinkList)malloc(sizeof(Node)); /* 生成新结点*/
p->data= rand()%100+1; /* 随机生成100以内的数字*/
p->next= (*L)->next;
(*L)->next= p; /* 插入到表头*/
}
}
/* 随机产生n个元素的值，建立带表头结点的单链线性表L (尾插法)*/
void CreateListTail(LinkList *L,int n)
{
LinkList p,r;
int i;
srand(time(A)); /* 初始化随机数种子*/
*L =(LinkList)malloc(sizeof(Node)); /* L为整个线性表*/
r=*L; /* r为指向尾部的结点*/
for(i=0;i<n;i++)
{
p=(Node *)malloc(sizeof(Node)); /**/
p->data=rand()%100+1;
r->next=p;
r=p;
}
r->next=NULL;
}
3.9单链表的整表删除
单链表整表删除的算法思路如下：
声明一指针p和q
将第一个结点赋值给p
循环：
a.将下一结点赋值给q；
b.释放p；
c.将q赋值给p。
实现代码算法如下:
/* 初始条件：链式线性表L已存在， 操作结果：将L重置为空表*/ Status ClearList(LinkList *L) { LinkList p,q; p=(*L)->next; /*p指向第一个结点*/ while(p) /*没到表尾*/ { q=p->next; free(p); p=q; } (*L)->next=NULL; /*头结点指针域为空*/ return OK; }
思考，这里的q变量的作用？
3.10单链表结构与顺序储存结构的优缺点
插入图4
总结得出一些结论：
若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构
当线性表中的元素个数变化较大或者根本不知道多大时，最好用单链表结构
3.11静态链表
此种的情况的前提，没有指针的情况，用数组描述的链表叫做静态链表，是由俩个数据域组成，data和cur。
cur相当于单链表中的next，存放该元素的后继在数组中的下标
cur叫做游标
代码的实现如下：
#define MAXSIZE 1000
/*线性表的静态链表存储结构*/
typedef struct
{
ElemType data;
int cur;
}Component,StaticLinkList[MAXSIZE];
静态链表的特殊处理：
- 对数组的第一个和最后一个元素做特殊处理，不存数据。
- 通常把未被使用的数组元素成为备用链表
- 数组的第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标
- 数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用。
插入图5
代码实现：
/*将一维数组space中各分量链成一个备用链表，space[0].cur为头结点*/
Status InitList(StaticLinkList space)
{
int i;
for(i=0;i<MAXSIZE;i++)
space[i].cur=i+1;
space[MAXSIZE-1],cur=0;
return OK;
}
示意图：
下标 0 1 2 3 4 5 6 7 8 ....... 999
data [] 甲 乙 丁 戊 己 庚
cur 7 2 3 4 5 6 0 8 9 ....... 1
备用链表第一个 下一位置数据为空 8.9后面为空闲空间 数组最
结点 的下标改为7 则cur用0表示 为备用空间 后一个元素cur用存
第一个插入元素的下标，相当于头结点
/* 若备用空间链表非空，则返回分配的结点下标，否则返回0*/
int Malloc_SSL(staticlink space)
{
int i;
i=space[0].cur
if(space[o].cur)
space[o].cur=space[i].cur;
return i;
}
3.11.2静态链表插入的思路:
先将要插入的数据放入到备用链表的第一个，然后将要插入的位置的前一个的cur改为备用链表的第一个空间的下标，在将下标的cur改为插如为止后面的下标
代码实现如下:
Status ListInsert(StaticLinkList L, int i ,ElemType e)
{
int j,k,l;
k=MAXSIZE-1;
if(i<1||i>ListLength(L)+1)
return ERROR;
j=malloc_SSL(L);
if(j)
{
L[j].data=e;
for(l=1;l<=i-1;l++)
k=L[k].cur;
L[j].cur=L[k].cur
L[k].cur=j;
return OK;
}
return ERROR;
}
静态链表删除操作
删除思路:插入图片
/*删除在L中第i个数据元素*/
Status ListDelete(StaticLinkList L,int i)
{
int j,k;
k=MAXSIZE-1;
if(i<1||i>ListLength(L))
return ERROR;
for(j=1;j<i-1;j++)
k=L[k].cur;
j=L[K].cur;
L[k].cur=L[j].cur;
Free(L,j);
return OK;
}
/**将下标为k的空闲结点回收到备用链表/
void Free_SSL(StaticLinkList space ,int k)
{
space[k].cur=space[0].cur;
space[0].cur=k;
}
静态链表的求长:
/* 初始条件:静态链表L已存在 操作结果:返回L中数据元素的个数*/
int ListLength(StaticLinkList L)
{
int j=0;
int i=[maxsize-1].cur;
while(i)
{
i=L[i].cur;
j++;
}
return j;
}
静态链表的优缺点:
插入图片：
3.12循环链表
3.12.1循环链表的定义:
就是将单链表中终端结点的指针段由空指针改为指向头结点，形成了一个环。
循环链表中可以包括头结点也可以不包括头结点。
包含头结点的空链表的表达形式，其头结点的指针域指向是头结点自己的本身。
而非空链表，则是链表的最后一个数据元素的指针域则是指向头结点。
注意，循环链表的判断循环结束的条件p-next 是不是指向的是头结点，若是，则循环结束，而普通的判断则是p-next是不是指向的是NULL；
3.12.2循环链表引入尾指针
循环链链表的尾指针是指向链表数据元素的最后一个指针域，有利于提升算法的时间效率 ，此时查找开始结点和终端结点都方便。
则此时的头结点的表达方式为，rear->next->next;;
插入图片（0）
代码的实现的过程:
与=引入中间变量的思想，类似于交换AB杯中水的问题：
p=rearA->next;
rearA->next=raerB->next->next;
q=rearB->next;
rearB->next=p;
free(q);
代码需要后序的解读：
3.13双向链表
3.13.1双向链表的定义:
双向链表是在单链表的每个结点中，在设置一个指向其前驱结点的指针域，一个指向直接后继，一个指向直接前驱：
代码的实现
/* 线性表的双向表存储结构*/
typedef struct DulNode
{
ElemType data;
struct DulNode *prior;
struct DulNode *next;
}DulNode ,*DulLinkList;
示意图的插入：
双向链表的特性：
==p->next->prior=p->prior->next;==
3.13.2双向链表的插入的操作:
假设存储元素e的结点为S，实现的目标是将结点s插入到p和p->next之间；
s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
同时注意其他类型的变化；
理解性的记忆，先处理s的前驱和后继，在处理后继结点的前驱，在解决前驱结点的后继。
3.13.3双向链表的删除的操作：
假设p结点存在，删除p结点。
代码的实现
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
双向链表的操作相对于单链表来说，会更复杂，而他的操作的时间的效率会更快，但会占用更多的储存空间，利用空间来换取时间的效率。
