第2章線性結(jié)構(gòu)2.1線性表2.2棧和隊(duì)列2.3串2.4數(shù)組、特殊矩陣和廣義表線性結(jié)構(gòu)（線性表、棧、隊(duì)、串、數(shù)組）數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)物理（存儲）結(jié)構(gòu)數(shù)據(jù)運(yùn)算非線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)插入運(yùn)算刪除運(yùn)算修改運(yùn)算查找運(yùn)算排序運(yùn)算數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容邏輯結(jié)構(gòu)唯一存儲結(jié)構(gòu)不唯一運(yùn)算的實(shí)現(xiàn)依賴于存儲結(jié)構(gòu)

若結(jié)構(gòu)是非空有限集，則有且僅有一個起始元素和一個終點(diǎn)元素，并且所有的數(shù)據(jù)元素最多只有一個直接前驅(qū)和一個直接后繼?！杀硎緸椋海╝1,a2,……,an）

線性數(shù)據(jù)結(jié)構(gòu)有且僅有一個起始元素，無直接前驅(qū)僅有一個直接后繼；有且僅有一個終點(diǎn)元素，無直接后繼僅有一個直接前驅(qū)；除起始元素和終點(diǎn)元素外，其它元素只有一個直接前趨和一個直接后繼。線性結(jié)構(gòu)的邏輯特征：

簡言之，線性結(jié)構(gòu)反映元素間的邏輯關(guān)系是

的。一對一(1:1)線性結(jié)構(gòu)包括線性表、堆棧、隊(duì)列、字符串、數(shù)組等等，其中，最典型、最常用的是------線性表用線性序列來表示線性結(jié)構(gòu)

（a1,a2,…,ai

,…,an）

a1

為起始元素，an

為終點(diǎn)元素，

ai

為索引號為i

的內(nèi)部元素線性數(shù)據(jù)結(jié)構(gòu)II2.1線性表2.1.1線性表的邏輯結(jié)構(gòu)2.1.2線性表的順序存儲及運(yùn)算2.1.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算2.1.4順序表和鏈表的比較2.1.1線性表的邏輯結(jié)構(gòu)1.線性表的定義2.線性表的基本操作（a1,a2,…ai-1，ai,ai＋1

，…,an）1.線性表的定義

定義：線性表是n（n≥0）個相同類型的數(shù)據(jù)元素a1,a2,…,an所構(gòu)成的有限線性序列。n=0時稱為空表n>0時稱為非空表數(shù)據(jù)元素線性起點(diǎn)ai的直接前驅(qū)ai的直接后繼下標(biāo)，是元素的序號，表示元素在表中的位置n為元素總個數(shù)，即表長線性終點(diǎn)

其中數(shù)據(jù)元素ai（1≤i≤n）只是一個抽象的符號，其具體含義在不同的情況下可以不同。例126個英文字母組成的英文表

（A,B,C,D,……,Z）學(xué)號姓名性別年齡班級2008011810205于春梅女182008級電信016班2008011810260何仕鵬男182008級電信017班2008011810284王爽女182008級通信011班2008011810360王亞武男182008級通信012班：：：

：：例2

學(xué)生情況登記表分析：數(shù)據(jù)元素都是記錄；元素間關(guān)系是線性的。分析：數(shù)據(jù)元素都是字母；元素間關(guān)系是線性的。注意：同一線性表中的元素必定具有相同數(shù)據(jù)類型！2.線性表的基本操作1.置空表：Init_List（L）將線性表L置成空表2.求長度：Length_List（L）求給定線性表L的長度3.取元素：Get_List（L，i)若1≤i≤length(L)，則取第i個位置上的元素，否則取得的元素為NULL（空元素）。4.定位函數(shù)：Locate_List（L，X）在線性表L中查找值為X的元素的位置。5.插入：Insert_List（L，i，X）在線性表L中第i個位置上插入值為X的元素。6.刪除：Delete_List（L，i）刪除線性表L中第i個位置上的元素。

例：假設(shè)線性表L=(23,56,89,76,18)，i=3，x=56，y=88，則對L的一組操作及結(jié)果如下：

所得結(jié)果//5//89//2//(23,56,88,89,76,18)//(23,56,88,76,18)(1)Length(L)(2)Get(L,i)(3)Locate(L,x)(4)Insert(L,i,y)(5)Delete(L,i+1)

線性表的分類根據(jù)數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的存儲結(jié)構(gòu)，可分成兩類：順序存儲結(jié)構(gòu)——順序表（向量表）鏈?zhǔn)酱鎯Y(jié)構(gòu)——鏈表2.1.2線性表的順序存儲及運(yùn)算1.順序表的定義及C語言描述2.順序表基本操作的實(shí)現(xiàn)3.順序表應(yīng)用舉例順序表線性表的順序表示又稱為順序存儲結(jié)構(gòu)或順序映像。

順序表的定義：用一組物理地址連續(xù)的存儲單元順序存儲在邏輯上相鄰的線性表數(shù)據(jù)元素。

順序存儲方法：用一組地址連續(xù)的存儲單元依次存儲線性表的元素。1.順序表的定義及C語言描述可以用

類型來實(shí)現(xiàn)數(shù)組線性表順序存儲特點(diǎn)：邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（利用數(shù)組下標(biāo)）。注意：C語言中的數(shù)組的下標(biāo)從0開始，即：data[n]的有效范圍是V[0]～V[n-1]

設(shè)首元素a1的存放地址為LOC(a1)（稱為首地址），設(shè)每個元素占用存儲空間（地址長度）為D字節(jié)，則表中任一數(shù)據(jù)元素ai的存放地址為：LOC(ai)=LOC(

a1

)+D*（i-1）上述公式的解釋如圖所示a1a2……aiai+1……an

地址內(nèi)容元素在表中的位序1i2n空閑區(qū)i+1Db=LOC(a1)b+Db+(i-1)Db+(n-1)Db+(max-1)DLOC(ai)=LOC(a1)+D*（i-1）線性表的順序存儲結(jié)構(gòu)示意圖注：順序表中任意一個元素的存取時間都相等，它是一個隨機(jī)存取結(jié)構(gòu)。因此：LOC(M[3])=98+5×(3-0)=113此題要注意下標(biāo)起點(diǎn)的不同解：地址計(jì)算通式為：LOC(ai)=LOC(a1)+L*（i-1）例：設(shè)有一維數(shù)組Ｍ，下標(biāo)的范圍是0到9，每個數(shù)組元素用相鄰的5個字節(jié)存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素Ｍ[0]的第一個字節(jié)的地址是98，則Ｍ[3]的第一個字節(jié)的地址是多少？113元素a1元素a2……..元素ai+1……..01i

