《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》信息

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題 目：內(nèi)部排序的性能比較與哈弗曼編碼學(xué) 院：商學(xué)院專(zhuān) 業(yè)：信息管理與信息系統(tǒng)班 級(jí)：信息092學(xué) 號(hào)：姓 名：同組成員：指導(dǎo)教師：完成日期：2010年01月13日 TOC o 1-5 h z 目 錄2 HYPERLINK l bookmark11 o Current Document 一、問(wèn)題描述31.1哈弗曼編碼31.2內(nèi)部排序性能分析3 HYPERLINK l bookmark18 o Current Document 二、問(wèn)題分析3 HYPERLINK l bookmark22 o Current Document 三、數(shù)據(jù)結(jié)構(gòu)描述4 HYPERLINK l boo

2、kmark52 o Current Document 四、算法設(shè)計(jì)54.1希爾排序流程圖：5 HYPERLINK l bookmark73 o Current Document 五、詳細(xì)程序清單7 HYPERLINK l bookmark283 o Current Document 六、程序運(yùn)行結(jié)果17 HYPERLINK l bookmark287 o Current Document 七、心得體會(huì)19一、問(wèn)題描述1.1哈弗曼編碼設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項(xiàng)目，直到選 擇退出為止。初始化：鍵盤(pán)輸入字符集大小n、n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)；編碼：利用建好

3、的哈夫曼樹(shù)生成哈夫曼編碼；輸出編碼；1.2內(nèi)部排序性能分析設(shè)計(jì)一個(gè)測(cè)試程序比較起泡排序、直接排序、簡(jiǎn)單選擇排序、快速排序、希爾排序 算法的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)以取得直觀感受(待排序表的表長(zhǎng)不小于100，表中數(shù)據(jù) 隨機(jī)產(chǎn)生，至少用5組不同數(shù)據(jù)作比較，比較指標(biāo)有：關(guān)鍵字參加比較次數(shù)和關(guān)鍵字的移動(dòng) 次數(shù)(關(guān)鍵字交換記為3次移動(dòng))。二、問(wèn)題分析我負(fù)責(zé)的是內(nèi)部排序之中希爾排序的性能比較，先設(shè)計(jì)出希爾排序的排序原理，框 架結(jié)構(gòu)，然后設(shè)計(jì)程序代碼，合并到總程序中，修改總程序。三、數(shù)據(jù)結(jié)構(gòu)描述typedef structint key;char otherinfo;Elem;typedef structE

4、lem rN+1;/r0 閑置或用作“哨兵” int length;Sqlist;void ShellSort(int a,int n)int i,j,d;d=n/2;while(d0)for(i=d+1;i=0 & a0aj)aj+d=aj;j=j-d;aj+d=a0;d=d/2;四、算法設(shè)計(jì)4.1希爾排序流程圖:結(jié)束循環(huán)iL.lengthT+i地址值與i-dk地址 值比較N0地址值賦值給j+dk地址值*S+j地址值賦值給 j+dk地址值 T+S+S+ J=i-dk T+開(kāi)始i=dk+1核心算法：希爾排序void ShellInsert(Sqlist *L,int dk, int *s,in

5、t *t)int i,j;for(i=dk+1;ilength ;i+)(*t)+;if(L-r i.key r i-dk.key )L-r 0.key =L-r i.key ;(*s)+;j=i-dk;(*t)+;while(j0&L-r 0.key r j.key )L-r j+dk.key =L-r j.key ;(*t)+;(*s)+;j-=dk;L-r j+dk.key =L-r 0.key ;(*s)+;/if/forvoid ShellSort(Sqlist *L)int i,j,dk;int s=0,t=0;for(i=(int)log(L-length +1);i0;i-)

6、形成增量 for(j=i;jlength +1);j+) dk =(int)pow(2,j-i+1)-1;ShellInsert(L,dk, &s,&t);printf（希爾排序比較次數(shù):d,移動(dòng)次數(shù):dn”,t,s）;五、詳細(xì)程序清單內(nèi)部排序與哈弗曼的總程序：#include#include#include#includetypedef structunsignedint weight;unsignedchar ch;unsignedint parent,lchild,rchild;HTNode,*HuffmanTree;typedef structchar ch;char *chs;Huf

