數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告--內(nèi)部排序算法的性能分析

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：16 大?。?55.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

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

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　一、課程設(shè)計概述：　　本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計共完成二個題：a.教學(xué)計劃編制問題b.內(nèi)部排序算法的性能分析　　使用語言：C　　編譯環(huán)境：TC3.0 / VC6.0

2、;　　二、課程設(shè)計題目一　　[實驗內(nèi)容]　　教學(xué)計劃編制問題　　[問題描述]　　答學(xué)的每個專業(yè)都要制定教學(xué)計劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)

3、年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限值均相等。每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學(xué)期。試在這樣的前提下設(shè)計一個教學(xué)計劃編制程序　　[需求分析] 　　輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每

4、門課的課程號（固定占3位的字母數(shù)字串）、學(xué)分和直接先修課的課程號。　　允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負擔盡量均勻；二是使課程盡可能地集中在前幾個學(xué)期中。　　若根據(jù)給定的條件問題無解，則報告適當?shù)男畔?；否則將教學(xué)計劃輸出到用戶指定的文件中。計劃的表格格式自行設(shè)計。

5、[概要設(shè)計]　　md init() /*初始化教學(xué)計劃*/　　void select (int quee[],int i,int j,md a) /*使課程集中在前面*/　　void arrage(md a) /*教學(xué)計劃函數(shù)*/<b

6、>　　[流程圖]　　[詳細設(shè)計]　　#include<stdio.h>　　#include <stdlib.h>　　#define NULL 0

7、;　　#define maxsize 100　　typedef struct stu　　{　　int number;　　int score;　　struct stu *next;</p

8、>　　}node;　　typedef struct　　{　　int vex_num;　　int vex_sco;<b&g

9、t;　　int have;　　node *first;　　}sd;　　typedef struct　　{　　sd arry[maxsi

10、ze];　　int max_class;　　int max_term;　　int score_limit;　　}md;　　md init()</p&

