第一篇：最短路徑_數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告

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

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告

設(shè)計題目：____醫(yī)院選址____________ 姓名：__________________ 學(xué)號：________________ 專業(yè)：___________

院系：____________

班級：_________________ 指導(dǎo)教師：_________________

年 1月 3 日

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

一、問題描述

(1)題目內(nèi)容：有n個村莊，現(xiàn)要從這n個村莊中選擇一個村莊新建一所醫(yī)院，使其余的村莊到這所醫(yī)院的距離總和來說較短。（n>=5）(2)基本要求：

(3)可以輸出每一對點間的路徑長度；然后選取偏心度，最小的偏心度即為所求。

二、需求分析

(4)本程序的功能包括找出每一對點間的路徑長度。(5)然后算出每一對點的偏心度。(6)其中最小的偏心度即為所求。

三、概要設(shè)計

操作集合：

(7)public:MGraph(DataType a[],int b[][MaxSize],int n,int e);//初始化鄰接矩陣和路徑

(8)void Floyd();//弗洛伊德算法的實現(xiàn)(9)void getE();//獲取偏心度

(10)void showdist();//把每一對頂點之間的路徑權(quán)值show出來(11)~MGraph(){} //類的析構(gòu)函數(shù)

四、數(shù)據(jù)結(jié)構(gòu)設(shè)計

(1)DataType vertex[MaxSize];//存放圖中頂點的數(shù)組(2)int

arc[MaxSize][MaxSize];//存放圖中邊的數(shù)組

(3)string path[MaxSize][MaxSize];//存放從Vi到Vj的最短路徑，初始為

//path[i][j]=“ViVj”

(4)int dist[MaxSize][MaxSize];//存放求得的最短路徑長度(5)int vertexNum, arcNum;//圖的頂點數(shù)和邊數(shù)(6)int E[MaxSize][2];//獲取最小偏心度和該頂點

五、算法設(shè)計

1.算法分析

1）對帶權(quán)有向圖的，調(diào)用Floyd算法，對每一對頂點間的最短路徑長度的矩陣；

2）對最短路徑長度矩陣的每列求最大值，即得到各點的偏心度； 3)具有最小偏心度的頂點即為所求。

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

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

2.算法實現(xiàn)

#include #include #include using namespace std;

const int MaxSize = 5;template class MGraph { public:，建立具有n個頂點e條邊的圖

};template MGraph::MGraph(DataType a[], int b[][MaxSize],int n,int e){

} template void MGraph::Floyd(){ int i,j,k;

MGraph(DataType a[], int b[][MaxSize],int n,int e);//構(gòu)造函數(shù)

void Floyd();void getE();void showdist();~MGraph(){} DataType vertex[MaxSize];int arc[MaxSize][MaxSize];int dist[MaxSize][MaxSize];int vertexNum, arcNum;int E[MaxSize][2];

//存放圖中頂點的數(shù)組 //存放圖中邊的數(shù)組 //存放求得的最短路徑長度 //圖的頂點數(shù)和邊數(shù) private:

string path[MaxSize][MaxSize];//存放從Vi到Vj的最短路徑，初始為path[i][j]=“ViVj” vertexNum = n;arcNum = e;for(int i=0;i

} arc[i][j]=b[i][j];dist[i][j]=arc[i][j];

//直接放入鄰接矩陣

for(int j=0;j

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

} for(i=0;i

} for(k=0;k

for(i=0;i

}

//頂點i和j之間是否經(jīng)過頂點k for(j=0;j

} dist[i][j]=dist[i][k]+dist[k][j];path[i][j]=path[i][k]+path[k][j];for(j=0;j

} dist[i][j]=arc[i][j];if(dist[i][j]!=10000)else path[i][j]=“";path[i][j]=vertex[i]+vertex[j];

template void MGraph::showdist(){

} template void MGraph::getE(){

心度。

} for(int i=0;i

}

for(int i=0;i

} for(int j=0;j

“;for(int i=0;i

E[i][0]=i;//存放某一個節(jié)點的序號 E[i][1]=0;//存放節(jié)點的最短路徑，權(quán)值。

int max = dist[0][i];//i表示列；j表示行。for(int j=0;j

if(dist[j][i]>max){ } E[i][1]=max;max = dist[j][i];

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

cout<

} void main(){

代表是無窮。

}

MGraph GM(a,b,5,7);GM.Floyd();GM.showdist();cout<

0,1,10000,10000,10000, 10000,0,2,10000,10000, 10000,10000,0,2,4, 10000,1,3,0,10000, 10000,10000,10000,5,0,};char a[5] = {'A','B','C','D','E'};int b[5][5] = {

//鄰接矩陣,A,B,C,D,E是節(jié)點的信息，代表某一個地點。

//存儲某兩個有向節(jié)點間的權(quán)值，代表路徑長度，10000 int min=E[0][1],k;for(int i=0;i

} cout<<”最佳選址為“<

