数据结构课程设计.doc
如有侵权，请联系网站删除，仅供学习与交流数据结构课程设计【精品文档】第 6 页姓名： 学号：班级：指导老师： 学院：计算机学院1 大数相乘1. 问题描述两个比较大的数，远远超过long long 类型，相乘，并计算结果。2. 设计思路通过模拟手工计算两数相乘，从低位乘到高位，两重循环，第一重循环控制乘数的第i位数与被乘数的相乘，第二重循环是被乘数的第j位数。第二重循环每循环完一次，再把结果*10与上次的结果相加，这里又运用到了大数相加，这样一直处理到第一重循环结束。只要合理的处理好进位就可以了。3. 数据结构设计把两数每位数存放数组里，通过控制循环实现相乘。4. 功能函数设计void nixu（）void mul ()；计算两个存在数组里的大数计算相乘结果。5. 程序代码#include<iostream>#include<cstring>using namespace std;void nixu(char* str, int p, int q) char temp; while(p < q) temp = strp; strp = strq; strq = temp; p +; q -;void mul(char* str1, char* str2)char result200; int l1 = strlen(str1); int l2 = strlen(str2); memset(result,'0',l1+l2); resultl1+l2 = '0' nixu(str1, 0, l1-1); nixu(str2, 0, l2-1); int index1; int index2; for(int i=0;i<l2; i+) index1 = 0; index2 = 0; for(int j=0;j<l1;j+) int temp1 = (str1j - '0') * (str2i - '0') + index1; index1 = temp1 / 10; temp1 = temp1 % 10; int temp2 = (resulti+j - '0') + temp1 + index2; index2 = temp2 / 10; resulti+j = temp2 % 10 + '0' resulti + l1 += index1 + index2; nixu(result, 0, l1+l2-1);cout<<"相乘后的数字为："<<endl;for(int i=0;i<l1+l2;i+)if(resulti != '0')cout<<resulti;cout<<endl;int main()char str1100,str2100;cout<<"请输入需要相乘的数字"<<endl;cin>>str1;cin>>str2;int l1 = strlen(str1);int l2 = strlen(str2);mul(str1,str2);return 0;6运行测试7设计心得大数相乘和大数相加不一样，大数相加比大数相乘简单一些，所以在大数相乘这边花了一点时间。2 哈弗曼树1.问题描述欲发一封内容为AABBCAB (共长 100 字符,其中:A 、B 、C 、D 、E 、F分别有7 、9 、12 、22 、23、27个)的电报报文,实现哈夫曼编码，并求平均编码长度。2.设计思路建立一个哈夫曼树，求编码的，再求平均编码长度。3.数据结构设计建立一个储存字符出现数目以及字符编码后的长度struct Inforint weight ;int length ;w30;再建立一个储存哈夫曼树的结点数据结构typedef structchar ch;int weight;int lchild,rchild ,parent;Hnode;4.功能函数设计void select(const Hnode HT,int n,int &s1,int &s2)求数组中权值最小和次小的值的下标void HTree(Hnode *huff , Infor w , int n)建立哈夫曼树，编码和编码长度。5.程序代码#include <stdio.h>#include <string.h>#include <limits.h>typedef structchar ch;int weight;int lchild,rchild ,parent;Hnode;struct Inforint weight ;int length ;w30;void select(const Hnode HT,int n,int &s1,int &s2) int i; s1 = s2 = 0; int min1 = INT_MAX;/最小值，INT_MAX在<limits.h>中定义的 int min2 = INT_MAX;/次小值 for ( i = 1; i <= n; +i ) if ( HTi.parent = -1 ) /筛选没有父节点的最小和次小权值下标if ( HTi.weight < min1 ) /如果比最小值小min2 = min1; s2 = s1;min1 = HTi.weight; s1 = i; else if ( (HTi.weight >= min1) && (HTi.weight < min2) )/如果大于等于最小值，且小于次小值 min2 = HTi.weight; s2 = i; else /如果大于次小值，则什么都不做void HTree(Hnode *huff , Infor w , int n)int m = 2*n-1 ,sum , s1 ,s2 ;for(int i = 1 ; i <= n ; +i )huffi.weight = wi-1.weight;huffi.lchild = huffi.rchild = huffi.parent = -1 ;for(int i = n+1 ; i <= m ; +i)huffi.weight = -1;huffi.lchild = huffi.rchild = huffi.parent = -1 ;if(n != 1)for(int i = 1 ; i <= n-1 ; +i )select(huff,n+i-1,s1,s2);sum = huffs1.weight+huffs2.weight ;huffn+i.weight = sum ;huffs1.parent = huffs2.parent = n + i ;huffn+i.lchild = s1 ;huffn+i.rchild = s2 ;elsew0.length = 1;for(int i = 1 ; i <= n ; +i)int k = 0 , c = 0 ;char temp10 ;for( int j = huffi.parent , k = i ; j != -1 ; k = j , j = huffj.parent )wi-1.length+;if(huffj.lchild = k)tempc+ = '0' ;elsetempc+ = '1' ;printf("%c 的编码为：",i+'A'-1) ;for(int i = c-1 ; i>= 0 ; -i)putchar(tempi) ;puts("") ;int main()Hnode huff60 ;char str1000;w0.weight = 7 ;w1.weight = 9 ;w2.weight = 12;w3.weight = 22;w4.weight = 23;w5.weight = 27;HTree(huff,w,6);int b=0;for(int i = 0 ; i < 6 ; +i)b += wi.length*wi.weight;printf("平均编码长度为： %.1fn",(b*1.0)/6) ;6运行测试