可用C語言中的一維數(shù)組來描述:#defineM100

/*定義M為常數(shù)100，M的值作為數(shù)組的最大容量*/

intV[M];

/*V是數(shù)組的名字，假設(shè)數(shù)組中的元素是整型類型*/第i個元素的ai存儲地址：Loc(ai)=Loc(a1)+(i-1)*DV[０]V[１]V[i]V[M-1]順序表的存儲結(jié)構(gòu)由于C語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表?！荆咳鄙偈裁葱畔?？】又因?yàn)槌擞脭?shù)組來存儲線性表的元素之外，順序表還應(yīng)該用一個變量來表示線性表的長度屬性，所以我們用結(jié)構(gòu)類型來定義順序表類型。

順序表的存儲結(jié)構(gòu)#defineMAXSIZE100

/*線性表可能達(dá)到的最大長度為100*/typedefintElemType;typedefstruct{ElemTypedata[MAXSIZE];

/*線性表占用的數(shù)組空間*/intcnt;/*線性表實(shí)際長度，空表置0。線性表中最后一個元素在數(shù)組data[]中的下標(biāo)為cnt-1*/}SeqList;

順序表的存儲結(jié)構(gòu)

順序表的存儲結(jié)構(gòu) #defineMAXSIZE100 typedefintElemType;typedefstruct { ElemTypedata[MAXSIZE]; intcnt; }SeqList;2.順序表基本操作的實(shí)現(xiàn)在順序表存儲結(jié)構(gòu)中，很容易實(shí)現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i個元素的訪問。注意：C語言中的數(shù)組下標(biāo)從“0”開始，因此，若L是SeqList類型的順序表，則表中第i

個元素是L.data[i-1]。順序表的表長cnt，最后一個元素為L.data[cnt-1]。

2.順序表基本操作的實(shí)現(xiàn)順序表的運(yùn)算：主要有存取、插入、刪除、合并、分解、復(fù)制、檢索（查找）、排序（分類）、求長度等常用的指針基本操作（設(shè)指針變量p、q的定義為SeqList*p,*q）q=(SeqList*)malloc(sizeof(SeqList));//stdlib.hp=q;free(p);2.順序表基本操作的實(shí)現(xiàn)順序表的初始化：(指針形式)順序表的初始化即構(gòu)造一個空表。將L設(shè)為指針參數(shù)，首先動態(tài)分配存儲空間，然后，將表中cnt置為0，表示表中沒有數(shù)據(jù)元素。算法如下：

SeqList*Init_SeqList(){ SeqList*L; L=(SeqList*)malloc(sizeof(SeqList)); L->cnt=0;returnL;}設(shè)調(diào)用函數(shù)為主函數(shù)，主函數(shù)對初始化函數(shù)的調(diào)用如下：

main(){ SeqList*L; L=Init_SeqList(); …

}順序表的初始化2.順序表基本操作的實(shí)現(xiàn)按序號查找：注意：元素標(biāo)號與數(shù)組的下標(biāo)之間的關(guān)系時間復(fù)雜度為?

