東北大學(xué)數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)考研輔導(dǎo)材料考者能同學(xué)們，2007年考研專業(yè)課的輔導(dǎo)開始了。為使大家在準(zhǔn)備過程中少走彎路，取得事半功倍的效果。首先我給大家談幾點(diǎn)意見，供同學(xué)們參考。一基本概念二基本結(jié)構(gòu)的算法描述方式:順序;鏈表;串;樹;圖.三基本操作類型:建立;查找；移動;插入;刪除;合并;倒置;連接理解邏輯概念與物理表示之間的對應(yīng)（或轉(zhuǎn)換）關(guān)系學(xué)會把邏輯描述用形式語言實(shí)現(xiàn)的方法要求你們:深刻理解基本概念；熟練掌握基本結(jié)構(gòu)；靈活運(yùn)用基本算法緒論基本概念：一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)1、數(shù)據(jù)在計(jì)算機(jī)科學(xué)領(lǐng)域，凡是計(jì)算機(jī)能識別與處理的數(shù)字、符號、圖形（象）、語音以及它們的匯集通稱數(shù)據(jù)。2、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)本身以及數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系。在數(shù)據(jù)處理時(shí)，為了用戶存取、查找、修改、更新、插入、刪除等操作方，對系統(tǒng)中提供的原始數(shù)據(jù)必須進(jìn)行加工與組織，而經(jīng)過人們加工得到的數(shù)據(jù)型式稱為數(shù)據(jù)結(jié)構(gòu)。它是一種抽象的邏輯結(jié)構(gòu)（logicalstructure）=Data-Structure=（D,S）D是數(shù)據(jù)元素的有限集合；S是D上關(guān)系的有限集。計(jì)算機(jī)科學(xué)領(lǐng)域常用的四種基本的數(shù)據(jù)結(jié)（1）集合結(jié)構(gòu)數(shù)據(jù)元素之間沒有固定關(guān)系。（2）線性結(jié)構(gòu)數(shù)據(jù)元素之間有一對一應(yīng)關(guān)系。

