第2章 线性表 丽水学院工学院

第2章 线性表 第3章 栈和队列 第4章 串、数组和广义表 线性结构 近5周 上课 内容 线性结构的定义： 第2章 线性表 第3章 栈和队列 第4章 串、数组和广义表 线性结构 近5周 上课 内容 （逻辑、存储和运算） 线性结构的定义： 若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。 可表示为：（a1 , a2 , ……, an） 丽水学院工学院

简言之，线性结构反映结点间的逻辑关系是 一对一 的 线性结构表达式：（a1 , a2 , ……, an） 线性结构的特点： ① 只有一个首结点和尾结点； ② 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。 简言之，线性结构反映结点间的逻辑关系是 一对一 的 线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是 线性表 丽水学院工学院

教学目标 第2章 线性表 1. 了解线性结构的特点 2.掌握顺序表的定义、查找、插入和删除 3.掌握链表的定义、创建、查找、插入和删除 第2章　线性表 教学目标 1. 了解线性结构的特点 2.掌握顺序表的定义、查找、插入和删除 3.掌握链表的定义、创建、查找、插入和删除 4.能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合 丽水学院工学院

教学内容 2.1 线性表的定义和特点 2.2 案例引入 2.3 线性的类型定义 2.4 线性表的顺序表示和实现 2.2 案例引入 2.3 线性的类型定义 2.4 线性表的顺序表示和实现 2.5 线性表的链式表示和实现 2.6 顺序表和链表的比较 2.7 线性表的应用 2.8 案例分析与实现 丽水学院工学院

2.1 线性表的定义和特点 （a1, a2, … ai-1，ai, ai＋1 ，…, an） 线性表的定义：用数据元素的有限序列表示 空表 线性起点 ai的直接前趋 ai的直接后继 线性终点 n为元素总个数，即表长 下标，是元素的序号，表示元素在表中的位置 空表 n=0时称为 丽水学院工学院

数据元素都是字母; 元素间关系是线性 数据元素都是记录; 元素间关系是线性 同一线性表中的元素必定具有相同特性 例1 分析26 个英文字母组成的英文表 （ A, B, C, D, …… , Z） 数据元素都是字母; 元素间关系是线性 例2 分析学生情况登记表 学号 姓名 性别 年龄 班级 041810205 于春梅 女 18 04级计算机1班 041810260 何仕鹏 男 20 04级计算机2班 041810284 王 爽 19 04级计算机3班 041810360 王亚武 04级计算机4班 ： 数据元素都是记录; 元素间关系是线性 同一线性表中的元素必定具有相同特性 丽水学院工学院

2.2 案例引入 案例2.1 ：一元多项式的运算 Pn(x) = p0 + p1x + p2x2 + … + pnxn 线性表P = (p0,p1,p2,…,pn) 数组表示 （每一项的指数i隐含在其系数pi的序号中） P(x) = 10 + 5x - 4x2 + 3x3 + 2x4 指数 （下标i） 1 2 3 4 系数p[i] 10 5 -4 丽水学院工学院

Rn(x) = Pn(x) + Qm(x) 稀疏多项式S(x) = 1 + 3x10000 + 2x20000 丽水学院工学院 线性表R = (p0 + q0,p1 + q1,p2 + q2,…,pm + qm,pm+1,…,pn) 稀疏多项式S(x) = 1 + 3x10000 + 2x20000 丽水学院工学院

线性表P =((p1, e1), (p2, e2),…,(pm, em)) 案例2.2 ：稀疏多项式的运算 多项式非零项的数组表示 （a）A(x) = 7 + 3x + 9x8 + 5x17 （b）B(x) = 8x + 22x7 − 9x8 下标i 1 2 3 系数a[i] 7 9 5 系数 b[i] 8 22 -9 指数 17 线性表P =((p1, e1), (p2, e2),…,(pm, em)) 创建一个新数组c 分别从头遍历比较a和b的每一项 指数相同，对应系数相加，若其和不为零，则在c中增加一个新项 指数不相同，则将指数较小的项复制到c中 一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可 北京林业大学信息学院

链式存储结构 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 丽水学院工学院 pa pb 顺序存储结构存在问题 存储空间分配不灵活 运算的空间复杂度高 链式存储结构 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 -1 7 3 1 9 8 5 17 22 -9 A B pa pb 丽水学院工学院

多项式相加 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 丽水学院工学院 pa pb A -1 7 3 1 3 1 9 8 5 17 B -1 8 1 22 7 -9 8 pb 丽水学院工学院

多项式相加 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 丽水学院工学院 pa pb A -1 7 11 1 11 1 9 8 5 17 B -1 8 1 22 7 -9 8 pb 丽水学院工学院

