計算機數據結構課程設計---dijkstra算法和排序器

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：17 大?。?47.00KB 人氣指數：12 舉報 版權申訴

已閱讀1頁，還剩16頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數據結構課程論文　　設計題目：Dijkstra算法和排序器（排序算法驗證及評價）　　圖的Dijkstra算法　　一、課題內容和要求　　Dijkstra算法的實現(xiàn)和演示。<

2、;/p>　　二、設計思路分析　　Dijkstra算法的基本思路是：假設每個點都有一對標號 (dj, pj)，其中dj是從起源點s到點j的最短路徑的長度 (從頂點到其本身的最短路徑是零路(沒有弧的路)，其長度等于零)；pj則是從s到j的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑算法的基本過程如下：　　1) 初始化。起源

3、點設置為：① ds=0, ps為空;② 所有其他點: di=∞, pi=?;③ 標記起源點s，記k=s,其他所有點設為未標記的?！　?) 檢驗從所有已標記的點k到其直接連接的未標記的點j的距離，并設置：　　dj=min［dj, dk+lkj］　　式中，lkj是從點k到j的直接連接距離。　　3) 選取下一個點。從所有未標記的結點中，選取dj 中最小的一

4、個i：　　di=min［dj, 所有未標記的點j］　　點i就被選為最短路徑中的一點，并設為已標記的?！　?) 找到點i的前一點。從已標記的點中找到直接連接到點i的點j*，作為前一點,設置：　　i=j*　　5) 標記點i。如果所有點已

5、標記，則算法完全推出，否則，記k=i，轉到2) 再繼續(xù)。　　三、概要設計 　　算法流程圖如下圖所示：　　CGraph類的聲明部分如下所示：　　#define maxPoint 100　　cla

6、ss CGraph　　{　　public:　　CGraph(void);　　~CGraph(void);　　bool SetGraph( double g

7、[maxPoint][maxPoint] , int startPoint , int size );　　bool Dijkstra();　　void Display();　　int GetStartPoint();　　bool setStart(int start);&

8、lt;/p>　　void ChangeMatix(double (*p)[maxPoint]);　　double GetBestWay( int dest , int path[] , int &pathLen );　　private:

9、bool solved;//標志當前圖是否已經求解　　double graph[maxPoint][maxPoint];//當前圖布局　　int size;//地圖大小　　int startPoint;//起點　　double dist[maxPoint];//當前圖的解

10、　　int prev[maxPoint];　　};　　四、詳細設計　　// Dijkstra2.cpp : Defines the entry point for the console appl

11、ication.　　//　　#include "stdafx.h"　　#include "Graph.h"　　// Dijkstra.cpp : 定義控制臺應用程序的入口點。

12、　　void DisplayMessage()　　{　　printf( "☆☆☆☆☆☆最短路徑算法Dijkstra演示☆☆☆☆☆☆☆☆\n\n" );　　printf("△1.連接矩陣顯示\n\n");</p

13、>　　printf("△2.修改連接矩陣\n\n");　　printf("△3.求解最短路徑\n\n");　　printf("△4.清空屏幕\n\n");　　printf("△5.退出\n\n");<

14、/p>　　printf("請您輸入選項");　　}　　//求解最短路徑函數　　void computerDijkstra(CGraph g,int dest,int size,int path[],int pathlen)<

15、;/p>　　{　　printf( "----------------------------------------\n" );　　double distanceLenth=0;　　for( dest = 0 ; dest &l

16、t; size ; dest++ )　　{　　distanceLenth = g.GetBestWay( dest , path , pathlen );　　printf( "從 %d 到 %d 的最短路徑長 %.f\n" , g.GetStartPoin

17、t() , dest , distanceLenth );　　printf( "所經結點為:\n" );　　for( int i = 0 ; i < pathlen ; i++ )　　printf( "%3d" , path[i] );<

18、p>　　printf( "\n----------------------------------------\n" );　　}　　}　　//主函數&

19、lt;p>　　void main()　　{　　//連接矩陣可以修改　　double graph[][maxPoint] =　　{　　{ 0 , 1

20、0 , -1 , 30 , 100 } ,　　{ -1 , 0 , 50 , -1 , -1 } ,　　{ -1 , -1 , 0 , -1 , 10 } ,　　{ -1 , -1 , 20 , 0 , 60 } ,　　{ -1 , -1 , -1 , -1 , 0 }&

