王玲 wangling@swpu.edu.cn 第 2 章 线性表 王玲 wangling@swpu.edu.cn 2019/2/25

数据结构课程的起点： 什么是 线性结构？ 2

CH2 线性表 2.1 线性表的逻辑结构 2.2 线性表的顺序存储及运算实现 2.3 线性表的链式存储和运算实现 2.1 线性表的逻辑结构 2.2 线性表的顺序存储及运算实现 2.3 线性表的链式存储和运算实现 2.4 线性表的两种存储结构的比较 2.5 线性表的应用举例

教学目标 线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。 掌握顺序表的含义及特点，顺序表上的插入、删除操作是及其平均时间性能分析，解决简单应用问题。 掌握链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。 领会顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。

教学重点与难点 教学方法 本章的重点是掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析； 难点是使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。 教学方法 课堂讲授 提问互动 实验

2.1 线性表的逻辑结构 线性表 n (≥0) 个数据元素的有限序列 定义： 数据元素 数据元素 例1 英文字母表（A , B , C , ….. Z) 数据元素 数据元素 例2 2019/2/25

线性表 2.1 线性表的逻辑结构 特点： 分类： 元素性质相同 存在唯一的一个首元素：“第一个”数据元素 存在唯一的一个末元素：“最后一个”数据元素 除首元素外，每个数据元素都有且只有一个前驱 除末元素外，每个数据元素都有且只有一个后继 有序表：元素按某个数据项的升序或降序排列 无序表：元素排列位置与元素内容无关 分类： 2019/2/25

线性表 2.1 线性表的逻辑结构 常用术语： 表长度：元素的个数，记为 n 直接前驱：ai 的直接前驱是 ai-1， a1无直接前驱 直接后继：ai 的直接后继是 ai+1， an无直接后继 前驱： ai 的前驱是 a1, …, ai-1， a1 无前驱 后继： ai 的后继是 ai+1 , …, an， an 无后继 2019/2/25

线性表的抽象数据类型定义 ADT List{ 数据对象：D={ai|ai∈ElemSet;1≤i≤n,n≥0;} 数据关系：R={<ai,ai+1>| ai, ai+1∈D,i=1,2,……,n-1} 基本操作： InitList(&L) ListLength(L) GetElem(L,i,&e) PriorElem(L,cur_e,&pre_e) NextElem(L,cur_e,&next_e) LocateElem(L,e,compare()) ListInsert(&L,i,e) ListDelete(&L,i,&e) }ADT List

2.2 线性表的物理结构 1：顺序存储结构 一、特点 a1 a2 …… ai ai+1 an 用一组地址连续的存储单元依次存放线性表中的元素；假设线性表的每个元素需占用L个存储单元，且基地址为LOC(a1)。 以元素在机内的“物理位置相邻”来表示数据之间的逻辑关系: LOC(ai+1)＝ LOC(ai )＋L 是一种随机存取的存储结构; LOC(ai)＝LOC(a1)＋(i－1)*L 实现：一维数组；插入／删除时需移动大量元素。 LOC(a1) a1 a2 …… ai ai+1 an LOC(ai) LOC(ai+1) 顺序表的特点是，逻辑关系上相邻的两个元素在物理位置上也相邻。这一特点使得顺序表有如下两个优点： 无需为表示数据元素之间的关系而额外增加存储空间； 可以随机存取表中任一数据元素，元素存储位置可以用一个简单、直观的公式表示。 这一特点也造成了这种存储结构的两个缺点： 插入和删除运算必须移动大量（几乎一半）数据元素，效率较低； 必须预先分配存储空间，造成空间利用率低，且表的容量难以扩充

LOC(ai) = LOC(a1) + L *（i-1） 例： 设有一维数组Ｍ，下标的范围是0到9，每个数组元素用相邻的5个字节存储。存储器按字节编址，设存储数组元素Ｍ[0]的第一个字节的地址是98，则Ｍ[3]的第一个字节的地址是多少？ 113 解：已知地址计算通式为： LOC(ai) = LOC(a1) + L *（i-1） 但此题要注意下标起点略有不同： LOC( M[3] ) = 98 + 5 ×(3-0) =113 11

顺序表的存储结构示意图 elem[0]=a1 elem[1]=a2 数据空间 存储空间 elem[n-1] = an length 1 n-1 下标 数组 1 2 length 位序 elem elem[0]=a1 elem[1]=a2 elem[n-1] = an 数据空间 存储空间 空闲 表长度＝元素个数 listsize - 1 存储容量＝数组大小 2019/2/25

顺序表的编程模型 1. 定义元素类型 2. 定义顺序表类型 3. 声明顺序表变量 4. 初始化存储空间 5. 操纵表元素：插入、删除、查找、读取、写入 6. 释放存储空间 2019/2/25