多项式相加 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 丽水学院工学院 pa pb A -1 7 11 1 11 1 9 8 5 17 B -1 8 1 22 7 -9 8 pb 丽水学院工学院

多项式相加 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 丽水学院工学院 pa pb A -1 7 11 1 11 1 9 8 5 17 B -1 8 1 22 7 -9 8 pb 丽水学院工学院

案例2.3 ：图书信息管理系统 （1）查找 （2）插入 （3）删除 （4）修改 （5）排序 （6）计数 丽水学院工学院

图书顺序表 图书链表 丽水学院工学院

丽水学院工学院 线性表中数据元素的类型可以为简单类型，也可以为复杂类型。 许多实际应用问题所涉的基本操作有很大相似性，不应为每个具体应用单独编写一个程序。 从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构和基本操作。 丽水学院工学院

2.3 线性表的类型定义 线性表的重要基本操作 1. 初始化 2. 取值 3. 查找 4. 插入 5. 删除 丽水学院工学院

2.4 线性表的顺序表示和实现 线性表的顺序表示又称为顺序存储结构或顺序映像。 顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。 简言之，逻辑上相邻，物理上也相邻 顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]来实现。 丽水学院工学院

顺序存储 丽水学院工学院 元素n …….. 元素i 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址 存储内容 Loc(元素i)=Lo+（i-1)*m 顺序存储 丽水学院工学院

顺序表的类型定义 丽水学院工学院 #define MAXSIZE 100 //最大长度 typedef struct { ElemType *elem; //指向数据元素的基地址 int length; //线性表的当前长度 }SqList； 丽水学院工学院

图书表的顺序存储结构类型定义 丽水学院工学院 #define MAXSIZE 10000 //图书表可能达到的最大长度 typedef struct //图书信息定义 { char no[20]; //图书ISBN char name[50]; //图书名字 float price; //图书价格 }Book; typedef struct Book *elem; //存储空间的基地址 int length; //图书表中当前图书个数 }SqList; //图书表的顺序存储结构类型为SqList 丽水学院工学院

malloc(m)：开辟m字节长度的地址空间，并返回这段空间的首地址 补充：C语言的动态分配函数（ <stdlib.h> ） malloc(m)：开辟m字节长度的地址空间，并返回这段空间的首地址 　　sizeof(x)：计算变量x的长度 free(p)：释放指针p所指变量的存储空间，即彻底删除一个变量 丽水学院工学院

int *p1= new int; 或 int *p1 = new int[10]; 补充：C++的动态存储分配 new 类型名T（初值列表） 功能： 申请用于存放T类型对象的内存空间，并依初值列表赋以初值 结果值： 成功：T类型的指针，指向新分配的内存 失败：0（NULL） int *p1= new int; 或 int *p1 = new int[10]; delete 指针P 功能： 释放指针P所指向的内存。P必须是new操作的返回值 delete p1; 丽水学院工学院

线性表的重要基本操作 1. 初始化 2. 取值 3. 查找 4. 插入 5. 删除 丽水学院工学院

