数据结构线性表(顺序表)讲解

1、第二章 线性表 顺序表 线性结构四大特点 第一个元素无直接前驱第一个元素无直接前驱 最后一个元素无直接后继最后一个元素无直接后继 除第一个元素外，其他每个数据元素除第一个元素外，其他每个数据元素 都有唯一一个直接前驱都有唯一一个直接前驱 除最后一个元素外，其他每个数据元除最后一个元素外，其他每个数据元 素都有唯一一个直接后面素都有唯一一个直接后面 线性表 定义定义 记法记法 特点特点 结构结构 基本术语基本术语 空表、表长 直接前驱、直接后继 位序 最基本、最常用的线性结构。若最基本、最常用的线性结构。若n(nn(n0) )个个 数据特性相同的数据元素组成的有限序列数据特性相同的数据元素组成的

2、有限序列 。 （a1,a2,ai-1,ai,ai+1,an) 1.同一线性表中的数据元素必须具有相同特性 2.具有线性结构的四大特性 3.数据元素之间存在序偶关系 逻辑结构（1对1）、物理结构（顺序存储和链式存储） 线性表的抽象数据类型 数据对象数据对象 数据关系数据关系 操作集操作集 初始化、销毁、查找、插入、删除、求前驱（后继）、遍历 线性表中的数据元素具有相同特性线性表中的数据元素具有相同特性 相邻数据元素之间存在序偶关系相邻数据元素之间存在序偶关系 线性表的基本操作声明线性表的基本操作声明 仅是模型定义，不涉及模型实现，参数不必考虑具仅是模型定义，不涉及模型实现，参数不必考虑具 体数据

3、类型，实际应用中，具体问题具体分析。体数据类型，实际应用中，具体问题具体分析。 顺序表 定义定义 特点特点 C C描述描述 基本形态基本形态 基本操作实现基本操作实现 用一组地址连续地址连续的存储单元依次存放依次存放线性表中的数 据元素。采用这种存储结构的线性表叫做顺序表顺序表。 a1 a2 ai-1 ai an 基地址基地址 1.数据元素在“逻辑逻辑关系上的相邻相邻”用“物理地址相邻物理地址相邻”来 表示。 2.顺序表中任一元素都可“随机存取随机存取”。 typedef struct SqList; / 俗称 顺序顺序 表表 #define MAXSIZE 100 / 线性表存储空间的分配量

4、，即数组长度 ElemType elemMAXSIZE; int length; / 当前长度 顺序表的C描述 顺序表空：条件顺序表空：条件 L.length=0 不允许删除操作 顺序表满：顺序表满： 条件 L.length=MAXSIZE 不允许插入操作 不空也不满：不空也不满： 可以插入，删除操作 顺序表的基本形态 顺序表- 基本算法 根据顺序表的实现形式，表长根据顺序表的实现形式，表长length是类型定义是类型定义 的属性，可以实现求表长、初始化、取值、判空的属性，可以实现求表长、初始化、取值、判空 等操作，时间复杂度均为等操作，时间复杂度均为O(1)。 而遍历算法、查找表中元素的存在

