數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) (

一、設(shè)計(jì)目的

1.1問題描述：

任意給定一個(gè)M進(jìn)制的數(shù)x，請(qǐng)實(shí)現(xiàn)如下要求：

１、對(duì)給字一個(gè)M進(jìn)制的數(shù)據(jù)x，求出此數(shù)x的10進(jìn)制值(用MD表示)；２、實(shí)現(xiàn)對(duì)x向任意的一個(gè)非M進(jìn)制的數(shù)的轉(zhuǎn)換；

1.2問題分析：

１、用串實(shí)現(xiàn)該問題：

⑴m,n,x是定義的全局變量；

⑵Loop循環(huán)是實(shí)現(xiàn)M進(jìn)制數(shù)轉(zhuǎn)換為10進(jìn)制；

⑶trans()是實(shí)現(xiàn)10進(jìn)制數(shù)轉(zhuǎn)換為n進(jìn)制數(shù)的函數(shù);(4)voidmain()是主函數(shù)，功能是給出測(cè)試的數(shù)據(jù)，并在特定條件下調(diào)用trans()

函數(shù)。

２、用棧實(shí)現(xiàn)該問題：

⑴SeqStack定義棧，top為棧頂指針；

⑵intInitStack(SqStack&S)到voidClearStack(SqStack&S)六大模塊分別表

示構(gòu)造一個(gè)空棧、判斷棧是否為空、判斷棧是否為滿、進(jìn)棧、出棧、摧毀棧；⑶SeqStackS是指定義棧S；

⑷for()循環(huán)和while()循環(huán)的功能是將M進(jìn)制數(shù)轉(zhuǎn)換成10進(jìn)制數(shù)；

⑸do...while實(shí)現(xiàn)輸入轉(zhuǎn)換合理的進(jìn)制，第二個(gè)while（）是把之前轉(zhuǎn)換的10進(jìn)

制值壓入棧，第三個(gè)while()循環(huán)是轉(zhuǎn)換后的出棧輸出；

⑹voidmain()是主函數(shù)。其功能是輸入需要測(cè)試的數(shù)據(jù)以及需要轉(zhuǎn)換的進(jìn)制，實(shí)

現(xiàn)M進(jìn)制數(shù)向任意非M進(jìn)制數(shù)的轉(zhuǎn)換。

二、設(shè)計(jì)過程

2.1方案確定：

在數(shù)組和棧實(shí)現(xiàn)時(shí)，利用for（）循環(huán)和while()循環(huán)以及調(diào)用進(jìn)制間的轉(zhuǎn)換函數(shù)和輸出函數(shù)，使M進(jìn)制先轉(zhuǎn)換成十進(jìn)制在轉(zhuǎn)換成非M進(jìn)制。2.2程序設(shè)計(jì)模塊設(shè)計(jì)連接圖

需要轉(zhuǎn)換M進(jìn)制數(shù)模塊串實(shí)現(xiàn)模塊棧實(shí)現(xiàn)模塊10進(jìn)制值輸出模塊10進(jìn)制值輸出模塊非M進(jìn)制轉(zhuǎn)換模塊1非M進(jìn)制轉(zhuǎn)換模塊2

2.3重點(diǎn)模塊功能描述：

1.串實(shí)現(xiàn)模塊：把M進(jìn)制數(shù)x存入串中。2.棧實(shí)現(xiàn)模塊：把M進(jìn)制數(shù)x存入棧中。3.非M進(jìn)制轉(zhuǎn)換模塊1,運(yùn)用串實(shí)現(xiàn)轉(zhuǎn)換。4.非M進(jìn)制轉(zhuǎn)換模塊2,運(yùn)用棧實(shí)現(xiàn)轉(zhuǎn)換。

2.4方法設(shè)計(jì):

程序運(yùn)用串和棧實(shí)現(xiàn)數(shù)組之間的轉(zhuǎn)換。把M進(jìn)制的數(shù)x的各位分別存入串和鏈棧中，運(yùn)用數(shù)組的讀入讀出和棧的出棧和入棧算法，讓程序更加人性化的實(shí)現(xiàn)任意數(shù)制之間的轉(zhuǎn)換，在運(yùn)用函數(shù)調(diào)用模塊的連接，輸出轉(zhuǎn)換成10進(jìn)制的值和非M進(jìn)制的值。2.5程序流程圖

開始串棧輸入需要轉(zhuǎn)換的進(jìn)制和數(shù)10進(jìn)制值輸出輸入要轉(zhuǎn)換到的進(jìn)制N轉(zhuǎn)換后輸出

串轉(zhuǎn)換：

#include#include

//輸入十進(jìn)制數(shù)N和轉(zhuǎn)化的進(jìn)制數(shù)Mvoidtrans(intn,intm){charstr[100];inti;for(i=0;n>0;i++)

{if(n%m0;n--){printf("%c",str[n-1]);}}

voidmain()

{intm,n,x;charch;

printf("geidingjingzhiM---");scanf("%d",&m);loop:

printf("geidingyige%djinzhideshuX---",m);fflush(stdin);//一個(gè)M進(jìn)制的數(shù)X轉(zhuǎn)10進(jìn)制for(x=0;;){ch=getchar();

if(ch>="0"&&ch="a"&&ch="A"&&ch=m){gotoloop;}x=x*m+n;}

printf("zhuanhuacheng10jinzhideshuwei---%d\\n",x);printf("geidingyaozhuanhuachengdejinzhiN---");scanf("%d",&m);

printf("zhuanhuacheng%djinzhihoudejieguo---",m);trans(x,m);printf("\\n");}

