版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、<p><b> 數(shù)據(jù)結(jié)構(gòu)課程論文</b></p><p> 設(shè)計題目:Dijkstra算法和排序器(排序算法驗證及評價)</p><p> 圖的Dijkstra算法</p><p><b> 一、課題內(nèi)容和要求</b></p><p> Dijkstra算法的實現(xiàn)和演示。<
2、;/p><p><b> 二、設(shè)計思路分析</b></p><p> Dijkstra算法的基本思路是:假設(shè)每個點都有一對標號 (dj, pj),其中dj是從起源點s到點j的最短路徑的長度 (從頂點到其本身的最短路徑是零路(沒有弧的路),其長度等于零);pj則是從s到j(luò)的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑算法的基本過程如下: 1) 初始化。起源
3、點設(shè)置為:① ds=0, ps為空;② 所有其他點: di=∞, pi=?;③ 標記起源點s,記k=s,其他所有點設(shè)為未標記的?! ?) 檢驗從所有已標記的點k到其直接連接的未標記的點j的距離,并設(shè)置:</p><p> dj=min[dj, dk+lkj]</p><p> 式中,lkj是從點k到j(luò)的直接連接距離?! ?) 選取下一個點。從所有未標記的結(jié)點中,選取dj 中最小的一
4、個i:</p><p> di=min[dj, 所有未標記的點j]</p><p> 點i就被選為最短路徑中的一點,并設(shè)為已標記的?! ?) 找到點i的前一點。從已標記的點中找到直接連接到點i的點j*,作為前一點,設(shè)置:</p><p><b> i=j*</b></p><p> 5) 標記點i。如果所有點已
5、標記,則算法完全推出,否則,記k=i,轉(zhuǎn)到2) 再繼續(xù)。</p><p><b> 三、概要設(shè)計 </b></p><p> 算法流程圖如下圖所示:</p><p> CGraph類的聲明部分如下所示:</p><p> #define maxPoint 100</p><p> cla
6、ss CGraph</p><p><b> {</b></p><p><b> public:</b></p><p> CGraph(void);</p><p> ~CGraph(void);</p><p> bool SetGraph( double g
7、[maxPoint][maxPoint] , int startPoint , int size );</p><p> bool Dijkstra();</p><p> void Display();</p><p> int GetStartPoint();</p><p> bool setStart(int start);&
8、lt;/p><p> void ChangeMatix(double (*p)[maxPoint]);</p><p> double GetBestWay( int dest , int path[] , int &pathLen );</p><p><b> private:</b></p><p>
9、bool solved;//標志當前圖是否已經(jīng)求解</p><p> double graph[maxPoint][maxPoint];//當前圖布局</p><p> int size;//地圖大小</p><p> int startPoint;//起點</p><p> double dist[maxPoint];//當前圖的解
10、</p><p> int prev[maxPoint];</p><p><b> };</b></p><p><b> 四、詳細設(shè)計</b></p><p> // Dijkstra2.cpp : Defines the entry point for the console appl
11、ication.</p><p><b> //</b></p><p> #include "stdafx.h"</p><p> #include "Graph.h"</p><p> // Dijkstra.cpp : 定義控制臺應(yīng)用程序的入口點。</p>
12、<p> void DisplayMessage()</p><p><b> {</b></p><p> printf( "☆☆☆☆☆☆最短路徑算法Dijkstra演示☆☆☆☆☆☆☆☆\n\n" );</p><p> printf("△1.連接矩陣顯示\n\n");</p
13、><p> printf("△2.修改連接矩陣\n\n");</p><p> printf("△3.求解最短路徑\n\n");</p><p> printf("△4.清空屏幕\n\n");</p><p> printf("△5.退出\n\n");<
14、/p><p> printf("請您輸入選項");</p><p><b> }</b></p><p> //求解最短路徑函數(shù)</p><p> void computerDijkstra(CGraph g,int dest,int size,int path[],int pathlen)<
15、;/p><p><b> {</b></p><p> printf( "----------------------------------------\n" );</p><p> double distanceLenth=0;</p><p> for( dest = 0 ; dest &l
16、t; size ; dest++ )</p><p><b> {</b></p><p> distanceLenth = g.GetBestWay( dest , path , pathlen );</p><p> printf( "從 %d 到 %d 的最短路徑長 %.f\n" , g.GetStartPoin
17、t() , dest , distanceLenth );</p><p> printf( "所經(jīng)結(jié)點為:\n" );</p><p> for( int i = 0 ; i < pathlen ; i++ )</p><p> printf( "%3d" , path[i] );</p><
18、p> printf( "\n----------------------------------------\n" );</p><p><b> }</b></p><p><b> }</b></p><p><b> //主函數(shù)</b></p>&
19、lt;p> void main()</p><p><b> {</b></p><p> //連接矩陣可以修改</p><p> double graph[][maxPoint] =</p><p><b> {</b></p><p> { 0 , 1
20、0 , -1 , 30 , 100 } ,</p><p> { -1 , 0 , 50 , -1 , -1 } ,</p><p> { -1 , -1 , 0 , -1 , 10 } ,</p><p> { -1 , -1 , 20 , 0 , 60 } ,</p><p> { -1 , -1 , -1 , -1 , 0 }&
21、lt;/p><p><b> };</b></p><p> int size = 5;</p><p> int start = 0;</p><p> int dest = 1;</p><p> int pathlen=0;</p><p> int path
22、[maxPoint];</p><p> double dist=0;</p><p><b> CGraph g;</b></p><p> double (*p)[maxPoint]=graph;</p><p> g.SetGraph(graph,start,size);</p><p&
23、gt;<b> while (1)</b></p><p><b> {</b></p><p> char InPutFlag;</p><p> DisplayMessage();</p><p> InPutFlag=getchar();</p><p>
24、switch (InPutFlag)</p><p><b> {</b></p><p><b> case '1':</b></p><p> g.Display();</p><p><b> break;</b></p><p
25、><b> case '2':</b></p><p> g.ChangeMatix(p);</p><p><b> break;</b></p><p><b> case '3':</b></p><p> computer
26、Dijkstra(g,dest,size,path,pathlen);</p><p><b> break;</b></p><p><b> case '4':</b></p><p> system("cls");</p><p><b>
27、 break;</b></p><p><b> case '5':</b></p><p><b> exit(0);</b></p><p><b> break;</b></p><p><b> }</b><
28、;/p><p> cout<<"回車繼續(xù)"<<endl;</p><p> getchar();</p><p> getchar();</p><p><b> }</b></p><p><b> }</b></p&
29、gt;<p> // Graph.cpp</p><p> #include "stdafx.h"</p><p> #include "Graph.h"</p><p><b> //構(gòu)造函數(shù)</b></p><p> CGraph::CGraph(voi
30、d)</p><p><b> {</b></p><p> for( int i = 0 ; i < maxPoint ; i++ )</p><p><b> {</b></p><p> for( int j = 0 ; j < maxPoint ; j++ )</p
31、><p> graph[i][j] = -1;</p><p><b> }</b></p><p> startPoint = -1;</p><p> size = -1;</p><p> solved = false; //當前圖還沒有求解</p><p>&
32、lt;b> }</b></p><p> CGraph::~CGraph(void)</p><p><b> {</b></p><p><b> }</b></p><p><b> //設(shè)置起始位置</b></p><p&g
33、t; bool CGraph::setStart(int start)</p><p><b> {</b></p><p> startPoint = start;</p><p> return true;</p><p><b> }</b></p><p>
34、 //設(shè)置求解矩陣和初始參數(shù)</p><p> bool CGraph::SetGraph( double g[maxPoint][maxPoint] , int startPoint , int size )</p><p><b> {</b></p><p> for( int i = 0 ; i < size ; i++
35、)</p><p><b> {</b></p><p> for( int j = 0 ; j < size ; j++ )</p><p> graph[i][j] = g[i][j];</p><p><b> }</b></p><p> this-&
36、gt;startPoint = startPoint;</p><p> this->size = size;</p><p> solved = false;</p><p> Dijkstra();</p><p> return true;</p><p><b> }</b>
37、;</p><p><b> //求解最短路徑</b></p><p> bool CGraph::Dijkstra()</p><p><b> {</b></p><p> bool s[maxPoint];</p><p> for( int j = 0 ;
38、j < size ; j++ )</p><p><b> {</b></p><p> dist[j] = graph[startPoint][j];</p><p> s[j] = false;</p><p> if( dist[j] < 0 ) //dist[i]<0,表示沒有路徑連接
39、結(jié)點startPoint 與 結(jié)點j</p><p> prev[j] = 0;</p><p><b> else</b></p><p> prev[j] = startPoint;</p><p><b> }</b></p><p><b> //
40、從起點出發(fā)</b></p><p> dist[startPoint] = 0;</p><p> s[startPoint] = true;</p><p> for( int i = 0 ; i < size ; i++ )</p><p><b> {</b></p><
41、;p> double temp;</p><p> int u = startPoint;</p><p> bool flag = false;</p><p> for( int j = 0 ; j < size ; j++ )</p><p><b> {</b></p><
42、;p> if( !s[j] )</p><p><b> {</b></p><p> //如果不是第一次比較,temp、u,都已經(jīng)賦值,則</p><p> if( flag )</p><p><b> {</b></p><p> if( dist[j
43、] > 0 && dist[j] < temp )</p><p><b> {</b></p><p><b> u = j;</b></p><p> temp = dist[j];</p><p><b> }</b></p>
44、;<p><b> }</b></p><p><b> else</b></p><p><b> {</b></p><p><b> u = j;</b></p><p> temp = dist[j];</p>
45、<p> flag = true;</p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p> s[u] = true;</p><p> for( j =
46、0 ; j < size ; j++ )</p><p><b> {</b></p><p> if( !s[j] && graph[u][j] > 0 )</p><p><b> {</b></p><p> double newDist = dist[u]
47、 + graph[u][j];</p><p> if( dist[j] < 0 || newDist < dist[j] )</p><p><b> {</b></p><p> dist[j] = newDist;</p><p> prev[j] = u;</p><p&g
48、t;<b> }</b></p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p> solved = true;</p><p> return
49、true;</p><p><b> }</b></p><p> //顯示連接矩陣數(shù)據(jù)</p><p> void CGraph::Display()</p><p><b> {</b></p><p> printf( " 當前地圖的鄰接矩
50、陣\n" );</p><p> for( int i = 0 ; i < size ; i++ )</p><p><b> {</b></p><p> for( int j = 0 ; j < size ; j++ )</p><p><b> {</b><
51、/p><p> printf( "%5.f" , graph[i][j] );</p><p><b> }</b></p><p> printf( "\n" );</p><p><b> }</b></p><p><b
52、> }</b></p><p> //修改連接矩陣數(shù)據(jù)</p><p> void CGraph::ChangeMatix(double (*p)[maxPoint])</p><p><b> {</b></p><p> printf( "修改連接矩陣的參數(shù),一次只能修改一個^^
53、\n" );</p><p> printf( "輸入格式如下:先輸入橫坐標 然后輸入縱坐標 最后輸入數(shù)值\n" );</p><p> int Xpoint=0,Ypoint=0,Pvalue=0;</p><p> cout<<"請輸入橫坐標(從0開始)"<<endl;</p&
54、gt;<p> cin>>Xpoint;</p><p> cout<<"請輸入縱坐標(從0開始)"<<endl;</p><p> cin>>Ypoint;</p><p> cout<<"請輸入要修改的值"<<endl;</
55、p><p> cin>>Pvalue;</p><p> p[Xpoint][Ypoint]=Pvalue;</p><p> graph[Xpoint][Ypoint]=Pvalue;</p><p><b> }</b></p><p><b> //得到最短路徑&
56、lt;/b></p><p> double CGraph::GetBestWay( int dest , int path[] , int &pathLen)</p><p><b> {</b></p><p> int p = dest;</p><p> int theway[maxPoin
57、t];</p><p> int len = 0;</p><p> while( p != startPoint )</p><p><b> {</b></p><p> theway[len] = p;</p><p> p = prev[p];</p><p&
58、gt;<b> len++;</b></p><p><b> }</b></p><p> theway[len] = startPoint;</p><p><b> len++;</b></p><p> for( int i = 0 , j = len - 1
59、 ; i < len ; i++ , j-- )</p><p> path[i] = theway[j];</p><p> pathLen = len;</p><p> return dist[dest];</p><p><b> }</b></p><p><b>
60、; //</b></p><p><b> //得到開始的點</b></p><p> int CGraph::GetStartPoint()</p><p><b> {</b></p><p> return startPoint;</p><p>
61、<b> }</b></p><p><b> //</b></p><p> 五、測試數(shù)據(jù)及其結(jié)果分析</p><p> 測試數(shù)據(jù)如下圖所示,是一個連接矩陣。</p><p> 0 10 -1 30 100</p><p> -1
62、 0 50 -1 -1 </p><p> -1 -1 0 -1 10</p><p> -1 -1 20 0 60</p><p> -1 -1 -1 -1 0</p><p><b> 測試結(jié)果如所示:<
63、;/b></p><p> 0到0 的最短路徑為0 </p><p><b> 所經(jīng)過節(jié)點為0</b></p><p> 0到1 的最短路徑為10 </p><p> 所經(jīng)過節(jié)點為0 1</p><p> 0到2 的最短路徑為50 </p><p> 所
64、經(jīng)過節(jié)點為0 3 2</p><p> 0到3 的最短路徑為30 </p><p> 所經(jīng)過節(jié)點為0 3</p><p> 0到4 的最短路徑為60 </p><p> 所經(jīng)過節(jié)點為0 3 2 4</p><p> 排序器(排序算法驗證及評價)</p><p>
65、 一、題目與要求:問題描述:排序器(排序算法驗證及評價)要 求:實現(xiàn)以下六種排序算法,將給定的不同規(guī)模大小的數(shù)據(jù)文件(data01.txt,data02.txt,data03.txt,data04.txt)進行排序,并將排序結(jié)果分別存儲到sorted01.txt,sorted02.txt,sorted03.txt和sorted04.txt文件中。1)、Shell排序;
66、160; 2)、Quick排序3)、錦標賽排序; 4)、堆排序5)、歸并排序; 6)、基數(shù)排序在實現(xiàn)排序算法1)~4)時,統(tǒng)計數(shù)據(jù)元素比較的次數(shù)和交換的次數(shù),進而對這四種算法在特定數(shù)據(jù)條件下的效率進行分析和評判。二、題目分析:首先需要讀取4個不同大小文件中的數(shù)據(jù),然后對其進行六種不同方法的排序,最后將結(jié)果儲存在不同的文件中。其次,需要定義
67、兩個變量分別來記錄前四種排序中數(shù)據(jù)的比較次數(shù)和移動次數(shù),從而對這四種算法在特定數(shù)據(jù)條件下的效率進行分析和評判。三、函數(shù)說明及概要設(shè)計:以下為本程序中所涉及到的所有函數(shù)或重要變量,在設(shè)計思想中有具體解釋:/*全局變量*/int comp;//用來記錄數(shù)據(jù)間</p><p> /*主函數(shù)*/int main()</p><p> /*菜單選擇函數(shù)*/int
68、menu()</p><p> /*從文件中讀取待排序數(shù)據(jù)*/int ReadInfo(LinkList *p,char *f)</p><p> /*在屏幕上輸出每次排序的數(shù)據(jù)數(shù)目,比較次數(shù),移動次數(shù)*/int PrintInfo(SqList *p)/*排序結(jié)果寫入文件中*/int WriteInfo(SqList *p,char *f)</p&g
69、t;<p> /*希爾排序*/int Shell_Sort(SqList *p)</p><p> /*希爾排序中的插入函數(shù)*/int Shell_Insert(SqList *p,int dk)</p><p> /*快速排序*/int Quick_Sort(SqList *p)</p><p> /*遞歸形式的快速排序函數(shù)*/int
70、 QSort(SqList *p,int low,int high)</p><p> /*快排中計算樞軸位置的函數(shù)*/int Partition(SqList *p,int low,int high)</p><p> /*錦標賽排序*/int Tournament_Sort(SqList *p)</p><p> /*錦標賽排序中的調(diào)整函數(shù)*/int
71、 UpdateTree(DataNode *tree,int i)</p><p> /*堆排序*/int Heap_Sort(SqList *H)</p><p> /*堆排序中的篩選函數(shù)*/void HeapAdjust(SqList *H,int s,int m)</p><p> /*歸并排序*/int Merg_Sort(SqList *p)&
72、lt;/p><p> /*遞歸形式的歸并排序函數(shù)*/int MSort(RedType SR[],RedType TR1[],int s,int t)</p><p> /*歸并排序中將一維數(shù)組中前后相鄰的兩個有序序列歸并為一個有序序列*/int Merge(RedType SR[],RedType TR[],int i,int m,int n)</p><p>
73、; /*基數(shù)排序*/int Radix_Sort(SqList *p,char *f1)</p><p> /*鏈式基數(shù)排序中一趟收集函數(shù)*/int Collect(SLCell *r,int i,ArrType f,ArrType e)/*鏈式基數(shù)排序中一趟分配函數(shù)*/int Distribute(SLCell *r,int i,ArrType f,ArrType e)本程序采用的數(shù)據(jù)存儲結(jié)構(gòu)有三
74、種:/*鏈式基數(shù)排序的數(shù)據(jù)結(jié)構(gòu)*/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];</p><p> /*勝者樹數(shù)據(jù)結(jié)點類的定義*/ //歸并排序typedef struct{ RedType data; int key;//關(guān)鍵字項 int index;//滿二叉樹中的順序號 int active;//1,參選 0,不參選}DataNode;&l
76、t;/p><p> /*其余排序的數(shù)據(jù)結(jié)構(gòu)*/typedef struct { int key;//關(guān)鍵字項 int info;//其他數(shù)據(jù)項}RedType;//記錄類型typedef struct { RedType *r;//[MAXSIZE+1] int length;//順序表長度
77、}SqList,*LinkList;</p><p> 1. 首先建立起改程序的框架:需要一個主函數(shù): int main( ),在主函數(shù)中調(diào)用菜單函數(shù)int menu()即可。</p><p> 2.在菜單函數(shù)中,使屏幕上輸出以下語句,以便進行選擇。1.Shell排序2.Quick排序3.錦標賽排序4.堆排序5.歸并排序6.基數(shù)排序7.退出并根據(jù)選擇的結(jié)果來
78、確定要調(diào)用的排序函數(shù),這里特別要指出的是,由于基數(shù)排序與其他排序的參數(shù)調(diào)用型式略有不同,所以本函數(shù)中定義了兩個函數(shù)指針int (*f)(SqList *),(*f1)(SqList *,char *),分別用來指向基數(shù)排序函數(shù)和其他排序函數(shù)。確定了要進行的排序,接下來,在for(i=0;i<4;i++)這個循環(huán)中,每循環(huán)一次讀一個文件,排序后存儲并釋放內(nèi)存空間,沒選擇一次排序的方法,則4個文件中的數(shù)據(jù)均可按照該方法排序
79、完成,直至選擇“7.退出”為止。</p><p> 3.希爾排序:它的基本思想是:先將整個待排記錄序列分割成為若干子序列分別進行直接插入排 序,待整個序列中的記錄“基本有序”時,再對全體記錄進行一次直接插入排序。 在希爾排序中,子序列的構(gòu)成不是簡單地“逐段分割”,而是將相隔某個“增量”的記錄組成一個子序列。如在第一趟排序時的增量為7,即將相隔為7的元素編成一組進行直接插
80、入排序。第二趟排序時的增量為3,增量進一步縮小。由于在這兩趟的插入排序中在子序列中逆序的關(guān)鍵字是跳躍式地移動,從而使得在進行最后一趟增量為1的插入排序時,序列已基本有序,只要作少量比較和移動即可完成排序,因此希爾排序的時間復雜度較直接插入排序低。在該排序中,定義一個整型數(shù)組用來存儲增量increment[],并且選取increment[i]=(k-1)/2。</p><p> 4.快速排序:快速排序是對冒泡
81、排序的一種改進。它的基本思想是:通過一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小,然后再按次方法對這兩部分數(shù)據(jù)分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數(shù)據(jù)變成有序序列。假設(shè)要排序的數(shù)組是A[1]……A[N],首先任意選取一個數(shù)據(jù)(通常選用第一個數(shù)據(jù))作為關(guān)鍵數(shù)據(jù),然后將所有比它的數(shù)都放到它前面,所有比它大的數(shù)都放到它后面,這個過程稱為一躺快速排序。一躺快速排序的算法是:
82、 1)、設(shè)置兩個變量I、J,排序開始的時候I:=1,J:=N; 2)以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù),賦值給X,即X:=A[1]; 3)、從J開始向前搜索,即由后開始向前搜索(J:=J-1),找到第一個小于X的值,兩者交換; 4)、從I開始向后搜索,即由前開始向后搜索(I:=I+1),找到第一個大于X的值,兩者交換; 5)、重復第3、4步,直到I=J; 例如
83、:待排序的數(shù)組A的值分別是:(初始關(guān)鍵數(shù)據(jù)X:=49) A[1] A[2] A[3] A[4] A[5] A[6]</p><p> 5.錦標賽排序:與體育淘汰賽類似,首先取得n個元素的關(guān)鍵字,進行兩兩比較,得到
84、60; n/2 個比較的優(yōu)勝者,將其作為第一次比較的結(jié)果保留下來,然后對這些元素再進行關(guān)鍵值的兩兩比較,…,如此重復,直到選出一個關(guān)鍵字最大的對象為止。每次兩兩比較的結(jié)果是把排序碼小者作為優(yōu)勝者上升到雙親結(jié)點,稱這種樹稱為勝者樹.位于最底層的葉結(jié)點叫做勝者樹的外結(jié)點.非葉結(jié)點稱為勝者樹的內(nèi)結(jié)點.每個結(jié)點除了存放對象的排序碼data外,還存放了該對象是否要參選的標志active和該對象在滿二叉樹中的序號index.勝者樹數(shù)
85、據(jù)結(jié)點類的定義typedef struct{ RedType data; int key;//關(guān)鍵字項 int index;//滿二叉樹中的順序號 int active;//1,參選 0,不參選}DataNode;</p><p> 6.堆排序堆排序利用了大根堆(或小根堆)堆頂記錄的關(guān)鍵字最大(或最小)這一特征,使得在當前無序區(qū)中選取最大(或最小)
86、關(guān)鍵字的記錄變得簡單。 (1)用大根堆排序的基本思想 ① 先將初始文件R[1..n]建成一個大根堆,此堆為初始的無序區(qū) ② 再將關(guān)鍵字最大的記錄R[1](即堆頂)和無序區(qū)的最后一個記錄R[n]交換,由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n],且滿足R[1..n-1].keys≤R[n].key ③ 由于交換后新的根R[1]可能違反堆性質(zhì),故應(yīng)將當前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最
87、大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換,由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n],且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys,同樣要將R[1..n-2]調(diào)整為堆。 …… 直到無序區(qū)只有一個元素為止。</p><p> 7.歸并排序本程序中采用遞歸的歸并排序算法。在遞歸的歸并排序方法中,首先要把整個待排序序列劃分為兩個長度大致相等的部分,分別
88、稱之為左子表和右子表。對這些子表分別遞歸地進行排序,然后再把排好序的兩個子表進行歸并。待排序?qū)ο笮蛄械年P(guān)鍵碼為 { 21, 25, 49, 25*,16, 08 },先是進行子表劃分,待到子表中只有一個對象時遞歸到底。再是實施歸并,逐步退出遞歸調(diào)用的過程。 </p><p> 8.基數(shù)排序基數(shù)排序是采用“分配”與“收集”的辦法,用對多關(guān)鍵碼進行排序的思想實現(xiàn)對單關(guān)鍵碼進行排序的方法。基數(shù)排序的
89、具體方法如下:1、根據(jù)數(shù)據(jù)項個位上的值,把所有的數(shù)據(jù)項分為10組;2、然后對這10組數(shù)據(jù)重新排列:把所有以0結(jié)尾的數(shù)據(jù)排在最前面,然后是結(jié)尾是1的數(shù)據(jù)項,照此順序直到以9結(jié)尾的數(shù)據(jù),這個步驟稱為第一趟子排序。3、在第二趟子排序中,再次把所有的數(shù)據(jù)項分為10組,但是這一次是根據(jù)數(shù)據(jù)項十位上的值來分組的。這次分組不能改變先前的排序順序。也就是說,第二趟排序之后,從每一組數(shù)據(jù)項的內(nèi)部來看,數(shù)據(jù)項的順序保持不變;4、然后再把10組數(shù)據(jù)項
90、重新合并,排在最前面的是十位上為0的數(shù)據(jù)項,然后是10位為1的數(shù)據(jù)項,如此排序直到十位上為9的數(shù)據(jù)項。5、對剩余位重復這個過程,如果某些數(shù)據(jù)項的位數(shù)少于其他數(shù)據(jù)項,那么認為它們的高位為0。</p><p> 五、六種排序算法的效率分析和評判1.Shell排序</p><p> 2. Quick排序</p><p><b> 3.
91、0;錦標賽排序</b></p><p><b> 4. 堆排序</b></p><p> 從對前四種排序中的數(shù)據(jù)比較次數(shù)和移動次數(shù)來看,快速排序最佳,其所需時間最省,但快速排序在比較壞的情況下的時間性能不如錦標賽排序和堆排序。當序列中的記錄“基本有序”或數(shù)據(jù)數(shù)目較小時,Shell排序是最佳的排序方法。 由文件中的排序結(jié)果可知,希
92、爾排序、快速排序和堆排序都是不穩(wěn)定的排序方法。</p><p><b> 總結(jié)</b></p><p> 在本程序的調(diào)試過程中,最大的體會就是對時間復雜度和空間復雜度逐步的認識。一開始調(diào)試較小的文件時,還并未涉及到這兩個問題,所以只考慮到了算法的正確性,而難免忽略了程序中對時間、空間復雜度的要求。舉個例子,在調(diào)試第四個大小為32.3M的文件時,經(jīng)常因為程序中一個極
93、小的錯誤而導致程序無限運行直至系統(tǒng)提示虛擬內(nèi)存不足。在剛開始的編寫中,由于并沒有釋放內(nèi)存空間,而導致經(jīng)常需要重啟電腦來達到清理內(nèi)存保證程序運行速度的目的。 第五種排序方法,歸并,由于使用的是課本上所講的遞歸方法,而其中每遞歸一次都要申請一次內(nèi)存空間,至今該排序?qū)?2.3M的文件仍然無法成功排序,可見空間復雜度的重要性,看來在一個程序中,算法的正確與否僅僅是程序好壞的一部分,而評估一個算法好壞的主要因素則是它的時間、空間復雜度
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--排序算法
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---排序算法比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--排序算法比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--排序算法演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---排序算法的實現(xiàn)
- 拓撲排序(算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計)
- 計算機畢業(yè)論文數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告--dijkstra算法求最短路徑
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計----內(nèi)部排序算法性能分析
- 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序算法演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-拓撲排序
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--內(nèi)部排序算法的比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--幾種排序算法的演示
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告--排序
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-拓撲排序
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---排序綜合
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告---幾種排序算法的演示
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---希爾排序,冒泡排序,快速排序
- 大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計排序算法演示系統(tǒng)58165
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計--冒泡排序法
評論
0/150
提交評論