數(shù)據(jù)結(jié)構(gòu)-02線性表分析

第2章線性表教學(xué)要求理解線性表的概念掌握線性表的抽象數(shù)據(jù)類型和應(yīng)具有的基本操作掌握線性表的順序存儲結(jié)構(gòu)的實現(xiàn)方法掌握線性表的鏈表存儲結(jié)構(gòu)的實現(xiàn)方法掌握線性表的簡單應(yīng)用重點線性表的抽象數(shù)據(jù)類型線性表的順序存儲結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的簡單應(yīng)用難點線性表算法的設(shè)計與實現(xiàn)線性結(jié)構(gòu)的基本特征為1集合中必存在唯一的“第一元素”；2集合中必存在唯一的“最后元素”；3除最后元素在外，均有唯一的后繼；4除第一元素之外，均有唯一的前驅(qū)。線性結(jié)構(gòu)是一個數(shù)據(jù)元素的有序（次序）集。線性表是一種很簡單的線性結(jié)構(gòu)21線性表的類型定義線性表線性表是N個元素的有序序列。它是很常用且很簡單的一種數(shù)據(jù)結(jié)構(gòu)。（A1,A2,AI1，AI,AI1，,AN）線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)ON0時稱為數(shù)據(jù)元素線性起點AI的直接前趨AI的直接后繼下標(biāo)，是元素的序號，表示元素在表中的位置N為元素總個數(shù)，即表長。N0空表線性終點（A,B,C,D,Z）學(xué)號姓名性別年齡班級012003010622陳建武男192003級電信0301班012003010704趙玉鳳女182003級電信0302班012003010813王澤男192003級電信0303班012003010906薛荃男192003級電信0304班012003011018王春男192003級電信0305班例2分析學(xué)生情況登記表是什么結(jié)構(gòu)。分析數(shù)據(jù)元素都是同類型（記錄），元素間關(guān)系是線性的。分析數(shù)據(jù)元素都是同類型（字母），元素間關(guān)系是線性的。注意同一線性表中的元素必定具有相同特性注意同一線性表中的元素必定具有相同特性例1分析26個英文字母組成的英文表的結(jié)構(gòu)。綜上例U線性表中的數(shù)據(jù)元素可以不同U但同一個表中的元素必須具有相同的屬性U相鄰數(shù)據(jù)元素之間存在序偶關(guān)系U線性表中每一個元素都有確定的位置，如A1是第1個數(shù)據(jù)元素，AI是第I個數(shù)據(jù)元素抽象數(shù)據(jù)類型線性表的定義ADTLIST數(shù)據(jù)對象DAI|AIELEMSET,I1,2,N,N0稱N為線性表的表長當(dāng)N0時為空表。數(shù)據(jù)關(guān)系R1|AI1,AID,I2,N設(shè)線性表為A1，A2,，AI，AN，稱I為AI在線性表中的位序?；静僮鹘Y(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作引用型操作加工型操作ADTLISTINITLIST2依值在線性表LA中進(jìn)行查訪3若不存在，則插入之。GETELEMLB,IELOCATEELEMLA,E,EQUALLISTINSERTLA,N1,E操作步驟4重復(fù)上述過程，直到訪問到LB中所有元素。GETELEMLB,I,E/取LB中第I個數(shù)據(jù)元素賦給EIFLOCATEELEMLA,E,EQUALLISTINSERTLA,LA_LEN,E/LA中不存在和E相同的數(shù)據(jù)元素，則插入之VOIDUNIONLIST/求線性表的長度LB_LENLISTLENGTHLBFORI1I。用一組地址連續(xù)的存儲單元依次存放線性表中的數(shù)據(jù)元素A1A2AI1AIAN線性表的起始地址稱作線性表的基地址以“存儲位置相鄰”表示有序?qū)?，即LOCAILOCAI1C其中C為一個數(shù)據(jù)元素所占存儲量所有數(shù)據(jù)元素的存儲位置均取決于第一個數(shù)據(jù)元素的存儲位置。LOCAILOCA1I1C基地址線性表順序映像的C語言描述TYPEDEFSTRUCTSQLIST/俗稱順序表ELEMTYPEELEM/存儲空間基址INTLENGTH/當(dāng)前長度INTLISTSIZE/當(dāng)前分配的存儲容量/以SIZEOFELEMTYPE為單位在C語言中，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語言的一維數(shù)組實現(xiàn)線性表的順序存儲。TYPEDEFSTRUCTELEMTYPELISTMAXSIZEINTSIZESQLIST/MAXSIZE表示數(shù)組的最大元素個數(shù)，LIST表示順序表的數(shù)組名，SIZE表示順序表中當(dāng)前存儲的數(shù)據(jù)元素個數(shù)，它必須滿足SIZEMAXSIZE，SQLIST是該結(jié)構(gòu)體的名字。/線性表的基本操作在順序表中的應(yīng)用INITLISTIFLELEMEXITOVERFLOWLLENGTH0LLISTSIZELIST_INIT_SIZERETURNOK如何實現(xiàn)定位線性表中元素的操作LOCATEELEML,E,COMPARE先看一下查找的過程例如順序表23754138546217LELEMLLENGTHLLISTSIZEE38PPPPPI1234850可見，其基本操作是將順序表中的元素逐個和給定值E進(jìn)行比較。INTLOCATEELEM_SQSQLISTL,ELEMTYPEE,STATUSCOMPAREELEMTYPE,ELEMTYPE/在順序表中查詢第1個滿足判定條件的數(shù)據(jù)元素，若存在，則返回它的位序，否則返回0。/LOCATEELEM_SQOLISTLENGTHL算法的時間復(fù)雜度I1/I的初值為第1元素的位序PLELEM/P的初值為第1元素的存儲位置WHILEI,表的長度增加2118307542568721183075例如LISTINSERT_SQL,5,66LLENGTH10PPPQ87564266Q/Q指示插入位置FORPPQPP1PPSTATUSLISTINSERT_SQSQLIST/Q指示插入位置FORPPQPP1P/插入位置及之后的元素右移QE/插入ELLENGTH/表長增1RETURNOK元素右移考慮移動元素的平均情況假設(shè)在第I個元素之前插入的概率為，則在長度為N的線性表中插入一個元素所需移動元素次數(shù)的期望值為若假定在線性表中任何一個位置上進(jìn)行插入的概率都是相等的，則移動元素的期望值為如何實現(xiàn)刪除線性表中元素的操作LISTDELETEQLELEMLLENGTH1FORPPLLENGTHRETURNERROR/刪除位置不合法考慮移動元素的平均情況假設(shè)刪除第I個元素的概率為,則在長度為N的線性表中刪除一個元素所需移動元素次數(shù)的期望值為若假定在線性表中任何一個位置上進(jìn)行刪除的概率都是相等的，則移動元素的期望值為問題、在順序表中，第個元素前面插入一個元素，要移動多少個元素、在順序表中，要刪除第個元素，要移動多少個元素算法順序表的合并已知順序表LA和LB按值非遞減排列，歸并兩表，得到新表LC也按值非遞減排列。分析LC中的數(shù)據(jù)元素或者是LA中的數(shù)據(jù)元素，或者是LB中的數(shù)據(jù)元素，則只要將LA或LB中的元素逐個插入到LC中即可。設(shè)兩個指針PA和PB分別指向LA和LB中的某個元素，若設(shè)PA當(dāng)前所指的元素為A，PB當(dāng)前所指的元素為B，則當(dāng)前應(yīng)插入到LC中的元素C為C；C很顯然，指針PA和PB的初值均為1，在所指元素插入LC后，PA，PB在LA或LB中順序后移。VOIDMERGELISTSQLISTLA,SQLISTLB,SQLISTPBLBELEMLCLISTSIZELCLENGTHLALENGTHLBLENGTHPCLCELEMELEMTYPEMALLOCLCLISTSIZESIZEOFELEMTYPEPALASTLAELEMLALENGTH1PBLASTLBELEMLBLENGTH1WHILEPANEXTJ1/P指向第一個結(jié)點，J為計數(shù)器WHILEJNEXTJ/順指針向后查找，直到P指向第I個元素/或P為空EPDATA/取得第I個元素RETURNOKP/第I個元素不存AI1線性表中LISTINSERTJ0WHILEPJ/尋找第I1個結(jié)點STATUSGETELEM_LLINKLISTL,INTI,ELEMTYPEJ1/P指向第一個結(jié)點，J為計數(shù)器WHILEJNEXTJ/順指針向后查找，直到P指向第I個元素/或P為空EPDATA/取得第I個元素RETURNOKP/第I個元素不存STATUSLISTINSERT_LLINKLISTL,INTI,ELEMTYPEE/L為帶頭結(jié)點的單鏈表的頭指針，本算法/在鏈表中第I個結(jié)點之前插入新的元素E/LINSTINSERT_LPLJ0WHILEPJ/尋找第I1個結(jié)點IFP|JI1RETURNERROR/I大于表長加1或者小于1SLINKLISTMALLOCSIZEOFLNODE/生成新結(jié)點SDATAESNEXTPNEXTPNEXTS/插入RETURNOKEAI1AISP線性表中LISTDELETEPNEXTQNEXTEQDATAFREEQPQSTATUSLISTDELETE_LLINKLISTL,INTI,ELEMTYPEJ0WHILEPNEXTJ/尋找第I個結(jié)點，并令P指向其前趨IFPNEXT|JI1RETURNERROR/刪除位置不合理QPNEXTPNEXTQNEXT/刪除并釋放結(jié)點EQDATAFREEQRETURNOKCLEARLISTLNEXTPNEXT/CLEARLISTFREEP算法時間復(fù)雜度OLISTLENGTHL如何從線性表得到單鏈表鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此生成鏈表的過程是一個結(jié)點“逐個插入”的過程。例如，逆位序輸入N個數(shù)據(jù)元素的值，建立帶頭結(jié)點的單鏈表。例如，逆位序輸入N個數(shù)據(jù)元素的值，建立帶頭結(jié)點的單鏈表。操作步驟1建立一個“空表”；2輸入數(shù)據(jù)元素AN，建立結(jié)點并插入；3輸入數(shù)據(jù)元素AN1，建立結(jié)點并插入；ANANAN14依次類推，直至輸入A1為止。VOIDCREATELIST_LLINKLISTLNEXTNULL/先建立一個帶頭結(jié)點的單鏈表FORINI0IPLINKLISTMALLOCSIZEOFLNODESCANF/輸入元素值PNEXTLNEXTLNEXTP/插入在單鏈表中設(shè)置頭結(jié)點的好處1、使空表和非空表統(tǒng)一。2、在設(shè)計算法的時候，使首元結(jié)點和其他結(jié)點的處理一致。將兩個有序鏈表合并為一個有序鏈表已知單鏈表LA和LB按值非遞減排列，歸并兩表，得到新表LC也按值非遞減排列。分析LC中的數(shù)據(jù)元素或者是LA中的數(shù)據(jù)元素，或者是LB中的數(shù)據(jù)元素，則只要將LA或LB中的元素逐個插入到LC中即可。設(shè)兩個指針PA和PB分別指向LA和LB中的某個元素，若設(shè)PA當(dāng)前所指的元素為A，PB當(dāng)前所指的元素為B，則當(dāng)前應(yīng)插入到LC中的元素C為C；C很顯然，指針PA和PB的初值均為1，在所指元素插入LC后，PA，PB在LA或LB中順序后移。VOIDMERGELISTSQLISTLA,SQLISTLB,SQLISTPBLBELEMLCLISTSIZELCLENGTHLALENGTHLBLENGTHPCLCELEMELEMTYPEMALLOCLCLISTSIZESIZEOFELEMTYPEPALASTLAELEMLALENGTH1PBLASTLBELEMLBLENGTH1WHILEPANEXTPBLBNEXTLCPCLAWHILEPAPCPAPAPANEXTELSEPCNEXTPBPCPBPBPBNEXTPCNEXTPAPAPBFREELB鏈表的優(yōu)點1、合理利用空間。2、插入和刪除時不用移動大量元素。上述定義的單鏈表實現(xiàn)線性表的操作時存在如下問題改進(jìn)鏈表的設(shè)置1單鏈表的表長是一個隱含的值；1增加“表長”、“表尾指針”和“當(dāng)前位置的指針”三個數(shù)據(jù)域；2在單鏈表的最后一個元素之后插入元素時，需遍歷整個鏈表；3在鏈表中，元素的“位序”的概念淡化了。2將基本操作中的“位序I”改變?yōu)椤爸羔楶”。1雙向鏈表232其它形式的鏈表TYPEDEFSTRUCTDULNODEELEMTYPEDATA/數(shù)據(jù)域STRUCTDULNODEPRIOR/指向前驅(qū)的指針域STRUCTDULNODENEXT/指向后繼的指針域DULNODE,DULINKLIST最后一個結(jié)點的指針域的指針又指回第一個結(jié)點的鏈表。A1A2AN2循環(huán)鏈表和單鏈表的差別僅在于，判別鏈表中最后一個結(jié)點的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點”。3雙向循環(huán)鏈表空表非空表A1A2AN雙向鏈表的操作特點1“查詢”和單鏈表相同。2插入”和“刪除”時需要同時修改兩個方向上的指針。AI1AIESNEXTPNEXTPNEXTSSNEXTPRIORSSPRIORPPS插入AI1刪除AIAI1PNEXTPNEXTNEXTPNEXTPRIORPP單循環(huán)鏈表的一個很重要的應(yīng)用是若瑟夫環(huán)問題N個人圍成一圈，每人有一個各不相同的編號。選擇一個人作為起點，然后順時針從1到K數(shù)數(shù)，每數(shù)到K的人退出圈子，圈子縮小，再從下一個人繼續(xù)從1到K數(shù)數(shù),重復(fù)上面過程。求最后退出圈子的那個人原來的編號。該問題是由古羅馬著名史學(xué)家JOSEPHUS提出的問題演變而來，所以通常稱之為JOSEPHUS問題。JOSEPHUS問題的解決需要采用循環(huán)鏈表，先構(gòu)造一個有N個結(jié)點的不帶頭結(jié)點的單循環(huán)鏈表，在鏈表的某個結(jié)點開始從1計數(shù)，計到K1時，將下一個結(jié)點從鏈表中刪除，然后再從被刪除結(jié)點的下一個結(jié)點又從1開始計數(shù)，數(shù)到K1，再將其下一個結(jié)點從單循環(huán)鏈表刪除，直到剩下一個結(jié)點為止。24一元多項式的表示在計算機(jī)中，可以用一個線性表來表示PP0,P1,，PN一元多項式但是對于形如SX13X100002X20000的多項式，上述表示方法合適嗎一般的，一元稀疏多項式可寫成PNXP1XE1P2XE2PMXEM其中PI是指數(shù)為EI的項的非零系數(shù)，0E1|AI1,AID,I2,N，且AI1中的指數(shù)值A(chǔ)I中的指數(shù)值CREATPOLYN/系數(shù)INTEXPN/指數(shù)TERM,ELEMTYPETYPEDEFORDEREDLINKLISTPOLYNOMIAL/用帶表頭結(jié)點的有序鏈表表示多項式結(jié)點的數(shù)據(jù)元素類型定義為有序鏈表中一些操作的功能STATUSLOCATELEMLINKLISTL,ELEMTYPEE,POSITION否則