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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告教學(xué)計劃編制問題內(nèi)部排序算法的性能分析 學(xué)院（系）： 數(shù)學(xué)與統(tǒng)計學(xué)院 班 級： 110010101 學(xué)生姓名： 楊曉格 學(xué) 號： 11001010129 指導(dǎo)教師： 韓逢慶 時 間： 從2011年12月31日 到2012年1月 6日一、課程設(shè)計概述：本次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計共完成二個題：a.教學(xué)計劃編制問題b.內(nèi)部排序算法的性能分析使用語言：C編譯環(huán)境：TC3.0 / VC6.0二、課程設(shè)計題目一實驗內(nèi)容 教學(xué)計劃編制問題問題描述答學(xué)的每個專業(yè)都要制定教學(xué)計劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限值均相等。每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學(xué)期。試在這樣的前提下設(shè)計一個教學(xué)計劃編制程序 需求分析 （1） 輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號（固定占3位的字母數(shù)字串）、學(xué)分和直接先修課的課程號。（2） 允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個學(xué)期中。（3） 若根據(jù)給定的條件問題無解，則報告適當?shù)男畔ⅲ环駝t將教學(xué)計劃輸出到用戶指定的文件中。計劃的表格格式自行設(shè)計。 概要設(shè)計md init() /*初始化教學(xué)計劃*/void select (int quee,int i,int j,md a) /*使課程集中在前面*/void arrage(md a) /*教學(xué)計劃函數(shù)*/流程圖初始化教學(xué)課程數(shù)學(xué)期數(shù)學(xué)分上限輸入后續(xù)課程教學(xué)計劃函數(shù) 詳細設(shè)計#include#include #define NULL 0#define maxsize 100typedef struct stuint number;int score;struct stu *next;node;typedef structint vex_num;int vex_sco;int have;node *first;sd;typedef structsd arrymaxsize;int max_class;int max_term;int score_limit;md;md init()int i,x,c;md a;node *p;printf(enter class total:);scanf(%d,&a.max_class);printf(enter term total:);scanf(%d,&a.max_term);printf(enter score limit:);scanf(%d,&a.score_limit);printf(enter class arrange n);for (i=1;i=a.max_class;i+)a.arryi.first=NULL;for(i=1;i0)p=(node *)malloc(sizeof(node);p-number=a.arryi.vex_num;p-next=a.arryx.first;a.arryx.first=p;c+;while(x0);a.arryi.have=c;return a;/*void disp(md a)node *p;int i;for (i=1;inumber.vex_num); p=p-next; printf(n); */void select (int quee,int i,int j,md a)int k,temp,min;min=i;for(k=i+1;k=j;k+)if (a.arryqueek.vex_scoa.arryqueemin.vex_sco)min=k;if(min!=i)temp=queei;queei=queemin;queemin=temp;void arrage(md a)int queemaxsize,front,bare,i,j,total_score;node *p;front=bare=0;j=1;for(i=1;i=a.max_class;i+)if (a.arryi.vex_num!=0&a.arryi.have=0)quee+bare=a.arryi.vex_num;printf(n %d term study:,j+);total_score=0;while(front!=bare)select(quee,front+1,bare,a);if (total_score+a.arryqueefront+1.vex_sconumber.have-;if (a.arryp-number.have=0)quee+bare=a.arryp-number.vex_num;p=p-next;elsetotal_score=0;printf( n%d term study:,j+);main()md h;h=init();arrage(h); 調(diào)試分析問題：現(xiàn)象：最后結(jié)果存在問題，無法提供內(nèi)存原因：函數(shù)的參數(shù)沒有寫正確： 運行結(jié)果及分析課程設(shè)計題目二實驗內(nèi)容 內(nèi)部排序算法的性能分析問題描述。設(shè)計一個測試程序比較幾種內(nèi)部排序算法的關(guān)鍵字比較次數(shù)和移動次數(shù)以取得直觀感受 需求分析 (1)對起泡排序、直接排序、簡單選擇排序、快速排序、希爾排序、堆排序算法進行比較；(2)待排序表的表長不小于100，表中數(shù)據(jù)隨機產(chǎn)生，至少用5組不同數(shù)據(jù)作比較，比較指標有：關(guān)鍵字參加比較次數(shù)和關(guān)鍵字的移動次數(shù)（關(guān)鍵字交換記為3次移動）；(3)輸出比較結(jié)果。 概要設(shè)計main()SqList L; addlist(L); qipao(L); InsertSort(L);SelectSort(L); QuickSort(L); addlist(L); MergeSort(L); 流程圖輸入數(shù)字冒泡排序直插排序希爾排序選擇排序歸并排序快速排序移動次數(shù)和比較次數(shù) 詳細設(shè)計 #include #include#include#include#define LIST_INIT_SIZE 50000int bj1,yd1,n;clock_t start_t,end_t;typedef struct int key; ElemType;typedef struct ElemType *elem; int length;SqList;void addlist(SqList &L) int i;a: printf(請輸入你要輸入的個數(shù):); scanf(%d,&n); if(n50000) printf(超出范圍重新輸入!n); goto a; L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem)exit(0); L.length=0; for(i=1;i30000)goto b; +L.length; void SelectSort(SqList &L)/選擇 start_t=clock(); int i,j,k,bj=0,yd=0; for(i=1;iL.length;i+) k=i; for(j=i+1;jL.length;j+) bj+; if(L.elemj.keyL.elemk.key)k=j; if(i!=k) L.elem0.key=L.elemi.key; L.elemi.key=L.elemk.key; L.elemk.key=L.elem0.key; yd+=3; end_t=clock(); printf(比較次數(shù)為 %d移動次數(shù)為 %dn,bj,yd); printf(排序用時為 %fn,float(end_t-start_t)/CLK_TCK);void qipao(SqList &L)/起泡 start_t=clock(); int i=1,j,bj=0,yd=0; while(iL.length) for(j=1;jL.elemj+1.key) L.elem0.key=L.elemj.key; L.elemj.key=L.elemj+1.key; L.elemj+1.key=L.elem0.key; yd+=3; i+; end_t=clock(); printf(比較次數(shù)為 %d移動次數(shù)為 %dn,bj,yd); printf(排序用時為 %fn,float(end_t-start_t)/CLK_TCK);void InsertSort(SqList &L)/直接插入 start_t=clock(); int i,j,yd=0,bj=0; for(i=2;i=L.length;i+) if(L.elemi.keyL.elemi-1.key) L.elem0.key=L.elemi.key; yd+; j=i-1; bj+; while(L.elem0.keyL.elemj.key) L.elemj+1.key=L.elemj.key; j-; yd+; bj+; L.elemj+1.key=L.elem0.key; yd+; end_t=clock(); printf(比較次數(shù)為 %d移動次數(shù)為 %dn,bj,yd); printf(排序用時為 %fn,float(end_t-start_t)/CLK_TCK);void xier(SqList &L)/希爾 start_t=clock(); int i,d=L.length/2,j,w=0,k,yd=0,bj=0; while(wd) w=1; for(i=w;iL.length;i=i+d) k=i; for(j=i+d;jL.elemj.key) k=j; bj+; if(i!=k) L.elem0.key=L.elemi.key; L.elemi.key=L.elemk.key; L.elemk.key=L.elem0.key; yd+=3; w+; d=d/2; w=1; end_t=clock(); printf(比較次數(shù)為 %d移動次數(shù)為 %dn,bj,yd); printf(排序用時為 %fn,float(end_t-start_t)/CLK_TCK);void BeforeSort() yd1=0,bj1=0;void display(int m,int n) printf(比較次數(shù)為 %d移動次數(shù)為 %dn,m,n);int Partition(SqList &L,int low,int high)/快速排序 int pivotkey; L.elem0=L.elemlow; yd1+; pivotkey=L.elemlow.key; while (lowhigh) yd1+; while(low=pivotkey) -high; L.elemlow=L.elemhigh; bj1+; yd1+; while (lowhigh&L.elemlow.key=pivotkey) +low; L.elemhigh=L.elemlow; bj1+; yd1+; L.elemlow=L.elem0; yd1+; return low;void QSort(SqList &L,int low,int high) int pivotloc; if(lowhigh) pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); void QuickSort(SqList &L) start_t=clock(); BeforeSort(); QSort(L,1,L.length); display(yd1,bj1); end_t=clock(); printf(排序用時為 %fn,float(end_t-start_t)/CLK_TCK);void Merge(ElemType R,ElemType R1,int low,int m,int high)/歸并 int i=low, j=m+1, k=low; while(i=m&j=high) if(Ri.key=Rj.key) bj1+; R1k=Ri; yd1+; i+; k+; else bj1+; R1k=Rj; yd1+; j+; k+; while(i=m) R1k=Ri; yd1+; i+; k+; while(j=high) R1k=Rj; yd1+; j+; k+; void MergePass(ElemType R,ElemType R1,int length, int n) int i=0,j; while(i+2*length-1n) Merge(R,R1,i,i+length-1,i+2*length-1); i=i+2*length; if(i+length-1n-1) Merge(R,R1,i,i+length-1,n-1); else for(j=i;jn;j+) R1j=Rj;void MSort(ElemType R,ElemType R1,int n) int length=1; while (lengthn) MergePass(R,R1,length,n); length=2*length; MergePass(R1,R,length,n); length=2*length; void MergeSort(SqList &L) start_t=clock(); BeforeSort(); MSort(L.elem,L.elem,L.length); display(yd1,bj1); end_t=clock(); printf(排序用時為 %fn,float(end_t-start_t)/CLK_TCK);void main() SqLis