棧轉(zhuǎn)換：

#include#include#defineStack_Size20typedefintElemType;//順序棧存儲(chǔ)類型typedefstruct

{ElemTypeelem[Stack_Size];inttop;}SeqStack;

//初始化：為未初始化的順序棧S設(shè)置棧頂指針voidInitStack(SeqStack*S)

{S->top=-1;printf("kongzhanS=()\\n");}//判空棧：判斷棧S是否為空棧intIsEmpty(SeqStack*S)

{if(S->top==-1)return1;elsereturn0;}//判棧滿：判斷棧S是否為滿棧intIsFull(SeqStack*S)

{if(S->top==Stack_Size-1)return1;elsereturn0;}//進(jìn)棧：向S棧頂壓入一個(gè)數(shù)據(jù)元素intPush(SeqStack*S,ElemTypex){if(IsFull(S))return0;S->top++;S->elem[S->top]=x;return1;}//出棧：彈出S的棧頂元素，并用x返回intPop(SeqStack*S,ElemType*x){

if(IsEmpty(S))return0;*x=S->elem[S->top];S->top--;return1;}

//銷毀棧S

voidClearStack(SeqStack*S)

{free(S);printf("zhanxiaohui\\n");}

voidmain()

{charx[20];intMx;intM;

intm;intX=0;intt;inti,length;

SeqStack*S=(SeqStack*)malloc(sizeof(SeqStack));InitStack(S);

printf("qingshurujinzhiheshu:");scanf("%d,%s",&Mx,x);t=1;

length=strlen(x);

for(i=0;i="a"&&x[i]=10)printf("%c","a"+m-10);elseprintf("%d",m);}

printf("\\n");ClearStack(S);}

三、運(yùn)行結(jié)果

1、2進(jìn)制的111的10進(jìn)制值，轉(zhuǎn)換成3進(jìn)制的測(cè)試情況如下（棧實(shí)現(xiàn)）：

2、7進(jìn)制的236的10進(jìn)制值，轉(zhuǎn)換成9進(jìn)制的測(cè)試情況如下（串實(shí)現(xiàn)）：

四、總結(jié)與展望

在這次課程設(shè)計(jì)中使我們明白在碰到一個(gè)大的程序，不知道該如何下手時(shí)，只有找多方面的資料，加強(qiáng)思考能力。做這次數(shù)制轉(zhuǎn)換的課程設(shè)計(jì)是我知道了只有在細(xì)節(jié)方面需要熟練運(yùn)用棧、數(shù)組、串，這樣才可以。

通過這次課程設(shè)計(jì)使我懂得了理論與實(shí)際相結(jié)合是很重要的，只有理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識(shí)與實(shí)踐相結(jié)合起來，從理論中得出結(jié)論，才是真正的知識(shí)，才能提高自己的實(shí)際動(dòng)手能力和獨(dú)立思考的能力。通過課程設(shè)計(jì)的訓(xùn)練，我進(jìn)一步學(xué)習(xí)和掌握了對(duì)程序的設(shè)計(jì)和編寫，從中體會(huì)到了數(shù)據(jù)結(jié)構(gòu)的方便和巧妙。

擴(kuò)展閱讀：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告

目錄

1.單位員工通訊錄管理系統(tǒng)（線性表的應(yīng)用）*********************22.停車場(chǎng)管理（棧和隊(duì)列的應(yīng)用）*******************************43.哈夫曼編碼/譯碼系統(tǒng)（樹應(yīng)用）******************************64.教學(xué)計(jì)劃編制問題（圖的應(yīng)用）*******************************85.藥店的藥品銷售統(tǒng)計(jì)系統(tǒng)（排序應(yīng)用**************************116.最小生成樹問題（**）**************************************137．總結(jié)*******************************************************158．源代碼*****************************************************1、單位員工通訊錄管理系統(tǒng)（線性表的應(yīng)用）

[需求分析]