cout<

if(E[i][1]

} min=E[i][1];k=i;

六、程序測試與實現(xiàn)

1、函數(shù)之間的調(diào)用關(guān)系

Main

Floyd()

showdist()

getE()

2、主程序

void main(){ char a[5] = {'A','B','C','D','E'};

//鄰接矩陣,A,B...是節(jié)點的信息，代表某一個地點。

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

int b[5][5] = { //存儲某兩個有向節(jié)點間的權(quán)值，代表路徑長度，10000代表是無窮。

0,1,10000,10000,10000, 10000,0,2,10000,10000, 10000,10000,0,2,4, 10000,1,3,0,10000, 10000,10000,10000,5,0,};

MGraph GM(a,b,5,7);

}

GM.Floyd();

GM.showdist();

cout<

GM.getE();

3、測試數(shù)據(jù)

int b[5][5] = { //存儲某兩個有向節(jié)點間的權(quán)值，代表路徑長度，10000代表是無窮。

0,1,10000,10000,10000, 10000,0,2,10000,10000, 10000,10000,0,2,4, 10000,1,3,0,10000, 10000,10000,10000,5,0,};

4、測試結(jié)果

七、調(diào)試分析

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

1．在算偏心度的時候；每一列的最大值算錯了，下次要注意。

在show的時候也把行和列搞反了；所以以為結(jié)果不對其是對的。2．算法的時空分析：(1)時間復(fù)雜度:O(n^3)；(2)空間復(fù)雜度:O(n^2)[1]

八、遇到的問題及解決辦法

1）在算偏心度的時候；每一列的最大值算錯了，下次要注意。

解決辦法：是把行變，列不變。

2)在show的時候也把行和列搞反了；所以以為結(jié)果不對其是對的。

解決辦法：把行和列反一下就好。

九、心得體會

Floyd算法的基本思想如下：從任意節(jié)點A到任意節(jié)點B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經(jīng)過若干個節(jié)點X到B。所以，我們假設(shè)Dis(AB)為節(jié)點A到節(jié)點B的最短路徑的距離，對于每一個節(jié)點X，我們檢查Dis(AX)+ Dis(XB)< Dis(AB)是否成立，如果成立，證明從A到X再到B的路徑比A直接到B的路徑短，我們便設(shè)置Dis(AB)= Dis(AX)+ Dis(XB)，這樣一來，當(dāng)我們遍歷完所有節(jié)點X，Dis(AB)中記錄的便是A到B的最短路徑的距離。通過這個學(xué)習(xí)；把Floyd算法搞懂了；模板也熟練了許多。

第二篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 關(guān)鍵路徑的實現(xiàn)

青島理工大學(xué)

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

題目： 關(guān)鍵路徑的實現(xiàn)

院（系）：

計算機工程學(xué)院

學(xué)生姓名:

班級： 學(xué)號:

起迄日期:

2014.7.8—2014.7.19

指導(dǎo)教師:

張艷

一、需求分析

1.問題描述

找出實際工程中的關(guān)鍵路徑，合理安排關(guān)鍵活動的施工順序。要求：

(1)表示工程的圖可以用鄰接表或鄰接矩陣存儲；(2)應(yīng)能以圖形的方式輸出圖；(3)輸出關(guān)鍵路徑和關(guān)鍵活動。2.基本功能

(1)用鄰接表存儲有向圖并建立AOE網(wǎng)

CreateGraph（）；

(2)用圖形的形式輸出有向圖Display();

(3)輸出關(guān)鍵路徑和關(guān)鍵活動 SearchMapPath（）；

3.輸入輸出

輸入:(1)有向圖的頂點數(shù)和弧數(shù)，都是int型，中間用空格隔開；

(2)圖中的各個頂點的值，char型;(3)圖中弧的權(quán)值、起點、終點,都是int型，中間用空格隔開；

輸出： 起點（char）、終點(char)、最早開始時間(int)、最遲開始時間(int)、差值(int)、是否為關(guān)鍵活動、關(guān)鍵路徑。

二、概要設(shè)計

1.設(shè)計思路：

(1)輸入圖的頂點數(shù)和弧數(shù)。

(2)輸入這個圖中每段弧的起始點及權(quán)值。

(3)用輸入的數(shù)據(jù)建立AOE網(wǎng)。

(4)用鄰接表來存儲圖的這些信息。

(5)用CreateGraph()函數(shù)建立AOE圖。(6)用Display()函數(shù)輸出AOE圖。

(7)用SearchMapPath()函數(shù)求出最長路徑，并輸出關(guān)鍵路徑。(8)編寫程序。

2.數(shù)據(jù)結(jié)構(gòu)設(shè)計：

