數(shù)據(jù)結(jié)構(gòu)C語言版

1、數(shù)據(jù)結(jié)構(gòu)(C語言版)計算機科學技術(shù)系1教材:數(shù)據(jù)結(jié)構(gòu)(C語言版)清華大學出版社嚴蔚敏 吳偉民 編著教參:數(shù)據(jù)結(jié)構(gòu)習題集 數(shù)據(jù)結(jié)構(gòu)(第二版)2教 學 計 劃第一章 緒論 4 學時第二章 線性表 10學時(含C語言鏈表)第三章 棧和隊列 10學時第四章 串 4 學時第五章 數(shù)組和廣義表 6 學時第六章 樹和二叉樹 14學時第七章 圖 12學時第八章 動態(tài)存儲管理 (自學)第九章 查找 8 學時第十章 排序 10學時復習 4學時 機動 2學時 考試 2學時 （周課時：5節(jié)/周）3第一章 緒 論內(nèi)容：什么是數(shù)據(jù)結(jié)構(gòu) 基本概念與術(shù)語 抽象數(shù)據(jù)類型的表示與實現(xiàn) 算法與算法分析重點：數(shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語

2、 算法的與算法評價難點：數(shù)據(jù)結(jié)構(gòu)的概念 算法的分析與評價4數(shù)據(jù)結(jié)構(gòu)第一章 緒 論1.1 什么是數(shù)據(jù)結(jié)構(gòu)用計算機解決問題的方法:問題建模編程設計算法調(diào)試運行 建模:分析問題,提取操作對象,并分析對象之間的包含關系,用數(shù)學方程或非數(shù)學方程表示. 算法:求解問題的一種方法或一種描述. 編程:用某種高級語言實現(xiàn)的可以在計算機上運行的程序.5第一章 緒 論建模的幾個例子：1、數(shù)學方程：梁架結(jié)構(gòu)應力模型 線性方程組 人口增長模型 常微分方程 曲面面積模型 微積分 等等2、非數(shù)學方程數(shù)據(jù)結(jié)構(gòu)的范疇： 圖書館書目檢索系統(tǒng) 表格、關系模型 人機 對弈 樹狀模型 多交叉路口交通控制燈管理 圖模型 服務業(yè)窗口排隊情

3、況的最佳方案 隊列模型 多數(shù)據(jù)排序 數(shù)據(jù)模型 6第一章 緒 論圖11“三子棋”對弈樹的局部情況初始狀態(tài)ABCDE圖12“五叉路口”交通燈控制可能通路連線表示不可同時通行通路ABACADBABC BDDADB DCEAEB EC ED圖的頂點著色問題7第一章 緒 論數(shù)據(jù)結(jié)構(gòu)的地位與作用：計算機硬件計算機軟件數(shù)學編碼理論 算子關系數(shù)據(jù)類型數(shù)據(jù)的表示 數(shù)據(jù)運算數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)存取機器組織數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)教學計劃中的核心課程之一，是一門綜合性的專業(yè)基礎課程。8第一章 緒 論1.2 基本概念與術(shù)語1、數(shù)據(jù)：客觀事物的符號表示。2、數(shù)據(jù)元素：數(shù)據(jù)的基本單位，通常當作一個整體來處理，它常由數(shù)據(jù)項組成。數(shù)據(jù)項

4、是不可分割的最小單位。3、數(shù)據(jù)對象：數(shù)據(jù)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。4、數(shù)據(jù)結(jié)構(gòu)：相互之間存在的一種或多種特定關系的數(shù)據(jù)元素的集合。5、結(jié)構(gòu)：數(shù)據(jù)元素之間的相互關系。集合圖或網(wǎng)絡線性結(jié)構(gòu) 樹9第一章 緒 論數(shù)據(jù)結(jié)構(gòu)的形式定義：Data-Structure=(D,S)其中D數(shù)據(jù)元素的集合，S是建立在D上的關系。例1、計算機中的算數(shù)可定義為： Complex=(C,R) 其中：C是兩個實數(shù)的集合C1,C2;R=P,而P是定義在集合C上的關系,表示C上的有序偶對，C1表示復數(shù)的實部，C2表示復數(shù)的虛部。例2、含有N個元素的數(shù)組： Array=( i,R) 其中i表示ai|ai為 整數(shù)，i=1

5、,2,N R=|i=1,2,.N-110第一章 緒 論例3：設某課題小組由一名教授、13名副教授、16名講師組成，它們之間構(gòu)成課題開發(fā)的指導關系，教授指導副教授，副教授指導12名講師。6、邏輯結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中定義的數(shù)據(jù)元素之間的邏輯關系。則課題小組的數(shù)據(jù)結(jié)構(gòu)為：Group=(P,R) 其中：P=P,V1,Vm,T11,Tmn| 1m3,1n2 R=R1,R2 R1=| 1im,1m3 R2=| 1im,1m3, 1jn,1n27、物理結(jié)構(gòu)、存儲結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（又稱映象）。11第一章 緒 論8、結(jié)點 數(shù)據(jù)元素在計算機中的存儲映象。9、順序存儲結(jié)構(gòu)（順序映象） 借助元素在存儲器中的