為某個(gè)單位建立一個(gè)員工通訊錄管理系統(tǒng)，可以方便查詢每一個(gè)員工的辦公室電話、手機(jī)號(hào)、及電子郵箱。其功能包括通訊錄鏈表的建立、員工通訊信息的查詢、修改、插入與刪除、以及整個(gè)通訊錄表的輸出。[問題分析]

為建立單位員工通訊錄系統(tǒng)，首先要實(shí)現(xiàn)員工信息的錄入、保存等基本操作。對(duì)于員工通訊錄我們要存入要求的員工的各種信息等，對(duì)于已經(jīng)保存的信息，我們要可以對(duì)這些信息進(jìn)行查詢、修改、插入新信息、刪除信息、還有可以直接輸出整個(gè)所有員工信息等。而這些操作對(duì)于我們來說都是對(duì)建立的鏈表的基本操作，對(duì)于本次試驗(yàn)我采用單向線性鏈表。[算法設(shè)計(jì)]

首先我們要進(jìn)行最基本的操作，即建立鏈表。鏈表的節(jié)點(diǎn)信息保存的有員工編號(hào)、員工姓名、辦公室電話號(hào)碼、手機(jī)號(hào)碼、員工郵箱這些信息。而鏈表的結(jié)點(diǎn)信息保存的有員工信息以及其指針域。然后我們可以添加員工信息，對(duì)于新的員工信息我們將其添加在鏈表的表尾，在添加之前我們要進(jìn)行一項(xiàng)操作，即遍歷鏈表找到其尾指針，然后開辟一個(gè)結(jié)點(diǎn)并將其加到鏈尾。我們還可以進(jìn)行員工信息的查詢操作，在進(jìn)行查詢時(shí)我們首先要遍歷鏈表，然后在遍歷的同時(shí)與關(guān)鍵字進(jìn)行比較從而找到員工信息并輸出。員工信息刪除操作，此操作首先要找到要?jiǎng)h除的員工信息，然后將此節(jié)點(diǎn)的前一節(jié)點(diǎn)的后續(xù)指針直接指向要?jiǎng)h除的結(jié)點(diǎn)的后續(xù)指針，并且釋放要?jiǎng)h除的結(jié)點(diǎn)空間即可。員工信息修改，首先找到要修改的員工，然后輸入要修改的員工信息，將輸入信息直接覆蓋在原有信息上即可。員工信息輸出，遍歷整個(gè)鏈表并輸出。

流程圖如下：

1.2.3.4.5.員工信息查詢員工信息插入員工信息修改員工信息刪除員工信息輸出2

開始建立員工信息鏈表

中項(xiàng)

結(jié)束所有操作或者返回重新選擇操作1.2.3.4.5

[調(diào)試分析及測(cè)試數(shù)據(jù)]

員工信息插入：

員工信息查詢：

員工信息刪除：

員工信息修改：

2、停車場(chǎng)管理（棧和隊(duì)列的應(yīng)用）

[需求分析]

設(shè)停車場(chǎng)是一個(gè)可以停放n輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次有北向南排列（大門在最

南端，最先到達(dá)的第一車停放在車場(chǎng)的最北端），若車場(chǎng)內(nèi)已停滿n輛車，那么后來的車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在它之后進(jìn)入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入車場(chǎng)，每輛停放在車場(chǎng)的車在它離開停車場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序。[問題分析]

停車場(chǎng)停車系統(tǒng)，首先來的車輛要進(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)。[算法設(shè)計(jì)]

此算法用到了棧和隊(duì)列，在棧中保存停車場(chǎng)車輛，在隊(duì)列中保存便道中車輛，本實(shí)驗(yàn)要定義一個(gè)隊(duì)列兩個(gè)棧，其中一個(gè)�？梢暂o助停車場(chǎng)中的車輛離開，即離開一輛車時(shí)，在此車前面的車依次進(jìn)入輔助棧，離開后這些車輛再進(jìn)入停車棧，然后判斷隊(duì)列中是否有車，如果有則將便道隊(duì)列中的車輛移進(jìn)停車廠。否則不進(jìn)行操作。本實(shí)驗(yàn)主要運(yùn)用的就是對(duì)棧和隊(duì)列的基本操作。流程圖如下：

[調(diào)試分析及測(cè)試數(shù)據(jù)]

結(jié)束1.進(jìn)車2.出車初始化棧和隊(duì)列可以反復(fù)選擇進(jìn)行重復(fù)操作開始

3、哈夫曼編碼/譯碼系統(tǒng)（樹應(yīng)用）

[需求分析]

