国产精品久久久久久成人影院,国产成人欧美亚洲日韩电影,亚洲aⅴ永久无码一区二区三区

第一篇：數據結構課程設計報告

數據結構課程設計報告

院系：計算機學院

班級：軟件121班

姓名：程猛

學號：201200834122 題目：最小生成樹

軟件121 程猛 201200834122

數據結構課程設計報告

指導老師：杜獻峰

一、引言..................................................................................................................4

二、設計題目..........................................................................................................4 1.問題描述...........................................................................................................4 2.系統要求...........................................................................................................4 3.測試數據...........................................................................................................5 4.實現提示...........................................................................................................5 5.參考文獻...........................................................................................................5 6.運行環境...........................................................................................................6

三、需求分析..........................................................................................................6 1.如何選擇存儲結構去建立一個帶權網絡。...................................................6 2.如何在所選存儲結構下輸出這個帶權網絡。...............................................6 3.如何實現PRIM算法和Kruskal算法的功能。.............................................6 4.如何從每個頂點開始找到所有的最小生成樹的頂點。...............................7 5.如何輸出最小生成樹的邊及其權值。...........................................................7

四、概要設計..........................................................................................................7 2.圖的存儲結構...................................................................................................8 3.流程圖...............................................................................................................8

五、詳細設計..........................................................................................................9 1.主函數模塊.......................................................................................................9 2.對路徑權值進行排序.....................................................................................10

六、調試與分析....................................................................................................14

七、測試結果........................................................................................................17

軟件121 程猛 201200834122 2

數據結構課程設計報告

八、設計心得體會................................................................................................17

附錄（源代碼）18

軟件121 程猛 201200834122 3

數據結構課程設計報告

摘要

最小生成樹是數據結構中圖的一種重要應用，在圖中對于n個頂點的連通網可以建立許多不同的生成樹，最小生成樹就是在所有生成樹中總的代價最小的生成樹。本課程設計是以鄰接矩陣作為圖的存儲結構,分別采用Prim和Kruskal算法求最小生成樹。Kruskal算法和Prim算法是求最小生成樹的常用算法它們分別適用于稠密圖和稀疏圖。最小生成樹的應用非常的廣，如礦井通風設計和改造最優化方面以及如何搭建最短的網絡線纜, 構建造價最低的通訊網絡。

一、引言

本課程設計我們要解決的問題是圖最小生成樹問題。要用到圖的先相關數據結構和求最小生成樹的兩種數據結構算法普里姆算法和克魯斯卡爾算法，以及儲存圖的邊和點的鄰接矩陣。

本課程設計要解決的問題構造連通網的最小生成樹 ,我們首先要做的是創建一個鄰接矩陣，用以來存儲圖，然后我們要想好怎樣利用普里姆算法和克魯斯卡爾算法來構造最小生成樹。把這兩種算法寫入主函數，調試好程序。最后寫好報告。

二、設計題目 1.問題描述

若要在n個城市之間建設通信網絡，只需要假設n-1條線路即可。如何以最低的經濟代價建設這個通信網，是一個網的最小生成樹問題。

2.系統要求

利用克魯斯卡爾算法求網的最小生成樹。利用普里姆算法求網的最小生成樹。要求輸出各條邊及它們的權值。

軟件121 程猛 201200834122 4

數據結構課程設計報告

3.測試數據

4.實現提示

通信線路一旦建成，必然是雙向的。因此，構造最小生成樹的網一定是無向圖。設圖的頂點數不超過30個，并為簡單起見，網中邊的權值設成小于100的整數，100則表示沒有路徑。

5.參考文獻

[1] 嚴蔚敏.數據結構（C語言版）[M].北京：清華大學出版社,1997.[2] 譚浩強.C程序設計（第三版）[M].北京：清華大學出版社，2005.1.[3] 二霍紅衛算法設計與分析〔」西安西安電子科技大學出版社，2005.113-127.[4] 陳杰.計算機專業課程設計中的需求分析[J].集美大學學報，2009，10(2)：89—92.[5] 高一凡.數據結構算法實現及解析[M ].西安:西安電子科技大學出版軟件121 程猛 201200834122

