课程设计报告
设计题目：1、链表应用
2、赫夫曼树应用
专业网络工程
班级网络081
学生秦颢语
学号28
同组学号22
指导教师路莹
起止时间2010-6-28至2010-7-目录
一、任务书——————————————————————————3
二、链表应用—————————————————————————5
1.流程图—————————————————————————5
2.源程序—————————————————————————6
3.运行结果————————————————————————9
三、赫夫曼树应用———————————————————————12
1.流程图—————————————————————————12
2.源程序—————————————————————————13
3.运行结果————————————————————————17
四、收获及体会————————————————————————18
五、软件环境及参考文献————————————————————18一、大连工业大学数据结构课程设计（论文）任务书
指导教师签字：路莹2010年6 月17 日
二、链表应用
1、流程图
2、源程序
#include #include int n; struct Lnode//创建结构体Lnode，包含数据域data和指针域next { int data; struct Lnode *next; }Lnode; void menu()//菜单程序 { printf("\\n链表应用\\n1 创建高次多项式A，B\\n2 加法运算A+B=C\\n3 减法运算A-B=C\\n4 输出C\\n5 退出\\n"); } struct Lnode *creat(char c)//创建链表 { int i,d; struct Lnode *head,*p; head = (struct Lnode *)malloc(sizeof(struct Lnode));//用malloc函数动态分配空间 head->next = 0;//赋初值 printf("\\n由0次到%d次输入%c的每项系数（若无该项则系数为0）： //记头结点head的下一结点位置为0，用结点在链表中的位置代表幂数，将系数存入对应数据域 for(i = 0;i <= n;i++) { scanf("%d p = (struct Lnode *)malloc(sizeof(struct Lnode)); //用malloc函数动态分配空间 p->data = d; p->next = head->next; head->next = p; } return(head); } struct Lnode *plus(struct Lnode *head1,struct Lnode *head2)//加法运算 { int i; struct Lnode *p,*q,*s,*head3; head3 = (struct Lnode *)malloc(sizeof(struct Lnode)); //用malloc函数动态分配空间 head3->next = 0;//初始化 p = head1; q = head2; //将链表A,B中位置相同（即幂数相同）的结点的数据域值（即系数）相加，所得和链成链表C for(i = 0;i <= n;i++) { s = (struct Lnode *)malloc(sizeof(struct Lnode)); //用malloc函数动态分配空间 s->data = p->next->data + q->next->data; s->next = head3->next; head3->next = s; p = p->next; q = q->next; } return(head3); } struct Lnode *minus(struct Lnode *head1,struct Lnode *head2)//减法运算（与加法运算原理相同） { int i; struct Lnode *p,*q,*s,*head3; head3 = (struct Lnode *)malloc(sizeof(struct Lnode)); head3->next = 0; p = head1; q = head2; for(i = 0;i <= n;i++) { s = (struct Lnode *)malloc(sizeof(struct Lnode)); s->data = p->next->data - q->next->data; s->next = head3->next; head3->next = s; p = p->next;q = q->next; } return(head3); } struct Lnode *display(struct Lnode *head)//输出链表C { int i,d; struct Lnode *p; p = head->next;//将位置为0的结点赋给p printf("\\n输出C\\n幂数\系数"); //用for循环依次输出各结点位置（即幂数）和数据域值（即系数）for(i = 0;i <= n;i++) { printf("\\n%d d = p->data; printf("\%d p = p->next; } return(head); } void main() { int choice; struct Lnode *A,*B,*C; menu(); printf("\\n输入选项:"); scanf("%d //用while循环实现菜单的循环选择 while(choice! = 5) { //用switch函数实现功能选择 switch(choice) { case 1: printf("\\n输入A，B的最高次项的幂数："); scanf("%d A = creat('A'); B = creat('B');break; case 2: C = plus(A,B);break;case 3: C = minus(A,B);break; case 4: C = display(C);break; } menu(); printf("\\n输入选项:"); scanf("%d } } 3、运行结果 三、赫夫曼树应用 1、流程图 2、源程序 #include #include int s1=0,s2=0;//定义全局变量 typedef struct//创建结构体，包含字符域c，权值域w，双亲域p，左孩子域l和右孩子域r；声明HT来代替结构体struct { int c; int w; int p,l,r; }HT; typedef char * *HuffmanCode; HT *HTree; HuffmanCode HCode; void Select(HT *HTree,int b)//选择双亲域值为0且权值最小的两个结点s1s2 { int i,j,t; //找第一个p为0的结点 for(i=1;i<=b;i++) if(!HTree[i].p)//若一结点双亲域值为0，则用s1记录其位置 { s1 = i; break; } //找第二个p为0的结点 for(j=i+1;j<=b;j++) if(!HTree[j].p) //若s1之后一结点双亲域值为0，则用s2记录其位置 { s2 = j; break; } //找第一个w最小的结点 for(i=1;i<=b;i++) if((HTree[s1].w>HTree[i].w)&&(!HTree[i].p)&&(s2!=i))//用s1与其他非s2的双亲域为0的结点比较权值 s1=i; //找第二个w最小的结点 for(j=1;j <= b;j++) if((HTree[s2].w>HTree[j].w)&&(!HTree[j].p)&&(s1!=j))//用s2与其他非s1的双亲域为0的结点比较权值s2=j; //令s1小于s2 if(s1>s2) { t=s1;//t为中间变量,做变量交换 s1=s2; s2=t; } } void Strcpy(char *p1,char *p2,int i,int j)//字符串连接 { int k; for(k=0;i<=j;k++,i++) *(p1+k)=*(p2+i); } void Print(HT *HTree,HuffmanCode HCode,int n)//打印赫夫曼编码 { int i; for(i=1;i<=n;i++) { printf("%c-- printf("%d-- printf("%s printf("\\n"); } } void main() { int n,m,i,C,W,start,t,P,l,WPL; int wpl[100]; HT *h; printf("\\n输入叶子节点个数:"); scanf("%d m=2*n-1;//含n个叶子结点的赫夫曼树共有2n-1个结点 HTree=(HT *)malloc((m+1)*sizeof(HT));//0号单元未用,用malloc函数动 态分配连续空间 h=HTree+1;//越过0号单元 printf("\\n输入%d个字符的ASCⅡ码和权值: //叶子结点初始化for(i=1;i<=n;i++,h++) { scanf("%d scanf("%d h->c=C; h->w=W; h->p=0; h->l=0; h->r=0; } //中间结点初始化 for(i=n+1;i<=m;i++,h++) { h->c=' '; h->w=0; h->p=0; h->l=0; h->r=0; } //输出初始状态图 printf("\\n输出初始状态图\\n字符\权值\双亲\左孩子\右孩子"); h=HTree+1; //越过0号单元 for(i=1;i<=m;i++,h++) { printf("\\n%c\%d\%d\%d\%d } //建赫夫曼树 for(i=n+1;i<=m;i++) { Select(HTree,i-1);//选择双亲域值为0且权值最小的两个结点s1，s2 HTree[s1].p=i;//将两个结点的和结点存入中间结点 HTree[s2].p=i; HTree[i].l=s1; HTree[i].r=s2; HTree[i].w=HTree[s1].w+HTree[s2].w; } //输出终结状态图 printf("\\n输出终结状态图\\n字符\权值\双亲\左孩子\右孩子"); h=HTree+1; //越过0号单元 for(i=1;i<=m;i++,h++){ printf("\\n%c\%d\%d\%d\%d } //从叶子到根逆向求赫夫曼树编码 char *code; HCode=(HuffmanCode)malloc((n+1)*sizeof(char));//0号单元未用,用malloc函数动态分配连续n个字符编码的头指针向量 code=(char *)malloc(n*sizeof(char));// 用malloc函数分配求编码的公用工 作空间 code[n-1]='\\0';//编码结束符 //逐个字符求赫夫曼编码 for(i=1;i<=n;i++) { start=n-1;//编码结束符位置 //从叶子到根逆向求编码 for(t=i,P=HTree[i].p;P!=0;t=P,P=HTree[P].p) { if (HTree[P].l==t) code[--start]='0';//左孩子表示0 else code[--start]='1'; //右孩子表示1 } HCode[i]=(char *)malloc((n-start)*sizeof(char));// 用malloc函数为第i 个字符编码分配空间 Strcpy(HCode[i],code,start,n-1); //字符串连接 } printf("\\n赫夫曼编码为:\\n"); Print(HTree,HCode,n); //打印赫夫曼编码 //赫夫曼树的带权路径长度 for(i=1;i<=n;i++) { for(l=0,P=HTree[i].p;P!=0;P=HTree[P].p)//若该结点有双亲，则边数l+1 l+=1; wpl[i]=HTree[i].w*l;//第i个结点的带权路径长度 } for(i=1,WPL=0;i<=n;i++)//树的带权路径长度为所有叶子结点的带权路 径长度之和 WPL+=wpl[i]; printf("\\n带权路径长度:%d\\n } 四、收获及体会 通过这次课程设计，我学到了很多东西。开始编写程序时，借鉴了一下本学期实验内容，将所需程序按功能分段，再逐段编写，这使得整个程序的思路很清晰，编起来也很顺利。 在链表应用程序中，由于思考不周，只将结点在链表中的位置表示幂数，使得储存空间极度浪费，如果在每个结点中多加一个幂数域，只存入有系数的项数，则会节约很大储存空间。 在赫夫曼树应用程序中，按照书上的伪代码，将其翻译成C语言可识别的程序代码，调整过后可以实现赫夫曼树的建立和赫夫曼树编码的构造。然后用嵌套for循环实现对赫夫曼树的带权路径长度的求解。 在图应用程序中，对于拓扑排序的实现出现了一些问题，参考了网上的一些程序后，还是无法调试成功。在时间和精力有限的情况下，没能够将其完成实在很遗憾。希望假期时能够再接再厉，完成图应用的设计。即使不为了学分，也要珍惜每一次的锻炼机会。 很感谢学校和老师提供给我们的这次锻炼机会，让我们可以学以致用，将学习成果实物化。我会继续努力，将本专业的课程融会贯通，成为可以独当一面的有用人才。 五、软件环境及参考文献 1、软件环境 2、文献 《数据结构（c语言版）》清华大学出版社下载本文