（3）樹型結(jié)構(gòu)數(shù)據(jù)元素之間有一對多的關(guān)系。（3）樹型結(jié)構(gòu)數(shù)據(jù)元素之間有一對多的關(guān)系。二、存儲結(jié)構(gòu)存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在存儲介質(zhì)上的具體表現(xiàn)形式。數(shù)據(jù)結(jié)構(gòu)與存儲結(jié)構(gòu)關(guān)系舉例例如原始數(shù)據(jù)：9,7,4,5,3,6,1,2,8,0數(shù)據(jù)結(jié)構(gòu)：0』,2,3,4,5,6,7,8,9順序存儲01 2 3 4 5 6 7 89鏈?zhǔn)酱鎯樞虼鎯?1 2 3 4 5 6 7 89鏈?zhǔn)酱鎯?shù)據(jù)結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系：1）一種數(shù)據(jù)結(jié)構(gòu)可以對應(yīng)多種存儲結(jié)構(gòu)。但是，在一個系統(tǒng)中一種數(shù)據(jù)結(jié)構(gòu)只能使用一種存儲結(jié)構(gòu)。2）存儲結(jié)構(gòu)在表現(xiàn)形式上可以與數(shù)據(jù)結(jié)構(gòu)相同，也可以不同。但是，它們都必須能準(zhǔn)確無誤地保證原數(shù)據(jù)結(jié)構(gòu)的邏輯關(guān)系。兩種基本的存儲結(jié)構(gòu)1、順序存儲順序存儲是按照數(shù)據(jù)結(jié)構(gòu)中元素的順序把數(shù)據(jù)依次存儲到地址連續(xù)的存儲區(qū)間。特點(diǎn)：1）必須預(yù)知最大空間量。2）每個數(shù)據(jù)元素都占用相同的存儲單元。3）邏輯上相鄰的元素，它們在存儲介質(zhì)上的物理位置一定相鄰。4）在任意位置上的插入與刪除元素浪費(fèi)時(shí)間。5）可以隨機(jī)查找。2、鏈?zhǔn)酱鎯κ前凑諗?shù)據(jù)結(jié)構(gòu)中元素的順序把數(shù)據(jù)依次存儲到任意的地址單元.特點(diǎn)：1）可用任意空閑地址單元實(shí)現(xiàn)對線性表的存儲：2）線性表中元素的邏輯關(guān)系，是用指針來保證的；3）在任意位置上插入與刪除數(shù)據(jù)元素方便：4）在單鏈表中查找數(shù)據(jù)只能用順序查找方式：5）空間利用率比順序存儲低；3、抽象數(shù)據(jù)類型（abstractdatatype,ADT）是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作.其定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān),即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部的使用.一般用三元組表示：（D,S,P）D數(shù)據(jù)對象;S是D上的關(guān)系;P是對D的基本操作.格式定義：ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：（數(shù)據(jù)對象的定義）數(shù)據(jù)關(guān)系：（數(shù)據(jù)關(guān)系的定義）基本操作：（基本操作的定義））基本操作名（參數(shù)表）初始條件：（初始條件描述）操作結(jié)果:（操作結(jié)果描述）例，抽象數(shù)據(jù)類型三元組的定義：ADTTriplet{數(shù)據(jù)對象：D={el,e2,e3|el,e2,e3GElemset}（定義了關(guān)系運(yùn)算的集合）數(shù)據(jù)關(guān)系:Rl={<el,e2>,<e2,e3>}（數(shù)據(jù)關(guān)系的定義）基本操作：（InitTriplet（&T,vl,v2,v3）結(jié)果把el,e2,e3分別賦給參數(shù)vl,v2,v3。DestroyTriplet（&T）結(jié)果三元組T銷毀. cneraticns dataGet（T,i,&e）初始條件:三元組T存在,l《iW3;in操作結(jié)果:用e返回T的第i元的值.InittripletPut（&T,i,e,）初始條件:三元組T存在，1Wi<3;getoTripietL操作結(jié)果:改變T的第i元的值為e.putoeiernMax（T,&e）初始條件:三元組T存在；maxrposition操作結(jié)果:用e返回T的3個元素中的最大值.desMin(T,&e)minrerror初始條件:三元組T存在；操作結(jié)果:用e返回T的3個元素中的最小值.}ADTTriplet三、算法的時(shí)間復(fù)雜度與空間復(fù)雜度1算法的定義:算法是對某類特定問題求解步驟的描述.它應(yīng)滿足下列特性：(1)有零個或多個輸入量；(2)每一步都有唯一確定的含義；(3)至少有一個輸出量；(4)執(zhí)行有限步后自動停止；(5)能用現(xiàn)有的程序語言實(shí)現(xiàn)編程上機(jī)運(yùn)行；2算法的描述方式自然語言；流程框圖；偽形式語言(pascal,c,C++)3算法的時(shí)間復(fù)雜度*程序時(shí)間復(fù)雜性的計(jì)算一個程序P,所占用的時(shí)間T(P)=編譯時(shí)間+運(yùn)行時(shí)間。編譯時(shí)間與程序的特征無關(guān)。因此主要討論程序的運(yùn)行時(shí)間，運(yùn)行時(shí)間通常用TP表示。令n代表程序的特征(即對程序時(shí)間有影響的參數(shù))。那么，TP的計(jì)算公式為：TP(n)=ClADD(n)+C2SUB(n)+C3MUL(n)+C4DIV(n)+-其中，Cl、C2、C3、C4分別表示，一次加、減、乘、除操作所需的時(shí)間。函數(shù)ADD(n)、SUB(n)>MUL(n)、DIV(n)分別表示程序P中，所使用的加、減、乘、除操作的次數(shù)。在應(yīng)用中大都是估算運(yùn)行時(shí)間。估算的方法往往用所有操作之中，最多的操作次數(shù)，作為該程序的時(shí)間復(fù)雜性。算法的時(shí)間相當(dāng)于程序時(shí)間中的運(yùn)行時(shí)間部分。同樣，關(guān)鍵操作的次數(shù)對時(shí)間復(fù)雜性的影響最大。假設(shè)，算法中關(guān)鍵操作執(zhí)行的次數(shù)是問題特征(規(guī)模)n的某個函數(shù)f(n)。那么，算法的時(shí)間量度(復(fù)雜性)記作：T(n)=O(Rn))它表示隨問題特征n的增大，算法中關(guān)鍵操作執(zhí)行次數(shù)(時(shí)間)與f(n)也增大，而且算法中關(guān)鍵操作執(zhí)行時(shí)間的增長率和f(n)的增長率相同。所以稱f(n)為算法的時(shí)間復(fù)雜性。算法中語句操作執(zhí)行的次數(shù)又稱為頻度.在實(shí)際中，用算法中語句的最大頻度，作為算法的時(shí)間復(fù)雜性。4算法的空間復(fù)雜度算法的空間相當(dāng)于程序所需空間中的可變空間部分SP。所以，算法所需空間的量度記作： S(n>O(f(n))其中N為問題特征。表示除輸入和程序之外所需的額外空間。四、關(guān)于算法時(shí)間在考試中的類型：1,給定一個算法，估算其時(shí)間復(fù)雜度;時(shí)間與空間的關(guān)系.2,給定兩個算法，比較它們的語句最大頻度及時(shí)間復(fù)雜度；3,限定算法時(shí)間復(fù)雜度，編寫完成功能的算法；例如，設(shè)計(jì)用時(shí)間復(fù)雜度為。(n)級的算法，完成稀疏矩陣的轉(zhuǎn)置陣.StatusTransposeMatrixM,TSMatrix&T)(//M為原陣T為轉(zhuǎn)置T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){ 〃存在非零元素

q=1； 〃轉(zhuǎn)置矩陣T的下標(biāo)初值for(col=l;col<=M.nu;++col)//從M陣的第一列開始查找for(p=l;p<=M.tu;++p)〃從第一個非零元素開始if(M.data[p].j=col){ 〃找到非零元素所在列號T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i；T.data[q].v=M.data[p].v;++q；}returnOK;}算法的時(shí)間復(fù)雜性為O(nu*tu).若用其求m*n矩陣的轉(zhuǎn)置陣算法的時(shí)間復(fù)雜性為O(m*n*n).StatusFstTransposcSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T,tu=M.tu;if(T.tu){for(col=l;col<=M.nu;-H-col)num[col]=0;〃置初值，清空for(t=l;t<=M.tu;-H-t)++num[M.data[t].j];//計(jì)算每列非零個數(shù)copt=l; //得到第一列中第一個非零元素的位置for(col=2;col<=Mnu;—col)〃算每歹ij中第一個元素在T中的序號cpot[col]=cpot[col一11+num[col-1];for(p=l;p<=m.tu;++p){col=M.data[p].j;q=cpot[col];//當(dāng)前列第一非零元素地址Tdata[q].i=M.data[p].j;T.data[q].j=M.dara[p].i;T.data[q].v=M.data[p].v;-H-cpot[coI];}fbr}ifReturnOK;}該算法的時(shí)間復(fù)雜度為O(n)或O(m). cc-ccuperaiion第二部分線性表的順序存儲cenlefI一、線性表的順序存儲線性表的定義：有限序列1第二部分線性表的順序存儲cenlefI一、線性表的順序存儲線性表的定義：有限序列1、線性表的抽象數(shù)據(jù)模型線性表(al,a2,a3,…?an)的數(shù)據(jù)結(jié)構(gòu)：LinearList=(D,R)其中，D={aiIai￡D0,i=l,2,3.n,n=0}priornextretrieveupdatafind

InsertrdeletelocateR={N},N={<ai-l,ai>Iai-l,aieD0i=2,3,…,n}。DO為某個數(shù)據(jù)對象。2、順序存儲的實(shí)現(xiàn)在高級程序語言中，一般都用數(shù)組來描述順序存儲。在C語言中可用動態(tài)分配的一維數(shù)組描述如下。defineLIST_INIT_SIZE100//初次分配用戶預(yù)估空間量defineLISTINCREAENT10〃每次分配增量，一個元素占Typesetstruct{ 〃用空間量ElemType*elem;//數(shù)組指針表的基址intlength;//當(dāng)前長度，實(shí)際已存元素個數(shù)intlistsize;//任何時(shí)刻能存最多元素個數(shù)}SqList;空間量=最多元素個數(shù)*每次分配增量(每個元素占用空間量)。3、順序存儲上的運(yùn)算1)查找--隨機(jī)查找隨機(jī)查找是利用下面兩個計(jì)算公式計(jì)算所要求元素物理地址.A)已知要查找元素的邏輯地址號.邏輯地址(相對地址)是元素的位置序號；物理地址是元素在存儲介質(zhì)上真正的存儲地址.邏輯地址號轉(zhuǎn)換成物理地址的公式：LOC(ai)=LOC(aO)+i*L(L>=1)i為元素在存儲空間的位置序號(邏輯地址，i從0開始)。BF贊1要查找元素在表中的下標(biāo)號.由元素的下標(biāo)號計(jì)算物理地址的公式：LOC(ai)=LOC(al)+(i-l)*L(L>=1)i為元素在表中數(shù)據(jù)ai的下標(biāo).(i從1開始)注： L為每個元素占有的存儲單元數(shù)(增量)舉例：有線性表(al32a3a4...am),求元素a3的物理地址;在表中該元素的下標(biāo)是3,所以根據(jù)公式：LOC(ai)=LOC(al)+(i-l)*L(L>=1)有LOC(a3)=LOC(al)+(3-l)*L(L>=1)=99+2*1=101又a3在內(nèi)存的邏輯地址是2,所以根據(jù)公式：LOC(ai)=LOC(aO)+i*L(L>=1)有LOC(a3)=LOC(aO)+2*L(L>=1)=99+2*1=101涉輯地址.0 1 2 3 m-1ala2a3a4am物理地址 ?99100101 102103... ....2)順序查找條件：不知要查找元素的邏輯地址和其在表中的元素下標(biāo)，已知要查找元素的值和表的長度.只能從表的一端開始逐一比較.StatusListSearch-Sq(SqList&L,inti,EIemTypee){i=l;(i為線性表元素的下標(biāo))While(i<=L.length&&L.elem[i-1]<>e)i++；if(i>L.length)returnERROR;elseretum(i?1);該算法的時(shí)間復(fù)雜度為O(n)。} 查找的有效范圍是0——length-10 1 2 3 ??? ???length-1ala2a3a4an問題：若要求時(shí)間復(fù)雜度不變，而要提高該算法的運(yùn)算速度，應(yīng)如何修改該算法？為提高實(shí)際查找速度，1)查找的有效范圍改為1—length；2)將控制循環(huán)查找的兩個條件去掉一個；3)引入輔助單元(0單元作為輔助空間)。其算法如下：StatusListSearch-Sq(SqList,&L,key,Typekey){L.elem[0]=key;〃將被查數(shù)據(jù)存放到0單元i=length;〃查找起始位置為高端While(!EQ(L.elem[i].key,key)〃循環(huán)查找■?i；if(i<l)returnERROR;〃超處查找范圍查找失敗returni; 〃查找成功}Search-seq0 1 2 3 4 lengthcabcd???n3)插入運(yùn)算(1)在給定表中查找插入位置.(順序或結(jié)合其他查找方式)(2)移動相關(guān)數(shù)據(jù)為新數(shù)據(jù)準(zhǔn)備空間.(3)插入新數(shù)據(jù).(4)修改當(dāng)前長度.例題知線性表順序存儲，設(shè)計(jì)算法查找一個值為X的元素，若不存在將新元素X插入到表的首部;若存在將其刪除.StatusListInsert-Sq(SqList&L,inti,ElemenTypee){i=l；(i為邏輯線性表的下標(biāo))While(i<=L.length&&L.elem[i-1]<>x)i++；if(i<L.length)p=&(L.elem[i-1]);〃P要被刪除數(shù)據(jù)的地址x=*p; //把刪除的數(shù)據(jù)放到x中q=L.elem+L.length-1; 〃需移動的最后數(shù)據(jù)的位置for(++p;p<=q;-H-p)*(p-l)=*p； 〃移動數(shù)據(jù)--L.length; //長度減1returnOK;}Else{if(L.length>=L.listsize){ 〃預(yù)定義空間用完newbase=(ElemType*)realloc(L.elem,(L.listsize+LlSTINCREMENT)*sizeof(ElemType));

//動態(tài)再分配if(inewbase)exit(OVERFLOW);//動態(tài)再分配if(inewbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}ifq=&(L.elem[i-l]);for(p=&(L.elem[L.length-1]);p>=q;—p)*(p+l)=*p；*q=x;++L」ength;returnOK;}〃再分配失敗〃新基值〃增加存儲容量//保存插入位置//移動相關(guān)數(shù)據(jù)為新數(shù)據(jù)插入準(zhǔn)備空間//插入新數(shù)據(jù)//長度增加1}（i為邏輯線性表元素的卜標(biāo)與該元素的邏輯地址差1）4）刪除運(yùn)算條件：刪除表中第i個元素StatusListDelete-Sq(SqList&L,int,ElemType&x){if(L.length=0)returnERROR;if((i<l)〃(i>L.length))returnERROR;p=&(L.elem[i-1]);〃P要被刪除的位置x=*p; //把刪除的數(shù)據(jù)放到x中q=L.elem+L.length-1; //需移動的最后數(shù)據(jù)的位置? for(++p;p<=q;-H-p)*(p-l)=*p;//移動數(shù)據(jù)--L.length; //長度減1returnOK;?(i為邏輯線性表元素的下標(biāo)與該元素的邏輯地址差1)例題順序存儲，且元素遞增有序.，若不存在插入，保持原序;若存在刪除.(要求省時(shí)間)voidInsertSq-list(SqList&L){low=0;high=L.Iength-l;while(low<=high){ //在子表中查找插入位置m=(low+high)/2;ifeq(x,Lelem[m]){for(j=m+l;j>=L.length-L.elem[j-1]= 刪除L.length=L.length-l;}elsehigh=m-l;//插入點(diǎn)在低半?yún)^(qū)elselow=m+1;}whilefor（j=L.length-l;j>=high+l;-j）L.elem[j+1]=L.elemfj];〃記錄后移L.elem[high+1]=x;//插入L.length=L.length+l;}設(shè)有N個大小不等的數(shù)據(jù)組，順序存放在空間區(qū)D內(nèi)，總占用空間量為m,每個數(shù)據(jù)占有一個存儲單元.編寫將元素X插到第i個數(shù)據(jù)組末尾且屬該于數(shù)據(jù)組的算法.（15）1）若第i（i=n）個數(shù)據(jù)組直接插入。修改S[i]的長度。2）i《》n從數(shù)據(jù)組1開始查找i,然后移動相關(guān)數(shù)據(jù)，為新元素插入準(zhǔn)備位置，修改S[i+1]到S[n]數(shù)據(jù)絹地址與Sfil的長度。

L.lengthL.lengthvoidinsert-x(sqlist&L,inti,ElemTypex){If(i>=l&&i<=L.length){for(j=0,p=L.elem[j];j<=m;j-H-)//p=L.elem[j]不是空閑單元繼續(xù)查找p++; 〃求D區(qū)空閑空間的首地址if(i=L.length)//插入第n個數(shù)組，即最后一個。*p=x; //直接插入，不用修改else{ 〃插入第N個數(shù)組前）位置fbr(q=L.elem[i];p>=q;-p)//q=L.elem[i]第i）位置*(p+l)=*p; 〃將(p?l)位置數(shù)據(jù)移到(p*p=X;//插入，修改從第[i+1]個數(shù)據(jù)組開始到S[n]數(shù)據(jù)組地址for(q=&L.elem[i],p=&L.elem[L.length-l];p>=q;q~H~)〃后邊位置加1(*qM;}mH;}例題知順序存儲,且數(shù)據(jù)元素遞增有序.設(shè)計(jì)算法查找值為X的元素，若存在與直接前驅(qū)元素交換.若不存在將X插入,仍保持原序;.(要求省時(shí)間)voidInsertSq-list(SqList&L){low=0;high=L.length-1;while(low<=high){ //在子表中查找插入位置m=(low+high)/2;ifeq(x,Lelem[m]){if(m=l)exit;else{temp=L.elem[m];〃直接前驅(qū)元素交換L.elem[m]=L.elem[m+1];L.elem[m+1]=temp;}}elsehigh=m-l;//插入點(diǎn)在低半?yún)^(qū)elselow=m+1;}whilefor(j=L.length-l;j>=high+1;—j)L.elem[j+1]=L.elem[j];//記錄后移L.elem[high+1]=x;//插入

L.length=L.length+l;例：編寫把從線性表(ala2a3…an)中值為X的元素開始到an的所有元素順序倒置的算法。從a5=e開始到a9=I0123 4 5 6 7 8倒置前abcdefghiabcdihgfe0 1 23 4 5 6 7 8倒置后for(i；iW[i+n]/2){an-1+1temp=l.element[i-1]；an-1+1l.element[i-l]=l.element[n-i+4]；l.clement[n-i+l]=temp}倒置類型題：1編寫把線性表(ala2a3…an)的順序完全倒置的算法。并計(jì)算該算法的時(shí)間復(fù)雜性及決定時(shí)間復(fù)雜性的語句頻度。與后面章中有聯(lián)系的問題：二叉樹的順序存儲;圖的順序存儲;查找;排序第三部分鏈表**基本概念與術(shù)語一、結(jié)點(diǎn)(node)線性表中一個數(shù)據(jù)元素所占用的存儲空間。它由數(shù)據(jù)域與指針域兩部分組成，數(shù)據(jù)域用來存儲用戶的有用數(shù)據(jù)；指針域用來存儲直接前驅(qū)或直接后繼數(shù)據(jù)元素所在結(jié)點(diǎn)的地址.1、含有一個直接后繼數(shù)據(jù)元素指針域的結(jié)點(diǎn)數(shù)據(jù)域指針域p n數(shù)據(jù)域指針域p n ?datanexttypedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;2、含有兩個指針域的結(jié)點(diǎn).一個直接前驅(qū)結(jié)點(diǎn)指針域，一個直接后繼結(jié)點(diǎn)指針域.在C語言中可用結(jié)構(gòu)指針來描述結(jié)點(diǎn)：prioudatanext前驅(qū)指針域數(shù)據(jù)域 后繼指針域TypedetstructDuLNode{ElemType data;前驅(qū)指針域數(shù)據(jù)域 后繼指針域structDuLNode*priou;structDuLNode*next;}DuLNode,*DuLinkList;二、單鏈表:

如果，構(gòu)成鏈表的每個結(jié)點(diǎn)都只含有一個指針域，那么稱這個表為單鏈表.1、不帶頭結(jié)點(diǎn)單鏈表；不帶頭結(jié)點(diǎn)的單鏈表的標(biāo)準(zhǔn)形式：不帶頭結(jié)點(diǎn)的單鏈表的空表標(biāo)準(zhǔn)形式:H=NULL.2、帶頭結(jié)點(diǎn)單鏈表的標(biāo)準(zhǔn)形式.首部結(jié)點(diǎn)C6A］尾結(jié)點(diǎn)帶頭結(jié)點(diǎn)的空單鏈表標(biāo)準(zhǔn)形式.L->next=NULL首部結(jié)點(diǎn)C6A］尾結(jié)點(diǎn)帶頭結(jié)點(diǎn)的空單鏈表標(biāo)準(zhǔn)形式.L->next=NULL三、循環(huán)單鏈表：1、不帶頭結(jié)點(diǎn)的循環(huán)單鏈表;四、雙向鏈表（循環(huán)，不循環(huán)）1、不帶頭結(jié)點(diǎn)的循環(huán)雙向鏈表;（略）2、帶頭結(jié)點(diǎn)循環(huán)雙向鏈表；空表結(jié)構(gòu)**基本運(yùn)算和例題一、單鏈表的插入運(yùn)算1,首部插入（生成結(jié)點(diǎn)，插入結(jié)點(diǎn)）2,尾部插入（查找尾部結(jié)點(diǎn)，生成結(jié)點(diǎn)，插入結(jié)點(diǎn)）3,條件插入（查找條件結(jié)點(diǎn),保存前驅(qū)結(jié)點(diǎn)，生成結(jié)點(diǎn)，插入結(jié)點(diǎn)）將y插入到將y插入到x之前Statusinsert-list(){Statusinsert-list(){p=h;ifp=nullreturnERROR;if(p->data<>x&&p->next<>null){q=p->next;while(q->data<>x&&q->next<>null){P=q；q=q->next;}}ifl(q->data=x)s=(LinkList)malloc(sizeofifLNode))s->data=y;Statusinsert-list(){P=L;q=p->next;while(q->data<>x&&q->nextonull){P=q;q=q->next;}if(q->data=x)s=(LinkList)malloc(sizeof(LNode))；s->data=y;s->next=p->next;P->next=s;s->next=p->next;P->next=s;）二、單鏈表的刪除運(yùn)算1,首部刪除（結(jié)點(diǎn)，釋放結(jié)點(diǎn)）.2,尾部刪除（查找尾部結(jié)點(diǎn)，保存前驅(qū)結(jié)點(diǎn),釋放結(jié)點(diǎn)）.3,條件刪除（查找條件結(jié)點(diǎn)，保存前驅(qū)結(jié)點(diǎn),釋放結(jié)點(diǎn)）.

三、循環(huán)單鏈表的插入與刪除:可以從表中任意已知地址查遍全表例題：Josephus問題:n個人圍成圓圈，從第s個開始計(jì)數(shù)到m,便將其刪除，從下一個開始，重復(fù)上述過程,直到所有人都刪除.Statusinsert-list(L){(不循環(huán))Statusinsert-list(L){(不循環(huán))P=L;q=p->next;while(q->data<>x&&q->nextonull){P=q;q=q->next;}if(q->data=x)s=(LinkList)malloc(sizeofi(LNode))s->data=y;s->next=p->next;P->next=s;Statusinsert-list(Lc){P=Lc;q=p->next;(循環(huán))

while(q->data<>x&&q->nextoLc){

P=q;q=q->next;}

if(q->data=x)

s=(LinkList)malloc(sizeof(LNode))；

s->data=y;s->next=p->next;P->next=s;Av為可用鏈表,lc為一數(shù)據(jù)無用的循環(huán)鏈表,要求用最少的時(shí)間把1c表與Av為可用鏈表,lc為一數(shù)據(jù)無用的循環(huán)鏈表,要求用最少的時(shí)間把1c表與Av連接在一起.LcAv=pav(1)建立一個含有n個結(jié)點(diǎn)的循環(huán)單鏈表jos?clist.#definefalse0#definetrue1(2)從第s個開始查找，輸出和刪除m#definefalse0#definetrue1{PNodep,q;(構(gòu)成循環(huán)鏈表)IntI;Typedefintdatatype;StuctNode;TypedefstuctNodepelist=p->link;PNode;pelist=p->link;StuctNode{datatypeinf;PNodelink;}；TypedefstuctNode*LinkList;Intinit_clink(PLinklistpclist,int,n)voidJosephus(PLinkIistpelist,ints,intm){PNodep,pre;intI;p=*pelist;if(s=l){pre=p;p=p->link;While(p!=*pelink){pre=p;p=p->link;})elsefbr(i=l;i<s;i-H-){pre=p;p=p->link;}While(p!=p->link){fbr(i=l;i<s;i++){pre=p;p=p->link;}prineflfUoutelement:p->infb)if(*pelist=p)q=(PNode)malloc(sizeof(stuctNode));Ifi(q=null)return(false);*pclist=q;Q->inf=1;q->link=q;If(n=l)return(true);For(i=2;i<n+l;i++){p=(PNodc)malloc(sizeofl(stuctNode)):Ifi(p:=null)return(false);p->inf=l;p-<link=q->link;q->link=p;q=pj/尾部插入)Pre->link=p->link;Free(p);p=Pre->link;}prinef(<4outelement:p->infb);*pelist=nullFree(p);)主程序Mia(){linklistjos-clist;intn,sm;Printfi("input"n);Scanfi(&n);Printf("input”s);Scanf(&s);PrintR“input"m);Scanfi(&m);Ifi(init-clink(&jos-clist,n))Josephus-clink(&jos-clist,s,m);Else print出“outofspace");四、循環(huán)雙向鏈表上的操作1、循環(huán)雙向鏈表上的插入2、循環(huán)雙向鏈表上的刪除插在P的后 插在P的前S->next=p->next; S->priou=P->priou;S->priou=p; S->next=p;P->next->priou=s; P->priou->next=s;P->next=s; P->priou=s;P為雙循環(huán)鏈表中任意一結(jié)點(diǎn)地址，設(shè)計(jì)用最少的輔助空間將P與其直接后繼結(jié)點(diǎn)交換的語句P->next->priou=p->priou;(1)P->priou->next=p->next;(2)p->priou=P->next;(3)例題：1、假設(shè)AB為按元素值遞增排列的單鏈表.編寫算法將AB歸并成一個按元素值遞減的C表(C中可以有相同元素;沒有相同元素).1)AB保留，生成C表;2)AB不保存，用其空間生成C表.LB 1 _叵衛(wèi)~卜30|_:0|八算法描述：(1)設(shè)定A為C表.并將其倒置.(2)qa,qb分別為兩表中當(dāng)前結(jié)點(diǎn)指針.(3)當(dāng)qa,qb都存在時(shí)重復(fù)：比較qa,qb結(jié)點(diǎn)數(shù)值，若qa<qb,將qb插到C表之前.若qa=qb,將qaqb分別插到C表之前.(4)當(dāng)qa空時(shí)，把qb剩余逐個插到C表之前；(5)當(dāng)qb空時(shí)，把qa剩余逐個插到C表之前；算法LA —> —? —? ——? 7\LB —卜21I-I150八voidmrege(linklist&pajinklist&pb){Lc=la;〃A表作為結(jié)果表qa=la?>next;〃第一個結(jié)點(diǎn)lc->next=null;//結(jié)果表置空qb=lb->next;while(!qa){//A表倒置ra=qa->next;qa->next=lc->next;lc->next=qa;qa=ra;}qa=lc->next;pre=Lc;while(!qb){while(qa->data>qb->data&&qa->next)//qa的數(shù)大{pre=qa;qa=qa->next;}if(qa->next=null){u=qb->next;qb->next=qa->next;qa->next=qb;qb=u);}if(qa->data<=qb->data)//qa的數(shù)值小,qb前插入{u=qb->next;qb->next=pre->next;pre->next=qb;pre=qb;qb=u;)}例2知A,B,C為三個單鏈表數(shù)據(jù)遞增有序，要求對A作如下處理:刪除與BC中相同的數(shù)據(jù)；vioddelet(linklist&la){pa=la;qa=la->next;qb=lb->next;qc=lc->next;while(!qc&&qb->data<>qc->data&&!qb){〃找出BC中所有相同元素qb=qb->next;

if(qb->data=qc->data){qb=qb->next;〃修改qb〃并刪除while(!qa&&qa?>dataoqc?>data)〃找出C中A中所有相同元素〃并刪除{pa=qa;qa=qa->next;}if(qa->data=qc->data){pa->next=qa->next;free(qa);qa=pa->next;}}qc=qc->next;〃修改3、（12分）假設(shè)一個有向圖G已經(jīng)以十字鏈表形式存儲在內(nèi)存中，試寫一個判斷該有向圖中是否有環(huán)（回路）的算法。解：對十字鏈表儲存結(jié)構(gòu)的有向圖采用拓?fù)渑判騍tatustoposort（OLGraphG）{findindegree(G,indegree);InitQueue(Q);Count=0;fbr(i=O;i<G.Vemum;i-H-)ifi(GVer[i].indegree=O)Enqueue(Q,i);findindegree(G,indegree);InitQueue(Q);Count=0;fbr(i=O;i<G.Vemum;i-H-)ifi(GVer[i].indegree=O)Enqueue(Q,i);While(!QueueEmpty(Q))Dequeue(Q,i)；Count-H-；P=Gver[i].firstout;while(p)(j=pfheadvex;〃對各頂點(diǎn)求入度〃隊(duì)列初始化〃計(jì)數(shù)器初始化〃入度為零的頂點(diǎn)入隊(duì)〃隊(duì)頭出隊(duì)〃取鄰接點(diǎn)〃處理鄰接點(diǎn)的入度Gver[j].indegree—Gver[j].indegree—;ifi(Gver[j].indegree==O)Enqueue(Qj);〃頂點(diǎn)j入隊(duì)p=pftlink;//指針后移}//while}//whileif((count<G.vemum)returnERROR;//有環(huán)elsereturnOK;elsereturnOK;}//toposortStatusfindindegree(G,indegree){(根據(jù)十字表計(jì)算每個頂點(diǎn)的入度數(shù)填到入度域)Count=0；fbr(i=O;ivG.Vemum;i++){〃循環(huán)p=G[i]oFirstin//while(p!=null)

{count=count+l；p=p-*next；}whileG[i]Indegree=count；}for}雙向循環(huán)鏈表Id為表頭結(jié)點(diǎn)地址LDsLDsviodchang-f(linklist&ld){(按使用頻度大小排列)q=ld->next;q->freq=0;While(q->priou<>ld) 〃置所有頻度初值{q->ferq=O;q=q->next;}scanfifx);while(x<>0){LOCATE(L,X))q->freq=q->freq+l;p=q->priou;while(pold&&p->freq<q->freq)p=p->freq;if(!(p->freq<q->freq)){q->next->priou=q->priou;q->priou->next=q->next;q->next=p->next;q->priou=p;p->next->priou=q;p->next=q;}scanf(x)）；}十字鏈表靜態(tài)鏈表其構(gòu)成：是按順序方式分配空間，是由用戶自己構(gòu)造的結(jié)點(diǎn)來形成的一種鏈表。其結(jié)構(gòu)類型說明如下：#defineMAXSIZE100 〃所需的最大空間量//初始備用空間鏈//初始備用空間鏈typedefstruct{ElemTypedata;//數(shù)據(jù)域intcur; 〃指針域}component,SLinkList[MAXSIZE];voidInitspace_SL(SLinkList&space){for(i=0;i<MAXSIZEspace[i].cur=i+1;space[MAXSIZE-l].CUR=0;}Initspace_SL由由圖可以看出space[0].cur=1;〃第一個空閑結(jié)點(diǎn)space[l].cur=2;space[2].cur=3;space[3].cur=4;space[4].cur=5;space[6].cur=7;space[7].cur=0備用鏈上的刪除運(yùn)算(把一個結(jié)點(diǎn)分配給用戶)當(dāng)用戶申請一個結(jié)點(diǎn)時(shí)，下邊的算法就把備用鏈中的第一個空閑結(jié)點(diǎn)分配給用戶。IntMallocSLfSLinkList&space){i=spacc[O].cur;if(space[0].cur)space[0].cur=space[i].cur;returni;}MallocSL備用鏈上的插入運(yùn)算 把用戶釋放的一個結(jié)點(diǎn)返回備用鏈供用戶再次使用。voidFree_SL(SLinkList&space,intk){space[k].cur=space[0].cur;space[0].cur=k;//采用首部插入}Free_SL假設(shè)集合A=(c,b,egf,d);B=(a,b,n,f),那么(A?B)U(B-A)為(c,e,g,d,n,a).0809備用鏈為0,6,9,10,llo數(shù)據(jù)鏈頭指針備用鏈表為212C32c4343n88,9,10,11共有4個空閑單元。-4e5-1eb數(shù)據(jù)鏈表5g65g7為：2,4,6f76f95,7,3,數(shù)據(jù)鏈表為：r2,3,4,5,6,7共有6個數(shù)據(jù)結(jié)點(diǎn)。一1d0r下d38o共有6個數(shù)據(jù)結(jié)點(diǎn)898a09109101011101111()110圖2-14集合Avoiddifference(SLinkList&space,int&s){InitSpacc_SL(spacc);

s=Malloc_SL(Space);r=s;scanffm,n);for(j=s=Malloc_SL(Space);r=s;scanffm,n);for(j=l;j<=m;++j){i=MallocSL(space);scanf(space[i].data);space[r].cur=i;r=i;space[r].cur=0;for(j=l;j<=n;++j){//R指向最后結(jié)點(diǎn)//輸入A和B的元素個數(shù)//建立集合A的鏈表//分配結(jié)點(diǎn)//輸入A的元素值//插入到表為尾//尾結(jié)點(diǎn)的指針為空//輸入B的元素在表A中查找是否存在scanfifb);p=s;k=space[s].cur;//k指向A的第一個結(jié)點(diǎn)，P為前驅(qū)while(k!=space[r].cur&&space[k].datd!=b){//在當(dāng)前表中找p=k;k=space[k].cur;}if(k=space[r].cur){〃表中沒有該元素，插在r所指點(diǎn)后r位置不變i=MallocSL(space);space[i].data=b;space[i].cur=space[r].cur;space[r].cur=i}ifelse{ //該元素在表中，刪除space[p].cur=space[k].cur;free_SL(space,k)if(r=k)r=p; 〃若刪除的是尾元素，則修改尾指針}else}for}defference注r位置后邊的元素都是B表中插入的元素，不用比較所以r不用改。單鏈表倒置.L 卜〃iTa12Hb =倒置前后一］十d倒置前后實(shí)現(xiàn)算法如下:statusListReverse_L(LinkList&L){P=L->next;〃保存第一個結(jié)點(diǎn)L->next=NULL;//將原表置成空表While(p){s=p->next;//保存直接后繼p->next=L?>next;〃首部插入L->next=p;P=s；}returnOK;

}該算法是達(dá)到同樣要求的所有算法中利用輔助空間最少的一個。倆表合并A=x+2x2-4x3+3x4B=2+3x+4x3-x$A=((1,1),(2,2),(-4,3),(3,4))；B=((2,0),(3,1),(4,3),(-1,5))；PaPbPaPb多項(xiàng)式各項(xiàng)生成的單鏈表假設(shè)La,Lb分別為兩個單鏈表的頭結(jié)點(diǎn)指針，m,n分別為兩表的長度。要求把兩表聯(lián)接成一個表(需要較少的時(shí)間)。實(shí)現(xiàn)算法如下：voidUnionList_L(LinkList&La,LinkList&Lb,linklist&Lc){if(m<n){p=La->next;Lc=La;q=Lb：}if 把兩表聯(lián)接else{p=Lb->next;Lc=Lb;q=La} La I『pFrwhile(!P->next)p=p->next;p->next=q->next;儂(哂 Lb—{7/T] 卜bH一卜cI—TTTreturn(Lc);例：(17分)設(shè)有?個正整數(shù)序列組成的有序單鏈表(按遞增次序有序，且允許有相等的整數(shù)存在)，試編寫能實(shí)現(xiàn)下列功能的算法乂要求用最少的時(shí)間和最小的空間)(00)確定在序列中比正整數(shù)x大的數(shù)有幾個(相同的數(shù)只計(jì)算?次，如序列(20,20,17,15,15,11,10,8,7,7,5,4)中比10大的數(shù)有5個)；在單鏈表中將比正整數(shù)x小的數(shù)按遞減次序排列；在單鏈表中將比正整數(shù)x大的偶數(shù)從單鏈表中刪除；解：voidexam(Linklist,La,int,x){p=La-*next;q=p;k=0; //p為工作指針pre=la;lafnext=NULL;.〃q指最小元素while(p&&p-*data<x){〃比x小的數(shù)遞減r=p->next;p->next=La-^next;La-*next=p;p=r;〃置逆}//whileq-next=p;pre=q;〃重新鏈接while(p->data=x){//考察等于x的情況pre=p; p=pfnext;}//whilewhile(p){〃k為計(jì)數(shù)器k++;x=p->data; 〃避免重復(fù)計(jì)算if(x%2=0){ 〃刪除偶數(shù)while(p-*data=x)(//考察等于x的情況u=p;p=pfnext;free(u);}//whilepre->next=p;}//ifelse//處理奇數(shù)whileCp->data=x){pre—next=p;pre=p;p=p-*next;}//while}//while(p)}//exam例：已知L為沒有頭結(jié)點(diǎn)的單鏈表中第一個結(jié)點(diǎn)的指針，每個結(jié)點(diǎn)數(shù)據(jù)域存放一個字符，該字符可能是英文字母字符或數(shù)字字符或其它字符。編寫算法構(gòu)造三個以帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示的線性表，使每個表中只含有同一個類字符。(要求用最少的時(shí)間和最少的空間)(15分)解：PROCA(L：linkisttp;VARLetter,Digit,Other:linkisttp);new(Letter);new(Digit);new(Other);Letter*.next:=Letter;Digif.next:=Digit;Other\next:=Other;Whilel<>nildo[p:=L;L:=L".next;if(p\data>=,a,Andp\data<=,z,)Or(p\data>=,A,Andp\data<=*z')Then[p*.next:=Letter.next; letter*.next:=p;Letter:=p]else[iftp*.data>=,O'Andp*.data<=,9')then[p\next:=DigiC.next;Digit".next:=p;Digit:=p]else[p".next:=Other*.next;Other*.next:=p;Other:=p]]ENDP;例：(15分)已知f為單鏈表的表頭指針，鏈表中存儲的都是整型數(shù)據(jù)，試設(shè)計(jì)算法將此鏈表的結(jié)點(diǎn)按照遞增次序進(jìn)行就地排序。voidInsertSort_L(Linklist&La){〃用直接插入排序使鏈表遞增有序if(La-next){〃鏈表不空p=La->nextfnext;La—nextfnextfNull;while(p!=Null){r=pfnext;〃暫存p的后繼q=La;while(q-*next&&q-*-next->data<p-*data){q=qfnext;〃查找插入位置p->next=qnext;〃插入q-*next=p;p=r;}//while}//if//InsertSortL例：(20分)某商店有一批手機(jī)，按價(jià)格從高價(jià)到底構(gòu)成一個單鏈表，結(jié)點(diǎn)包括數(shù)量、價(jià)格、指針?，F(xiàn)新到n臺價(jià)格不同的手機(jī)，編寫將新到手機(jī)插入到原鏈表中的算法。解：定義此單鏈表的結(jié)點(diǎn)結(jié)構(gòu)：typedefstructLnode{intnumber://數(shù)量域intvalue： 〃價(jià)格域structLnode*next;〃指針域}Lnode,*Linklist;voidinsertlink(Linklist&L,intn){〃將新到n臺價(jià)格不同的手機(jī)插到有序鏈表中fbr(i=l;i<=n;i++){Scanf(&price); //讀入每臺手機(jī)價(jià)格S=(Linklist)malloc(sifeof(Lnode));Sfvalue=price;s number=1;P=L->next;if(p-*value<s—value){〃插入首部Snext=L-*next;L->next=s;}//ifelse{while(p->next&&(p-*next-*-value>svalue))p=p-*next;if(!pfnext){〃插入表尾s—next=pfnext;p->next=s;}//ifelseifi(p—nextfvalue=svalue)pfnextfnumber++;else{s->next=pnext;p—next=s;}//else}//fbr練習(xí)題：1、把上題以單鏈表的存儲形式再編寫算法.2、知有正整數(shù)組成的無序單鏈表，編寫完成下列功能的算法:(1)找出最小值結(jié)點(diǎn),并打印輸出.(2)若該數(shù)值是奇數(shù),將其與直接后繼交換.(3)若該數(shù)值是偶數(shù),將其與直接后繼刪除.(00)

3、單鏈表存儲的數(shù)據(jù)是按遞增有序且都是正整數(shù)，編寫完成下列功能的算法（用最少的時(shí)間和空間）:（1）計(jì)算比X大的數(shù)有幾個？（相同的計(jì)算一次）.（2）將小于X的部分表倒置.（3）將大于X的部分表中的偶數(shù)刪除.（01）4、L為無頭結(jié)點(diǎn)單鏈表的第一個結(jié)點(diǎn)指針，每個結(jié)點(diǎn)存放一個字符，該字符可能是英文字母或數(shù)字或其他字符.編寫構(gòu)造三個帶頭結(jié)點(diǎn)循環(huán)單鏈表的算法.每個表中只含一類字符.（時(shí)空）.（02）5,L為單鏈表頭結(jié)點(diǎn)指針，數(shù)據(jù)都是正整數(shù)，設(shè)計(jì)算法按遞增就地排序.（03）6、知手機(jī)價(jià)格按遞減構(gòu)成單鏈表，現(xiàn)有N臺新的價(jià)格不同的手機(jī)，編寫把它們插到表中合適位置的算法.（04）7、（15分）已知遞增有序的單鏈表AJB分別存儲了一個集合，請?jiān)O(shè)計(jì)算法以求出兩個集合A和B的差集A-B（即僅由在A中而不在B中出現(xiàn)的元素所構(gòu)成的集合），并以同樣的形式存儲。要求用最少的時(shí)間。（05）8、（17分）設(shè)單鏈表的表頭指針為h,結(jié)點(diǎn)結(jié)構(gòu)由data和next兩個域構(gòu)成，其中data域?yàn)樽址?。編寫算法，判斷該鏈表的前n個字符組成的是否為回文，要求使用棧和隊(duì)列。（回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。）（06）第四部分棧隊(duì)列一、棧棧是允許數(shù)據(jù)元素的插入與刪除從表的同一端進(jìn)行的一種線性表（即輸入、輸出受限的一種線性表）棧上運(yùn)算的最大特點(diǎn)是：先進(jìn)后出或后進(jìn)先出（FILO、LIFO）。?？梢杂庙樞蚍绞綄?shí)現(xiàn)，也可以用鏈?zhǔn)綄?shí)現(xiàn)。opreation data允許數(shù)據(jù)元素插入、刪除的一端稱為棧頂另一端稱為棧底端；棧頂指示器用top表;一)順序存儲的棧:用C語言棧的順序存儲表示如卜：//defineSTACKJNIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*bot;SEIemType*top;intstacksize;}SqStack;1、棧頂動進(jìn)棧退棧時(shí)棧頂指示器移動stackelementerrorTop=boot=0;boot不動，數(shù)據(jù)進(jìn)退棧由Top指示,

數(shù)據(jù)進(jìn)棧后Top+1,Top靜態(tài)位置為新數(shù)據(jù)要存放的位置。退棧時(shí)Top要先減1。stackelementerrorTop=boot=0;boot不動，數(shù)據(jù)進(jìn)退棧由Top指示，。單元不存放數(shù)據(jù)，Top=Top+l的 枝頂端位置，為進(jìn)棧數(shù)據(jù)的位置，也就是要退 3 I——棧數(shù)據(jù)的位置。 ； 2、棧底動進(jìn)棧退棧時(shí)棧底指示器移動 ； Top=boot=nnTop不動，數(shù)據(jù)進(jìn)棧后 ：一Boot-1,boot靜態(tài)位置為新數(shù)據(jù)要存放的位置。 2 輸入abcde，經(jīng)過一個棧處理，是否能得到： TOP，二 對于一個非空棧，棧頂指示器始終是在當(dāng)前棧頂數(shù)據(jù)元素位置 迄二 *s.top-H-=*s.top-H-=e;returnOK;//把數(shù)據(jù)進(jìn)棧后TOP再加1加1的位置上。用C語言編寫的算法如下： 棧頂端StatusPush(SqStack&,SElemTypee){ Top ,if(S.top-S.bot>=S.stacksize){ 〃判預(yù)分空間是否用完 bootS.bot=(SElemType*)realloc(S.bot//動態(tài)再分配空間—m(S.stacksize+STACKINCREMENT)*sizeofi(SElemType));if(!S.bot)exit(OVERFLOW); //空間分配失敗S.top=S.bot+S.stacksize; 〃修改棧頂指示器S.stacksize+=STACKINCREMENT:3、設(shè)共有m個連續(xù)空間單元，要求分成2個棧，每個棧容量不知且不相等.要求在任何時(shí)刻存儲數(shù)據(jù)個數(shù)只要小于m便能滿足用戶的需要./Topi=0 |Top2=m-1boot1=0U乂iboot2=m-10 1 2 m-1Top2=m-1Boot2=m-1Top2=m-1Boot2=m-1Boot1=0判兩個棧是否滿是關(guān)鍵if(topl>top2)或if(top2<topl)4、多個棧的設(shè)計(jì)設(shè)共有m個連續(xù)空間單元，要求分成n(n>2)個棧,每個棧容量不知且產(chǎn)】等空理灣遨翅分配空.間;■警再今照聞…Topi=0'bootl=Topi=0'bootl=0Top2=4boot2=4Topi=(i-1)*m/nbooti=(i-1)*m/nBoot(n+1)=m-11)靜態(tài)預(yù)分配空間假使每個棧容量相等為m/n,則每個棧的棧頂,棧底初始位置便可以確定.for(i=l,i<=n,-*-+i){Topi=(i-l)*m/n;booti=(i-l)*m/n)Boot(n+l)=m-l;5、多個棧上的操作0 1 2 345 6 ii+1 m-1Top1=01bootl=0 1 2 345 6 ii+1 m-1Top1=01bootl=0Top2=3boot2=3Topi=(i-1)*m/nBoot(n+1)=m-1booti=(i-1)*m/n**當(dāng)數(shù)據(jù)耍進(jìn)第i個棧時(shí)若預(yù)分空間沒有用完，可按單個棧操作.關(guān)鍵是如何判斷第i個棧是否滿？理論上講，如果第i個棧的棧頂指示器的值與第i+1個棧的棧底指示器的值相等，則說明預(yù)分空間用完。實(shí)現(xiàn)時(shí)可用下面語句:if(topi!=boot(i+l)) 〃分空間沒有用完if(topi=boot(i+l)) 〃預(yù)分空間用完若預(yù)分空間已經(jīng)用完2)動態(tài)再分配空間(查找空閑單元)首先向右查找最小的j,即第j個棧與第j+1個棧之間有空閑單元;While(topj=botj+1)j=j+l;其次，移動從第i+1個棧到第j個棧之間的元素，把一個空閑單元到與第i個棧的棧頂相鄰處供第i個棧使用.實(shí)現(xiàn)語句：For(k=topj-l;k=boti+l;k-)S[k+1]=S[k]最后，把第i+1個棧到第j個棧的棧頂、棧底指示器都向右移動一個位置。For(k=i+l;k<=j;k++)top[k]=top[k]+lboot[k]=boot[k]+16、棧上的基本操作進(jìn)棧Push(s,top);退棧Pop(s,top);注意*一般正常操作每個數(shù)據(jù)只進(jìn)一次棧，退一次棧.*棧頂指示器top的兩種使用方式： top若top指示棧頂元素所在的實(shí)際位置，則新元素進(jìn)棧前top+1;若top指示棧頂元素實(shí)際位置的下個位置，則新元素進(jìn)棧后top+1.5棧應(yīng)用例1)兩個棧的設(shè)計(jì)(00).2)把串3*-y-a/yA2改為3y-*ay2A/-,X,S分別代表一次進(jìn)退棧，寫出操作步驟.XSXXXSSSXXSXXSXXSSSS.(Ol)3)從左向右釋放二叉樹所有葉子結(jié)點(diǎn)，并將它們存放在一向量中.(02)7、鏈?zhǔn)綏４鎯σ粋€數(shù)據(jù)元素的空間單元為結(jié)點(diǎn)。數(shù)據(jù)操作滿足棧的先進(jìn)后出，其他操作滿足鏈表特點(diǎn)。Top右圖為線性表(abcde)棧頂按順序輸入構(gòu)成的鏈?zhǔn)綏?。顯然,從圖中可以看出數(shù)據(jù)a是第 一-———?個進(jìn)棧的元素.所以，它將是最后出棧的?個數(shù)據(jù)。而數(shù)據(jù)c是top最后進(jìn)棧的元素，但它確是第一個出棧的元素。這部分內(nèi) |d|容比較簡單.，學(xué)生自己可以編寫有關(guān)的進(jìn)棧、退棧的算法。舉例：算術(shù)表達(dá)式計(jì)算求值算法的基本思想是：(1)首先置操作符棧OPTR為空，表達(dá)式起始符"#"為運(yùn)算符棧的棧底元素。(2)依次讀入表達(dá)式中每個字符，若是操作數(shù)則進(jìn)OPND棧，若是運(yùn)算符則和OPTR棧的棧頂運(yùn)算符比較優(yōu)先權(quán)，若棧頂符號小于當(dāng)前C中符號的優(yōu)先級，則C中符號進(jìn)棧，否則退棧運(yùn)算。直到整個表達(dá)boot?a式求值結(jié)束。符號的優(yōu)先級查看書中給出的表。有算術(shù)表達(dá)式：3*(7-2) 棧底.求值過程描述步驟OPTR棧OPND棧輸入字符主要操作1#3*(7-2)#PUSH(OPND,3)2# 3*(7-2)#PUSH(OPTR,?)3#? 3(7-2)#PUSH(OPTR,(4#?( 37-2)#PUSH(OPND,7)5#?( 37-2)#PUSH(OPTR,-)6#?(- 372)#PUSH(OPTR,2)7#*(- 372)#OPREATE(7, 2)8#*( 35)#POP(OPTR)消除一對括號9#* 35#OPREATE(3,*,5)10# 15#RETURN(GETTOP(OPND)OperandTypeEvaluateExpression(){InitStack(OPTR);Push(OPTRJ#")；//運(yùn)算符棧OPTR置結(jié)束符#InitStack(OPND);c=getchar():〃數(shù)棧置空，并得到表達(dá)式中一個號While(c!="#"GetTop(OPTR)!=){ 〃c與OPTR棧頂不是#if(!In(c,op)){Push((OPNDE,c);c=getchar();}//數(shù)進(jìn)OPND棧elseswitch(Precede(GetTop(optr),c)){//棧頂符號與C進(jìn)行比較棧頂小casey'：Push(OPTR,c);c=getchar();break;〃運(yùn)算符號C進(jìn)棧case4=':Pop(OPTR,X);c=getchar();break;〃相等為()號case:Pop(OPTR,theta); 〃棧頂符號權(quán)高退棧,c中符號不變Pop(OPND,b);Pop(OPND,a); 〃退出棧頂元素a,bPush(OPND,Operatc(a,theta,b))break;; 〃運(yùn)算結(jié)果進(jìn)棧}switch}whilereturnGetTop(OPND);}算法執(zhí)行過程參考書中P54例3-1o例:有數(shù)據(jù)"al2b3c4de“要求經(jīng)過處理得到abed,4321設(shè)計(jì)結(jié)構(gòu)m-11 2m-11 2Top=m-1Boot=m-1請利用兩個棧S1和S2來模擬一個隊(duì)列。已知棧的三個運(yùn)算定義如下：PUSH(ST,x):元素x入ST棧；POP(ST,x)：ST棧定元素出棧，賦給變量x;sempty(ST)：判ST棧是否為空。那么如何利用棧的運(yùn)算來實(shí)現(xiàn)該隊(duì)列的三個運(yùn)算：enquence:插入一個元素入隊(duì)列；dequence:刪除一個元素出隊(duì)列；quenceempty：判對列為空。m-11 2m-11 2Top1=0Boot1=001 2.出隊(duì)歹ir 隊(duì)頭frontala2a3an-1rearTop1=0Boot1=001 2.出隊(duì)歹ir 隊(duì)頭frontala2a3an-1rear隊(duì)尾?--n-1進(jìn)隊(duì)列出隊(duì)列- 隊(duì)頭隊(duì)尾frontrearTop2=m-1Boot2=m-1二、隊(duì)列抽象數(shù)據(jù)類型定義ADTQueue{數(shù)據(jù)對象：D={aiIaiGElemSet,i=l,2,3....n,n20}數(shù)據(jù)關(guān)系：RI={<ai-l,ai>Iai-l,aiGD,i=2,3,…n}基本操作：EnQueue(&Q,e)Q為非空隊(duì)列。插入元素e為Q的新隊(duì)尾。DeQueue(&Q,&e)Q為非空隊(duì)列。刪除Q的隊(duì)頭元素。隊(duì)列是允許數(shù)據(jù)元素從一端插入，而從另一端刪除的一種線性表。特點(diǎn)，先進(jìn)先出。即經(jīng)過隊(duì)列輸出數(shù)據(jù)的順序與輸入數(shù)據(jù)的順序完全相同。允許數(shù)據(jù)元素插入的一端稱為隊(duì)尾(rear),允許數(shù)據(jù)元素刪除的一端稱為隊(duì)頭(fh)nt)。假設(shè),q=(a1,a2,a3..…an)為隊(duì)列，其存儲形式如下圖所示。進(jìn)隊(duì)列是利用循環(huán)的方式安排使用隊(duì)列中有限空間的隊(duì)列。一個具有使用價(jià)值的循環(huán)隊(duì)列,是利用模數(shù)運(yùn)算來判斷隊(duì)列是否滿的循環(huán)隊(duì)列.注意 Q.fh)nt=Q.rear=O為初次隊(duì)列空的標(biāo)志；一個空滿循環(huán)隊(duì)列如下圖(1)示。Q.front指示要刪除元素的位置。Q.rear指示當(dāng)前隊(duì)尾元素的下一個位置。允許數(shù)據(jù)從一端輸入兩端輸出的，稱為輸入受限雙端隊(duì)列。?隊(duì)頭?隊(duì)尾?隊(duì)頭?隊(duì)尾2)輸出受限雙端隊(duì)列允許數(shù)據(jù)從一端輸出兩端輸入的，稱為輸出受限雙端隊(duì)列。隊(duì)頭隊(duì)尾示例:假設(shè)有隊(duì)頭隊(duì)尾示例:假設(shè)有m個連續(xù)的存儲單元，要求分成一個棧和一個隊(duì)列使用，每個容量不知且不相等，可以隨機(jī)進(jìn)入.隊(duì)首0 1 2 m-1 隊(duì)尾 4共用區(qū)間| 「棧底端例，用循環(huán)數(shù)組表示隊(duì)列，且只有一個首指針front,設(shè)一個計(jì)數(shù)器記錄隊(duì)列中個數(shù).1)編寫判空，入隊(duì)歹打出隊(duì)列;(2)隊(duì)列能容納數(shù)據(jù)最多個數(shù).(02)TYPEqu=ARRAY。..m?l]ofelemtp(l)FUNCempty(VARq:qu;VARfront,count;int):bollean;{if(count=0)empty=true;elseempty=false;}〃進(jìn)隊(duì)列FUNCenqueue(VARq:qu;VARfront,count;int;VARx:elemtp):bollean;{if(count==m)return;〃隊(duì)歹U滿elseJcount+4-;i=(front+count)MODm;q[i]=x}}PROCdequeue(VARq:qu;VARfront,count;int);{〃出隊(duì)歹Uif(count=0)empty;//隊(duì)歹性

else{front=(front+1)MODm;II修改首指針count—})}鏈?zhǔn)疥?duì)列隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)存儲數(shù)據(jù)的空間單元為結(jié)點(diǎn)。存儲結(jié)構(gòu)為單鏈表。操作滿足隊(duì)列先進(jìn)先出，以及單鏈表的運(yùn)算方式。一個空的鏈隊(duì)列完全類似一個空鏈表(如卜頁圖示)。一個鏈?zhǔn)疥?duì)列完全類似一個帶頭結(jié)點(diǎn)的單鏈表(如下圖示)：front鏈隊(duì)列的存儲結(jié)構(gòu)用C語言描述如下：TypedefstructQNode{〃結(jié)點(diǎn)結(jié)構(gòu)front鏈隊(duì)列的存儲結(jié)構(gòu)用C語言描述如下：TypedefstructQNode{〃結(jié)點(diǎn)結(jié)構(gòu)QEIemTypedata;structQnode*next;}Qnode,*QueuePtr;typeddefstruct{ （隊(duì)頭、隊(duì)尾定義）QueuePtrfront;QueuePtrrear:JLinkQueue;Q.frontQ.rear空鏈隊(duì)列進(jìn)隊(duì)列運(yùn)算功能：把新的元素e從隊(duì)尾插入，成為當(dāng)前隊(duì)列的隊(duì)尾。出隊(duì)列運(yùn)算功能：將一個非空隊(duì)列的隊(duì)頭元素刪除Q.front隊(duì)頭隊(duì)尾■|Q.front隊(duì)頭隊(duì)尾■|a—b-c——>dQ.rear第五部分串(一)串上的基本操作1賦值運(yùn)算Assign(s,ss);Creat(s,ch);2長度運(yùn)算Len(s)3求子串運(yùn)算Substr(I,j,length)4定位運(yùn)算 Index(s,t)聯(lián)接運(yùn)算Concat(T,sl,s2)替換運(yùn)算Rplace(s,t,v)(二)串的存儲1、串的順序存儲(1)串的定長順序存儲是用一個地址連續(xù)的存儲單元存儲字符串的字符序列。其實(shí)現(xiàn)的方法是按照用戶予定義的大小，系統(tǒng)為每個串的變量分配一個固定長度的存儲區(qū)。串的實(shí)際長度可在予定義長度的范圍內(nèi)隨意調(diào)整，超過予定義長度的串值將被舍去。(2)堆分配存儲這仍然是用一組地址連續(xù)的存儲單元存放字符序列，但它們的空間是在執(zhí)行過程中動態(tài)分配的.在C語言中存在一個稱為"堆''的自由存儲區(qū).C語言用函數(shù)malloc和free來管理.2、串的鏈表存儲1)數(shù)組(1)二維數(shù)組的存儲與尋址設(shè)有二維數(shù)組A,bl〈i〈dl,b2〈j〈d2,其按行主序存儲的尋址公式：Loc(aij)=L0+[(i-bl)*(d2-b2+l)+(j-b2)]*l按列主序存儲的尋址公式：Loc(aij)=L0+[(j-b2)*(dl-bl+l)+(i-bl)]*l其中L0為基址;1為每個數(shù)據(jù)元素占有的存儲單元.(2)特殊矩陣的壓縮存儲對稱陣;三角陣;帶狀(對角)矩陣N階時(shí)稱矩陣A中的元素滿足下述性質(zhì)aij=ajiIWiJWnN階對稱矩陣的存儲矩陣中的每一對對稱元素分配一個存儲空間，則可將n*n個元素壓縮存儲到n(n+1)/2個存儲空間中。假設(shè)以?維數(shù)組Sa[n(n+1)⑵作為n階對稱矩陣A的存儲結(jié)構(gòu)，則Sa[K]和矩陣元素aij之間存在著一一對應(yīng)的關(guān)系：i(i-l)/2+j-1 i2jK=j(j-l)/2+i-li<j對稱矩陣的壓縮存儲K=i(i-l)/2+j-1 iej.j(j-l)/2+i-l i<j對稱矩陣的壓縮存儲alla21a22a31a32a33an1an2an3....annalla21a22a31 an,l ... an,nK=0 1 2帶狀(對角)矩陣3 n(n-l)/2n(n+l)/2-l1)主對角線一i=j.2)主對角線之下的對角線(低對角線)一i=j+l.3)主對角線之上的對角線(高對角線)一三條對角線上的元素總數(shù)為3*n-2,故可用含有3*n-2個存儲空間的一維數(shù)組實(shí)現(xiàn)存儲。l)K=2*(i-l)+j(以行優(yōu)先存儲如下)

allal2al3al4allal2a21a22a23a32a33a34a43a445 6 7 8 9102)K=2*(j-l)+i(以列優(yōu)先存儲如下)a23a24a3b^32^a3?a34a41a22^43^44al1a21al2a22K=1 23 4allal2al3al4allal2a21a22a23a32a33a34a43a445 6 7 8 9102)K=2*(j-l)+i(以列優(yōu)先存儲如下)a23a24a3b^32^a3?a34a41a22^43^44al1a21al2a22K=1 23 4a32a23a33a435 6 7 8a34a449 10LS=(al,a2,a3....an)其中LS是廣義表的名字，n是它的長度。ai(lWn)是表中任意元素。在線性表中它只能是單元素，但在廣義表中它可以是單元素，也可以是一個廣義表(稱為子表)。習(xí)慣上廣義表的名字用大寫字母表示，單元素用小寫字母表示。當(dāng)廣義表不空時(shí)，稱第一個元素al為LS的表頭(head)元素，而稱其余的元素為尾元素.(1)廣義表的表頭，表尾元素的劃分與圖形表示廣義表的頭元素可以是單元素，也可以是表元素來充當(dāng)。但是廣義表的尾元素，只能是表元素來充當(dāng)。例如： /D)GetHead(B)=e;GetTail(B)=(). W@GetHead(D)=A;GetTail(D)=(B,C); 七| 不大由于(B,C)為非空列表，還可以繼續(xù)分解得到：GetHead((B,C))=B; ~~/r-LhcGetTail((B,C))=