數據結構課程設計報告

社, 2002 6.運行環境

VC++6.0

三、需求分析

1.如何選擇存儲結構去建立一個帶權網絡。

此問題的關鍵在于如何實現PRIM算法和Kruskal算法，實現的過程中如何得到構成最小生成樹的所有頂點，此外輸出也是一個關鍵問題所在，在此過程中經過了多次調試。

2.如何在所選存儲結構下輸出這個帶權網絡。

將圖中的所有頂點存儲到一個一維數組中，通過一個二維數組用鄰接矩陣連實現對各邊權值的存儲

3.如何實現PRIM算法和Kruskal算法的功能。

首先我們對prim算法的問題進行大致的概要分析：

假設N=（V，{E}）是連通網，TE是N上最小生成樹中邊的集合。算法從U={u0}（u0∈V），TE={}開始，重復執行下述操作：在所有u∈U，v∈V-U的邊（u，v）∈E中找一條代價最小的邊（u0,v0）并入集合TE，同時v0并入U，直至U=V為止。此時TE中必有n-1條邊，則T=(V,{TE})為N的最小生成樹。

克魯斯卡爾算法從另一種途徑求網的最小生成樹：

假設連通網N=(V,{E})，則另最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖T=(V,{})，圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價最小的邊。以此類推直至T中的軟件121 程猛 201200834122

數據結構課程設計報告

所有頂點都在同一連通分量上為止。

4.如何從每個頂點開始找到所有的最小生成樹的頂點。

對于prim算法從圖的點集中任取一個頂點作為起始頂點，然后找到依附于該頂點的所有邊選取權值最小的，依次找下去直至圖中所有頂點都在一個點集中為止。對于克魯斯卡爾算法則通過對權值進行排序找出權值最小的頂點和邊并把該邊的頂點并入點集之中。

5.如何輸出最小生成樹的邊及其權值。

通過訪問數組來實現對最小生成樹邊和權值的輸出。

四、概要設計

1、設定圖的抽象數據類型: ADT Graph{ 數據對象V:V是具有相同特性的數據元素的集合,稱為點集.數據關系R: R={VR} VR={(v,w)|v,w屬于V,(v,w)表示v和w之間存在的路徑} 基本操作P: CreatGraph(&G,V,VR)初始條件:V是圖的頂點集,VR是圖中弧的集合.操作結果:按V和VR是定義構造圖G.Sort(edge* ,MGraph *)初始條件: 圖G存在，各邊權值已知；操作結果:對權值進行排序； Find(int *, int)初始條件:前者為已存在的集合，后者為集合中的元素；操作結果:查找函數，確定后者所屬子集； Swapn(edge *, int, int)初始條件: 圖G存在，各邊權值已知；操作結果:交換某兩個邊的權值；

軟件121 程猛 201200834122

數據結構課程設計報告

2.圖的存儲結構

typedef struct {

int vexnum,arcnum;}ALGraph;typedef struct //邊的結構體定義 {

int begin,end;//邊的開始和結束頂點

int cost;//權值 }EDGE;typedef struct {

int edges[max][max];//

int n,e;}MGraph;3.流程圖

軟件121 程猛 201200834122

數據結構課程設計報告

五、詳細設計

在該函數中有6個模塊，分別是主函數模塊、路徑權值進行排序、交換頂點及權值模塊、判斷是否回環、prim算法的實現、Kruskal算法的實現。

1.主函數模塊