（1）邏輯結(jié)構(gòu)采用圖狀的結(jié)構(gòu)。圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中，數(shù)據(jù)元素之間僅有線性關(guān)系，每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼；在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個元素（即其孩子結(jié)點）相關(guān)，但只能和上一層中一個元素（即其雙親結(jié)點）相關(guān)；而在圖形結(jié)構(gòu)中，結(jié)點之間的關(guān)系可以是

任意的，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)。而由于本程序的操作對象是有向圖，所以必須采用圖狀的結(jié)構(gòu)。

（2）存儲結(jié)構(gòu)采用鏈?zhǔn)降慕Y(jié)構(gòu)。由于圖的結(jié)構(gòu)比較復(fù)雜，任意兩個頂點之間都可能存在聯(lián)系，因此無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示元素之間的關(guān)系，即圖沒有順序映象的存儲結(jié)構(gòu)，因此采用鏈?zhǔn)降拇鎯Y(jié)構(gòu)。

（3）抽象數(shù)據(jù)類型圖的定義如下：

ADT Graph{ 數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。

數(shù)據(jù)關(guān)系R：

R={VR} VR={|v,w∈V且P（v,w）,表示從v到w的弧，謂詞P（v,w）定義了弧的意義或信息} 基本操作P：

CreateGraph(&G,V,VR);初始條件：V是圖的頂點集，VR是圖中弧的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖G。SearchMapPath(&G,V,VR)；

初始條件：V是圖的頂點集，VR是圖中弧的集合。操作結(jié)果：求出最長路徑，并輸出關(guān)鍵路徑。Display(&G,V,VR)；

初始條件：V是圖的頂點集，VR是圖中弧的集合。操作結(jié)果：以圖形的形式輸出圖。}ADT Graph

3.軟件結(jié)構(gòu)設(shè)計：

求關(guān)鍵路徑主函數(shù)main()建立AOE網(wǎng)void CreateGraph()顯示有向圖void Display（）計算關(guān)鍵路徑int SearchMapPath()

三、詳細(xì)設(shè)計

1.定義程序中所有用到的數(shù)據(jù)及其數(shù)據(jù)結(jié)構(gòu): 鄰接表的存儲單元: typedef struct node { int adjvex;int w;struct node *nextedge;}edgenode;表頭結(jié)點:

typedef struct { char data;int id;int x,y;//頂點的橫坐標(biāo)、縱坐標(biāo)

edgenode *firstedge;}vexnode;

2．主函數(shù)和其他函數(shù)的偽碼算法: 主函數(shù)：

void main()

{ int vexnumber,arcnumber;

printf(“請輸入這個圖中的節(jié)點數(shù)和弧數(shù):”);

scanf(“%d %d”,&vexnumber,&arcnumber);

vexnode* Graph=(vexnode*)malloc(vexnumber*sizeof(vexnode));CreateGraph(Graph,vexnumber,arcnumber);

SearchMapPath(Graph,vexnumber,arcnumber);}

建立AOE網(wǎng)函數(shù)：

void CreateGraph(vexnode* Graph,int vexnumber,int arcnumber)

