數(shù)據(jù)結(jié)構(gòu)教案市公開課金獎市賽課一等獎?wù)n件

第0章緒論教學(xué)目的：1.掌握數(shù)據(jù)結(jié)構(gòu)基本概念；

2.掌握抽象數(shù)據(jù)類型概念和軟件結(jié)構(gòu)辦法

3.理解算法含義，掌握算法時間復(fù)雜度計(jì)算教學(xué)重點(diǎn)：1.數(shù)據(jù)結(jié)構(gòu)概念

2.抽象數(shù)據(jù)結(jié)構(gòu)軟件結(jié)構(gòu)辦法

3.時間復(fù)雜度計(jì)算教學(xué)難點(diǎn)：算法和算法時間復(fù)雜度作業(yè)：1-1

1-3

1-11（前三道小題）第1頁第1頁

一.基本概念數(shù)據(jù)：人們利用文字符號、數(shù)字符號以及其它要求符號對現(xiàn)實(shí)世界事物及其活動所作抽象描述．*數(shù)據(jù)元素：表示一個事物一組數(shù)據(jù)稱為一個數(shù)據(jù)元素．*數(shù)據(jù)項(xiàng)：構(gòu)成數(shù)據(jù)元素?cái)?shù)據(jù)稱為該數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)．抽象數(shù)據(jù)元素：沒有實(shí)際含義數(shù)據(jù)元素．抽象數(shù)據(jù)類型：沒有確切定義數(shù)據(jù)類型叫抽象數(shù)據(jù)類型，用符號DataType來表示．?dāng)?shù)據(jù)邏輯結(jié)構(gòu)：即為數(shù)據(jù)元素之間互相聯(lián)系方式．可分為線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)．1.1數(shù)據(jù)結(jié)構(gòu)基本概念第2頁第2頁二本門課程主要內(nèi)容數(shù)據(jù)存儲結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)中存儲方式．它基本形式有兩種：順序存儲結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)．?dāng)?shù)據(jù)操作：對一個數(shù)據(jù)類型數(shù)據(jù)進(jìn)行某種處理．?dāng)?shù)據(jù)操作集合：對一個數(shù)據(jù)類型數(shù)據(jù)所有操作．?dāng)?shù)據(jù)結(jié)構(gòu)課程主要討論表、堆棧、隊(duì)列、串、數(shù)組、樹、二叉樹、圖等典型慣用數(shù)據(jù)結(jié)構(gòu)．在討論這些結(jié)構(gòu)時，主要從它們邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)操作三個方面進(jìn)行分析討論．第3頁第3頁三.

.

數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)舉例假設(shè)要描述學(xué)生信息，看表1-1學(xué)生信息表學(xué)號

姓名性別年令01張三男20

02李四男21

03王五女22表中除第一行標(biāo)題行外，其它每一行為一個數(shù)據(jù)元素，每一列為一個數(shù)據(jù)項(xiàng)．三舉倒第4頁第4頁關(guān)于數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)描述都能夠使用某種高級程序設(shè)計(jì)語言來描述，本書采用C語言描述．如上表學(xué)生信息可定義為下列結(jié)構(gòu)體：

typedefstructstudent{charnumber[8];charname[10];charsex[3];intage;}studenttype用C語言描述

第5頁第5頁

有了上面定義后，studenttype就可看做與structstudent含義相同標(biāo)識符1．線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)ABCDABDFCEGABCDFEG結(jié)構(gòu)與標(biāo)識符由圖可見，線性結(jié)構(gòu)除第一個和最后一個數(shù)據(jù)元素外，每個數(shù)據(jù)元素只有一個前驅(qū)數(shù)據(jù)元素和一個后繼數(shù)據(jù)元素．而樹結(jié)構(gòu)是除根結(jié)點(diǎn)外每個元素只有一個前驅(qū)元素，可有零個或若干個后繼元素．圖每個元素可有零或多個前驅(qū)或后繼元素．第6頁第6頁1.

把數(shù)據(jù)元素存放在一塊連續(xù)地址空間內(nèi)存中，其特點(diǎn)是邏輯上相鄰數(shù)據(jù)元素在物理上也相鄰，數(shù)據(jù)間邏輯關(guān)系表現(xiàn)在數(shù)據(jù)元素存放位置上．以下圖所表示：

a0

a1a2……an-2an-1

2。順序存儲結(jié)構(gòu)0

12

ｎ-2

ｎ-1第7頁第7頁使用指針把相互直接關(guān)聯(lián)結(jié)點(diǎn)鏈接起來，其特點(diǎn)是邏輯上相鄰數(shù)據(jù)元素在物理上不一定相鄰，數(shù)據(jù)間邏輯關(guān)系表現(xiàn)在結(jié)點(diǎn)鏈接關(guān)系上．以下圖示3。鏈?zhǔn)酱鎯Y(jié)構(gòu)第8頁第8頁

數(shù)據(jù)類型：指一個類型和定義在這個類型上操作集合.比如，當(dāng)說計(jì)算機(jī)中整數(shù)數(shù)據(jù)類型時，就不但指計(jì)算機(jī)所能表示整數(shù)數(shù)值集合，而且指能對這個整數(shù)類型進(jìn)行+、-、*、＼和求模（％）操作．抽象數(shù)據(jù)類型（AbstractDataType縮寫為ADT）：是指一個邏輯概念上類型和這個類型上操作集合．?dāng)?shù)據(jù)類型和抽象數(shù)據(jù)類型不同之處于于：數(shù)據(jù)類型指是高級程序設(shè)計(jì)語言支持基本數(shù)據(jù)類型，而抽象數(shù)據(jù)類型指是在基本數(shù)據(jù)類型支持下用戶新設(shè)計(jì)數(shù)據(jù)類型．像表、堆棧、隊(duì)列、串、數(shù)組、樹、圖等就是一個個不同抽象數(shù)據(jù)類型．12抽象數(shù)據(jù)類型和軟件結(jié)構(gòu)辦法第9頁第9頁13。算法和算法時間復(fù)雜度（1）1.3.1算法算法是描述求解問題辦法操作環(huán)節(jié)集合．它主要有三種形式：文字形式偽碼形式和程序設(shè)計(jì)語言形式．例1-1設(shè)計(jì)一個把存儲在數(shù)組A中ｎ個抽象數(shù)據(jù)元素ａ0，ａ1，…，ａｎ-1逆置算法，即要求逆置后數(shù)組中數(shù)據(jù)元素序列為ａｎ－１，…ａ1，ａ0，并要求原數(shù)組中數(shù)據(jù)元素值不能被改變．設(shè)計(jì)：這是一個算法設(shè)計(jì)問題．該算法要求有一個表示元素個數(shù)輸入?yún)?shù)ｎ，一個表示原數(shù)組輸入?yún)?shù)ａ和一個表示逆置后數(shù)組輸出參數(shù)ｂ．第10頁第10頁．算法設(shè)計(jì)下列：voidReverse(intn,DataTypea[],DataTypeb[]){inti;for(i=0;i<n;i++)b[i]=a[n-1-i];}算法時間復(fù)雜度（2）第11頁第11頁該算法實(shí)現(xiàn)辦法如圖1-3所表示．b0+3?a0?b1+3?.?a1?.?bn-2?an-2?bn-1?An-1?