5、、插入、删除而遍历算法、查找表中元素的存在、插入、删除 等操作，时间复杂度均为等操作，时间复杂度均为O(n)。 （1）初始化 空表 时间复杂为：O(1) 顺序表- 基本算法 L.length=0； （2）判空 时间复杂为：O(1) 顺序表- 基本算法 if(L.length=0) return OK; else return ERROR; （3）求表长 时间复杂为：O(1) 顺序表- 基本算法 return L.length； （4）取元素（取第i个元素e） 时间复杂为：O(1) 顺序表- 基本算法 e=L.elemi-1; i合法 if(i=1 return OK; else return

6、ERROR; 顺序表- 基本算法 （5）遍历 for ( i=1; i=L.length; i+ ) visit( L.elemi-1 ); 时间复杂为：O(L.length) 顺序表- 基本算法 （6）查找 搜索顺序表中是否存在指定 的数据元素。存在，查找成 功；否则，查找失败。 例如：顺序表 23 75 41 38 54 62 17 L.elem0 L.length-1 e =38 i 1 2 3 4 1 8 50 可见，基本操作是： 将顺序表中的元素 逐个和给定值 e 相比较。 算法的算法的时间复杂度时间复杂度为：为： O( L.length ) int LocateElem(SqLis

7、t L,Elemtype e) for(i=1 ;i=L.length;i+) if(e=L.elemi-1) return i; return 0; 顺序表- 基本算法 （7）插入 在顺序表中插入指定的数据元素， 插入成功，表长增1。 线性表操作 ListInsert( j- ) /元素后移 L.elemj = L.elemj-1; L.elemi-1 = e; / 插入e L.length+; / 表长增1 return OK; / 插入成功 else return ERROR; 插入算法时间复杂度分析：插入算法时间复杂度分析： 考虑移动元素的平均情况考虑移动元素的平均情况 插入位置插入位

8、置需要移动的结点次数需要移动的结点次数 1n 2 n-1 n1 n+10 平均次数平均次数: (1+2+n-1+n)/(n+1) =n/2 T(n)=O(n) 顺序表- 基本算法 （8）删除 在顺序表中删除指定位置的数据 元素，删除成功，表长减1。 线性表操作 ListDelete( for ( j=i+1; j=L.length; j+ ) /元素前移 L.elemj-2 = L.elemj-1; L.length-; / 表长减1 return OK; / 删除成功 else return ERROR; 删除算法时间复杂度分析：删除算法时间复杂度分析： 考虑移动元素的平均情况考虑移动元素的

9、平均情况 删除位置删除位置需要移动的结点次数需要移动的结点次数 1n-1 2 n-2 n0 平均次数平均次数: (0+1+n-11)/n =(n-1)/2 T(n)=O(n) 时间复杂度为O(1) 顺序表- 基本算法 （9）求前驱 pre=L.elemi-2; 在顺序表中查找元素cur_e，位序为i i=LocateElem(L,cur_e); cur_e是顺序表中元素，但不是第一个元素 便有直接前驱pre 顺序表- 基本算法 （10）求后继 next=L.elemi; 在顺序表中查找元素cur_e，位序为i i=LocateElem(L,cur_e); cur_e是顺序表中元素，但不是最后一

10、个元 素便有直接后继next 时间复杂度为O(1) 顺序表- 经典算法分析 n n 1 1i i 2 2 1 1n n i i) )( (n n n n 1 1 算法插入删除 基本操作移动元素移动元素 平均移动 次数 时间复杂 度 O(nO(n) )O(nO(n) ) 最好情况在n+1处插入，不需移动删除第n个，不需移动 1 1n n 1 1i i 2 2 n n 1 1) )i i( (n n 1 1n n 1 1 线性表应用举例 例例1 1：合并线性表：合并线性表 例例2 2：归并线性表：归并线性表 例1：合并线性表 假设有两个集合 A 和 B 分别用两个线性 表 LA 和 LB 表示，即

11、：线性表中的数据 元素即为集合中的成员。现要求一个新的 集合AAB。去掉重复元素去掉重复元素 扩大线性表LA，将存在于线性表LB 中而不存在于线性表LA中的数据元 素插入到线性表LA中去。 问题分析问题分析： 1从线性表LB中依次取得每个数据元素; 2依值在线性表LA中进行查访; 3若不存在，则插入之。 GetElem(LB, i)e LocateElem(LA, e, equal( ) ListInsert(LA, n+1, e) 操作步骤：操作步骤： GetElem(Lb, i, e); / 取取Lb中第中第i个数据元素赋给个数据元素赋给e if (!LocateElem(La, e, e

12、qual( ) ) ListInsert(La, +La_len, e); / La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之 void union(List / 求线性表的长度求线性表的长度 Lb_len = ListLength(Lb); for (i = 1; i = Lb_len; i+) / union 算法分析 时间复杂度：时间复杂度： O(O(ListLength(LAListLength(LA) )* *ListLength(LBListLength(LB) ) ) 空间复杂度：空间复杂度： O(O(1 1) ) 例2：归并线性表 已知线性表LA

13、和LB中的数据元素按值非递 减有序排列，现要求将LA和LB归并为一个 新的线性表LC，且LC中的数据元素仍按值 非递减有序排列。 不去掉重复元素不去掉重复元素 LC中的数据元素或是LA中的数据元素，或 是LB中的数据元素。则先设LC为空表，然 后将LA或LB中的元素逐个插入到LC中。为 使LC表按值非递减有序排列，可设两个整 型变量i、j，分别指向LA和LB，比较i、j 所指元素的大小，决定哪个元素插入LC。 插入后，在LA 或LB 中顺序后移。 问题分析问题分析： void MergeList(List La, List Lb, List / 构造空的线性表 Lc i = j = 1; k

14、= 0; La_len = ListLength(La); Lb_len = ListLength(Lb); 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) / 当La不空时 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入插入 La 表中剩余元素表中剩余元素 while (j = Lb_len) / 当Lb不空时 GetElem(Lb

15、, j+, bj); ListInsert(Lc, +k, bj); / 插入插入 Lb 表中剩余元素表中剩余元素 算法分析 时间复杂度：时间复杂度： O(O(ListLength(LA)ListLength(LA)+ +ListLength(LBListLength(LB) ) ) 空间复杂度：空间复杂度： O(O(ListLength(LA)ListLength(LA)+ +ListLength(LBListLength(LB) ) ) void MergeList(SqList La,SqList Lb,SqList pb=Lb.elem; Lc.length =La.length+Lb

16、.length; pc=Lc.elem; pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while(pa=pa_last else *pc+ = *pb+; while(pa=pa_last)*pc+=*pa+; while(pb=pb_last)*pc+=*pb+; if( *pa*pb ) *pc+ =*pa+; else if(*pa=*pb) *pc+=*pa+;pb+; else *pc+ = *pb+; 一元多项式 Pn(x)=p0+p1x+p2x2+p3x3+pnxn Qn(x)=q0+q1x+q2x2+q3x3+