數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)匯總

1、1 / 28識(shí)點(diǎn)匯總第二章21線性表的概念及其抽象數(shù)據(jù)類型的定義2。1 . 1 線性表的邏輯結(jié)構(gòu)線性表是 n 個(gè)類型相同的數(shù)據(jù)元素的有限序列，對(duì)n0，除第 線性表的特點(diǎn): i數(shù)據(jù)類型.2) 有窮性：線性表由有限個(gè)數(shù)據(jù)元素組成，表長就是表中數(shù)據(jù) 3 ) 有序性： 線性表 中相鄰數(shù)據(jù)元素之 間存在著序偶關(guān)系 抽象數(shù)據(jù)類型定義:見課本P P 。38 39定義線性表的順序存儲(chǔ)結(jié)構(gòu) 是指用一組地址連續(xù)的存儲(chǔ)單元依次存 2 / 28識(shí)點(diǎn)匯總, 即通過數(shù)據(jù)元素物理存儲(chǔ)的相鄰關(guān)系來反 地址為 Loc (a ) ， 則可通過如 下 公式計(jì)算 出第 i 個(gè)元素 的地址1Loca ) ：ii 11線性存儲(chǔ)結(jié)構(gòu)的C語

2、言定義E l emType elemMAXS I ZE; *ElemT y pe 可為i nt，char等*in t last； 記錄線性表中最后一個(gè)元素在數(shù)組 elem 中的位置(下標(biāo) 值)*/知識(shí)延伸(typedef)(C 課本P P 用typedef算識(shí)點(diǎn)匯總序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)分析2。3 線性表的鏈?zhǔn)酱鎯?chǔ)1)按實(shí)現(xiàn)角度看：鏈表可分為動(dòng)態(tài)鏈表和靜態(tài)鏈表。2)按鏈接方式的角度看 :鏈表可分為單鏈表、循環(huán)鏈表和雙鏈 3 / 284 / 28識(shí)點(diǎn)匯總InitList(Lin k List *L)*L(L i nkList) malloc(sizeof(Node); /*建立頭結(jié)點(diǎn)/ (L) ne

3、 xt =NULL；*建立空的單鏈表 L 注意:L是指向單鏈表的頭結(jié)點(diǎn)的指針，用來接收主程序中帶初 始化單鏈表的頭指針變量的地址, L相當(dāng)于主程序中帶初始化單鏈 算法描述:從一個(gè)空表開始,重復(fù)讀入數(shù)據(jù),生成新結(jié)點(diǎn),將讀入數(shù) 點(diǎn)之后,直至讀入結(jié)束標(biāo)志為止.5 / 28識(shí)點(diǎn)匯總 Node，*Linklis t ; /* LinkLi s t 為結(jié)構(gòu)指針類型*/ i nkLi stL，則 L 為單鏈表的頭指針,從而提高程序的可讀性.用Node *來定義typedef st ruct NodeNod e * s ;ch ar c；in t flag1；whi l e(flag) else f lag=

4、0；2)尾插法建表算法描述:頭插法建立鏈表雖然簡(jiǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序 和輸入的順序相反。若希望二者相同,可采用尾插法建表.該方法是將 6 / 28識(shí)點(diǎn)匯總typed ef st ruct NodeElemTyp e data;N od e，*Linkl is t；void CreatFromH ead (LinkList L)r=L;ch ar c; while (flag)f lag=0； r next= NULL; 1)按序號(hào)查找算法描述：設(shè)帶頭結(jié)點(diǎn)的單鏈表的長度為 n，要查找表中第i個(gè) 結(jié)點(diǎn),則需要從單鏈表的頭指針 L 出發(fā),從頭結(jié)點(diǎn)(Lnext)開始順著 鏈域掃描,用指針 p

5、指向當(dāng)前掃描到的結(jié)點(diǎn)，初值指向頭結(jié)點(diǎn),用j做 計(jì)數(shù)器,累計(jì)當(dāng)前掃描過的結(jié)點(diǎn)數(shù)(初值為0)，當(dāng)j= i時(shí),指針 p 所指 7 / 28識(shí)點(diǎn)匯總typed ef st ru ct N o d eNode,L ink li st；No d e Ge t(LinkList L,int i)i nt j0；i f (inext;j+；return i; /*找到了 i*/2)按值查找算法描述:按值查找是指在單鏈表中查找是否有節(jié)點(diǎn)值等于e的 結(jié)點(diǎn)，若有的話,則返回首次找到的其值等于e的結(jié)點(diǎn)的存儲(chǔ)位置,否 則返回NULL。查找過程從單鏈表的頭指針指向的頭結(jié)點(diǎn)出發(fā),順著 鏈逐個(gè)將結(jié)點(diǎn)的值和給定值e作比較。El