圖1-3例1-1算法實(shí)現(xiàn)辦法圖示該算法實(shí)現(xiàn)辦法第12頁第12頁

設(shè)計(jì)一個把存儲在數(shù)組A中ｎ個抽象數(shù)據(jù)元素ａ0，ａ1，…，ａｎ-1就地逆置算法，即要求逆置后數(shù)組中數(shù)據(jù)元素序列為ａｎ－１，…ａ1，ａ0，并要求原數(shù)組中數(shù)據(jù)元素值被改變．設(shè)計(jì)：這是另一個算法設(shè)計(jì)問題．該算法要求有一個表示元素個數(shù)輸入?yún)?shù)ｎ，一個表示原數(shù)組輸入?yún)?shù)ａ和一個表示逆置后數(shù)組輸出參數(shù)ｂ．由于要求原數(shù)組中數(shù)據(jù)元素這被改變，因此輸出參數(shù)ｂ必須與輸入?yún)?shù)ａ相同，因此，這兩個參數(shù)應(yīng)設(shè)計(jì)為同一個參數(shù)，其參數(shù)類型設(shè)計(jì)為輸入輸出混合型參數(shù)．例1---2第13頁第13頁算法設(shè)計(jì)下列：voidReverse(intn,DataTypea[]){inti,m=n/2;DataTypetemp;for(i=0;i<m;i++){temp=a[i];a[i]=a[n–1–i];a[n–1–i]=temp;}該算法實(shí)現(xiàn)辦法如圖1—4所表示p20算法設(shè)計(jì)第14頁第14頁

(1)正確性能(2)可讀性

(3)健壯性

(4)

高時間效率

(5)

高空間效率13.2算法設(shè)計(jì)目的第15頁第15頁.（1）

事后統(tǒng)計(jì)辦法（2）

事前分析辦法事前分析辦法主要分析算法時間效率與算法所處理數(shù)據(jù)個數(shù)ｎ函數(shù)關(guān)系定義1-1

T(n)=O(f(n))當(dāng)且僅當(dāng)存在正常數(shù)c和n0對所有n(n≥n0)滿足T(n)≤c*f(n).即：當(dāng)算法時間復(fù)雜度T(n)與數(shù)據(jù)個數(shù)n無關(guān)系時，T(n)≤c﹡1，因此此時算法時間復(fù)雜度T(n)=

O(1)；當(dāng)算法時間復(fù)雜度T(n)與數(shù)據(jù)個數(shù)n為線性關(guān)系時，因此此時算法時間復(fù)雜度T(n)=O(ｎ)；依次類推分析一個算法中基本語句執(zhí)行次數(shù)與數(shù)據(jù)個數(shù)函數(shù)關(guān)系，就可求出該算法時間復(fù)雜度．13.3算法時間效率度量第16頁第16頁例1-3

設(shè)數(shù)組ａ和ｂ在前邊部分已賦值，求下列兩個ｎ階矩陣相乘運(yùn)算算法時間復(fù)雜度．for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;／*基本語句1*／for(k=0;k<n;k++)c[i][j]=c[i][j]+a[i][j]b[k][j];/*基本語句2*/}舉例闡明下面舉例闡明算法時間復(fù)雜度分析辦法：第17頁第17頁解：設(shè)基本語句執(zhí)行次數(shù)為f(n)，有f(n)=c1*n2+c2*n3因T(n)=f(n)=c1*n2+c2*n3=c*n3，其中c1,c2,c可為任意常數(shù)，因此該算法時間復(fù)雜度為T(n)=O(n3)

第18頁第18頁例1-6

下邊算法是在一個有ｎ個數(shù)據(jù)元素?cái)?shù)組ａ中刪除第ｉ個位置數(shù)組元素，要求當(dāng)刪除成功時數(shù)組元素個數(shù)減1，求該算法時間復(fù)雜度．其中，數(shù)組下標(biāo)為0～ｎ-1．intDelete(inta[],int*n,inti){?intj;f(i<0‖I>=*n)return0;/*刪除位置錯誤，失敗返回*/ifor(j=i+1;j<*n;j++)a[j-1]=a[j];/*順次移位填補(bǔ)*/(*n)--;/*數(shù)組元素個數(shù)減1*/return;/*刪除成功返回*/}第19頁第19頁

解：此算法時間復(fù)雜度隨刪除數(shù)據(jù)位置不同而不同．當(dāng)刪除最終一個位置數(shù)組元素時有i＝n－1，j＝i+1＝n，故不需要移位填補(bǔ)二循環(huán)次數(shù)為0，…，當(dāng)刪除第一個位置數(shù)組元素時有i＝0，j＝i+1＝1，需移位填補(bǔ)n－1次而循環(huán)次數(shù)為n－1．此時算法時間復(fù)雜度應(yīng)是刪除數(shù)據(jù)位置等概率取值情況下平均次數(shù)．設(shè)為刪除第個位置上數(shù)據(jù)元素概率，則有，設(shè)E為刪除數(shù)組元素平均次數(shù)，則有E=1/n∑0n-1(n-1-i)=1/n[(n-1)+(n-2)+…2+1+0]=1*/n1n(n-1)/2=(n–1)/2因T(n)=E≤(n–1)/2≤c*n，其中c為常數(shù)，因此該算法等概率平均時間復(fù)雜度為T(n)=0(n)

算法時間復(fù)雜度隋刪除數(shù)據(jù)位置不同而不同第20頁第20頁（）

(1)

各種符號均以英語單詞命名，所有命名應(yīng)見名知意．(2)

變量名字母均小寫，若單詞多于一個時，第二個單詞首字母大寫．

(3)

自定義結(jié)構(gòu)體名常量名和文獻(xiàn)名均小寫．但所有單詞首字母大寫．可縮寫．

(4)

函數(shù)中抽象數(shù)據(jù)類型參數(shù)用單字母大寫，順序表SeqList類型參數(shù)L．1.4算法書寫要求第21頁第21頁教學(xué)目的：1.理解線性表抽象數(shù)據(jù)類型2.掌握線性表順序表示和實(shí)現(xiàn)3.掌握線性表鏈?zhǔn)奖硎竞蛯?shí)4.掌握靜態(tài)鏈表概念5.掌握順序表和單鏈表算法設(shè)計(jì)教學(xué)重點(diǎn)：1.概念理解2.線性表操作3.算法設(shè)計(jì)辦法教學(xué)難點(diǎn)：線性表概念，順序表和鏈表操作作業(yè)：2-11

2-12第二章線性表第22頁第22頁2.1.1線性表定義線性表是一個能夠在任意位置進(jìn)行插入和刪除數(shù)據(jù)元素操作由n(n≥0)個相同類型數(shù)據(jù)元素a0,a1,a2,…,an-1構(gòu)成線性結(jié)構(gòu)．順序存儲結(jié)構(gòu)存儲數(shù)據(jù)元素詳細(xì)是用數(shù)組存儲，數(shù)據(jù)元素編號從0開始．2。1。1線性表抽象數(shù)據(jù)類別第23頁第23頁.

線性表抽象數(shù)據(jù)類型主要包括兩個方面，即數(shù)據(jù)集合和該數(shù)據(jù)集合上操作集合．

