搜索
第二章线形表数据结构2百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理1、线性表(LinearList)：定义：由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。记作：L=(a1，a2，…ai-1，ai，ai+1，…an)其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）数据结构3百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理例3、学生健康情况登记表如下：例4、一副扑克的点数（2，3，4，…，J，Q，K，A）姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….数据结构4百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理线性表——元素及元素之间的关系为线性线性：（1）有且仅有一个开始节点（该节点只有一个后继节点，没有前趋节点）（2）有且仅有一个结束节点（该节点只有一个前趋节点，没有后继节点）（3）除首节点，其余节点有且仅有一个前趋k1k2k3k4k1k2k3（4）除尾节点，其余节点有且仅有一个后继数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。数据结构5百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理线性表的类型定义抽象数据类型线性表的定义ADTList{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}基本操作：{初始化}InitList(&L)操作结果：构造一个空的线性表L。{结构销毁}DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。{引用型操作}ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。数据结构6百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理ADTListGetElem(L,i,&e)初始条件：线性表L已存在，1≤i≤LengthList(L)操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。ListTraverse(L,visit())初始条件：线性表L已存在。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。数据结构7百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理ADTList{加工型操作}ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。PutElem(L,i,&e)初始条件：线性表L已存在，1≤i≤LengthList(L)操作结果：L中第i个元素赋值同e的值。ListInsert(&L,i,e)初始条件：线性表L已存在，1≤i≤LengthList(L)+1操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤LengthList(L)操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。}ADTList数据结构8百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理举例假设线性表L=(23,56,89,76,18),i=3,x=56,y=88,则对L的一组操作及结果如下：ListLength(L)//所得结果为5GetElem(L,i,&e)//所得结果为89PriorElem(L,x,&pre_e)//所得结果为23NextElem(L,x,&next_e)//所得结果为89LocateElem(L,x,equal)//所得结果为2ListInsert(&L,i,y)//所得结果为(23,56,88,89,76,18)ListDelete(&L,i+1,&e)/所得结果为(23,56,88,76,18)89数据结构9百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理如何实现线性表的其它操作例2-1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。设计思想：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。分下列三步进行：1．从线性表LB中依次取得每个数据元素;2．依值在线性表LA中进行查访;3．若不存在，则插入之。数据结构10百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理A=A∪B算法描述：//将所有在线性表Lb中但不在La中的数据元素插入到La中voidUnion(List&La，ListLb){//求线性表的长度La-len=ListLength(La);Lb-len=ListLength(Lb);for(i=1;i=Lb-len;i++){//取Lb中第i个数据元素赋给eGetElem(Lb，i，e);//La中不存在和e相同的数据元素，则插入之if(!LocateElem(La，e，equal))ListInsert(La，++La-en，e);}}//Union数据结构11百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理A=A∪B时间复杂度分析：GetElem取遍Lb表元素需Lb_len=ListLength(Lb)次；循环体内的Locate操作平均需ListLength(La)次最坏情况为：ListLength(La)总的时间复杂度：O[ListLength(Lb)*ListLength(La)]数据结构12百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理例2-1-2已知一个非纯集合B，试构造集合A，要求集合A中只包含集合B中所有值不相同的数据元素。设计思想：解法一：同上例，分别以线性表LA和LB表示集合A和B，则首先初始化线性表LA为空表，之后的操作和例2-1完全相同。解法二：仍以线性表表示集合。只是求解之前先对线性表LB中的数据元素进行排序，即线性表LB中的数据元素依其值从小到大有序排列，则值相同的数据元素必相邻。则上述操作中的第二步就不需要进行从头至尾的查询。数据结构13百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理A=Bvoidpurge(List&La,ListLb){//已知线性表Lb中的数据元素依值非递减有序排列，现构造线性表La，//使La中只包含Lb中所有值不相同的数据元素InitList（La）；//初始化La为空表La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度for(i=1;i=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(ListEmpty(La)||!equal(en，e))ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之en=e;//en，La中的已插入元素}//for}//purge数据结构14百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理A=B时间复杂度分析：GetElem取遍Lb表元素需Lb_len=ListLength(Lb)次；解法一:循环体内的Locate操作平均需ListLength(Lb)次故时间复杂度为：O(ListLength2(LB))；解法二的时间复杂度：循环体内的基本操作与表长无关故时间复杂度为：O(ListLength(Lb))数据结构15百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理C=A∪B例2-2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。设计思想：1、LC为空表，用来存放LA和LB的元素2、表LA和LB的元素逐一进行比较取小者放入表LC中3、插入表LA或表LB中剩余的元素数据结构16百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理算法描述：//已知线性表La和Lb中的元素按值非递减排列。//归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。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)){//La和Lb均非空GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}数据结构17百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理C=A∪Bwhile(i=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}//MergeList数据结构18百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理C=A∪B时间复杂度分析：该算法中包含了三个WHILE语句，其中，第一个处理了某一张表的全部元素和另一张表的部分元素；后两个WHILE循环只可能有一个执行，用来完成将未归并到LC中的余下部分元素插入到LC中。“插入”是估量归并算法时间复杂度的基本操作，其语句频度为：LENGTH（LA）+LENGTH（LB）该算法的时间复杂度为：O（LENGTH（LA）+LENGTH（LB））若LA和LB的元素个数为同数量级n，则该算法的时间复杂度为:O(n)数据结构19百度风云榜www.69wb.com整理数据结构百度风云榜www.69wb.com整理线性表的顺序表示和实现一、线性表的顺序存储结构顺序表：——线性表的顺序存储结构把线性表的结点按逻辑顺序（顺序）依次存放在一组地址连续的存储单元里。1、线性表的地址计算：假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置（首地址）。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：LOC(ai+1)