數(shù)據(jù)結(jié)構(gòu)大話《數(shù)據(jù)結(jié)構(gòu)》PPT課件

1、數(shù)據(jù)結(jié)構(gòu)大話數(shù)據(jù)結(jié)構(gòu)崔 基 哲2 0 1 6 年算法和數(shù)據(jù)結(jié)構(gòu)1算法和數(shù)據(jù)結(jié)構(gòu)2第一章 緒論第二章 算法第三章 線性表第四章 棧和隊(duì)列第五章 串第六章 樹第七章 圖第八章 查找第九章 排序棧棧是限定于只在表尾進(jìn)行插入和刪除操作的線性表?xiàng)Ｊ窍薅ㄓ谥辉诒砦策M(jìn)行插入和刪除操作的線性表后進(jìn)先出（后進(jìn)先出（Last in first out,LIFOLast in first out,LIFO）相關(guān)概念相關(guān)概念棧頂（表尾）棧底（表頭）算法和數(shù)據(jù)結(jié)構(gòu)3第四章：棧和隊(duì)列舉例：IE瀏覽器中的“前，后”常常是件很令人惱火的事情尤其是在我們這樣的人口大國w 電話亭1978年在北京15%的電話要在1小時(shí)后才能接通。

2、在電報(bào)大樓打電話的人還要帶著午飯去排隊(duì) w 銀行窗口，ATMw 醫(yī)院、理發(fā)、火車售票w 游樂場(chǎng)的游樂項(xiàng)目算法和數(shù)據(jù)結(jié)構(gòu)5w 在游樂園中的頻頻排隊(duì)會(huì)極為掃興算法和數(shù)據(jù)結(jié)構(gòu)6算法和數(shù)據(jù)結(jié)構(gòu)7怎樣縮短排隊(duì)的等待時(shí)間？算法和數(shù)據(jù)結(jié)構(gòu)8w 銀行的排隊(duì)叫號(hào)機(jī) 只是有序的組織了顧客，并沒有減少等待時(shí)間w 如果能實(shí)現(xiàn)知道輪到自己需要等待多少時(shí)間，再選擇合適的時(shí)間來，豈不很好？w 排隊(duì)排隊(duì)( (隊(duì)列隊(duì)列) )到底有什么學(xué)問？到底有什么學(xué)問？隊(duì)列隊(duì)列的特點(diǎn)隊(duì)列的特點(diǎn) 先進(jìn)先出，F(xiàn)irst in first out(FIFO)相關(guān)概念相關(guān)概念 隊(duì)頭：刪除 隊(duì)尾：插入算法和數(shù)據(jù)結(jié)構(gòu)9A1 A2 A3 A4 A5 An

3、入隊(duì)出隊(duì)隊(duì)頭（front）隊(duì)尾（rear）第三章：棧和隊(duì)列隊(duì)列的操作初始化：初始化：InitQueueInitQueue判斷是否為空：判斷是否為空：IsEmptyIsEmpty入隊(duì)列：入隊(duì)列：EnQueueEnQueue出隊(duì)列：出隊(duì)列：DlQueueDlQueue取隊(duì)列頭：取隊(duì)列頭：GetHeadGetHead清空隊(duì)列：清空隊(duì)列：ClearClear得到隊(duì)列長度：得到隊(duì)列長度：GetSizeGetSize算法和數(shù)據(jù)結(jié)構(gòu)10第三章：棧和隊(duì)列隊(duì)列順序存儲(chǔ)的不足隊(duì)列順序存儲(chǔ)的不足排隊(duì)打飯，頭名打完后面所有元素都要往前移動(dòng)，O(n) 不必要的浪費(fèi)？引入兩個(gè)指針：假溢出 算法和數(shù)據(jù)結(jié)構(gòu)11算法和數(shù)據(jù)結(jié)構(gòu)

4、12012345678910(3)(4)(5)(6)(7)Q(8)tailhead012345678910(4)(5)(6)(7)Q(8)tailhead循環(huán)隊(duì)列算法和數(shù)據(jù)結(jié)構(gòu)13假溢出 當(dāng)隊(duì)頭與隊(duì)尾元素重合時(shí)候，隊(duì)滿溢出算法和數(shù)據(jù)結(jié)構(gòu)14循環(huán)隊(duì)列演示J1Q.frontQ.rearJ2J3J1J2J3Q.frontQ.rearJ3Q.frontQ.rearJ4J5J6J3J5J6J4Q.frontQ.rearJ5J6Q.frontQ.rearJ7J8還存在問題不是循環(huán)存儲(chǔ)，算法的時(shí)間性能不高不是循環(huán)存儲(chǔ)，算法的時(shí)間性能不高是循環(huán)隊(duì)列，也要面臨著數(shù)組可能會(huì)溢出的問題是循環(huán)隊(duì)列，也要面臨著數(shù)組可能