數(shù)據(jù)集合：線線性表數(shù)據(jù)集合能夠表示為a0,a1,a2,…,an-1或a1,a2,…,an，每個數(shù)據(jù)據(jù)元素?cái)?shù)據(jù)類型為抽象數(shù)據(jù)元素類型DataType．

2.1.2線性表抽象數(shù)據(jù)類型第24頁第24頁操作集合.

（1）初始化

ListInitiate(L)：初始化線性表

L.（2）求當(dāng)前數(shù)據(jù)元素個數(shù)(ListLength(L)：函數(shù)返回線性表L當(dāng)前數(shù)據(jù)元素個數(shù)

．

（3）

插入數(shù)據(jù)元素ListInsert(L,i,x)：在線性表L第i個數(shù)據(jù)前插入數(shù)據(jù)元素x

（4）

刪除數(shù)據(jù)元素ListDelete(L,i,x)：刪除線性表L第i個數(shù)據(jù)元素，所刪除數(shù)據(jù)元素x由輸出參數(shù)帶回．（5）

取數(shù)據(jù)元素ListGet(L,i,x)：取線性表L第i個數(shù)據(jù)元素，所取數(shù)據(jù)元素x由輸出參數(shù)帶回．第25頁第25頁2。2線性順序表示和實(shí)現(xiàn)線性表抽象數(shù)據(jù)類型有兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)；鏈?zhǔn)酱鎯Y(jié)構(gòu)．順序存儲結(jié)構(gòu)線性表稱作順序表．2.2.1

順序表存儲結(jié)構(gòu)數(shù)組有靜態(tài)數(shù)組和動態(tài)數(shù)組兩種．靜態(tài)數(shù)組存儲空間申請和釋放由系統(tǒng)自動完畢，動態(tài)數(shù)組存儲空間申請和釋放由用戶通過調(diào)用系統(tǒng)函數(shù)完畢．順序表普通采用靜態(tài)數(shù)組辦法實(shí)現(xiàn)數(shù)據(jù)元素存儲．第26頁第26頁順序表存儲結(jié)構(gòu)示意圖下列：List

0123456MaxSize-1size=5為用C語言描述上圖所表示順序表，定義結(jié)構(gòu)體

SeqList下列：typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;a0a1a2a3a4順序表存儲結(jié)構(gòu)示意圖第27頁第27頁（1）

初始化ListInitiate(SeqList*L)voidListInitiate(SeqList*L)/*初始化順序表L*/{L->size=0;/*定義初始數(shù)據(jù)元素個數(shù)*/}（2）

求當(dāng)前數(shù)據(jù)元素個數(shù)(ListLength(L)intListLength(SeqListL)

/*返回順序表L當(dāng)前數(shù)據(jù)元素個數(shù)*/{returnL.size;}2.2.2順序表操作實(shí)現(xiàn)第28頁第28頁（3）

插入數(shù)據(jù)元素ListInsert(L,i,x)intListInsert(SeqList*L,inti,DataTypex)/*在順序表L第i（0≤i≤size）個位置前插入數(shù)據(jù)元素x*//*插入成功返回1，插入失敗返回0*/{intj;if(L->size>=MaxSize){printf(“順序表已滿無法插入?。躰”);return0;}elseif(i<0‖i>L->size){

2。2。2順序表操作實(shí)現(xiàn)（2）第29頁第29頁插入數(shù)據(jù)元素（一）printf(“參數(shù)i不合法?。躰”);

return0;}return0;}else{/*為插入做準(zhǔn)備*/

for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];L->list[i]=x;

/*插入x*/第30頁第30頁L->size++;/*元素個數(shù)加1*/return1;}}插入步驟：首先把存放單元size-1至存放單元i中數(shù)據(jù)元素依次后移一個存放單元，然后把數(shù)據(jù)元素x插入到存放單元i中（注意此操作是前插），最終把數(shù)據(jù)元素個數(shù)加1．其過程以下圖：list01234567MaxSIZE-1…

插入數(shù)據(jù)元素（二）

1011121314151610111214151613list

0

1

2

3

4

5

6

7

MaxSize-1

第31頁第31頁（1）

（intintListDelete(SeqList*L,inti,DataType*x)//*刪除順序表L中位置為i（0≤i≤size-1）數(shù)據(jù)元素并存儲到x中*//*/*刪除成功返回1，刪除失敗返回0*/{)?intj;if(L->size<=0){printf(“順序表已空無法刪除！＼n”);return0;}（4）刪除數(shù)據(jù)元素取數(shù)據(jù)元素ListDelete(L,i,x)第32頁第32頁elseif(i<0‖i>L->size){printf(“參數(shù)i不合法?。躰”);

return0;}Else{*x=L->list[i];/*保留刪除元素到x中*//*依次前移*/

for(j=i+1;j<=L->size-1;j++)L->list[j-1]=L->list[j];L->size--;/*數(shù)據(jù)元素個數(shù)減1*/return1;)?)?

刪除和取數(shù)據(jù)元素（二）第33頁第33頁（5））

取數(shù)據(jù)元素ListGet(L,i,x)intListGet(SeqListL,inti,DataType*x)//*取順序表L中第i個數(shù)據(jù)元素存于x中成功返回1失敗返回0*/{if(i<0‖i>L.size-1){printf(“參數(shù)i不合法＼n”);return0;}else{x=L.list[i];return1）?）?;（5）取數(shù)據(jù)元素第34頁第34頁順序表上插入和刪除是順序表中時間復(fù)雜度最高組員函數(shù)．在順序表中插入一個數(shù)據(jù)元素時，最壞情況是pos＝0，需移動size個數(shù)據(jù)元素；最好情況是pos＝size，需移動0個數(shù)據(jù)元素．設(shè)pi是在第i個存儲位置上插入一個數(shù)據(jù)元素概率，設(shè)順序表中數(shù)據(jù)元素個數(shù)為n，當(dāng)在順序表任何位置上插入數(shù)據(jù)元素概率相等時，有pi＝1/（n+1），，則向順序表插入一個數(shù)據(jù)元素需移動數(shù)據(jù)元素平均次數(shù)為：Eis=∑0npi(n-i)=∑0n(n-i)=n/2刪除操作時間復(fù)雜度計(jì)算見教材ｐ33．順序表中其余操作都與數(shù)據(jù)元素個數(shù)n無關(guān)，在順序表中插入和刪除一個數(shù)據(jù)元素時間復(fù)雜度為O(n)，其余操作時間復(fù)雜度為O(1)．2。2。3順序表操作分析第35頁第35頁2。2。4順序表應(yīng)用舉例請同窗們自己分析例題算法第36頁第36頁2。3線性表鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)指針：指向物理存儲單元地址變量結(jié)點(diǎn)：由數(shù)據(jù)元素域和一個或若干個指針域構(gòu)成一個結(jié)構(gòu)體鏈表：鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表鏈表主要有單鏈表、單循環(huán)鏈表和雙向循環(huán)鏈表三種．第37頁第37頁單鏈表是構(gòu)成鏈表結(jié)點(diǎn)只有一個指向直接后繼結(jié)點(diǎn)指針域．1.

單鏈表表示辦法定義單鏈表結(jié)點(diǎn)結(jié)構(gòu)體下列：typedefstructNode{DataTypedata;structNode*next;}SLNode;數(shù)據(jù)域指針域

