数据结构课程设计.doc

姓名： 学号：班级：指导老师： 学院：计算机学院1 大数相乘1. 问题描述两个比较大的数，远远超过long long 类型，相乘，并计算结果。2. 设计思路通过模拟手工计算两数相乘，从低位乘到高位，两重循环，第一重循环控制乘数的第i位数与被乘数的相乘，第二重循环是被乘数的第j位数。第二重循环每循环完一次，再把结果*10与上次的结果相加，这里又运用到了大数相加，这样一直处理到第一重循环结束。只要合理的处理好进位就可以了。3. 数据结构设计把两数每位数存放数组里，通过控制循环实现相乘。4. 功能函数设计void nixu（）void mul ()；计算两个存在数组里的大数计算相乘结果。5. 程序代码#include#includeusing 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;il2; i+) index1 = 0; index2 = 0; for(int j=0;jl1;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;il1+l2;i+)if(resulti != 0)coutresulti;coutendl;int main()char str1100,str2100;cout请输入需要相乘的数字str1;cinstr2;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 #include #include 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在中定义的 int min2 = INT_MAX;/次小值 for ( i = 1; i = n; +i ) if ( HTi.parent = -1 ) /筛选没有父节点的最小和次小权值下标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 = 0 ; -i)putchar(tempi) ;puts() ;int main()Hnode huff60 ;char str1000;w0.weight = 7 ;w1.weight = 9 ;w2.weight = 12;w3.weight = 22;w