利用哈夫曼編碼進(jìn)行通信，可以壓縮通信的數(shù)據(jù)量，提高傳輸效率，縮短信息的傳輸時(shí)間，還有一定的保密性�，F(xiàn)在要求編寫一程序模擬傳輸過程，實(shí)現(xiàn)在發(fā)送前將要發(fā)送的字符信息進(jìn)行編碼，然后進(jìn)行發(fā)送，接收后將傳來的數(shù)據(jù)進(jìn)行譯碼，即將信息還原成發(fā)送前的字符信息。[問題分析]

在本例中設(shè)置發(fā)送者和接受者兩個(gè)功能，發(fā)送者的功能包括：①輸入待傳送的字符信息；

②統(tǒng)計(jì)字符信息中出現(xiàn)的字符種類數(shù)和各字符出現(xiàn)的次數(shù)（頻率）；②根據(jù)字符的種類數(shù)和各自出現(xiàn)的次數(shù)建立哈夫曼樹；③利用以上哈夫曼樹求出各字符的哈夫曼編碼；④將字符信息轉(zhuǎn)換成對(duì)應(yīng)的編碼信息進(jìn)行傳送。接受者的功能包括：

①接收發(fā)送者傳送來的編碼信息；

②利用上述哈夫曼樹對(duì)編碼信息進(jìn)行翻譯，即將編碼信息還原成發(fā)送前的字符信

息。

從以上分析可發(fā)現(xiàn)，在本例中的主要算法有三個(gè)：（1）哈夫曼樹的建立；（2）哈夫曼編碼的生成；（3）對(duì)編碼信息的翻譯。

本實(shí)驗(yàn)首先從文件中讀取數(shù)據(jù)，然后分析數(shù)據(jù)，對(duì)不同的元素依次存入一字符數(shù)組并統(tǒng)計(jì)其出現(xiàn)的次數(shù)并當(dāng)做其權(quán)值，然后根據(jù)這些信息建立哈弗曼樹，并對(duì)各個(gè)字符進(jìn)行哈弗曼編碼，然后根據(jù)各個(gè)字符的編碼對(duì)所有輸入的一組字符進(jìn)行哈弗曼編碼。譯碼是根據(jù)哈弗曼樹和接收到的一組編碼進(jìn)行譯碼操作。譯碼也就是對(duì)哈弗曼樹的遍歷。[算法設(shè)計(jì)]

首先讀入一組字符，然后統(tǒng)計(jì)這些字符中不同字符出現(xiàn)的次數(shù)，并當(dāng)做其權(quán)值，然后根據(jù)不同字符及其權(quán)值建立哈弗曼樹。建立哈弗曼樹后即可得到這些不同字符的哈弗曼編碼，然后即可根據(jù)這些哈弗曼編碼對(duì)那組輸入的一串字符進(jìn)行哈弗曼編碼。譯碼是根據(jù)一組編碼翻譯成一組字符的操作，其算法就是根據(jù)這一串編碼來對(duì)哈弗曼樹進(jìn)行遍歷，每遍歷到一個(gè)葉子結(jié)點(diǎn)即輸出一個(gè)字符，直至將編碼操作完即可完成多編碼的翻譯操作。[調(diào)試分析及測(cè)試數(shù)據(jù)]

4、教學(xué)計(jì)劃編制問題（圖的應(yīng)用）

[需求分析]

大學(xué)的每個(gè)專業(yè)都要制定教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限值均相等。每個(gè)專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個(gè)學(xué)期。試在這

樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序。

1、輸入?yún)��?shù)應(yīng)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號(hào)（可以是固定占3位的字母數(shù)字串）、學(xué)分和直接先修課的課程號(hào)。2、應(yīng)允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個(gè)學(xué)期中。

3、若根據(jù)給定的條件問題無解，則報(bào)告適當(dāng)?shù)男畔�；否則將教學(xué)計(jì)劃輸出到用戶指定的文件中。計(jì)劃的表格格式可以自己設(shè)計(jì)。

4、可設(shè)學(xué)期總數(shù)不超過12，課程總數(shù)不超過100。如果輸入的先修課程號(hào)不在該專業(yè)開設(shè)的課程序列中，則作為錯(cuò)誤處理。

[問題分析]

