【文章內(nèi)容簡介】 缺 缺點(diǎn) : ? 插入 、 刪除操作需要移動大量的元素 ? 預(yù)先分配空間需按最大空間分配 ， 利用不充分 ? 表容量難以擴(kuò)充 優(yōu)點(diǎn) : ? 邏輯相鄰 ， 物理相鄰 ? 可隨機(jī)存取任一元素 ? 存儲空間使用緊湊 69 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?單鏈表 (線性鏈表 ) 特點(diǎn) : 用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素 每個數(shù)據(jù)元素 ai，除存儲本身信息外，還需存儲其直接后繼的信息 70 ?單鏈表 (線性鏈表 ) 特點(diǎn) : 用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素 每個數(shù)據(jù)元素 ai，除存儲本身信息外，還需存儲其直接后繼的信息 指針 數(shù)據(jù)域 結(jié)點(diǎn) 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?結(jié)點(diǎn) 數(shù)據(jù)域： 元素本身信息 指針域： 指示直接后繼的存儲位置 71 頭指針 31 H 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 43 存儲地址 數(shù)據(jù)域 指針域 ZHOU 43 LI QIAN SUN WANG WU ZHAO ZHENG 1 7 13 19 25 31 37 13 1 NULL 37 7 19 25 ? 定義：結(jié)點(diǎn)中只含一個指針域的鏈表，也叫單鏈表 例 線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG) 72 LI ZHAO QIAN SUN ZHOU WU ZHENG WANG ^ H 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 73 ?實(shí)現(xiàn) typedef struct node { datatype data。 struct node *next。 }LNode,*LinkList。 LNode *h,*p。 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 74 data next p 結(jié)點(diǎn)（ *p） ?(*p)表示 p所指向的結(jié)點(diǎn) ?(*p).data/pdata表示 p指向結(jié)點(diǎn)的數(shù)據(jù)域 ?(*p).next/pnext表示 p指向結(jié)點(diǎn)的指針域 ?生成一個 LNode型新結(jié)點(diǎn)： p=(LNode *)malloc(sizeof(LNode))。 ?系統(tǒng)回收 p結(jié)點(diǎn)： free(p) 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 75 h a1 a2 an ^ …... h 空表 ^ 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?頭結(jié)點(diǎn) ：在單鏈表第一個結(jié)點(diǎn)前附設(shè)的一個結(jié)點(diǎn)。 頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空 76 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?在帶頭節(jié)點(diǎn)的單鏈表中查找第 i 個結(jié)點(diǎn) Status ListSearch_L(LinkList L,int i, datatype *e){ P = Lnext。j = 1。 While(p!=NULL amp。amp。 ji){ p = pnext。 j++。} if(p==NULL) return ERROR。 *e = pdata。 return OK； } 77 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?在帶頭節(jié)點(diǎn)的單鏈表中第 i 個結(jié)點(diǎn)處插入新元素 x 78 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) Status ListInsert_L ( LinkList L, ElemType x, const int i ) { p=L。j=0。 while (pamp。amp。j i1){p=pnext。j++。}//找第 i1個結(jié)點(diǎn) if ((p= =NULL )|| (j i1)){ printf( ― 無 效 的 插 入 位 置 !\n‖)。return ERROR。} //創(chuàng)建新結(jié)點(diǎn) ,數(shù)據(jù)為 x,指針為 NULL s=(LinkList )malloc(sizeof(LNode))。 s data = x。snext = pnext。 pnext = s。 return OK。} 79 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?刪除元素 ： 80 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) Status ListDelete_L (LinkList L,int I,ElemType *e){ P = L。 j= 0。 While(pnextamp。amp。ji1){//尋找第 i個結(jié)點(diǎn) ,并令 p指向其前趨 P = pnext。 ++ j。 } if(!(pnext)||j i1) return ERROR。//刪除位置不合理 q = pnext。 pnext = qnext。 //刪除并釋放結(jié)點(diǎn) *e = q data 。free(q)。 return OK。 }//ListDelete_L ?刪除元素 ： 81 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?兩個有序單鏈表合并為一個有序單鏈表 (非遞減 ) MergeList_L(Linklist La,LinkList Lb,LinkList Lc){ pa = Lanext。 pb = Lbnext。 Lc = pc = La。 While (pa amp。amp。 pb){ If(padata = pbdata){ pcnext = pa。pc = pa。 pa = panext。 } else{pcnext = pb。pc = pb。 pb= pbnext。} } pcnext = pa?pa:pb。 free(Lb)。 } 82 ?它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用 ?不需預(yù)先分配空間 ?指針占用額外存儲空間 ?不能隨機(jī)存取，查找速度慢 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 單鏈表具有單向性的缺點(diǎn) ?單鏈表特點(diǎn) 83 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) h 空表 h ?循環(huán)鏈表 :表中最后一個結(jié)點(diǎn)的指針指向表頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀 – 特點(diǎn)： 從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn) ， 提高查找效率 84 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?循環(huán)鏈表 操作與單鏈表基本一致 ,循環(huán)條件不同 ?單鏈表 : p或 pnext=NULL ?循環(huán)鏈 : p或 pnext=H h h ^ 85 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) （ double linked list ) prior element next 指向前驅(qū)結(jié)點(diǎn) 數(shù)據(jù) 指向后繼結(jié)點(diǎn) ?結(jié)點(diǎn)定義 typedef struct node{ datatype data。 struct node *prior,*next。 }DLNode,*DLinkLIst 86 L ?空雙向循環(huán)鏈表 ： ?非空雙向循環(huán)鏈表 ： L A B 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?雙向鏈表圖例 87 b c a p ppriornext= p= pnextproir。 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?雙向鏈表圖例 88 x S P a b 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?在給定結(jié)點(diǎn) p前插入一個新結(jié)點(diǎn) 89 ?在給定結(jié)點(diǎn) p前插入一個新結(jié)點(diǎn) S=(DLinklist)malloc(sizeof(DLNode))。 sdata = x。 sprior = pprior。 ① snext = p。② ppriornext = s。③ pprior = s。 ④ 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 90 b c a P ppriornext=pnext。 pnextprior=pprior。 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?刪除給定結(jié)點(diǎn) p 91 ppriornext=pnext。 pnextprior=pprior。 ?刪除給定結(jié)點(diǎn) p動畫演示 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) b a c p 92 ppriornext = pnext。 pnextprior = pprior。 free(p)。 ?刪除給定結(jié)點(diǎn) p 算法 就這么簡單！ 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 93 167。 3 存儲結(jié)構(gòu)的選用 順序與鏈?zhǔn)酱鎯Y(jié)構(gòu)的選用應(yīng)考慮因素： （ 1）存儲空間 （ 2）運(yùn)算時間 （ 3）程序設(shè)計(jì)語言 結(jié)點(diǎn)數(shù)據(jù)占用存儲量量結(jié)點(diǎn)數(shù)據(jù)本身占用存儲存儲密度 ?94 習(xí)題與練習(xí) 二 ： 頭結(jié)點(diǎn)、頭指針和開始結(jié)點(diǎn) 鏈表有 。 A、 B，編寫算法將兩表合并為一個按元素值遞減的線性表 C。 （分別以順序、鏈?zhǔn)綄?shí)現(xiàn)） 95 習(xí)題與練習(xí) 二 A[MAXSIZE]的前elenum個分量中，且遞增有序。試寫一算法，將 x 插入線性表適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時間復(fù)雜性。 。 96 習(xí)題與練習(xí) 二 算： (1) 初始化 (2) 定位 (3) 插入 (4) 刪除 97 【 學(xué)習(xí)內(nèi)容 】 ? 棧的抽象數(shù)據(jù)類型、順序表示、鏈表表示及相應(yīng)操作 (特別注意?？蘸蜅M的條件） ? 隊(duì)列的定義 、 特性 ? 隊(duì)列的抽象數(shù)據(jù)類型 、 順序表示 、 鏈表表示及相應(yīng)操作 （ 特別是循環(huán)隊(duì)列中隊(duì)頭與隊(duì)尾指針的變化情況 ） ? 棧和隊(duì)列是兩種特殊的線性表，是操作受限的線性表，稱限定性 DS。 第三章 棧與隊(duì)列 98 第 三 章 棧 與 隊(duì)列 167。 棧（ stack） 167。 定義 ?通常稱插入、刪除的這一端（如 表尾 ）為棧頂 (Top)，另一端（表頭）為 棧底(Bottom)。當(dāng)表中沒有元素時稱為 空棧 ?特點(diǎn)： 先進(jìn)后出 （ FILO） 或后進(jìn)先出（ LIFO） 99 例：假設(shè)棧 S=(a1， a2， a3， … an) 則 a1稱為棧底元素， an為棧頂元素。 ?進(jìn)棧 top+1。新元素插入 elements[top]位置 ?出棧 top1。棧中元素按 a1， a2， a3， … an的次序進(jìn)棧，退棧按后進(jìn)先出的原則進(jìn)行的 ,因此按 an …… a3 a2 a1的次序出棧 棧 （ stack） 100 棧 （ stack） ?棧的主要操作： （ 1）建立一個空棧 IniStack(amp。s) （ 2 ）判斷一個棧是否為空 StackEmpty(amp。s) （ 3） 進(jìn)棧 Push(amp。s,x) （ 4） 出棧 Pop(amp。s,amp。e) （ 5）獲得棧頂元素值 GetTop(s,amp。e) 101 進(jìn)棧： top+1。新 元 素 插 入elements[top]位置 出棧： top1 an a1 a2 ……... 棧底 棧頂 ... 出棧 進(jìn)棧 棧 s=(a1,a2,……,an) 棧 （ stack） ?棧的圖示 102 棧 （ stack） 棧和線性表類似，也有兩種（順序、鏈?zhǔn)剑?shí)現(xiàn)方法 103 ?存儲結(jié)構(gòu)定義 define MAXSIZE 6 typedef struct{ datatype elements[MAXSIZE]。 int top。 }SqStack。 棧 （ stack） 一、棧的順序存儲 104 棧 （ stack） ?棧的順序存儲 ?棧頂指針 top 指示棧頂元素在順序棧中的位置 – top=1,?？眨藭r出棧，則下溢（ under