ALGraph G;MGraph G2;int v,i,j;char a;do {

system(“cls”);

cout<<“t***********************************nn”;

cout<<“t

克魯斯卡爾

n”;

cout<<“t

普

里

姆

n”;

cout<<“t

退

出

nn”;

cout<<“t***********************************n”;

cout<<“請輸入序號：”;

cin>>a;

switch(a)

{

case '1': MiniSpanTree_Kruskal(G);system(“pause”);break;

case '2': cout<<“請輸入結點數：”;

cin>>G2.n;

for(j=1;j<=G2.n;j++)

{

cout<<“請輸入第”<

for(i=1;i<=G2.n;i++)

cin>>G2.edges[j][i];

}

cout<<“請輸入開始頂點:”;

cin>>v;

MiniSpanTree_PRTM(G2,v);system(“pause”);break;軟件121 程猛 201200834122

數據結構課程設計報告

default : break;

} }while(a!='3');return 0;

該模塊包含菜單的設計以及通過一個switch語句來實現對prim算法和Kruskal算法的實現。進入主菜單后選擇相應的序號執行相應的操作，每進行一步后，按任意鍵繼續進行下一個操作可重復執行。

2.對路徑權值進行排序

void Sort(EDGE *edges,ALGraph G)//對帶權路徑從小到大排序 { int i,j;for(i=1;i<=G.arcnum;i++)for(j=i;j<=G.arcnum;j++)if(edges[i].cost>edges[j].cost)Swapn(edges,i,j);}

在圖中找到權值最小的邊

3.交換頂點及權值

void Swapn(EDGE *edges,int i,int j)// 交換的兩個頂點及權值 { int temp;temp=edges[i].begin;edges[i].begin=edges[j].begin;edges[j].begin=temp;temp=edges[i].end;edges[i].end=edges[j].end;edges[j].end=temp;temp=edges[i].cost;edges[i].cost=edges[j].cost;edges[j].cost=temp;軟件121 程猛 201200834122

數據結構課程設計報告

}

該模塊主要用于Kruskal算法，找到圖中權值最小的一條邊，然后交換它們的頂點和權值。

4.判斷是否回環

int Find(int *parents,int f)//判斷是否形成環 { while((parents[f])>0&&(f!=parents[f]))f=parents[f];return f;}

在Kruskal算法中初始parents[]為0來設置訪問未訪問標志，以此來判斷圖是否成環。

5.prim算法的實現