編制教學(xué)計(jì)劃，當(dāng)然涉及到的課程都要給學(xué)完。所以我們可以將所以的課程編制成一張圖，然后遍歷圖。由于課程有前續(xù)后繼的關(guān)系，所以用AOV網(wǎng)是最合適。對(duì)AOV網(wǎng)進(jìn)行拓?fù)渑判蚣纯梢缘贸鼋Y(jié)果。對(duì)AOV網(wǎng)進(jìn)行拓?fù)渑判蛴袃煞N情況：廣度優(yōu)先和深度優(yōu)先。在進(jìn)行深度優(yōu)先周游時(shí)，我們要考慮到一種情況。例如：高等數(shù)學(xué)和C語言編程是并列的兩門學(xué)科，他們之間沒有前續(xù)后繼的關(guān)系，可以同時(shí)進(jìn)行學(xué)習(xí)。高等數(shù)學(xué)是數(shù)值分析和電子電路的基礎(chǔ)課程，電子電路又是模擬電子電路的基礎(chǔ)課程。C語言編程是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)課程，數(shù)據(jù)結(jié)構(gòu)是算法設(shè)計(jì)與分析的基礎(chǔ)課程。如果按照深度優(yōu)先周游的話就有可能將上面幾門課程排成：C語言程序設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)，算法設(shè)計(jì)與分析，高等數(shù)學(xué)，電子電路，模擬電子電路。這樣的教學(xué)計(jì)劃很明顯不符合實(shí)際教學(xué)的需要。因此我們應(yīng)該進(jìn)行廣度優(yōu)先周游，將高等數(shù)學(xué)和C語言程序設(shè)計(jì)先學(xué)，再學(xué)其他后繼課程。[算法設(shè)計(jì)]

首先確定學(xué)期數(shù)和每學(xué)期的學(xué)分總數(shù)上限，不能一學(xué)期將很多課全部學(xué)完。然后根據(jù)輸入的計(jì)劃課程樹和輸入的拓?fù)渑判蛩�形成的課程先修關(guān)系建立拓?fù)鋱D。有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)。若G無回路,則輸出G的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷豋K，否則返回ERROR。[調(diào)試分析及測(cè)試數(shù)據(jù)]

5、藥店的藥品銷售統(tǒng)計(jì)系統(tǒng)（排序應(yīng)用）

[需求分析]

設(shè)計(jì)一系統(tǒng)，實(shí)現(xiàn)醫(yī)藥公司定期對(duì)銷售各藥品的記錄進(jìn)行統(tǒng)計(jì)，可按藥品的編號(hào)、單價(jià)、銷售量或銷售額做出排名。[問題分析]

在本設(shè)計(jì)中，首先從數(shù)據(jù)文件中讀出各藥品的信息記錄，存儲(chǔ)在順序表中。各藥品的信息包括：藥品編號(hào)、藥名、藥品單價(jià)、銷出數(shù)量、銷售額。藥品編號(hào)共4位，采用字母和數(shù)字混合編號(hào)，如：A125，前一位為大寫字母，后三位為

數(shù)字，按藥品編號(hào)進(jìn)行排序時(shí)，可采用基數(shù)排序法。對(duì)各藥品的單價(jià)、銷售量或銷售額進(jìn)行排序時(shí)，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直接選擇排序等方法。在本設(shè)計(jì)中，對(duì)單價(jià)的排序采用冒泡排序法，對(duì)銷售量的排序采用快速排序法，對(duì)銷售額的排序采用堆排序法。[算法設(shè)計(jì)]

首先從txt文件中讀取數(shù)據(jù)信息并保存，本次試驗(yàn)采用了5中排序方法。其中編號(hào)排序是按照基數(shù)排序，采用多關(guān)鍵字進(jìn)行排序�；鶖�(shù)排序是借助“分配”和“收集”兩種操作對(duì)單邏輯關(guān)鍵字進(jìn)行排序的一種內(nèi)部排序方法。對(duì)單價(jià)的排序采用了直接插入排序和冒泡排序，直接插入排序就是首先將第一個(gè)元素看成是一個(gè)有序的，然后第二個(gè)元素和第一個(gè)比較，若大于第一個(gè)則放在其后面否則放前面，依次直至最后一個(gè)。冒泡排序就是采用兩個(gè)循環(huán)，即將第一個(gè)元素和第二個(gè)比較若第一個(gè)大于第二個(gè)則交換，否則不變，然后第二個(gè)和第三個(gè)比較，同上。第一趟可將最大的一個(gè)放在最后，依次可得排序。銷售量是快速排序，快速排序就是首先設(shè)置一個(gè)關(guān)鍵字，然后讓最后一個(gè)和其比較，直至找到一個(gè)比關(guān)鍵字小的，然后和其交換，接下來讓第一個(gè)和其比較，直至找到一個(gè)比其大的，然后交換，在找到的位置分別做標(biāo)記，依次執(zhí)行即可。銷售額使用的是堆排序，堆排序首先要建立一個(gè)完全二叉樹的堆，其標(biāo)準(zhǔn)符合為父節(jié)點(diǎn)始終比子節(jié)點(diǎn)大。然后依次輸出頂結(jié)點(diǎn)，然后在建立一個(gè)符合標(biāo)準(zhǔn)的堆重復(fù)操作即可。[調(diào)試分析及測(cè)試數(shù)據(jù)]

6、最小生成樹問題（**）

【需求分析】

若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要假設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問題。[問題分析]