6、相對位置表示數(shù)據(jù)元素之間的邏輯關系，即數(shù)據(jù)邏輯位置與存儲位置順序相一致。10、鏈式存儲結(jié)構(gòu)（非順序映象） 借助元素在存儲器中的地址（指針）表示數(shù)據(jù)元素之間的邏輯關系，即數(shù)據(jù)邏輯位置與存儲位置順序不一致。11、數(shù)據(jù)類型 一個值的集合和定義在這個值集上的一組操作的總稱。 一般分成：原子類型 和 構(gòu)造類型12第一章 緒 論12、抽象數(shù)據(jù)類型ADT 指一個數(shù)學模型以及定義在該模型上的一組操作。它僅取決于一組邏輯特性，而與計算機的存儲與實現(xiàn)無關。 一個抽象數(shù)據(jù)類型的軟件模塊通常由定義、表示和實現(xiàn)三部分組成。抽象數(shù)據(jù)類型的表示：ADT（D，S，P）其中：D表示數(shù)據(jù)對象，S表示D上的關系，P表示對D的操作A

7、DT抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象的定義 偽代碼 數(shù)據(jù)關系：數(shù)據(jù)關系的定義 偽代碼 基本操作：基本操作的定義 函數(shù)調(diào)用及說明 ADT抽象數(shù)據(jù)類型名13第一章 緒 論例：用抽象數(shù)據(jù)類型定義一個三元組(e1,e2,e3) ADT Triplet 數(shù)據(jù)對象：D=e1,e2,e3 數(shù)據(jù)關系：S=, 基本操作： initTriplet(&T,v1,v2,v3); 初始條件：T已定義的三元組，v1,v2,v3已賦值 操作結(jié)果：構(gòu)造T，v1,v2,v3分別賦給e1,e2,e3 Max(T,&e) 表示能返回值 初始條件：三元組T已存在 操作結(jié)果：用e返回T的最大值 . ADT Triplet14第一章

8、緒 論 通過固有的數(shù)據(jù)類型來表示與實現(xiàn)。 本書 采用類C語言作為描述工具目的：易于描述與討論算法，但不拘泥于C語言本身的細節(jié)，又容易轉(zhuǎn)換成C或C程序。 主要有以下方面：1、預定義一些常量與類型 1.3 抽象數(shù)據(jù)類型的表現(xiàn)與實現(xiàn)TrueFalseokErrorinfeasibleOverflowint1010-1-2Status2、數(shù)據(jù)結(jié)構(gòu)表示 用typedef 描述 元素類型約定用 ElemType ,用戶根據(jù)實際自行定義。15第一章 緒 論3、基本操作的算法用如下形式的函數(shù)描述： 函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表） /算法說明 語句序列 /函數(shù)名 函數(shù)參數(shù)需要說明類型，而輔助變量則可以不做說明。

9、 在形參表中以&開頭的參數(shù)即為引用參數(shù)（傳地址）4、賦值語句有多種靈活的表示 如成組賦值、交換賦值、條件賦值等5、選擇語句 if/if-else/switch6、循環(huán)語句 for/while/do-while16第一章 緒 論7、結(jié)束語句 return/break/exit( )8、輸入輸出語句 scanf/printf9、注釋： /10、基本函數(shù) max/min/ abs/ floor/ceil/eof( )/eoln( )11、邏輯判定 與& 或 |，采用優(yōu)先判定法。 特別注意： 以上表示類似于C語言，但又不同于C語言，同學們務必掌握其表現(xiàn)方法，為將來學習算法描述奠定基礎。在將算法轉(zhuǎn)換成C

10、程序時，必須遵守C語言的語法規(guī)則，上機時不能盲目照搬照抄算法，否則上機將得不到結(jié)果。17181920第一章 緒 論1.4 算法與算法分析一、算法（Algorithm) 對特定問題求解步驟的一種描述，是指令的有限序列。算法特性：1、有窮性 一個算法對任何輸入均應在有限步內(nèi)完成，且每一步都可在有限時間內(nèi)完成。（時間可接受性）2、確定性 對同一輸入的不同運行只能得到同一輸出。3、可行性 算法操作只能通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)4、輸入 可以是0個或多個5、輸出 至少1個以上21第一章 緒 論二、算法設計的要求1、正確性（correctness) 分四層 1)不含語法錯誤 2)對幾組數(shù)據(jù)運行

11、正確 3)對精心選擇的、比較邊緣的數(shù)據(jù)運行正確 4)對任何輸入均能正確運行（無錯誤程序）2、可讀性(readability)3、健壯性(robustness)4、效率與存儲容量要求 效率指算法執(zhí)行時間。 存儲容量指算法執(zhí)行過程中所需的最大存儲空間。22第一章 緒 論三、算法效率的度量度量方法：1、事后統(tǒng)計法根據(jù)運行結(jié)果去統(tǒng)計時間2、事前分析估計法 一個程序的執(zhí)行時間取決于： 1)算法的選取 主觀因素 2)問題的規(guī)模 3)語言的選取 4)編譯程序所產(chǎn)生的機器代碼質(zhì)量 5)機器執(zhí)行指令的速度 客觀因素中的問題的規(guī)模是無法抗拒的,而其它因素則是可以改變的.因此算法效率主要考慮1)和2)兩方面.客觀因

