數(shù)據(jù)結(jié)構(gòu)課程教案

1、數(shù)據(jù)結(jié)構(gòu)課程教案08-09學(xué)期（下）計算機科學(xué)教育系 劉健第一章 概論教學(xué)目的： 1、理解數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語； 2、理解抽象數(shù)據(jù)類型的表示與實現(xiàn)； 3、掌握算法和算法分析。教學(xué)內(nèi)容：什么是數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型、算法的定義、算法的特性、算法的時空代價1.1基本概念和術(shù)語數(shù)據(jù)(data)：是對客觀事物的符號表示，在計算機科學(xué)中是指所有能輸入計算機中并被計算機程序處理的符號的總稱。它是計算機程序加工的“原料”。例如，一個利用數(shù)值分析方法解代數(shù)方程的程序，其處理對象是整數(shù)和實數(shù)；一個編譯程序或文字處理程序的對象是字符串。因此，對計算機而言

2、，數(shù)據(jù)的含義極為廣泛，如圖象， 聲音等都可以通過編碼而歸數(shù)據(jù)的范疇數(shù)據(jù)元素(data element)：是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。有時，一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是不可分割的最小單位。 數(shù)據(jù)對象(data object)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)(data structure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素都不是孤立存在 的，而是在它們之間存在著某種關(guān)系，這種數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)(structure)。包括三方面內(nèi)容：(1)數(shù)據(jù)元素之間的邏輯關(guān)系，也稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；(2

3、)數(shù)據(jù)元素及其關(guān)系在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu)；(3)數(shù)據(jù)的運算，即對數(shù)據(jù)施加的操作。數(shù)據(jù)的邏輯結(jié)構(gòu)：是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機，包括兩大類：(1)線性結(jié)構(gòu)：特征是有且僅有一個開始結(jié)點和一個終端結(jié)點，其余的結(jié)點有且僅有一個直接前趨和一個直接后繼。如：線性表、棧、隊列。(2)非線性結(jié)構(gòu)：特征是一個結(jié)點可能有多個直接前趨和直接后繼。如：廣義表、樹、圖。數(shù)據(jù)的存儲結(jié)構(gòu)：是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)。有四種存儲方式：(1)順序存儲方法：是用一組連續(xù)的存儲單元把邏輯上相鄰的結(jié)點存儲在物理位置上相鄰的存儲單元里；(2)鏈?zhǔn)酱鎯Ψ椒ǎ菏怯靡唤M不一定連續(xù)的存儲單元

4、存儲邏輯上相鄰的結(jié)點，結(jié)點間的邏輯關(guān)系是由附加的指針域表示的。(3)索引存儲方法：是存儲結(jié)點信息的同時還建立附加的索引表。(4)散列存儲方法：是根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址。1.2抽象數(shù)據(jù)類型的表示與實現(xiàn)數(shù)據(jù)類型:是一個值的集合和定義在這個值集上的所有的操作。例如，整數(shù)類型。數(shù)據(jù)類型可分為：非結(jié)構(gòu)的原子類型和結(jié)構(gòu)類型。原子類型的值是不可分解的，結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成的。 抽象數(shù)據(jù)類型:是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念，它僅取決于數(shù)據(jù)類型的邏輯性，而與其在計算機內(nèi)部如何表示和實現(xiàn)是無關(guān)的。 抽象數(shù)據(jù)類型的定義由一個

5、值域和定義在該值域上的一組操作組成。抽象數(shù)據(jù)類型按其值的不同特性，分為三種類型：               原子類型:變量的值是不可分解的。               固定聚合類型:變量的值由確定數(shù)目的成分按某種結(jié)構(gòu)組成。        

6、;       可變聚合類型:其值的成分?jǐn)?shù)目不確定。抽象數(shù)據(jù)類型的形式定義：我們用一個三元組來表示一個抽象數(shù)據(jù)類型。（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)系的定義基本操作：基本操作的定義ADT 抽象數(shù)據(jù)類型名。抽象數(shù)據(jù)類型的表示與實現(xiàn)：抽象數(shù)據(jù)類型可通過固有數(shù)據(jù)類型來表示和實現(xiàn)，即利用處理器中已存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實現(xiàn)的操作來組合新的操作。精選了C 的一個子集，擴充修改，增強了語言的描述功能。l  &

7、#160;    預(yù)定義常量和類型l       數(shù)據(jù)結(jié)構(gòu)的表示：存儲結(jié)構(gòu)用類型（typedef）定義來描述。數(shù)據(jù)元素類型約定為ElemType.l       基本操作的算法用函數(shù)描述：函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表）/*算法說明*/語句序列 1.3 算法的描述和算法的分析1、算法（Algorithm）是對特定問題求解步驟的一種描述，它是指令的有限序列。算法具有五個重要特性：有窮性、確定性、可行性、輸入、輸出2、算法設(shè)計的要求正確性、可讀性、健壯