O(1)元素an……..元素ai……..元素a2元素a1data[0]data[1]data[i-1]data[n-1]2.順序表基本操作的實(shí)現(xiàn)按內(nèi)容查找：Locate（L，x）：查找順序表中是否含有與x值相同的元素。ai-1…..a2a1an…ai+1aix2.順序表基本操作的實(shí)現(xiàn)按內(nèi)容查找：Locate（L，x）：查找順序表中是否含有與x值相同的元素。ai-1…..a2a1an…ai+1aix2.順序表基本操作的實(shí)現(xiàn)按內(nèi)容查找：ai-1…..a2a1an…ai+1aix如果x和ai-1相同，則找到并停止查找；否則按照前面的步驟繼續(xù)下去2.順序表基本操作的實(shí)現(xiàn)按內(nèi)容查找：ai-1…..a2a1an…ai+1aix如果此時仍然沒有找到，返回錯誤并停止有關(guān)算法及程序在“查找與排序”一章中介紹2.順序表基本操作的實(shí)現(xiàn)按內(nèi)容查找Locate（L，x）：intLocate_SeqList(SeqList*L,ElemTypex){ inti=1;//i為邏輯序號 while(i<=L->cnt&&L->data[i-1]!=x) i++; if(i>L->cnt)return-1; elsereturni;/*返回數(shù)據(jù)元素邏輯序號*/}2.順序表基本操作的實(shí)現(xiàn)以下主要討論線性表的插入和刪除兩種運(yùn)算。1)順序表的插入：順序表的插入是指在長度為n的線性表（a1，a2，…，ai，…，an）的第i－1個元素ai－1之后和第i個元素ai之前插入一個新元素ax。設(shè)插入后的線性表中的數(shù)據(jù)元素為，則插入操作示意圖…..a2a1an…..ai+1ai01i-1iai-1…..a2a1an…ai+1ai

axai-1…..a2a1

aiai+1…an

an……ai+1ai

axn-1插入操作示意圖動畫順序表上完成這一運(yùn)算通過以下步驟進(jìn)行：

(1)將ai～an順序向后移動，為新元素讓出位置,向后移動的結(jié)點(diǎn)個數(shù)為（n－i＋1）

(2)將x置入空出的第i個位置；

(3)修改表長。在第i個結(jié)點(diǎn)之前插入數(shù)據(jù)元素時，移動元素次數(shù)的平均值為：2.順序表基本操作的實(shí)現(xiàn)其中，注：時間復(fù)雜度為O(n)插入運(yùn)算intInsert_SeqList(SeqList*L,inti,ElemTypex){/*在線性表L中第i個元素之前插入x，

i的合法值為1

i(L->cnt+1)*/intj;if((i<1)||(i>L->cnt+1)){ printf(“位置錯LocateError!”); return0;} /*位置i值不合法*/if(L->cnt==MAXSIZE){printf(“表滿Filled!");return(ERROR);}for(j=(L->cnt-1);j>=(i-1);j--) L->data[j+1]=L->data[j];/*插入位置后的元素依次右移*/L->data[i-1]=x;/*插入x*/L->cnt++;/*表長加1*/return1;}示例：2.順序表基本操作的實(shí)現(xiàn)2)順序表的刪除：順序表的刪除是指在長度為n的線性表（a1，a2，…，ai，…，an）中刪除第i個元素ai，則其長度變?yōu)閚-1。設(shè)刪除后的線性表中的數(shù)據(jù)元素為，則刪除操作示意圖ai-1…..a2a1alen

…ai+1aiai-1…..a2a1aiai+1…alen

ai+1alenai+1…ai+1

…alen

…..a2a1an…..ai+1ai01i-1in-12.順序表基本操作的實(shí)現(xiàn)2)順序表的刪除：刪除第i個元素，移動結(jié)點(diǎn)的個數(shù)為（n-i），則移動次數(shù)的平均值為其中，注：時間復(fù)雜度為O(n)例：下圖(a)是一個長度為7的有序線性表，若要刪除表中值為24的元素，則必須把值為28到77的所有元素依次向前移動一個位置。算法流程圖→(,a1,a2,…,ai-1,ai+1,...,an)3.順序表應(yīng)用舉例例

將順序表(a1,a2,…,ai-1,ai,ai+1,...,an)重新排列為以a1為界的兩部分：a1前面的值均比a1小，a1后面的值都比a1大(這里假設(shè)數(shù)據(jù)元素的類型具有可比性,不妨設(shè)為整數(shù)型)，操作過程如圖2.5所示。這一操作稱為劃分。a1也稱為基準(zhǔn)?；舅悸罚簭牡诙€元素開始到最后一個元素，逐一向后掃描：(a)當(dāng)前數(shù)據(jù)元素ai比a1大(>=)時，表明它已經(jīng)在a1的后面，不必改變它與a1之間的位置，繼續(xù)比較下一個。(b)若比a1小，說明它應(yīng)該在a1的前面，此時將它前面的元素都依次向后移動一個位置，然后將它置入最前面。

(a1,a2,…,ai-1,ai,ai+1,...,an)ai

↑

2515301020206025103035601535……

(a)劃分前

(b)劃分后圖2.5順序表的劃分算法描述如下：

voidpart(SeqList*L){ inti,j;//i是邏輯序號，j是循環(huán)變量 ElemTypex,y; x=L->data[0];//將基準(zhǔn)置入x中 for(i=2;i<=L->cnt;i++) { if(L->data[i-1]<x)//當(dāng)前元素小于基準(zhǔn)

{ y=L->data[i-1];//保存當(dāng)前元素

for(j=i-1;j>=1;j--)//移動

L->data[j]=L->data[j-1]; L->data[0]=y;//當(dāng)前元素置入最前面

} }}說明：

本算法中，有兩重循環(huán)，外循環(huán)執(zhí)行n-1次，內(nèi)循環(huán)中移動元素的次數(shù)與當(dāng)前數(shù)據(jù)的大小有關(guān)。當(dāng)?shù)趇個元素小于a1時，要移動它上面的i-1個元素，再加上當(dāng)前結(jié)點(diǎn)的保存及置入，所以移動i-1+2次，在最壞情況下，a1后面的結(jié)點(diǎn)都小于a1，總的移動次數(shù)為：即最壞情況下移動數(shù)據(jù)時間性能為O(n2)。這個算法簡單但效率低，在快速排序中的另一種劃分算法，它的性能為O(n)。nn(n-1)*(n+4)∑(i-1+2)=∑(i+1)=i=2i=22→(,a1,a2,…,ai-1,ai+1,...,an)(a1,a2,…,ai-1,ai,ai+1,...,an)ai

↑順序表小結(jié)順序表的優(yōu)點(diǎn)：邏輯關(guān)系體現(xiàn)在存儲結(jié)構(gòu)的相鄰關(guān)系中，無需增加額外的存儲空間；可以隨機(jī)存取表中任一元素(時間復(fù)雜度為O(1))。缺點(diǎn)：插入和刪除運(yùn)算都不太方便(時間復(fù)雜度為O(n))

；采用靜態(tài)存儲分配，可能會浪費(fèi)空間；容量不容易擴(kuò)充。解決方法?：引入另一種存儲形式：鏈?zhǔn)酱鎯Y(jié)構(gòu)順序表作業(yè)：習(xí)題2:2.5(1)2.1.3線性表的鏈?zhǔn)酱鎯斑\(yùn)算1.

單鏈表2.

雙向鏈表線性表要點(diǎn)回顧線性結(jié)構(gòu)(包括表、棧、隊(duì)、數(shù)組）的定義和特點(diǎn)：僅一個首、尾結(jié)點(diǎn)，其余元素僅一個直接前驅(qū)和一個直接后繼。2.線性表邏輯結(jié)構(gòu)：“一對一”或1:1存儲結(jié)構(gòu)：順序、鏈?zhǔn)竭\(yùn)算：修改、插入、刪除3.順序存儲特征：邏輯上相鄰，物理上也相鄰；優(yōu)點(diǎn)：隨機(jī)查找快O(1)缺點(diǎn)：插入、刪除慢O(n)1.單鏈表(1)鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)鏈表(LinkedList)是指用一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素。這組存儲單元即可以是連續(xù)的，也可以是不連續(xù)的。邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰，只能順序(依次)訪問。如何實(shí)現(xiàn)？ 在存儲每個結(jié)點(diǎn)值的同時，還必須存儲指示其后繼或前驅(qū)結(jié)點(diǎn)的地址（或位置）信息，這個信息稱為指針(pointer)或鏈(link)。(1)鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)鏈表中的結(jié)點(diǎn)結(jié)構(gòu)：數(shù)據(jù)域+指針域。鏈表的樣式：指針數(shù)據(jù)指針數(shù)據(jù)指針或樣式：數(shù)據(jù)域：存儲數(shù)據(jù)元素信息指針域：存儲直接后繼或者直接前驅(qū)的存儲位置鏈表存放示意圖如下：a1heada2/\an……說明：鏈表中的每一個結(jié)點(diǎn)只有一個指向后繼的指針，這種鏈表稱為單鏈表（SingleLinkedList)。單鏈表中每個結(jié)點(diǎn)的存儲地址是存放在其前驅(qū)結(jié)點(diǎn)的指針域中。起始結(jié)點(diǎn)（表頭結(jié)點(diǎn)）無前驅(qū)，故應(yīng)設(shè)表頭指針（頭指針）HEAD指向起始結(jié)點(diǎn)。終點(diǎn)元素?zé)o后繼，它的指針域?yàn)榭眨碞ULL（圖示中也可用^表示)。鏈表存放示意圖datanext結(jié)點(diǎn)示意圖例：請畫出26個英文字母表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。該字母表在內(nèi)存中鏈?zhǔn)酱娣诺臉邮脚e例如下：解：該字母表的邏輯結(jié)構(gòu)為：（a,b,…,y,z）討論1：每個存儲結(jié)點(diǎn)包含兩部分：數(shù)據(jù)域和