顺序表的编程模型 typedef int ElemType; 1. 定义元素类型：元素可以是简单类型的数据 2. 定义顺序表类型 3. 声明顺序表变量 4. 初始化存储空间 5. 操纵表元素：插入、删除、查找、读取、写入 6. 释放存储空间 typedef int ElemType; 2019/2/25

顺序表的编程模型 typedef struct studenthealth { char sno[20]; char sname[20]; 1. 定义元素类型：元素也可以是复合类型的数据 2. 定义顺序表类型 3. 声明顺序表变量 4. 初始化存储空间 5. 操纵表元素：插入、删除、查找、读取、写入 6. 释放存储空间 typedef struct studenthealth { char sno[20]; char sname[20]; char sex[2]; int age; char class[50]; char health[30]; } ElemType; 2019/2/25

顺序表的编程模型 typedef struct { ElemType *elem; //元素数组 int length; //表长度 1. 定义元素类型 2. 定义顺序表类型：存储元素的数组+表长度+存储容量 3. 声明顺序表变量 4. 初始化存储空间 5. 操纵表元素：插入、删除、查找、读取、写入 6. 释放存储空间 typedef struct { ElemType *elem; //元素数组 int length; //表长度 int listsize; //存储容量 } SqList; 2019/2/25

顺序表的编程模型 SqList L; 1. 定义元素类型 2. 定义顺序表类型 3. 声明顺序表变量：注意！此时的 L.elem＝NULL 4. 初始化存储空间 5. 操纵表元素：插入、删除、查找、读取、写入 6. 释放存储空间 SqList L; 2019/2/25

顺序表的编程模型 L.elem = (ElemType*) malloc ( LIST_INIT_SIZE * sizeof (ElemType) ) ; 1. 定义元素类型 2. 定义顺序表类型 3. 声明顺序表变量 4. 初始化存储空间：为数组分配内存空间 5. 操纵表元素：插入、删除、查找、读取、写入 6. 释放存储空间 2019/2/25

顺序表的编程模型 具体细节后面再说 1. 定义元素类型 2. 定义顺序表类型 3. 声明顺序表变量 4. 初始化存储空间 5. 操纵表元素：插入、删除、查找、读取、写入 6. 释放存储空间 具体细节后面再说 2019/2/25

顺序表的编程模型 free ( L.elem ) ; //释放数组空间 L.elem = NULL ; //清空指针内容 1. 定义元素类型 2. 定义顺序表类型 3. 声明顺序表变量 4. 初始化存储空间 5. 操纵表元素：插入、删除、查找、读取、写入 6. 释放存储空间：将数组占用的内容空间还给操作系统 free ( L.elem ) ; //释放数组空间 L.elem = NULL ; //清空指针内容 2019/2/25

2.2 线性表的顺序存储结构 二、描述方式（动态分配方式） #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 typedef struct { ElemType *elem； //存储空间基址，体现动态性 int length; //当前表的长度 int listsize; //当前分配的存储容量 }SqList; 注意：存储容量以sizeof(ElemType)为基本单位

比较：静态分配方式：需要申请非常大的空间，适应度比较差 #define MAXSIZE 1024 typedef int ElemType; Typedef struct { ElemType elem[MAXSIZE]; int length; // 顺序表当前长度 } SqList;

2.2 线性表的顺序存储结构 三、基本操作的算法描述 初始化顺序表 （算法 2.3） 插入元素 （算法 2.4） 删除元素 （算法 2.5） 初始化顺序表 （算法 2.3） 插入元素 （算法 2.4） 删除元素 （算法 2.5） 元素的查找 （算法 2.6） 顺序表的合并 （算法 2.7）

算法2.3 （初始化顺序表） Status InitList_Sq(SqList &L){ L.elem=(ElemType*) malloc(LIST_INIT_SIZE*sizeof(ElemType)); if (!L.elem) exit （OVERFLOW）; L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }//InitList_Sq 注：动态分配函数 #include <stdlib.h> void *malloc(unsigned size) void *realloc(void *p,unsigned size) void free (void *p) char sizeof(数据类型名)

2.2 线性表的顺序存储结构 三、基本操作的算法描述 初始化顺序表 （算法 2.3） 插入元素 （算法 2.4） 删除元素 （算法 2.5） 初始化顺序表 （算法 2.3） 插入元素 （算法 2.4） 删除元素 （算法 2.5） 元素的查找 （算法 2.6） 顺序表的合并 （算法 2.7）

( SqList &L, int i, ElemType e) 插入算法的输入与输出： ( SqList &L, int i, ElemType e) 插入算法的思想： （1）检查参数i 1 =< i <= L.length + 1 （2）测试当前存储容量 若 L.length >= L.listsize, 则申请再分配空间； （3）将第i个至第n个元素后移 （4）插入新元素，并将表长加1

L.elem 1 i-1 i 下标 a1 a2 ai ai+1 an a1 a2 ai an-1 an e

算法2.4 ：顺序表中插入一个元素 for (j=L.length-1;j>=i-1;j--) Status ListInsert_Sq(SqList &L,int i,ElemType e){ if (i<1||i>L.length+1) return ERROR; if (L.length>=L.listsize){ newbase=(ElemType *) realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit (OVERFLOW); L.elem=newbase;L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]); for (p=&(L.elem[L.length-1]);p>=q;- -p)) *(p+1)=*p; *q=e; ++L.length; return OK; }//ListInsert_Sq for (j=L.length-1;j>=i-1;j--) L.elem[j+1]=L.elem[j]; L.elem[i-1]=e;

