算法設(shè)計(jì)及分析實(shí)驗(yàn)報(bào)告-模板

1、-. z.實(shí)驗(yàn)報(bào)告（2016/2017學(xué)年 第一學(xué)期）課程名稱算法分析與設(shè)計(jì)實(shí)驗(yàn)名稱分治策略實(shí)驗(yàn)時(shí)間2016年10月18日指導(dǎo)單位計(jì)算機(jī)學(xué)院軟件教學(xué)中心指導(dǎo)教師季一木學(xué)生周文超班級(jí)*B14041527學(xué)院(系)計(jì)算機(jī)學(xué)院、軟件學(xué)院專 業(yè)軟件工程-. z.實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)名稱分治策略指導(dǎo)教師季一木實(shí)驗(yàn)類型驗(yàn)證實(shí)驗(yàn)學(xué)時(shí)2實(shí)驗(yàn)時(shí)間實(shí)驗(yàn)?zāi)康暮腿蝿?wù)1.理解分治法的算法思想，閱讀實(shí)現(xiàn)書上已有的部分程序代碼并完善程序，加深對(duì)分治法的算法原理及實(shí)現(xiàn)過(guò)程的理解。 2.用分治法實(shí)現(xiàn)一組無(wú)序序列的兩路合并排序和快速排序。要求清楚合并排序及快速排序的基本原理，編程實(shí)現(xiàn)分別用這兩種方法將輸入的一組無(wú)序序列排序?yàn)橛行蛐?/p>

2、列后輸出。 實(shí)驗(yàn)環(huán)境(實(shí)驗(yàn)設(shè)備)算法設(shè)計(jì)與分析課本筆記本電腦 VC+6.0三、實(shí)驗(yàn)原理及容（包括操作過(guò)程、結(jié)果分析等）實(shí)驗(yàn)原理運(yùn)用分治法 ：無(wú)序-部分有序-整體有序歸并排序中分”與合”的過(guò)程是結(jié)合在一起的，即每一趟都在做分” 與合”的工作，并不是先分”完再合” 基本程序兩路合并排序#includeclass SortableListpublic:SortableList(int mSize) /構(gòu)造函數(shù)ma*Size = mSize;l = new intma*Size;n = 0;SortableList()deletel; /析構(gòu)函數(shù)void Input();void Merge(int

3、left,int mid,int right);void MergeSort();void MergeSort(int left,int right);void Output();private:int *l; /動(dòng)態(tài)生成一維數(shù)組int ma*Size; /線性表的最大表長(zhǎng)int n; /線性表的實(shí)際長(zhǎng)度;void SortableList:Input()for(int i = 0;ili;n+;void SortableList:Merge(int left,int mid,int right)int *temp = new intright-left+1;int i = left,j =

4、mid +1,k = 0;while(i=mid)&(j=right)if(li=lj)tempk+=li+;elsetempk+=lj+;while(i=mid)tempk+=li+;while(j=right)tempk+=lj+;for(i = 0,k=left;k=right;)lk+=tempi+;void SortableList:MergeSort()MergeSort(0,n-1);void SortableList:MergeSort(int left,int right)if(leftright)/若序列的長(zhǎng)度超過(guò)1，則劃分成兩個(gè)子序列int mid = (left+rig

5、ht)/2;/將待排序的序列一分為二MergeSort(left,mid);/對(duì)左序列排序 MergeSort(mid+1,right);/對(duì)右序列排序Merge(left,mid,right);/將兩個(gè)有序子序列合并成一個(gè)有序序列void SortableList:Output()for(int i = 0;ima*Size;i+)coutli ;void main()SortableList l(10);cout請(qǐng)輸入10個(gè)數(shù)：endl;l.Input();l.MergeSort();cout排序后是：endl;l.Output();（二）快速排序#includeclass Sortabl

6、eListpublic:SortableList(int mSize) /構(gòu)造函數(shù)ma*Size = mSize;l = new intma*Size;n = 0;SortableList()deletel; /析構(gòu)函數(shù)void Input();void Swap(int i,int j);int Partition(int left,int right);void QuickSort(int left,int right);void QuickSort();void Output();private:int *l; /動(dòng)態(tài)生成一維數(shù)組int ma*Size; /線性表的最大表長(zhǎng)int n;

7、/線性表的實(shí)際長(zhǎng)度;void SortableList:Input()for(int i = 0;ili;n+;void SortableList:Swap(int i,int j)int c = li;li = lj;lj = c;int SortableList:Partition(int left,int right)/前置條件：left=rightint i = left,j = right + 1; dodo i+;while(lilleft);if(ij)Swap(i,j);while(ij);Swap(left,j);return j;void SortableList:Quic

8、kSort()QuickSort(0,n-1);void SortableList:QuickSort(int left,int right)if(leftright) /當(dāng)序列長(zhǎng)度大于1時(shí)，需進(jìn)行分割int j = Partition(left,right);/對(duì)left,right圍的序列進(jìn)行分劃QuickSort(left,j-1);/對(duì)左子序列實(shí)施快速排序QuickSort(j+1,right);/對(duì)右子序列實(shí)施快速排序void SortableList:Output()for(int i = 0;ima*Size;i+)coutli ;void main()SortableList l(10);cout請(qǐng)輸入10個(gè)數(shù)：endl;l.Input();l.QuickSort();cout排序后是：endl;l.Output();實(shí)驗(yàn)結(jié)果兩路合并排序快速排序六、實(shí)驗(yàn)小結(jié)（包括問(wèn)題和解決方法、心得體會(huì)等） 合并排序的基本運(yùn)算是把兩