。討論2：在單鏈表中，除了首結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲位置由

指示。其前驅(qū)結(jié)點(diǎn)的指針域的值指針域(2)與鏈?zhǔn)酱鎯τ嘘P(guān)的術(shù)語：1）結(jié)點(diǎn)：數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成；2）鏈表：

n個結(jié)點(diǎn)由指針鏈組成一個鏈表。它是線性表的鏈?zhǔn)酱鎯τ诚瘢Q為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。3）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表：

結(jié)點(diǎn)只有一個指針域的鏈表，稱為單鏈表；有兩個指針域的鏈表，稱為雙鏈表；有多個指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環(huán)鏈表。a1heada2an……h(huán)ead循環(huán)鏈表示意圖：4）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)

示意圖如下：頭指針頭結(jié)點(diǎn)首結(jié)點(diǎn)a1heada2…infoan^頭指針是指向鏈表中第一個結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭捉Y(jié)點(diǎn)）（即線性表的第一個元素）的特殊指針；首結(jié)點(diǎn)是指鏈表中存儲線性表第一個數(shù)據(jù)元素a1的結(jié)點(diǎn)；頭結(jié)點(diǎn)是在鏈表的首結(jié)點(diǎn)之前附設(shè)的一個結(jié)點(diǎn)，其數(shù)據(jù)域內(nèi)可以不存儲任何信息（也可存放線性表的長度等附加信息）。（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結(jié)構(gòu)用單鏈表表示如下，請問其頭指針的值是多少？存儲地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例：一個線性表的邏輯結(jié)構(gòu)為：答：頭指針是指向鏈表中第一個結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個結(jié)點(diǎn)的地址。7ZHAOH31∴頭指針的值是31①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①

無頭結(jié)點(diǎn)②

有頭結(jié)點(diǎn)上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：答：討論2.如何表示空表？頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲線性表的數(shù)據(jù)元素，其作用是為了對鏈表進(jìn)行操作時，可以對空表、非空表的情況以及對首結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。答：無頭結(jié)點(diǎn)時，當(dāng)頭指針的值為空時表示空表；有頭結(jié)點(diǎn)時，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r表示空表。^頭指針^頭指針頭結(jié)點(diǎn)無頭結(jié)點(diǎn)有頭結(jié)點(diǎn)討論1.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？討論3.頭結(jié)點(diǎn)的數(shù)據(jù)域內(nèi)裝的是什么？頭結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放線性表長度等附加信息，但此結(jié)點(diǎn)不能計(jì)入鏈表長度值。答：討論4.鏈表的數(shù)據(jù)元素有兩個域，不再是簡單數(shù)據(jù)類型，編程時該如何表示？因每個結(jié)點(diǎn)至少有兩個分量，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。答：什么是結(jié)構(gòu)類型？如何書寫表達(dá)？——補(bǔ)充C語言內(nèi)容

頭結(jié)點(diǎn)的數(shù)據(jù)域H補(bǔ)充：結(jié)構(gòu)類型的C語言表示法①類型定義和變量說明可以合寫為：typedefstruct

node

//structnode是自定義結(jié)構(gòu)類型名稱{char

data;//定義數(shù)據(jù)域的變量名及其類型struct

node

*next;//定義指針域的變量名及其類型}SLNODE;

//SLNODE等價于structnodeSLNODE

test，*head;//test變量是structnode結(jié)構(gòu)類型,*head是node結(jié)構(gòu)類型的頭指針//以26個字母的鏈表為例，每個結(jié)點(diǎn)都有兩個分量：字符型指針型假設(shè)某個結(jié)點(diǎn)用變量test表示，其中兩個分量分別用data和*next表示，則：*nextdatatest補(bǔ)充：結(jié)構(gòu)類型的C語言表示法②對于指向結(jié)構(gòu)變量test首地址的指針，還可說明為：

SLNODE

test

,*p,*q;

③每個結(jié)點(diǎn)的分量如何表示？*nextdatatestp方式1：直接用

test.data＝'a'；

test.next=q方式2：先讓指針變量p指向該結(jié)點(diǎn)的首地址，然后用：

p->data='a';p->next=q;方式3：先讓指針變量p指向該結(jié)點(diǎn)的首地址，然后用：

(*p).data='a'；(*p).next＝q‘a(chǎn)’‘b’qp設(shè)p為指向鏈表的第i個元素的指針,則第i個元素的數(shù)據(jù)域?qū)憺?/p>

，指針域?qū)憺?/p>

。p->dataai的值p->nextai+1的地址練習(xí)：對于單鏈表結(jié)點(diǎn)結(jié)構(gòu)的抽象描述:typedefstructnode{ElemTypedata;//數(shù)據(jù)域

structnode*next;//指針域}SLNODE;數(shù)據(jù)元素之間的相對關(guān)系是由指針域所指示的，由鏈建立的順序必須與數(shù)據(jù)元素的邏輯次序一致，而結(jié)點(diǎn)在存儲器中的物理位置可以是任意的。對比：關(guān)于順序表的抽象定義：typedefstructSqnode{ElemTypedata[MAXNUM];//表長（特指元素個數(shù)）intLast;//表當(dāng)前存儲容量（字節(jié)數(shù)）}SqList;補(bǔ)充：結(jié)構(gòu)類型的C語言表示法④三個有用的庫函數(shù)（都在<stdlib.h>中）：sizeof(x)——計(jì)算變量x的長度；malloc(m)

—開辟m字節(jié)長度的地址空間，并返回這段空間的首地址；free(p)

——釋放指針p所指變量的存儲空間，即徹底刪除一個變量。問1：自定義結(jié)構(gòu)類型結(jié)點(diǎn)的長度m是多少？問2：結(jié)構(gòu)變量的首地址(指針p）是多少？問3：怎樣刪除結(jié)構(gòu)結(jié)點(diǎn)？*nextdata長度為m字節(jié)pm＝sizeof(SLNODE)p＝(SLNODE*)malloc(m)free(p)只能借助其指針刪除！

單鏈表的實(shí)現(xiàn)(1)單鏈表的定義及其初始化

(2)單鏈表的建立和輸出(3)單鏈表的訪問(4)單鏈表的插入(5)單鏈表的刪除(1)單鏈表的定義及其初始化單鏈表的定義：n個結(jié)點(diǎn)由指針鏈組成一個鏈表。其結(jié)點(diǎn)只有一個指針域的鏈表，稱為單鏈表或線性鏈表；鏈表是由一個個結(jié)點(diǎn)構(gòu)成的，結(jié)點(diǎn)定義如下：typedefstructnode{

ElemTypedata;//數(shù)據(jù)域

structnode*next;//指針域

}SLNODE;單鏈表的初始化定義頭指針變量：

structnode*h;或者SLNODE*h這樣定義一個structnode類型的指針變量之后，系統(tǒng)并沒有為它分配內(nèi)存單元。這需要通過動態(tài)申請內(nèi)存單元來存放結(jié)點(diǎn)。C語言中提供的malloc(n)可以完成此功能。由于一個空的單鏈表沒有一個結(jié)點(diǎn)，故頭結(jié)點(diǎn)(或頭指針)指向?yàn)榭誑ULL。具體操作如下：h=(SLNODE*)malloc(sizeof(SLNODE));h->next=NULL;執(zhí)行后的邏輯示意圖如上圖所示。

^空表h(2)單鏈表的建立實(shí)現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個數(shù)據(jù)元素開辟存儲空間并賦值，并及時將其地址存放在相應(yīng)結(jié)點(diǎn)的指針域中。假設(shè)線性表中結(jié)點(diǎn)的數(shù)據(jù)類型是字符型，我們逐個輸入這些字符型的結(jié)點(diǎn)，并以特殊字符(例如“\n”)為輸入結(jié)束標(biāo)記。動態(tài)地建立單鏈表的常用方法有如下兩種：頭插法建表尾插法建表babaxPPs在P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)xs單鏈表的插入關(guān)鍵語句：s->next=P->next;P->next=s;∧HH∧a1Hsa2該方法從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。關(guān)鍵語句：