datanext2。3。1單鏈表存儲結(jié)構(gòu)（1）第38頁第38頁其中，data域用來存儲數(shù)據(jù)元素，next域用來存儲指向下一個結(jié)點(diǎn)指針．單鏈表有帶頭結(jié)點(diǎn)結(jié)構(gòu)和不結(jié)點(diǎn)結(jié)構(gòu)兩種．指向單鏈表指針稱作頭指針，頭指針?biāo)覆淮鎯?shù)據(jù)元素第一個結(jié)點(diǎn)稱為頭結(jié)點(diǎn)．存儲第一個數(shù)據(jù)元素結(jié)點(diǎn)稱為第一個數(shù)據(jù)元素結(jié)點(diǎn)．符號＂∧＂表示空指針，空指針是一個特殊標(biāo)識，用來標(biāo)識鏈結(jié)束．空指針在算法描述中用NULL表示．在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，數(shù)據(jù)元素邏輯順序是通過鏈中指針鏈接實(shí)現(xiàn)．2。3。1（2）第39頁第39頁(1）帶頭單鏈表每個元素存貯區(qū)別為兩大部分：headpdatanext帶頭和不帶頭結(jié)點(diǎn)單鏈表比較a0

an-1∧

X∧

上圖是在帶頭結(jié)點(diǎn)單鏈表第一個數(shù)據(jù)元素前插入結(jié)點(diǎn)前圖示第40頁第40頁a0a1an-1

∧x上圖是在帶頭結(jié)點(diǎn)單鏈表第一個數(shù)據(jù)元素前插入結(jié)點(diǎn)后圖示．也可參考下圖：headp

s帶頭和不帶頭結(jié)點(diǎn)單鏈表比較（2）第41頁第41頁plen

a1?

an?

?a2?headq

單鏈表插入結(jié)點(diǎn)P->next=q;q->next=p->next;第42頁第42頁Headpnext

a0a1

a

n-1∧上圖是刪除帶頭結(jié)點(diǎn)單鏈表第一個數(shù)據(jù)元素結(jié)點(diǎn)示意圖第43頁第43頁22）不帶頭結(jié)點(diǎn)單鏈表插入刪除數(shù)據(jù)元素結(jié)點(diǎn)示意圖下列：在第一個數(shù)據(jù)元素前插入結(jié)點(diǎn)時，頭指針head值將改變?yōu)樾虏迦虢Y(jié)點(diǎn)指針s，其插入過程下列：heada0

a1an-1?

x∧插入刪除數(shù)據(jù)元素結(jié)點(diǎn)示意圖第44頁第44頁在第一個數(shù)據(jù)元素前插入結(jié)點(diǎn)時，頭指針head值將改變?yōu)樾虏迦虢Y(jié)點(diǎn)指針s，其插入過程下列：

head插入前示意圖shead

sa0上圖是在不帶頭結(jié)點(diǎn)單鏈表第一個數(shù)據(jù)元素前插入結(jié)點(diǎn)后示意圖

a0a1an-1

∧x∧a0a1an-1

∧x不帶頭結(jié)點(diǎn)單鏈表插入刪除數(shù)據(jù)元素示意圖第45頁第45頁在不帶頭結(jié)點(diǎn)單鏈表其它數(shù)據(jù)元素前插入結(jié)點(diǎn)示意圖下列：headdatanextpa0ai-1

aian-1∧

X?

s插入結(jié)點(diǎn)示意圖第46頁第46頁類似地，刪除不帶頭結(jié)點(diǎn)單鏈表第一個數(shù)據(jù)元素結(jié)點(diǎn)時，頭指針head值將改變?yōu)閔ead->next，即指針head等于原h(huán)ead->next值headdatanexta0

a1

an-1∧

刪除不帶頭結(jié)點(diǎn)示意第47頁第47頁

刪除不帶頭結(jié)點(diǎn)單鏈表其它數(shù)據(jù)元素結(jié)點(diǎn)時示意圖下列

：headdatanextpa0ai-1aiai+1an-1

∧第48頁第48頁單鏈表是由一個個結(jié)點(diǎn)鏈接構(gòu)成，單鏈表中每個結(jié)點(diǎn)結(jié)構(gòu)體定義下列：typedefstructNode{

DataTypedata;structNode*next;}SLNode;在帶頭結(jié)點(diǎn)單鏈存儲結(jié)構(gòu)下，線性表抽象數(shù)據(jù)類型操作集合中各個操作詳細(xì)實(shí)現(xiàn)辦法下列：（1）

初始化ListInitiate(SLNode**head)

voidListInitiate(SLNode**head)/*初始化*/{/*假如有內(nèi)存空間，申請頭結(jié)點(diǎn)空間并使頭指針head指向頭結(jié)點(diǎn)*/if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1)(*head)->next=NULL;}

第49頁第49頁intListLength(SLNode*head){SLNode*p=head;/*ｐ指向頭結(jié)點(diǎn)*/intsize=0;/*size初始為0*/while(p->next!=NULL)/*循環(huán)計(jì)數(shù)*/{

p=p->next;size++;}returnsize;

}（2）求當(dāng)前數(shù)據(jù)元素個數(shù)ListLength(SLNode*head)求當(dāng)前數(shù)據(jù)元數(shù)個數(shù)第50頁第50頁headpsize=0a0

a1

an-1

^headpsize=na0

a1

an-1∧∧

接上面第51頁第51頁（1）（（3）

插入ListInsert(SLNode*head,inti,DataTypex)

intListInsert(SLNode*head,inti,DataTypex)/*在帶頭結(jié)點(diǎn)單鏈表head第i(0≤i≤size)個結(jié)點(diǎn)前*/

/*插入一個存儲數(shù)據(jù)元素x結(jié)點(diǎn)．插入成功時返回1，失敗返回0*/{SLNode*p,*q;intj;

while(p->next!=NULL&&j<i-1)

/*最后讓指針p指向第i-1個結(jié)點(diǎn)*/{p=p->next;j++;}插入存儲數(shù)據(jù)元素結(jié)點(diǎn)（1）第52頁第52頁if(j!=i-1){printf(“插入位置參數(shù)錯!”);return0;}/*生成新結(jié)點(diǎn)由指針q批示*/if(q=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1)q->data=x;q->next=p->next;/*插入環(huán)節(jié)1*/p->next=q;/*插入環(huán)節(jié)2*/return1;}插入存儲數(shù)據(jù)元素結(jié)點(diǎn)（2）第53頁第53頁（4）

刪除取數(shù)據(jù)元素ListDelete(SLNode*head,inti,DataTypex)

intListDelete(SLNode*head,inti,DataTypex)/*刪除帶頭結(jié)點(diǎn)單鏈表head第i（0≤i≤size-1）個結(jié)點(diǎn)*//*被刪除結(jié)點(diǎn)數(shù)據(jù)元素域值由x帶回．刪除成功時返回1，失敗返回0*/{SLNode*p,*s;intj;p=head;j=-1;刪除取數(shù)據(jù)元素（1）第54頁第54頁while(p->next!=NULL&&p->next->next!=NULL&&j<i-1){/*最后讓指針ｐ指向第i-1個結(jié)點(diǎn)*/

p=p->next;j++;}if(j!=i-1){printf(“刪除位置參數(shù)錯!”);return0;}

s=p->next;/*指針ｓ指向ai結(jié)點(diǎn)*/*x=s->data;/*把指針ｓ所指向結(jié)點(diǎn)數(shù)據(jù)元素域值賦予x*/p->next=p->next->next;/*刪除*/free(s);/*釋放指針ｓ所指向結(jié)點(diǎn)內(nèi)存空間*/return1;}刪除取數(shù)據(jù)元素（2）第55頁第55頁（5）

