数据结构专业课程设计模板.doc

姓名：
学号：
班级：
指导老师：
学院：计算机学院

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 = 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<l2; i++)
{
index1 = 0;
index2 = 0;
for(int j=0;j<l1;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);

cout<<"相乘后数字为："<<endl;
for(int i=0;i<l1+l2;i++)
{
if(result[i] != '0')
cout<<result[i];
}
cout<<endl;
}
int main()
{
char str1[100],str2[100];
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 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 <stdio.h>
#include <string.h>
#include <limits.h>

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在<limits.h>中定义
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
{
//假如大于次小值，则什么全部不做
;
}
}
}
}

void HTree(Hnode *huff , Infor w[] , int n)
{
int m = 2*n-1 ,sum , s1 ,s2 ;
for(int i = 1 ; i <= n ; ++i )
{
huff[i].weight = w[i-1].weight;
huff[i].lchild = huff[i].rchild = huff[i].parent = -1 ;
}

for(int i = n+1 ; i <= m ; ++i)
{
huff[i].weight = -1;
huff[i].lchild = huff[i].rchild = huff[i].parent = -1 ;
}
if(n != 1)
{
for(int i = 1 ; i <= n-1 ; ++i )
{
select(huff,n+i-1,s1,s2);
sum = huff[s1].weight+huff[s2].weight ;
huff[n+i].weight = sum ;
huff[s1].parent = huff[s2].parent = n + i ;
huff[n+i].lchild = s1 ;
huff[n+i].rchild = s2 ;
}
}
else
{
w[0].length = 1;
}

for(int i = 1 ; i <= n ; ++i)
{
int k = 0 , c = 0 ;
char temp[10] ;
for( int j = huff[i].parent , k = i ; j != -1 ; k = j , j = huff[j].parent )
{
w[i-1].length++;
if(huff[j].lchild == k)
{
temp[c++] = '0' ;
}
else
{
temp[c++] = '1' ;
}
}
printf("%c 编码为：",i+'A'-1) ;
for(int i = c-1 ; i>= 0 ; --i)
{
putchar(temp[i]) ;
}
puts("") ;
}
}

int main()
{
Hnode huff[60] ;
char str[1000];
w[0].weight = 7 ;
w[1].weight = 9 ;
w[2].weight = 12;
w[3].weight = 22;
w[4].weight = 23;
w[5].weight = 27;
HTree(huff,w,6);

int b=0;
for(int i = 0 ; i < 6 ; ++i)
{
b += w[i].length*w[i].weight;
}
printf("平均编码长度为： %.1f\n",(b*1.0)/6) ;
}

6运行测试