s->next=H->next;H->next=s;頭插法建表s∧a1SLNODE*createfromHead(){ SLNODE*head;SLNODE*s; ElemTypex; head=(SLNODE*)malloc(sizeof(SLNODE));x=get_data();while(x!=-1）{s=(SLNODE*)malloc(sizeof(SLNODE));s–>data=x;s–>next=head->next;

head->next=s;x=get_data();} returnhead}頭插法建表head->next=NULL;頭插法建立鏈表雖然算法簡單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。如何實(shí)現(xiàn)？該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。尾插法建表關(guān)鍵是要保存尾結(jié)點(diǎn)（最后一個結(jié)點(diǎn)）的位置。尾插法建表∧HrHq新結(jié)點(diǎn)頭指針頭結(jié)點(diǎn)a1∧增加一個結(jié)點(diǎn)Ha1b2∧q新結(jié)點(diǎn)rr（始終指向尾結(jié)點(diǎn)）關(guān)鍵語句：r->next=q;r=q;SLNODE*createfromRear(){SLNODE*head;SLNODE*r,*q; ElemTypex; head=(SLNODE*)malloc(sizeof(SLNODE)); r=head;

head->next=NULL;x=get_data();while(x!=-1） {q=(SLNODE*)malloc(sizeof(SLNODE));

q–>data=x;r–>next=q; r=q;/*r永遠(yuǎn)指向鏈表的最后一個結(jié)點(diǎn)*/x=get_data();}

r->next=NULL;

//將最后一個結(jié)點(diǎn)的next鏈域置為空returnhead;}尾插法建表特別容易忘記?。?/帶頭結(jié)點(diǎn)SLNODE*createfromRear2(){SLNODE*head; SLNODE*r,*q; ElemTypex;

head=NULL; r=head;x=get_data();while(x!=-1） {q=(SLNODE*)malloc(sizeof(SLNODE));

q–>data=x;

if(head==NULL){head=q;r=head;}//新結(jié)點(diǎn)插入空表

else

r–>next=q; r=q;/*r永遠(yuǎn)指向鏈表的最后一個結(jié)點(diǎn)*/x=get_data();}

if(r!=NULL) r->next=NULL;

//將最后一個結(jié)點(diǎn)的next鏈域置為空returnhead;}尾插法建表不帶頭結(jié)點(diǎn)頭結(jié)點(diǎn)的用途：對首結(jié)點(diǎn)進(jìn)行統(tǒng)一的處理；對空表、非空表進(jìn)行統(tǒng)一的處理。voiddisplay(SLNODE*head)/*字母鏈表的輸出*/{SLNODE*p;p=head;/*只要沒到最后一個元素，就不停地“順藤摸瓜”輸出*/while(p->next!=NULL)/*存在頭結(jié)點(diǎn)*/{p=p->next;printf("%c",p->data);}

}討論：要統(tǒng)計(jì)鏈表中數(shù)據(jù)元素的個數(shù)，該如何改寫？

sum++;單鏈表的輸出(3)單鏈表的訪問思路：要找到第i個數(shù)據(jù)元素，關(guān)鍵是要先找到指向該結(jié)點(diǎn)的指針p即可。難點(diǎn)：單鏈表中想訪問第i個元素，必須從頭指針出發(fā)尋找（順藤摸瓜），不能隨機(jī)存取。核心語句：j=0;p=head;WHILE(p->next!=NULL&&j<i){p=p->next;j++;}if(p!=NULL&&j==i)

return

(p->data);eslereturn(-1);}在鏈表中插入一個元素的示意圖如下：(4)單鏈表的插入babax∧anaia1a2ppai-1xLs∧anaia1a2pai-1LInsLinkList(SLNODE*p,intx){/*在p所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)*/SLNODE*s;/*定義指向結(jié)點(diǎn)類型的指針*/

s=(SLNODE*)malloc(sizeof(SLNODE));/*生成新結(jié)點(diǎn)*/s->data=x;s->next=p->next;p->next=s;returnOK;}s(4)單鏈表的插入∧anaia1a2pai-1xLInsLinkList(SLNODE*p,intx){/*在p所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)*/SLNODE*s;/*定義指向結(jié)點(diǎn)類型的指針*/s=(SLNODE*)malloc(sizeof(SLNODE));/*生成新結(jié)點(diǎn)*/

s->data=x;

s->next=p->next;p->next=s;returnOK;}s(4)單鏈表的插入∧anaia1a2pai-1xLInsLinkList(SLNODE*p,intx){/*在p所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)*/SLNODE*s;/*定義指向結(jié)點(diǎn)類型的指針*/s=(SLNODE*)malloc(sizeof(SLNODE));/*生成新結(jié)點(diǎn)*/s->data=x;

s->next=p->next;p->next=s;returnOK;}s(4)單鏈表的插入∧anaia1a2ai-1xLInsLinkList(SLNODE*p,intx){/*在p所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn)*/SLNODE*s;/*定義指向結(jié)點(diǎn)類型的指針*/s=(SLNODE*)malloc(sizeof(SLNODE));/*生成新結(jié)點(diǎn)*/s->data=x;s->next=p->next;

p->next=s;returnOK;}(4)單鏈表的插入ps思考：如何在p所指向的結(jié)點(diǎn)之前插入新的結(jié)點(diǎn)？(5)單鏈表的刪除思想方法

刪除運(yùn)算是將表的第i個結(jié)點(diǎn)（ai）刪去。

具體步驟：（1）找到ai-1的存儲位置p（因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲地址是在其直接前驅(qū)結(jié)點(diǎn)ai-1的指針域中）（2）令ai-1的指針域(p-＞next)指向ai的直接后繼結(jié)點(diǎn)（即把a(bǔ)i從鏈上摘下）（3）釋放結(jié)點(diǎn)ai的空間。單鏈表的刪除刪除步驟（即核心語句）：q=p->next;//保存b的指針，靠它才能指向cp->next=q->next;//a、c兩結(jié)點(diǎn)相連free(q)；//刪除b結(jié)點(diǎn)，徹底釋放在鏈表中刪除某元素的示意圖如下：cabpp->next(p->next)->next××DelLinkList(SLNODE*p)/*刪除p指針指向結(jié)點(diǎn)的后一個結(jié)點(diǎn)*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后繼結(jié)點(diǎn)*/p->next=q->next;/*修改p結(jié)點(diǎn)的指針域*/free(q);}/*刪除并釋放結(jié)點(diǎn)*/}

(5)單鏈表的刪除ai-1a1aiai+1LpDelLinkList(SLNODE*p)/*刪除p指針指向結(jié)點(diǎn)的后一個結(jié)點(diǎn)*/{SLNODE*q;

if(p->next!=NULL){q=p->next;/*q指向p的后繼結(jié)點(diǎn)*/p->next=q->next;/*修改p結(jié)點(diǎn)的指針域*/free(q);}/*刪除并釋放結(jié)點(diǎn)*/}q(5)單鏈表的刪除ai-1a1aiai+1LpDelLinkList(SLNODE*p)/*刪除p指針指向結(jié)點(diǎn)的后一個結(jié)點(diǎn)*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后繼結(jié)點(diǎn)*/p->next=q->next;/*修改p結(jié)點(diǎn)的指針域*/free(q);}/*刪除并釋放結(jié)點(diǎn)*/}(5)單鏈表的刪除ai-1a1aiai+1LpqDelLinkList(SLNODE*p)/*刪除p指針指向結(jié)點(diǎn)的后一個結(jié)點(diǎn)*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后繼結(jié)點(diǎn)*/p->next=q->next;/*修改p結(jié)點(diǎn)的指針域*/free(q);}/*刪除并釋放結(jié)點(diǎn)*/}

