第二章线性表 2.1线性表的类型定义 2.2线性表的顺序存储 2.3线性表的链式存储 2.4一元多项式的表示和相加 3 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 1 中国科学技术大学 第二章 线性表 2.1 线性表的类型定义 2.2线性表的顺序存储 2.3线性表的链式存储 2.4一元多项式的表示和相加
2.1线性表的类型定义 线性表的定义 线性表是n(n>=O)个数据元素的有限序列，表中 各个元素具有相同地属性，表中相邻元素间存 在“序偶”关系。 记做：(a1,a2,…a-1a,a+1…,n-1,an） a.1称为a的直接前驱元素，a+l是a的直接后继 元素 线性表的长度：表中的元素个数n 位序：称元素ai在线性表中的位序 23 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 2 中国科学技术大学 2.1线性表的类型定义 线性表的定义 线性表是n(n>=0)个数据元素的有限序列，表中 各个元素具有相同地属性，表中相邻元素间存 在“序偶”关系。 记做：(a1 ,a2 ,…….ai-1 ,ai ,ai+1 ,…,an-1 ,an ) ai-1称为ai 的直接前驱元素，ai+1是ai的直接后继 元素 线性表的长度：表中的元素个数 n 位序：i称元素ai在线性表中的位序
S 线性表的ADT定义 ADT List{ 数据对象：D={aa∈Elemset,i=l,2..n,n20} 数据关系：R={a.1,a∈D,i-2,.n 基本操作： InitList(&L) DestroyList(&L) ClearList(&L) ListEmpty(L) ListLength(L) GetElem(L,i,&e) 1<=i<=ListLength (L) LocateItem(L,e,compare() PriorElem(L,Cur_e,&pre_e) NextElem(L,cur e,&next_e) ListInsert(&L,i,e)1<=i<=ListLength(L)+1 ListDelete(&L,i,&e)1<=i<=ListLength (L) ListTraverse(L,visitO) ADT List ypb@ustc.edu.cn 3 中国科学技术大学
ypb@ustc.edu.cn 3 中国科学技术大学 ADT List{ 数据对象: D={ai |aiElemset,i=1,2…n, n≥0} 数据关系: R={|ai-1 ,ai D, i=2,…n} 基本操作: InitList(&L) DestroyList(&L) ClearList(&L) ListEmpty(L) ListLength(L) GetElem(L,i,&e) 1<=i<= ListLength (L) LocateItem(L,e,compare()) PriorElem(L,Cur_e,&pre_e) NextElem(L,cur_e,&next_e) ListInsert(&L,i,e) 1<=i<= ListLength (L)+1 ListDelete(&L,i,&e) 1<=i<= ListLength (L) ListTraverse(L,visit()) }ADT List 线性表的ADT定义
【例】对两个线性表La、Lb表示的集合A和B,求一个 新集合A=AUB//算法2.1 a)从Lb中取一个元素（重复直至遍历全部Lb元素） b)在La中查询 c)若La中不存在，则将其插入La 【例】对一个非纯集合B,构造一个纯集合A,使A中只包 涵B中不同值的成员。同上，只是创建La。 【例】判断两个集合是否相等。构造C=A 【例】已知线性表La、Lb中数据元素按值非递减排列， 现要求将La和Lb归并为一新的线性表Lc,且Lc也非 递减排列。//算法2.2 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 4 中国科学技术大学 【例】对两个线性表La、Lb表示的集合A和B，求一个 新集合A＝AUB //算法2.1 a) 从Lb中取一个元素(重复直至遍历全部Lb元素) b) 在La中查询 c) 若La中不存在，则将其插入La 【例】对一个非纯集合B，构造一个纯集合A，使A中只包 涵B中不同值的成员。同上，只是创建La。 【例】判断两个集合是否相等。构造C＝A 【例】已知线性表La、Lb中数据元素按值非递减排列， 现要求将La和Lb归并为一新的线性表Lc,且Lc也非 递减排列。 //算法2.2
S 2.2线性表的顺序表示和实现 顺序表—线性表的顺序存储表示 #define LIST INIT SIZE 100 (C规范) #define LISTINCREMENT 10 Typedef Struct Elemtype elem; int length; int listsize; }SqList; 3 ypb@ustc.edu.cn 5 中国科学技术大学
ypb@ustc.edu.cn 5 中国科学技术大学 2.2线性表的顺序表示和实现 顺序表——线性表的顺序存储表示 #define LIST_INIT_SIZE 100 (C规范) #define LISTINCREMENT 10 Typedef Struct { Elemtype * elem; int length; int listsize; }SqList;
顺序表中基本操作的实现 初始化操作InitList Sq 查找元素操作LocateItem Sq O(n) 插入元素操作ListInsert Sq O(n) 删除元素操作ListDelete_Sq O(n) 归并操作MergeList_Sq O(n+m) 1/算法2.7 对比算法2.22.72.12 插入和删除操作的时间分析： Ein=∑p(n-i+l)=n/2 Edl=p(n-i)=(n-1)/2 23 ypb@ustc.edu.cn 6 中国科学技术大学
ypb@ustc.edu.cn 6 中国科学技术大学 初始化操作 InitList_Sq 查找元素操作 LocateItem_Sq O(n) 插入元素操作 ListInsert_Sq O(n) 删除元素操作 ListDelete_Sq O(n) 归并操作MergeList_Sq O(n+m) //算法2.7 插入和删除操作的时间分析： Ein=Σpi (n-i+1)=n/2 Edl=Σpi (n-i)=(n-1)/2 顺序表中基本操作的实现 对比算法2.2 2.7 2.12
查找元素操作 时间复杂度O(n) 例如：顺序表 L.elem L.listsize 23754138546217 t.ip L.length =7 8 e= 38 返回值=4 e=50 返回值=0 3 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 查找元素操作 时间复杂度O(n) 例如：顺序表 23 75 41 38 54 62 17 L.elem L.length = 7 L.listsize e = 38 p p p p p i 12348 e = 50 p 返回值 = 4 返回值 = 0
插入元素操作 时间复杂度On) (a1,…,a-,a,…,an)改变为 (a1,...,ai1e,ai,an) ,<e,ap aj a2 a-1 a ⑦0 a a ai-1 e a ●● 表的长度增加 ypb@ustc.edu.cn 8 中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学 (a1 , …, ai-1 , ai , …, an ) 改变为 a1 a2 … ai-1 ai … an a1 a2 … ai-1 e ai … an , 表的长度增加 (a1 , …, ai-1 , e, ai , …, an ) 插入元素操作 时间复杂度O(n)
删除元素操作时间复杂度0n)） (a1,,a-1,a,a+1…,an)改变为 (a1,,a-i,a+1,…,an) , <a-1ya+1 a a ai1 ai a+1 a a ●●● ai-lait1…an 表的长度减少 3 ypb@ustc.edu.cn 9 中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 删除元素操作 时间复杂度O(n) (a1 , …, ai-1 , ai , ai+1, …, an ) 改变为 ai+1 … an , 表的长度减少 a1 a2 … ai-1 ai ai+1 … an a1 a2 … ai-1 (a1 , …, ai-1 , ai+1, …, an )
顺序表其它算法举例* >比较两个顺序表的大小（逐个比较元素字符） 时间复杂度OMin(A.length,B.length) >用尽量少得辅助空间将前m个元素和后n个元 素互换 -exchangel时间复杂度.Omxn, -invert时间复杂度：Oi-s+l) -exchange.2时间复杂度：Om+n 注意：代码简洁和效率是两回事 23 ypb@ustc.edu.cn 10 中国科学技术大学
ypb@ustc.edu.cn 10 中国科学技术大学 ➢比较两个顺序表的大小 (逐个比较元素字符) 时间复杂度O(Min(A.length,B.length)) ➢用尽量少得辅助空间将前m个元素和后n个元 素互换 – exchange1 时间复杂度：O(m×n) – invert 时间复杂度：O(t-s+1) – exchange2 时间复杂度：O(m+n) 顺序表其它算法举例* 注意：代码简洁和效率是两回事