{

int begin,end,duttem;

char ch;

edgenode *p;

//輸入頂點信息存儲在頂點表中，并初始化該頂點的便表。

for(int i=0;i

Graph[i].id =0;

Graph[i].firstedge =NULL;

}

//輸入邊所依附的兩個頂點的序號i和j然后生成新的鄰接點序號為j的//邊表結(jié)點,將該結(jié)點插入到第i個表頭部。

printf(“請輸入這個圖中的各個頂點的值:n”);

for(i=0;i

{

scanf(“%s”,&ch);

Graph[i].data=ch;

}

printf(“請輸入圖中弧的權(quán)值、起點、終點:（中間用空格隔開）n”);

for(int k=0;k

{

scanf(“%d %d %d”,&duttem,&begin,&end);

p=(edgenode*)malloc(sizeof(edgenode));

p->adjvex =end-1;

p->w =duttem;

Graph[end-1].id ++;

p->nextedge =Graph[begin-1].firstedge;

Graph[begin-1].firstedge =p;

}

} 顯示有向圖函數(shù)：

void Display(vexnode* Graph,int vexnumber,int arcnumber){

int i;int arw[6];edgenode *p;initgraph(400, 600);for(i=0;i

if(i%3==0||i==0){

} if(i%3==1||i==1){ outtextxy(10,50*(i+1), Graph[i].data);outtextxy(100,50*(i+1), Graph[i].data);Graph[i].x=100;Graph[i].y=50*(i+1);

}

} Graph[i].x=10;Graph[i].y=50*(i+1);if(i%3==2||i==2){

} outtextxy(200,50*i, Graph[i].data);Graph[i].x=200;Graph[i].y=50*i;for(i=0;i

p=Graph[i].firstedge;while(p){

line(Graph[i].x,Graph[i].y,Graph[p->adjvex].x,Graph[p->adjvex].y);outtextxy((Graph[i].x+Graph[p->adjvex].x)/2,(Graph[i].y+Graph[p->adjvex].y)/2,p->w+48);

} getch();} 求解關(guān)鍵路徑函數(shù)：

int SearchMapPath(vexnode* Graph,int vexnumber,int arcnumber)

{

int totaltime=0;int m=0;int i,j,k,t;char sv[100];closegraph();

arw[0]=Graph[p->adjvex].x+5;arw[1]=Graph[p->adjvex].y-10;arw[2]=Graph[p->adjvex].x;arw[3]=Graph[p->adjvex].y;arw[4]=Graph[p->adjvex].x+5;arw[5]=Graph[p->adjvex].y+10;drawpoly(3,arw);} p=p->nextedge;

int front,rear;

int *topology_queue,*vl,*ve,*el,*ee;front=rear=-1;t=0;

topology_queue=(int*)malloc(vexnumber*sizeof(int));

vl=(int*)malloc(vexnumber*sizeof(int));

ve=(int*)malloc(vexnumber*sizeof(int));

el=(int*)malloc(arcnumber*sizeof(int));

ee=(int*)malloc(arcnumber*sizeof(int));

edgenode *p;

for(i=0;i

for(i=0;i

{

if(Graph[i].id==0)

} {

topology_queue[++rear]=i;

m++;}

while(front!=rear)

{

front++;

j=topology_queue[front];

m++;

p=Graph[j].firstedge;

while(p)

}

if(m

{ {

}

k=p->adjvex;

Graph[k].id--;

if(ve[j]+p->w >ve[k])

ve[k]=ve[j]+p->w;

if(Graph[k].id ==0)topology_queue[++rear]=k;

p=p->nextedge;

printf(“n該圖中存在回路，不可計算出關(guān)鍵路徑！n”);

return 0;

}

totaltime=ve[vexnumber-1];

for(i=0;i

vl[i]=totaltime;

for(i=vexnumber-2;i>=0;i--)

{

j=topology_queue[i];

p=Graph[j].firstedge;

while(p){

k=p->adjvex;

if((vl[k]-p->w)

vl[j]=vl[k]-p->w;

p=p->nextedge;

}

}

printf(“| 起點 | 終點 | 最早開始時間 | 最遲開始時間n”);

i=0;

for(j=0;j

{

p=Graph[j].firstedge;

while(p)

{

k=p->adjvex;

ee[++i]=ve[j];

el[i]=vl[k]-p->w;

printf(“|

%4c

|

%4c

|

%12d

|

%12d |”,Graph[j].data ,Graph[k].data ,ee[i],el[i],el[i]-ee[i]);

差值 | |

%4d

|

if(el[i]==ee[i])

{

}

printf(“ 是關(guān)鍵活動 ”);

sv[t]=Graph[j].data;t++;

printf(“n”);

p=p->nextedge;

} }

printf(“關(guān)鍵路徑為：”);

sv[t]=Graph[vexnumber-1].data;

for(i=0;i<=t;i++)

{ printf(“%c”,sv[i]);

}

printf(“n”);if(sv[i]!=Graph[vexnumber-1].data)printf(“→”);

return 1;

}

3.主要函數(shù)的程序流程圖：

開始輸入圖中各個頂點的值輸入圖中弧的權(quán)值、起點、終點結(jié)束圖2 CreateGraph()函數(shù)流程圖

開始i=0否i=0i是否小于頂點數(shù)？是否輸出頂點的值，并保存頂點值在屏幕上的坐標(biāo)i是否小于頂點數(shù)？是p=Graph[i].firstedgei++i++是p=NULL?否從頂點Graph[i]向它的第一個鄰接頂點畫直線；輸出該弧的權(quán)值結(jié)束p=p->nextedge;圖3 Display()函數(shù)流程圖

開始在所有頂點中找出入度為0的頂點，并將其下標(biāo)保存到拓?fù)湫蛄袛?shù)組的第一個值中求出每個頂點的最早開始時間ve(i)和最晚開始時間vl(i)求出段弧的最早開始時間ee(i)和最晚開始時間el(i)否ee(i)是否等于最晚開始時間el(i)？是輸出該弧為關(guān)鍵活動輸出起點、終點、最早開始時間、最遲開始時間、差值 輸出關(guān)鍵路徑結(jié)束圖4 SearchMapPath()函數(shù)流程圖

4.畫出函數(shù)之間的調(diào)用關(guān)系圖:

主函數(shù)main()建立AOE網(wǎng)void CreateGraph()顯示有向圖void Display（）計算關(guān)鍵路徑int SearchMapPath()

四、調(diào)試分析

1.實際完成的情況說明: 本程序完成的功能是：顯示用戶從鍵盤輸入的有向圖，并計算出其關(guān)鍵路徑。支持用戶輸入char型的頂點值，int型的弧數(shù)和頂點數(shù)，int型的權(quán)值； 2.程序的性能分析：

本程序的時間復(fù)雜度為O(n),空間復(fù)雜度為O（1）。3.上機過程中出現(xiàn)的問題及其解決方案：

（1）有向圖的存儲。存儲時，由于對鄰接表的具體代碼實現(xiàn)不了解，導(dǎo)致在寫這部分程序的過程中遇到不少麻煩，比如如何在結(jié)點里添加指向下一鄰接結(jié)點的指針等，后來查閱了教材，解決了這一部分的問題。

（2）有向圖的顯示。如何在屏幕上以圖形的形式輸出圖，困惑了我好久。通過在網(wǎng)上查找資料及尋找?guī)椭?，明白了需在頭文件里添加graphics.h文件，并使用該庫里的line()函數(shù)和outtextxy()函數(shù)。接著是如何顯示帶箭頭的直線，由于graphics.h庫里不含有畫帶箭頭的直線的函數(shù)，于是，我使用了畫多邊形的函數(shù)drawpoly()來實現(xiàn)箭頭，但是這個函數(shù)的第二個形參類型是數(shù)組型的，需用數(shù)組來存儲三個點的坐標(biāo)信息。

（3）關(guān)鍵路徑的求解。由于對關(guān)鍵路徑的基本算法不了解，所以特地查閱了這一方面的書籍，了解了關(guān)鍵路徑的基本算法。4.程序中可以改進的地方說明：

有向圖的顯示里，箭頭無法隨直線的斜率的變化而變化，頂點值與箭頭重合，看不清箭頭的方向。

5.程序中可以擴充的功能及設(shè)計實現(xiàn)假想：

應(yīng)能顯示多個有向圖，能求解多個有向圖的關(guān)鍵路徑，關(guān)鍵活動。界面可以做成可視化，人性化的界面。

五、測試結(jié)果

（1）輸入一組可以構(gòu)成AOE網(wǎng)的頂點與弧的數(shù)據(jù)

（2）輸入一組不可構(gòu)成AOE網(wǎng)的頂點與弧的數(shù)據(jù)（即存在回路）

六、用戶手冊

(1)輸入圖中的節(jié)點數(shù)與弧數(shù)（2）輸入圖中各個頂點的值

（3）輸入圖中弧的權(quán)值、起點、終點

（4）按回車鍵

（5）按回車鍵

（6）按任意鍵

七、體會與自我評價

通過本次課程設(shè)，掌握了鄰接表的存儲結(jié)構(gòu)，圖形顯示的一些函數(shù)的使用以及關(guān)鍵路徑的求法。在實驗過程中出現(xiàn)了不少的問題，通過查閱資料，向老師、同學(xué)尋求幫助，解決了出現(xiàn)的問題。

從這次的課程設(shè)計任務(wù)中我深刻地體會到：任何事情并不像我們想的那樣艱難。剛開始拿到這個課設(shè)任務(wù)時，對于關(guān)鍵路徑很是發(fā)怵，因為之前對這一部分的知識運用的少，再加上任務(wù)書上還要求以圖形的形式顯示有向圖，在這次課設(shè)之前，我從來沒有接觸過圖形處理的函數(shù)。然而，俗話說“世上無難事，只怕有心人”，通過積極地查閱書籍，上網(wǎng)查找資料，這些困難都一個個的迎刃而解。并且在解決這些困難的同時，自己也復(fù)習(xí)并掌握了這些知識。本次課設(shè)遇到了很多理論課上所沒有遇到過的問題，也讓理論課上所學(xué)的理論得到驗證和使用，通過實際操作，扎實了理論知識，開拓了自己的算法思想。通過本次課設(shè)，更讓我意識到團隊合作的力量，通過小組成員的討論和互相解惑，學(xué)到很多自己沒有遇到過的問題的解決辦法，學(xué)會了如何在團隊合作中互幫互助，共同進步。

但是自己的程序仍存在一些不足，比如在有向圖的顯示方面，箭頭與頂點值重合了，導(dǎo)致無法清晰辨認(rèn)弧的方向。這次課設(shè)讓我明白了只有扎扎時時的學(xué)習(xí)知識才能解決實際生活中的實際問題，以后要多了解相關(guān)知識,更多的做一些實踐動手活動，將知識運用到實際問題中。同時，增加自己的動手能力，這樣才能便于我們更好的解決問題。為今后打下好的基礎(chǔ)。課外時間應(yīng)該多擴展一些編程方面的知識，提高自己的編程能力。

八、參考文獻

[1]嚴(yán)蔚敏，數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學(xué)出版社，2007 [2]邱建華，C語言程序設(shè)計教程，東軟電子出版社，2009 [3]劉汝佳，算法競賽入門經(jīng)典，清華大學(xué)出版社，2009

第三篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告

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

散列表的應(yīng)用:插隊買票

專業(yè) 計算機科學(xué)與技術(shù)（網(wǎng)絡(luò)技術(shù)）

金玲 計算機131 1310704114 張靜林 2015年1月23日 學(xué)生姓名 班學(xué)級 號

指導(dǎo)教師 完成日期

目錄概述……………………………………………………………………………………1 1.1 課程設(shè)計目的……………………………………………………………………….1 1.2 課程設(shè)計內(nèi)容……………………………………………………………………….1 2 系統(tǒng)需求分析……………………………………………………………………….1 2.1 主體功能…………………………………………………………………………....2 3系統(tǒng)概要設(shè)計…………………………………………………………………………2 3.1 系統(tǒng)流程圖………………………………………………………………………….2 4 系統(tǒng)詳細(xì)設(shè)計…………………………………………………………………………3 5 測試……………………………………………………………………………………5 5.1 測試方案…………………………………………………………………………….5 5.2 測試結(jié)果…………………………………………………………………………….5 6 小結(jié)……………………………………………………………………………………5 參考文獻…………………………………………………………………………………5 附錄………………………………………………………………………………………7 附錄1 源程序清單……………………………………………………………………...7 概述

1.1 課程設(shè)計目的

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計是為數(shù)據(jù)結(jié)構(gòu)課程獨立開設(shè)的實踐性教學(xué)環(huán)節(jié)。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計對于鞏固數(shù)據(jù)結(jié)構(gòu)知識，加強學(xué)生的實際動手能力和提高學(xué)生綜合素質(zhì)是十分必要的。課程設(shè)計的目的：

1．要求學(xué)生達(dá)到熟練掌握C語言的基本知識和技能。

2．了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力。3．提高程序設(shè)計和調(diào)試能力。學(xué)生通過上機實習(xí)，驗證自己設(shè)計的算法的正確性。學(xué)會有效利用基本調(diào)試方法，迅速找出程序代碼中的錯誤并且修改。

4．培養(yǎng)算法分析能力。分析所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度，進一步提高程序設(shè)計水平。

5．初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能。

1.2課程設(shè)計內(nèi)容

本課程設(shè)計的任務(wù)是寫一個程序模擬這種情況。每個隊伍都允許插隊。如果你在排隊，有一個以上的朋友要求插隊，則你可以安排他們的次序。每次一個人入隊，并且如果這個入隊的人發(fā)現(xiàn)隊伍中有自己的朋友，則可以插入到這個朋友的后面；當(dāng)隊伍中的朋友不止一個的時候，這個人會排在最后一個朋友的后面；如果隊伍中沒有朋友，則他只能夠排在這個隊伍的最后面。每一個入隊的人都先進行上述的判斷。當(dāng)隊伍前面的人買到車票之后，依次出隊。系統(tǒng)需求分析

2.1 主體功能

程序從“input.txt”文件讀入測試用例，一個文件可包含多個測試用例。每個用例的第一行是朋友組的數(shù)目n（1<=n<=1000)。對于一個朋友組以朋友的數(shù)目j（1<=j<=1000）開始，由朋友的個數(shù)以及他們的名字組成，一個空格后接該組朋友的名字，以空格分開，并且每個人的名字都不同。每個名字不超過四個字母，由{A，B，...，Z，a，b，...，z}組成。一個朋友組最多有1000個人，每個人只屬于一個朋友組。n=0時，測試數(shù)據(jù)結(jié)束。

下面是一些具體命令：.ENQUEUE——X入隊;.DEQUEUE——排隊頭的人買票，離開隊伍，即出隊；.STOP——一個測試用例結(jié)束。

測試結(jié)果輸出到“output.txt”文件中。每個測試用例第一行輸出“Scenario#k”，k是測試用例的序號（從1開始）。對每一個出隊命令，輸出剛買票離開隊伍的人名。兩個測試試用例 之間隔一空行，最后一個用例結(jié)束不輸出空行。系統(tǒng)概要設(shè)計

3.1 系統(tǒng)流程圖 系統(tǒng)詳細(xì)設(shè)計

本題目主要解決兩個問題：一是怎么存放和查找大量數(shù)據(jù)（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。

用散列表來存放和查找數(shù)據(jù)。由于最多有1000個朋友組，每組最多有1000人，使用平方探測法解決沖突，則表的大小是2*（1000*1000），所以選擇TableSize=2000003（2000003是大于2000000的最小素數(shù)）。同一個組內(nèi)的都是朋友，所以每個人除了記錄他的名字name，還要記錄他屬于哪個組group，另外用info來表示該單元是否被占用，數(shù)據(jù)結(jié)構(gòu)如圖4.1所示。散列函數(shù)是根據(jù)Honer法則計算一個以64為階的多項式，如圖4.2所示。沖突解決方法采用平方探測法，如圖4.3所示。

#define TabSize 2000003 typedef struct hashtab *PtrToHash;struct hashtab

/*散列表數(shù)據(jù)結(jié)構(gòu)*/ { char name[5];

/*名字*/ int group;

/*屬于哪個朋友組*/ char info;

/*標(biāo)志位，該單元是否被占用*/ };圖4.1數(shù)據(jù)結(jié)構(gòu)：散列表

Int Hash(char *key,int TableSize){

Int HashVal=0;

While(key!=NULL)

HashVal=(HashVal<<6)+*key;

Return HashVal%TableSize;} 圖4.2散列函數(shù)

Long int Find(PtrToHash hash,char *c){

key=c;

CurrentPos=Hash(key,TableSize);

CollisionNum=0;

While((單元被占用)and(單元內(nèi)的名字與查找的名字不同))

{

CurrentPos+=2*(++CollisionNum)-1;

If(CurrentPos>=TabSize)

CurrentPos=TabSize;

}

Return CurrentPos;} 圖4.3用平方探測法解決沖突

第二個問題是關(guān)于怎么操作“ENQUEUE”和“DEQUEUE”命令。這可以用隊列來模擬。由于有插隊現(xiàn)象的存在，不能單純的用一個數(shù)組來表示隊列，因為這樣的話，插入一個朋友，則他后面的人都要往后移一個單位，刪除一個人，則他后面的人都要前移一個，會降低效率。所以，采用一個Index標(biāo)記來表示當(dāng)前元素的后繼元素，最后一個單元的后繼元素是第0個，形成環(huán)，數(shù)據(jù)結(jié)構(gòu)如圖4.4所示。不用鏈表是因為鏈表存放指針也需要空間，并且鏈表插入、刪除的效率沒有數(shù)組高。

typedef struct Que *PtrToQue;struct Que

/*隊列數(shù)據(jù)結(jié)構(gòu)*/ { long int HashVal;

/*散列值*/ long int Index;

/*在中的隊列序號*/ };圖4.4數(shù)據(jù)結(jié)構(gòu)：隊列

輸入ENQUEUE命令，如果隊伍里有朋友，則排在朋友后面；如果沒有朋友，則排在隊尾。入隊時，用一個數(shù)組記錄每個朋友組的最后一位，以便下一個朋友到來時排到他后面，這個數(shù)組被稱為“插隊數(shù)組”。

輸入DEQUEUE命令，則根據(jù)“先進先出”，按照各個元素和它后繼元素的先后順序，每次刪除隊列重的第一個。程序結(jié)構(gòu)如圖4.5所示。

While(讀測試文件){

if(輸入”ENQUEUE”)

{

讀入名字；

插入散列表；

插入隊列；

}

else if(輸入”DEQUEUE”)

{

刪除隊列第一個名字；

將該名字輸出到文件；

}

else stop;} 圖4.5入隊、出隊操作 測試

5.1 測試方案 按輸入要求輸入正常測試數(shù)據(jù)，測試程序是否能正確解決問題，得到正確答案。應(yīng)注意邊界測試。例如，將n，j分別取為1的用例和n為1000的用例。n，j比較大時需寫程序生成測試用例。

不按輸入要求輸入數(shù)據(jù)，測試程序能否對輸入內(nèi)容進行數(shù)據(jù)合法性檢測并進行相應(yīng)的異常處理。例如，將n或j取為小于1或大于1000的數(shù)，名字超過4個字母等情況下的測試用例。5.2 測試結(jié)果 小結(jié)

在前面的學(xué)習(xí)過程中我們學(xué)到了很多知識而這次課程設(shè)計又是對我們所學(xué)的 一次總結(jié)，剛開始，可以說是沒有頭緒，于是就去圖書館找資料，找到了一些關(guān)于程序方面的，可這遠(yuǎn)遠(yuǎn)不夠，這只是小小的開始。我們必須掌握很多已學(xué)的知識才能很好的完成本次的課程設(shè)計。在這次課程設(shè)計中，總的感覺是我遇到了很多困難這主要是由于我編寫代碼的經(jīng)驗不足，有時雖然是一個很小的問題但解決起來卻花費了我不少的時間，值得欣慰的是，當(dāng)自己苦思冥想或者和其它同學(xué)一起探討把問題解決的時候我還是覺得獲益非淺，這就是在摸索中尋求到的知識。在設(shè)計時也免不了存在著些不足，所以在今后的學(xué)習(xí)中我會努力取得更大的進步。雖然對著電腦做程序，有些累，可當(dāng)看到勞動成果時，卻有另一番滋味。

參考文獻

[1]范策，周世平，胡曉琨.《算法與數(shù)據(jù)結(jié)構(gòu)（C語言版）》[M].北京：機械工業(yè)出版社，2004 [2]嚴(yán)蔚敏.《數(shù)據(jù)結(jié)構(gòu)（C語言版）》.北京：清華大學(xué)出版社，2004 [3]許卓群，楊冬青，唐世渭，張銘.《數(shù)據(jù)結(jié)構(gòu)與算法》.北京：高等教育出版社，2004 [4]徐孝凱.《數(shù)據(jù)結(jié)構(gòu)實用教程（第二版）》.北京：清華大學(xué)出版社，2006

附錄

附錄1 源程序清單

#include #include #include #define TabSize 2000003

/*散列表大小TabSize 是大于表最大空間的素數(shù)*/ #define Max 1000001

/*隊列空間最大值*/ struct hashtab;typedef struct hashtab *PtrToHash;struct hashtab

/*散列表數(shù)據(jù)結(jié)構(gòu)*/ { char name[5];

/*名字*/ int group;

/*屬于哪個朋友組*/ char info;

/*標(biāo)志位，該單元是否被占用*/ };struct Que;typedef struct Que *PtrToQue;struct Que

/*隊列數(shù)據(jù)結(jié)構(gòu)*/ { long int HashVal;

/*散列值*/ long int Index;

/*在中的隊列序號*/ };

int hashedx=0;

/*標(biāo)記元素是否已經(jīng)在散列表里*/ long int Find(PtrToHash hash,char *c)/*查找在散列表中的位置*/ { char *key;long int CurrentPos,CollisionNum;

key=c;for(CurrentPos=0;*key;++key)

/*散列函數(shù)，計算散列值*/

CurrentPos=(CurrentPos<<6)+*key;CurrentPos%=TabSize;

/*散列值*/ CollisionNum=0;/*如果當(dāng)前單元被占用：單元內(nèi)的元素與當(dāng)前操作的名字不同，使用平方探測法解決沖突；與當(dāng)前操作的名字相同，則直接返回在散列中的位置*/ while((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)))

{

/*平方探測法*/

CurrentPos+=2*(++CollisionNum)-1;

if(CurrentPos>=TabSize)

CurrentPos-=TabSize;}

if((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)==0))

/*元素已經(jīng)在散列表里*/

hashedx=1;else /*元素不在散列表里*/

hashedx=0;return CurrentPos;/*返回在散列表中的位置*/ }

int main(){ long int Find(PtrToHash hash,char *c);

/*查找在散列表中的位置*/

PtrToHash hash;

/*散列表*/ PtrToQue queue;

/*隊列*/ int *grouppos;

/*記錄每個朋友組的最后一位，即插隊數(shù)組*/ int n;

/*測試用例數(shù)目*/ int num;

/*當(dāng)前測試用例序號*/ long int i,ii,j,key,temp;long int head,last;

/*隊列的頭和尾*/ char c[8],tempc[8];

/*名字*/ FILE *fpin,*fpout;

/*輸入、輸出文件指針*/

if(!(fpin=fopen(“input.txt”,“r”)))

/*打開測試文件*/ {

printf(“fopen error!”);

/*文件打開錯誤*/

return-1;} if(!(fpout=fopen(“output.txt”,“w”)))

/*打開輸出文件*/ {

printf(“fopen error!”);

return-1;}

hash=(PtrToHash)malloc(sizeof(struct hashtab)*TabSize);/*為散列表申請空間*/ queue=(PtrToQue)malloc(sizeof(struct Que)*Max);/*為隊列申請空間*/ grouppos=(int *)malloc(sizeof(int)*1000);/*申請空間記錄每個朋友組的最后一位*/ for(i=0,j=1;i

queue[i].Index=j;queue[i-1].Index=0;/*最后一個單元的后繼單元是第0個，形成環(huán)*/ num=0;for(fscanf(fpin,“%d”,&n);n;fscanf(fpin,“%d”,&n))/*輸入當(dāng)前測試用例的朋友組數(shù)*/ {

if(n<1||n>1000)

/*處理異常輸入n*/

{

fprintf(fpout,“n is out of rangen”);

return-1;

}

num++;

if(num!=1)

/*兩個測試用例間輸入一空行*/

fprintf(fpout,“n”);

for(i=0;i

hash[i++].info=0;

/*初始化散列表，標(biāo)記位置0*/

for(i=0;i

/*對每一組朋友*/

{

fscanf(fpin,“%d”,&j);

/*當(dāng)前組里的人數(shù)*/

if(j<1||j>1000)

/*處理異常輸入j*/

{

fprintf(fpout,“j is out of rangen”);

return-1;

}

for(;j;--j)

{

fscanf(fpin,“%s”,c);

/*輸入名字*/

for(ii=0;ii

tempc[ii]='