8、性和效率與低存儲量要求3、算法效率的度量算法時間是由控制結(jié)構(gòu)和原操作的決定的。做法：選取一種是基本操作的原操作，以該基本操作重復(fù)的次數(shù)作為算法的時間量度。時間復(fù)雜度：算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f（n），T（n）=O（f（n）它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f（n）的增長綠相同。語句的頻度：是該語句重復(fù)執(zhí)行的次數(shù)。例：求兩個n階方陣的乘積C=A×B，其算法如下：#define n 100 void MatrixMultiply(int Ann,int Bnn,int Cnn)int i,j,k for (i=1;i<=n;+i) n+1fo

9、r (j=1;j<=n;+j) n*(n+1)Cij=0; n2for (k=1;k<=n,k+) n2(n+1)Cij=Cij+aik*bkj; n3T(n)=2n3+3n2+2n+1limT(n)/ n3=2 T(n)=O(n3)例： （a）+x;s=0;（b）for (i=1;i<=n;+i) +x;s+=x;（c）for (j=1;j<=n;+j)for (k=1;k<=n;k+)+x;s+=x;含基本操作“x增1”的語句的頻度分別為1,n和n2時間復(fù)雜度是O(1),O(n)和O(n2)。時間復(fù)雜度有時與輸入有關(guān)。4、算法的存儲空間需求空間復(fù)雜度：S（n）

10、=O（f（n）本章小結(jié)本單簡要地介紹了數(shù)據(jù)，數(shù)據(jù)結(jié)構(gòu)等基本概念；闡述了數(shù)據(jù)結(jié)構(gòu)所包含的三個方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算；討論了線性結(jié)構(gòu)和非線性結(jié)構(gòu)的邏輯特征，以及數(shù)據(jù)存儲的四種基本方法；讀者學(xué)習(xí)這些內(nèi)容和例子后，希望能對數(shù)據(jù)結(jié)構(gòu)的基本概念，具有初步的認(rèn)識和理解。本書使用C語言來描述算法，為了便于讀者了解C語言描寫的算法，本章簡要介紹了C語言的程序結(jié)構(gòu)和主要語句的語法。算法和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)，不可分割，本章引進了算法，算法的時間復(fù)雜度等概念，以及分析時間復(fù)雜度的簡易方法。第二章 線性表教學(xué)目的： 1、理解線性表的基本定義和基本操作；2、了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元

11、素之間存在著線性關(guān)系； 3、掌握線性表的兩種存儲結(jié)構(gòu)及其基本操作的實現(xiàn)； 4、比較兩種存儲結(jié)構(gòu)的異同。教學(xué)內(nèi)容： 線性表的定義、基本運算、線性表的順序存儲、線性表的鏈?zhǔn)酱鎯Α?.1線性表的概念及運算線性結(jié)構(gòu)的特點：在數(shù)據(jù)元素的非空有限集中 存在唯一的一個被稱做“第一個”的數(shù)據(jù)元素； 存在唯一的一個被稱做“最后一個”的數(shù)據(jù)元素； 除第一個之外，每個元素都只有一個直接前驅(qū)； 除最后一個之外，每個元素都只有一個直接后繼。1、線性表：是數(shù)據(jù)元素的有限序列。表中的數(shù)據(jù)元素是屬于同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系。所以可將線性表記為L=a1,ai-1,ai,ai+1,an）2、線性表的基本運算：