取數(shù)據(jù)元素ListGet(SLNode*head,inti,DataTypex)

intListGet(SLNode*head,inti,DataTypex){SLNode*p;intj;

p=head;j=-1;while(p->next!=NULL&&j<i){p=p->next;j++;}if(j!=i){printf(“取元素位置參數(shù)錯！”);

return0;}x=p->data;return1;}

取數(shù)據(jù)元素第56頁第56頁（6）

撤消單鏈表Destroy(SLNode**head)

voidDestroy(SLNode**head){SLNode*p,*p1;p=*head;

while(p!=NULL){p1=p;p=p->next;free(p1);}head=NULL;}

撤消單鏈表第57頁第57頁當(dāng)在單鏈表任何位置上插入數(shù)據(jù)元素概率相等時，在單鏈表中插入一個數(shù)據(jù)元素時比較數(shù)據(jù)元素平均次數(shù)為：Eis=∑0npi(n-i)=1/(n+1)∑0n(n-i)=n/2刪除單鏈表一個數(shù)據(jù)元素時比較數(shù)據(jù)元素平均次數(shù)為：Edl=∑0n-1qi(n-i)=1/n∑0n-1(n-i)=(n-1)/2單鏈表數(shù)據(jù)元素個數(shù)操作時間復(fù)雜度為T（n）=O（n）單鏈表主要長處是不需要預(yù)先擬定數(shù)據(jù)元素最大個數(shù)，插入和刪除操作時不需要移動數(shù)據(jù)元素；主要缺點(diǎn)是每個結(jié)點(diǎn)中要有一個指針域，因此，空間單元利用效率不高．另外，單鏈表操作算法較復(fù)雜．2。3。3單鏈表操作效率分析第58頁第58頁本章結(jié)束時，再行分析．2。3。4單鏈表應(yīng)用舉例第59頁第59頁循環(huán)單鏈表是單鏈表另一個形式，其結(jié)構(gòu)特點(diǎn)是鏈表中最后一個結(jié)點(diǎn)指針域不再是結(jié)束標(biāo)識∧，而是指向整個鏈表第一個結(jié)點(diǎn)，從而使鏈表形成一個環(huán)．帶頭結(jié)點(diǎn)循環(huán)鏈表操作與帶頭單鏈表操作相同，差別在于：1.

在初始化函數(shù)中，把語句(*head)->next=NULL改為(*head)->next=head．2.

在其它函數(shù)中，循環(huán)判斷條件p->next!=NULL和p->next->next!=NULL中NULL改為頭指針head．

2。3。5循環(huán)單鏈表第60頁第60頁1.雙向鏈表存儲結(jié)構(gòu)雙向鏈表是每個結(jié)點(diǎn)除后繼指針域外尚有一個前驅(qū)指針域．這里討論是帶頭結(jié)點(diǎn)雙向循環(huán)鏈表．在雙向鏈表中，每個結(jié)點(diǎn)包括三個域，分別是data域﹑next域﹑prior域．雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)體定義下列：

priordatanext

typedefstructNode{DataTypedata;structNode*next;structNode*prior;}DLNode;雙向循環(huán)鏈表后繼指針和前驅(qū)指針各自構(gòu)成自己單循環(huán)鏈表，見圖ｐ482-17．雙向鏈表有助于頻繁查找當(dāng)前結(jié)點(diǎn)后繼結(jié)點(diǎn)和當(dāng)前結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)．2。3。6雙向鏈表第61頁第61頁3.雙向鏈表操作實(shí)例

ai1

ai

ai+1

設(shè)指針ｐ指向雙向鏈表中第i個結(jié)點(diǎn)，則p->next指向第i+1個結(jié)點(diǎn)，p->next->prior仍指向第i個結(jié)點(diǎn)，即p->next->prior==p；同樣地，p->prior指向第i-1個結(jié)點(diǎn)，p->prior->next仍指向第i個結(jié)點(diǎn)，即p->prior->next==p．p

head

雙向鏈表指針關(guān)系空鏈表第62頁第62頁雙向鏈表操作實(shí)現(xiàn)下列：(1)初始化voidListInitiate(DLNode**head){if(*head=(DLNode*)malloc(sizeof(DLNode)))==NULL)exit(0);(*head)->prior=*head;/*構(gòu)成前驅(qū)指針循環(huán)鏈*/(*head)->next=*head;/*構(gòu)成后繼指針循環(huán)鏈*/}操作實(shí)現(xiàn)下列第63頁第63頁/*在帶頭結(jié)點(diǎn)雙向循環(huán)鏈表第i個結(jié)點(diǎn)前*//*插入一個存儲數(shù)據(jù)元素x結(jié)點(diǎn)．插入成功返回1，失敗返回0*/intListInsert(DLNode*head,inti,DataTypex){DLNode*p,*s;intj;

p=head->next;j=0;

while(p!=head&&j<i)/*尋找第i結(jié)點(diǎn)*/{p=p->next;j++;}if(j!=i){printf(“插入位置參數(shù)犯錯！”)

return0;}(2)插入數(shù)據(jù)元素（1）第64頁第64頁if((s=(DLNode*)malloc(sizeof(DLNode)))==NULL)exit(0);s->data=x;s->prior=p->prior;/*插入環(huán)節(jié)1*/p->prior->next=s;/*插入環(huán)節(jié)2*/s->next=p;/*插入環(huán)節(jié)3*/p->prior=s;/*插入環(huán)節(jié)4*/

return1;}(2)插入數(shù)據(jù)單元（2）第65頁第65頁循環(huán)雙向鏈表插入過程下列：head

p

插入過程

a

ai1

ai