重要基本操作的算法实现 在进行函数调用时，在函数体内，对形参进行运算相当于对实参进行运算。 初始化线性表L （参数用引用） 丽水学院工学院 Status InitList_Sq(SqList &L){ //构造一个空的顺序表L L.elem=new ElemType[MAXSIZE]; //为顺序表分配空间 if(!L.elem) exit(OVERFLOW); //存储分配失败 L.length=0; //空表长度为0 return OK; } 丽水学院工学院

初始化线性表L （参数用指针） 丽水学院工学院 Status InitList_Sq(SqList *L){ //构造一个空的顺序表L L-> elem=new ElemType[MAXSIZE]; //为顺序表分配空间 if(! L-> elem) exit(OVERFLOW); //存储分配失败 L-> length=0; //空表长度为0 return OK; } L-> elem L-> length 丽水学院工学院

补充：几个简单基本操作的算法实现 销毁线性表L 清空线性表L 丽水学院工学院 void DestroyList(SqList &L) { if (L.elem) delete[]L.elem; //释放存储空间 } 清空线性表L void ClearList(SqList &L) { L.length=0; //将线性表的长度置为0 } 丽水学院工学院

补充：几个简单基本操作的算法实现 求线性表L的长度 判断线性表L是否为空 int IsEmpty(SqList L) { int GetLength(SqList L) { return (L.length); } 判断线性表L是否为空 int IsEmpty(SqList L) { if (L.length==0) return 1; else return 0; } 丽水学院工学院

线性表的重要基本操作 1. 初始化 2. 取值 3. 查找 4. 插入 5. 删除 丽水学院工学院

2. 取值（根据位置i获取相应位置数据元素的内容） 获取线性表L中的某个数据元素的内容 int GetElem(SqList L,int i,ElemType &e) {if (i<1||i>L.length) return ERROR; //判断i值是否合理，若不合理，返回ERROR e=L.elem[i-1]; //第i-1的单元存储着第i个数据 return OK; } 丽水学院工学院

顺序查找图示 查找 16 查找成功 3.查找（根据指定数据获取数据所在的位置） data 25 34 57 16 48 09 i 0 1 2 3 4 5 data 25 34 57 16 48 09 查找 16 i 25 34 57 16 48 09 i 25 34 57 16 48 09 i 25 34 57 16 48 09 i 查找成功 丽水学院工学院

3. 查找（根据指定数据获取数据所在的位置） data 25 34 57 16 48 查找 50 i 25 34 57 16 48 i 0 1 2 3 4 data 25 34 57 16 48 查找 50 i 25 34 57 16 48 i 25 34 57 16 48 i 25 34 57 16 48 i 25 34 57 16 48 查找失败 i 丽水学院工学院

3. 查找（根据指定数据获取数据所在的位置） 查找算法时间效率分析 ？？？ 在线性表L中查找值为e的数据元素 int LocateELem(SqList L,ElemType e) { for (i=0;i< L.length;i++) if (L.elem[i]==e) return i+1; return 0; } 查找算法时间效率分析 ？？？ 丽水学院工学院

4. 插入（插在第 i 个结点之前） 插第 4 个结点之前，移动 6－4+1 次 插在第 i 个结点之前，移动 n-i+1 次 2 3 4 5 6 7 8 9 25 12 47 89 36 14 25 12 47 89 36 14 25 12 47 89 36 14 25 12 47 89 36 14 25 12 47 99 89 36 14 99插入 插第 4 个结点之前，移动 6－4+1 次 插在第 i 个结点之前，移动 n-i+1 次 丽水学院工学院

【算法步骤】 丽水学院工学院 （1）判断插入位置i 是否合法（合法值为1≤i≤length+1）。 （2）判断顺序表的存储空间是否已满。 （4）将要插入的新元素e放入第i个位置。 （5）表长加1，插入成功返回OK。 丽水学院工学院

【算法描述】 4. 在线性表L中第i个数据元素之前插入数据元素e 丽水学院工学院 Status ListInsert_Sq(SqList &L,int i ,ElemType e){ if(i<1 || i>L.length+1) return ERROR; //i值不合法 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; //将新元素e放入第i个位置 ++L.length; //表长增1 return OK; } 丽水学院工学院

【算法分析】 算法时间主要耗费在移动元素的操作上 若插入在尾结点之后，则根本无需移动（特别快）； 若插入在首结点之前，则表中元素全部后移（特别慢）； 若要考虑在各种位置插入（共n+1种可能）的平均移动次数，该如何计算？ 丽水学院工学院

5. 删除（删除第 i 个结点） 删除第 4 个结点，移动 6－4 次 删除第 i 个结点，移动 n-i 次 丽水学院工学院 1 2 3 4 7 8 9 25 12 47 89 36 14 25 12 47 36 14 25 12 47 36 14 25 12 47 36 14 删除 删除第 4 个结点，移动 6－4 次 删除第 i 个结点，移动 n-i 次 丽水学院工学院

【算法步骤】 （1）判断删除位置i 是否合法（合法值为1≤i≤L.length）。 （2）将欲删除的元素保留在e中。 （4）表长减1，删除成功返回OK。 丽水学院工学院

【算法描述】 5. 将线性表L中第i个数据元素删除 丽水学院工学院 Status ListDelete_Sq(SqList &L,int i){ if((i<1)||(i>L.length)) return ERROR; //i值不合法 for (j=i;j<=L.length-1;j++) 　 　L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移 --L.length; //表长减1 return OK; } 丽水学院工学院

【算法分析】 算法时间主要耗费在移动元素的操作上 若删除尾结点，则根本无需移动（特别快）； 若删除首结点，则表中n-1个元素全部前移（特别慢）； 若要考虑在各种位置删除（共n种可能）的平均移动次数，该如何计算？ 丽水学院工学院

显然，顺序表的空间复杂度S(n)=O(1) 查找、插入、删除算法的平均时间复杂度为 　　　O(n) 显然，顺序表的空间复杂度S(n)=O(1) （没有占用辅助空间） 丽水学院工学院

顺序表（顺序存储结构）的特点 （1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致 （2）在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等　 　这种存取元素的方法被称为随机存取法 丽水学院工学院

链表 顺序表的优缺点 缺点： 在插入、删除某一元素时，需要移动大量元素 浪费存储空间 属于静态存储形式，数据元素的个数不能自由扩充 优点： 存储密度大（结点本身所占存储量/结点结构所占存储量） 可以随机存取表中任一元素 缺点： 在插入、删除某一元素时，需要移动大量元素 浪费存储空间 属于静态存储形式，数据元素的个数不能自由扩充 链表 为克服这一缺点 丽水学院工学院

2.5 线性表的链式表示和实现 链式存储结构 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻 线性表的链式表示又称为非顺序映像或链式映像。 丽水学院工学院

单链表的存储映像 如何实现？ 通过指针来实现 (a) 可利用存储空间 free free first (b) 经过一段运行后的单链表结构  free first (b) 经过一段运行后的单链表结构 丽水学院工学院

例 画出26 个英文字母表的链式存储结构 逻辑结构：（ a, b, … ,y, z） 链式存储结构： a b z 丽水学院工学院 …… 例 画出26 个英文字母表的链式存储结构 逻辑结构：（ a, b, … ,y, z） 链式存储结构： a head b /\ z …… 丽水学院工学院

指针 数据 各结点由两个域组成： 数据域：存储元素数值数据 指针域：存储直接后继结点的存储位置 丽水学院工学院

1、结点：数据元素的存储映像。由数据域和指针域两部分组成 与链式存储有关的术语 1、结点：数据元素的存储映像。由数据域和指针域两部分组成 2、链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构 丽水学院工学院

单链表示意图： 3、单链表、双链表、循环链表： 结点只有一个指针域的链表，称为单链表或线性链表 a b z 丽水学院工学院 …… head /\ z …… 丽水学院工学院

3、单链表、双链表、循环链表： 有两个指针域的链表，称为双链表 双链表示意图： 丽水学院工学院

3、单链表、双链表、循环链表： 首尾相接的链表称为循环链表 循环链表示意图： 丽水学院工学院

4、头指针、头结点和首元结点 头指针 头结点 首元结点 头指针是指向链表中第一个结点的指针 首元结点是指链表中存储第一个数据元素a1的结点 head a2 … info an ^ 头指针是指向链表中第一个结点的指针 首元结点是指链表中存储第一个数据元素a1的结点 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息 丽水学院工学院

上例链表的逻辑结构示意图有以下两种形式： ① ZHAO QIAN LI SUN ZHOU WU ZHENG /\ WANG H ② ZHAO QIAN LI SUN ZHOU WU ZHENG /\ WANG H 区别：① 无头结点 ② 有头结点 丽水学院工学院

有头结点时，当头结点的指针域为空时表示空表 讨论1. 如何表示空表？ 有头结点时，当头结点的指针域为空时表示空表 非空表 空表 an a0 head ^ 表头结点 第一个结点 丽水学院工学院

首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理; 讨论2. 在链表中设置头结点有什么好处？ ⒈便于首元结点的处理 首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理; ⒉便于空表和非空表的统一处理 无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。 丽水学院工学院

讨论3. 头结点的数据域内装的是什么？ 头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。 H 头结点的数据域 丽水学院工学院

链表（链式存储结构）的特点 （1）结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻 （2）访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等 　这种存取元素的方法被称为顺序存取法 丽水学院工学院

链表的优缺点 优点 数据元素的个数可以自由扩充 插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高 丽水学院工学院

链表的优缺点 缺点 存储密度小 存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜） 丽水学院工学院

2.5.1 单链表的定义和实现 非空表 空表 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名 若头指针名是L，则把链表称为表L 丽水学院工学院

单链表的存储结构定义 LNode *p LinkList p typedef struct LNode{ ElemType data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; // *LinkList为Lnode类型的指针 LNode *p LinkList p 丽水学院工学院

LNode *p 注意区分指针变量和结点变量两个不同的概念 指针变量p：表示结点地址 结点变量*p：表示一个结点 若p->data=ai, 则p->next->data=ai+1 丽水学院工学院

2.5.2 单链表基本操作的实现 1. 初始化 2. 取值 3. 查找 4. 插入 5. 删除 丽水学院工学院

1.初始化(构造一个空表 ) 【算法步骤】 （1）生成新结点作头结点，用头指针L指向头结点。 （2）头结点的指针域置空。 【算法描述】 Status InitList_L(LinkList &L){ L=new LNode; L->next=NULL;　　　　　 return OK; } 丽水学院工学院

线性表的重要基本操作 1. 初始化 2. 取值 3. 查找 4. 插入 5. 删除 丽水学院工学院

2. 取值（根据位置i获取相应位置数据元素的内容） e=L.elem[i-1]; //第i-1的单元存储着第i个数据 链表的查找：要从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。 丽水学院工学院

例：分别取出表中i=3和i=15的元素 L i=3 i=15 21 18 30 75 42 56 ∧ p p p p p p j 6 7 2 3 1 1 从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p = L->next。 j做计数器，累计当前扫描过的结点数，j初值为1。 当p=p->next指向扫描到的下一结点时，计数器j加1。 当j = i时，p所指的结点就是要找的第i个结点。\ 当p为空或j=i时，结束查找。 【算法步骤】 丽水学院工学院

2. 取值（根据位置i获取相应位置数据元素的内容） //获取线性表L中的某个数据元素的内容 Status GetElem_L(LinkList L,int i,ElemType &e){ p=L->next;j=1; //初始化 while(p&&j<i){ //向后扫描，直到p指向第i个元素或p为空 p=p->next; ++j; } if(!p || j>i)return ERROR; //第i个元素不存在 ,i>n或i<1 e=p->data; //取第i个元素 return OK; }//GetElem_L 丽水学院工学院

L 21 18 30 75 30 56 p p p p p p j 1 2 1 3 7 6 3.查找（根据指定数据获取数据所在的位置） x=30 x=51 21 18 30 75 30 56 ∧ p p p p p p j 1 2 1 3 7 6 未找到，返回0 找到，返回i 从第一个结点起，依次和e相比较。 如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”或地址； 如果查遍整个链表都没有找到其值和e相等的元素，则返回0或“NULL”。 丽水学院工学院

【算法描述】 //在线性表L中查找值为e的数据元素 int LocateELem_L (LinkList L，Elemtype e) { p=L->next; j=1; while(p &&p->data!=e) {p=p->next; j++;} if(p) return j; else return 0; } 丽水学院工学院

【算法描述】 //在线性表L中查找值为e的数据元素 LNode *LocateELem_L (LinkList L，Elemtype e) { //返回L中值为e的数据元素的地址，查找失败返回NULL p=L->next; while(p &&p->data!=e) p=p->next; return p; } 丽水学院工学院

s->next=p->next; p->next=s 3. 插入（插在第 i 个结点之前） 将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间 s->next=p->next; p->next=s 思考：步骤1和2能互换么？ 丽水学院工学院

【算法步骤】 （1）找到ai-1存储位置p （2）生成一个新结点*s （3）将新结点*s的数据域置为x （4）新结点*s的指针域指向结点ai 04:18 丽水学院工学院

【算法描述】 //在L中第i个元素之前插入数据元素e 丽水学院工学院 Status ListInsert_L(LinkList &L,int i,ElemType e){ p=L;j=0; while(p&&j<i−1){p=p->next;++j;} //寻找第i−1个结点 if(!p||j>i−1)return ERROR; //i>n+1或i<1 s=new LNode; //生成新结点s s->data=e; //将结点s的数据域置为e s->next=p->next; //将结点s插入L中 p->next=s; return OK; }//ListInsert_L 丽水学院工学院

（3）令p-＞next指向ai的直接后继结点 （4）释放结点ai的空间 步骤： （1）找到ai-1存储位置p （2）保存要删除的结点的值 （3）令p-＞next指向ai的直接后继结点 （4）释放结点ai的空间 丽水学院工学院

p->next = q->next ??? 5. 删除（删除第 i 个结点）  ai-1  ai ai+1 删除前  ai-1 ai ai+1  p q 删除后 p->next = q->next ??? 丽水学院工学院

【算法步骤】 （1）找到ai-1存储位置p （2）临时保存结点ai的地址在q中，以备释放 （3）令p->next指向ai的直接后继结点 （4）将ai的值保留在e中 （5）释放ai的空间

【算法描述】 //将线性表L中第i个数据元素删除 Status ListDelete_L(LinkList &L,int i,ElemType &e){ p=L;j=0; while(p->next &&j<i-1){//寻找第i个结点，并令p指向其前驱 p=p->next; ++j; } if(!(p->next)||j>i-1) return ERROR; //i>n或i<1删除,位置不合理 q=p->next; //临时保存被删结点的地址以备释放 p->next=q->next; //改变删除结点前驱结点的指针域 e=q->data; //保存删除结点的数据域 delete q; //释放删除结点的空间 return OK; }//ListDelete_L

链表的运算时间效率分析 1. 查找: 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。 丽水学院工学院

单链表的建立（前插法） 从一个空表开始，重复读入数据： 生成新结点 将读入数据存放到新结点的数据域中 将该新结点插入到链表的前端 丽水学院工学院

p->data=an p->data=an-1 单链表的建立（前插法） p->next= L->next L->next=p p->next= L->next p->data=an p->data=an-1 丽水学院工学院

【算法描述】 void CreateList_F(LinkList &L,int n){ L=new LNode; L->next=NULL; //先建立一个带头结点的单链表 for(i=n;i>0;--i){ p=new LNode; //生成新结点 cin>>p->data; //输入元素值 p->next=L->next;L->next=p; //插入到表头 } }//CreateList_F 丽水学院工学院

单链表的建立（尾插法） 丽水学院工学院 从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。 初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。 丽水学院工学院

【算法描述】 丽水学院工学院 void CreateList_L(LinkList &L,int n){ //正位序输入n个元素的值，建立带表头结点的单链表L L=new LNode; L->next=NULL; r=L; //尾指针r指向头结点 for(i=0;i<n;++i){ p=new LNode; 　 //生成新结点 cin>>p->data; //输入元素值 p->next=NULL; r->next=p; //插入到表尾 r=p; //r指向新的尾结点 } }//CreateList_L 丽水学院工学院

2.6 顺序表和链表的比较 存储结构 比较项目 顺序表 链表 空间 存储空间 预先分配，会导致空间闲置 或溢出现象 预先分配，会导致空间闲置 或溢出现象 动态分配，不会出现存储 空间闲置或溢出现象 存储密度 不用为表示结点间的逻辑关 系而增加额外的存储开销， 存储密度等于1 需要借助指针来体现元素 间的逻辑关系，存储密度 小于1 时间 存取元素 随机存取，按位置访问元素 的时间复杂度为O(1) 顺序存取，按位置访问元 素时间复杂度为O(n) 插入、删除 平均移动约表中一半元素， 时间复杂度为O(n) 不需移动元素，确定插入、 删除位置后，时间复杂度 为O(1) 适用情况 ① 表长变化不大，且能事先 确定变化的范围 ② 很少进行插入或删除操作， 经常按元素位置序号访问数 据元素 ① 长度变化较大 ② 频繁进行插入或删除操 作

2.7 线性表的应用 线性表的合并 有序表的合并 1 2 丽水学院工学院

2.7.1 线性表的合并 问题描述： 假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合 A=AB 2.7.1 　线性表的合并 问题描述： 假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合 A=AB La=(7, 5, 3, 11) Lb=(2, 6, 3) La=(7, 5, 3, 11, 2, 6) . 丽水学院工学院

【算法步骤】 依次取出Lb 中的每个元素，执行以下操作： 　在La中查找该元素 　如果找不到，则将其插入La的最后 丽水学院工学院

【算法描述】 void union(List &La, List Lb){ //求线性表的长度 La_len=ListLength(La); Lb_len=ListLength(Lb); //依次取LB中第i个数据元素赋给e for(i=1;i<=Lb_len;i++){ GetElem(Lb,i,e); //如果LA中不存在和e相同的数据元素，则插入之 if(!LocateElem(La,e)) ListInsert(&La,++La_len,e); }} 丽水学院工学院

【算法描述】 void union(List &La, List Lb){ //求线性表的长度…… //依次取LB中第i个数据元素赋给e for(i=1;i<=Lb_len;i++){ GetElem(Lb,i,e); //如果LA中不存在和e相同的数据元素，则插入之 if(!LocateElem(La,e)) ……} } 丽水学院工学院

2.7.2 　有序表的合并 问题描述： 已知线性表La和Lb中的数据元素按值非递减有序排列,现要求将La和Lb归并为一个新的线性表Lc,且Lc中的数据元素仍按值非递减有序排列。 La=(1 ,7, 8) Lb=(2, 4, 6, 8, 10, 11) Lc=(1, 2, 4, 6, 7 , 8, 8, 10, 11) . 丽水学院工学院

【算法步骤】－有序的顺序表合并 (1) 创建一个空表Lc； (2) 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止； (3) 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的最后。 丽水学院工学院

【算法描述】－有序的顺序表合并 丽水学院工学院 void MergeList_Sq(SqList LA,SqList LB,SqList &LC){ //指针pa和pb的初值分别指向两个表的第一个元素 pa=LA.elem; pb=LB.elem; //新表长度为待合并两表的长度之和 LC.length=LA.length+LB.length; //为合并后的新表分配一个数组空间 LC.elem=new ElemType[LC.length]; //指针pc指向新表的第一个元素 pc=LC.elem; //指针pa_last指向LA表的最后一个元素 pa_last=LA.elem+LA.length-1; //指针pb_last指向LB表的最后一个元素 pb_last=LB.elem+LB.length-1; 丽水学院工学院

【算法描述】－有序的顺序表合并 T(n)= 丽水学院工学院 S(n)= O(n) //两个表都非空 while(pa<=pa_last && pb<=pb_last) //依次“摘取”两表中值较小的结点 { if(*pa<=*pb) *pc++=*pa++; else *pc++=*pb++; } //LB表已到达表尾 while(pa<=pa_last) *pc++=*pa++; //LA表已到达表尾 while(pb<=pb_last) *pc++=*pb++; }//MergeList_Sq T(n)= S(n)= O(n) 丽水学院工学院

要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。 有序链表合并－－重点掌握 将两个有序链表合并成一个有序的单链表。 要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。 表中允许有重复的数据。 丽水学院工学院

有序链表合并－－重点掌握 La Lb La 合并后 丽水学院工学院 1 7 8 2 4 6 8 10 11 1 2 4 6 7 8 10

【算法步骤】－有序的链表合并 (1)Lc指向La (2) 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的最后，直至其中一个表变空为止 (3) 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的最后 (4) 释放 Lb 表的表头结点 丽水学院工学院

有序链表合并（初始化） La 1 7 8 Lc = pc pa Lb 2 4 6 8 10 11 pb 丽水学院工学院

有序链表合并( pa->data < ＝pb->data ) La(Lc ,pc) 1 7 8 pa Lb 2 4 6 8 10 11 pb pc->next = pa; 丽水学院工学院

有序链表合并( pa->data < ＝pb->data ) La(Lc) 1 1 7 8 pc Pa Lb 2 4 6 8 10 11 pb pc->next = pa; pc= pa; 丽水学院工学院

有序链表合并( pa->data < ＝pb->data ) La(Lc) 1 1 7 8 pc pa = pa->next; pa Lb 2 4 6 8 10 11 pb pc->next = pa; pc= pa; 丽水学院工学院

有序链表合并( pa->data >pb->data ) La(Lc) 1 1 7 8 pc pa Lb 2 4 6 8 10 11 pb pc->next = pb; 丽水学院工学院

有序链表合并( pa->data >pb->data ) La(Lc) 1 1 7 8 pa Lb 2 2 4 6 8 10 11 pc pc= pb; pb pc->next = pb; 丽水学院工学院

有序链表合并( pa->data >pb->data ) La(Lc) 1 1 7 8 pa Lb 2 2 4 6 8 10 11 pc pc= pb; pb =pb->next; pb pc->next = pb; 丽水学院工学院

pc-> next=pa?pa:pb; 有序链表合并 La(Lc) 1 7 8 pa(NULL) 2 4 6 8 10 11 pc pb pc-> next=pa?pa:pb; 丽水学院工学院

有序链表合并 合并后 La(Lc) 1 7 8 delete Lb; 2 4 6 8 10 11 丽水学院工学院

【算法描述】－有序的链表合并 丽水学院工学院 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) { //pa和pb的初值分别指向两个表的第一个结点 pa=La->next; pb=Lb->next; //用LA的头结点作为LC的头结点 LC = LA; //pc的初值指向LC的头结点 pc = LC; …… 丽水学院工学院

【算法描述】－有序的链表合并 丽水学院工学院 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ …… //两个表都非空 while(pa && pb){ //依次"摘取"两表中值较小的结点插入到LC表的最后 if(pa->data<=pb->data) {//将pa所指结点链接到pc所指结点之后 pc->next=pa;pc=pa;pa=pa->next;} //将pb所指结点链接到pc所指结点之后 else{pc->next=pb; pc=pb; pb=pb->next;} 丽水学院工学院

【算法描述】－有序的链表合并 丽水学院工学院 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ …… //插入剩余段 pc->next=pa?pa:pb; //释放Lb的头结点 delete Lb; } T(n)= S(n)= O(1) 丽水学院工学院

思考1：要求合并后的表无重复数据，如何实现？ La(Lc) 1 7 8 2 4 6 8 10 11 提示：要单独考虑 pa->data = =pb->data 丽水学院工学院

2.8 案例分析与实现 案例2.1 ：一元多项式的运算 P(x) = 10 + 5x - 4x2 + 3x3 + 2x4 10 5 -4 数组表示 （每一项的指数i隐含在其系数pi的序号中） P(x) = 10 + 5x - 4x2 + 3x3 + 2x4 指数 （下标i） 1 2 3 4 系数p[i] 10 5 -4 Rn(x) = Pn(x) + Qm(x) 线性表R = (p0 + q0,p1 + q1,p2 + q2,…,pm + qm,pm+1,…,pn) 丽水学院工学院

线性表P =((p1, e1), (p2, e2),…,(pm, em)) 案例2.2 ：稀疏多项式的运算 多项式非零项的数组表示 （a）A(x) = 7 + 3x + 9x8 + 5x17 （b）B(x) = 8x + 22x7 − 9x8 下标i 1 2 3 系数a[i] 7 9 5 系数 b[i] 8 22 -9 指数 17 线性表P =((p1, e1), (p2, e2),…,(pm, em)) 创建一个新数组c 分别从头遍历比较a和b的每一项 指数相同，对应系数相加，若其和不为零，则在c中增加一个新项 指数不相同，则将指数较小的项复制到c中 一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可

链式存储结构 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 丽水学院工学院 顺序存储结构存在问题 存储空间分配不灵活 运算的空间复杂度高 链式存储结构 typedef struct PNode { float coef;//系数 int expn; //指数 struct PNode *next; //指针域 }PNode,*Polynomial;   A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 -1 7 3 1 9 8 5 17 22 -9 A B 丽水学院工学院

多项式创建---【算法步骤】 丽水学院工学院 ① 创建一个只有头结点的空链表。 ② 根据多项式的项的个数n，循环n次执行以下操作： 生成一个新结点*s； 输入多项式当前项的系数和指数赋给新结点*s的数据域； 设置一前驱指针pre，用于指向待找到的第一个大于输入项指数的结点的前驱，pre初值指向头结点； 指针q初始化，指向首元结点； 循链向下逐个比较链表中当前结点与输入项指数，找到第一个大于输入项指数的结点*q； 将输入项结点*s插入到结点*q之前。 丽水学院工学院

多项式创建---【算法描述】 丽水学院工学院 void CreatePolyn(Polynomial &P,int n) {//输入m项的系数和指数，建立表示多项式的有序链表P //先建立一个带头结点的单链表 P=new PNode; P->next=NULL; //依次输入n个非零项 for(i=1;i<=n;++i){ //生成新结点 s=new PNode; //输入系数和指数 cin>>s->coef>>s->expn; //pre用于保存q的前驱，初值为头结点 pre=P; //q初始化，指向首元结点 q=P->next; } 丽水学院工学院

多项式创建---【算法描述】 丽水学院工学院 void CreatePolyn(Polynomial &P,int n) { //输入m项的系数和指数，建立表示多项式的有序链表P …… //找到第一个大于输入项指数的项*q while(q&&q->expn<s->expn) { pre=q; q=q->next; } //while //将输入项s插入到q和其前驱结点pre之间 s->next=q; pre->next=s; } //for } 丽水学院工学院

A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 丽水学院工学院 pa pb -1 7 3 1 9 8 5 17 3 1 9 8 5 17 22 -9 A B pa pb 丽水学院工学院

多项式相加 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 丽水学院工学院 pa pb A -1 7 3 1 3 1 9 8 5 17 B -1 8 1 22 7 -9 8 pb 丽水学院工学院

多项式相加 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 丽水学院工学院 pa pb A -1 7 11 1 11 1 9 8 5 17 B -1 8 1 22 7 -9 8 pb 丽水学院工学院

多项式相加 A17(x)=7+3x+9x8+5x17 B8(x)=8x+22x7-9x8 丽水学院工学院 pa pb A -1 7 11 1 11 1 9 8 5 17 B -1 8 1 22 7 -9 8 pb 丽水学院工学院

A17(x) = 7 + 3x + 9x8 + 5x17 B8(x) = 8x + 22x7 − 9x8 丽水学院工学院

多项式相加---【算法步骤】 丽水学院工学院 ① 指针p1和p2初始化，分别指向Pa和Pb的首元结点。 ③ 当指针p1和p2均未到达相应表尾时，则循环比较p1和p2所指结点对应的指数值（p1->expn与p2->expn），有下列3种情况： 当p1->expn等于p2->expn时，则将两个结点中的系数相加，若和不为零，则修改p1所指结点的系数值，同时删除p2所指结点，若和为零，则删除p1和p2所指结点； 当p1->expn小于p2->expn时，则应摘取p1所指结点插入到“和多项式”链表中去； 当p1->expn大于p2->expn时，则应摘取p2所指结点插入到“和多项式”链表中去。 ④ 将非空多项式的剩余段插入到p3所指结点之后。 ⑤ 释放Pb的头结点。 丽水学院工学院

小结 问1：线性表的逻辑结构特点是什么？其顺序存储结构和链式存储结构的特点是什么？ 答： 线性表逻辑结构特点是，只有一个首结点和尾结点；除首尾结点外其他结点只有一个直接前驱和一个直接后继。简言之，线性结构反映结点间的逻辑关系是一对一（1:1）的。 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。 链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。

小结 问2：顺序存储和链式存储各有哪些优缺点？ 答： 顺序存储的优点是存储密度大(＝1)，存储空间利用率高。缺点是插入或删除元素时不方便。 链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小（<1），存储空间利用率低。 事实上，链表插入、删除运算的快捷是以空间代价来换取时间。

问3：在什么情况下用顺序表比链表好？ 答： 顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表； 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。