數(shù)據(jù)結構大話《數(shù)據(jù)結構》PPT課件

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

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

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

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

5、會溢出的問題需要隊列的鏈式存儲結構需要隊列的鏈式存儲結構 鏈隊列算法和數(shù)據(jù)結構21第三章：棧和隊列隊列的鏈式存儲算法和數(shù)據(jù)結構22NULLpFrontpRear入隊只對 pRear操作，出隊對pFront操作 鏈隊列 結點定義3.3.3隊列隊列 的存儲實現(xiàn)及運算實現(xiàn)的存儲實現(xiàn)及運算實現(xiàn)typedef struct LQNode int data; struct LQNode *next;LQueueNode;typedef struct LQueueNode *front,*rear; LinkQueue;LinkQueue *q;頭結點 .q-front隊頭隊尾q-rear頭結點q-fron

6、tq-rearv鏈隊列基本運算實現(xiàn)（1）創(chuàng)建一個帶頭結點的空隊頭結點q-frontq-rear（2）判隊空（3）入隊q-frontq-rearx入隊xq-frontq-reary入隊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出隊xyfront reary出隊（4）出隊int Out_LQueue(LinkQueue *q , ElemType *x) LQueueNode *p; if (Empty_LQueue

8、(q) ) printf (隊空)； 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; 隊列的應用算法和數(shù)據(jù)結構26模擬打印機緩沖區(qū)： 在主機將數(shù)據(jù)輸出到打印機時，會出現(xiàn)主機速度與打印機的打印速度不匹配的問題。這時主機就要停下來等待打印機。顯然，這樣會降低主機的使用效率。為此人們設想了一種辦法：為打印機設置一個打印數(shù)據(jù)緩沖區(qū)算法和數(shù)據(jù)結構27需要打印數(shù)據(jù)時，先將數(shù)據(jù)依次寫入這個緩沖區(qū)，寫滿后主機轉去做其他的事情，而打印機就從緩沖區(qū)中按照先進先出的原則依次讀取數(shù)據(jù)并打印，這樣做即保證了打印數(shù)據(jù)的正確性，又提高了主機的使用效率。由此可見，打印機緩沖區(qū)實際上就是一個隊列結構。算法和數(shù)據(jù)結構28CPU分時系統(tǒng) 在一個帶有多個終端的計算機系統(tǒng)中，同時有多個用戶需要使用CPU運行各自的應用程序，它們分別通過各自的終端向操作系統(tǒng)提出使用CPU的請