利用克魯斯卡爾算法求網(wǎng)的最小生成樹。利用普里姆算法求網(wǎng)的最小生成樹。要求輸出各條邊及它們的權(quán)值。通信線路一旦建成，必然是雙向的。因此，構(gòu)造最小生成樹的網(wǎng)一定是無向網(wǎng)。設(shè)圖的頂點(diǎn)數(shù)不超過30個(gè)，并為簡(jiǎn)單起見，網(wǎng)中邊的權(quán)值設(shè)成小于100的整數(shù)，可利用C語言提供的隨機(jī)函數(shù)產(chǎn)生。圖的存儲(chǔ)結(jié)構(gòu)的選取應(yīng)和所作操作相適應(yīng)。為了便于選擇權(quán)值最小的邊，此題的存儲(chǔ)結(jié)構(gòu)既不選用鄰接矩陣的數(shù)組表示法，也不選用鄰接表，而是以存儲(chǔ)邊（帶權(quán)）的數(shù)組表示圖。

[算法設(shè)計(jì)]

Kruskal算法要選擇n-1條邊，所使用的貪婪準(zhǔn)則是：從剩下的邊中選擇一條不會(huì)產(chǎn)生環(huán)路的具有最小耗費(fèi)的邊加入已選擇的邊的集合中。注意到所選取的邊若產(chǎn)生環(huán)路則不可能形成一棵生成樹。Kruskal算法分e步，其中e是網(wǎng)絡(luò)中邊的數(shù)目。按耗費(fèi)遞增的順序來考慮這e條邊，每次考慮一條邊。當(dāng)考慮某條邊時(shí)，若將其加入到已選邊的集合中會(huì)出現(xiàn)環(huán)路，則將其拋棄，否則，將它選入。Prim首先任意選取一個(gè)頂點(diǎn)放入到最小生成樹中去，然后分別在最小生成樹的內(nèi)外各選取一個(gè)定點(diǎn)頂點(diǎn)，要求這兩個(gè)頂點(diǎn)之間的權(quán)重是最小的。然后將最小生成樹外的這個(gè)頂點(diǎn)加入到最小生成樹中去，而這條邊就做為最小生成樹的一條邊。重復(fù)以上操作，最后將頂點(diǎn)全部包含在最小生成樹之中為止

[調(diào)試分析及測(cè)試數(shù)據(jù)]

[總結(jié)]

做了兩個(gè)星期的程序設(shè)計(jì)終于做完了，在這次程序設(shè)計(jì)課中，真是讓我獲益匪淺，我突然發(fā)現(xiàn)寫程序還挺有意思的。

由于上學(xué)期的C++語言跟這學(xué)期的數(shù)據(jù)結(jié)構(gòu)都算不上真正的懂，對(duì)于書上的稍微難點(diǎn)的知識(shí)就是是而非的，所以我只是對(duì)老師的程序理解，我也試著去改變了一些變量，自己也盡量多的去理解老師做程序的思路。當(dāng)我第一天坐在那里的時(shí)候，我就不知道該做些什么，后來我只有下來自己看了一遍書來熟悉下以前學(xué)過的知識(shí)。

通過這次的程序設(shè)計(jì)，發(fā)現(xiàn)一個(gè)程序設(shè)計(jì)就是算法與數(shù)據(jù)結(jié)構(gòu)的結(jié)合體，自己也開始對(duì)程序產(chǎn)生了前所未有的興趣，以前偷工減料的學(xué)習(xí)也不可能一下子寫出一個(gè)程序出來，于是我就認(rèn)真看老師寫的程序，發(fā)現(xiàn)我們看懂了一個(gè)程序其實(shí)不難，難的是對(duì)于一個(gè)程序的思想的理解，我們要掌握一個(gè)算法，不僅僅限于讀懂，主要的是要理解老師的思路，學(xué)習(xí)老師的解決問題的方法。

這次試驗(yàn)中，我發(fā)現(xiàn)書本上的知識(shí)是一個(gè)基礎(chǔ)，但是我基礎(chǔ)都沒掌握，更別說寫出一個(gè)整整的程序了。自己在寫程序的時(shí)候，也發(fā)現(xiàn)自己的知識(shí)太少了，特別是基礎(chǔ)知識(shí)很多都是模模糊糊的一個(gè)概念，沒有落實(shí)到真正的程序，所以自

