一需求分析
1.執行環境
microsoft visual studio 2005
2.程式所實現的功能
對直接插入排序、折半插入排序、氣泡排序、簡單選擇排序、快速排序、堆排序、歸併排序演算法的演示,並且輸出每一趟的排序情況。
3.程式的輸入(包含輸入的資料格式和說明)
<1>排序種類三輸入
<2>排序數的個數的輸入
<3>所需排序的所有數的輸入
4.程式的輸出(程式輸出的形式)
<1>主選單的輸出
<2>每一趟排序的輸出,即排序過程的輸出
二設計說明
1.演算法設計思想
<1>交換排序(氣泡排序、快速排序)
交換排序的基本思想是:對排序表中的資料元素按關鍵字進行兩兩比較,如果發生逆序(即排列順序與排序後的次序正好相反),則兩者交換位置,直到所有資料元素都排好序為止。
<2>插入排序(直接插入排序、折半插入排序)
插入排序的基本思想是:每一次設法把乙個資料元素插入到已經排序的部分序列的合適位置,使得插入後的序列仍然是有序的。開始時建立乙個初始的有序序列,它只包含乙個資料元素。
然後,從這個初始序列出發不斷插入資料元素,直到最後乙個資料元素插到有序序列後,整個排序工作就完成了。
<3>選擇排序(簡單選擇排序、堆排序)
選擇排序的基本思想是:第一趟在有n個資料元素的排序表中選出關鍵字最小的資料元素,然後在剩下的n-1個資料元素中再選出關鍵字最小(整個資料表中次小)的資料元素,依次重複,每一趟(例如第i趟,i=1,…,n-1)總是在當前剩下的n-i+1個待排序資料元素中選出關鍵字最小的資料元素,作為有序資料元素序列的第i個資料元素。等到第n-1趟選擇結束,待排序資料元素僅剩下乙個時就不用再選了,按選出的先後次序所得到的資料元素序列即為有序序列,排序即告完成。
<4>歸併排序(兩路歸併排序)
兩路歸併排序的基本思想是:假設初始排序表有n個資料元素,首先把它看成是長度為1的首尾相接的n個有序子表(以後稱它們為歸併項),先做兩兩歸併,得n/2上取整個長度為2的歸併項(如果n為奇數,則最後乙個歸併項的長度為1);再做兩兩歸併,……,如此重複,最後得到乙個長度為n的有序序列。
2.程式的主要流程圖
3.程式的主要模組(要求對主要流程圖中出現的模組進行說明)
程式的主要模組主要分為主選單模組和排序演算法演示模組。
<1>主選單
主要功能:程式執行時,可使執行者根據提醒輸入相關操作,從而進入不同的排序方法或者退出。
<2>排序方法及輸出
根據執行者對排序的不同選擇,進入排序過程
a.直接插入排序:根據直接排序的演算法,輸出排序過程
b.折半插入排序:根據折半插入的演算法,輸出排序過程
c.氣泡排序:根據氣泡排序演算法,輸出排序過程
d.簡單選擇排序:根據簡單選擇排序的演算法,輸出排序過程
e.快速排序:根據快速排序的演算法,輸出排序過程
f.堆排序:根據堆排序的演算法,輸出排序過程
g.歸併排序:根據歸併排序的演算法,輸出排序過程
4. 程式的主要函式及其偽**說明
<1>模板類
主要說明程式中用到的類的定義
templateclass sortlist
//建構函式
sortlist(int n)
void insert(int i,type x)
~sortlist()//析構函式
void swap(type &x,type &y)//資料元素x和y交換位置
void bubblesort();//氣泡排序
void quicksort(int low,int high);//快速排序
void insertionsort();//直接插入排序
void binaryinsertsort();//折半插入排序
void selectsort();//簡單選擇排序
void heapsort();//堆排序
void mergesort(sortlist &table);//歸併排序
void filterdown(const int start);//建立最大堆
void mergepass(sortlist&sourcetable,sortlist&mergedtable,const int len);//一趟歸併
void merge(sortlist&sourcetable,sortlist&mergedtable,const int left,const int mid,const int right);//兩路歸併演算法
};<2>直接插入排序
直接插入排序的基本思想:開始時把第乙個資料元素作為初始的有序序列,然後從第二個資料元素開始依次把資料元素按關鍵字大小插入到已排序的部分排序表的適當位置。當插入第i(1以下是在順序表上實現的直接插入排序
在順序表上進行直接插入排序時,當插入第i(1偽**如下
template //直接插入排序
void sortlist::insertionsort()
arr[j+1]=temp;
cout<<"第"<<++num<<"趟排序結果為:";
for(int t=0;t cout< cout< }
num=0;
}<3>折半插入排序
折半插入排序的基本思想:設在排序表中有n個資料元素arr[0],arr[1],…,arr[n-1]。其中,arr[0],arr[1],…,arr[n-1]是已經排好序的部分資料元素序列,在插入arr[i]時,利用折半查詢方法尋找arr[i]的插入位置。
折半插入排序方法只能在順序表儲存結構實現。
偽**如下:
template //折半插入排序
void sortlist::binaryinsertsort()
for(int k=i-1;k>=left;k--)//向後移動
arr[k+1]=arr[k];
arr[left]=temp;
cout<<"第"<<++num<<"趟排序結果為:";
for(int t=0;tcout< cout< }
num=0;
}<4>氣泡排序
氣泡排序的基本思想是:設排序表中有n個資料元素。首先對排序表中第一,二個資料元素的關鍵字arr[0]和arr[1]進行比較。
如果前者大於後者,則進行交換;然後對第二,三個資料做同樣的處理;重複此過程直到處理完最後兩個相鄰的資料元素。我們稱之為一趟冒泡,它將關鍵字最大的元素移到排序表的最後乙個位置,其他資料元素一般也都向排序的最終位置移動。然後進行第二趟排序,對排序表中前n-1個元素進行與上述同樣的操作,其結果使整個排序表中關鍵字次大的資料元素被移到arr[n-2]的位置。
如此最多做n-1趟冒泡就能把所有資料元素排好序。
偽**如下:
template //氣泡排序
void sortlist:: bubblesort()
num=0;
}<5>簡單選擇排序(直接選擇排序)
直接選擇排序的演算法基本思想是:
a)開始時設i的初始值為0。
拓撲排序課程設計報告
演算法與資料結構 課程設計報告 題目 拓撲排序 一 問題描述 對乙個有向無環圖g進行拓撲排序,是將g中所有頂點排成乙個線性序列,使得圖中任意一對由某個集合上的乙個偏序得到該集合上的乙個全序,這個操作就稱之為拓撲排序。偏序集合中僅有部分成員之間顆比較,而全序指集合中全體成員之間均可比較,而由偏序定義得...
《C 課程設計》報告
課程設計題一 使用類和物件設計回應程式 一課題內容和要求 1 測試程式如下 假使類名為wel e void main void 2 測試程式的輸出結果如下 wel e thank you.輸入 how are you?輸出 how are you?輸入 fine,thank you.輸出 fine,...
C課程設計報告
課程名稱 c語言課程設計 課題名稱班級檔案管理系統 專業電子資訊 班級1502 學號 201501030232 姓名湛興 指導教師黃曉宇陳世清黃哲 2016年 7 月 3 日 湖南工程學院 課程設計任務書 課程名稱 c語言課程設計 課題班級檔案管理系統 專業班級電子資訊1502班 學生姓名湛興 學號...