void MiniSpanTree_PRTM(MGraph &G,int v){ int closedge[max];int lowcost[max];int i,j,k,min;for(i=1;i<=G.n;i++){

lowcost[i]=G.edges[v][i];

closedge[i]=v;} for(i=1;i

min=INF;

for(j=1;j<=G.n;j++)

if(lowcost[j]!=0&&lowcost[j]

{

min=lowcost[j];

k=j;

} 軟件121 程猛 201200834122

數據結構課程設計報告

}

} printf(“邊(%d,%d)權為:%dn”,closedge[k],k,min);lowcost[k]=0;for(j=1;j<=G.n;j++)if(G.edges[k][j]!=0&&G.edges[k][j]

void MiniSpanTree_Kruskal(ALGraph &G)//MiniSpanTree_Kruskal()函數實現 {

int i,s,v1,v2,value,bnf,edf;

int parents[MAX_VERTEX_NUM];

EDGE edges[MAX_VERTEX_NUM];

cout<

cin>>G.vexnum;

//輸入頂點數

cout<<“請輸入邊數: ”;

cin>>G.arcnum;

//輸入邊數

cout<<“請輸入(V1和V2), 例如:(V1=1,V2=3),(V1=2,V2=4)...”;

cout<

//輸入arc(v1,v2)

for(i=1;i<=G.arcnum;++i)

{

cout<

cin>>v1;

//輸入頭頂點

cout<<“請輸入第 ”<

cin>>v2;

//輸入尾頂點

cout<<“請輸入第 ”<

: ”;

cin>>value;

//輸入邊的權值

edges[i].begin=v1;

edges[i].end=v2;

while(v1<1||v1>G.vexnum||v2<1||v2>G.vexnum)

//如果輸入的非法，重新輸入

{ 軟件121 程猛 201200834122

數據結構課程設計報告

cout<<“輸入不合法，請重新輸入！”;

cout<

cin>>v1;

cout<<“請輸入第 ”<

cin>>v2;

cout<<“請輸入第 ”<

: ”;

cin>>value;

edges[i].begin=v1;

edges[i].end=v2;

}

edges[i].cost=value;}

Sort(edges,G);

//調用Sort()函數

cout<<“按照排列好的序列逐個輸出權值”<

//初始化array parents[]

cout<

for(i=1,s=1;s<=G.vexnum&&i<=G.arcnum;i++)

{

bnf=Find(parents,edges[i].begin);

edf=Find(parents,edges[i].end);

if(bnf!=edf)

{

parents[bnf]=edf;

cout<

//輸出最小生成樹

cout<

s++;

}

} }

軟件121 程猛 201200834122 13

數據結構課程設計報告

六、調試與分析

測試數據如下圖

求該圖的最小生成樹

1.進入主頁面

2.利用克魯斯卡爾算法求最小生成樹

選擇序號1使用克魯斯卡爾算法求圖的最小生成樹。

軟件121 程猛 201200834122 14

數據結構課程設計報告

輸入每條邊的頂點和權值

對權值進行排序，并且輸出最小生成樹。

軟件121 程猛 201200834122 15

數據結構課程設計報告

3.利用prim算法求最小生成樹

選擇序號2用prim算法求最小生成樹。通過一個n階的鄰接矩陣來實現圖的輸入

輸入起始頂點然后輸出最小生成樹的各邊及其每一條邊的權值。

4.退出程序

選擇序號3退出程序

軟件121 程猛 201200834122 16

數據結構課程設計報告

七、測試結果

克魯斯卡爾算法求得的最小生成樹為3?5?2?1?4?6 Prim算法求得的最小生成樹為1?2?5?3?4?6

八、設計心得體會

在我的努力下，課程設計終于完成，由于我們對數據結構和c語言不是很了解，有時忽略了一些關鍵的細節，使得在編寫程序的過程中出現了一些問題。對于打字有時粗心導致出現一些難以發現的小錯誤，在我的耐心，細致的調試下最終使得程序能夠運行，課程設計圓滿完工。

軟件121 程猛 201200834122

數據結構課程設計報告

問題一：求出圖中的最小值現象：求出的最小值是0 原因：圖中沒有連通的兩個頂點之間的權值賦值為0 問題二：求最小生成樹時，else語句需再調用一個函數現象：對某些二叉樹能求出最小生成樹，但不能普遍適應

原因：對于找最小生成樹邊的各種可能沒有考慮全面，代碼才沒有廣泛的適應性

問題三：兩個頂點之間的邊是否是最小生成樹的邊現象：代碼的功能不能分辨出是否是最小生成樹的邊

原因：把簡單的代碼寫的很復雜，從而雜亂無章出現錯誤。

在課設過程中，遇到許多問題，通過查閱資料和課本。是我對數據結構有了更進一步的認識。當然，這中間也有其他人的幫助。我的同學，以及指導老師都給我提出了非常寶貴的意見。通過與同學和老師的交流，使我找到了數據結構這門課程的學習方法。但是，我感覺這不僅僅是數據結構的學習方法，他或許就是學習軟件工程這門專業的方法，那就是多動手。的確如此，對于一個算法，你知道它的算法思想和用計算機實現它卻是另外一回事。這門課程，不僅需要我們用心去理解每一種算法的思想，更需要我們去動手來實現它。

附錄（源代碼）

#include “iostream” using namespace std;#define MAX_VERTEX_NUM 30 //定義最大頂點數 #define MAXQSIZE 100 #define max 20 #define INF 10

typedef struct {

int vexnum,arcnum;}ALGraph;

typedef struct //邊的結構體定義 {

軟件121 程猛 201200834122

數據結構課程設計報告

int begin,end;//邊的開始和結束頂點

int cost;//權值 }EDGE;

////////////////////////////// typedef struct {

int edges[max][max];//

int n,e;}MGraph;