5、會(huì)溢出的問題需要隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)需要隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 鏈隊(duì)列算法和數(shù)據(jù)結(jié)構(gòu)21第三章：棧和隊(duì)列隊(duì)列的鏈?zhǔn)酱鎯?chǔ)算法和數(shù)據(jù)結(jié)構(gòu)22NULLpFrontpRear入隊(duì)只對(duì) pRear操作，出隊(duì)對(duì)pFront操作 鏈隊(duì)列 結(jié)點(diǎn)定義3.3.3隊(duì)列隊(duì)列 的存儲(chǔ)實(shí)現(xiàn)及運(yùn)算實(shí)現(xiàn)的存儲(chǔ)實(shí)現(xiàn)及運(yùn)算實(shí)現(xiàn)typedef struct LQNode int data; struct LQNode *next;LQueueNode;typedef struct LQueueNode *front,*rear; LinkQueue;LinkQueue *q;頭結(jié)點(diǎn) .q-front隊(duì)頭隊(duì)尾q-rear頭結(jié)點(diǎn)q-fron

6、tq-rearv鏈隊(duì)列基本運(yùn)算實(shí)現(xiàn)（1）創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空隊(duì)頭結(jié)點(diǎn)q-frontq-rear（2）判隊(duì)空（3）入隊(duì)q-frontq-rearx入隊(duì)xq-frontq-reary入隊(duì)xyLQueue *Init_LQueue() LinkQueue *q; LQueueNode *p; q=(LinkQueue *)malloc(sizeof(LinkQueue); p=(LQueueNode *)malloc(sizeof(LQueueNode); p-next=NULL; q-front=q-rear=p; return q; int Empty_LQueue( LinkQueue *q)

7、 if (q-front=q-rear) return 1; else return 0; void In_LQueue(LinkQueue *q , ElemType x) LQueueNode *p; p =(LQueueNode *)malloc(sizeof(LQueueNode); p-data=x; p-next=NULL; q-rear-next=p; q-rear=p;frontrearx出隊(duì)xyfront reary出隊(duì)（4）出隊(duì)int Out_LQueue(LinkQueue *q , ElemType *x) LQueueNode *p; if (Empty_LQueue

8、(q) ) printf (隊(duì)空)； return 0; else p=q-front-next; q-front-next=p-next; *x=p-data; free(p); if (q-front-next=NULL) q-rear=q-front; return 1; 隊(duì)列的應(yīng)用算法和數(shù)據(jù)結(jié)構(gòu)26模擬打印機(jī)緩沖區(qū)： 在主機(jī)將數(shù)據(jù)輸出到打印機(jī)時(shí)，會(huì)出現(xiàn)主機(jī)速度與打印機(jī)的打印速度不匹配的問題。這時(shí)主機(jī)就要停下來等待打印機(jī)。顯然，這樣會(huì)降低主機(jī)的使用效率。為此人們?cè)O(shè)想了一種辦法：為打印機(jī)設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)算法和數(shù)據(jù)結(jié)構(gòu)27需要打印數(shù)據(jù)時(shí)，先將數(shù)據(jù)依次寫入這個(gè)緩沖區(qū)，寫滿后主機(jī)轉(zhuǎn)去做其他的事情，而打印機(jī)就從緩沖區(qū)中按照先進(jìn)先出的原則依次讀取數(shù)據(jù)并打印，這樣做即保證了打印數(shù)據(jù)的正確性，又提高了主機(jī)的使用效率。由此可見，打印機(jī)緩沖區(qū)實(shí)際上就是一個(gè)隊(duì)列結(jié)構(gòu)。算法和數(shù)據(jù)結(jié)構(gòu)28CPU分時(shí)系統(tǒng) 在一個(gè)帶有多個(gè)終端的計(jì)算機(jī)系統(tǒng)中，同時(shí)有多個(gè)用戶需要使用CPU運(yùn)行各自的應(yīng)用程序，它們分別通過各自的終端向操作系統(tǒng)提出使用CPU的請(qǐng)