注意：顺序表内指定位置插入新元素的实现方式： for ( j = L.length-1; j>=i-1; j--) L.elem[ j+1 ]=L.elem[ j ]; // 元素 j 后移 L.elem[ i - 1 ]=e; // 插入 e 1、纯数组方式(简洁、易懂) *q=L.elem + i - 1; // q为插入位置 for ( p = L.elem + L.length - 1; p >= q; --p ) *(p+1)=*p; // 指针 p 指 向元素后移 *q=e; // 插入e 2、纯指针方式 2019/2/25

注意：顺序表内指定位置插入新元素的实现方式： 3、数组与指针混用方式(教材采用，但不适用于纯 C 环境) q = &( L.elem[i-1] ); //指针 q 指向插入位置 for ( p = &(L.elem[L.length-1] ; p>=q ; --p ) *(p+1)=*p; // 指针 p 指向元素后移 *q=e; // 插入 e 4、数组与指针混用方式(纯 C 环境)，实验中采用 for ( j = L->length - 1; j >= i - 1; j-- ) L->elem[j+1]=L->elem[j]; // 元素后移 L->elem[i-1]=e; // 插入e 顺序表采用指针变量（SqList *L），元素用数组下标访问 2019/2/25

插入算法的时间复杂度分析 故时间复杂度为O(n)。 插入算法花费的时间，主要在于循环中元素的向后移动上面，而元素的移动次数与插入的位置i有关： (设L.length=n) 当i=1时，全部元素都得移动，需n次移动， 当i=n+1时，不需移动元素， 一般地：在i位置插入时移动次数ci为n-i+1， 假设在每个位置插入的概率为pi （不妨设为等概率） ，则平均移动元素的次数为： （其它语句花费的时间可以省去），即从插入位置到最后位置的所有元素都要后移一位，使空出的位置插入元素值x。 故时间复杂度为O(n)。

2.2 线性表的顺序存储结构 三、基本操作的算法描述 初始化顺序表 （算法 2.3） 插入元素 （算法 2.4） 删除元素 （算法 2.5） 初始化顺序表 （算法 2.3） 插入元素 （算法 2.4） 删除元素 （算法 2.5） 元素的查找 （算法 2.6） 顺序表的合并 （算法 2.7）

删除算法的输入与输出： ( SqList &L, int i, Elemtype &e) 删除算法的思想： （1）检查参数i 1 =< i <= L.length （2）将第i+1个至第n个元素前移 （3）将表长减1

