【正文】 1 數(shù) 據(jù) 結(jié) 構(gòu)學(xué)生學(xué)號(hào)： ************ 學(xué)生姓名: ******* 專業(yè)班級(jí)： ******* 指導(dǎo)教師： ************ 課程設(shè)計(jì)報(bào)告 2目 錄單位員工管理系統(tǒng) ......................................1停車場(chǎng)管理 ..................................................2哈弗曼編碼 ..................................................4教學(xué)計(jì)劃編制問(wèn)題 ......................................6藥店藥品銷售統(tǒng)計(jì)系統(tǒng) ..............................9校園導(dǎo)航 ....................................................11附件 源程序代碼 ......................................15第 1 頁(yè) 共 36 頁(yè) 1單位員工通訊錄管理系1. 問(wèn)題描述為某個(gè)單位建立一個(gè)員工通訊錄管理系統(tǒng)，可以方便查詢每一個(gè)員工的辦公室電話、手機(jī)號(hào)、及電子郵箱。其功能包括通訊錄鏈表的建立、員工通訊信息的查詢、修改、插入與刪除、以及整個(gè)通訊錄表的輸出。2. 主要數(shù)據(jù)類型和函數(shù)建立員工信息管理系統(tǒng)用到鏈表的儲(chǔ)存結(jié)構(gòu)，通過(guò)單鏈表實(shí)現(xiàn)所有操作可定義如下的存儲(chǔ)結(jié)構(gòu)：typedef struct staff { /*員工通訊信息的結(jié)構(gòu)類型定義*/ char num。 /*員工編號(hào)*/ char name[8]。 /*員工姓名*/ char phone。 /*辦公室電話號(hào)碼*/ char call。 /*手機(jī)號(hào)碼*/ struct staff *next。}staff,*Linkliust。主要函數(shù)：LinkList Creat()，void Search()，void Delete(),void Insert(),void change().3. 算法設(shè)計(jì)A、首先先創(chuàng)建一個(gè)鏈表，定義一個(gè)結(jié)構(gòu)體包含一個(gè) next 指針和一個(gè)DataType 型數(shù)據(jù) data，構(gòu)造一個(gè)指針類型的函數(shù) LinkList Creat(LinkListamp。L)，需要先弄一個(gè)頭指針 head 并對(duì)其開(kāi)辟一個(gè)空間再通過(guò)一個(gè)循環(huán)實(shí)現(xiàn)鏈表的儲(chǔ)存功能。創(chuàng)建后要對(duì)其進(jìn)行一系列操作，查找、刪除、插入、修改。B、查找操作：根據(jù)輸入的需要查找的選項(xiàng)，再利用 t 利用一個(gè)循環(huán)體 while(pamp。amp。p!=t) {p=pnext。}找到所需要查找的信息。C、刪除操作：也是根據(jù)輸入要?jiǎng)h除的選項(xiàng)，先查找到要?jiǎng)h除的信息位置while(pnextamp。amp。pnext!=t){ p=pnext。 } if(pnext) {s=pnext。pnext=snext。第 2 頁(yè) 共 36 頁(yè) 2free(s)。 }通過(guò)指針的變換來(lái)實(shí)現(xiàn)刪除。D、修改操作：先輸入要修改的選項(xiàng)，然后選擇要修改的項(xiàng)目進(jìn)行修改。調(diào)試及測(cè)試結(jié)果建立記錄 查詢記錄 其他測(cè)試結(jié)果這里不一一列舉(源代碼見(jiàn)附錄)停車場(chǎng)管理（棧和隊(duì)列的應(yīng)用） 問(wèn)題描述設(shè)停車場(chǎng)是一個(gè)可以停放 n 輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次有北向南排列（大門在最南端，最先到達(dá)的第一車停放在車場(chǎng)的最北端），若車場(chǎng)內(nèi)已停滿 n 輛車，那么后來(lái)的車只能在門外的便道上等候，一旦有車開(kāi)走，則排在便道上的第一輛車即可開(kāi)入；當(dāng)停車場(chǎng)內(nèi)某輛車要離開(kāi)時(shí)，在它之后進(jìn)入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開(kāi)出大門外，其他車輛再按原次序進(jìn)入車場(chǎng)，每輛停第 3 頁(yè) 共 36 頁(yè) 3放在車場(chǎng)的車在它離開(kāi)停車場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。 需求分析停車場(chǎng)管理系統(tǒng)，以棧模擬停車場(chǎng)，以隊(duì)列模擬車場(chǎng)外的便道。首先來(lái)的車輛要進(jìn)入停車廠或者進(jìn)入便道。當(dāng)停車場(chǎng)車輛未滿時(shí)直接將車停入停車場(chǎng)。當(dāng)停車場(chǎng)車輛停滿時(shí)，則此時(shí)進(jìn)入的車輛應(yīng)該進(jìn)入便道。然后等待停車場(chǎng)中的車輛離去，離去一輛車則便道中的車輛進(jìn)入停車場(chǎng)。棧以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn) 算法設(shè)計(jì)算法思路：模擬停車場(chǎng)管理，需要用一個(gè)棧來(lái)表示停車場(chǎng)，然后用一個(gè)隊(duì)列用來(lái)表示車站停滿車時(shí)把車停在停車場(chǎng)外的便道上。本實(shí)驗(yàn)要定義一個(gè)隊(duì)列兩個(gè)棧，其中一個(gè)?？梢暂o助停車場(chǎng)中的車輛離開(kāi)，即離開(kāi)一輛車時(shí)，在此車前面的車依次進(jìn)入輔助棧，離開(kāi)后這些車輛再進(jìn)入停車棧，然后判斷隊(duì)列中是否有車，如果有則將便道隊(duì)列中的車輛移進(jìn)停車廠。否則不進(jìn)行操作。關(guān)于費(fèi)用的計(jì)算，出車站的時(shí)間減去進(jìn)車站的時(shí)間得到的時(shí)間差再乘以每小時(shí)的停車費(fèi)用就是這輛車本次停車所需要交的費(fèi)用主要函數(shù)void chushihua(SqStack amp。S) ==。初始化void jinche(SqStack amp。S,LinkQueue amp。L)車進(jìn)棧void chuche(SqStack amp。S,SqStack amp。q,LinkQueue amp。L)車出棧調(diào)試并運(yùn)行第 4 頁(yè) 共 36 頁(yè) 4進(jìn)車 車已進(jìn)滿，再來(lái)的車將進(jìn)入便道出車出車后，因?yàn)楸愕纼?nèi)有車，所以便道內(nèi)的車開(kāi)始進(jìn)停車場(chǎng)。其他測(cè)試結(jié)果這里不一一列詳細(xì)代碼見(jiàn)附錄哈夫曼編碼/譯碼系統(tǒng)（樹(shù)應(yīng)用）問(wèn)題分析利用哈夫曼編碼進(jìn)行通信，可以壓縮通信的數(shù)據(jù)量，提高傳輸效率，縮短信息的傳輸時(shí)間，還有一定的保密性?，F(xiàn)在要求編寫(xiě)一程序模擬傳輸過(guò)程，實(shí)現(xiàn)在發(fā)送前將要發(fā)送的字符信息進(jìn)行編碼，然后進(jìn)行發(fā)送，接收后將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼，即將信息還原成發(fā)送前的字符信息。第 5 頁(yè) 共 36 頁(yè) 5需求分析在本例中設(shè)置發(fā)送者和接受者兩個(gè)功能，發(fā)送者的功能包括：①輸入待傳送的字符信息；②統(tǒng)計(jì)字符信息中出現(xiàn)的字符種類數(shù)和各字符出現(xiàn)的次數(shù)（頻率） ；②根據(jù)字符的種類數(shù)和各自出現(xiàn)的次數(shù)建立哈夫曼樹(shù)；③利用以上哈夫曼樹(shù)求出各字符的哈夫曼編碼；④將字符信息轉(zhuǎn)換成對(duì)應(yīng)的編碼信息進(jìn)行傳送。接受者的功能包括：①接收發(fā)送者傳送來(lái)的編碼信息；②利用上述哈夫曼樹(shù)對(duì)編碼信息進(jìn)行翻譯，即將編碼信息還原成發(fā)送前的字符信息。從以上分析可發(fā)現(xiàn)，在本例中的主要算法有三個(gè)：（1）哈夫曼樹(shù)的建立；（2）哈夫曼編碼的生成；（3）對(duì)編碼信息的翻譯。算法設(shè)計(jì)首先讀入一組字符，然后統(tǒng)計(jì)這些字符中不同字符出現(xiàn)的次數(shù)，并當(dāng)做其權(quán)值，然后根據(jù)不同字符及其權(quán)值建立哈弗曼樹(shù)。建立哈弗曼樹(shù)后即可得到這些不同字符的哈弗曼編碼，然后即可根據(jù)這些哈弗曼編碼對(duì)那組輸入的一串字符進(jìn)行哈弗曼編碼。譯碼是根據(jù)一組編碼翻譯成一組字符的操作，其算法就是根據(jù)這一串編碼來(lái)對(duì)哈弗曼樹(shù)進(jìn)行遍歷，每遍歷到一個(gè)葉子結(jié)點(diǎn)即輸出一個(gè)字符，直至將編碼操作完即可完成多編碼的翻譯操作。主要函數(shù)void tongji(char *d1,int *w,char *d,int amp。n) 對(duì)個(gè)字符出現(xiàn)的頻率進(jìn)行統(tǒng)計(jì)void HuffmanCoding(HuffmanTree amp。HT,HuffmanCode amp。HC,int *w,int n,char *d)構(gòu)建哈夫曼樹(shù)void bianma(HuffmanCode HC,char *d1,char *d,char *bc) 哈夫曼編碼void yima(HuffmanTree HT,int n,char*bc) 有編碼得到譯碼調(diào)試并運(yùn)行輸入一段字符后，尖括號(hào)中表示的是該字符的出現(xiàn)的頻率，并得到哈夫曼編碼，最后又編碼得到譯碼第 6 頁(yè) 共 36 頁(yè) 6教學(xué)計(jì)劃編制問(wèn)題（圖的應(yīng)用） 問(wèn)題分析大學(xué)的每個(gè)專業(yè)都要制定教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限值均相等。每個(gè)專業(yè)開(kāi)設(shè)的課程都是確定的，而且課程在開(kāi)設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒(méi)有。每門課恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序。 需求分析：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號(hào)（可以是固定占 3 位的字母數(shù)字串） 、學(xué)分和直接先修課的課程號(hào)。：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個(gè)學(xué)期中。，則報(bào)告適當(dāng)?shù)男畔ⅲ环駝t將教學(xué)計(jì)劃輸出到用戶指定的文件中。計(jì)劃的表格格式可以自己設(shè)計(jì)。 12，課程總數(shù)不超過(guò) 100。如果輸入的先修課程號(hào)不在該專業(yè)開(kāi)設(shè)的課程序列中，則作為錯(cuò)誤處理。算法分析對(duì)于有向圖，我們采取鄰接表作為數(shù)據(jù)結(jié)構(gòu)。首先確定學(xué)期數(shù)和每學(xué)期的學(xué)分總數(shù)上限，不能一學(xué)期將很多課全部學(xué)完。然后根據(jù)輸入的計(jì)劃課程樹(shù)和輸入的拓?fù)渑判蛩纬傻恼n程先修關(guān)系建立拓?fù)鋱D。在拓?fù)渑判虻倪^(guò)程之中，第 7 頁(yè) 共 36 頁(yè) 7輸入入度為零（即沒(méi)有前趨）的頂點(diǎn)，同時(shí)將該頂點(diǎn)的直接后繼的入度減 1。（1） 、查鄰接表中入度為零的頂點(diǎn)，并進(jìn)棧。（2） 、當(dāng)棧為空時(shí)，進(jìn)行拓?fù)渑判?。（a） 、退棧，輸出棧頂元素 V。（b） 、在鄰接表中查找 Vj 的直接后繼 Vk，將 Vk 的入度減一，并令入度減至零的頂點(diǎn)進(jìn)棧。表節(jié)點(diǎn)（弧結(jié)構(gòu)） ；typedef struct ArcNode{ }ArcNode。頭結(jié)點(diǎn)；typedef struct{}VNode, AdjList[MAX_VERTEX_NUM]。圖結(jié)構(gòu)；typedef struct{}ALGraph。操作結(jié)果: 若 G 中存在頂點(diǎn) u,則返回該頂點(diǎn)在圖中位置。否則返回1 ；int LocateVex(ALGraph G,VertexType u)采用鄰接表存儲(chǔ)結(jié)構(gòu),構(gòu)造沒(méi)有相關(guān)信息的圖 G(用一個(gè)函數(shù)構(gòu)造種圖 )；Status CreateGraph(ALGraph amp。G)輸出圖的鄰接矩陣 G ；void Display(ALGraph G)求頂點(diǎn)的入度；void FindInDegree(ALGraph G,int indegree[])順序棧；typedef struct SqStack{}SqStack。構(gòu)造一個(gè)空棧 S；Status InitStack(SqStack *S)清空棧的操作；void ClearStack(SqStack *S)若棧 S 為空棧，則返回 TRUE，否則返回 FALSE ；Status StackEmpty(SqStack S)若棧不空，則刪除 S 的棧頂元素，用 e 返回其值，并返回 OK；否則返回 ERROR ；Status Pop(SqStack *S,SElemType *e)插入元素 e 為新的棧頂元素；Status Push(SqStack *S,SElemType e)求大學(xué)所有課程總學(xué)分；Status zxf(ALGraph G)程序的核心函數(shù)：Status TopologicalSort(ALGraph G)有向圖 G 采用鄰接表存儲(chǔ)結(jié)構(gòu)，若 G 無(wú)回路,則按用戶選擇的方案輸出 G 的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷?OK, 否則返回 ERROR；第 8 頁(yè) 共 36 頁(yè) 8調(diào)試并運(yùn)行運(yùn)行結(jié)果：使學(xué)習(xí)負(fù)擔(dān)盡量均勻：使課程盡量分布在前幾個(gè)學(xué)期：第 9 頁(yè) 共 36 頁(yè) 9藥品銷售統(tǒng)計(jì)系統(tǒng)（排序應(yīng)用）問(wèn)題分析在本設(shè)計(jì)中，首先從數(shù)據(jù)文件中讀出各藥品的信息記錄，存儲(chǔ)在順序表中。各藥品的信息包括：藥品編號(hào)、藥名、藥品單價(jià)、銷出數(shù)量、銷售額。藥品編號(hào)共 4 位，采用字母和數(shù)字混合編號(hào)，如：A125，前一位為大寫(xiě)字母，后三位為數(shù)字，按藥品編號(hào)進(jìn)行排序時(shí)，可采用基數(shù)排序法。對(duì)各藥品的單價(jià)、銷售量或銷售額進(jìn)行排序時(shí)，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直接選擇排序等方法。在本設(shè)計(jì)中，對(duì)單價(jià)的排序采用冒泡排序法，對(duì)銷售量的排序采用快速排序法，對(duì)銷售額的排序采用堆排序法。算法分析A、拿一個(gè)和后邊的比較如果大，則后移，一趟結(jié)束后最大的放到最后邊了，然后循環(huán)調(diào)用實(shí)現(xiàn)排序。B、快速排序：用兩個(gè)指針 low 和 high 分別指向頭和尾，首先以頭元素為軸，如果 high 大于軸元素，high，否則把 high 指針指向的元素賦給 low，然后 low++，如果 low 指向的元素小于軸 low++，反之把 low 指向的元素賦給high，依次遞歸調(diào)用實(shí)現(xiàn)快速排序。C、基數(shù)排序：基數(shù)排序是借助