(5)單鏈表的刪除ai-1a1aiai+1LpqDelLinkList(SLNODE*p)/*刪除p指針指向結(jié)點(diǎn)的后一個結(jié)點(diǎn)*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后繼結(jié)點(diǎn)*/

p->next=q->next;/*修改p結(jié)點(diǎn)的指針域*/free(q);}/*刪除并釋放結(jié)點(diǎn)*/}

(5)單鏈表的刪除ai-1a1aiai+1LpDelLinkList(SLNODE*p)/*刪除p指針指向結(jié)點(diǎn)的后一個結(jié)點(diǎn)*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后繼結(jié)點(diǎn)*/p->next=q->next;/*修改p結(jié)點(diǎn)的指針域*/

free(q);}/*刪除并釋放結(jié)點(diǎn)*/}(5)單鏈表的刪除intDelete_LinkList(SLNODE*HEAD,inti){SLNODE*q,*p;int j=0;q=HEAD;while(q->next!=NULL&&j<i-1){q=q->next;j++;} //使p指向第i-1個結(jié)點(diǎn)if((j!=i-1)||(q->next==NULL))return0; //第i個結(jié)點(diǎn)不存在，不能刪除else{ p=q->next; q->next=p->next; //修改指向關(guān)系free(p); //釋放被刪除結(jié)點(diǎn)空間return1;}}ai-1a1aiai+1Lq(5)單鏈表的刪除:刪除第i個結(jié)點(diǎn)p背景：對于單鏈表而言，若已知某結(jié)點(diǎn)的指針為p，其后繼結(jié)點(diǎn)的指針則為p->next，而找其前驅(qū)則只能從該鏈表的頭指針開始，順著各結(jié)點(diǎn)的next域進(jìn)行，即找后繼的時間性能是O(1)，找前驅(qū)的時間性能是O(n)。問題：如何使得找前驅(qū)的時間性能達(dá)到O(1)？付出空間的代價：每個結(jié)點(diǎn)再加一個指向前驅(qū)的指針域，用這種結(jié)點(diǎn)組成的鏈表稱為雙向鏈表。雙向鏈表:

在單鏈表的每個結(jié)點(diǎn)里再增加一個指向其直接前驅(qū)的指針域prior。這樣形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。和單鏈表類似，雙鏈表一般也是由頭指針唯一確定的，增加頭結(jié)點(diǎn)也能使雙鏈表上的某些運(yùn)算變得方便。

2.雙向鏈表雙向鏈表在非線性結(jié)構(gòu)（如樹結(jié)構(gòu)）中將大量使用。2.

雙向鏈表這種指針域包括指向該結(jié)點(diǎn)的直接前驅(qū)和直接后繼的兩個指針的存儲結(jié)構(gòu)－雙向鏈表此結(jié)點(diǎn)結(jié)構(gòu)的C語言描述為：typedefstructnode{elemtypedata;structnode*prior,*next;}DLNODEpriordatanext指向前驅(qū)結(jié)點(diǎn)的指針域數(shù)據(jù)域指向后繼結(jié)點(diǎn)的指針域雙向鏈表的邏輯示意圖：?

雙向鏈表結(jié)構(gòu)的對稱性若P是指向表中某一結(jié)點(diǎn)的指針則有：(P->next)->prior=p(P->prior)->next=p即結(jié)點(diǎn)*p的存儲位置既存放在其前驅(qū)結(jié)點(diǎn)*(p->prior)的直接后繼指針域中，也存放在它的后繼結(jié)點(diǎn)*(p->next)的直接前驅(qū)指針域中。ana1a2?hintDlinkIns(DLNODE*L,DLNODE*P,ElemTypex)如何在P指向結(jié)點(diǎn)之前插入新的結(jié)點(diǎn)SL123PSx

S->prior=P->prior;

P->prior->next=S;

S->next=P;

P->prior=S;雙向鏈表的前插運(yùn)算關(guān)鍵步驟∧∧注意：步驟

必須在步驟

和

后面，即確保指針域P->prior使用完之后，再賦新的值。L123intDlinkDel(DLNODE*L,DLNODE*P)//刪除指定結(jié)點(diǎn)PPP->next->prior=P->prior;P->prior->next=P->next；Free(P)注意：與單鏈表的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時修改兩個方向上的指針。上述兩個算法的時間復(fù)雜度均為O(1)。雙向鏈表的刪除操作討論：鏈表能不能首尾相連？怎樣實(shí)現(xiàn)？答：能。只要將表中最后一個結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)即可(P->next=head;)。這種形成環(huán)路的鏈表稱為循環(huán)鏈表。特別：帶頭結(jié)點(diǎn)的空循環(huán)鏈表樣式H

特點(diǎn)：

1、從任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)。