21、lt;/p>　　};　　int size = 5;　　int start = 0;　　int dest = 1;　　int pathlen=0;　　int path

22、[maxPoint];　　double dist=0;　　CGraph g;　　double (*p)[maxPoint]=graph;　　g.SetGraph(graph,start,size);<p&

23、gt;　　while (1)　　{　　char InPutFlag;　　DisplayMessage();　　InPutFlag=getchar();

24、switch (InPutFlag)　　{　　case '1':　　g.Display();　　break;<p

25、>　　case '2':　　g.ChangeMatix(p);　　break;　　case '3':　　computer

26、Dijkstra(g,dest,size,path,pathlen);　　break;　　case '4':　　system("cls");

27、　break;　　case '5':　　exit(0);　　break;　　}<

28、;/p>　　cout<<"回車繼續(xù)"<<endl;　　getchar();　　getchar();　　}　　}</p&

29、gt;　　// Graph.cpp　　#include "stdafx.h"　　#include "Graph.h"　　//構造函數　　CGraph::CGraph(voi

30、d)　　{　　for( int i = 0 ; i < maxPoint ; i++ )　　{　　for( int j = 0 ; j < maxPoint ; j++ )</p

31、>　　graph[i][j] = -1;　　}　　startPoint = -1;　　size = -1;　　solved = false; //當前圖還沒有求解&

32、lt;b>　　}　　CGraph::~CGraph(void)　　{　　}　　//設置起始位置<p&g

33、t;　　bool CGraph::setStart(int start)　　{　　startPoint = start;　　return true;　　}

34、　　//設置求解矩陣和初始參數　　bool CGraph::SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size )　　{　　for( int i = 0 ; i < size ; i++

35、)　　{　　for( int j = 0 ; j < size ; j++ )　　graph[i][j] = g[i][j];　　}　　this-&

36、gt;startPoint = startPoint;　　this->size = size;　　solved = false;　　Dijkstra();　　return true;　　}

37、;　　//求解最短路徑　　bool CGraph::Dijkstra()　　{　　bool s[maxPoint];　　for( int j = 0 ;

38、j < size ; j++ )　　{　　dist[j] = graph[startPoint][j];　　s[j] = false;　　if( dist[j] < 0 ) //dist[i]<0，表示沒有路徑連接

39、結點startPoint 與結點j　　prev[j] = 0;　　else　　prev[j] = startPoint;　　}　　//

40、從起點出發(fā)　　dist[startPoint] = 0;　　s[startPoint] = true;　　for( int i = 0 ; i < size ; i++ )　　{<

41、;p>　　double temp;　　int u = startPoint;　　bool flag = false;　　for( int j = 0 ; j < size ; j++ )　　{<

42、;p>　　if( !s[j] )　　{　　//如果不是第一次比較，temp、u，都已經賦值，則　　if( flag )　　{　　if( dist[j

43、] > 0 && dist[j] < temp )　　{　　u = j;　　temp = dist[j];　　}

44、;　　}　　else　　{　　u = j;　　temp = dist[j];

45、　　flag = true;　　}　　}　　}　　s[u] = true;　　for( j =

46、0 ; j < size ; j++ )　　{　　if( !s[j] && graph[u][j] > 0 )　　{　　double newDist = dist[u]

47、 + graph[u][j];　　if( dist[j] < 0 || newDist < dist[j] )　　{　　dist[j] = newDist;　　prev[j] = u;<p&g

48、t;　　}　　}　　}　　}　　solved = true;　　return

49、true;　　}　　//顯示連接矩陣數據　　void CGraph::Display()　　{　　printf( " 當前地圖的鄰接矩

50、陣\n" );　　for( int i = 0 ; i < size ; i++ )　　{　　for( int j = 0 ; j < size ; j++ )　　{<

51、/p>　　printf( "%5.f" , graph[i][j] );　　}　　printf( "\n" );　　}<b

52、>　　}　　//修改連接矩陣數據　　void CGraph::ChangeMatix(double (*p)[maxPoint])　　{　　printf( "修改連接矩陣的參數，一次只能修改一個^^

53、\n" );　　printf( "輸入格式如下：先輸入橫坐標然后輸入縱坐標最后輸入數值\n" );　　int Xpoint=0,Ypoint=0,Pvalue=0;　　cout<<"請輸入橫坐標(從0開始)"<<endl;</p&