6、emT yp e data; N o de，*Linklist;No de Loca t e(LinkList L，ElemType key)Node *p;while(p!=NULL)8 / 28識(shí)點(diǎn)匯總r e turn NULL; /*沒有找到了key/ 申請(qǐng):申請(qǐng)新節(jié)點(diǎn)s，將其數(shù)據(jù)域的值置為e；ElemType d at a ; Node， Lin kli st ; Nod e *pre，*s;int k; if (i=0) return ERROR； pre= L;k= 0 ;i f(k=i) snext=pre n e xt； re tu r n OK;9 / 28識(shí)點(diǎn)匯總print

7、f(插入位置不合理”)；retu rn ERROR； 結(jié)果:將長度為n的線性表(a , , a , a , , a ) 變成長度為n 11 i1 i n的線性表(a ,1i1 i+1 ntyped ef s tr uc t Nodestruct Nod e * nex t；Node,*L i nkl i st;if(in ext;while(p!=NULL)ataqdata free(r); /*釋放被刪除的元素的空間* 3、有兩個(gè)單鏈表LA 和 LB，其元素均為非遞減有序排列,編寫一個(gè) 要求：新表 LC 利用現(xiàn)有的表 LA和LB中的元素結(jié)點(diǎn)空間,而不 12 / 28識(shí)點(diǎn)匯總算法思想：要求利用

8、現(xiàn)有的表 LA 和LB 中的結(jié)點(diǎn)空間來建立新 表LC,可通過更改結(jié)點(diǎn)的 nex t域來重建新的元素之間的線性關(guān)系 . 新表中的結(jié)點(diǎn)不用malloc，而只要從表 LA 和 LB中選擇合適的點(diǎn)插 ElemType data;s t ru c t N ode ne xt ;LinkList MergeLinkList (LinkL i st LA，L i nkList LB)Node *pa,*pb,pc;LinkList LC；/pa和pb 分別指向兩個(gè)單鏈表 LA 和LB 中的將要判斷 的結(jié)點(diǎn)， pc初值為 LC 且 pc 始終指向LC的表尾*/LCLA ;LCnextNULL; *將 LC 初

9、始置為空表/pc=LC； /*pc 始終指向 LC 的表尾*/*當(dāng)兩表均未處理完時(shí)，選擇較小者/ whil e (pa!=NULLp b !=NULL) pc nextpb;pc=pcnext;pb=pb ne x t ; el s e /表 A 未處理完*/r eturn LC ;13 / 28識(shí)點(diǎn)匯總23 3 循環(huán)鏈表特點(diǎn)：將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域由NULL改為指向頭結(jié) 帶頭結(jié)點(diǎn)的循環(huán)鏈表的算法和帶頭結(jié)點(diǎn)的單鏈表的算法的區(qū) p別條件為 例題:有兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表 LA、 LB,編寫算法，將兩個(gè) 算法思想：先找到兩個(gè)鏈表 LA、LB 的表尾,并分別由指針p ,q s t ruc t

10、 No de n ext;LinkL ist merge_1(LinkList LA,LinkList LB)p =LA；q LB;while(q- next!=LB) *修改A的尾指針,并使之為 B 的第一節(jié)點(diǎn)/14 / 28識(shí)點(diǎn)匯總/*修改 B 的尾指針，并使之為A的頭結(jié)點(diǎn)*/n若循環(huán)單鏈表設(shè)置為尾指針表示,在實(shí)現(xiàn)上述合并時(shí),無需循環(huán)遍歷找尾結(jié)點(diǎn),只需直接修改尾結(jié)點(diǎn)的指針域，其執(zhí)行時(shí)間是O(1)。typedef s tru c t NodeL inkL i st merge_2(LinkLi st RA,Li nkList LB)f r ee (RB- next );RB-nextp;r