2、操作僅有一點(diǎn)與單鏈表不同：循環(huán)條件單鏈表-----p=NULL或p->next=NULL

循環(huán)鏈表-----p=head或p->next=head3.循環(huán)鏈表單向循環(huán)鏈表雙向循環(huán)鏈表hha1a2an……h(huán)hana1a2單向循環(huán)鏈表最后一個結(jié)點(diǎn)的指針指向第一個結(jié)點(diǎn)；用尾指針命名，則

a1:r->next->nextan:r常作為隊(duì)列的存儲結(jié)構(gòu)a1a2an……h(huán)r2.1.4順序表與鏈表的比較（討論題形式小結(jié)）線性表邏輯結(jié)構(gòu)特點(diǎn)是，只有一個首結(jié)點(diǎn)和尾結(jié)點(diǎn)；除首尾結(jié)點(diǎn)外其他結(jié)點(diǎn)只有一個直接前驅(qū)和一個直接后繼。簡言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對一（1:1）的。問1：線性表的邏輯結(jié)構(gòu)特點(diǎn)是什么？其順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)是什么？答：

順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。鏈?zhǔn)酱鎯r，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。問2：順序存儲和鏈?zhǔn)酱鎯Ω饔心男﹥?yōu)缺點(diǎn)？順序存儲的三個優(yōu)點(diǎn)：

(1)方法簡單，容易實(shí)現(xiàn)，沒有使用指針。

(2)不用為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲開銷。

(3)順序表具有按元素序號隨機(jī)訪問的特點(diǎn)（時間復(fù)雜度O(1)）。順序存儲的兩個缺點(diǎn)：

(1)在順序表中做插入刪除操作時，平均移動大約表中一半的元素，因此對n較大的順序表效率低（時間復(fù)雜度O(n)）。

(2)需要預(yù)先分配足夠大的存儲空間（估計(jì)過大，可能會導(dǎo)致順序表后部大量閑置；預(yù)先分配過小，又會造成溢出）。鏈表的優(yōu)缺點(diǎn)恰好與順序表相反。

答：問2：順序存儲和鏈?zhǔn)酱鎯Ω饔心男﹥?yōu)缺點(diǎn)？鏈表優(yōu)點(diǎn)：

(1)無需事先了解線性表的長度，允許線性表的長度動態(tài)變化(2)能夠適應(yīng)經(jīng)常插入刪除內(nèi)部元素的情況（時間復(fù)雜度O(1)）。鏈表的缺點(diǎn)：

(1)需要使用指針。

(2)每個元素都有結(jié)構(gòu)性存儲開銷

(3)按元素序號訪問不方便（時間復(fù)雜度O(n)）。問3：在什么情況下用順序表比鏈表好？順序表適宜于存儲靜態(tài)數(shù)據(jù)，如進(jìn)行查找(按序號訪問)這樣的操作；鏈表宜于存儲動態(tài)數(shù)據(jù)，進(jìn)行插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。答：作業(yè)：鏈表作業(yè)：習(xí)題22.1,2.2,2.5(2)Ch2線性結(jié)構(gòu)

2.2棧和隊(duì)列

2.2.1棧

1棧的定義及基本運(yùn)算

2棧的存儲結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn)

3棧的應(yīng)用

2.2.2隊(duì)列

1隊(duì)列的定義及基本運(yùn)算

2隊(duì)列的存儲結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn)

3隊(duì)列應(yīng)用舉例

操作受限的線性表?xiàng)＃⊿tack）運(yùn)算只在表的一端進(jìn)行隊(duì)列（Queue）運(yùn)算只在表的兩端進(jìn)行

2.2.1棧（stack）