54、gt;　　cin>>Xpoint;　　cout<<"請輸入縱坐標(從0開始)"<<endl;　　cin>>Ypoint;　　cout<<"請輸入要修改的值"<<endl;</

55、p>　　cin>>Pvalue;　　p[Xpoint][Ypoint]=Pvalue;　　graph[Xpoint][Ypoint]=Pvalue;　　}　　//得到最短路徑&

56、lt;/b>　　double CGraph::GetBestWay( int dest , int path[] , int &pathLen)　　{　　int p = dest;　　int theway[maxPoin

57、t];　　int len = 0;　　while( p != startPoint )　　{　　theway[len] = p;　　p = prev[p];<p&

58、gt;　　len++;　　}　　theway[len] = startPoint;　　len++;　　for( int i = 0 , j = len - 1

59、 ; i < len ; i++ , j-- )　　path[i] = theway[j];　　pathLen = len;　　return dist[dest];　　}

60、;　　//　　//得到開始的點　　int CGraph::GetStartPoint()　　{　　return startPoint;

61、　　}　　//　　五、測試數據及其結果分析　　測試數據如下圖所示，是一個連接矩陣。　　0 10 -1 30 100　　-1

62、 0 50 -1 -1 　　-1 -1 0 -1 10　　-1 -1 20 0 60　　-1 -1 -1 -1 0　　測試結果如所示：<

63、;/b>　　0到0 的最短路徑為0 　　所經過節(jié)點為0　　0到1 的最短路徑為10 　　所經過節(jié)點為0 1　　0到2 的最短路徑為50 　　所

64、經過節(jié)點為0 3 2　　0到3 的最短路徑為30 　　所經過節(jié)點為0 3　　0到4 的最短路徑為60 　　所經過節(jié)點為0 3 2 4　　排序器（排序算法驗證及評價）

65、　一、題目與要求：問題描述：排序器（排序算法驗證及評價）要求：實現(xiàn)以下六種排序算法，將給定的不同規(guī)模大小的數據文件（data01.txt，data02.txt，data03.txt，data04.txt）進行排序，并將排序結果分別存儲到sorted01.txt，sorted02.txt，sorted03.txt和sorted04.txt文件中。1）、Shell排序； &#

66、160; 2）、Quick排序3）、錦標賽排序； 4）、堆排序5）、歸并排序； 6）、基數排序在實現(xiàn)排序算法1）~4）時，統(tǒng)計數據元素比較的次數和交換的次數，進而對這四種算法在特定數據條件下的效率進行分析和評判。二、題目分析：首先需要讀取4個不同大小文件中的數據，然后對其進行六種不同方法的排序，最后將結果儲存在不同的文件中。其次，需要定義

67、兩個變量分別來記錄前四種排序中數據的比較次數和移動次數，從而對這四種算法在特定數據條件下的效率進行分析和評判。三、函數說明及概要設計：以下為本程序中所涉及到的所有函數或重要變量，在設計思想中有具體解釋：/*全局變量*/int comp;//用來記錄數據間　　/*主函數*/int main()　　/*菜單選擇函數*/int

68、menu()　　/*從文件中讀取待排序數據*/int ReadInfo(LinkList *p,char *f)　　/*在屏幕上輸出每次排序的數據數目,比較次數,移動次數*/int PrintInfo(SqList *p)/*排序結果寫入文件中*/int WriteInfo(SqList *p,char *f)</p&g

69、t;　　/*希爾排序*/int Shell_Sort(SqList *p)　　/*希爾排序中的插入函數*/int Shell_Insert(SqList *p,int dk)　　/*快速排序*/int Quick_Sort(SqList *p)　　/*遞歸形式的快速排序函數*/int

70、 QSort(SqList *p,int low,int high)　　/*快排中計算樞軸位置的函數*/int Partition(SqList *p,int low,int high)　　/*錦標賽排序*/int Tournament_Sort(SqList *p)　　/*錦標賽排序中的調整函數*/int

71、 UpdateTree(DataNode *tree,int i)　　/*堆排序*/int Heap_Sort(SqList *H)　　/*堆排序中的篩選函數*/void HeapAdjust(SqList *H,int s,int m)　　/*歸并排序*/int Merg_Sort(SqList *p)&