7、fmanCode;typedef structchar ch;int weight;sw;typedef structHuffmanTree HT;HuffmanCode *HC;huf;void select(HTNode * HT,int n,int *n1,int *n2)int i=1;int n3;while(HTi.parent!=0)i+;*n1=i;i+;while(HTi.parent!=0)i+;*n2=i;if(HT*n1.weightHT*n2.weight)(n3=*n1;*n1=*n2;*n2=n3;for(i+;i=n;i+)if(HTi.parent=0)if(

8、HTi.weightHT*n1.weight)*n1=i;else if(HTi.weightHT*n2.weight)*n2=i;huf * HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,sw *w,int n,huf *HUF) int m,i,s1,s2,start,c,f;HuffmanTree p;char *cd;if(n=1) return 0;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;iweight=w-weight;p-ch=w-ch;p-pa

9、rent=0;p-lchild=0;p-rchild=0;for(;iweight=0;p-ch=A;p-parent=0;p-lchild=0;p-rchild=0;for(i=n+1;i=m;i+)select(HT,i-1,&s1,&s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode *)malloc(n+1)*sizeof(char);cd=(char *)malloc(n*sizeof(char);cdn-1=0;f

10、or(i=1;iHT=HT;HUF-HC=HC;return HUF;char *convert(char *chars,char *chars1,HuffmanCode *hc,int n)char *p=chars; int i;strcpy(chars1,);while(*p)i=1; while(hci.ch!=*p&i=n) i+;strcat(chars1,hci.chs); p+;printf(the chars translate are:%sn,chars1);return chars1;void transcode(HuffmanTree ht,char *chars2,c

11、har*chars3)int i=1,p; char *q=chars2;char *r=chars3;while(hti.parent!=0) i+;p=i;while(*q)while(htp.lchild!=0 & *q)if(*q=0)p=htp.lchild;else p=htp.rchild;q+; if(htp.lchild=0)*r=htp.ch;r+;p=i; *r=0;printf(the chars are:); puts(chars3);void input(int *n,sw *w) int i;printf(-請(qǐng)輸入字符數(shù):，scanf(%d”,n);for(i=1

12、;ich,&w-weight);void mainl(void)HTNode HT;HuffmanCode HC,*hc;HuffmanTree ht;huf *HUF,huf2;int n;sw w40;char ch,inchar500,outchar1000;char *abc;char *p=inchar;input(&n,w);HUF=HuffmanCoding(&HT,&HC,w,n,&huf2);#include#include#include#define N 100typedef structint key;char otherinfo;Elem;typedef struct

13、Elem rN+1;int length;Sqlist;void InitSqlist(Sqlist *L)L-length =N;void print(Sqlist *L)int i;for(i=1;ilength ;i+)printf(%5d”,L-ri);printf(n);void gensort(Sqlist *L)int i,j;int s=0,t=0;int temp;int change;for(i=1,change=1;ilength&change=1 ;i+)change=0;for(j=i+1;jlength ;j+)t+;if(L-r i.key L-r j.key )

14、temp=L-r i.key ;L-r i.key =L-r j.key ;L-r j.key =temp;s+=3;change=1;printf(-排序后結(jié)果：n);print(L);printf(起泡排序比較次數(shù)：%d移動(dòng)次數(shù)：dn”,t,s);int Partion(Sqlist *L,int low,int high,int *t,int *s)int pivot;L-r 0.key =L-r low.key ;(*s)+;pivot=L-r low.key ;while(lowhigh)(*t)+;while(lowr high.key =pivot)-high;(*t)+;L-r

15、 low.key =L-r high.key ;(*s)+;(*t)+;while(lowr low.key r high.key =L-r low.key ;(*s)+;L-r low.key =L-r 0.key ;(*s)+;return low;void Qsort(Sqlist *L,int low,int high,int *t,int *s)int pivot;if(lowlength ,&t,&s);printf(快速排序比較次數(shù)：%d移動(dòng)次數(shù)：dn”,t,s);void ShellInsert(Sqlist *L,int dk, int *s,int *t)int i,j;f

16、or(i=dk+1;ilength ;i+)(*t)+;if(L-r i.key r i-dk.key )L-r 0.key =L-r i.key ;(*s)+;j=i-dk;(*t)+;while(j0&L-r 0.key r j.key )L-r j+dk.key =L-r j.key ;(*t)+;(*s)+;j-=dk;L-r j+dk.key =L-r 0.key ;(*s)+;void ShellSort(Sqlist *L)int i,j,dk;int s=0,t=0;for(i=(int)log(L-length +1);i0;i-)for(j=i;jlength +1);j+

17、)dk =(int)pow(2,j-i+1)-1;ShellInsert(L,dk, &s,&t);printf(希爾排序比較次數(shù):d,移動(dòng)次數(shù):dn”,t,s);void InsertSort(Sqlist *L)int i,j;int s=0,t=0;for(i=2;ilength ;i+) t+;if(L-ri.key ri-1.key )L-r0.key =L-ri.key ;s+;j=i-1;t+;while(L-r0.key rj.key )L-rj+1.key =L-rj.key ;j-;s+;t+;L-rj+1.key =L-r0.key ;s+;printf(直接插入排序比較

18、次數(shù):%d移動(dòng)次數(shù):dn”,t,s);void simpleSort(Sqlist *L)int i,j,k;int s=0,t=0;int temp;for(i=1;ilength ;i+)k=i;for(j=i+1;jlength ;j+)t+;if(L-rk.key L-rj.key )k=j;if(k!=i)temp=L-rk.key ;L-rk.key =L-ri.key ;L-ri.key =temp;s+=3;printf(簡(jiǎn)單選擇排序比較次數(shù)：%d移動(dòng)次數(shù):dn”,t,s);void Sort(Sqlist *L1,Sqlist *L2,Sqlist *L3,Sqlist *L

19、4,Sqlist *L5)gensort(L1);ShellSort(L2);QuickSort(L3);InsertSort(L4);simpleSort(L5);void suiji(Sqlist *L1,Sqlist *L2,Sqlist *L3,Sqlist *L4,Sqlist *L5)int i;for(i=1; ilength ; i+)L1-ri.key =rand()%100;L2-r i.key =L1-r i.key ;L3-ri.key =L1-r i.key ;L4-ri.key =L1-r i.key ;L5-ri.key =L1-r i.key ;printf(%

20、5d”, L1-r i.key );void main2()int i,j;Sqlist L1,L2,L3,L4,L5;InitSqlist(&L1);InitSqlist(&L2);InitSqlist(&L3);InitSqlist(&L4);InitSqlist(&L5);for(i=1,j=1;i=L1.length ,j=L1.length ;i+,j+) L1.ri.key =j;L2.ri.key =j;L3.ri.key =j;L4.ri.key =j;L5.ri.key =j;printf(排序前正序數(shù)組:n);for(i=1;i0,j=L1.length ;i-,j+) L

21、1.r j.key =i;L2.r j.key =i;L3.r j.key =i;L4.r j.key =i;L5.r j.key =i;printf(排序前逆序數(shù)組:n);for(i=1;i=L1.length ;i+) printf(%5d”,L1.r i.key );printf(n);Sort(&L1,&L2,&L3,&L4,&L5);printf(第一組亂序：n);suiji(&L1,&L2,&L3,&L4,&L5);printf(n);Sort(&L1,&L2,&L3,&L4,&L5);printf(第二組亂序：n);suiji(&L1,&L2,&L3,&L4,&L5);print

22、f(n);Sort(&L1,&L2,&L3,&L4,&L5);printf(第三組亂序：n);suiji(&L1,&L2,&L3,&L4,&L5);printf(”n”)；Sort(&L1,&L2,&L3,&L4,&L5);void welcome()r/主程序界面printf( printf( printf( printf( printf(printf(Welcome to our systemn);*n );1.哈夫碼編碼*n);2.排序的性能分析*n);3.退出*n);*n);int main()int choice;welcome();printf(please make your c

23、hoice:);scanf(%d”,&choice);while(1)switch(choice)case 1:system(cls);main1();break;case 2:system(cls);main2();break;case 3:exit(-1);default:printf(please chooose the right choice!);break;printf(please make your choice:);scanf(%d”,&choice);六、程序運(yùn)行結(jié)果3334353637383940171819202122232449505152535455 S66S 66

24、676869707172818283848586878825415773891尊26425074眼1127435975911220446尊7692132945617793143D46627894153147637995979899 100E序后皓果：123456781710333435363738394049505152 S3 54555681848871708725415773891尊26425074眼112743597S91122044院7692132945617793143尊466278941531476379958 一二一二9一二.一二.一二.二=Lfe799 100比較次數(shù)：99整動(dòng)次數(shù):8 比寂次數(shù)：?58,移動(dòng)次數(shù):旌 比較次fe： 5148將可次數(shù):396尤膠次數(shù)；9?瞥島次數(shù)；咨 主咬次瘢：49555襟京1吹數(shù)&917S59432711264250749色9對(duì)74584226 :LD11274359759189735741251220446D76928872564S24813294561779387715539