12、素23第一章 緒 論一般地:算法中的基本操作的重復執(zhí)行次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，因此算法的時間度量記作: T(n)=O(f(n)在分析基本操作的重復執(zhí)行次數(shù)時,可以考慮最深層循環(huán)語句的執(zhí)行頻度(為什么?)。例 1) +x;s+=x; O(1) 2) for(i=0;in;i+) +x;s+=i; O(n) 3) for(i=0;in;i+) for(j=0;jn;j+) +x;s+=i+j; O(n2) 4) for(i=0;in;i+) O(n3) for(j=0;jn;j+) for(k=0;k=0稱為長度）。元素(item)稱為記錄，由若干數(shù)據(jù)項組成(屬于同一數(shù)據(jù)對象)。文件(

13、file)含有大量記錄(record)的線性表?；静僮鳎涸L問、求長度、插入、刪除等。29第二章 線性表線性表的抽象數(shù)據(jù)類型：ADT List 數(shù)據(jù)對象： D=ai|i=1,2,3.n;n=0數(shù)據(jù)關系：R1=|aiD,i=1,2,.n基本操作：initList(&L) DestoryList(&L) ClearList(&L) ListEmpty(L) ListLength(L) GetElem(L,i,&e) LocateElem(L,e,compare( ) PriorElem(L,cur-e,&next-e) NextElem(L,cur-e,&next-e) Listinsert(&L

14、,i,e) ListDelete(&L,i,&e) ListTraverse(L,visit( ) ADT List30第二章 線性表例21 利用表LA和LB分別表示兩個集合A和B，求AABvoid union( 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); /union算法思想：把lb中不屬于la的元素加入到la的后面。時間復雜度：O

15、(la_len*lb_len)31第二章 線性表例22 兩個線性表la和lb均以非遞減順序存放，將la和 lb歸并到lc中后仍以非遞減順序存放。void MergeList(list la,list lb,list &lc) initlist(lc); i=j=1;k=0; la_len=ListLength(la);lb_len=ListLength(lb); while(i=la_len)&j=lb_len) GetElem(la,i,ai);GetElem(lb,j,bj); if(ai=bj) Listinsert(lc,+k,ai;i+); else Listinsert(lc,+k

16、,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,bi); /MergeList時間復雜度：O(la_len+lb_len)322.2 線性表的順序表示與實現(xiàn) 線性表的循序表示：用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素數(shù)據(jù)元素的存儲位置LOC(ai)滿足下列關系： LOC(ai+1)=LOC(ai) LOC(ai)=LOC(a1)+(i-1)*l線性表數(shù)據(jù)元素的關系:邏輯上相鄰在物理上也相鄰。33第二章 線

17、性表線性表的順序存儲：用高級語言中的一維數(shù)組實現(xiàn)。 其描述如下：# define List_init-size 100 /初始分配量#define Listincrement 10/分配增量typedef struct Elemtype *elem; /存儲空間基址 int length; /當前長度 int listsize;/當前分配的存儲容量 / (以sizeof(ElemType)為單位)sqlist;34第二章 線性表初始化線性表：Status initList(sqlist &L) /構(gòu)造一個空線性表L L.elem=(ElemType *) malloc(List_init-si

18、ze *sizeof(ElemType); if (!L.elem) exit(OVERFLOW); L.lenth=0; L.listsize= List_init-size ;訪問線性表的第i個元素，在C語言中用L.elemi-1實現(xiàn)。35第二章 線性表插入算法：在線性表L中的第i個位置前插入新元素e.Status Listinsert_sq(sqlist &l,int i,ElemType e) if (il.length+1) return error; if (l.length=L.listsize) newbase=(ElemType *) realloc(L.elem, list

19、size+listincrement) *sizeof(ElemType); if (!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=listcrement ; q=&(l.elemi-1); for(p=&(l.eleml.length-1);p=q;-p) *(p+1)=*p; *q=e; +l.length; return ok;/ listinsert_sq;元素后移！時間復雜度：O(n),n為線性表長度36第二章 線性表刪除算法：在線性表L中刪除第i個元素，并返回給e.Status Listdelete_sq(sqlist

20、&l,int i,ElemType &e) if (il.length+1) return error; p=&(l.elemi-1); e=*p; q=l.elem+l.length-i; for(+p;p=q;+p) *(p-1)=*p -l.length; return ok;/ listdelete_sq;元素前移！時間復雜度：O(n),n為線性表長度37第二章 線性表查找：在線性表L中查找第1 個值與e滿足compare()的元素的位序。 int LocateElem_sq(sqlist L,ElemType e,status(*compare) (Elemtype,Elemtype

21、) /成功返回位序，否則返回0 i=1; p=l.elem; while(i=l.length &!(*compare)(*p+,e) +i; if (i=l.length) return i; else return 0;/ locateElem_sq38第二章 線性表兩有序序列歸并：void mergelist_sq(sqlist la,sqlist lb,sqlist &lc) pa=la.elem;pb=lb.elem; lc.listsize=lc.length=la.length+lb.length; pc=lc.elem=(elemtype*)malloc(lc.listsize

22、*sizeof(elemtype); if (!lc.elem) exit(OVERFLOW); pa_last=la.elem+la.length-1; Pb_last=lb.elem+lb.length-1; while (pa=pa_la)& pb=pa_last) if (*pa=*pb) *pc+=*pa+; else *pc+=*pb+ ; while(pa=pa_last) *pc+=*pa+; while(pb=pb_last) *pc+=*pb+; /mergelist_sq;39第二章 線性表2.3 線性表的鏈式表示與實現(xiàn) 線性表的順序表示的特點：邏輯上相鄰的兩個元素在物理

23、位置上相鄰，插入、刪除操作需移動大量數(shù)據(jù)（平均移動一半），但能隨機訪問。線性表的鏈式表示的特點：邏輯上相鄰的兩個元素在物理位置上不相鄰，插入、刪除操作不需移動數(shù)據(jù)，但不能隨機訪問。 2.3.1 線性鏈表數(shù)據(jù)域 指針域Node指示下一個元素的地址鏈表：n個結(jié)點（ai(1=inext指向下一個元素（結(jié)點）a i+1.42第二章 線性表GetElem在單鏈表中的實現(xiàn)：Status GetElem_l(linklist l,int i,elemtype &e)/L為帶頭結(jié)點的單鏈表，當?shù)趇個元素存在時，其值賦給e. p=L-next; j=1; while (p & jnext; +j; if(!p|

24、ji) return error; e=p-data; return ok; /GetElem_l 43第二章 線性表在單鏈表中插入一個元素： b a pb a px sb a px s(a) 初始狀態(tài)：在a后面插入元素x。(b) 構(gòu)造x結(jié)點s，將x指針鏈到b(p后面)操作：s-next=p-next(c) 把x結(jié)點s鏈到p后面操作：p-next=s注意操作次序44第二章 線性表在單鏈表 中插入一個元素的算法： Status listinsert_L(linklisi &l,int i,elemtype e)/在帶頭結(jié)點的單鏈表L中第i個位置之前插入元素e p=l;j=0; while (p

25、&jnext ;+j; if ( !p | ji-1)return error; s=(Linklist ) malloc(sizeof(Lnode); s-data=e; s-next=p-next; p-next (b) 刪除b結(jié)點 p-next=p-next-next(c) 釋放b結(jié)點 free(q) 注意操作要點與步驟。46第二章 線性表在單鏈表中刪除一個元素的算法： Status listdelete_L(linklisi &l,int i,elemtype &e)/在帶頭結(jié)點的單鏈表L中，刪除第i個元素，并由e返回 p=l;j=0; while (p-next &jnext ;+j

26、; if ( !p-next | ji-1)return error; q=p-next p-next=p-next-next; e=q-data; free(q); return ok;/ linkdelete_L; 時間復雜度為O(n)47第二章 線性表創(chuàng)建鏈表：方法1：每次將數(shù)據(jù)插入到頭結(jié)點的后面（逆序輸入）。Void creatlist_L(linklist &l,int n)/n 為元素個數(shù),l為頭結(jié)點 l=(linklist) malloc(sizeof(Lnode); l-next=NULL; for(i=n;i0;i-) p=(linklist) malloc(sizeof(L

27、node); scanf(&p-data); p-next=l-next;l-next=p;/注意用圖表示 /creatlist_L;48第二章 線性表創(chuàng)建鏈表：方法2：每次將數(shù)據(jù)插入到鏈表尾部（正序輸入數(shù)據(jù)）。Void creatlist_L(linklist &l,int n)/n 為元素個數(shù),l為頭結(jié)點 l=(linklist) malloc(sizeof(Lnode); l-next=NULL; q=l; for(i=1;idata); q-next=p;q=p;/注意用圖表示 q-next=NULL;/creatlist_L;49第二章 線性表鏈表歸并：特點：不增加空間，只改變原鏈指

28、針。void mergelist_l(linklist &la,listlink &lb,listlink &lc)/非遞減鏈表la和lb歸并成lc pa=la-next;pa=-lb-next; lc=pa=la; while(pa&pb) if(pa-datadata) pc-next=pa;pc=pa;pa=pa-next; else pc-next=pb;pc=pb;pb=pb-next; pc-next=pa?pa:pb; free(lb);/mergelink_L; /時間復雜度O(m+n)50第二章 線性表2.3.2 循環(huán)鏈表a1an-1a2anLL空表特點:一個結(jié)點的指針域指向

29、頭結(jié)點，鏈表形成一個環(huán)。非空表操作：同單鏈表，只需改變循環(huán)判別條件。有時為了方便，可以只設立尾指針，而不設頭指針。如用尾指針表示的兩個循環(huán)鏈表的連接運算，其算法時間為O（1）。51第二章 線性表2、3、3 雙向鏈表1、單鏈表的不足：查找前趨結(jié)點的時間為O(n),因為必須從頭找起，為此設立雙向鏈表。2、雙向鏈表結(jié)點有兩個指針域，一個指向其前趨，一個指向其后繼。priordatanextdataABCLL空表非空表52第二章 線性表3、雙向鏈表的存儲結(jié)構(gòu)Typedef struct dulnode elemtype data; struct dulnode *prior; struct dulno

30、de *next; dulnode, *dulinklist;priordatanext設d為雙向循環(huán)鏈表中的一個結(jié)點，則顯然有： d-next-prior=d-prior-next=dABCABCpp(a) 刪除前刪除P結(jié)點(b) 刪除后刪除操作：(1)(2)53第二章 線性表刪除算法：Status listdelete_dul(dulinklidt &l,int i,elemtype &e) if (!(p=getelemP-dul(L,i) return error; e=p-data; p-prior-next=p-next; (1) p-next-prior=p-prior; (2)

31、 free(p); return ok; /listdelete_dul;54第二章 線性表插入算法：Status listinsert_dul(dulinklidt &l,int i,elemtype e) if (!(p=getelemt-dul(L,i) return error; if(!(s=(dulinklist)malloc(sizeof(dulnode) return error; s-data=e; s-prior=p-prior; (1) p-prior-next=s; (2) s-next=p; (3) p-prior=s; (4) return ok; /listins

32、ert_dul;ABpxs 注意順序，先掛后斷55第二章 線性表2.4 一元多項式表示及相加一、多項式的表示設多項式按升冪寫成： pn(x)=p0+p1x+p2x2+pnxn則可用n+1個系數(shù)唯一確定，因此可用線性表P來表示. p=(p0,p1,p2,pn )其中指數(shù)隱含在其系數(shù)序號中。二、多項式存儲結(jié)構(gòu)的思考1、順序存放適用于多項式指數(shù)分布比較均勻的情形。2、鏈表存儲適用于多項式指數(shù)分布比較稀疏的情形。 此時，多項式結(jié)點結(jié)表示為：系數(shù) 指數(shù) 指針三、多項式相加算法實際上是歸并算法的改進（注意合并、刪除等）。56第三章 棧和隊列本章重點1、棧結(jié)構(gòu)的表示與實現(xiàn)2、隊列結(jié)構(gòu)的表示實現(xiàn)3、棧與隊列的

33、典型應用難點1、棧的應用2、回溯算法、表達式計算方法（編譯）實驗報告用C語言實現(xiàn)迷宮求解算法。57第三章 棧和隊列3、1 棧一、棧的ADT定義與特點棧(stack)：是限定在表尾進行插入或刪除操作的線性表。棧頂(top)：進行插入或刪除的一端。棧底(bottom)：線性表中固定不動的一端。topbottompushpop1、概念2、特點LiFO：Last in First Out 58第三章 棧和隊列ADT Stack 數(shù)據(jù)對象：d=ai|aielemset,i=1.2.n, n0 數(shù)據(jù)關系：r1=| ai-1,ai D,i=1,2,n 基本操作： initstack(&S) destorys

34、tack(&S) clearstack(&S) stackempty(s) stacklength(s) gettop(s,&e) push(&s,e) pop(&s,&e) stacktraverse(s,visit( ) ADT stack59第三章 棧和隊列3.1.2 棧的表示與實現(xiàn)和線性表一樣，棧同樣有兩種存儲實現(xiàn)，即順序與鏈式存儲。本節(jié)只討論棧的順序存儲：# define stack_init_size 100#define stackincrement 10typedef struct selemtype *base;/棧底 selemtype *top;/棧頂指針,指向棧頂?shù)目瘴?/p>

35、置 int stacksize;/棧空間大小sqstack;antopbottompushpop60第三章 棧和隊列基本算法：Status initstack(sqstack &s) s.base=(selemtype *)malloc(stack_init_size *sizeof(elemtype) if(!s.base) exit(OVERFLOW); s.top=s.base; s.stacksize=stack_init_size; return OK;Status gettop(sqstack s,selemtyope &e) if (s.top=s.base) return er

36、ror; e=*(s.top-1);/注意棧頂指針位置 return ok;61第三章 棧和隊列基本算法：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) exit(OVERFLOW); s.top=s.base+s.stacksize; s.stacksize+=stackincrement; *s.top+=e;return

37、 OK;Status pop(sqstack &s,selemtyope &e) if (s.top=s.base) return error; e=*-s.top;/注意棧頂指針位置 return ok;/pop62第三章 棧和隊列3.2 棧的應用一、數(shù)制轉(zhuǎn)換 十進制到其它進制的轉(zhuǎn)換，其結(jié)果的生成是一個典型的LiFO（后進先出）類型。Void conversion(int n,int p)/n轉(zhuǎn)換為p進制數(shù) initstack(s); while (n) push(s,n%p);n=n/p; while(!stack(empty(s) pop(s,e);printf(“%d”,e); 二、括

38、號匹配的檢查 檢查表達式中（）的匹配情況：設立一個棧，讀入“(”則進棧，讀入“)”則出棧。當表達式結(jié)束時棧恰為空，匹配；其余任何情況均出錯。63第三章 棧和隊列3、2、3 行編輯程序通常做法：數(shù)據(jù)輸入緩沖區(qū)，如發(fā)現(xiàn)錯誤及時改正，待輸入回車鍵后存入用戶數(shù)據(jù)區(qū)。如刪除前一個字符，刪除本行前面所有字符。 如輸入： whli#ilr#e(s#*s) outchaputchsr(*s=#+)等價于： while(*s) putchar(*s+)為此可將緩沖區(qū)設為一個棧，輸入 非#、則壓棧， 是則彈棧， 是則清空棧。64第三章 棧和隊列算法：Void linedit( )initstack(s);Ch=g

39、etchar( );While(ch!=EOF) while(ch!=EOF&ch!=n) switch(ch) case #: pop(s,c); case :clearstack(s); default:push(s,ch); ch=getchaar(); 將棧中的元素送到數(shù)據(jù)區(qū)； if(ch!=EOF) ch=getchar( ); destorystack(S);/ lineedit65第三章 棧和隊列3.2.4 迷宮求解 入口出口思想：“窮舉求解”，即從入口出發(fā)，沿某一 方向前進，若能走，則繼續(xù)；否則，沿原路退回一格（回溯），換一個方向繼續(xù)，直到到達出口（成功）或已搜索所有可能路徑（

40、失?。?。計算機走宮應解決的幾個問題： 1、迷宮存放通與不通的表示 2、當前位置 3、搜索方向 4、改變方向 5、當前路徑 6、前進一步 7、后退一步 8、實現(xiàn)方法66第三章 棧和隊列描述算法：設定入口位置（當前位置）do 若當前位置可通 則 將當前位置插入棧頂； 若該位置是出口位置，則結(jié)束； 否則改變當前位置到東鄰位置； 否則 若棧不空且棧頂位置尚有其它方向未搜索 則設定新的當前位置為棧頂位置的下一鄰塊 若棧不空且棧頂位置四周不通 則 刪去棧頂位置； 若棧不空，則重新測試新的棧項位置， 直到找到一個可通的鄰塊或?？眨?while (棧不空）67第三章 棧和隊列棧的元素結(jié)構(gòu)：typedef st

41、ruct int ord;/路徑號 posttype seat; int di;/方向 selemtypeStatus mazepath(mazetype maze,poptype start,poptype eds)initstack(s);curpos=start;Curstep=1;do if (pass(curpos) footprint(curpose); e=(curstep,curpos,1); push(s,e); if(curpos=end) return(true); curpos=nextpos(curpos,1); curstep+; 68第三章 棧和隊列else /當

42、前位置不通 pop(s,e) while(e.di=4&!stackempty(s) makeprint(e.seat);pop(s,e); if(e.di4) e.di+;push(s,e); curpos=nextpos(e.seat,di); while(!stackempty(s);Return(FALSE);/mazepath算法續(xù)上頁：69第三章 棧和隊列3.2.5 表達式求值方法：利用編譯原理知識中的算法優(yōu)先關系表對日常表達式進行運算。要求：從鍵盤以字符串方式輸入一算術(shù)表達式（只含 和括號運算）建立算符優(yōu)先表為計算，設立兩個棧：OPTR運算符棧和OPND運算操作數(shù)棧按下面算法求值

43、： 1）OPND置空，OPTR清空再將壓棧 2）讀表達式字符，若是操作數(shù)，則進OPND棧， 是運算符，則和OPTR棧頂元素比較，選擇進?；蜻\算。重復上述過程，直到結(jié)束。70第三章 棧和隊列Operandtype EvaluateExpression( ) initstack(optr);push(optr,#); initstack(opnd);c=getchar(); while(c!=#|gettop(optr)!=#) if(!in(c,op)push(opnd,c);c=getchar(); else switch(precde(gettop(optr),c) case :pop(op

44、tr,theta); pop(opnd,b);pop(opnd,a); push(onpd,operate(a,theta,b);break; /while return gettop(opnd);表達式運算算法71第三章 棧和隊列3、4 隊 列一、抽象數(shù)據(jù)類型隊列的定義特點： 隊列是一種先進先出表（FiFO），插入和刪除分別在隊列的兩端進行，類似于日常生活中的各種排隊現(xiàn)象。 隊頭（FRONT）：允許刪除的一端 隊尾（REAR）：允許插入元素的一端典型應用： 操作系統(tǒng)中作業(yè)隊列、就緒進程等a1 a2 a3 anfrontrearoutin72第三章 棧和隊列ADT queue 數(shù)據(jù)對象：d=a

45、i|aielemset,i=1.2.n, n0 數(shù)據(jù)關系：r1=| ai-1,ai D,i=1,2,n 基本操作： a1為隊頭 an為隊尾 initqueue(&Q) destoryqueue(&Q) clearqueue(&Q) queueempty(Q) queuelength(Q) Gethead(Q,&e) enQueue(&Q,e) DeQueue(&Q,&e) queuetraverse(Q,visit( ) ADT queue73第三章 棧和隊列雙端隊列： 隊列兩端均可以插入和刪除。(形變）a1 a2 a3 anend1end2a1 a2 a3 anend1end2a1 a2 a

46、3 anend1end274第三章 棧和隊列3、4、2 鏈隊列兩個指針：一個指向隊頭，一個指向隊尾。a1an-1a2an Q.frontQ.reara1an-1a2an Q 其操作實現(xiàn)同鏈表運算，詳見教材P62。75第三章 棧和隊列3、4、3 循環(huán)隊列 在隊列順序存儲方式中（數(shù)組存儲），為充分利用給定的存儲空間和避免隊列操作時數(shù)據(jù)移動，我們需將隊列改造成為循環(huán)隊列。01maxsize - 1q.frontq.rear隊列元素關鍵問題： 隊空與隊滿條件的區(qū)別：q.front=q.rear?區(qū)別方法： 1）專設標志位 2）騰空一個單元，當隊尾追上隊頭時隊滿，反之當隊頭追上隊尾時隊空。一般常采用第2

47、種方法。76第三章 棧和隊列算法：循環(huán)隊列順序存儲Tyopedef struct Qelemtype *base; int front; int rear; SqueueStatus initqueue(squeue &q) q.base=(qelemtype *)malloc(maxqsize*sizeof(qelemtuype);if(!q.base)exit (overflow);q.front=q.rear=0;Return OK;隊列初始化int queuelength (squeue q)return q.rear-q.front+maxqsize)%maxqsize;隊長度77第

48、三章 棧和隊列status enqueue (squeue &Q,qelemtype e) if(Q.rear+1)%maxqsize=Q.front)return ERROR; Q.baseQ.rear=e; Q.rear=(Q.rear+1)%maxqsize; return OK;/入隊status dequeue (squeue &q,qelemtype &e) if(Q.rear= =Q.front) return ERROR; e=Q.baseQ.front; Q.front=(Q.front+1)%maxqsize; return OK;/出隊78第4章 串字符串的特點：非數(shù)值計

49、算問題，因而其操作比數(shù)值問題要復得多。字符串的應用非常廣泛：如源程序、文字處理、事物處理、信息檢索、自然語言翻譯系統(tǒng)及音樂分析程序等均以字符串數(shù)據(jù)作為處理對象的。4、1 串類型定義串（String):是由0個或多個字符的有限序列。表示： s=a1a2an (n=0) 空串：長度為0 (即n=0)的字符串稱為串。子串：串中任意個連續(xù)的字符組成的子序列。主串：包含子串的串位置：字符在序列中的序號79第4章 串串相等：串長度相等并且對應字符全部相等。空格串：同一個或多個空格字符組成的串。ADT string 數(shù)據(jù)對象：Dai|aiCharacterset i=1,2,n,n0數(shù)據(jù)關系：Ri=| ai

50、 D i=1,2,n基本操作： destorystring(&s) strassign(&t,chars) concat(&t,s1,s2) strcopy(&t,s) substring(&sub,s,pos,len) strempty(s) index(s,t,pos) strcompare(s,t) replace(&s,t,v) strlength(s) strinsert(&s,pos,t) claerstring(&s) strdelete(&s,pos,len)ADT string80第4章 串算法例子： int index(string s,string t,int pos)

51、if (pos0) n=strlength(s);m=strlength(t);i=pos; while(i=n-m+1) substring(sub,s,i,m); if(str(compare(sub,t)!=0) +i; else return i; return 0;81第4章 串4.2 串的表示與實現(xiàn)4、2、1 定長順序存儲表示 一般用定長數(shù)組實現(xiàn)。 #define maxstrlen 255 typedef unsigned char sstringmaxstrlen+1;/0號單元存放字符串的長度算法：1、串連接 concat(&t,s1,s2) 分三種情況： s10+s20 m

52、axstelen s10maxstrlen & s10+s20 maxstelen s10=maxstrlen 82第4章 串Status concat (sstring &t,sstring s1;sstring ,s2) if(s10+s20 maxstelen) t1.s10=s11.s10; ts10+1.s10+s20=s21.s20; t0=s10+s20; uncut=TRUE; else if(s10maxstrlen ) t1.s10=s11.s10; ts10+1.maxstrlen=s21.maxstrlen-s10; t0=maxstrlen;unxut=False;

53、else t1.maxstrlen=s11.maxstrlen;uncut=False; return uncut83第4章 串Status substring(sstring &sub,sstring s,int pos,int len) if(poss0 |lens0-pos+1) return error; Sub1.len=spos.pos+len-1; Sub0=len;return OK;2、求子串substring(&sub,s,pos,len) 首先進行合法檢查 如合法 ，則求出其中的子串部分。84第4章 串4、3 串的模式匹配算法4、3、1 求子串位置的定位函數(shù) 子串的定位操

54、作通常稱作串的模式匹配，它是字符串處理系統(tǒng)中最重要的操作之一。int index (sstring s,sstring t,int pos)/S為源串，T為模式串，pos為S中的起始位置i=pos;j=1; while(i=s0&jt0) return i-t0; else return 0;/匹配成功，返回其位置，否則返回0；85第4章 串應用：文本編輯、求子串例子：s=“ababcabcacbab”,t=“abcac”,pos=1第一趟： ababcabcacbab abc 第二趟： ababcabcacbab a 第四趟： ababcabcacbab a 第三趟： ababcabcacb

55、ab abcac 第五趟： ababcabcacbab a 第六趟： ababcabcacbab abcac i=3i=2i=7i=4i=5i=11j=3j=1j=5j=1j=1j=6返回坐標 686第4章 串int strlen( char *s)/98年程序員下午試題一 char *t=s; while (*t+); return t-s-1;int commstr( char *str1,char *str2,int *sublen)char *s1,*s2; int count=0,len1,len2,k,j,i,p; len1=strlen(str1); len2=strlen(st

56、r2); if (len1len2) s1=str1;s2=str2; else len2=len1;s1=str2;s2=str1;應用舉例：求兩個字符串的最長公共子串和它們的個數(shù)。87第4章 串for(j=len2;j0;j-) for(k=0;k+j len2;k+) for(i=0;s1i+j-1!=0;i+) for(p=0;pj&s1p+i=s2p+k;p+); if(p=j ) for(p=0;p0) break; *sublen=(count0)? j : 0; return count; main()char *st1=agabcdeagfabcdeaaa; char *st

57、2=gaaabcdeafd; int x,y; x=commstr(st1,st2,&y); printf(count=%d,len=%d,x,y); 斜線為待填項88第4章 串4、4 串的操作應用一、文本編輯 文本編輯程序是一個面向用戶的系統(tǒng)服務程序，廣泛應用于源程序的輸入和修改、書報排版系統(tǒng)、辦公自動化系統(tǒng)等。 基本操作：串的查找、串的插入、串的刪除操作等。二、建立詞索引表 從書目文件生成有序詞表的方法： 1）從書目文件中讀入一個書目單 2）從書目串中提取所有關鍵詞插入詞表 3）對詞表的每一個關鍵詞，在索引表中進行查找，并作相應的修改。 重復上過程，直到書目文件的結(jié)尾。89第5章 數(shù)組與廣

58、義表 本章所討論的數(shù)組是線性表的擴充，即線性表的每個元素均是一種數(shù)據(jù)結(jié)構(gòu)，俗稱多維數(shù)組。 廣義表指“表中有表”，即線性表中的每個元素可能仍然是一個線性表。5、1 數(shù)組定義ADT Array數(shù)據(jù)對象：ji=0,1,bi-1,i=1,2,.n, d=aj1j2jn|n(0)稱為數(shù)組的維數(shù),bi是第i維的長度,ji是數(shù)組第i維下標,aj1j2jnElemset數(shù)據(jù)關系：R=R1,R2,Rn90Ri=| 0jkbk-1 1 k n 且ki, 0jibi-2, aj1jijn ,aj1ji+1jnD,i=1,2.n基本操作： iinitarray(&A,n,bound1,boundn)/初始化 Dest

59、oryarray(&A)/銷毀數(shù)組 Value(A,&e,index1,，indexn)/取值 Assign(&A,e,index1,indexn)/賦值 ADT array第5章 數(shù)組與廣義表n維數(shù)組中含有b1*b2*bn個元素，n=1為線性表。91第5章 數(shù)組與廣義表二維數(shù)組定義：a00 a01 a02 a0,n-1a00 a01 a02 a0,n-1 a00 a01 a02 a0,n-1Am*n=(a00 a01 a0,n-1 )(a10 a11 a1,n-1 ) (am-1,0 am-1,1 am-1,n-1 )Am*n=a00 a01 a0,n-1 a10 a11 a1,n-1 am

60、-1,0 am-1,1 am-1,n-1 Am*n=(a0 a1 am-1 )(a0 a1 an-1 )用行向量表示：用列向量表示：矩陣表示其中ai代表數(shù)組中第i行其中aj代表數(shù)組中第j行92第5章 數(shù)組與廣義表5.2 數(shù)組的順序表示和實現(xiàn)由于數(shù)組運算沒有插入和刪除，因此用順序表示是自然的。數(shù)組存放：行主序(row major order) 列主序(column major order)。存儲位置：以行主序為例 二維數(shù)組由m*n組成， 每個元素占L個存儲單元，則： LOC(i,j)=LOC(0,0)+(i*n+j)*L | 0=i=m-1 , 0=j=n-1推廣：已知n維數(shù)組每維長度分別為b1