11、e tur n RB； /*返回新循環(huán)鏈表的尾指針*/2.3.4 雙向鏈表 r15 / 28識(shí)點(diǎn)匯總ElemTyp e data;設(shè)指針p指向雙鏈表中某一點(diǎn)，則有下式成立:(p prior next=p算法思想：欲在雙向鏈表第i個(gè)結(jié)點(diǎn)之前插入一個(gè)新的結(jié)點(diǎn),則指針st ru ct DNod e prio r ,* next；int Dli n k Ins (DoubleList L，int i,El emType e) return ERROR ;whi l e(p！=NULLk i16 / 28識(shí)點(diǎn)匯總,if(p=NULL), pri ntf (插入位置不合理 );,return ERROR；

12、, ,s=(DNode )malloc (sizeof (DNode) ;,p prior-ne x t=s；,r e turn OK；算法思想:欲刪除雙向鏈表中的第i個(gè)結(jié)點(diǎn),則指針的變化情況如DNo d e ,* Doub l eList;i nt D l inkD e l(D oubl eList L , i nt i,El emType *e)/將刪除的元素保存到*e中*/, DNode * p；in t k；17 / 28識(shí)點(diǎn)匯總while (p!=NULL&knext；fr ee(q); t ai l=p;t empq； fr ee (temp)；tail=q; if(p!NULL)

13、tail-n ex t= p；識(shí)點(diǎn)匯總 雜度為O(M N) 。2 。5 順序表和鏈表的綜合比較(課本P P )66 6722 / 2823 / 28識(shí)點(diǎn)匯總 序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)線性表的順序存儲(chǔ)(順序表) :采用靜態(tài)分配方式，借助于C語言 針類型,動(dòng)態(tài)申請(qǐng)與動(dòng)態(tài)釋放地址空間，故鏈表中的各結(jié)點(diǎn)的物理存 24 / 28識(shí)點(diǎn)匯總(1) 順鏈操作技術(shù)：從“頭”開始,訪問單鏈表L中結(jié)點(diǎn) i(p 指 向該結(jié)點(diǎn))時(shí)，由于第i 個(gè)結(jié)點(diǎn)的地址在第 i- 1個(gè)結(jié)點(diǎn)(p re指向該 結(jié)點(diǎn),為p的前驅(qū))的指針域中存放,查找必須從單鏈表的“首結(jié)點(diǎn)”開 (2) 指針保留技術(shù)：通過對(duì)第 i 個(gè)結(jié)點(diǎn)進(jìn)行插入、刪除等操作 時(shí),需要

14、對(duì)第 i 1個(gè)結(jié)點(diǎn)的指針域進(jìn)行鏈址操作(pre- next) ,因此 在處理過程中始終需要維持當(dāng)前指針 p 與其前驅(qū)指針 pre的關(guān)系,將 這種技術(shù)簡(jiǎn)稱為“指針保留技術(shù)”。理中的相關(guān)技術(shù)(1)單鏈表與多重鏈表的差別在于指針域的個(gè)數(shù).(2)一般鏈表與循環(huán)鏈表的差別在于是否首尾相接,將非空表、 (3)判斷當(dāng)前結(jié)點(diǎn) p 是否是表尾。一般鏈表中， p 結(jié)點(diǎn)是表尾 結(jié)點(diǎn)的條件是：該結(jié)點(diǎn)的后繼指針值為空指針，即p-next=NUL L;循環(huán)鏈表中,p 結(jié)點(diǎn)是表尾結(jié)點(diǎn)的條件是:該結(jié)點(diǎn)的后繼指針值為頭 ， 2。6。2 典型例題例1：分解順序表為奇偶兩部分25 / 28識(shí)點(diǎn)匯總 將位于表尾左半部分的偶數(shù)與位于表

15、右半部分的奇數(shù)通過一個(gè) 輔助變量進(jìn)行交換.st #defin e Ma xSi z e 100typed ef st r uc ti n t elemMaxSize ;int last；/記錄線性表中最后一個(gè)元素在數(shù)組elem中的位置(下標(biāo)值)*/ whi le (i j )j; i f (ie le m i；Lelemi=L-e l emj;26 / 28識(shí)點(diǎn)匯總Lelemj =t；逆置就是使得表中內(nèi)容由原來的a1 2 i1 i i+1 n n n1 i+1 i i1 1路:借鑒頭插入法建鏈表的方法:1)記錄原表第一個(gè)元素結(jié)點(diǎn)的地址2)將頭結(jié)點(diǎn)的nex t域置空得新的空鏈表3)從原有單鏈表上依次“摘下”結(jié)點(diǎn),并采用頭插法插入到新的 Node,*L inkList;Nod e *p,q； L -nextNULL；while(p！=NULL) p=q;27 / 28識(shí)點(diǎn)匯總 中每個(gè)結(jié)點(diǎn)的 data域存放一個(gè)二進(jìn)制位。并在此鏈表上實(shí)現(xiàn)對(duì)二進(jìn) 位,把該位改為 1，其后所有各位改為0。 鏈表實(shí)現(xiàn)方法：從高位往低