void Swapn(EDGE *edges,int i,int j);

// 交換的兩個頂點及權值 void Sort(EDGE *edges,ALGraph G);

//對帶權路徑從小到大排序 int Find(int *parents,int f);

//判斷是否形成環

void MiniSpanTree_Kruskal(ALGraph &G);//MiniSpanTree_Kruskal()函數實現

void Sort(EDGE *edges,ALGraph G)//對帶權路徑從小到大排序 { 軟件121 程猛 201200834122

數據結構課程設計報告

int i,j;for(i=1;i<=G.arcnum;i++)for(j=i;j<=G.arcnum;j++)if(edges[i].cost>edges[j].cost)Swapn(edges,i,j);}

int Find(int *parents,int f)//判斷是否形成環 { while((parents[f])>0&&(f!=parents[f]))f=parents[f];return f;}

void MiniSpanTree_Kruskal(ALGraph &G)//MiniSpanTree_Kruskal()函數實現 {

int i,s,v1,v2,value,bnf,edf;

int parents[MAX_VERTEX_NUM];

EDGE edges[MAX_VERTEX_NUM];

cout<

cin>>G.vexnum;

//輸入頂點數

cout<<“請輸入邊數: ”;

cin>>G.arcnum;

//輸入邊數

cout<<“請輸入(V1和V2), 例如:(V1=1,V2=3),(V1=2,V2=4)...”;

cout<

//輸入arc(v1,v2)

for(i=1;i<=G.arcnum;++i)

{

cout<

cin>>v1;

//輸入頭頂點

cout<<“請輸入第 ”<

cin>>v2;

//輸入尾頂點

cout<<“請輸入第 ”<

: ”;

cin>>value;

//輸入邊的權值

軟件121 程猛 201200834122

數據結構課程設計報告

edges[i].begin=v1;

edges[i].end=v2;

while(v1<1||v1>G.vexnum||v2<1||v2>G.vexnum)

//如果輸入的非法，重新輸入

{

cout<<“輸入不合法，請重新輸入！”;

cout<

cin>>v1;

cout<<“請輸入第 ”<

cin>>v2;

cout<<“請輸入第 ”<

: ”;

cin>>value;

edges[i].begin=v1;

edges[i].end=v2;

}

edges[i].cost=value;}

Sort(edges,G);

//調用Sort()函數

cout<<“按照排列好的序列逐個輸出權值”<

//初始化array parents[]

cout<

for(i=1,s=1;s<=G.vexnum&&i<=G.arcnum;i++)

{

bnf=Find(parents,edges[i].begin);

edf=Find(parents,edges[i].end);

if(bnf!=edf)

{

parents[bnf]=edf;

cout<

//輸出最小生成樹

cout<

s++;

}

軟件121 程猛 201200834122

數據結構課程設計報告

} /////////////////////// void MiniSpanTree_PRTM(MGraph &G,int v){ int closedge[max];int lowcost[max];int i,j,k,min;for(i=1;i<=G.n;i++){

lowcost[i]=G.edges[v][i];