1棧的定義及基本運(yùn)算定義：棧是限定在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。允許插入和刪除的一端稱為棧頂(top），另一端稱為棧底（bottom）。如給定棧s＝（a1，a2，…，an），棧中元素按a1，a2，…，an的順序進(jìn)棧，則稱a1是棧底元素，an是棧頂元素。后進(jìn)先出（LIFO）表

棧的基本運(yùn)算(1)棧初始化：Init_Stack()初始條件：棧不存在。操作結(jié)果：構(gòu)造一個空棧(不含任何元素）。(2)判?？眨篒sEmpty_Stack(s)/EMPTY(S)初始條件：棧s已存在。操作結(jié)果：若s為空棧返回為1(T)，否則返回為0(F)。(3)入棧：Push_Stack(s，x)初始條件：棧s已存在。操作結(jié)果：在棧s頂部插入一個新元素x，x成為新的棧頂元素。棧發(fā)生變化。

棧的基本運(yùn)算(4)出棧：Pop_Stack(s)初始條件：棧s存在且非空。操作結(jié)果：棧s的頂部元素從棧中刪除，棧中少了一個元素。棧發(fā)生變化。(5)讀棧頂元素：GetTop_Stack(s)初始條件：棧s存在且非空。操作結(jié)果：棧頂元素作為結(jié)果返回，棧不變化。

僅在表尾進(jìn)行插入、刪除操作的線性表。表尾(即an端)稱為棧頂;表頭(即a1端)稱為棧底。例如：棧S=(a1,a2,a3,……….,an-1,an)插入元素到棧頂?shù)牟僮?，稱為入棧。從棧頂刪除最后一個元素的操作，稱為出棧。an稱為棧頂元素a1稱為棧底元素想一想：要從棧中取出a1，應(yīng)當(dāng)如何操作？強(qiáng)調(diào)：插入和刪除都只能在表的一端（棧頂）進(jìn)行！棧：2棧的存儲結(jié)構(gòu)和運(yùn)算實(shí)現(xiàn)存儲結(jié)構(gòu)： 用順序棧或鏈棧存儲均可，但以順序棧更常見。邏輯結(jié)構(gòu)： 與線性表相同，仍為一對一關(guān)系。運(yùn)算規(guī)則： 只能在棧頂運(yùn)算，且訪問結(jié)點(diǎn)時依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）的原則。實(shí)現(xiàn)方式：關(guān)鍵是編寫入棧和出棧函數(shù)，具體實(shí)現(xiàn)因順序?；蜴湕５牟煌煌?。Q1：堆棧是什么？它與一般線性表有什么不同？

堆棧是一種特殊的線性表，它只能在表的一端（即棧頂）進(jìn)行插入和刪除運(yùn)算。與一般線性表的區(qū)別：僅在于運(yùn)算規(guī)則不同。一般線性表堆棧邏輯結(jié)構(gòu)：1:1邏輯結(jié)構(gòu)：1:1存儲結(jié)構(gòu)：順序表、鏈表存儲結(jié)構(gòu)：順序棧、鏈棧運(yùn)算規(guī)則：隨機(jī)存取/刪減運(yùn)算規(guī)則：后進(jìn)先出“進(jìn)”＝插入=壓入=PUSH（an+1)“出”＝刪除=彈出=POP(an)1）順序棧棧的順序存儲結(jié)構(gòu)簡稱為順序棧，它是運(yùn)算受限的線性表。因此，可用數(shù)組來實(shí)現(xiàn)順序棧。棧底位置是固定不變的，可以將棧底位置設(shè)置在數(shù)組的兩端的任何一個端點(diǎn)。棧頂位置是隨著進(jìn)棧和退棧操作而變化。需用一個整型變量top來指示當(dāng)前棧頂?shù)奈恢?通常稱top為棧頂指針)。順序棧的類型定義只需將順序表的類型定義中的長度cnt改為top即可。1）順序棧利用一組地址連續(xù)的存儲單元依次存放從棧底到棧頂?shù)娜舾蓴?shù)據(jù)元素。(1)定義：

#defineMaxSize1024typedefstructstack{ElemTypedata[MaxSize];

/*用一維數(shù)組存放自棧底到棧頂?shù)臄?shù)據(jù)元素*/inttop;

/*附設(shè)一個位置變量top*/}SeqStack;

設(shè)S是SeqStack類型的指針變量。若棧底位置在數(shù)組低端，即s–>data[0]是棧底元素.那么：進(jìn)棧：出棧：空棧：棧滿：上溢：下溢：1）順序棧s–>top加1；s–>top減1；s–>top=-1；s–>top=MaxSize-1。當(dāng)棧滿時再做進(jìn)棧運(yùn)算必定產(chǎn)生的空間溢出;當(dāng)棧空時再做出棧運(yùn)算產(chǎn)生的溢出。設(shè)數(shù)組S是一個順序棧棧S的最大容量MaxSize=4，初始狀態(tài)top=－1

10S[4]2310basetop=top+1S[top]=xtop

10

25

30S[4]2310topbase*x=S[top]top=top-1棧空10進(jìn)棧30出棧S[4]2310top=-1top棧滿top=MaxSize-1

10

25

30

40S[4]2310top=3basetop1）順序棧(2)初始化SeqStack*Init_SeqStack(){ SeqStack*s; s=(SeqStack*)malloc(sizeof(SeqStack));

s->top=-1; returns;};#defineMaxSize100intPush(SeqStack*S,intx){if(S->top==MaxSize－1)return0;S->top++;S->data[S->top]=x;return(1);}a2a3a4987654321a10top（3）入棧操作#defineMaxSize100intPush(SeqStack*S,intx){if(S->top==MaxSize－1)return(0);

S->top++;S->data[S->top]=x;return(1);}a2a3a4987654321a10top（3）入棧操作#defineMaxSize100intPush(SeqStack*S,intx){if(S->top==MaxSize－1)return(0);S->top++;

S->data[S->top]=x;return(1);}a2a3a4987654321a10topx（3）入棧操作

intPop(SeqStack*S,ElemType*x){if(S->top==－1){printf(“stackempty”);return(0);}else{*x=S->data[S->top];/*返回出棧元素*/S->top--;return(1);}

}通過指針變量x，帶回出棧元素a2a3a4987654321a10top（4）出棧操作a2a3a4987654321a10top*x

intPop(SeqStack*S,ElemType*x){if(S->top==－1){printf(“stackempty”);return(0);}else{

*x=S->data[S->top];/*返回出棧元素*/

S->top--;return(1);}

}（4）出棧操作（5）取棧頂元素elemtypeGetTop(SeqStack*s){ if(s->top<0) return0；//?？?/p>

elsereturn(s->data[s->top]);}順序棧的共享為兩個棧申請一個共享的一維數(shù)組空間S[M]將兩個棧的棧底分別放在一維數(shù)組的兩端，分別是0，M－1a1a2a3b5b4b3b2b10M－1top1top2a1a2a3

0M－1top共享?xiàng)５慕Y(jié)構(gòu)定義a1a2a3b5b4b3b2b10M－1top1top2#defineM100typedefstructstack{ElemTypedata[M];inttop1,top2;}SharedStack;共享?xiàng)５牟僮鱝1a2a3b5b4b3b2b10M－1top1top2判空：判滿：

top1==-1&&top2==M;top1+1==top2;共享?xiàng)５某跏蓟疭haredStack*InitSharedStack(){ SharedStack*s; s=(SharedStack*)malloc(sizeof(SharedStack)); s->top1=-1; s->top2=M; returns;}共享?xiàng)５倪M(jìn)棧操作intPush(SharedStack*S,ElemTypex,inti){ if(S->top[0]+1==S->top[1])return(0); switch(i)//i=1或2，表示堆棧號

{ case1:

S->top1++; S->data[S->top1]=x;break;

case2: S->top2--; S->data[S->top2]=x;break; default: return(0);} return(1);}共享?xiàng)５某鰲２僮鱥ntPop(SharedStack*S,ElemType*x,inti){switch(i){ case1: if(S->top1==-1)return(0); *x=S->data[S->top1]; S->top1--;break;

case2: if(S->top