12、表的初始化、求表長、取表中的結(jié)點、查找結(jié)點、插入結(jié)點和刪除結(jié)點。例1：擴大線性表LA，將存在于線性表LB中而不在LA中的數(shù)據(jù)元素加入到線性表LA中。算法思想：逐一取出LB中的元素，判斷是否在LA中，若不在，則插之。算法：void unin(List &La List Lb)La_len=(ListLength(La); Lb_len=(ListLength(Lb);for (i=1;i<=Lb_len;i+)GetElem(Lb,i,e);if (!LocateElem(La,e,equal) ListInsert(La,+La_len,e);/*La 中不存在和e 相同的元素，

13、則插入之*/ 算法的時間復(fù)雜度：O（ListLength(LA) ×ListLength(LB)）例2： 線性表LA和LB是非遞減的，將兩表合并成新的線性表LC，且LC也是非遞減的。算法思想：將LA、LB兩表中的元素逐一按序加入到一個新表LC中。void MergeList(List La, List Lb, List &Lc)InitList(Lc);i=j=k=1; k=0;La_len=(ListLength(La); Lb_len=(ListLength(Lb);while (i<=La_len)&&(j<=Lb_len) GetElem(

14、La,i,ai); GetElem(Lb,j,bj);if(ai<=bj)ListInsert(Lc,+k,ai);+i;else ListInsert(Lc,+k,bj);+j;while (i<=La_len)GetElem(La,i+,ai); ListInsert(Lc,+k,ai);while (j<=Lb_len) GetElem(Lb,j+,bj); ListInsert(Lc,+k,bj);算法的時間復(fù)雜度：O（ListLength(LA) +ListLength(LB)）2.2、線性表的順序表示和實現(xiàn)1、線性表的順序表示：指的是用一組地址連續(xù)的存儲單元依次存

15、儲線性表的數(shù)據(jù)元素。用物理位置來表示邏輯結(jié)構(gòu)。LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-1)*l2、順序表的特點：隨機存取的存儲結(jié)構(gòu)。只要確定了存儲線性表的起始位置，線性表中的任一數(shù)據(jù)元素可隨機存取。3、線性表的動態(tài)分配順序存儲結(jié)構(gòu)（用一維數(shù)組）#define LIST_INIT_SIZE 100#define LISTINCREAMENT 10type structElemType *elem;int length;int listsize;SqList4、順序線性表的操作順序表容易實現(xiàn)訪問操作，可隨機存取元素。但插入和刪除操作主要是移動元素。初始化操作算法

16、思想：構(gòu)造一個空表。設(shè)置表的起始位置、表長及可用空間。算法：Status InitList_Sq(SqList &L)L.elem=(ElemType )malloc(LIST_INIT_SIZE*sizeof(ElemType);If (!L.elem)exit(OVERFLOW);L.length=0;L.listsize= LIST_INIT_SIZE;Return OK;插入操作算法思想：在第i個位置上插入一個新元素，將第n 至（i+1）個元素逐一向后移動一個位置。算法：Status ListInsert_Sq(SqList &L, int i, ElemType e

17、)if (i<1|i>L.length+1) return ERROR;if (L.length>=L.listsize)newbase=(ElemType )realloc(L.elem,(L.listsize+LISTINCREMENT)sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+= LISTINCREMENT;q=&(L.elemi-1);for (p=&(L.elemL.length-1);p>=q;-p)*(P+1)=*p;*q=e;+L.lengt

18、h;return OK;刪除操作：算法思想：刪除第i個元素，將第（i+1）至第n個元素逐一向前移動一個位置。順序表的合并5、順序表操作的時間復(fù)雜度插入和刪除操作移動元素的操作為基本操作。假定在線性表的任意位置上插入和刪除都是等概率的。插入概率為1/（n+1），刪除概率為1/n。時間復(fù)雜度：O（n）求表長、取元素：時間復(fù)雜度：O（1）順序表的合并：基本操作為兩個元素的比較時間復(fù)雜度：O（ListLength(LA) ×ListLength(LB)）O（ListLength(LA) +ListLength(LB)）2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)一、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)1、線性表的鏈?zhǔn)酱鎯?/p>

19、結(jié)構(gòu)的特點：是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素。數(shù)據(jù)元素的映象用一個結(jié)點來表示。結(jié)點的一個域表示元素本身，另一個域是能指示其后繼的指針，用來表示線性表數(shù)據(jù)元素的邏輯關(guān)系。結(jié)點（Node）、數(shù)據(jù)域、指針域、指針、鏈、頭指針2、鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點：插入、刪除操作是不再需要移動大量的元素，但失去了順序表的可隨機存取特點。鏈表可分為單鏈表、循環(huán)鏈表和雙向鏈表。二、線性鏈表：1、單鏈表：鏈表中的每一個結(jié)點中只包含一個指針域的稱為單鏈表或線性鏈表。2、單鏈表的存儲結(jié)構(gòu)單鏈表可由頭指針唯一確定，在C語言中，用結(jié)構(gòu)指針來描述。typedef struc LNodeElemType data; stru

20、ct LNode *next LNode, *LinkList3、單鏈表的操作：訪問：算法思想：單鏈表是非隨機存取結(jié)構(gòu)。每個元素的位置信息都包含在前驅(qū)結(jié)點的信息中，所以取得第i個元素必須從頭指針出發(fā)尋找。設(shè)置一個指針變量指向第一個結(jié)點，然后，讓該指針變量逐一向后指向，直到第i個元素。Status GetElem_L(LinkList L, int i, ElemType)/*L為帶頭結(jié)點的單鏈表的頭指針*/*當(dāng)?shù)趇個元素存在時，其值賦給e并返回OK，否則返回ERROR*/p=Lnext; j=1;while(p && j<i)p=pnext; +j;e=pdata;ret

21、urn OK;插入操作：要在數(shù)據(jù)元素a和b 之間插入元素x。算法思想：決定a和b之間的相鄰關(guān)系是由a 的指針決定的。若要實現(xiàn)插入，生成x結(jié)點，然后讓a 的指針指向x 且x 的指針指向b。實現(xiàn)三個元a、x和b的邏輯關(guān)系。設(shè)p為指向結(jié)點a 的指針，s為指向結(jié)點x的指針，則修改s、a的指針：snext=pnext；pnext=s；算法：Status ListInsert_L(ListLInk &L, int i, ElemType e)/*在帶頭結(jié)點的單鏈表L中第i個位置前插入元素*/p=L; j=0;while(p && j<i-1)p=pnext; +j;if (!

22、p | j<i-1) return ERROR;s=(LinkList)malloc(sizeof(LNode);sdata=e; snext=p-next;pnext=s;return OK;刪除操作：在單鏈表數(shù)據(jù)元素a、b、c三個相鄰的元素中刪除b，算法思想：就是要讓a 的指針直接指向c，使b從鏈表中脫離。即，pnext=pnextnext單鏈表的合并：例：將兩個有序鏈表合并為一個有序鏈表。設(shè)立三個指針pa、pb和pc 分別用來指向兩個有序鏈表和合并表的當(dāng)前元素。比較兩個表的當(dāng)前元素的大小，將小的元素鏈接到合并表中，即，讓合并表的當(dāng)前指針指向該元素，然后，修改指針。在歸并兩個鏈表為一

23、個鏈表時，不需要另建新表的結(jié)點空間，而只需將原來兩個鏈表中結(jié)點之間的關(guān)系解除，重新建立關(guān)系。4、 靜態(tài)單鏈表有些高級語言沒有指針，我們可以用數(shù)組來表示單鏈表，在數(shù)組中以整型游標(biāo)來代替指針。這種用數(shù)組描述的鏈表稱為靜態(tài)鏈表。存儲結(jié)構(gòu)：#define MAXSIZE 1000typedef structElemType data;Int cur;component, SLinklistMAXSIZE;Si.cur 指示第i+1個結(jié)點的位置。靜態(tài)鏈表的操作和動態(tài)鏈表相似。以整型游標(biāo)代替動態(tài)指針。int LocateElem_SL(SLinkList L, ElemType)/*在靜態(tài)鏈表L中查找值為

24、e的元素*/*若找到，則返回它在L中的位序，否則返回0*/i=S0.cur;while(i &&Si.data!=e) i=Si.cur;return i;三、循環(huán)鏈表1、循環(huán)鏈表：是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)，其特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。循環(huán)鏈表可分為單鏈和多鏈的。2、循環(huán)鏈表的操作：和線性鏈表基本一致，差別僅在于循環(huán)條件判定是否為空改為是否為頭指針。四、雙向鏈表1、雙向鏈表：在雙向鏈表的結(jié)點中有兩個指針域，分別指向前驅(qū)和后繼。 雙向鏈表也可以有循環(huán)鏈表。2、雙向鏈表的存儲結(jié)構(gòu)：typedef struct DuLNode ElemType

25、data;struct DuLNode *prior;struct DuLNode *next; DuLNode, *DuLinklist;3、雙向鏈表的操作：雙指針使得鏈表的雙向查找更為方便、快捷。NextElem和PriorElem的執(zhí)行時間為O（1）。 僅需涉及一個方向的指針的操作和線性鏈表的操作相同。插入和刪除需同時修改兩個方向的指針。2.4順序表和鏈?zhǔn)奖淼谋容^1、基于空間的考慮2、基于時間的考慮3、基于語言的考慮本章小結(jié)線性表是一種最基本，最常用的數(shù)據(jù)結(jié)構(gòu)。本章介紹了線性表的定義，運算和各種存儲結(jié)構(gòu)的描述方法。重點討論了線性表的兩種存儲結(jié)構(gòu)-順序表和鏈表，以及在這兩種存儲結(jié)構(gòu)上實現(xiàn)的

26、基本運算。順序表是用數(shù)組實現(xiàn)的，鏈表是用指針或游標(biāo)實現(xiàn)的。用指針來實現(xiàn)的鏈表，因為它的結(jié)點是動態(tài)分配的，故稱之為動態(tài)鏈表；用游標(biāo)模擬指針實現(xiàn)的鏈表，由于其結(jié)點空間是靜態(tài)分配的，所以稱之為靜態(tài)鏈表。這兩種鏈表又可按鏈接形式的不同，區(qū)分為單鏈表，雙鏈表和循環(huán)鏈表。在實際應(yīng)用中，對線性表采用哪種存儲結(jié)構(gòu)，要視實際問題的要求而定，主要考慮求解算法的時間復(fù)雜度和空間復(fù)雜度。因此，建議讀者熟練掌握在順序表和鏈表上實現(xiàn)的各種基本運算及其時間，空間特性。第三章 棧、隊列教學(xué)目的： 1、理解棧的定義、特性，掌握棧的存儲結(jié)構(gòu)以及基本操作的實現(xiàn)； 2、理解隊列的定義、特性，掌握隊列的存儲結(jié)構(gòu)以及基本操作的實現(xiàn)；教學(xué)

27、內(nèi)容： 1、棧的定義、特點、兩種存儲結(jié)構(gòu)、棧的應(yīng)用 2、隊列的定義、特點、兩種存儲結(jié)構(gòu)、隊列的應(yīng)用3.1棧一、棧的定義：棧（stack):是限定在表尾進行插入或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義，稱為棧頂（TOP），相應(yīng)的，表頭端稱為棧底（bottom).不含元素的空表稱為空棧。 棧的特點：先進后出。 棧的基本運算： 1、建立一個空棧 2、判?？?3、進棧 4、出棧 5、取棧頂元素二、棧的順序存儲結(jié)構(gòu)： 限定在表尾進行插入和刪除操作的順序表類型定義： typedef struct SElemType *base; SElemType *top; int stacksize;