己寫的時(shí)候也感到萬分痛苦，基本上涉及一個(gè)知識(shí)我就會(huì)去看看書，對(duì)于書本上的知識(shí)沒掌握好。在飯后閑暇時(shí)間我也總結(jié)了一下，自己以前上課也認(rèn)真的聽了，但是還是寫不出來，這主要?dú)w結(jié)于自己的練習(xí)太少了，而且也總是半懂就不管了。在改寫老師的程序中也出現(xiàn)了很多的問題，不斷的修改就是不斷的學(xué)習(xí)過程，當(dāng)我們?nèi)�身心的投入其中時(shí)，實(shí)際上是一件很有樂趣的事情。對(duì)于以后的學(xué)習(xí)有了幾點(diǎn)總結(jié)：第一、熟記各種數(shù)據(jù)結(jié)構(gòu)類型，定義、特點(diǎn)、基本運(yùn)算（分開點(diǎn)一點(diǎn)也沒多少東西，難度不大，但是基本）；第二、各種常用的排序算法，如冒泡排序、堆排序……，這些是必考的內(nèi)容，分?jǐn)?shù)不會(huì)少于20%；第三，多做習(xí)題，看題型，針對(duì)題型來有選擇復(fù)習(xí)；數(shù)據(jù)結(jié)構(gòu)看上去很復(fù)雜，但你靜下心來把書掃上幾遍，分解各個(gè)知識(shí)點(diǎn)，這一下來，學(xué)數(shù)據(jù)結(jié)構(gòu)的思路就會(huì)很清晰了。

1.

#include#includeusing

namespacestd;typedefstruct{/*員工通訊信息的結(jié)構(gòu)類型定義*/char

num[20];/*員工編號(hào)*/charname[20];/*員工姓名*/charphone[20];/*辦公室電話號(hào)碼*/charcall[20];/*手機(jī)號(hào)碼*/charemail[20];//員工郵

箱}DataType;/*通訊錄單鏈表的結(jié)點(diǎn)類型*/typedefstructnode

