数据结构课件

第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示和信息的处理。而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。

1.1概述例1、书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表例2、人机对奕问题树……..……..…...…...…...…...例3、多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图求解非数值计算的问题：主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？因此，可以认为：

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系（逻辑关系和存储关系）和操作的学科。1.2基本概念和术语数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。数据结构的形式定义为：数据结构是一个二元组。

Data_Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例：复数的数据结构定义如下：

Complex=(C，R)其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。

R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。数据结构的三个方面的含义：1、逻辑结构数据元素间抽象化的相互关系（简称为数据结构）。与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。存储结构（物理结构）数据元素及其关系在计算机存储器中的存储方式。是逻辑结构用计算机语言的实现，它依赖于计算机语言。运算或操作（算法）逻辑结构的划分：集合——

结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构——

结构中的数据元素之间存在一对一的关系。树型结构——

结构中的数据元素之间存在一对多的关系。图状结构或网状结构——

结构中的数据元素之间存在多对多的关系。存储结构：存储结构两方面的内容：数据元素自身值的表示（数据域）该结点与其它结点关系的域（链域或指针域）两种基本的存储方法：顺序存储方法（结构）：用数据元素在存储器中相对位置来表示数据元素之间的逻辑关系。链接存储方法（链式存储结构）：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3∧元素41345h1346

元素31536

…….

……..

…….1536

元素21400

…….

……..

…….∧

元素413461400

元素11345

指针

存储内容存储地址

链式存储

h

数据的逻辑结构

数据的存储结构数据的运算：检索、排序、插入、删除、修改等

线性结构

非线性结构

顺序存储

链式存储线性表栈队树形结构图形结构小结：数据结构的三个方面1.3抽象数据类型的表示和实现数据类型（datatype）：在一种程序设计语言中，变量所具有的数据种类。例：在C语言中，数据类型包括基本类型和构造类型。基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义抽象数据类型（abstractdatatype，ADT）：是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。抽象数据类型与数据类型的区别：“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型还包括用户自定义的数据类型。抽象数据类型三元组的定义：（D，S，P）其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。抽象数据类型的定义格式：ADT抽象数据类型名｛数据对象：（数据对象的定义）数据关系：（数据关系的定义）基本操作：（基本操作的定义）｝ADT抽象数据类型名抽象数据类型的表示和实现：利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。本书采用介于伪码和C语言之间的类C语言作为描述工具。（见书P10－P13）1.4算法和算法分析算法：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：（1）有穷性（2）确定性（3）可行性（4）输入（5）输出算法设计的要求：评价一个好的算法有以下几个标准。正确性(Correctness)：算法应满足具体问题的需求。可读性(Readability)：算法应该好读，以有利于阅读者对程序的理解。健状性(Robustness)：算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。例4、电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：

(a1，b1)(a2，b2)…(an，bn)其中ai，bi(i=1，2…n)分别表示某人的名字和对应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。分析：算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据的结构，直接影响算法的选择和效率。解：上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)（其中，1≤i≤n）。数据结构还要提供每种结构类型所定义的各种运算的算法。数值计算解决问题的一般步骤：数学模型→选择计算机语言→编出程序→测试→最终解答。数值计算的关键是：如何得出数学模型（方程）？程序设计人员比较关注程序设计的技巧。

算法效率的度量：对一个算法要作出全面的分析可分成两个阶段进行，即事先分析和事后测试。事先分析：求出该算法的一个时间界限函数事后测试：收集此算法的执行时间和实际占用空间的统计资料。定义：如果存在两个正常数c和n0，对于所有的n≧n0，有 ︱f(n)︳≦c｜g(n)︳，则记作f(n)=O(g(n))。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作：

T(n)=O(f(n))称作算法的渐近时间复杂度。频度：是指该语句重复执行的次数例１、for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}解：由于是一个三重循环，每个循环从1到n，则总次数为:n×n×n=n3，时间复杂度为T(n)=O(n3)。例2、{++x;s=0;}解：将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)。如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。例３、for(i=1;i<=n;++i){++x;s+=x;}解：语句频度为：2n其时间复杂度为：O(n)即时间复杂度为线性阶。例４、for(i=1;i<=n;++i)

for(j=1;j<=n;++j){++x;s+=x;}解：语句频度为：2n2其时间复杂度为：O(n2)

即时间复杂度为平方阶。定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)。例５、for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i,j]=x;}解：语句频度为：

1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴时间复杂度为O(n2)。即此算法的时间复杂度为平方阶。结论：一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其关系为：

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指数时间的关系为：

O(2n)<O(n!)<O(nn)

当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如：Voidbubble-sort(inta[]，intn)for(i=n-1;change=TURE;i>1&&change;--i){change=false;for(j=0;j<i;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=TURE;}}最好情况：0次最坏情况：1+2+3+…+n-1=n(n-1)/2平均时间复杂度为:O(n2)

算法的存储空间需求空间复杂度:算法所需存储空间的度量，记作:S(n)=O(f(n))其中n为问题的规模(或大小)。第一章小结数据结构的相关概念和术语数据结构的三个方面的研究内容逻辑结构存储结构操作算法和算法分析练习题下面程序段的时间复杂度是多少？for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;下面程序段的时间复杂度是多少？i=1;While(i<=n)i=i*3;有如下递归函授fact（n），分析其时间复杂度。fact（intn）｛

