(此文档为word 格式，下载后您可任意编辑修改！)
C 语言课程设计说明书
题目： 长整型数四则运算
学 院：
班 级：
学 生：
学 号：
班内序号：
提交日期： 年 月 日
目 录 一、需求分析 ........................................................................................................................................................... 1 二、设计思路 ........................................................................................................................................................... 1 三、详细设计 ........................................................................................................................................................... 2
1、主要函数 ..................................................................................................................................................... 2
2、函数的主要调用关系图 ............................................................................................................................. 3 四、调试分析及编程心得体会 ............................................................................................................................... 3 五、用户手册 ........................................................................................................................................................... 3 六、测试结果 ........................................................................................................................................................... 3 七、源程序代码 ....................................................................................................................................................... 4
1、 main.c 主控文件 ..................................................................................................................................... 4
2、IntFace.h 程序界面模块头文件 ............................................................................................................. 5
3、IntFace.c 程序界面处理模块文件 ......................................................................................................... 6
4、LongInt.h 长整型数输入输入及运算模块头文件 . ................................................................................. 9
5、LongIO.c 长整型数输入输出处理模块文件............................................................................................ 9
6、LongInt.c 长整型数运算处理模块文件.................................................................................................11
7、DuCiLink.h 双向循环链表处理模块头文件.......................................................................................... 16
8、DuCiLink.c 双向循环链表处理模块代码.............................................................................................. 17
一、需求分析
1、 设计一个实现任意长的整数进行四则运算的程序。
2、 输入和输出形式是按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开，长整数位数没有上
限，以分号结束长整型数据的输入。
3、 程序执行的命令包括：
1）、输入长整数1；2）、输入长整数2；3）、输入执行的运算符；4）、计算并输出结果；5）、结束。
4、测试数据：（以加法为例）
（1）、0;0;+;应输出“0”。
（2）、－; －;+;应输出“－”。
（3）、－; 0000;+;应输出“01”.
（4）、; －;+;应输出“0”.
（5）、; －;+;应输出“1”。
（6）、－99; －99;+;应输出“－9998”.
（7）9999;1;+;应输出“0000”.
二、设计思路
我们首先要考虑的是如何表示长整型数。按照传统习惯要求每4位数形成1组，而一个长整型数可能会有很多组这种4位数，而每节之间是有先后顺序的，因此我们可以考虑用数组和链表来存储数据。(1)再考虑到每个长整型数的长度在输入之间是无法预知的，因此使用链表在存储空间的分配上更方便一些。
(2)在输入数据时总是从高位到低位地存储，而计算时总是从低位向高位运算，因此采用双向链表更方便，而为了从头结点方便地转到尾结点可以采用循环链表。总之，为了实现上述功能，应以双向循环链表表示长整数，每个结点含一个整型变量，且仅绝对值不超过9999的整数，整个链表用十进制数表示。(3)对于每一个长整型数可以设置一个头结点，其中的数据域用来表示该长整型数的正负号及组数，该值的符号则表示该长整型数的符号，该数的绝对值表示该长整型数包含的4位数的组数。第一个存储4位数据组的结点称为首结点，而最后一个4位数据组结点称为尾结点。
为此需要两个结构数据类型：双向循环链表和长整数，两个类型采用相同的结构，只是双向循环链表用来存储数据，长整型用表示数据的运算。
1、 双向循环链表的数据结构及操作定义如下：
typedef short ElemType; //定义基本数据类型，我们采用short 来表示任意4位整数。
typedef struct DuCiLinkNode{ // 双向循环链表结点的存储结构
ElemType data;
struct DuCiLinkNode *prior; //指向上一结点
struct DuCiLinkNode *next; //指向下一结点
}DuCiLinkNode,*DuCiLinkList; //定义双向循环链表结点及链表的类型名
基本操作：
DuCiLinkNode *MakeNode(ElemType e); //以4位整数e 构造1个双向循环链表结点
Status InitList(DuCiLinkList *L); //初始化1个双向循环链表，分配1个结点作头结点
//数据域赋初值0，上下结点指针指向自己
void DestroyList(DuCiLinkList *L); //消毁1个双向循环链表，释放它所占用的所有内存空间 //并让链表*L指向NULL
void ClearList(DuCiLinkList L); //清除1个双向循环链表，释放数据结点所占用的内存空间 //保留头结点，并将数据域置为0，上下结点指针指向自己 Status InsTail(DuCiLinkList L, ElemType e); //在双向循环链表L 的尾结点之后加入1个以e 为 //数据域的新结点, 并返回OK; 否则返回ERROR 。
Status InsFirst(DuCiLinkList L, ElemType e);
//将数据元素e 插入在线性链表L 头结点之后, 并返回OK; 否则返回ERROR 。
Status CopyList(DuCiLinkList L, DuCiLinkList C);
//将双向循环链表L 复制到双向循环链表C 中。
2、 长整数的数据类型和和操作定义为：
typedef struct DuCiLinkNode LongIntNode,*LongInt;//采用双向循环链表为实际的存储结构
void OutputNumber(LongInt a); //输出一个长整型数
void InputNumber(LongInt a,int OneOrTwo); //输入一个长整型数
void add(LongInt c,LongInt a,LongInt b); //长整型数 c = a + b
void sub(LongInt c,LongInt a,LongInt b); //长整型数 c = a - b
Status mul(LongInt c,LongInt a,LongInt b); //长整型数 c = a * b
void div(LongInt c,LongInt a,LongInt b); //长整型数 c = a / b (整除)
void rem(LongInt c,LongInt a,LongInt b); //长整型数 c = a % b (求余)
void power(LongInt c,LongInt a,int n); //长整型数 c = a ^ n (乘方)
3、 本程序包含四个模块：
1） 主程序模块：
void main() //main.c
{
初始化；
do{
接受命令；
处理命令；
}while(“命令”=“结束”)
｝
2） 程序界面模块 //IntFace.c, IntFace.h
3） 双向循环链表处理模块 // DuCiLink.c,DuCiLink.h
4） 长整型数的输入输出模块 //LongIO.c, LongInt.h
5） 长整数运算模块 //LongInt.c LongInt.h
各模块之间的调用关系如下：
三、详细设计
1、主要函数
(1)、主控模块main.c
void DoCommand() //根据输入命令进行相应的处理
void Calculate() //执行计算功能
void ReSet() //重设系统环境
(2)、程序界面模块 IntFace.c
void InitiInterface(); //界面初始化
void GoToCmdxy(); //将光标定位到命令选项提示之后
void GoToPrompt(); //将光标定位到命令选项提示行首
void ShowMainPrompt(); //显示命令选项提示
void ClearScreen(); //以清除整个屏幕，并设置为黑底白字模式
void ClearPromptLine(); //清除提示行的显示
void ClearWorkSpace(); //清除工作区的显示
void InputNumberBox(int OneOrTwo);//指定两个输入数的输入窗口，如果超过这个范围文字将自动流动 void ResultBox(); //指定计算结果的显示窗口，如果超过这个范围文字将自动流动
(3)、长整型数输入输出模块 见二小节2分节
(4)、长整型数四则运算处理模块 见二小节2分节
(5)、长整型数存储模块—双向循环链表模块 见二小节1分节
2、函数的主要调用关系图
四、调试分析及编程心得体会
1、刚开始考虑进位问题过于简单，导致测试数据时多次出错。
2、刚开始时在输入方式中花了较大功夫，而且用户界面不够友好，程序容错性较差。
3、开始写程序时源程序没有严格按单元模块结构编写，可读性较差。
4、由于初次进行系统的程序设计，层次结构划分不太合理，应在以后的设计中强化此思维，逐渐与工程设计接轨。
„„„„„„„„„„„„„„„„
五、用户手册
1、本程序的运行环境为DOS 操作系统，执行文件为LongInt.exe 。
2、进入演示程序后即显示文本方式的用户界面
3、输入命令，执行相应的功能：
1 –– 输入第1个整数 o,O –– 输入运算符
2 –– 输入第2个整数 c,C –– 执行运算 r, R –– 重置系统 q,Q –– 退出系统
六、测试结果
（1）、0和0的四则运算：
（2）、;;+;应输出“－”。
（3）、－; 0000;+;应输出“01”.
（4）、; －;+;应输出“0”.
（5）、; －;+;应输出“1”。
（6）、－99; －99;+;应输出“－9998”.
（7）9999;1;+;应输出“0000”.
略„„„„„„„„„„„„„
七、源程序代码
/*******************************************************
1、main.c 主控文件
*******************************************************/
#include "IntFace.h"/*界面模块头文件*/
#include "LongInt.h"/*长整型数处理模块头文件*/
char cmd; /* menu command */
char opt; /* operator */
int n; /* power */
LongInt a,b,c; /* Long integer numbers */
int flag_n1=0,flag_n2=0,flag_opt=0,flag_cal=0,flag_reset=1; /*标志位*/
void ReSet() /* Reset system */
{
ClearWorkSpace(); //清屏幕的工作区
flag_n1=0; //重置长整数1是否输入的标志
flag_n2=0; //重置长整数2是否输入的标志
flag_opt=0; //重置运算符 是否输入的标志
flag_cal=0; //重置是否进行了运算的标志
flag_reset=1; //重置 重置标志
}
void Calculate() //执行计算
{
int overflow = OK;
if (flag_n1*flag_n2*flag_opt == 0 ) return;
/*Input is not complete! 输入不完整则直接返回*/
switch (opt)
{
case '+': add(c,a,b); break;//执行加法运算
case '-': sub(c,a,b); break;//执行减法运算
case '*': mul(c,a,b); break;//执行乘法运算
case '/': overflow = div(c,a,b); break;//执行整除运算
case '%': rem(c,a,b); break;//执行求余运算
case '^': n = b->prior->data;power(c,a,n); break;
//暂时以长整数b 的最后一组数据为幂，执行乘方运算
};
gotoxy(2,10); //定位到输出位置
cprintf(overflow==OK ? "Result = ":"DivideBy");//输出结果提示
ResultBox(); //控制输出范围，以免搞乱程序界面
OutputNumber(c); //输出运算结果
ClearList(c); //清空长整数c
window(); //重新设置显示窗口为全屏幕
}
void DoCommand() //根据输入命令进行相应的处理
{
switch(cmd)
{
case '1':InputNumber(a,1);flag_n1=1;break; //输入第1个长整数
case '2':InputNumber(b,2);flag_n2=1;break; //输入第2个长整数
case 'O':
case 'o':opt=InputOperator();flag_opt=1;break; //输入运算符
case 'C':
case 'c':Calculate();flag_cal=1;break; //执行运算
case 'R':
case 'r':ReSet(); //重设系统以便执行下一次运算
}
}
void main()
{
InitiInterface();//初始化程序界面
InitList(&a); //初始化长整形数据a,b,c
InitList(&b);
InitList(&c);
do{
GoToCmdxy(); //将光标定位到输入命令处
cmd = getche(); //读取一个操作命令
DoCommand(); //执行相应的命令
}while(cmd!='q' && cmd != 'Q'); //如果输入的是Q 或q 则退出
DestroyList(&a); //销毁长整形数据a,b,c ，释放它们所占的
DestroyList(&b);
DestroyList(&c);
ClearScreen(); //清除屏幕上的显示
}
/*******************************************************
2、IntFace.h 程序界面模块头文件
*******************************************************/
#include
#include
#define NofMenuItem 6
#define IntMenuItem 2
struct IntFaceType
{
int height; //界面高度
int width; //界面宽度
char ProgramName[30]; //程序名
char MenuItems[NofMenuItem][12];//功能选项
int MaxItemLength; //功能选项名最大长度
char prompt[40]; //命令选项提示
int backcolor; //界面背景
int textcolor; //文本颜色
int WaitCmdx; //功能选项输入坐标x
int WaitCmdy; //功能选项输入坐标y
};
void InitiInterface(); //界面初始化
void GoToCmdxy(); //将光标定位到命令选项提示之后
void GoToPrompt(); //将光标定位到命令选项提示行首
void ShowMainPrompt(); //显示命令选项提示
void ClearScreen(); //以清除整个屏幕，并设置为黑底白字模式
void ClearPromptLine(); //清除提示行的显示
void ClearWorkSpace(); //清除工作区的显示
void InputNumberBox(int OneOrTwo);//指定两个输入数的输入窗口，如果超过这个范围文字将自动流动 void ResultBox(); //指定计算结果的显示窗口，如果超过这个范围文字将自动流动 /*******************************************************
3、IntFace.c 程序界面处理模块文件
*******************************************************/
#include "IntFace.h"
#include "dos.h"
/*界面长宽及菜单等数据，具体含义见头文件*/
struct IntFaceType IntFace = {14,40,"Long Integer Calcultor",
{"Number 1 ","Number 2 ","Operator ","Calculate","Reset ",
"Quit "},9,"Enter a hotkey: 1,2,O,C,R or Q:",BLUE,WHITE};
/*画界面框架、显示程序功能选项、输入提示等 ┌─────────── Long Integer Calcultor ───────────┐ │ Number 1 Number 2 Operator Calculate Reset Quit │ ├──────────────────────────────────┤ │ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ ├──────────────────────────────────┤ │Enter a hotkey: 1,2,O,C,R or Q: │ └──────────────────────────────────┘*/ void DrawIntFace()
{
int i,j,LenProgramName,len;
putch(218); //画左上角的转角线
LenProgramName = strlen(IntFace.ProgramName); //计算程序名称的长度
len = (IntFace.width - 4 - LenProgramName)/2; //计算程序名称左右横线的长度 for(i=0;i
putch(' ');cputs(IntFace.ProgramName);putch(' ');//显示程序名
for(i=0;i
putch(191); //画右上角的转角线
gotoxy(1,2);putch(179); //画第2行首的竖线
for(i=0;i
for(j=0;j
{
cputs(IntFace.MenuItems[j]);
for(i=0;i
}
putch(179); //画第2行尾的竖线
gotoxy(1,3);putch(195); //画第3行首的三岔线
for(i=0;i
putch(180); //画第3行尾的三岔线
for(j=4;j
{
gotoxy(1,j); //到第j 行首
putch(179); //画行首的竖线
for(i=0;i
putch(179); //画行尾的竖线
}
gotoxy(1,IntFace.height-2);putch(195); //画倒数第3行的横线
for(i=0;i
putch(180);
gotoxy(1,IntFace.height-1);putch(179); //显示倒数第2行的输入提示 len = strlen(IntFace.prompt);
cputs(IntFace.prompt);
for(i=0;i
putch(179);
gotoxy(1,IntFace.height);putch(192); //画最后一行的横线
for(i=0;i
putch(217);
}
void InitiInterface() //界面初始化
{
int i, len, lenprompt;
for(i=0;i
{
len = strlen(IntFace.MenuItems[i]);
if(len > IntFace.MaxItemLength) IntFace.MaxItemLength = len;
}
len = (IntFace.MaxItemLength + IntMenuItem) * NofMenuItem + IntMenuItem + 2;
lenprompt = strlen(IntFace.prompt); //输入提示的长度
if (len
if (IntFace.width
if (IntFace.height
IntFace.WaitCmdx = lenprompt+2; //命令输入处的X 坐标
IntFace.WaitCmdy = IntFace.height - 1; //命令输入处的Y 坐标
clrscr(); //清屏，以便显示程序界面 textbackground(IntFace.backcolor); //设置界面的背景颜色
textcolor(IntFace.textcolor); //设置界面的文本颜色
DrawIntFace(); //画出界面
}
void ClearScreen()//以清除整个屏幕，并设置为黑底白字的DOS 传统模式
{
textbackground(BLACK);
textcolor(WHITE);
clrscr();
}
void ClearPromptLine()/* 清除提示行的显示 */
{
int i;
gotoxy(2,IntFace.height-1); //到倒数第2行首
for(i=0;i
GoToPrompt();
}
void ClearWorkSpace()/* 清除工作区的显示 */
{
int i,j;
for(j=4;j
{
gotoxy(2,j); //到第j 行首
for(i=0;i
}
}
void GoToCmdxy() /* 将光标定位到命令选项提示之后 */
{
gotoxy(IntFace.WaitCmdx, IntFace.WaitCmdy);
}
void GoToPrompt() /* 将光标定位到命令选项提示行首 */
{
gotoxy(2,IntFace.height-1);
}
void ShowMainPrompt() /* 显示命令选项提示 */
{
ClearPromptLine();
cputs(IntFace.prompt);
}
void InputNumberBox(int OneOrTwo)
{ /*指定两个输入数的输入窗口，如果超过这个范围文字将自动流动*/
window(11,(OneOrTwo==1)?4:6,IntFace.width-1,(OneOrTwo==1)?5:7);
clrscr();
}
void ResultBox()
{ /*指定计算结果的显示窗口，如果超过这个范围文字将自动流动*/
window(11,10,IntFace.width-1,11);
clrscr();
}
/*******************************************************
4、LongInt.h 长整型数输入输出及运算模块头文件
*******************************************************/
#include "DuCiLink.h"
typedef struct DuCiLinkNode LongIntNode,*LongInt;//采用双向循环链表为实际的存储结构 void OutputNumber(LongInt a); //输出一个长整型数
void InputNumber(LongInt a,int OneOrTwo); //输入一个长整型数
void add(LongInt c,LongInt a,LongInt b); //长整型数 c = a + b
void sub(LongInt c,LongInt a,LongInt b); //长整型数 c = a - b
void mul(LongInt c,LongInt a,LongInt b); //长整型数 c = a * b
Status div(LongInt c,LongInt a,LongInt b); //长整型数 c = a / b (整除)
void rem(LongInt c,LongInt a,LongInt b); //长整型数 c = a % b (求余)
void power(LongInt c,LongInt a,int n); //长整型数 c = a ^ n (乘方)
/*******************************************************
5、LongIO.c 长整型数输入输出处理模块文件
*******************************************************/
#include "Intface.h"
#include "LongInt.h"
#include
void OutputNumber(LongInt a) /*输出长整型数*/
{
LongIntNode *s;
s = a->next;
if(a->data
/*第1节按实际位数显示*/
cprintf("%d%c",s->data,(s == a->prior)?'\0':',');
s = s->next;
while(s!=a)/*其它每节显示4位数，不足的以0补齐*/
{
cprintf("%04d%c",s->data,(s == a->prior)?'\0':',');
s = s->next;
}
}
void InputNumberMsg(int OneOrTwo)
{ /*显示输入两个长整型时提示 */
window();
ClearPromptLine();
cputs("Example:;");
gotoxy(2,(OneOrTwo==1)?4:6);
cprintf("Number %d:",OneOrTwo);
InputNumberBox(OneOrTwo);
}
void InputNumberErrMsg()
{ /*输入出错时的提示*/
window();
ClearPromptLine();
cprintf("One number out of [0-9999]! Please input the whole number again!"); getch();
}
void InputNumber(LongInt a,int OneOrTwo)
{ /*输入长整型数*/
char c; //记录输入时的逗号和分号
short e; //记录输入数据
short sign = 0; //记录长整型数的符号
short FirstSection = 1; //是否是第1个4位数据组
LongIntNode *pa,*s; //节点的临时指针
InputNumberMsg(OneOrTwo);//显示输入提示
ClearList(a); // 清空长整型数的存储空间
fflush(stdin); // 刷清输入缓冲区，以避免以前错误按键的残留
do{
cscanf("%d",&e);c = getche();//读取数据
if (FirstSection) //如果是第1个组, 则设置整型数的符号
{
if(e>=0) sign = 1;
if(e
FirstSection = 0;
}
if(e9999)
{ //如果每组的数值不在0-9999之内则报错并要求重输整个长整型数
InputNumberErrMsg();
InputNumberMsg(OneOrTwo);
FirstSection = 1;
ClearList(a);
fflush(stdin);/*刷清输入缓冲区*/
c=',';
}
else//如果本组数值符合要求则加入到长整型数据中
{
InsTail(a,e); //在长整型数尾端加入本组数据
a->data++; //组数加1
}
}while(c!=';');
pa = a->next; //pa指向首结点
while (pa->data == 0 && pa->next != a) //数值为0且不是尾结点则删除
{ /*输入时可在前几节输入多个0，需要删除，但又不能将0删除完*/
s = pa; pa = pa->next; //s指向当前结点,pa 指向下结点
a->next = pa; //断开对s 的链接
pa->prior = a;
free(s); //释放s
a->data--; //组数减1
}
a->data *= sign; //设置长整型数的符号
InputNumberMsg(OneOrTwo); //以正规格式显示长整数1
OutputNumber(a);
window(); //重置显示窗为整个屏幕
ShowMainPrompt(); //回到功能选项等待命令输入
}
char InputOperator() //输入运算符
{
char opt;
window();
ClearPromptLine();
cputs("Input the operation type ( + - * / % ^ )");
gotoxy(2,8);
cprintf("Operator:");
fflush(stdin); //刷清输入缓冲区
do{
opt = getche();
gotoxy(11,8); //回退1格以便再次输入
}while(opt!='+' && opt!='-' && opt!='*'
&& opt!='/' && opt!='%' && opt!='^');//输入字符是否符合要求
ShowMainPrompt(); //回到功能选项等待命令输入
return opt;
}
/*******************************************************
6、LongInt.c 长整型数运算处理模块文件
*******************************************************/
#include "LongInt.h"
Status UnsignedAdd(LongInt c,LongInt a,LongInt b)
{ /*无符号数相加，是普通加减法的基础*/
short sum,carry=0; //进位
LongIntNode *pa,*pb;
pa = a->prior; /*pa,pb分别指两个加数的尾结点*/
pb = b->prior;
while(pa!=a && pb!=b)/* a 和 b 中都有没加的组时，执行加法*/
{
sum = pa->data + pb->data + carry;
carry = sum / 10000; /*进位*/
sum = sum % 10000; /*余数，为当前组的数值*/
if (!InsFirst(c,sum)) return ERROR;/*加到和长整型数的首位*/
pa = pa->prior; /*下一组*/
pb = pb->prior;
c->data++; /*组数加1*/
}
while(pa!=a)/* a 中还有没加的组时，补到和上去*/
{
sum = pa->data + carry;
carry = sum / 10000;
sum = sum % 10000;
if (!InsFirst(c,sum)) return ERROR;
pa = pa->prior;
c->data++;
}
while(pb!=b)/* b 中还有没加的组时，补到和上去*/
{
sum = pb->data + carry;
carry = sum / 10000;
sum = sum % 10000;
if (!InsFirst(c,sum)) return ERROR;
pb = pb->prior;
c->data++;
}
if(carry)/* 如果还有进位*/
{
if (!InsFirst(c,carry)) return ERROR;
c->data++;
}
return OK;
}
Status UnsignedSub(LongInt c,LongInt a,LongInt b)
{ /*无符号数相减，总是用绝对值大的数减绝对小的数
是普通加减法的基础*/
short diff,borrow=0;
LongIntNode *pa,*pb,*pc,*s;
pa = a->prior;
pb = b->prior;
while(pa!=a && pb!=b)
{
diff = pa->data - borrow - pb->data;
if (diff
if (!InsFirst(c,diff)) return ERROR;
pa = pa->prior;
pb = pb->prior;
c->data++;
}
while(pa!=a)
{
diff = pa->data - borrow;
if (diff
if (!InsFirst(c,diff)) return ERROR;
pa = pa->prior;
c->data++;
}
if(borrow || pb!=b) return PleaseExchange;
/* 不够减，提请调用程序交换a,b */
pc = c->next;
while (pc->data == 0 && pc->next != c)
{/*相减可能造成前几节数据为0，需要删除，但结果为零时又不能将0删除完*/
s = pc; pc = pc->next;
c->next = pc;
pc->prior = c;
free(s);
c->data--;
}
return OK;
}
void add(LongInt c,LongInt a,LongInt b)
{
if ((a->data * b->data) > 0)
{ /*两数同号，则执行无符号加法，零为当成正数处理*/
UnsignedAdd(c,a,b);
c->data *= (a->data>=0)?1:-1;
}
else /*两数异号，则执行无符号减法*/
{ /*总是用绝对值大的数减绝对小的数*/
if(UnsignedSub(c,a,b) == PleaseExchange)
{ /* a不够b 减，则交换a,b 的顺序再减*/
ClearList(c);
UnsignedSub(c,b,a);
c->data *= (b->data>=0)?1:-1;
}
else/* a够b 减 */
{
c->data *= (a->data>=0)?1:-1;
}
}
}
void sub(LongInt c,LongInt a,LongInt b)
{ /*变减法为加法*/
b->data *= -1;
add(c,a,b);
b->data *= -1;
}
void mul(LongInt c,LongInt a,LongInt b)
{
long product,carry=0; //进位
short sum;
LongIntNode *pa,*pb,*pcend,*pccur,*pc,*s;
pa = a->prior; /*从a 的尾结点，即最后一个4位组开始*/
pcend = c; /*记录a 的每一组与b 相乘时最低位应加到积的哪一组之前*/
while(pa!=a) /*只要a 中还有结点未纳入运算，则循环*/
{
if (pa->data == 0) /*如果a 的当前4位组为0，则直接加0*/
{
InsFirst(c,0);
c->data++;
}
else
{
pccur = pcend->prior;/*记录乘数应加到积的哪一组*/
pb = b->prior; /*取b 的每组与a 的当前组相乘*/
while(pb!=b)
{ /*特别注意两个0-9999以内的数相乘需要用long 来记录，否则会有溢出*/ product = carry + (long)pa->data * (long)pb->data;
carry = product / 10000;/*进位*/
product = product % 10000;/*余数，也即当前组的值*/
if (pccur == c) /*需要新的结点来存放数据*/
{
InsFirst(c,(short)product);
pccur = c->next;
c->data++;
}
else /*以前的运算已经插入过本4位组，则增加到当前组上*/
{
sum = pccur->data + (short)product;
if (sum > 9999){carry++; sum -= 10000;}
pccur->data = sum;
}
pccur = pccur->prior; /*移动乘积数的当前指针*/
pb = pb->prior; /*移动被乘数的当前指针*/
}/*如果还有进位，则加上去*/
if(carry>0) InsFirst(c,(short)carry);
carry = 0;c->data++;/*清空进位器，并将4位数组数加1*/
}
pcend = pcend->prior; /*乘积数的最低位上移一组*/
pa = pa->prior; /*乘数上移一组*/
}
c->data *= ((a->data * b->data)>=0)?1:-1;
pc = c->next;
while (pc->data == 0 && pc->next != c)
{ /*相乘可能造成前几节数据为0，需要删除，但结果为零时又不能将0删除完*/
s = pc; pc = pc->next;
c->next = pc;
pc->prior = c;
free(s);
c->data--;
}
}
void Addn(LongInt c, short n)
{ /*一个正的长整型加一个最大为20000的正数*/
short carry = n,sum;
LongIntNode *pc;
pc = c->prior;
while(carry != 0 && pc != c)
{
sum = pc->data + carry;
carry = sum / 10000;
sum = sum % 10000;
pc->data = sum;
pc = pc->prior;
}
while(carry != 0)/*如果进位不为零说明需要新的结点*/
{
sum = carry;
carry = sum / 10000;
sum = sum % 10000;
InsFirst(c,sum);
c->data++;
}
}
Status div(LongInt c,LongInt a,LongInt b)/*整除*/
{ //变除为减可以较容易地实现整除，但实际中的意义可能不大
LongInt d,e;
short i = 0,EnoughSub;
short adata = a->data, bdata = b->data;
if(b->data == 1 && b->next->data == 0) return OVERFLOW;
if (a->data data *= -1;
if (b->data data *= -1;
InitList(&d);InitList(&e); /*使用临时长整型数*/
CopyList(a,e); /* e = a */
EnoughSub = UnsignedSub(d,e,b); /* d = e - b */
while(EnoughSub == OK)
{
i++;
if (i == 20000)/*多次相减后再才保存*/
{
Addn(c,i);
i = 0;
}
ClearList(e);CopyList(d,e);ClearList(d);
EnoughSub = UnsignedSub(d,e,b);
/*若采用自减运算则可能没有这样复杂*/
}
Addn(c,i);/*将最后的尾数补上*/
a->data = adata; b->data = bdata;
c->data *= ((adata*bdata >= 0)?1:-1);
DestroyList(&d);DestroyList(&e);
return OK;
}
void rem(LongInt c,LongInt a,LongInt b)/*求余*/
{ //变除为减可以较容易地实现整除，但实际中的意义可能不大
LongInt e;
int EnoughSub;
short adata = a->data, bdata = b->data;
if (a->data data *= -1;
if (b->data data *= -1;
InitList(&e);
CopyList(a,c);
EnoughSub = UnsignedSub(e,c,b);
while(EnoughSub == OK)
{ /*若采用自减运算则可能没有这样复杂*/
ClearList(c);CopyList(e,c);ClearList(e);
EnoughSub = UnsignedSub(e,c,b);
}
a->data = adata; b->data = bdata;
if(adata data *= -1;
DestroyList(&e);
}
void power(LongInt c,LongInt a,int n)
{ /*乘方运算，变乘方为累乘*/
int i;
LongInt b;
if (n==0){InsFirst(c,0);return;}
else if(n==1){CopyList(a,c);return;}
InitList(&b);
CopyList(a,b);
for(i=0;i
{
mul(c,a,b);
ClearList(b);
CopyList(c,b);
ClearList(c);
}
mul(c,a,b);
DestroyList(&b);
}
/*******************************************************
7、DuCiLink.h 双向循环链表处理模块头文件
*******************************************************/
#include
#include
#define TRUE 1 //定义一些常数
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define PleaseExchange 22
typedef int Status; //定义函数返回值的类型
typedef short ElemType; //定义基本数据类型，我们采用short 来表示任意4位整数。
typedef struct DuCiLinkNode{ // 双向循环链表结点的存储结构
ElemType data;
struct DuCiLinkNode *prior; //指向上一结点
struct DuCiLinkNode *next; //指向下一结点
}DuCiLinkNode,*DuCiLinkList; //定义双向循环链表结点及链表的类型名
DuCiLinkNode *MakeNode(ElemType e); //以4位整数e 构造1个双向循环链表结点
Status InitList(DuCiLinkList *L); //初始化1个双向循环链表，分配1个结点作头结点 //数据域赋初值0，上下结点指针指向自己
void DestroyList(DuCiLinkList *L); //消毁1个双向循环链表，释放它所占用的所有内存空间 //并让链表*L指向NULL
void ClearList(DuCiLinkList L); //清除1个双向循环链表，释放数据结点所占用的内存空间 //保留头结点，并将数据域置为0，上下结点指针指向自己 Status InsTail(DuCiLinkList L, ElemType e); //在双向循环链表L 的尾结点之后加入1个以e 为 //数据域的新结点, 并返回OK; 否则返回ERROR 。 Status InsFirst(DuCiLinkList L, ElemType e);
//将数据元素e 插入在线性链表L 头结点之后, 并返回OK; 否则返回ERROR 。
Status CopyList(DuCiLinkList L, DuCiLinkList C);//将双向循环链表L 复制到双向循环链表C 中。 /*******************************************************
8、DuCiLink.c 双向循环链表处理模块代码
*******************************************************/
#include "DuCiLink.h"
DuCiLinkNode *MakeNode(ElemType e)
{ /*以e 为数据申请并构造一个结点*/
DuCiLinkNode *s;
s = (DuCiLinkNode *)malloc(sizeof(DuCiLinkNode));
if (s) s->data = e;
return s;
}
Status InitList(DuCiLinkList *L)
{ /*初始化1个双向循环链表，分配1个结点作头结点数据域赋初值0，上下结点指针指向自己*/ (*L) = (DuCiLinkNode *)malloc(sizeof(DuCiLinkNode));
if (!(*L)) return OVERFLOW; //存储分配失败
(*L)->data = 0;
(*L)->prior = (*L);
(*L)->next = (*L);
return OK;
}
void DestroyList(DuCiLinkList *L)
{ /*消毁1个双向循环链表，释放它所占用的所有内存空间并让链表*L指向NULL*/ DuCiLinkNode *p,*s;
p = (*L)->prior;
(*L)->prior = NULL;
while(p){s = p; p = p->prior; free(s);}
(*L) = NULL;
}
void ClearList(DuCiLinkList L)
{ /*清除1个双向循环链表，释放数据结点所占用的内存空间
保留头结点，并将数据域置为0，上下结点指针指向自己*/
DuCiLinkNode *p,*s;
p = L->prior;
while(p!=L){s = p; p = p->prior; free(s);}
L->data = 0;
L->prior = L;
L->next = L;
}
Status CopyList(DuCiLinkList L, DuCiLinkList C)
{ /*将双向循环链表L 复制到双向循环链表C 中。*/
DuCiLinkNode *p,*s;
C->data = L->data;
p = L->prior;
while(p!=L)
{
s = (DuCiLinkNode *)malloc(sizeof(DuCiLinkNode));
if (!s) return OVERFLOW; //存储分配失败
s->data = p->data;
C->next->prior = s;
s->next = C->next;
s->prior = C;
C->next = s;
p = p->prior;
}
return OK;
}
Status InsTail(DuCiLinkList L, ElemType e)
{ /*在双向循环链表L 的尾结点之后加入1个以e 为
数据域的新结点, 并返回OK; 否则返回ERROR 。*/
DuCiLinkNode *s;
s = (DuCiLinkNode *)malloc(sizeof(DuCiLinkNode));
if (!s) return OVERFLOW; //存储分配失败
s->data = e;
s->prior = L->prior;
s->next = L;
L->prior->next = s;
L->prior = s;
return OK;
} // InsTail
Status InsFirst(DuCiLinkList L, ElemType e)
{// 将数据元素e 插入在线性链表L 头结点之后, 并返回OK; 否则返回ERROR 。
DuCiLinkNode *s;
s = (DuCiLinkNode *)malloc(sizeof(DuCiLinkNode)); if (!s) return OVERFLOW; //存储分配失败 s->data = e;
L->next->prior = s;
s->next = L->next;
s->prior = L;
L->next = s;
return OK;
} // InsTail