an-1xs第66頁第66頁intListDelete(DLNode*head,inti,DataType*x)/*刪除帶頭結(jié)點(diǎn)雙向循環(huán)鏈表head第i(0≤i≤size-1)個結(jié)點(diǎn)*//*被刪除結(jié)點(diǎn)數(shù)據(jù)元素域值由x帶回，刪除成功時返回1，失敗返回0*/{DLNode*p;intj;

p=head->next;j=0;while(p->next!=head&&j<i)/*尋找第ｉ個結(jié)點(diǎn)*/{

p=p->next;j++;}（3）刪除數(shù)據(jù)無數(shù)（1）第67頁第67頁（3）刪除數(shù)據(jù)元素（2）if(j!=i){printf(“刪除位置參數(shù)犯錯！”);

return0;{p->prior->next=p->next;/*刪除環(huán)節(jié)1*/p->next->prior=p->prior;/*刪除環(huán)節(jié)2*/*x=p->data;free(p);return1;}

第68頁第68頁voidDestroy(DLNode**head){DLNode*p,*p1;inti,n=ListLength(*head);

p=*head;for(i=0;i<=n;i++){p1=p;p=p->next;free(p1);}head=NULL;}（4）撤消內(nèi)存空間Destroy(DLNode**head)

第69頁第69頁2。4靜態(tài)鏈表2。5算法設(shè)計(jì)舉例（1）2.5.1

順序表算法設(shè)計(jì)舉例例2-4

結(jié)構(gòu)一個順序表刪除算法，把順序表L中數(shù)據(jù)元素ｘ刪除．算法思想；此刪除問題可通過一個循環(huán)比較過程來實(shí)現(xiàn)算法設(shè)計(jì)下列：intListDataDelete(SeqList*L,DataTypex){inti,j;第70頁第70頁for(i=0;i<L->size;i++)/*尋找元素x*/if(x==L->list[i])break;if(i==L->size)return0;/*未尋找到元素x*/else/*尋找到元素*/{

for(j=i;j<L->size;j++)/*元素依次前移*/L->list[j]=L->list[j+1];L->size--;/*元素個數(shù)減1*/

return1;}}算法設(shè)計(jì)舉例（2）第71頁第71頁例2-5

設(shè)頭指針為head，并設(shè)帶頭結(jié)點(diǎn)單鏈表中數(shù)據(jù)元素遞增有序，編寫算法將數(shù)據(jù)元素x插入到帶頭結(jié)點(diǎn)單鏈表適當(dāng)位置，要求插入后保持單鏈表數(shù)據(jù)元素遞增有序．算法思想；從鏈表第一個數(shù)據(jù)元素結(jié)點(diǎn)開始，逐一比較每個結(jié)點(diǎn)data域值和x值，當(dāng)data小于等于x時，進(jìn)行下一個結(jié)點(diǎn)比較；不然，就找到了插入結(jié)點(diǎn)適當(dāng)位置，此時申請新結(jié)點(diǎn)把x存入，然后把新結(jié)點(diǎn)插入；當(dāng)比較到最后一個結(jié)點(diǎn)仍有data小于等于x時，則把新結(jié)點(diǎn)插入單鏈表尾．2。5。2單鏈表算法設(shè)計(jì)舉例第72頁第72頁voidLinListInsert(SLNode*head,DataTypex){SLNode*curr,*pre,*q;/*循環(huán)初始化*/curr=head->next;/*curr指向第一個設(shè)計(jì)元素結(jié)點(diǎn)*/pre=head;/*pre指向頭結(jié)點(diǎn)*//*循環(huán)定位插入位置*/while(curr!=NULL&&curr->data<=x){pre=curr;curr=curr->next;}學(xué)生分析剩余例題．算法設(shè)計(jì)下列第73頁第73頁教學(xué)目的：1.掌握堆棧基本概念2.理解堆棧抽象數(shù)據(jù)類型

3.純熟掌握堆棧表示和實(shí)現(xiàn)

4.掌握隊(duì)列基本概念

5.掌握順序循環(huán)隊(duì)列表示和實(shí)現(xiàn)

6.掌握鏈?zhǔn)疥?duì)列存儲結(jié)構(gòu)和操作實(shí)現(xiàn)教學(xué)重點(diǎn)：1.堆棧表示和實(shí)現(xiàn)

2.隊(duì)列實(shí)現(xiàn)教學(xué)難點(diǎn)：堆棧實(shí)現(xiàn)

第三章堆棧和隊(duì)列第74頁第74頁3.1.1

堆?；靖拍疃褩Ｊ且粋€特殊線性表．其數(shù)據(jù)元素以及數(shù)據(jù)元素間邏輯關(guān)系和線性表完全相同，差別在于線性表允許在任意位置插入和刪除，而堆棧只允許在棧頂進(jìn)行操作．堆棧也稱作后進(jìn)先出表．它可完畢比較復(fù)雜數(shù)據(jù)元素特定序列轉(zhuǎn)換任務(wù)．3。1堆棧第75頁第75頁

數(shù)據(jù)集合：堆棧數(shù)據(jù)集合能夠表示為a0,a1,…,an-1每個數(shù)據(jù)元素?cái)?shù)據(jù)類型為DataType.操作集合：1.初始化StackInitiate(S)：初始化堆棧S2.非空否StackNotEmpty(S)：堆棧S非空否．若堆棧非空，則函數(shù)返回1；不然，返回03.入棧StackPush(S,x)：在堆棧當(dāng)前棧頂插入數(shù)據(jù)元素x．4.出棧StackPop(S,d)：把堆棧S當(dāng)前棧頂數(shù)據(jù)元素刪除并由參數(shù)d帶回．5.取棧頂數(shù)據(jù)元素StackTop(S,d)：取堆棧S當(dāng)前棧頂數(shù)據(jù)元素并由參數(shù)d帶回以上3.4.5均為成功返回1；不然，返回03。1。2堆棧抽象數(shù)類型

3。1。2堆棧抽象數(shù)據(jù)類型第76頁第76頁

1.

1.順序堆棧存儲結(jié)構(gòu)順序堆棧存儲結(jié)構(gòu)示意圖下列：Stack棧底棧頂012345MaxStackSize-1top用C語言定義上述順序堆棧結(jié)構(gòu)體SeqStack下列：typedefstruct{DataTypestack[MaxStackSize];inttop;}SeqStack;

a0a1a2a3a43。1。3堆棧順序表示和實(shí)現(xiàn)第77頁第77頁;

.

(1)初始化StackInitiate(S)voidStackInitiate(SeqStack*S)/*初始化順序堆棧S*/{S->top=0;/*定義初始棧頂下標(biāo)值*/}（2）

非空否StackNotEmpty(S)intStackNotEmpty(SeqStackS)/*判斷順序堆棧S非空否，非空返回1，不然返回0*/{

if(S.top<=0)return0;elsereturn1;}2。順序堆棧操作實(shí)現(xiàn)（1）第78頁第78頁intStackPush(SeqStack*S,DataTypex)/*把數(shù)據(jù)元素值x壓入順序堆棧S，入棧成功返回1，不然返回0*/{if(S->top>=MaxStackSize){printf(“堆棧已滿無法插入?。躰”);return0;}else{S->stack[S->top]=x;S->top++;return1;}]

(3)入棧StackPush(SeqStack*Sz,DataTypex)操作實(shí)現(xiàn)（2）第79頁第79頁intStackPop(SeqStack*S,DataType*d)/*彈出順序堆棧S棧頂數(shù)據(jù)元素值到參數(shù)d，出棧成功返回1，不然返回0*/{if(S->top<=0){printf(“堆棧已空無數(shù)據(jù)元素出棧?。躰”);return0;}else{S->top--;*d=S->stack[S->top];return1;}}操作實(shí)現(xiàn)（3）（4）