if（n<＝1）return（1）；

elsereturn（n*fact（n））；｝下列是几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。A＝（D，S）D＝｛a，b，c，d，e，f，g，h｝S＝｛s｝s＝｛<a，b>，<b，c>，<c，d>，<d，e>，<e，f>，<f，g>，<g，h>｝A＝（D，S）D＝｛a，b，c，d，e，f，g，h｝S＝｛s｝s＝｛<d，b>，<d，g>，<d，a>，<b，c>，<g，e>，<g，h>，<e，f>｝下列是几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。A＝（D，S）D＝｛1，2，3，4，5，6｝S＝｛s｝s＝｛(1，2)，(2，3)，(3，4)，(3，5)，(3，6)，(4，5)，(4，6)｝这里的圆括号对表示两结点是双向的。第二章线性表线性结构特点：在数据元素的非空有限集中，存在唯一的一个被称作“第一个”的数据元素；存在唯一的一个被称作“最后一个”的数据元素；除第一个外，集合中的每个数据元素均只有一个前驱；除最后一个外，集合中的每个数据元素均只有一个后继。例如：线性表、栈、队列、串等。第二章线性表

2.1线性表的基本概念和类型定义

2.2线性表的顺序表示和实现

2.3线性表的链式表示和实现2.1线性表的类型定义线性表的定义：线性表是由n(n≧0)个数据元素（结点）a1，a2，……，an组成的有限序列。例1、英文字母表（A，B，C，……，Z）是一个线性表。例2、数据元素学号姓名年龄001张三18002李四19………………线性表的特征：元素个数n(n≧0)为线性表的长度，n＝0时线性表为空表。线性表为非空表时，ai的直接前驱是ai-1,a1没有前驱，为首元（第一个元素）；ai的直接后继是ai+1,an没有后继，为末元（最有一个元素）。ai是第i个元素，i为元素ai在线性表中的位序。（数据元素在线性表中的位置只取决于它的序号。）元素同构，且不能出现缺项a1a2anai－1aiai＋1…………线性表的形式化定义:(二元组）LL=（D,S）D={a1,a2,…,an}S={r}r={<ai-1,ai>｜ai∈D，i=2,…,n}线性表的抽象数据类型定义：ADTList{

数据对象：D

数据关系：S

基本操作：……}ADTList

线性表的运算（操作）：数据的运算是定义在逻辑结构上的，而具体的实现则在存储结构上进行。构造空表：InitList(&L)销毁线性表DestroyList(&L)

加工型操作线性表清零：Clearlist（&L）赋e值给线性表的第i个元素：PutElem（L，i，&e）在线性表第i个元素之前插入值为e的元素：（&L，i，e）删除线性表的第i个元素并用e值返回其值：ListDelete（&L，i，&e）引用型操作：判断线性表是否为空：ListEmpty(L)求线性表长度：ListLengh(L)求前驱：priorElem(L,cur_e,&pre_e)求后继：NextElem(L,cur_e,&next_e)取第i个元素的值:GetElem(L,i,&e)判定线性表中是否存在值为e的元素：LocateElem(L,e,compare())依次调用线性表中的元素：ListTraverse(L,visit())注：可以利用上述基本运算来实现一些复杂的操作。例1、利用两个线性表LA和LB分别表示两个集合A和B，要求得到一个新集合A＝AUB。基本思想：扩大线性表LA，将存在于线性表LB中而不存在于LA中的数据元素插入到线性表LA中。实现：

1、从线性表LB中依次取得各个数据元素，GetElem(LB,i,e)2、依值在线性表LA中查找，LocateElem(LA,e,equal())3、若不存在，则将其插入。ListInert(LA,n+1,e)45138LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}45138LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}45138LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}45138LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i45138LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i45138LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i451383LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i451383LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i451383LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i451383LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i45138311LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i45138311LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i45138311LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i45138311LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i45138311LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i45138311LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i45138311LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i451383117LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i451383117LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i451383117LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i451383117LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal)()ListInsert(La,++La_len,e);

}}i451383117LA311475LBVoindunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i451383117LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}i451383117LA311475LBVoidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);

}}iVoidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++)GetElem(Lb,i,e);if(!LocateElem(La,e,equal())ListInsert(La,++La_len,e)}}算法分析：基本操作是：GetElem、LocateElem、ListInsertGetElem和ListInsert的执行时间与表长无关

LocateElem的执行时间与表长成正比所以，该算法的时间复杂度为：O（ListLength（LA）×ListLength（LB）)例2、已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。基本思想：将LA和LB中的元素逐个插入到空表LC中。实现：设置两个指针i和j分别指向LA和LB中的某个元素a和b，则插入LC中的元素应为a和b中较小的一个。voidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbvoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLcvoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLckjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLckjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLckjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLckjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc2kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc2kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc2kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc23kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc23kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc23kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc235kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc235kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc235kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc2356kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc2356kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc2356kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc23567kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc23567kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc23567kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc235677kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);ListInsert(Lc,++k,bj);}}357162671821LaLbLc235677kjivoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(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(Lb,j++,bj);