算法2.5 顺序表中删除元素 Status ListDelete_Sq(Sqlist &L,int i,ElemType & e){ 算法2.5 顺序表中删除元素 Status ListDelete_Sq(Sqlist &L,int i,ElemType & e){ if ((i<1)||(i>L.length)) return ERROR; p=&(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for (++p;p<=q;++p) *(p-1)=*p; - -L.length; return OK; }//ListDelete_Sq e=L.elem[i-1]; For (j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j]； ：边界条件 元素移动方向 时间复杂度分析

删除算法的时间复杂度分析 删除算法花费的时间，主要在于循环中元素的前移上，而元素的移动次数与删除的位置i有关： (设L.length=n) 当i=1时，其后的全部元素都得移动，需n-1次移动， 当i=n时，不需移动元素， 一般地：在i位置删除元素时的移动次数ci为n-i 假设在每个位置删除的概率为pi （不妨设为等概率） ，则平均移动元素的次数为： 故时间复杂度为O(n)。

2.2 线性表的顺序存储结构 三、基本操作的算法描述 初始化顺序表 （算法 2.3） 插入元素 （算法 2.4） 删除元素 （算法 2.5） 初始化顺序表 （算法 2.3） 插入元素 （算法 2.4） 删除元素 （算法 2.5） 元素的查找 （算法 2.6） 顺序表的合并 （算法 2.7）

算法2.6-1 顺序表中元素的查找 int LocateElem_Sq(Sqlist L, ElemType e){ i=0; 算法2.6-1 顺序表中元素的查找 int LocateElem_Sq(Sqlist L, ElemType e){ i=0; while (i<L.length && L.elem[i]!=e) ++i; if (i<L.length) return i+1; else return 0; }//LocateElem_Sq 注意：查找过程也可以借助指针实现。 设L.length=n，

2.2 线性表的顺序存储结构 三、基本操作的算法描述 初始化顺序表 （算法 2.3） 插入元素 （算法 2.4） 删除元素 （算法 2.5） 初始化顺序表 （算法 2.3） 插入元素 （算法 2.4） 删除元素 （算法 2.5） 元素的查找 （算法 2.6） 顺序表的合并 （算法 2.7）

已知两个线性表LA和LB中的元素按值非递减有序排列，现将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍然按值非递减有序排列。 基本步骤： 1．分别从LA和LB中取得当前元素ai和bj； 2．若ai≤bj，则将ai插入到LC中，否则将bj插入到LC中; 重复第1、2步直到有一个表的元素取完为止; 4. 将没有处理完的表中所剩元素，复制到LC中。 LA =（3, 5 ,8, 11） LB =（2, 6, 8, 9, 11, 15 , 20 ） LC =（2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20） i i j j 第4步建议在编写代码的时候提出 2 3

O(ListLength(La)+ ListLength(Lb)) 该算法的时间复杂度为： O(ListLength(La)+ ListLength(Lb)) void MergeList(List La, List Lb, List & Lc) { InitList(Lc); //初始化Lc i=j=1; k=0; La_len=ListLength(La); //求La的长度 Lb_len= ListLength(Lb); //求Lb的长度 while(i<=La_len)&&(j<=Lb_len)) { { GetElem(La,i,ai); GetElem(Lb,j,bj); if(ai<=bj) { ListInsert(Lc,++k,ai); ++i; } else { ListInsert(Lc,++k, bj); ++j; } } } while(i<=La_len) { GetElem(La,i++,ai); ListInsert(Lc,++k,ai); } while(j<=Lb_len) { GetElem(La,j++,bj); ListInsert(Lc,++k,bj); }

算法2.7 顺序表的合并 void MergeList_Sq(Sqlist La, Sqlist Lb, Sqlist &Lc){ 算法2.7 顺序表的合并 void MergeList_Sq(Sqlist La, Sqlist Lb, Sqlist &Lc){ //非递减排列的有序线性表的合并 pa=La.elem; pb=Lb.elem; Lc.ListSize=Lc.length=La.length+Lb.length; pc=Lc.elem= (ElemType*) malloc(Lc.ListSize*sizeof(ElemType)); if (!pc) exit(OVERFLOW); pa_last=pa+La.length-1; pb_last=pb+Lb.length-1; while ((pa<=pa_last) &&(pb<=pb_last) if (*pa<=*pb) *pc++=*pa++; else *pc++=*pb++; while (pa<=pa_last) *pc++=*pa++; while (pb<=pb_last) *pc++=*pb++; }

练习 顺序表逆置：将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法(函数)如下： void ReverseList( Sqlist *L) { Elemtype t ; //设置临时空间用于存放data int i; for ( i=0 ; i < L->length/2 ; i++) { t = L->data[i]; //交换数据 L -> data[ i ] = L -> data[ L -> length - 1 - i ] ; L -> data[ L -> length - 1 - i ] = t ; }

顺序表在数据存储、基本操作上的特点 顺序表小结 优点 缺点 元素存储关系与逻辑关系一致 随机存取元素 存储空间使用紧凑 物理相邻直接对应逻辑相邻 随机存取元素 可按下标直接访问 存储空间使用紧凑 无需附加信息 缺点 插入、删除操作需要移动大量的元素 后移、前移 预先分配空间需按最大空间分配，空间利用率不高 备用空间经常空闲 表容量难以扩充 成块内存申请 2019/2/25

在顺序表中查找、插入、删除元素时 需要平均比较或移动表的一半元素 元素的平均比较或移动次数 顺序表内查找、插入、删除操作 假定查找、插入、删除某个元素是等概率的 插入元素时平均移动次数 删除元素时平均移动次数 查找元素时平均比较次数 在顺序表中查找、插入、删除元素时 需要平均比较或移动表的一半元素 2019/2/25

作业：设有一个存储整数的顺序表，且每个元素互不相等 设计一个算法把所有奇数移到所有偶数前。 void Move_OddList_Sq(Sqlist &L){ …… } 练习2思路：从左到右找到偶数A.data[i]，从右到左找到奇数A.data[j]，将两者交换；循环该过程直到i大于j。 2019/2/25