28、SqStack; SqStack s說明：§ base稱為棧底指針，始終指向棧底；當(dāng)base = NULL時，表明棧結(jié)構(gòu)不存在。§ top為棧頂指針 a. top的初始值指向棧底，即top=base b. 空棧：當(dāng)top=base時為棧空的標(biāo)記 c. 當(dāng)棧非空時，top的位置：指向當(dāng)前棧 頂元素的下一個位置§ stacksize 當(dāng)前?？墒褂玫淖畲笕萘繋c說明：l       ?？諚l件：s. top =s. base 此時不能出棧l      

29、棧滿條件：s.top-s.base>=s.stacksizel       進棧操作：*s.top+=e; 或*s.top=e; s.top+;l       退棧操作：e=*-s.top； 或s.top-； e=*s.top；l       當(dāng)棧滿時再做進棧運算必定產(chǎn)生空間溢出，簡稱“上溢”;l       當(dāng)棧空時再做退棧運算也將產(chǎn)生溢出，簡稱“下

30、溢”?；静僮鞯膶崿F(xiàn)1、棧的初始化操作 Status InitStack (SqStack &S) S.base = (SElemType )malloc(STACK_INIT_SIZE * sizeof(ElemType);if (!S.base) return (OVERFLOW);S.top=S.base;S.stacksize = STACK_INIT_SIZE;return OK;2、取棧頂元素 Status GetTop(SqStack S, SElemType &e)if (S.top = S.base) return ERROR;e = *(S.top-1);r

31、eturn OK;3、進棧操作 Status Push(SqStack &S, SElemType e) if (S.top-S.base>=S.stacksize) S.base=(SElemType*)realloc(S.base, (S.stacksize+STACKINCREMENT) *sizeof(ElemType); if (!S.base) return (OVERFLOW); S.top = S.base +S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; /* *S.top = e; S.top

32、= S.top+1; return OK;4、退棧操作 Status Pop(SqStack &S, SElemType &e)if (S.top = S.base) return ERROR; e=*-S.top; /* S.top= S.top;-1; e=*S.top; return OK;三、棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)：§ 不帶頭結(jié)點的單鏈表，其插入和刪除操作僅限制在表頭位置上進行。鏈表的頭指針即棧頂指針。 § 類型定義： typedef struct SNode SElemType data; struct SNode *next; SNode, *Link

33、Stack;LinkStack s;l       鏈棧示意圖 l       棧空條件： s=NULLl       棧滿條件： 無 / 無Free Memory可申請1、進棧操作：Status Push_L (LinkStack &s，SElemType e) p=(LinkStack)malloc(sizeof(SNode); if (!p) exit(Overflow); p->data = e

34、; p->next = s; s=p; return OK; 2、退棧操作Status Pop_L (LinkStack &s, SElemType &e) if (!s) return ERROR; e=s->data; p=s; s=s->next; free(p); return OK; 四、棧的應(yīng)用：1、數(shù)制轉(zhuǎn)換將十進制數(shù)N轉(zhuǎn)換成d進制N=(N div d)*d + N mod d計算過程是從低位到高位順序產(chǎn)生d進制數(shù)的各個數(shù)位。算法思想：將計算過程的d進制數(shù)逐位進棧，然后逐個出棧。void conversion(seqstack *s)SETNULL

35、(s); scanf(“%d%d”,N,d); while(N)PUSH(s,N%d); N=N/d; while(!EMPTY(s)e=pop(s); printf(“%d”,e);2、文字編輯器設(shè)計一個簡單的文字編輯器，使其具有刪除打錯字符的功能void EDIT(seqstack *s)char c; SETNULL(s); c=getchar(); while(c!=*) if(c=#) POP(s);else if (c=) SETNULL(s); else PUSH(s,c);c=getchar( ); 3 表達(dá)式求值 概念：前綴表達(dá)式，中綴表達(dá)式，后綴表達(dá)式 +a b, a+b,

36、 a b+ 算符：運算符和界符。算符的優(yōu)先關(guān)系。<、=、> 算法的思想：設(shè)置兩個工作棧：運算符棧OPTR和操作數(shù)棧OPND。操作數(shù)棧也放表達(dá)式的運算結(jié)果。首先置操作數(shù)棧為空棧，置運算符棧的棧底為表達(dá)式的起始符#。依次讀入表達(dá)式中的每個字符，若是操作數(shù)則進OPND棧；若是運算符，則和OPTR中的棧頂元素做比較再操作，直至表達(dá)式求置完畢。 這里重點介紹中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式，并對后綴表達(dá)式求值。 （1） 中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式 設(shè)中綴表達(dá)式和后綴表達(dá)式分別在向量IFX和PFX申，用棧S實現(xiàn)中綴式轉(zhuǎn)為后綴式，對IFX中表達(dá)式從左到右掃描，設(shè)TOKEN是掃描讀到的符號，轉(zhuǎn)換算法可描述如

37、下。 1)棧初始化。 2)從左到右掃描向量IFX，重復(fù)下述兩步操作，直到表達(dá)式尾。 從IPX中取出下個TOKEN(數(shù)字、運算符、左括號、右括號)； CASE TOKEN OF '('：將TOKEN壓入棧S; 操作數(shù)：將操作數(shù)直接送入PFX; 操作符：如?？栈騎OKEN比棧頂元素優(yōu)先級高，將TOKEN進棧；否則，退棧并將退棧元素送入PFX，然后再將TOKEN與新棧頂元素比較之; ）：退棧并將退棧元素送PFX，直到碰到左括號，左括號退棧不送PFX。 3)當(dāng)遇到中綴表達(dá)式結(jié)束符號，連續(xù)退棧并送退棧元素到PFX，直至?？铡＃?） 對后綴表達(dá)式求值 用實型數(shù)棧S存放計算后綴式的中間及最終

38、結(jié)果，求值算法可描述如下。 1)棧初始化。 2)從左到右掃描向量PFX，重復(fù)下述兩步操作，直到表達(dá)式尾。 從PFX中取出下個TOKEN(操作數(shù)、運算符) CASE TOKEN OF 操作數(shù)：將操作數(shù)直接送入棧S1;操作符：出棧兩個操作數(shù)，對其進行TOKEN操作，結(jié)果壓人棧S1 3)當(dāng)遇到后綴表達(dá)式結(jié)束符號，棧頂?shù)闹稻褪墙Y(jié)果(應(yīng)是棧中唯一元素)。4、棧與遞歸的實現(xiàn)遞歸：在函數(shù)執(zhí)行中，直接或間接調(diào)用自己的函數(shù)稱為遞歸函數(shù)?！斑f歸工作?！睏ｍ敒椤肮ぷ饔涗洝保▍?shù)、局部變量以及上一層的返回地址。遞歸過程的應(yīng)用： 問題的定義是遞歸的：f(n)=n*f(n-1)數(shù)據(jù)結(jié)構(gòu)是遞歸的：鏈表問題的解法是遞歸的

39、：Hanoi 塔問題用棧實現(xiàn)遞歸函數(shù)int FACT(n)int n;if(n=1) return(1); else return(n*FACT(n-1);3.2 隊列 1、隊列的定義隊列是允許在一端進行插入而在另一端進行刪除的線性表。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。隊列也稱為先進先出表（FIFO）。2、隊列的運算（1）入隊 Enqueue(&Q, e) 在隊列Q中插入元素e。（2）出隊Dequeue(&Q, &e) 若隊列Q不空，則刪除其隊頭元素。（3）取隊頭元素Gethead(&Q, &e) 若隊列Q不空，用e返回隊頭元素。

40、（4）判隊列是否為空Queueempty(Q) 若隊列Q為空，返回true，否則，返回false。3、隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)鏈隊列：用鏈表示的隊列typedef struct QNodeQelemType data ;struct QNode *next ; QNode, *QueuePtr;typedef structQueuePtr*front ;QueuePtr*rear ;front：隊頭指針，指向頭結(jié)點rear：隊尾指針，指向尾結(jié)點。空鏈隊列：隊頭指針和隊尾指針均指向頭結(jié)點。4、隊列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的實現(xiàn)（1）入隊Enqueue(&Q, e) p=(QueuePtr) ma

41、lloc(sizeof(node); /*生成結(jié)點*/ p->data=e;p->next=NUllt; Q.rear->next=p; Q.rear=p（2）出隊 Dequeue(&Q, &e)if (Q.front=Q.rear) return Error; p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear=p) Q.rear=Q.front;free(p);5、循環(huán)隊列隊列的順序表示和實現(xiàn)l       順

42、序隊列：用一組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素l       設(shè)兩個指針：         Q.front 指向隊列頭元素；         Q.rear 指向隊列尾元素的下一個位置l       初始狀態(tài)（空隊列）：       &

43、#160; Q.front = Q.rear=0l       隊列的真滿與假滿類型定義 #define MAXSIZE 100typedef struct QElemType *base; int front; int rear; SqQueue;SqQueue Q;n       進隊時，將新元素按Q.rear 指示位置加入，再將隊尾指針增1， Q.rear = Q.rear + 1 。n       出隊時，將

44、下標(biāo)為Q.front 的元素取出，再將隊頭指針增1， Q.front = Q.front + 1 。n       隊滿時再進隊將溢出出錯；隊空時再出隊作隊空處理。l       存儲循環(huán)隊列的數(shù)組被當(dāng)作首尾相接的表處理。l       隊頭、隊尾指針加1時從maxSize -1直接進到0，可用語言的取模(余數(shù))運算實現(xiàn)。l       隊頭指針進1: Q.

45、front = (Q.front + 1)% MAXSIZE 隊尾指針進1: Q.rear = (Q.rear + 1)% MAXSIZE;l       隊列初始化：Q.front = Q.rear = 0;l       隊空條件：Q.front = Q.rear;l       隊滿條件：(Q.rear + 1) % MAXSIZE = Q.front l    

46、0;  隊列長度：(Q.rear-Q.front+MAXSIZE)%MAXSIZE說明：l       不能用動態(tài)分配的一維數(shù)組來實現(xiàn)循環(huán)隊列，初始化時必須設(shè)定一個最大隊列長度。l       循環(huán)隊列中要有一個元素空間浪費掉 -p63 約定隊列頭指針在隊列尾指針的下一位置上為“滿”的標(biāo)志l       解決 Q.front=Q.rear不能判別隊列“空”還是“滿”的其他辦法：  

47、60;      使用一個計數(shù)器記錄隊列中元素的總數(shù)（即隊列長度）         設(shè)一個標(biāo)志變量以區(qū)別隊列是空或滿基本操作：l       初始化 Status InitQueue (SqQueue &Q)Q.base=(QElemTye *)malloc(MAXQSIZE*sizeof(QElemType);if (!Q.base) exit(OVERFLOW);Q.front=Q.rear=0

48、;return OK;l       求隊列的長度 int QueueLength(SqQueue Q)return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;l       入隊Status EnQueue (SqQueue &Q, QElemType e)if (Q.rear+1) % MAXQSIZE =Q.front) return ERROR;Q.baseQ.rear=e;Q.rear = (Q.rear+1)%MAXQSIZE;

49、return OK;l       出隊 Status DeQueue(SqQueue &Q, QElemType &e)if (Q.rear=Q.front) return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;l       判隊空Status QueueEmpty(SqQueue Q)if (Q.front=Q.rear) return TRUE;return FALSE

50、;l       取隊頭元素Status GetHead(SqQueue Q,QElemType &e)if QueueEmpty(Q) return ERROR;e=Q.baseQ.front;return OK;非循環(huán)隊列：l       類型定義：與循環(huán)隊列完全一樣l       關(guān)鍵：修改隊尾/隊頭指針 Q.rear = Q.rear + 1; Q.front = Q.front+1;l &

51、#160;     在判斷時，有%MAXQSIZE為循環(huán)隊列，否則為非循環(huán)隊列l(wèi)       隊空條件： Q.front = Q.rearl       隊滿條件： Q.rear>= MAXQSIZEl       注意“假上溢”的處理l       長度： Q.rear - Q.front6、隊列的應(yīng)用本章小結(jié)

52、棧和隊列事兩種常見的數(shù)據(jù)結(jié)構(gòu)，他們都事運算受限的線性表。棧的插入和刪除均是在棧頂進行，它是后進先出的線性表；隊列的插入在隊尾，它是先進先出的線性表。在具有后進先出（或先進先出）特性的實際問題種，我們可以使用棧（或隊列）這種數(shù)據(jù)結(jié)構(gòu)來求解。和線性表類似，依照存儲表示的不同，棧有順序棧和鏈棧之分，隊列有順序隊列和鏈隊列兩種，而實際中使用的順序隊列事循環(huán)隊列。本章分別介紹了順序棧，循環(huán)隊列和鏈隊列的五種基本運算，對鏈棧則討論了它的插入和刪除運算，建議讀者掌握。值得提出的是：棧和隊列“上溢”和“下溢”概念及其判別條件應(yīng)重點領(lǐng)會，希望讀者能正確判別?；蜿犃械目臻g滿而產(chǎn)生的溢出，正確使用?？栈蜿犃锌諄砜刂?/p>

53、返回。第四章 串教學(xué)目的： 1、理解串的基本概念及基本運算； 2、掌握串的存儲結(jié)構(gòu)及串運算的實現(xiàn)。教學(xué)內(nèi)容： 什么是串、串的基本運算、存儲結(jié)構(gòu)、串運算的實現(xiàn)。一、    串類型的定義1、串：是由零個或多個字符組成的有限序列。S=a1 a2an （n>0）串值：用單引號括起來的字符序列。長度：串中字符的數(shù)目?？沾洪L度為零。子串：子序列。位置：字符在序列中的序號。相等：當(dāng)且僅當(dāng)兩個串的值相等?？崭翊河梢粋€或多個空格組成的串。2、串的操作：以串的整體為操作對象。串賦值、串比較、求串長、串連接、求子串。以上是串的最小操作子集。例：定位函數(shù)Index的實現(xiàn)：（用判

54、等、求串長、求子串操作）二、    串的表示和實現(xiàn)1、 定長順序存儲表示 表示：用一組地址連續(xù)的存儲單元存儲串值的字符序列。可用定長數(shù)組描述。 #define MAXSTRLEN 255typedef unsigned char SstringMAXSTRLEN +1; 串操作的實現(xiàn)：實現(xiàn)串操作的原操作為“字符序列的復(fù)制”。操作的時間復(fù)雜度基于復(fù)制字符序列的長度。例：串連接：復(fù)制、截尾。求子串：復(fù)制。2、 堆分配存儲表示 表示：以一組地址連續(xù)的存儲單元存放串值字符序列，但它們的存儲空間是在程序執(zhí)行的過程中動態(tài)分配而得。typedef struc

55、tchar *ch;int length;Hstring; 串操作的實現(xiàn)：也是基于字符序列的復(fù)制。例：串復(fù)制、串插入、及串的基本操作。堆分配存儲結(jié)構(gòu)有順序順序存儲結(jié)構(gòu)的特點，處理方便，且操作中對串長沒有限制。3、 串的塊鏈存儲表示 表示：用鏈表方式存儲串值，每個結(jié)點可以存放一個字符，也可以存放多個字符。#DEFINECHUNKSIZE 80typedefstruct ChunkcharchCHUNKSIZE;structChunk*next;Chunk;typedefstructChunk*head, *tail;intcurlen;Lstring;存儲密度=串值所占的存儲位/實際分配的存儲位

56、。 串操作的實現(xiàn)：串值在鏈?zhǔn)酱鎯Y(jié)構(gòu)時操作的實現(xiàn)和線性表類似，對連接操作方便。三、    串的模式匹配算法1、求子串位置的定位函數(shù) Index(S, T, pos) 模式匹配：子串的定位操作稱作串的模式匹配。T：模式串例：定長順序存儲結(jié)構(gòu)的匹配算法（不依賴于串的其他操作）思想：從主串S的第pos個字符起和模式的第一個字符比較之，若相等，則繼續(xù)比較后續(xù)字符，否則從主串的下一個字符起再重新和模式的字符比較之。算法：int index(SString S, SString T, int pos )i=pos;j=1;while(i<=S0&&j&l

57、t;=T0) if (Si=Tj+i; +j; elsei=i-j+2;j=1;算法時間復(fù)雜度：O（n+m）算法缺點：有時效率低，回溯指針次數(shù)多。2、模式匹配的一種改進算法KMP算法的改進：每當(dāng)一趟匹配過程中出現(xiàn)字符比較不等時，不需指針回溯，而是利用得到的部分匹配的結(jié)果，將模式向右滑動盡可能遠(yuǎn)的一段距離后，繼續(xù)進行比較。主串：s1s2sn模式串：p1p2pm當(dāng)匹配過程中產(chǎn)生失配(即，si¹pj)時，將模式串向右移動至模式中的第k個字符和主串中的第i個字符對齊。令：nextj=k，則next的函數(shù)定義如下： 0 當(dāng)j=1時，nextj= Maxk | 1<k<j 且p1pk-1=pj-k+1pj-1 其他情況KMP算法：int Index_KMP(SString