o void mergelist(list La, list Lb, list &Lc) initList(Lc); i=j=1; k=0 La-len=listlength (La); Lb-len=listlength (Lb); whle(i<=Laen)&&(j<=Lb-len)La和Lb均非空 GetElem (La,i, ai); GetElem(Lb,j, b) if(ai<=bj[Listlnsert(LC, ++k, ai); ++1; 3 else ListInsert(LC,++k, bj); ++j:31 while(i<=La-Ien) GetElem((La, i++, ai); ListInsert(LC, ++k, ai)] while(<=Lb-len)t GetElem((Lb,j++, bj); ListInsert(LC, ++k, b]; /MergeList 北京邮电大学自动化学院 11
北京邮电大学自动化学院 11 ⚫ void mergelist(list La，list Lb，list &Lc) ⚫ InitList(Lc)；i=j=1; k=0; ⚫ La-len=listlength(La); Lb-len=listlength(Lb); ⚫ while((i<=La-len) && (j<=Lb-len)) {//La和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){ ⚫ GetElem((La,i++,ai); ListInsert(Lc,++k,ai); } ⚫ while(j<=Lb-len){ ⚫ GetElem((Lb,j++,bj);ListInsert(Lc,++k, bj); }}//MergeList
4、算法的存储空间需求 ●上述两个算法的时间复杂度取决于抽象数据类型ist定义中基本 操作的执行时间。假如 Getelem和 Listlnser这两个操作的执行 寸间和表长无关, LocateElen的执行时间和表长成正比。 ●则算法21的时间复杂度为 .o(ListLength (LAx listlength (LB), ●算法22的时间复杂度则为 .o(List Length (LA)+ListLength (LB ●虽然算法22中含有三个( While)循环语句,但只有当ij均指 向表中实际存在的数据元素时,才能取得数据元素的值并进行相 互比较;并且当其中一个线性表的数据元素均已插入到线性表 Lc中后,只要将另外一个线性表中的剩余元素依次插入即可。 北京邮电大学自动化学院
北京邮电大学自动化学院 12 ⚫ 上述两个算法的时间复杂度取决于抽象数据类型list定义中基本 操作的执行时间。假如GetElem和 ListInsert这两个操作的执行 时间和表长无关，LocateElem的执行时间和表长成正比。 4、算法的存储空间需求 ⚫ 则算法2.1的时间复杂度为 ⚫ O（ListLength(LA) ListLength(LB), ⚫ 算法2.2的时间复杂度则为 ⚫ O（List Length(LA)+ListLength(LB)。 ⚫ 虽然算法2.2中含有三个（While）循环语句，但只有当i和j均指 向表中实际存在的数据元素时，才能取得数据元素的值并进行相 互比较；并且当其中一个线性表的数据元素均已插入到线性表 LC中后，只要将另外一个线性表中的剩余元素依次插入即可
22线性表的顺序存储结构 、线性表的顺序表示线性表的顺序表示指的是用一组地址 连续的存储单元依次存储线性表的数据元素。 ●假设线性表的每个元素需占用个存储单元,并以所占的第一个 单元的存储地址作为数据元素的存储位置。则线性表中第i+1个 数据元素的存储位置LOc(a)和第i个数据元素的存储位置 Loc(a1)之间满足下列关系: ●Loc(ap=Loc(a+ 般来说,线性表的第i个数据元素a的存储位置为: Loc(ai=LOC(a1)+(i-1) 若每个数据元素占用m个存储单元,则第个数据元素a的存储位 置为:LOc(a小=LOC(a1)+(i-1)*m 北京邮电大学自动化学院 13
北京邮电大学自动化学院 13 ⚫ 一、 线性表的顺序表示 线性表的顺序表示指的是用一组地址 连续的存储单元依次存储线性表的数据元素。 2.2 线性表的顺序存储结构 ⚫ 假设线性表的每个元素需占用l个存储单元，并以所占的第一个 单元的存储地址作为数据元素的存储位置。则线性表中第i+1个 数据元素的存储位置LOC( a i+1)和第i个数据元素的存储位置 LOC(ai )之间满足下列关系： ⚫ LOC(a i+1)=LOC(ai )+l ⚫ 一般来说，线性表的第i个数据元素ai的存储位置为： ⚫ LOC(ai )=LOC(a1 )+(i-1)*l ⚫ 若每个数据元素占用m个存储单元，则第i个数据元素ai的存储位 置为： LOC(ai )=LOC(a1 )+(i-1)*m
线性表的顺序表示 ●线性表的这种机内表示称作线性表的顺序存储结构,称 这种存储结构的线性表为顺序表。 ●顺序存储的结构特点:以数据元素在计算机“物理位置 相邻”来表示表中数据元素间的逻辑关系。对于这种存 储方式,要访问第i个数据元素,就可以直接计算出a的 存储位置Loc(a)。因而能随机存取表中任一数据元素, 换言之,数据元素在顺序表中的存储位置取决于该数据 元素在线性表中的顺序号。 例如:一个班学生,集体出游,按学号分配房 间 北京邮电大学自动化学院 14
北京邮电大学自动化学院 14 ⚫ 线性表的这种机内表示称作线性表的顺序存储结构，称 这种存储结构的线性表为顺序表。 一、 线性表的顺序表示 ⚫ 顺序存储的结构特点：以数据元素在计算机“物理位置 相邻”来表示表中数据元素间的逻辑关系。对于这种存 储方式，要访问第i个数据元素，就可以直接计算出ai的 存储位置Loc(ai )。因而能随机存取表中任一数据元素， 换言之，数据元素在顺序表中的存储位置取决于该数据 元素在线性表中的顺序号。 ⚫ 例如：一个班学生，集体出游，按学号分配房 间
线性表的顺序表示 ●由于C语言中的一维数组也是采用顺序存储表示,故可以用数组 类型来描述顺序表。又因为除了用数组来存储线性表的元素之 外,顺序表还应该用一个变量来表示线性表的长度属性,所以我 们用结构类型来定义顺序表类型。 ●# define list- NIT-SIZE100线性表初始分配量 # define list| NCREMENT10川线性表分配增量 typedef struct Elemtype *elem∥存储空间基址 int length;当前长度 int Listsize;3 sqlist; 北京邮电大学自动化学院
北京邮电大学自动化学院 15 ⚫ 由于C语言中的一维数组也是采用顺序存储表示，故可以用数组 类型来描述顺序表。又因为除了用数组来存储线性表的元素之 外，顺序表还应该用一个变量来表示线性表的长度属性，所以我 们用结构类型来定义顺序表类型。 一、 线性表的顺序表示 ⚫ # define LIST-INIT-SIZE 100 //线性表初始分配量 ⚫ # define LISTINCREMENT 10 //线性表分配增量 ⚫ typedef struc{ ⚫ Elemtype *elem //存储空间基址 ⚫ int length ;//当前长度 ⚫ int ListSize; } Sqlist;