出棧StackPop(SeqStack*S,DataType*d)第80頁第80頁StackTop(SeqStackS,DataType*d)intStackTop(SeqStackS,DataType*d)/*取順序堆棧S當(dāng)前棧頂數(shù)據(jù)元素值到參數(shù)d，成功返回1，不然返回0*/{if(S.top<=0){printf(“堆棧已空！＼n”);return0;}else{*d=S.stack[S.top-1];return1;}（5）取頂數(shù)據(jù)元素第81頁第81頁設(shè)上述順序堆棧結(jié)構(gòu)體定義和操作實(shí)現(xiàn)函數(shù)存儲在文件‘SS＂中，設(shè)計(jì)下列測試主函數(shù)進(jìn)行測試：﹟include<stdio.h>/*該文獻(xiàn)包括printf()函數(shù)*/﹟include<stdlib.h>/*該文獻(xiàn)包括exit()函數(shù)*/﹟defineMaxStackSize100/*定義MaxStackSize為100*/typedefintDataType;/*定義DataType為int數(shù)據(jù)類型*/﹟include“SeqStack.h”

voidmain(void){SeqStackmyStack;inti,x;3。順序堆棧測試（1）第82頁第82頁StackInitiate(&myStack);/*初始化*/for(i=0;i<10;i++){if(StackPush(&myStack,i+1)==0)/*入棧10個數(shù)據(jù)元素*/{

printf(“錯誤!＼n”);return;}｝

if(StackTop(myStack,&x)==0)/*取棧頂數(shù)據(jù)元素*/{

printf(“錯誤!＼n”);return;}3。順序堆棧測試（2）第83頁第83頁

elseprintf(“當(dāng)前棧頂數(shù)據(jù)元素為：%d＼n”,x);printf(“依次出棧數(shù)據(jù)元素序列下列：＼n”);while(StackNotEmpty(myStack)){StackPop(&myStack,&x);/*出棧*/printf(“%d”,x);/*顯示數(shù)據(jù)元素*/}}程序運(yùn)營輸出結(jié)果下列：當(dāng)前棧頂數(shù)據(jù)元素為：10依次出棧數(shù)據(jù)元素序列下列：109876543213。順序堆棧測試（3）第84頁第84頁1.鏈?zhǔn)蕉褩４鎯Y(jié)構(gòu)

與線性鏈表類似，鏈?zhǔn)綏Ｒ残枰粋€描述結(jié)點(diǎn)，它作為整個棧代表。鏈?zhǔn)綏Ｖ写尜A棧元素結(jié)點(diǎn)結(jié)構(gòu)與線性鏈表相同。3。1。4堆棧鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（1）第85頁第85頁堆棧有兩端，插入元素和輸出元素一端為棧頂，另一端為棧底．鏈?zhǔn)蕉褩６荚O(shè)計(jì)成把靠近頭指針一端定義為棧頂．如上圖所表示：鏈?zhǔn)蕉褩＝Y(jié)點(diǎn)結(jié)構(gòu)體定義下列：

typedefstructsnode{DataTypedata;structsnode*next;}3.1.4堆棧鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)（2）第86頁第86頁鏈?zhǔn)蕉褩２迦牒蛣h除操作都是在鏈表表頭進(jìn)行．若把鏈?zhǔn)蕉褩ＴO(shè)計(jì)成帶頭結(jié)點(diǎn)結(jié)構(gòu)，則入棧和出棧操作改變只是頭指針?biāo)割^結(jié)點(diǎn)域值，而不是頭指針值，因此，頭指針參數(shù)可設(shè)計(jì)成結(jié)點(diǎn)指針類型，故此頭指針參數(shù)必須設(shè)計(jì)成結(jié)點(diǎn)雙重指針（即指針指針）類型．帶頭結(jié)點(diǎn)鏈?zhǔn)蕉褩２僮鲗?shí)現(xiàn)下列：（1）

初始化StackInitiate(LSNode**head)voidStackInitiate(LSNode**head)/*初始化帶頭結(jié)點(diǎn)鏈?zhǔn)蕉褩?/{

if(*head=(LSNode*)malloc(sizeof(LSNode)))==NULL)exit(1);(*head)->next=NULL;}3。鏈?zhǔn)蕉褩２僮鲗?shí)現(xiàn)第87頁第87頁（2）

非空否StackNotEmpty(LSNode*head)intStackNotEmpty(LSNode*head)/*判斷堆棧是否非空，非空返回1，不然返回0*/{

if(head->next==NULL)return0;return1;}3。鏈?zhǔn)蕉褩２僮鲗?shí)現(xiàn)（2）第88頁第88頁（3）入棧StackPush(LSNode*head,DataTypex)/*把數(shù)據(jù)元素x插入鏈?zhǔn)蕉褩ｍ攈ead作為新棧頂*/intStackPush(LSNode*head,DataTypex){LSNode*p;if((p=(LSNode*)malloc(sizeof(LSNode)))==NULL){printf(“內(nèi)存空間不足無法插入！\n”);return0;}

p->data=x;p->next=head->next;/*新結(jié)點(diǎn)鏈入棧頂*/head->next=p;/*新結(jié)點(diǎn)成為新棧頂*/return1;}3。鏈?zhǔn)蕉褩２僮鲗?shí)現(xiàn)（3）第89頁第89頁(4)出棧StackPop(LSNode*head,DataType*d)intStackPop(LSNode*head,DataType*d)/*出棧并把棧頂元素由參數(shù)d帶回*/{

LSNode*p=head->next;if(p==NULL){printf(“堆棧已空犯錯!”);

return0;}head->next=p->next;/*刪除原棧頂結(jié)點(diǎn)*/*d=p->data;/*原棧頂結(jié)點(diǎn)元素賦予d*/free(p);/*釋放原棧頂結(jié)點(diǎn)內(nèi)存空間*/

return1;}3。鏈?zhǔn)蕉褩２僮鲗?shí)現(xiàn)（4）第90頁第90頁(5取棧頂數(shù)據(jù)元素StackTop(LSNode*head,DataType*d)intStackTop(LSNode*head,DataType*d)/*取棧頂元素并把棧頂元素由參數(shù)d帶回*/{

LSNode*p=head->next;if(p==NULL){printf(“堆棧已空犯錯!”);

return0;}d=p->data;return1;}3。鏈?zhǔn)蕉褩２僮鲗?shí)現(xiàn)（5）第91頁第91頁(5)

撤消動態(tài)申請空間Destroy(LSNode*head)voidDestroy(LSNode*head){LSNode*p,*p1;p=head;while(p!=NULL){p1=p;p=p->next;free(p1);}}與單鏈表操作集合相同，鏈?zhǔn)蕉褩Ｒ惨鲩L一個撤消動態(tài)申請空間操作．

3。鏈?zhǔn)蕉褩２僮鲗?shí)現(xiàn)（6）第92頁第92頁3。3隊(duì)列3.3.1隊(duì)列基本概念隊(duì)列是一個特殊線性表．它允許在其一端進(jìn)行插入操作，在其另一端進(jìn)行刪除操作．隊(duì)列中允許進(jìn)行插入操作一端稱為隊(duì)尾，允許進(jìn)行刪除操作一端稱為隊(duì)頭．插入稱為入隊(duì)列，刪除稱為出隊(duì)列．當(dāng)隊(duì)列中沒有數(shù)據(jù)元素時稱為空隊(duì)列．因隊(duì)尾插入，隊(duì)頭刪除，它也稱作先進(jìn)先出表，即FIFO（FirstInFirstOut）結(jié)構(gòu)．插入與刪除分別稱為入隊(duì)與出隊(duì)。第93頁第93頁數(shù)據(jù)集合：隊(duì)列數(shù)據(jù)集合能夠表示為a0,a1,…,an-1，每個數(shù)據(jù)元素?cái)?shù)據(jù)類型為DataType．操作集合：（1）