closedge[i]=v;} for(i=1;i

min=INF;

for(j=1;j<=G.n;j++)

if(lowcost[j]!=0&&lowcost[j]

{

min=lowcost[j];

k=j;

}

printf(“邊(%d,%d)權為:%dn”,closedge[k],k,min);

lowcost[k]=0;

for(j=1;j<=G.n;j++)

if(G.edges[k][j]!=0&&G.edges[k][j]

{

lowcost[j]=G.edges[k][j];

closedge[j]=k;

} } }

int main(){ ALGraph G;軟件121 程猛 201200834122

數據結構課程設計報告

MGraph G2;int v,i,j;char a;do {

system(“cls”);

cout<<“t***********************************nn”;

cout<<“t

克魯斯卡爾

n”;

cout<<“t

普

里

姆

n”;

cout<<“t

退

出

nn”;

cout<<“t***********************************n”;

cout<<“請輸入序號：”;

cin>>a;

switch(a)

{

case '1': MiniSpanTree_Kruskal(G);system(“pause”);break;

case '2': cout<<“請輸入結點數：”;

cin>>G2.n;

for(j=1;j<=G2.n;j++)

{

cout<<“請輸入第”<

for(i=1;i<=G2.n;i++)

cin>>G2.edges[j][i];

}

cout<<“請輸入開始頂點:”;

cin>>v;

MiniSpanTree_PRTM(G2,v);system(“pause”);break;

default : break;

} }while(a!='3');return 0;} 軟件121 程猛 201200834122 23

第二篇：數據結構課程設計報告

數據結構課程設計

散列表的應用:插隊買票

專業計算機科學與技術（網絡技術）

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

指導教師完成日期

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

1.1 課程設計目的

數據結構課程設計是為數據結構課程獨立開設的實踐性教學環節。數據結構課程設計對于鞏固數據結構知識，加強學生的實際動手能力和提高學生綜合素質是十分必要的。課程設計的目的：

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

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

4．培養算法分析能力。分析所設計算法的時間復雜度和空間復雜度，進一步提高程序設計水平。

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

1.2課程設計內容

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

2.1 主體功能

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

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

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

3.1 系統流程圖系統詳細設計

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

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

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

/*散列表數據結構*/ { char name[5];

/*名字*/ int group;

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

/*標志位，該單元是否被占用*/ };圖4.1數據結構：散列表

Int Hash(char *key,int TableSize){

Int HashVal=0;

While(key!=NULL)

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

Return HashVal%TableSize;} 圖4.2散列函數

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

key=c;

CurrentPos=Hash(key,TableSize);

CollisionNum=0;

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

{

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

If(CurrentPos>=TabSize)

CurrentPos=TabSize;

}

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

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

typedef struct Que *PtrToQue;struct Que

/*隊列數據結構*/ { long int HashVal;

/*散列值*/ long int Index;

/*在中的隊列序號*/ };圖4.4數據結構：隊列

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

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

While(讀測試文件){

if(輸入”ENQUEUE”)

{

讀入名字；

插入散列表；

插入隊列；

}

else if(輸入”DEQUEUE”)

{

刪除隊列第一個名字；

將該名字輸出到文件；

}

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

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

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

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

參考文獻

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

附錄

附錄1 源程序清單

#include #include #include #define TabSize 2000003

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

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

/*散列表數據結構*/ { char name[5];

/*名字*/ int group;

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

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

/*隊列數據結構*/ { long int HashVal;

/*散列值*/ long int Index;

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

int hashedx=0;

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

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

/*散列函數，計算散列值*/

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

/*散列值*/ CollisionNum=0;/*如果當前單元被占用：單元內的元素與當前操作的名字不同，使用平方探測法解決沖突；與當前操作的名字相同，則直接返回在散列中的位置*/ 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))

/*元素已經在散列表里*/

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

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

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

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

PtrToHash hash;

/*散列表*/ PtrToQue queue;

/*隊列*/ int *grouppos;

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

/*測試用例數目*/ int num;

/*當前測試用例序號*/ 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個，形成環*/ num=0;for(fscanf(fpin,“%d”,&n);n;fscanf(fpin,“%d”,&n))/*輸入當前測試用例的朋友組數*/ {

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;

/*初始化散列表，標記位置0*/

for(i=0;i

/*對每一組朋友*/

{

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

/*當前組里的人數*/

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]='

久久99精品久久久久久琪琪,久久人人爽人人爽人人片亞洲,熟妇人妻无码中文字幕,亚洲精品无码久久久久久久

數據結構課程設計報告

第一篇：數據結構課程設計報告

第二篇：數據結構課程設計報告