数据结构课程设计报告
时间：2003年12月 姓名：叶焕青
学号：200250001055
一．任意长整数的加减运算
（1） 要求：利用双循环链表实现长整数的存储。每个节点一位数字，头节点存储正负号。
（2）源程序、目标程序在磁盘中的路径、名称：A:\\JISUANQI.C Ａ:\\JISUANQI.EXE
（3）问题描述：
1．首先需要建立一个接收和建立函数，接收从键盘输入的一个欲求的式子，将其链接
成双循环链表。
2．建立独立的加法，减法函数。
3．建立一个可以混合调用加、减法的计算函数。函数返回值为结果的双循环链表的头
指针。
4．设计输出函数，把结果的双循环链表输出。
（4）数据结构描述：
1．类型描述： typedef struct pnode
{ char data;
struct pnode *prior,*next;
} polynode;
polynode *head[100];
双循环链表中的节点类型为polynode.其中data部分放char类型的一位数字（头节
点放正负号）。另加上前趋指针域和后继指针域。每一个数连同其前面的符号链接成一个链表。
每个数的链表的首地址存于全局变量polynode *head[100]中。则该系统能完成100
个数以内的加减混合运算。 2．图例描述：（见下页）
(5) 函数说明：
开始 : void begin( ) 开始界面，提示输入信息
建立 ：void creat( ) 把输入的式子联成若干个链表，每个数（包括符号）为
一个链表。全局变量head[ ]中存这些链表的头指针。
加法 ：polynode *noequal(polynode *rear,polynode *rear3,polynode *c,int x) 专门处理当数a+b时a与b位数不同的情况。参数为位
数多的数的当前指针polynode *rear，结果数组的当前指针polynode *rear3，位数多的数的头指针polynode *c和记录进位的数int x。返回处理后的结果的头指针。
polynode *add(polynode *a,polynode *b, char sign)
处理a+b，参数为两个被加数的头指针，和结果的符号
（由cal2函数判断）。返回结果的头指针。
add函数调用noeqal函数实现加法功能。 减法： polynode *compare(polynode *a,polynode *b)
比较a和b两个数哪个的绝对大。返回大的数的头指针。 polynode *mine(polynode *a,polynode *b)
计算a的绝对值减b的绝对值的值，其中参数a的绝对
值比b的绝对值大。返回结果的头指针。
polynode *miners(polynode *a,polynode *b)
计算a－b的值，返回结果的头指针。 miners调用mine再调用compare函数实现减法功能。 计算： polynode *cal1(polynode *a,polynode *b)
计算a与b运算的结果，返回结果的头指针。 polynode *cal2( ) 实现多个数的混合运算的函数，返回结果的头指针。 cal2调用cal1再调用加减法函数实现多个数混合运算的功能。 输出： void output(polynode *c) 输出结果。
图例显示：（例如式子为-789+102+536＝）
(6)主要算法描述：
1． 计算：polynode *cal1(polynode *a,polynode *b)
{polynode *c;
if(a>0且b>0) c=a+b; if(a<0且b<0) c=-(a+b);
if(a>0且b<0) c=a-b; if(a<0且b>0) c=b-a
return(c);
}
2．减法（a-b）：polynode *miners(polynode *a,polynode *b)
{polynode *p,*c;
p=(a,b)中绝对值大的那个； (由compare函数得到) if(a的绝对值大) {c=a-b} (由mine函数得到) if(b的绝对值大) {c=-(b-a)} （由mine函数得到） return(c);
}
减法（绝对值大的减绝对值小的）：
polynode *mine(polynode *a,polynode *b)
{polynode *p,*ptr,*rear1,*rear2,*rear3; 退位x=0;
rear1=a；rear2=b;
rear3=malloc(sizeof(polynode)); ptr=结果头指针；
rear1前移一位，指向链表a的个位； rear2前移一位，指向链表b的个位；
当（a，b均没有处理完 ）
{rear3->prior=malloc(sizeof(polynode)); rear3自己形成双循环链表； if(a的该位－退位>=b的该位)
{rear3->data=(rear1->data-rear2->data-x);x=0;}
else {rear3->data=(rear1->data+10-rear2->data-x);x=1;} rear1前移一位；rear2前移一位； }
while(a未处理完而b处理完) /*因为a的绝对值比b的绝对值大，所以必
定b先处理完*/
{rear3->prior=malloc(sizeof(polynode)); rear3自己形成双循环链表；
if(a的该位-退位>=0)
{rear3->data=rear1->data-x;x=0;}
else {rear3->data=rear1->data-x+10;x=1;} rear1前移一位； }
将rear3与c头指针连上； return(ptr);
}
(7)测试数据及结果：
1． 按照提示输入式子，如“-123+745-654＝”，要以“＝”结束。
2． 若输入的不规范，如不是＋，—号，也不是数字，则提示错误，然后推出
程序。
3． 当连续输入多个＋，—号时，按最后一个计算。如：
12-+2—+3＝17 12+++23+＝35 12+-23-+34-＝23
4． 可接受输入时的无效0，结果正确。如0003+2＝5
5． 当没有输入错误，正常运行完一次后，出现continue(y/n)?界面。此时，
输入任意不是y或n的字符都能容错。要求重新输入。
（8）特点：
优点：1．源程序层次比较清晰，分块较好，把相对独立的部分都写成一个函数，
每个函数算法都不复杂，多个函数嵌套调用完成某一项功能，源代码的可重用性较好，所以使得源程序比较简洁。 2. 以进行多个数的加减混合运算。
3. 结果可以将高位的无效零清除，输出正确结果。 4. 可以进行多次计算。
5．在continue(y/n)?界面有一定的容错能力，
（9）小结：总体上说程序在正确输入的情况下可以进行多次多个数加减混合运算，
功能较完善。但容错能力有待进一步提高。
二．哈夫曼编码
( 1 )要求：设计一个哈夫曼编码解码程序。把一个文本文件进行哈夫曼编码压缩，
生成压缩文件，将已压缩文件读出，翻译还原。
(2) 源程序、目标程序在磁盘中的路径、名称：A:\\HUF.C A:\\HUF.EXE
(3) 问题描述：1。首先要建立一个数组s[ch]记录文件中每个字符出现的频率,ch
对应字符ch。
2．将出现过的字符用另一个权值数组weight[ ]记录。 3．计算原文件的大小，用Weight记录。 4．用NUM记录原文件中不同字符的个数。 5．建立哈夫曼树tree[ ]。 6．建立编码code[ ]。
7．把NUM，Weight，以及哈夫曼树写入压缩文件中。并利用位运算，把编码以位的形式写入压缩文件中。这样就完成了压缩。 8． 解压时，按照哈夫曼树把编码翻译到新的文件中。
（4）数据结构描述：
1．类型描述：typedef struct
{char ch;
unsigned char lchild,rchild,parent; }hufmtree;
hufmtree tree[m];
long weight[m];
typedef struct {char bits[n]; int start;