11、gt;　　{　　int i,x,c;　　md a;　　node *p;　　printf("enter class total:

12、");　　scanf("%d",&a.max_class);　　printf("enter term total:");　　scanf("%d",&a.max_term);　　print

13、f("enter score limit:");　　scanf("%d",&a.score_limit);　　printf("enter class arrange \n");　　for (i=1;i<=a.max_class;i++)&l

14、t;/p>　　a.arry[i].first=NULL;　　for(i=1;i<=a.max_class;i++)　　{　　printf("enter %i class number and score:",i);<

15、/p>　　scanf("%d %d",&a.arry[i].vex_num,&a.arry[i].vex_sco);　　printf("enter %i prior class:",i);　　c=0;<p

16、>　　do　　{　　scanf("%d",&x);　　if (x>0)　　{&l

17、t;/p>　　p=(node *)malloc(sizeof(node));　　p->number=a.arry[i].vex_num;　　p->next=a.arry[x].first;　　a.arry[x].first=p;&l

18、t;b>　　c++;　　}　　}while(x>0);　　a.arry[i].have=c;　　}　　r

19、eturn a;　　}　　/*void disp(md a)　　{　　node *p;<b

20、>　　int i;　　for (i=1;i<=a.max_class;i++)　　{　　printf("%d",a.arry[i].vex_num);　　p=a.arry[i].fi

21、rst;　　while(p!=NULL)　　{　　printf("%d",a.arry[p->number].vex_num);　　p=p->next;<

22、b>　　}　　printf("\n");　　}　　} */　　void select (int quee[],int i,int j,md a)<

23、;/p>　　{　　int k,temp,min;　　min=i;　　for(k=i+1;k<=j;k++)　　if (a.arry[quee[k]].vex_sc

24、o<a.arry[quee[min]].vex_sco)　　min=k;　　if(min!=i)　　{　　temp=quee[i];　　quee[i

25、]=quee[min];　　quee[min]=temp;　　}　　}　　void arrage(md a)　　{&

26、lt;/p>　　int quee[maxsize],front,bare,i,j,total_score;　　node *p;　　front=bare=0;　　j=1;

27、　　for(i=1;i<=a.max_class;i++)　　if (a.arry[i].vex_num!=0&&a.arry[i].have==0)　　quee[++bare]=a.arry[i].vex_num;　　printf("\n %d term study:"

28、,j++);　　total_score=0;　　while(front!=bare)　　{　　select(quee,front+1,bare,a);　　if (total_score+a.a

29、rry[quee[front+1]].vex_sco<=a.score_limit)　　{　　printf("%d",a.arry[quee[front]].vex_num);　　a.arry[quee[front]].vex_num=0;</

30、p>　　total_score+=a.arry[quee[front]].vex_sco;　　p=a.arry[quee[front]].first;　　while(p!=NULL)　　{　　a.arry[

31、p->number].have--;　　if (a.arry[p->number].have==0)　　quee[++bare]=a.arry[p->number].vex_num;　　p=p->next;　　}

32、;　　}　　else　　{　　total_score=0;　　printf(" \n%d term stu

33、dy:",j++);　　}　　}　　}　　main()<b&g

34、t;　　{　　md h;　　h=init();　　arrage(h);　　}

35、　[調(diào)試分析]　　問題：　　現(xiàn)象：最后結(jié)果存在問題，無法提供內(nèi)存　　原因：函數(shù)的參數(shù)沒有寫正確　?。?[運行結(jié)果及分析]　　課程設(shè)計題目二</b&g

36、t;　　[實驗內(nèi)容]　　內(nèi)部排序算法的性能分析　　[問題描述]　　。設(shè)計一個測試程序比較幾種內(nèi)部排序算法的關(guān)鍵字比較次數(shù)和移動次數(shù)以取得直觀感受<b

37、>　　[需求分析] 　　(1)對起泡排序、直接排序、簡單選擇排序、快速排序、希爾排序、堆排序算法進行比較；　　(2)待排序表的表長不小于100，表中數(shù)據(jù)隨機產(chǎn)生，至少用5組不同數(shù)據(jù)作比較，比較指標有：關(guān)鍵字參加比較次數(shù)和關(guān)鍵字的移動次數(shù)（關(guān)鍵字交換記為3次移動）；　　(3)輸出比較結(jié)

38、果。　　[概要設(shè)計]　　main()　　SqList L;　　addlist(L);　　qipao

39、(L);　　InsertSort(L);　　SelectSort(L);　　QuickSort(L);　　addlist(L); 　　MergeSort(L);<

40、b>　　[流程圖]　　[詳細設(shè)計]　　#include<stdio.h> 　　#include<stdlib.h>　　#include<string.h>

41、;　　#include<time.h>　　#define LIST_INIT_SIZE 50000　　int bj1,yd1,n;　　clock_t start_t,end_t;　　typedef struct &

42、lt;p>　　{　　int key; 　　}ElemType;　　typedef struct 　　{　　El

43、emType *elem;　　int length;　　}SqList;　　void addlist(SqList &L)　　{

44、　　int i;　　a: printf("請輸入你要輸入的個數(shù):");　　scanf("%d",&n);　　if(n>50000)　　{

45、　　printf("超出范圍重新輸入!!!\n");　　goto a;　　}　　L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));&l

46、t;/p>　　if(!L.elem)exit(0);　　L.length=0;　　for(i=1;i<n+1;i++)　　{　　b: L.elem[i].key=rand();

47、　　if(L.elem[i].key>30000)goto b;　　++L.length;　　}　　}　　void SelectSort(SqList &L)//

48、選擇　　{　　start_t=clock();　　int i,j,k,bj=0,yd=0;　　for(i=1;i<L.length;i++)　　{&

49、lt;/p>　　k=i;　　for(j=i+1;j<L.length;j++)　　{　　bj++;　　if(L.elem[j

50、].key<L.elem[k].key)k=j;　　}　　if(i!=k)　　{　　L.elem[0].key=L.elem[i].key;</p

51、>　　L.elem[i].key=L.elem[k].key;　　L.elem[k].key=L.elem[0].key;　　yd+=3;　　}　　}

52、　　end_t=clock();　　printf("比較次數(shù)為 %d移動次數(shù)為 %d\n",bj,yd);　　printf("排序用時為 %f\n",float(end_t-start_t)/CLK_TCK);<

53、/p>　　}　　void qipao(SqList &L)//起泡　　{　　start_t=clock();　　int i=1,j,bj=0,yd=0;<

54、/p>　　while(i<L.length)　　{　　for(j=1;j<L.length;j++)　　{　　bj++;

55、;　　if(L.elem[j].key>L.elem[j+1].key)　　{　　L.elem[0].key=L.elem[j].key;　　L.elem[j].key=L.elem[j+1].key;&

56、lt;p>　　L.elem[j+1].key=L.elem[0].key;　　yd+=3;　　}　　}　　i++;

57、　　}　　end_t=clock();　　printf("比較次數(shù)為 %d移動次數(shù)為 %d\n",bj,yd);　　printf("排序用時為 %f\n",f

58、loat(end_t-start_t)/CLK_TCK);　　}　　void InsertSort(SqList &L)//直接插入　　{　　start_t=clock();</p&

59、gt;　　int i,j,yd=0,bj=0;　　for(i=2;i<=L.length;i++)　　{　　if(L.elem[i].key<L.elem[i-1].key)　　{&

60、lt;/b>　　L.elem[0].key=L.elem[i].key;　　yd++;　　j=i-1;　　bj++;<p&

61、gt;　　while(L.elem[0].key<L.elem[j].key)　　{　　L.elem[j+1].key=L.elem[j].key;　　j--;　　yd++

62、;　　bj++;　　}　　L.elem[j+1].key=L.elem[0].key;　　yd++;<p&g

63、t;　　}　　}　　end_t=clock();　　printf("比較次數(shù)為 %d移動次數(shù)為 %d\n",bj,yd);　　printf("

64、排序用時為 %f\n",float(end_t-start_t)/CLK_TCK);　　}　　void xier(SqList &L)//希爾　　{　　start_t

65、=clock();　　int i,d=L.length/2,j,w=0,k,yd=0,bj=0;　　while(w<d)　　{　　w=1;　　for

66、(i=w;i<L.length;i=i+d)　　{　　k=i;　　for(j=i+d;j<L.length;j=j+d)　　{

67、　　if(L.elem[i].key>L.elem[j].key)　　{　　k=j;　　bj++;　　}<

68、/b>　　}　　if(i!=k)　　{　　L.elem[0].key=L.elem[i].key;　　L.el

69、em[i].key=L.elem[k].key;　　L.elem[k].key=L.elem[0].key;　　yd+=3;　　}　　w++;</p&g

70、t;　　}　　d=d/2;　　w=1;　　}　　end_t=clock();

71、　　printf("比較次數(shù)為 %d移動次數(shù)為 %d\n",bj,yd);　　printf("排序用時為 %f\n",float(end_t-start_t)/CLK_TCK);　　}<p&g

72、t;　　void BeforeSort()　　{　　yd1=0,bj1=0;　　}　　void display(int m,int n)

73、　　{　　printf("比較次數(shù)為 %d移動次數(shù)為 %d\n",m,n);　　}　　int Partition(SqList &L,int low,int high)//快速排序

74、　　{　　int pivotkey;　　L.elem[0]=L.elem[low];　　yd1++;　　pivotkey=L.elem[low].key;

75、　　while (low<high) 　　{　　yd1++;　　while(low<high&&L.elem[high].key>=pivotkey)<p

76、>　　--high;　　L.elem[low]=L.elem[high];　　bj1++;　　yd1++;　　while (low<high&am

77、p;&L.elem[low].key<=pivotkey)　　++low;　　L.elem[high]=L.elem[low];　　bj1++;　　yd1++;&l

78、t;/b>　　}　　L.elem[low]=L.elem[0];　　yd1++;　　return low;　　}

79、;　　void QSort(SqList &L,int low,int high)　　{ 　　int pivotloc;　　if(low<high)　　{&l

80、t;/b>　　pivotloc=Partition(L,low,high);　　QSort(L,low,pivotloc-1);　　QSort(L,pivotloc+1,high);　　}

81、;　　}　　void QuickSort(SqList &L)　　{　　start_t=clock();　　BeforeSort();　　QSor

82、t(L,1,L.length);　　display(yd1,bj1);　　end_t=clock();　　printf("排序用時為 %f\n",float(end_t-start_t)/CLK_TCK);　　}</

83、b>　　void Merge(ElemType R[],ElemType R1[],int low,int m,int high)//歸并　　{　　int i=low, j=m+1, k=low;　　while(i<=m&

84、amp;&j<=high)　　{　　if(R[i].key<=R[j].key)　　{　　bj1++;<p&

85、gt;　　R1[k]=R[i];　　yd1++;　　i++;　　k++;　　}

86、　　else　　{　　bj1++;　　R1[k]=R[j];　　yd1++;&

87、lt;b>　　j++;　　k++;　　}　　}　　while(i<=m)<b&

88、gt;　　{　　R1[k]=R[i];　　yd1++;　　i++;　　k++;

89、　　}　　while(j<=high)　　{　　R1[k]=R[j];　　yd1++;　　j++;</b

90、>　　k++;　　}　　}　　void MergePass(ElemType R[],ElemType R1[],int length, int n)&