初始化QueueInitiate(Q)：初始化隊(duì)列Q.（2）

非空否QueueNotEmpty(Q)：隊(duì)列Q非空否．若隊(duì)列非空，函數(shù)返回1，不然，函數(shù)返回0．

（3）

入隊(duì)列QueueAppend(Q,x):在隊(duì)列Q隊(duì)尾插入數(shù)據(jù)元素x．如入隊(duì)列成功，返回1；不然，返回0．（4）

出隊(duì)列QueueDelete(Q,d)：把隊(duì)列 Q隊(duì)頭數(shù)據(jù)元素刪除并由參數(shù)d帶回．如出隊(duì)列成功，返回1；失敗，則返回0．（5）

取隊(duì)頭數(shù)據(jù)元素QueueGet(Q,d)：取隊(duì)頭數(shù)據(jù)元素并由參數(shù)d帶回．如取到數(shù)據(jù)元素返回1；不然，返回0．.

3。3。2隊(duì)列抽象數(shù)據(jù)類型第94頁第94頁1.

順序隊(duì)列存儲結(jié)構(gòu)見ｐ73圖3-7隊(duì)列順序存儲結(jié)構(gòu)稱為順序隊(duì)列，順序隊(duì)列事實(shí)上是運(yùn)算受限順序表，和順序表同樣，順序隊(duì)列也是必須用一個向量空間來存儲當(dāng)前隊(duì)列中元素。由于隊(duì)列隊(duì)頭和隊(duì)尾位置是改變，因而要設(shè)兩個指針以分別批示隊(duì)頭和隊(duì)尾元素在隊(duì)列中位置，它們初始值地隊(duì)列初始化時均應(yīng)置為０。入隊(duì)時將新元素插入所指位置，然后尾指針將加１。出隊(duì)時，刪去所指元素，然后頭指針將加１并返回被刪元素。由此可見，當(dāng)頭尾指針相等時隊(duì)列為空。在非空隊(duì)列里，頭指針始終指向隊(duì)頭元素，而尾指針始終指向隊(duì)尾元素下一位置。順序隊(duì)列動態(tài)示意圖見ｐ73圖3-7

3。3。3順序隊(duì)列第95頁第95頁由于在入隊(duì)和出隊(duì)操作中，頭尾指針只增長不減小，致使被刪除元素空間永遠(yuǎn)無法重新利用。因此，盡管隊(duì)列中實(shí)際元素個數(shù)遠(yuǎn)遠(yuǎn)小于向量空間規(guī)模，但也也許由于尾指針?biāo)瘸鱿蛄靠臻g上界而不能做入隊(duì)操作。該現(xiàn)象稱為假上溢。見教材上例子．2.順序隊(duì)列“假溢出”問題第96頁第96頁.

1。順序循環(huán)隊(duì)列基本原理為充足利用向量空間?？朔鲜黾偕弦绗F(xiàn)象辦法是將向量空間想象為一個首尾相接圓環(huán)，并稱這種向量為循環(huán)向量，存儲在其中隊(duì)列稱為循環(huán)隊(duì)列（CircularQueue)。在循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時，頭尾指針仍要加1，朝前移動。只但是當(dāng)頭尾指針指向向量上界（QueueSize-1）時，其加1操作結(jié)果是指向向量下界0。由于循環(huán)隊(duì)列元素空間能夠被利用，除非向量空間真被隊(duì)列元素所有占用，不然不會上溢。因此，除一些簡樸應(yīng)用外，真正實(shí)用順序隊(duì)列是循環(huán)隊(duì)列。.

.。2。順序循環(huán)隊(duì)列隊(duì)空和隊(duì)滿判斷問題由于入隊(duì)時尾指針向前追趕頭指針，出隊(duì)時頭指針向前追趕尾指針，故隊(duì)空和隊(duì)滿時頭尾指針均相等。因此，我們無法通過front=rear來判斷隊(duì)列“空”還是“滿”。

3。3。4順序循環(huán)隊(duì)列表示和實(shí)現(xiàn)1-2。第97頁第97頁（1）少用一個存儲單元：

商定入隊(duì)前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認(rèn)為隊(duì)滿（注意：rear所指單元始終為空）隊(duì)列滿判斷條件為：(rear+1)%MaxQueueSize==front隊(duì)列空判斷條件仍然為：

rear==front處理問題辦法有三種（1）第98頁第98頁（2）設(shè)置一個標(biāo)志位設(shè)標(biāo)志位為tag，初始時置tag=0；每當(dāng)入隊(duì)列成功就置tag=1；每當(dāng)出隊(duì)列操作成功就置tag=0．則隊(duì)列空判斷條件為：rear==front&&tag=0隊(duì)列滿判斷條件為:rear==front&&tag=1（3）

設(shè)置一個計(jì)數(shù)器（此辦法最為簡樸）設(shè)計(jì)數(shù)器為count，初始時置count=0；每當(dāng)入隊(duì)列操作成功就使count加1；每當(dāng)出隊(duì)列操作成功就使count減1．這樣，隊(duì)列空判斷條件為：

count==0隊(duì)列滿判斷條件為：

count>0&&rear==front

處理問題辦法有三種（2-3）第99頁第99頁循環(huán)隊(duì)列類型定義typedefStruct{DataTypequeue[MaxQqueueSize]intrear;/*隊(duì)尾指針*/intfront;/*隊(duì)頭指針*/intcount;/*計(jì)數(shù)器*/}SeqCQueue;用上述第三種辦法（計(jì)數(shù)器法）實(shí)現(xiàn)循環(huán)隊(duì)列上六種基本操作

（1）初始化QueueInitiate(SeqCQueue*Q)voidQueueInitiate(SeqCQueue*Q)/*初始化順序循環(huán)隊(duì)列Q*/{Q->rear=0;/*定義初始隊(duì)尾指針下標(biāo)值*/Q->front=0;/*定義初始隊(duì)頭指針下標(biāo)值*/Q->count=0;}/*定義初始計(jì)數(shù)器值*/

3。順序循環(huán)隊(duì)列實(shí)現(xiàn)第100頁第100頁（2）

非空否QueueNotEmpty(SeqCQueueQ)intQueueNotEmpty(SeqCQueueQ)/*判斷順序循環(huán)隊(duì)列Q非空否，非空時返回1，不然返回0*/

{if(Q.count!=0)return1;elsereturn0;}

3。順序循環(huán)隊(duì)列實(shí)現(xiàn)（2）第101頁第101頁（3）

入隊(duì)列QueueAppend(SeqCQueue*Q,DataTypex)intQueueAppend(SeqCQueue*Q,DataTypex)/*把數(shù)據(jù)元素值x插入順序循環(huán)隊(duì)列Q隊(duì)尾，成功返回1，失敗返回0*/{if(Q->count>0&&Q->rear==Q->front)/*判斷隊(duì)列滿否*/{printf(“隊(duì)列已滿無法插入!＼n”)return0;}else{Q->queue[Q->rear]=x;Q->rear=(Q->rear+1)%MaxQueueSize;Q->count++;return1;}3。順序循環(huán)隊(duì)列實(shí)現(xiàn)（3）第102頁第102頁（4）

出隊(duì)列QueueDelete(SeqCQueue*Q,DataType*d)intQueueDelete(SeqCQueue*Q,DataType*d)