数据结构第二章(汇总)
2线性表
“以下四章为线性结构相关的知识，同时本章是整个课程的重点与核心内容，也是其他后续章节的重要基础。”
2.1 线性表的定义和特点
线性表是具有相同特性的数据元素的一个有限序列
$\large (a1,a2,a3,……a_i,a_{i+1},……,a_n)$ 也就是说数组就是线性表咯
其中数据元素的个数n定义为表的长度。
-
当n=0时称为空表。
-
将非空的线性表记作(a1,a2……，an)
可以看出线性表的逻辑特征是：
- 有且仅有一个开始结点$a1$，他没有直接前驱，而仅有一个直接后继$a2$。
- 有且仅有一个终端结点$a_n$，他没有直接前驱，而仅有一个直接前驱$a{n-1}$。
- 其余内部结点都有且仅有一个直接前驱和一个直接后继。
2.2 案例引入
2.2.1 一元多项式的运算
$\large P_n(x)=p_0+p_1x+p_2x^{2}+……+p_nx^n$ $\large Q_n(x)=q_0+q_1x+q_2x^{2}+……+q_nx^n$
- 其中$\large p_x和\large q_x$是系数
- 那么两个多项式相加的结果$R_n(x)=P_n(x)+Q_m(x)$可用线性表R表示：
- $\large R=(p_0+q_0,p1+q1,p2+q2+……+p_n+q_n)$
- 那么两个多项式相加的结果$R_n(x)=P_n(x)+Q_m(x)$可用线性表R表示：
2.2.2 稀疏多项式的运算
$\large S(x)=1+3x^{10000}+2x^{20000}$
- 仅记录系数不为零的系数即可，这样可以大大节省空间。
线性表A：(7,0)、(3,1)、(9,8)、(5,7)
线性表B：(8,1)、(22,7)、(-9,8)
- 创建一个新数组C
- 分别从头比较A、B的每一项 PS：就是相当于走一遍一元多项式运算的步骤
- 指数相同：对应系数相加，若其和不为零，则在C中增加一个新项
- 指数不相同：则将指数较小的项复制到C中
- 一个线性表添加完后，将另一个线性表剩余项依次复制到C中即可
| 0 | 1 | 7 | 8 | 7 |
|---|---|---|---|---|
| 7 | 11 | 22 | 0 | 5 |
- 顺序结构存在的问题
- 存储空间分配不灵活
- 运算的空间复杂度高
- 由此引出了链式存储结构
-
- 不需要额外的操作空间
2.2.3 图书信息管理系统
- 将图书表抽象为线性表
- 表中每本图书抽象线性表中数据元素
- 具体实现，学完这一章就会了，暂时按下不表
总结：
- 线性表中数据元素的类型可以为简单类型，也可以为复杂类型。
- 许多实际应用问题所涉及的基本操作有很大相似性，不应为每个具体应用单独编写一个程序。
- 从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构和基本操作。
2.3 线性表的类型定义
- 抽象数据类型线性表定义如下：
PS: List是线性表的英文名
- 基本操作：
- InitList(&L) (Initialization List)
操作结果：构造一个空的线性表L。 - DestroyList(&L)
初始条件:线性表L已存在。
操作结果：将L重置为空表。 - ListEmpty(L)
初始条件：线性表L已存在。
操作结果：若L为空表， 则返回true, 否则返回false。 - ListLength(L)
初始条件：线性表L已存在。
操作结果：返回L中数据元素个数。 - GetElem(L,i,&e)
初始条件：线性表L巳存在，且1:,s;i:os;ListLength(L)。
操作结果：用e返回L中第1个数据元素的值。 - LocateElem(L,e)
初始条件：线性表L已存在
操作结果：返回L中第1个 值与e相同的元素在 L中的位置 。若这样的数据元素不存在 ， 则返回值为0。 - PriorElem(r,cur_e,&pre_e)
初始条件：线性表L已存在。
操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回其前驱，否则操作失败，pre_e无定义。 - NextElem(L,cur_e,&next_e)
初始条件：线性表L已存在。
操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义。 - Listinsert(&L,i,e)
初始条件：线性表L已存在，且1:,s;i:os;ListLength (L) +l。
操作结果：在 L中第1个位置之前插入新的数据元素 e, L的长度加1。 - ListDelete(&L,i)
初始条件：线性表L已存在且非空 ，且l:os;i:os;ListLength(L)。
操作结果：删除L的第1个数据元素，L的长度减1。 - TraverseList(L)
初始条件：线性表L已存在
操作结果：对线性表L进行遍历，在遍历过程中对 L的每个结点访问一次。
- InitList(&L) (Initialization List)
2.4 线性表的顺序表示和实现
2.4.1 线性表的顺序存储表示
- 线性表的顺序表示又称为顺序存储结构或顺序映像
- 顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构
线性表的第一个数据元素$a_1$的存储位置，称作线性表的起始位置或基地址
-
顺序表的特点：以物理位置相邻表示逻辑关系，任一元素均可随机存取。（优点）
- PS：必须是占用一片连续的存储空间，中间不存在空的存储单元
-
线性表类型定义的模版：
1 |
|
- 例一：多项式的顺序存储结构类型定义
1 |
|
- 例二：图书表的顺序存储结构类型定义
1 |
|
-
补充：数组定义
-
数组静态分配
1
2
3
4typedef struct{
ElemType data[MaxSize];
int length;
}SqList; //顺序表类型 -
数组动态分配
1
2
3
4typedef struct{
ElemType *data;
int length;
}SqList; //顺序表类型 -
C语言的内存动态分配
SqList L；
L.data=(ElemType*^f)malloc(sizeof(ElemType)*MaxSize);
需要加载头文件：<stdlid.h>
-
-
传地址方式——指针变量做参数(c++)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void swap(float*m,float*n){
float t:
t=*m;
*m=*n;
*n=t;
}
void main(){
float a,b,*p1,*p2;
cin>>a>>b; //cin>>输入的意思
p1=&a; p2=&b;
swap(p1,p2);
cout<<a<<endl<<b<<endl; //endl换行的意思
} -
传地址方式——数组名作参数
1
2
3
4
5
6
7
8
9
void sub(char b[]){
b[]="world";
}
void main (void){
char a[10]="hello";
sub(a):
cout<<a<<endl; //结果为world
} -
传地址方式——引用类型作参数
1
2
3
4
5
6
7
void main(){
int i=5;
int &j=i; //i是本名；j是小名
i=7; //i值改变j值也会跟着改变
cout<<"i="<<i<<"j="<<j; //输出i=7 j=7
}- 形参变化实参也发生变化
- 占有同一片区域
-
顺序表示意图
1
2
3
4
5
typedef struct{
ElemType *elem;
int length;
}SqList; //定义顺序表类型- $\large SqList$ $\large L$； //定义变量L，L是SqList这种类型的，L是个顺序表
2.4.2 顺序表的基本操作的实现
-
初始化线性表L
算法2.1 顺序表的初始化
- elem指向这段空间的基地址
- 将表的当前长度设为0
1
2
3
4
5
6Status lnitLIS_Sq(SqList &L){ //构造一个空的顺序表
L.elem=new ElemType[MAXSIZE]; //为顺序表分配空间
if(!L.elem)exit(OVERFLOW); //存储分配失败
L.length=0; //空表长度为0
retunrn OK;
} -
销毁线性表L
1
2
3void DestroyList(SqList &L){
if(L.elem)delete L.elem: //释放存储空间
} -
清空线性表L
1
2
3void ClearList(SqList &L){
L.length=0; //将线性表长度置为0
} -
求线性表L的长度
1
2
3int GetLength(SqList L){
return(L.length);
} -
判断线性表L是否为空
1
2
3
4int IsEmpty(SqList L){
if(L.length==0)return 1;
else return 0;
} -
取值
算法2.2 顺序表的取值
- 根据指定的位置序号$\large i$，获取顺序表中第$\large i$个数据元素的值。
- 若是$\large i$值合理，则将将第 $\large i $个数据元素 $\large L.elem[i-1]$赋给参数$\large e$, 通过$\large e$返回第 1 个数据元素的传值。
1
2
3
4
5int GetElem(SqList L,int i,ElemType &e){
if(i<1||i>L.length)return ERROR: //i是序号，所以不能小于1
e=L.elem[i-1];
return OK
} -
查找
算法2.3 顺序表的查找
- 从第一个元素开始，往后找，查找成功返回该元素的序号i+1
- 若找到最后还是没找到，则查找失败，返回0
1
2
3
4
5int LocateELem(SqList L,ElemType e){
for(i=0;i<L.length;i++)
jif(L.elem[i]==e)return i+1; //查找成功返回i+1
return 0； //查找失败返回0
}平均查找长度ASL ：在查找时，为确定元素在顺序表中的位置， 需和给定值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度
$\large ASL=\sum\limits_{i=1}^nP_iC_i$ $P_i$是第i个记录被查找的概率 $C_i$是第i个记录需要比较的次数
$\large ASL=p_1+2p_2+3p_3+np_n=\dfrac{1}{n}(1+2+3+……+n)$ 每一个记录被查找的概率都相等是$\large p_i=\dfrac{1}{n}$
$ASL=\dfrac{1}{n}\dfrac{n(n+1)}{2}=\dfrac{n+1}{2}$
tips：这里和C语言的查找有着异曲同工之妙，还是要打好C语言的基础学这个就会轻松很多了
-
插入
算法2.4 顺序表的插入
- 看插入位置是否合法（1<=i<=n+1）,不合法则返回error
- 看顺序表存储空间是否已满，已满返回error
- 将第n干活到第i个位置元素一次后移一个位置
- 将e放入第i个位置
- 表长+1
1
2
3
4
5
6
7
8
9status ListInsert(SqList &L,int i,ElemType e){
if(i<=1||i>L.length+1)return ERROR;
if(L.length==MAXSIZE)return ERROR;
for(j=L.length-1;j>=i-1;j--)
L,elem[j+1]=L.elem[j]; //元素后移
L.elem[i-1]=e; //赋值
L.length++; //表长加一
return OK;
}顺序表插入算法分析：$\large E_{ins}=\dfrac{1}{n+1}\sum\limits_{i=1}^{n+1}(n-i+1)=\dfrac{n}{2}$
i是第几个位置，x是移动次数，第1个移动n次，第2个移动n-1次最后一个移动0次，可发现$\large i+x=n+1$
所以顺序表插入算法的平均复杂度为$\large O(n)$ (前面最高次项的系数二分一是常数，删除了)
-
删除
算法2.5 顺序表的删除
- 判断位置i是否合法
- 将位置i后的元素一次前移
- 表长-1，删除成功返回OK、
1
2
3
4
5
6
7status ListInsert(SqList &L,int i,ElemType e){
if(i<=1||i>L.length+1)return ERROR;
for(j=i.j<length-1;j++
L,elem[j-1]=L.elem[j]; //元素前移
L，length--;
ruturn OK;
}顺序表删除算法分析：$\large E_{del}=\dfrac{1}{n}\sum\limits_{i=1}^{n}(n-i)=\dfrac{n-1}{2}$
i是第一个移动n-1次，i是2移动n-2次,i是第n个移动0次，可发现$\large x=n-i$
2.5 线性表的链式表示和实现
通过上一小节的学习，我们不难发现顺序表的优点是任一元素均可随机存取。但他的缺点也很明显，在进行插入和删除操作时，需移动大量元素，存储空间不灵活
所有这些问题，都可以通过线性表的另一种表示方法——链式存储结构来解决。
- 再开始本章的学习之前，我们先了解一下什么是链表：
- 用一组物理位置任意的存储单元来存放线性表的数据元素。
- 这组存储单元既可以是连续的也可以是不连续的，甚至是零散分布在存储中任意位置上的。
- 链表中的元素的逻辑次序和物理次序不一定相同
其中姓名列为数据域，数据域是用来存储元素数值数据
后面的四位编码为指针域，用来存储直接后继结点的存储位置
我们可以通过头指针来命名单链表
- 与链式存储相关的术语
- 结点：数据元素的存储映像。有数据域和指针域两部分组成
- 链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。
- 单链表，双链表，循环链表
- 节点只有一个指针域的链表称为单链表或线性链表
- 结点有两个指针域的链表，称为双链表
- 首位相连的链表称为循环链表
- 头指针，头结点，首元结点（头指针>头结点>首元结点）
- 头指针：指向链表中第一个结点的指针
- 首元结点：存储第一个元素的结点
- 头结点：首元结点前附设的一个结点
- 带头结点
- 不带头结点
-
空表如何表示？
无头结点时，头指针为空
有头结点时，头结点指针域为空
-
多设置一个头结点有什么好处？
-
便于首元结点的处理
结点是由结构体构造的，没有头结点的话，第一个数据元素的地址储存在头指针里，就没有储存在结构体里，操作上就和其他数据元素不同，而有了头结点，在链表里第一个位置的操作和其他位置一致，无须进行特殊处理
-
便于空表和非空表的统一处理
结点是由结构体构造的，没有头结点的话，第一个数据元素的地址储存在头指针里，就没有储存在结构体里，操作上就和其他数据元素不同
-
头结点的数据域内装什么
可以空着也可以存放线性表长度等附加信息，但该结点不能计入链表长度值
顺序表是随机存取法：找到要取的元素直接找他的位置就可以了
链表是顺序存取：只能从头指针进入链表，然后顺序扫描其余结点。
-
2.5.1 单链表的定义和表示
-
单链表的存储结构为： 数据域|指针域 =》 【data|next】
-
其中data什么类型取决于数据元素什么类型，如果处理的是学生表这种，比较复杂的数据类型，则通常定义为ElemType类型
-
next的类型取决于他存放的地址的数据元素是什么类型 比如存放的是int a=5,那么就是int *P
1 | typedef struct Lnode{ //声明结点的类型和指向结点的指针类型 |
定义链表L：LinkList L；
定义结点指针P：LNode *P；
- 例如：有一个存储学生学号、姓名、成绩的单链表结点类型定义如下：
1 | typedef Struct student{ |
这样写不常用，不方便不统一，通常用一下格式
1 | typedef Struct{ |
2.5.2 单链表基本操作和实现 （重点）
2.5.2.1 初始化
算法2.6 单链表的初始化
- 生成新结点作为头结点，用头指针L 指向头结点。
- 头结点的指针域置空。 =》 【 |^】
1 | Status lnitList_L(LinkList &L){ |
补充单链表的几个常用简单算法：
-
判断链表是否为空
1
2
3
4
5
6int ListEmpty(LinkList L){
if(L->next)
return 0;
else
return 1;
} -
单链表的销毁
-
从头指针开始，依次释放所有结点
1
2
3
4
5
6
7
8
9Status DestroyList_L(LinkList &L){ //销毁单链表P
Lnode *p; //或LinkLIst p
while(L){ //L指向空停止循环
p=L; //把L的地址给p
L=L->next; //L指向下一个地址
delete p; //删除p所指的结点
}
return OK;
}
-
-
清空链表
-
依次释放所有结点，并将头结点的指针域设置为空
1
2
3
4
5
6
7
8
9
10
11
12
13Status clearList_L(LinkList &L){ //将L重置为空表
Lnode *p,*q;
p=L->next;
while(p){ //没到表尾
g=p->next;
delete p;
p=q;
}
L->next=NULL; //头结点指针域为空
return OK:
}
-
-
求链表表长
-
从首元结点开始，依次计数所有结点
1
2
3
4
5
6
7
8
9
10int ListLength_L(LinkList L){ //LinkLIst定义的变量就是指针型的
LinkList p:
P=L->next;
i=0;
while(p){
i++;
p=p->next
}
return i;
}
-
重要知识点重温：
2.5.2.2 取值
算法2.7 取值 ——取链表中第i个元素的内容
-
从头开始，顺着链域往下搜索，指针后移且计数器x++直到x=i.
1
2
3
4
5
6
7
8
9Status GetElem_L(LinkList L,int i, ElemType &e){
p=L->next;i=1; //初始化
while(p&&j<i){ //向后扫，知道p指向第i个元素或p为空
p=p->next;++j;
}
if(!p||j>i)return ERROR; //第i个元素不存在
e=p->data;
return OK;
}//GetElem_L
2.5.2.3 查找
算法2.8 按值查找——根据指定数据获取改数据所在位置
-
从第一个结点开，依次和e比较
-
如果找到了与e值相等的数据元素，则返回其地址
-
没找到则返回0或NULL
1
2
3
4
5
6Lnode *LocateELem_L (LinkList L, Elemtype e) {
p=L->next;
while(p&&p->data!=e)
p=p->next;
return p;
}或者
1
2
3
4
5
6
7int LocateELem_L(LinkList L, Elemtype e){
p=L->next;i=1:
while(p&&p->data!=e)
{p=p->next;j++;}
if(p)return j; //没找到的话p指向空
else return 0;
}
2.5.2.4 插入
算法2.9 插入——在第i个结点前插入值为e的新结点
-
找到结点i-1
-
建构新结点s
-
s->next=p->next；p->next=s；
1
2
3
4
5
6
7
8
9Status Listlnsert_L(lLinkList &L,int i,ElemType e){
p=L;j=0;
while(p&&j<i-1){p=p->next;++j;} //找节点
if(!p||j>i-1)return ERROR; //判断位置是否合法（是否小于一或大于表长加一）
s=new LNode; s->data=e; //生成新结点s,数据域为e
s->next=p->next; //插入新结点
p->next=s;
return OK;
}//Listlnsert_L
2.5.2.5 删除
算法2.10 删除——删除第i个结点
-
找到结点i-1
-
p->next=p->next->next
-
释放结点i的空间
1
2
3
4
5
6
7
8
9
10Status ListDelet_L(LinkList &L,int i,ElemType &e){
p=L;j=0;q;i;
while(p->next&&j<i-1){p=p-next;++j;} //找到i-1
if(!(p->next)||j>i-1)return ERROR; //删除位置不合理
q=p->next; //q指向要删除的结点
p->next=q->next; //是p指针next域指向删除域的下一个结点
e=q->data; //保存删除结点的数据域
delete q; //释放空间
retun OK;
}
分析单链表查找，插入，删除算法的时间效率分析：
- 查找：应为只能顺序存取，即要从头指针开始找起，查找时间复杂度为$\large O(n)$
- 插入和删除：因为线性链表不需要移动元素，只用修改至臻，一般情况下的时间复杂度为$\large O(1)$
2.5.2.6 创建单链表
2.5.2.6.1 头插法——插到链表头部
-
L=new LNode;
L=（LinkList）malloc(sizeof(LNode));//C语言 //生成一个结点
p->data=$a_n$ //数据域赋值
-
p->next=L->next; L->next=p; //L指针域的空赋给p的指针域,L指针域指向p
1
2
3
4
5
6
7
8
9
10void CreateList_H(LinkList &L,int n){
L=new LNode;
L->next=NULL; //建立带头结点的单链表
for(i=n;i>0;--i){
p=（LNode*)malloc(sizeof（LNode)); //生成新结点
scanf(&p->data);
p->next=L->next;
L->next=P:
}
}
2.5.2.6.2 尾插法——插到链表尾部
-
从空表L开始，将新结点逐个插入到链表尾部，尾指针r指向链表的尾节点
-
初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。
1
2
3
4
5
6
7
8
9
10
11void CreatList_R(LinkList &L,int n){
L=new LNode;
L->next=NULL;
r=L;
for(i=0;i<n;++i){
p=（LNode*)malloc(sizeof（LNode)); //生成新结点
scanf(&p->data);
r->next=p;
r=p;
}
}
2.5.3 循环链表
-
循环链表：头尾相接的链表
- 优点：从表中任意结点出发均可找到表中其他结点
- 注意：终止条件为判断他们是否等于头指针
- 如果是头指针表示的单循环链表
- 找$a_1$的时间复杂度：O(1)
- 找$a_n$的时间复杂度：O(n)
- 若是尾指针表示的单循环链表
- 找$a_1$的存储是：R->next->next 时间复杂度：O(1)
- 找$a_n$的存储是：R 时间复杂度：O(1)
-
带尾指针循环链表的合并
-
p存表头结点 将Tb表头连接到Ta表尾 释放Tb表头结点 修改指针
-
p=Ta->next ; Ta->next=Tb->next->next ; delete Tb->next ; Tb->next=p;
1
2
3
4
5
6
7LinkList Connect(LinkList Ta,LinkList Tb){
p=Ta->next; // an指向b1,没毛病，但是bn指向a头结点p就找不到了因为第一步你覆盖了an，所以an指向b1前，要利用an找到a头结点，bn指向bn的next
Ta->next=Tb->next->next:
delete Tb->next:
Tb->next=p;
return Tb;
} //时间复杂度O(1) -
2.5.4 双向链表
-
双向链表的结构可以定义如下：
1
2
3
4typedef struct DuLNode{ //前面的Du是double双向的意思
Elemtype data;
struct DuLNode *prior,*next; //一个指向前驱，一个指向后驱
}DuLNode,*DuLinkList; -
双向循环列表
- 让头结点的前驱指针指向链表的最后一个结点
- 让最后一个结点的后继指针指向头结点
-
双向链表结构的对称性：
- $\large p->prior->next=p=p->next->prior$
算法2.13 双向链表的插入
-
-
void Listlnsert_DuL(DuLinkList &L, lnt i, ElemType e){ //双向链表头结点指针L，第i个位置，值为e的元素 if(!(p=GetElemP_DuL(L,i)))return ERROR; //确定第i个元素的位置指针P S=new DuLNode; s->date=e; s->prior=p->prior; P->prior->next=s; s->next=p; p->prior=s; return OK; }//Listlnsert_DuL1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
**算法2.14 双向链表的删除**
```c
void ListDelete_DuL(DuLinkList &L, lnt i, ElemType &e){
//用e返回
if(!(p=GetElemP_DuL(L,i)))return ERROR; //确定第i个元素的位置指针P，顺着链表查找时间复杂度为O(n)
e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
return OK;
}//ListDelete_DuL
-
单链表、循环链表和双向链表的时间效率比较
查找表头结点（首元结点） 查找表尾结点 查找结点*p的前驱结点 带头结点的单链表L L->next
时间复杂度O(1)L->next依次向后遍历
时间复杂度O(n)通过p->next无法找到其前驱 带头结点仅设头指针L的循环单链表 L->next
时间复杂度O(1)L->next依次向后遍历
时间复杂度O(n)通过p->next可以找到其前驱
时间复杂度O(n)带头结点仅设尾指针R的循环单链表 R->next
时间复杂度O(1)R
时间复杂度O(1)通过p->next可以找到其前驱
时间复杂度O(n)带头结点的双向循环链表L L->next
时间复杂度O(1)L-》prior
时间复杂度O(1)p->prior
时间复杂度O(1)
2.6顺序表和链表的比较
-
链式存储结构的优点：
-
结点空间可以动态申请和释放
-
数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素
-
-
链式存储结构的缺点：
-
存储密度小，每个结点的指针域需要额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大。
-
$\large 存储密度=\dfrac {结点数据本身占用的空间}{结点占用的空间总量}$
-
链式存储结构是非随机存储结构。对任一结点的操作都要从头遍历，这增加了算法的复杂度
-
-
2.7 线性表的应用
2.7.1 线性表的合并
-
线性表的合并
-
问题描述：
假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合A=AUB
La=(7,5,3, 11) Lb=(2, 6, 3) ====》 La=(7, 5, 3, 11, 2, 6)
-
算法步骤：
从Lb中的每个元素,执行以下操作：
- 在La中查找该元素
- 如果找不到，则将其插入到La的最后
-
代码实现:
1
2
3
4
5
6
7
8void union(List &La, List Lb){
La_len=ListLength(La);
Lb_len=ListLength(Lb);
for(i=1;i<=Lb_len;i++){
GetElem(Lb,i,e);
if(!LocateElem(La,e)) Listlnsert(&La,++La_len,e);
}
}时间复杂度为La的长度乘以Lb的长度
-
2.7.2 有序表的合并
-
有序表的合并
-
问题描述：
已知线性表La 和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。
-
算法步骤：
- 创建一个空表Lc
- 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止
- 继续将La或Lb其中一个表的剩余结点插入在Lc表的最后
-
用顺序表实现合并的代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15void MergeList_Sq(SqList LA,SqList LB,SqList &LC){
pa=LA.elem;
pb=LB.elem; //指针pa和pb的初值分别指向两个表的第一个元素
LC.length=LA.length+LB.length; //新表的长度等于两表长之和
LC.elem=new ElemType[LC.length]; //为合并后的新表分配一个数组空间
pc=LC.elem; //指针pc指向新表第一个元素
pa_last=LA.elem+LA.length-1; //指针pa_last指向LA表的最后一个元素（基地址加上长度减一）
pa_last=LB.elem+LB.length-1; //指针pa_last指向LB表的最后一个元素（基地址加上长度减一）
while(pa<pa_last&&pb<=pb_last){ //两个表都非空
if(*pa<=*pb)*pc++=*pa++; //依次“摘取”两表中值较小的结点
else *pc++=*pb++;
}
while(pa<=pa_last) *pc++=*pa++; //LB表已经到达表位，将LA中剩余元素加入LC
while(pb<=pb_last) *pc++=*pb++; //LA表已经到达表位，将LB中剩余元素加入LC
}//MergeList_Sq -
用链表实现合并的代码实现：
1
2
3
4
5
6
7
8
9
10void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
pa=La->next; pb=Lb->next;
pc=Lc=La; //用La的头结点作为Lc的头结点
while( pa && pb){
if(pa->data<=pb->data) {pc->next=pa; pc=pa; pa=pa->next;}
else {pc->next=pb; pc=pb; pb=pb->next;}
}
pc->next=pa?pa:pb; //插入剩余段delete Lb;
delete LB;
}算法的时间复杂度是：O(ListLength(La)+ListLength(Lb)）
-
2.8案例分析与实现
案例2.1 一元多项式的运算：实现两个多项式加、减、乘、除运算 线性表
- 实现两个多项式相加运算
案例2.2：稀疏多项式的运算 链表
- 创建一个新数组C
- 分别从头遍历比较A和B的每一项
- 指数相同，系数相加，和若不为零，则在C中新加一项
- 指数不同，则将指数较小的项复制到C中
- 一个多项式已遍历完毕时，将另一个剩余项依次复制到C中即可
用顺序存储结构的话，存储空间分配不灵活，运算的空间复杂度高，所以我们常用链式存储结构
- 创建一个只有头结点的空链表。
- 根据多项式的项的个数n，循环n次执行以下操作:
- 生成一个新结点*s;
- 输入多项式当前项的系数和指数赋给新结点*s的数据域：
- 设置一前驱指针pre，用于指向待找到的第一个大于输入项指数的结点的前驱pre初值指向头结点;
- 指针q初始化，指向首元结点;
- 循链向下逐个比较链表中当前结点与输入项指数，找到第一个大于输入项指数的结点*q;
- 将输入项结点s插入到结点q之前。
- 算法步骤：
- 指针p1和p2初始化，分别指向Pa和Pb的首元结点
- p3指向和多项式的当前结点，初值为Pa的头结点
- 当指针p1和p2均未到达相应表尾时，则循环比较p1和p2所指结点对应的指数值(p1->expn与p2->expn) 有下列3种情况:
- 当p1->expn==p2->expn时，则将两个结点中的系数相加
- 若和不为零，则修改p1所指结点的系数值，同时删除p2所指结点
- 若和为零，则删除p1和p2所指结点;
- 当p1->expn
expn时，则应摘取p1所指结点插入到“和多项式”链表中去 - 当p1->expn>p2->expn时，则应摘取p2所指结点插入到“和多项式”链表中去
- 当p1->expn==p2->expn时，则将两个结点中的系数相加
- 将非空多项式的剩余段插入到p3所指结点之后
- 释放Pb的头结点
案例2.3 图书信息管理系统 线性表或链表
