数据结构-02线性表分析

第2章线性表教学要求理解线性表的概念掌握线性表的抽象数据类型和应具有的基本操作掌握线性表的顺序存储结构的实现方法掌握线性表的链表存储结构的实现方法掌握线性表的简单应用重点线性表的抽象数据类型线性表的顺序存储结构线性表的链式存储结构线性表的简单应用难点线性表算法的设计与实现线性结构的基本特征为1集合中必存在唯一的“第一元素”；2集合中必存在唯一的“最后元素”；3除最后元素在外，均有唯一的后继；4除第一元素之外，均有唯一的前驱。线性结构是一个数据元素的有序（次序）集。线性表是一种很简单的线性结构21线性表的类型定义线性表线性表是N个元素的有序序列。它是很常用且很简单的一种数据结构。（A1,A2,AI1，AI,AI1，,AN）线性表的逻辑结构线性表的逻辑结构ON0时称为数据元素线性起点AI的直接前趋AI的直接后继下标，是元素的序号，表示元素在表中的位置N为元素总个数，即表长。N0空表线性终点（A,B,C,D,Z）学号姓名性别年龄班级012003010622陈建武男192003级电信0301班012003010704赵玉凤女182003级电信0302班012003010813王泽男192003级电信0303班012003010906薛荃男192003级电信0304班012003011018王春男192003级电信0305班例2分析学生情况登记表是什么结构。分析数据元素都是同类型（记录），元素间关系是线性的。分析数据元素都是同类型（字母），元素间关系是线性的。注意同一线性表中的元素必定具有相同特性注意同一线性表中的元素必定具有相同特性例1分析26个英文字母组成的英文表的结构。综上例U线性表中的数据元素可以不同U但同一个表中的元素必须具有相同的属性U相邻数据元素之间存在序偶关系U线性表中每一个元素都有确定的位置，如A1是第1个数据元素，AI是第I个数据元素抽象数据类型线性表的定义ADTLIST数据对象DAI|AIELEMSET,I1,2,N,N0称N为线性表的表长当N0时为空表。数据关系R1|AI1,AID,I2,N设线性表为A1，A2,，AI，AN，称I为AI在线性表中的位序。基本操作结构初始化操作结构销毁操作引用型操作加工型操作ADTLISTINITLIST2依值在线性表LA中进行查访3若不存在，则插入之。GETELEMLB,IELOCATEELEMLA,E,EQUALLISTINSERTLA,N1,E操作步骤4重复上述过程，直到访问到LB中所有元素。GETELEMLB,I,E/取LB中第I个数据元素赋给EIFLOCATEELEMLA,E,EQUALLISTINSERTLA,LA_LEN,E/LA中不存在和E相同的数据元素，则插入之VOIDUNIONLIST/求线性表的长度LB_LENLISTLENGTHLBFORI1I。用一组地址连续的存储单元依次存放线性表中的数据元素A1A2AI1AIAN线性表的起始地址称作线性表的基地址以“存储位置相邻”表示有序对，即LOCAILOCAI1C其中C为一个数据元素所占存储量所有数据元素的存储位置均取决于第一个数据元素的存储位置。LOCAILOCA1I1C基地址线性表顺序映像的C语言描述TYPEDEFSTRUCTSQLIST/俗称顺序表ELEMTYPEELEM/存储空间基址INTLENGTH/当前长度INTLISTSIZE/当前分配的存储容量/以SIZEOFELEMTYPE为单位在C语言中，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。TYPEDEFSTRUCTELEMTYPELISTMAXSIZEINTSIZESQLIST/MAXSIZE表示数组的最大元素个数，LIST表示顺序表的数组名，SIZE表示顺序表中当前存储的数据元素个数，它必须满足SIZEMAXSIZE，SQLIST是该结构体的名字。/线性表的基本操作在顺序表中的应用INITLISTIFLELEMEXITOVERFLOWLLENGTH0LLISTSIZELIST_INIT_SIZERETURNOK如何实现定位线性表中元素的操作LOCATEELEML,E,COMPARE先看一下查找的过程例如顺序表23754138546217LELEMLLENGTHLLISTSIZEE38PPPPPI1234850可见，其基本操作是将顺序表中的元素逐个和给定值E进行比较。INTLOCATEELEM_SQSQLISTL,ELEMTYPEE,STATUSCOMPAREELEMTYPE,ELEMTYPE/在顺序表中查询第1个满足判定条件的数据元素，若存在，则返回它的位序，否则返回0。/LOCATEELEM_SQOLISTLENGTHL算法的时间复杂度I1/I的初值为第1元素的位序PLELEM/P的初值为第1元素的存储位置WHILEI,表的长度增加2118307542568721183075例如LISTINSERT_SQL,5,66LLENGTH10PPPQ87564266Q/Q指示插入位置FORPPQPP1PPSTATUSLISTINSERT_SQSQLIST/Q指示插入位置FORPPQPP1P/插入位置及之后的元素右移QE/插入ELLENGTH/表长增1RETURNOK元素右移考虑移动元素的平均情况假设在第I个元素之前插入的概率为，则在长度为N的线性表中插入一个元素所需移动元素次数的期望值为若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为如何实现删除线性表中元素的操作LISTDELETEQLELEMLLENGTH1FORPPLLENGTHRETURNERROR/删除位置不合法考虑移动元素的平均情况假设删除第I个元素的概率为,则在长度为N的线性表中删除一个元素所需移动元素次数的期望值为若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为问题、在顺序表中，第个元素前面插入一个元素，要移动多少个元素、在顺序表中，要删除第个元素，要移动多少个元素算法顺序表的合并已知顺序表LA和LB按值非递减排列，归并两表，得到新表LC也按值非递减排列。分析LC中的数据元素或者是LA中的数据元素，或者是LB中的数据元素，则只要将LA或LB中的元素逐个插入到LC中即可。设两个指针PA和PB分别指向LA和LB中的某个元素，若设PA当前所指的元素为A，PB当前所指的元素为B，则当前应插入到LC中的元素C为C；C很显然，指针PA和PB的初值均为1，在所指元素插入LC后，PA，PB在LA或LB中顺序后移。VOIDMERGELISTSQLISTLA,SQLISTLB,SQLISTPBLBELEMLCLISTSIZELCLENGTHLALENGTHLBLENGTHPCLCELEMELEMTYPEMALLOCLCLISTSIZESIZEOFELEMTYPEPALASTLAELEMLALENGTH1PBLASTLBELEMLBLENGTH1WHILEPANEXTJ1/P指向第一个结点，J为计数器WHILEJNEXTJ/顺指针向后查找，直到P指向第I个元素/或P为空EPDATA/取得第I个元素RETURNOKP/第I个元素不存AI1线性表中LISTINSERTJ0WHILEPJ/寻找第I1个结点STATUSGETELEM_LLINKLISTL,INTI,ELEMTYPEJ1/P指向第一个结点，J为计数器WHILEJNEXTJ/顺指针向后查找，直到P指向第I个元素/或P为空EPDATA/取得第I个元素RETURNOKP/第I个元素不存STATUSLISTINSERT_LLINKLISTL,INTI,ELEMTYPEE/L为带头结点的单链表的头指针，本算法/在链表中第I个结点之前插入新的元素E/LINSTINSERT_LPLJ0WHILEPJ/寻找第I1个结点IFP|JI1RETURNERROR/I大于表长加1或者小于1SLINKLISTMALLOCSIZEOFLNODE/生成新结点SDATAESNEXTPNEXTPNEXTS/插入RETURNOKEAI1AISP线性表中LISTDELETEPNEXTQNEXTEQDATAFREEQPQSTATUSLISTDELETE_LLINKLISTL,INTI,ELEMTYPEJ0WHILEPNEXTJ/寻找第I个结点，并令P指向其前趋IFPNEXT|JI1RETURNERROR/删除位置不合理QPNEXTPNEXTQNEXT/删除并释放结点EQDATAFREEQRETURNOKCLEARLISTLNEXTPNEXT/CLEARLISTFREEP算法时间复杂度OLISTLENGTHL如何从线性表得到单链表链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。例如，逆位序输入N个数据元素的值，建立带头结点的单链表。例如，逆位序输入N个数据元素的值，建立带头结点的单链表。操作步骤1建立一个“空表”；2输入数据元素AN，建立结点并插入；3输入数据元素AN1，建立结点并插入；ANANAN14依次类推，直至输入A1为止。VOIDCREATELIST_LLINKLISTLNEXTNULL/先建立一个带头结点的单链表FORINI0IPLINKLISTMALLOCSIZEOFLNODESCANF/输入元素值PNEXTLNEXTLNEXTP/插入在单链表中设置头结点的好处1、使空表和非空表统一。2、在设计算法的时候，使首元结点和其他结点的处理一致。将两个有序链表合并为一个有序链表已知单链表LA和LB按值非递减排列，归并两表，得到新表LC也按值非递减排列。分析LC中的数据元素或者是LA中的数据元素，或者是LB中的数据元素，则只要将LA或LB中的元素逐个插入到LC中即可。设两个指针PA和PB分别指向LA和LB中的某个元素，若设PA当前所指的元素为A，PB当前所指的元素为B，则当前应插入到LC中的元素C为C；C很显然，指针PA和PB的初值均为1，在所指元素插入LC后，PA，PB在LA或LB中顺序后移。VOIDMERGELISTSQLISTLA,SQLISTLB,SQLISTPBLBELEMLCLISTSIZELCLENGTHLALENGTHLBLENGTHPCLCELEMELEMTYPEMALLOCLCLISTSIZESIZEOFELEMTYPEPALASTLAELEMLALENGTH1PBLASTLBELEMLBLENGTH1WHILEPANEXTPBLBNEXTLCPCLAWHILEPAPCPAPAPANEXTELSEPCNEXTPBPCPBPBPBNEXTPCNEXTPAPAPBFREELB链表的优点1、合理利用空间。2、插入和删除时不用移动大量元素。上述定义的单链表实现线性表的操作时存在如下问题改进链表的设置1单链表的表长是一个隐含的值；1增加“表长”、“表尾指针”和“当前位置的指针”三个数据域；2在单链表的最后一个元素之后插入元素时，需遍历整个链表；3在链表中，元素的“位序”的概念淡化了。2将基本操作中的“位序I”改变为“指针P”。1双向链表232其它形式的链表TYPEDEFSTRUCTDULNODEELEMTYPEDATA/数据域STRUCTDULNODEPRIOR/指向前驱的指针域STRUCTDULNODENEXT/指向后继的指针域DULNODE,DULINKLIST最后一个结点的指针域的指针又指回第一个结点的链表。A1A2AN2循环链表和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。3双向循环链表空表非空表A1A2AN双向链表的操作特点1“查询”和单链表相同。2插入”和“删除”时需要同时修改两个方向上的指针。AI1AIESNEXTPNEXTPNEXTSSNEXTPRIORSSPRIORPPS插入AI1删除AIAI1PNEXTPNEXTNEXTPNEXTPRIORPP单循环链表的一个很重要的应用是若瑟夫环问题N个人围成一圈，每人有一个各不相同的编号。选择一个人作为起点，然后顺时针从1到K数数，每数到K的人退出圈子，圈子缩小，再从下一个人继续从1到K数数,重复上面过程。求最后退出圈子的那个人原来的编号。该问题是由古罗马著名史学家JOSEPHUS提出的问题演变而来，所以通常称之为JOSEPHUS问题。JOSEPHUS问题的解决需要采用循环链表，先构造一个有N个结点的不带头结点的单循环链表，在链表的某个结点开始从1计数，计到K1时，将下一个结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，数到K1，再将其下一个结点从单循环链表删除，直到剩下一个结点为止。24一元多项式的表示在计算机中，可以用一个线性表来表示PP0,P1,，PN一元多项式但是对于形如SX13X100002X20000的多项式，上述表示方法合适吗一般的，一元稀疏多项式可写成PNXP1XE1P2XE2PMXEM其中PI是指数为EI的项的非零系数，0E1|AI1,AID,I2,N，且AI1中的指数值AI中的指数值CREATPOLYN/系数INTEXPN/指数TERM,ELEMTYPETYPEDEFORDEREDLINKLISTPOLYNOMIAL/用带表头结点的有序链表表示多项式结点的数据元素类型定义为有序链表中一些操作的功能STATUSLOCATELEMLINKLISTL,ELEMTYPEE,POSITION否则