数据结构课程设计

姓名：

学号：

班级：

指导老师：

学院：计算机学院

大数相乘1

1.问题描述两个比较大的数，远远超过long long 类型，相乘，并计算结果。

2.设计思路

通过模拟手工计算两数相乘，从低位乘到高位，两重循环，第一重循环控制乘数的第i位数与被乘数的相乘，第二重循环是被乘数的第j位数。第二重循环每循环完一次，再把结果*10与上次的结果相加，这里又运用到了大数相加，这样一直处理到第一重循环结束。只要合理的处理好进位就可以了。

3.数据结构设计

把两数每位数存放数组里，通过控制循环实现相乘。

4.功能函数设计

（）void nixu void mul ()；

计算两个存在数组里的大数计算相乘结果。

5.程序代码

#include

#include

using namespace std;

void nixu(char* str, int p, int q)

{

char temp;

while(p < q)

{

temp = str[p];

str[p] = str[q];

str[q] = temp;

p ++;

q --;

}

}

void mul(char* str1, char* str2)

{

char result[200];

int l1 = strlen(str1);

int l2 = strlen(str2);

memset(result,'0',l1+l2);

result[l1+l2] = '\0';

nixu(str1, 0, l1-1);

nixu(str2, 0, l2-1);

int index1;

int index2;

for(int i=0;i

{

index1 = 0;

index2 = 0;

for(int j=0;j

{

int temp1 = (str1[j] - '0') * (str2[i] - '0') + index1;

index1 = temp1 / 10;

temp1 = temp1 % 10;

int temp2 = (result[i+j] - '0') + temp1 + index2;

index2 = temp2 / 10;

result[i+j] = temp2 % 10 + '0';

}

result[i + l1] += index1 + index2;

}

nixu(result, 0, l1+l2-1);

挠畯?尼相乘后的数字为：<

for(int i=0;i

{

if(result[i] != '0')

cout<

}

cout<

}

int main()

{

char str1[100],str2[100];

<>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 Infor{

int weight ;

int length ;

}w[30];

再建立一个储存哈夫曼树的结点数据结构

typedef struct{

char 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 struct{

char ch;

int weight;

int lchild,rchild ,parent;

}Hnode;

struct Infor{

int weight ;

int length ;

}w[30];

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 ( HT[i].parent == -1 )

{

// 筛选没有父节点的最小和次小权值下标

if ( HT[i].weight < min1 )

{

// 如果比最小值小

min2 = min1;

s2 = s1;

min1 = HT[i].weight;

s1 = i;

}

else if ( (HT[i].weight >= min1) && (HT[i].weight < min2) )

{

如果大于等于最小值，且小于次小值// min2 = HT[i].weight; s2 = i;

}

else