72、lt;/p>　　/*遞歸形式的歸并排序函數*/int MSort(RedType SR[],RedType TR1[],int s,int t)　　/*歸并排序中將一維數組中前后相鄰的兩個有序序列歸并為一個有序序列*/int Merge(RedType SR[],RedType TR[],int i,int m,int n)

73、;　　/*基數排序*/int Radix_Sort(SqList *p,char *f1)　　/*鏈式基數排序中一趟收集函數*/int Collect(SLCell *r,int i,ArrType f,ArrType e)/*鏈式基數排序中一趟分配函數*/int Distribute(SLCell *r,int i,ArrType f,ArrType e)本程序采用的數據存儲結構有三

74、種:/*鏈式基數排序的數據結構*/typedef struct{ int keys[MAX_NUM_OF_KEY]; int info; int keysnum; int next;}SLCell;typedef struct{ SLCell *r; int keynum; int recnum;

75、}SLList;typedef int ArrType[RADIX];　　/*勝者樹數據結點類的定義*/ //歸并排序typedef struct{ RedType data; int key;//關鍵字項 int index;//滿二叉樹中的順序號 int active;//1,參選 0,不參選}DataNode;&l

76、t;/p>　　/*其余排序的數據結構*/typedef struct { int key;//關鍵字項 int info;//其他數據項}RedType;//記錄類型typedef struct { RedType *r;//[MAXSIZE+1] int length;//順序表長度

77、}SqList,*LinkList;　　1. 首先建立起改程序的框架:需要一個主函數: int main( )，在主函數中調用菜單函數int menu()即可。　　2．在菜單函數中，使屏幕上輸出以下語句，以便進行選擇。1.Shell排序2.Quick排序3.錦標賽排序4.堆排序5.歸并排序6.基數排序7.退出并根據選擇的結果來

78、確定要調用的排序函數，這里特別要指出的是，由于基數排序與其他排序的參數調用型式略有不同，所以本函數中定義了兩個函數指針int (*f)(SqList *),(*f1)(SqList *,char *)，分別用來指向基數排序函數和其他排序函數。確定了要進行的排序，接下來，在for(i=0;i<4;i++)這個循環(huán)中，每循環(huán)一次讀一個文件，排序后存儲并釋放內存空間，沒選擇一次排序的方法，則4個文件中的數據均可按照該方法排序

79、完成，直至選擇“7.退出”為止。　　3．希爾排序:它的基本思想是：先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。在希爾排序中，子序列的構成不是簡單地“逐段分割”，而是將相隔某個“增量”的記錄組成一個子序列。如在第一趟排序時的增量為7，即將相隔為7的元素編成一組進行直接插

80、入排序。第二趟排序時的增量為3，增量進一步縮小。由于在這兩趟的插入排序中在子序列中逆序的關鍵字是跳躍式地移動，從而使得在進行最后一趟增量為1的插入排序時，序列已基本有序，只要作少量比較和移動即可完成排序，因此希爾排序的時間復雜度較直接插入排序低。在該排序中，定義一個整型數組用來存儲增量increment[]，并且選取increment[i]=(k-1)/2。　　4．快速排序:快速排序是對冒泡

81、排序的一種改進。它的基本思想是：通過一躺排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一不部分的所有數據都要小，然后再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然后將所有比它的數都放到它前面，所有比它大的數都放到它后面，這個過程稱為一躺快速排序。一躺快速排序的算法是：

82、 1）、設置兩個變量I、J，排序開始的時候I：=1，J：=N； 2）以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]； 3）、從J開始向前搜索，即由后開始向前搜索（J：=J-1），找到第一個小于X的值，兩者交換； 4）、從I開始向后搜索，即由前開始向后搜索（I：=I+1），找到第一個大于X的值，兩者交換； 5）、重復第3、4步，直到I=J；例如

83、：待排序的數組A的值分別是：（初始關鍵數據X：=49） A[1] A[2] A[3] A[4] A[5] A[6]　　5．錦標賽排序:與體育淘汰賽類似，首先取得n個元素的關鍵字，進行兩兩比較，得到