91、lt;/p>　　{ 　　int i=0,j;　　while(i+2*length-1<n)　　{ 　　Merge(R,R1,i,i+length-1,i+2*

92、length-1);　　i=i+2*length;　　}　　if(i+length-1<n-1)　　Merge(R,R1,i,i+length-1,n-1);　　els

93、e　　for(j=i;j<n;j++)　　R1[j]=R[j];　　}　　void MSort(ElemType R[],ElemType R1[],int n)&l

94、t;b>　　{ 　　int length=1;　　while (length<n)　　{　　MergePass(R,R1,length,n);　　length=

95、2*length;　　MergePass(R1,R,length,n);　　length=2*length;　　}　　}　　void MergeSort(

96、SqList &L)　　{　　start_t=clock();　　BeforeSort();　　MSort(L.elem,L.elem,L.length);　　display(yd1,

97、bj1);　　end_t=clock();　　printf("排序用時為 %f\n",float(end_t-start_t)/CLK_TCK);　　}　　void main()

98、　　{　　SqList L;　　addlist(L);　　printf("起泡排序: \n");　　qipao(L);</

99、b>　　addlist(L);　　printf("直插排序: \n");　　InsertSort(L);　　addlist(L);　　printf("選擇排序: \n&q

100、uot;);　　SelectSort(L);　　addlist(L);　　printf("希爾排序: \n");　　xier(L);　　addlist(L);&

101、lt;/p>　　printf("快速排續(xù): \n");　　QuickSort(L);　　addlist(L); 　　printf("歸并排序: \n");　　MergeSort(L

102、);　　}　　[運行結(jié)果及分析]　　四、課程設(shè)計心得 　　一周的課程設(shè)計結(jié)束了，從課程設(shè)計的學(xué)習(xí)過程結(jié)束了，一開始，我并不知道要學(xué)這門課，我一直打算復(fù)習(xí)好考試

103、的科目的，所以說是實話，我剛開始的時候，真的是很懊惱，很糾結(jié)?？墒亲屑毾胂氩还芪以敢饣蛘卟辉敢?，我都必須學(xué)習(xí)，這是我的責(zé)任，我不可推卸。我唯一可以做的就是好好學(xué)習(xí)，更好的安排好我的學(xué)習(xí)時間，更加有計劃的利用好我的時間。有句話說的好，時間是擠出來的。而且漸漸地我明白了一個道理，環(huán)境一直在改變，沒有人知道未來的自己會遭遇什么樣的事情，惟有發(fā)展好自己才是最根本的，最有效的辦法。還有就是，課程設(shè)計這門課，讓我體會到會編寫有用的程序是多么的充實，

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告--內(nèi)部排序算法的性能分析

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告--內(nèi)部排序算法的性能分析

文檔簡介

溫馨提示

最新文檔

評論

免費下載