{DataTypedata;/*結(jié)點(diǎn)的數(shù)據(jù)域*/

structnode*next;/*結(jié)點(diǎn)的指針域

*/}ListNode,*LinkList;LinkListlist=newListNode;voidchushihua(LinkListlist){ListNode*p=newListNode;strcpy(p->data.call,"15011111111");

strcpy(p->data.email,"1@163.com");

strcpy(p->data.name,"lvdezhou");

strcpy(p->data.num,"201*1");

strcpy(p->data.phone,"1314111");

list->next=p;p->next=NULL;vo

aa=list->next;coutbh;

do{if(!(strcmp(bh,aa->data.num))){

cout}while(aa->next!=NULL,aa=aa->next);}void

yuangongxinxicharu(LinkListlist){

ListNode*w;w=list->next;while(w->next!=N

ULL)

{

w=w->next;}

ListNode*u=newListNode;

u->next=NULL;

coutu->data.call;coutu->data.email;coutu->data.name;coutu->data.num;coutu->data.phone;w->next=u;w=w->

next;}

voidshanchu(LinkListlist){

ListNode*cz1;ListNode*cz2;ListNode*cz3;cz1=list;

cz2=list;

ints=0;

charchax[20];

coutchax;

while((strcmp(chax,cz1->data.num))){

s++;cz1=cz1->next;

}

for(intj=0;jnext;

}

cz3=cz2->next;cz2->next=cz3->next;}

voidxiugai(LinkListlist){

ListNode*xiug;

ListNode*zans;zans=list->next;

coutbh;

do{if(!(strcmp(bh,zans->data.num))){

xiug=newListNode;

coutvoidjiemian(LinkListlist){

intxuhao=0;

coutcout>chu;

S.top--;

while(strcmp(S.top->name,chu)){

*(q.top)=*(S.top);q.top++;

S.top--;}

coutSqStackq;//備用棧，用來輔助車的進(jìn)出//便道用隊(duì)列進(jìn)行操作，假設(shè)停車每天不超過輛

}HTNode,*HuffmanTree;

HuffmanTreep;inti;

typedefchar**HuffmanCode;

voidtongji(char*d1,intfor(p=HT+1,i=1;irchild=0;

p->weight=*w;}

for(;ilchild=p->parent=p->rchild=0;

p->weight=0;

}

for(i=n+1;iif(HT[t].parent==0&&t!=s1){s2=t;break;}

for(t=t+1;tHT[t].weight&&HT[t].parent==0&&t!=s1)

s2=t;

}

HT[s1].parent=i;HT[s2].parent=i;

HT[i].lchild=s1;HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight;}HC=newchar*[n+1];char*cd=newchar[n];

cd[n-1]="\\0";intstart,c,f;for(i=1;i

HuffmanCoding(HT,HC,w,n,d);

cout/*圖的鄰接表存儲(chǔ)的基本操作*/int

LocateVex(ALGraphG,VertexTypeu)

{/*初始條件:圖G存在,u和G中頂點(diǎn)有相同特征*/

/*操作結(jié)果:若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中位置;否則返回-1*/

inti;

for(i=0;i

{p=G.vertices[i].firstarc;

while(p){printf("%s→%s",G.vertices[i].data,G.vertices[p->adjvex].data);#define

STACK_INIT_SIZE10/*存儲(chǔ)空間初始分配量*/#define

STACKINCREMENT2/*存儲(chǔ)空間分配增量*/

typedefstructSqStackvoid

ClearStack(SqStack*S)//清空棧的操作

{S->top=S->base;}Status

StackEmpty(SqStackS)

p=p->nextarc;}printf("\\n");}}void

FindInDegree(ALGraphG,intindegree[])

{/*求頂點(diǎn)的入度，算法調(diào)用*/

inti;ArcNode*p;

for(i=0;inextarc;}}}typedefint

SElemType;/*棧類型*/

/*棧的順序存儲(chǔ)表示*/

{

SElemType*base;/*在棧構(gòu)造之前和銷毀之后，base的值為NULL*/SElemType*top;/*棧頂指針*/

intstacksize;/*當(dāng)前已分配的存儲(chǔ)空間，以元素為單位*/

}SqStack;/*順序棧*/

/*順序棧的基本操作*/

Status

InitStack(SqStack*S)

{/*構(gòu)造一個(gè)空棧S*/

(*S).base=(SElemType

*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!(*S).base)

exit(OVERFLOW);/*存儲(chǔ)分配失敗*/

(*S).top=(*S).base;

(*S).stacksize=STACK_INIT_SIZE;

returnOK;}

{/*若棧S為空棧，則返回TRUE，否則返回FALSE*/

if(S.top==S.base)returnTRUE;else

returnFALSE;}StatusPop(SqStack*S,SElemType*e)

{/*若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR*/

if((*S).top==(*S).base)

returnERROR;*e=*--(*S).top;returnOK;}StatusPush(SqStack*S,SElemTypee)

{/*插入元素e為新的棧頂元素*/

if((*S).top-(*S).base>=(*S).stacksize)/*棧滿，追加存儲(chǔ)空間*/

{(*S).base=(SElemType

*)realloc((*S).base,((*S).stac

ksize+STACKINCREMENT)*sizeof

(SElemType));pathtwob;ArcNode*p;

FindInDegree(G,indegree);/*

for(p=G.vertices[i].firstarc;p;p=p->nextarc)

{/*對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減*/

if(!(*S).base)

exit(OVERFLOW);/*存儲(chǔ)分配失敗*/

(*S).top=(*S).base+(*S).stacksize;

(*S).stacksize+=STACKINCREMENT;}

*((*S).top)++=e;returnOK;}

typedefint

pathone[MAXCLASS];typedefint

pathtwo[MAXCLASS];Status

TopologicalSort(ALGraphG)

{/*有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)。若G無回路,則輸出G的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷豋K,*//*否則返回ERROR。*/

int

i,k,j=0,count,indegree[MAX_VERTEX_NUM];

boolhas=false;SqStackS;pathonea;

對(duì)各頂點(diǎn)求入度

indegree[0..vernum-1]*/InitStack(&S);/*初始化棧*/

for(i=0;iintqq=1;//學(xué)期

數(shù)

intxxf;

while(qqnextarc){/*對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減*/

k=p->adjvex;

indegree[k]--;

/*if(!(--indegree[k]))若入度減為,則入棧

{

Push(&S,k);}*/}

result[rtop]=i;rtop++;

}

cout{DataTyper[20];

intlength;

//couta;

for(inti=0;iif(S.r[i].price>L.r[i-1].price)

{L.r[i]=S.r[i];

}}

for(inte=0;e\\t"if(!f[j])

f[j]=p;

else

r[e[j]].next=p;

e[j]=p;}}}

voidCollect(DataType*r,inti,int*f,int*e)

{intj,t;for(j=0;!f[j];j++);r[0].next=f[j];t=e[j];

while(j#include#include#include#includeusingnamespacestd;//存儲(chǔ)結(jié)點(diǎn)結(jié)構(gòu)structNode{intData1;intData2;

intdis;};

//比較函數(shù)

boolJudgDis(constNode&p1,constNode&p2){returnp1.disData1];cout

友情提示：本文中關(guān)于《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) (》給出的范例僅供您參考拓展思維使用，數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) (：該篇文章建議您自主創(chuàng)作。

來源：網(wǎng)絡(luò)整理 免責(zé)聲明：本文僅限學(xué)習(xí)分享，如產(chǎn)生版權(quán)問題，請(qǐng)聯(lián)系我們及時(shí)刪除。

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) (》由互聯(lián)網(wǎng)用戶整理提供,轉(zhuǎn)載分享請(qǐng)保留原作者信息,謝謝!
鏈接地址：http://www.seogis.com/gongwen/693823.html

• 上一篇：201*UML建模課程設(shè)計(jì)模板
• 下一篇：15.《上海市建筑玻璃幕墻管理辦法》解讀