《数据结构课程设计》信息

1、数据结构课程设计报告题 目：内部排序的性能比较与哈弗曼编码学 院：商学院专 业：信息管理与信息系统班 级：信息092学 号：姓 名：同组成员：指导教师：完成日期：2010年01月13日 TOC o 1-5 h z 目 录2 HYPERLINK l bookmark11 o Current Document 一、问题描述31.1哈弗曼编码31.2内部排序性能分析3 HYPERLINK l bookmark18 o Current Document 二、问题分析3 HYPERLINK l bookmark22 o Current Document 三、数据结构描述4 HYPERLINK l boo

2、kmark52 o Current Document 四、算法设计54.1希尔排序流程图：5 HYPERLINK l bookmark73 o Current Document 五、详细程序清单7 HYPERLINK l bookmark283 o Current Document 六、程序运行结果17 HYPERLINK l bookmark287 o Current Document 七、心得体会19一、问题描述1.1哈弗曼编码设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选 择退出为止。初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；编码：利用建好

3、的哈夫曼树生成哈夫曼编码；输出编码；1.2内部排序性能分析设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序 算法的关键字比较次数和移动次数以取得直观感受(待排序表的表长不小于100，表中数据 随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动 次数(关键字交换记为3次移动)。二、问题分析我负责的是内部排序之中希尔排序的性能比较，先设计出希尔排序的排序原理，框 架结构，然后设计程序代码，合并到总程序中，修改总程序。三、数据结构描述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;四、算法设计4.1希尔排序流程图:结束循环iL.lengthT+i地址值与i-dk地址 值比较N0地址值赋值给j+dk地址值*S+j地址值赋值给 j+dk地址值 T+S+S+ J=i-dk T+开始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（希尔排序比较次数:d,移动次数:dn”,t,s）;五、详细程序清单内部排序与哈弗曼的总程序：#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(-请输入字符数:，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(-排序后结果：n);print(L);printf(起泡排序比较次数：%d移动次数：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(快速排序比较次数：%d移动次数：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(希尔排序比较次数:d,移动次数: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、次数:%d移动次数: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(简单选择排序比较次数：%d移动次数: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(排序前正序数组: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(排序前逆序数组: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);六、程序运行结果3334353637383940171819202122232449505152535455 S66S 66

24、676869707172818283848586878825415773891尊26425074眼1127435975911220446尊7692132945617793143D46627894153147637995979899 100E序后皓果：123456781710333435363738394049505152 S3 54555681848871708725415773891尊26425074眼112743597S91122044院7692132945617793143尊466278941531476379958 一二一二9一二.一二.一二.二=Lfe799 100比较次数：99整动次数:8 比寂次数：?58,移动次数:旌 比较次fe： 5148将可次数:396尤胶次数；9?瞥岛次数；咨 主咬次瘢：49555襟京1吹数&917S59432711264250749色9对74584226 :LD11274359759189735741251220446D76928872564S24813294561779387715539