84、60; n/2 個比較的優(yōu)勝者，將其作為第一次比較的結果保留下來，然后對這些元素再進行關鍵值的兩兩比較，…，如此重復，直到選出一個關鍵字最大的對象為止。每次兩兩比較的結果是把排序碼小者作為優(yōu)勝者上升到雙親結點,稱這種樹稱為勝者樹.位于最底層的葉結點叫做勝者樹的外結點.非葉結點稱為勝者樹的內結點.每個結點除了存放對象的排序碼data外,還存放了該對象是否要參選的標志active和該對象在滿二叉樹中的序號index.勝者樹數

85、據結點類的定義typedef struct{ RedType data; int key;//關鍵字項 int index;//滿二叉樹中的順序號 int active;//1,參選 0,不參選}DataNode;　　6．堆排序堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特征，使得在當前無序區(qū)中選取最大(或最小)

86、關鍵字的記錄變得簡單。 (1)用大根堆排序的基本思想 ① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區(qū) ② 再將關鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key ③ 由于交換后新的根R[1]可能違反堆性質，故應將當前無序區(qū)R[1..n-1]調整為堆。然后再次將R[1..n-1]中關鍵字最

87、大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。 …… 直到無序區(qū)只有一個元素為止。　　7．歸并排序本程序中采用遞歸的歸并排序算法。在遞歸的歸并排序方法中，首先要把整個待排序序列劃分為兩個長度大致相等的部分，分別

88、稱之為左子表和右子表。對這些子表分別遞歸地進行排序，然后再把排好序的兩個子表進行歸并。待排序對象序列的關鍵碼為 { 21, 25, 49, 25*,16, 08 }，先是進行子表劃分，待到子表中只有一個對象時遞歸到底。再是實施歸并，逐步退出遞歸調用的過程。 　　8．基數排序基數排序是采用“分配”與“收集”的辦法，用對多關鍵碼進行排序的思想實現(xiàn)對單關鍵碼進行排序的方法?；鶖蹬判虻?/p>

89、具體方法如下:1、根據數據項個位上的值，把所有的數據項分為10組；2、然后對這10組數據重新排列：把所有以0結尾的數據排在最前面，然后是結尾是1的數據項，照此順序直到以9結尾的數據，這個步驟稱為第一趟子排序。3、在第二趟子排序中，再次把所有的數據項分為10組，但是這一次是根據數據項十位上的值來分組的。這次分組不能改變先前的排序順序。也就是說，第二趟排序之后，從每一組數據項的內部來看，數據項的順序保持不變；4、然后再把10組數據項

90、重新合并，排在最前面的是十位上為0的數據項，然后是10位為1的數據項，如此排序直到十位上為9的數據項。5、對剩余位重復這個過程，如果某些數據項的位數少于其他數據項，那么認為它們的高位為0。　　五、六種排序算法的效率分析和評判1.Shell排序　　2. Quick排序　　3.

91、0;錦標賽排序　　4. 堆排序　　從對前四種排序中的數據比較次數和移動次數來看，快速排序最佳，其所需時間最省，但快速排序在比較壞的情況下的時間性能不如錦標賽排序和堆排序。當序列中的記錄“基本有序”或數據數目較小時，Shell排序是最佳的排序方法。由文件中的排序結果可知，希

92、爾排序、快速排序和堆排序都是不穩(wěn)定的排序方法。　　總結　　在本程序的調試過程中，最大的體會就是對時間復雜度和空間復雜度逐步的認識。一開始調試較小的文件時，還并未涉及到這兩個問題，所以只考慮到了算法的正確性，而難免忽略了程序中對時間、空間復雜度的要求。舉個例子，在調試第四個大小為32.3M的文件時，經常因為程序中一個極

93、小的錯誤而導致程序無限運行直至系統(tǒng)提示虛擬內存不足。在剛開始的編寫中，由于并沒有釋放內存空間，而導致經常需要重啟電腦來達到清理內存保證程序運行速度的目的。第五種排序方法，歸并，由于使用的是課本上所講的遞歸方法，而其中每遞歸一次都要申請一次內存空間，至今該排序對32.3M的文件仍然無法成功排序，可見空間復雜度的重要性，看來在一個程序中，算法的正確與否僅僅是程序好壞的一部分，而評估一個算法好壞的主要因素則是它的時間、空間復雜度

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

計算機數據結構課程設計---dijkstra算法和排序器

文檔簡介

溫馨提示

最新文檔

評論

計算機數據結構課程設計---dijkstra算法和排序器

文檔簡介

溫馨提示

最新文檔

評論

免費下載