*******************
实践教学
*******************
兰州理工大学
技术工程学院
2013年春季学期
课程设计
题 目： 长整数的加减运算 专业班级：计算机科学与技术一班 姓 名： 郭利强 学 号： 11730108 指导教师： 王连相 成 绩：
计算机科学与技术专业
数据结构课程设计任务书
（11级）
题目：长整数的加减运算
学生姓名： 郭利强 学号： 11730108 班级： 11级计算机科学与技术一班
题目类型：软件工程（R ） 指导教师： 王连相
一． 题目简介
该设计要求学生设计程序，实现两个任意长的整数求和及差的运算问题。通过该题目的设计过程，可以加深理解线性表的逻辑结构、存储结构，掌握线性表上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。
二． 主要任务
第一部分：基本算法实现
1、线性结构基本算法实现（指导老师根据题目指定）； 2、树型结构基本算法实现（指导老师根据题目指定）； 3、图型结构基本算法实现（指导老师根据题目指定）； 4、查找基本算法实现（指导老师根据题目指定）； 5、排序基本算法实现（指导老师根据题目指定）； 第二部分：指定题目的设计与实现 1、查阅文献资料，一般在3篇以上； 2、建立数据的逻辑结构和物理结构； 3、完成相应算法的设计；
4、完成测试工作； 5、撰写设计说明书； 6、做好答辩工作。
三． 主要内容、功能及技术指标
（1）使用双向循环链表存储长整数，每个结点含一个整型变量，主要功能有：长整数输入（建立双向循环链表）、长整数的加法、长整数的减法及结果的显示输出等；
（2）至少要用10组测试数据，算法对于这些合法的输入数据都能产生满足规格说明要求的结果；
（3）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出有效信息；
（4）任何整型变量的范围是-(215-1)~（215-1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开，例1，0000，0000，0000；而输入为1，0001，0001和-1，0001，0000实现加法时，应输出"1" ；
（5）较高要求：使程序在整型量范围是-(2n-1)~(2n-1)的计算机上都能有效地运行。其中，n 是由程序读入的参量。
四． 提交的成果
1. 设计说明书一份，内容包括：
1) 中文摘要100字；关键词3-5个； 2) 序言；
3）采用类c 语言定义相关的数据类型 4）各模块的伪码算法 5）函数的调用关系图 6）调试分析
a 、调试中遇到的问题及对问题的解决方法； b 、算法的时间复杂度和空间复杂度。
7）测试结果 8）源程序（带注释）
9) 设计总结、参考文献、致谢等。 2. 刻制光盘一张。
五． 主要参考文献
1．严蔚敏，吴伟民. 《数据结构（C 语言版）》. 清华大学出版社. 2．严蔚敏，吴伟民. 《数据结构题集（C 语言版）》. 清华大学出版社.
3 ．《DATA STRUCTURE WITH C++》. William Ford,William Topp .清华大学出版社（影印版）.
4．谭浩强. 《c 语言程序设计》. 清华大学出版社.
5．数据结构与算法分析（Java 版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 张铭, 刘晓丹译 电子工业出版社 2001 年1月 六、各阶段时间安排（共2周）
2013年6月28日
摘要
数据结构解决实际应用中的问题，将学习的理论知识应用于实践，增强学生解决
实际问题的能力。采用的基本数据结构为线性表。计算机存储的数据是有范围限制的，对于超出存储限制的数据无法直接在计算机中计算，为此需要设计相应的程序来完成这种超出范围限制的长整数间的加减运算。实现任意长的整形数进行加减运算 的程序，要求完成长整数的加、减运算。在这里长整数没有范围限制，可任意长。运算后的进位、借位等都要进行正确处理，可实现动态的输入，实时的输出。
关键字：任意长整数，加、减运算
序言
课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次程序设计中我选择了长整数的代数计算这个题目，在一般的程序运算中，长整数是无法计算的，因为计算机一次能够运算的位数是有限，一旦整数很长，就需要一个程序来进行多次计算，通过这个程序，可一把一个长整数分成多个普通整数来进行计算，使得长整数也可以进行运算。我编写的这个程序就可以进行加减乘除的运算，各个数据也可以是负数。
目录
一、概要设计„„„„„„„„„„„„„„„„„„„„„„„
1.1数据结构„„„„„„„„„„„„„„„„„„„„„„ 1.2使用函数„„„„„„„„„„„„„„„„„„„„„„ 二、流程图„„„„„„„„„„„„„„„„„„„„„„„„ 三、详细设计„„„„„„„„„„„„„„„„„„„„„„„ 3.1数据结构详细设计„„„„„„„„„„„„„„„„„„
3.2链表初始化函数：„„„„„„„„„„„„„„„„„„ 3.3计算已知的链表长度：„„„„„„„„„„„„„„„„ 3.4插入函数：„„„„„„„„„„„„„„„„„„„„„ 3.5绝对值函数：„„„„„„„„„„„„„„„„„„„„ 3.6读入数据并插入对应的链表函数：„„„„„„„„„„„ 3.7输出函数„„„„„„„„„„„„„„„„„„„„„„ 3.8加法函数（正数加上正数）„„„„„„„„„„„„„„ 3.9判断俩正数大小函数：„„„„„„„„„„„„„„„„ 3.10减法函数：„„„„„„„„„„„„„„„„„„„„„ 3.11整合八种情况函数：„„„„„„„„„„„„„„„„„ 3.12主函数：„„„„„„„„„„„„„„„„„„„„„„ 四、调试分析„„„„„„„„„„„„„„„„„„„„„„„„ 4.1调试过程中遇到的问题„„„„„„„„„„„„„„„„ 五、使用说明和测试结果„„„„„„„„„„„„„„„„„„„ 5.1使用说明„„„„„„„„„„„„„„„„„„„„„„ 5.2测试结果„„„„„„„„„„„„„„„„„„„„„„ 附录„„„„„„„„„„„„„„„„„„„„„„„„„„„„ 设计总结„„„„„„„„„„„„„„„„„„„„„„„„„„ 参考文献„„„„„„„„„„„„„„„„„„„„„„„„„„ 致谢„„„„„„„„„„„„„„„„„„„„„„„„„„„„
一、概要设计
1.1数据结构
此实验采用的数据结构是双向循环链表。这样可以很容易的找到他的前驱以及它的后继。节点采用结构体类型，代码如下：
typedef struct Node // 双向链表的结构体定义 {
int data;
struct Node *prior; struct Node *next; }DLNode;
1.2使用函数
1) void ListInitiate(DLNode **head)
操作结果：初始化一个头结点为head 的双向循环链表； 2) int ListLength(DLNode *head)
操作结果：计算以head 为头结点的链表的长度 3) int ListInsert(DLNode *head,int i,int x) 操作结果：将节点数据为x 的节点插到第i 个位置上去。 4) int abs(int x)
操作结果：绝对值函数，返回x 的绝对值。 5) int InputNumber(DLNode *head)
操作结果：将从键盘中接收数据并把得到的数据存入以head 为头结点的链表中。四位一存，中间以逗号区分，结束符为分号。 6) void OutputNumber(DLNode *head,int sign)
操作结果：将以head 为头结点的链表中的所有数据输出到显示屏上，
7) void add(DLNode *head1,DLNode *head2,DLNode *head3) 操作结果：实现正数加正数的加法操作。 8) int change(DLNode *head1,DLNode *head2)
操作结果：判断存在俩个链表中的数的大小，如何head1中的数大于head2中的数那么返回值为0，反之返回值为1，相等时返回值为2；
9) void minus(DLNode *head1,DLNode *head2,DLNode *head3) 操作结果：计算正数减正数的减法运算。
10) void yunsuan(DLNode *head1,DLNode *head2,DLNode *head3,char ch) 操作结果：正数，负数，加法，减法。计算式共分为八种运算，在这之前我已经实现了二种运算，那么这个函数就是把这八种运算按照一定的规则转化成已经实现的二种运算来实现完整的加减法运算。 11) void main()
操作结果：主函数。调用以上的各个函数来引导用户进行长整数的加法运算，加法运算.
二、函数流程图
三、详细设计
3.1数据结构详细设计
typedef struct Node // 双向链表的结构体定义
{
int data; struct Node *prior; struct Node *next;
}DLNode;
双向循环链表的节点由三个部分组成，第一是数据部分data 存储此节点的数据，第二是此节点的前驱指针部分*prior指向此节点的前驱，第三是此节点的后继指针部分*next指向此节点的后继。数据部分我们约定它为整形变量，前驱后继指针均为结构体Node 类型。
3.2链表初始化函数：
void ListInitiate(DLNode **head) //双向链表的初始化
{
}
初始化之前需要定义一个类型为Node 型的头结点变量，经过函数后完成链表的初始化即：头节点的前驱指针指向自己，同时他的后继指针也指向自己。 if ((*head=(DLNode *)malloc(sizeof (DLNode)))==NULL) exit(0); (*head)->prior=*head; (*head)->next=*head;
3.3计算已知的链表长度：
int ListLength(DLNode *head) //双向链表的表长
{
DLNode *p=head;
int size=0; while (p->next!=head) { } p=p->next; size++;
return size;
}
此函数计算的是已知链表的长度。主要思想：从头结点开始寻找下一个节点，找到计数器加一。直到再次寻找到头结点时停止，计算完毕。
3.4插入函数：
int ListInsert(DLNode *head,int i,int x) //双向链表的数据插入,i 表示是插入的第几个元素
{
DLNode *p,*s; int j; p=head->next; j=0; while (p!=head&&jnext; j++;
} if ((s=(DLNode *)malloc(sizeof (DLNode)))==NULL) exit(0); s->data=x; s->prior=p->prior;//插入 p->prior->next=s; s->next=p; p->prior=s; return 1;
此函数是已知一双向链表实现在第i 个位置插入data 为x 的节点。函数需要注意的是在什么位置插入才是合法的，在就是在该节点指针时的顺序不要搞错。
3.5绝对值函数：
int abs(int x)
{
}
此函数是实现求一个整数的绝对值。设计这么一个函数主要是考虑到在存储负数的时候头结点应该变为正整数，然后通过其他手段变相实现那种运算。 if (x
3.6读入数据并插入对应的链表函数：
int InputNumber(DLNode *head) //读入输入的数据
{
int input,i=0;//第i 个节点 char c; scanf("%d%c",&input,&c); while (1) { if (input
} } { } else if (input>=0&&i==0)//输入数为正且是第一个节点 { } else { } i++; if (c==';' ) break ; //遇到数据输入完成标志，跳出循环 scanf("%d%c",&input,&c); if (head->next->data>=0) { } //input=-1*input; ListInsert(head,i,input); ListInsert(head,i,input);//非第一个节点 else head->data=1;//将长整数的符号保存在头结点中 ListInsert(head,i,input);//插入数据 head->data=0;//将长整数的符号保存在头结点中 //input=abs(input);//取输入数字的绝对值 ListInsert(head,i,input);//插入数据 return 1;
此函数实现的是从键盘上得到数据根据三种情况进行不同的处理，判断是否是头结点，判断是否是整数，判断输入的字符是否是“；”分号。并且如果是正整数它的头结点data 等于1否则为0。
3.7输出函数
void OutputNumber(DLNode *head,int sign) //从表尾输出数据元素 {
DLNode *r=head->next; while (r->data==0&&r!=head->prior) { } if (sign==1) { } else { } printf("%d",r->data); r=r->next; while (r!=head) { if (r->datadatadata); printf(" 结果是: -"); printf(" 结果是:"); r=r->next; printf(",00" ); printf("%d",r->data);
} } } else if (r->datanext; printf(",%d",r->data); printf(",0" ); printf("%d",r->data); printf("\n");
此函数实现的是将最后的结果输出到显示屏上，经过判断数据的正负和数据的范围来进行不同的处理，以保证在显示屏上显示的是正确的格式。
3.8加法函数（正数加上正数）
void add(DLNode *head1,DLNode *head2,DLNode *head3){
int z=0;
int e; DLNode *p1,*p2;
p1=head1->prior;
p2=head2->prior; while (p1!=head1&&p2!=head2) { e=p1->data+p2->data+z;
} if (e>=10000) { } else z=0; ListInsert(head3,0,e); p1=p1->prior;p2=p2->prior; z=1; e=e%10000;
if (p1==head1&&p2!=head2)
{
while (p2!=head2) { e=p2->data+z; if (e>=10000) { } else z=0; ListInsert(head3,0,e); p2=p2->prior; z=1; e=e%10000; } if (z==1) ListInsert(head3,0,z);
}
else if (p1!=head1&&p2==head2){
while (p1!=head1) {
e=p1->data+z; if (e>=10000) { } z=1; e=e%10000; else z=0;
ListInsert(head3,0,e);
p1=p1->prior; } if (z==1) ListInsert(head3,0,z);
}
else {
if (z==1) ListInsert(head3,0,z);
}
}
此函数实现的是两个正数之间的相加运算，主要的算法和我们手算加法是一样的，首先设置一个进位计数的变量，根据存储的特点从低位开始相加带上进位即可得出相应的位和，最后更新进位变量。处理边界状况：如果两个链表一样长同时他们最高位在计算完成时仍然会有进位，那么应该考虑到在数据的更高位插入一个1表示最后的计算结果，这样才可以保证数据的完整性。
3.9判断俩正数大小函数：
int change(DLNode *head1,DLNode *head2)
{
int length1,length2,r=2; length1=ListLength(head1);
length2=ListLength(head2);
DLNode *p1,*p2;
p1=head1->next; p2=head2->next; if (length1>length2) { } else if (length1data>p2->data) { } else if (p2->data>p1->data) { } r=1; return r; break ; r=0; return r; break ; r=1; return r; r=0; return r;
} } else { } p1=p1->next; p2=p2->next; r=2; return r;
}
此函数实现的是判断俩个正数的大小。考虑俩正数的在链表中所占存储单元的多少，多的一定大，当他们一样长时，一位一位的比较直到找到一个节点中的data 比另一个链表的对应节点的data 大为止。如果最后仍是一样大那么这两个数就是一样大的。返回值为自己约定的参数r 等于2表示俩数一样大，等于1表示第二个数大，等于 0表示第一个数大。
3.10 减法函数：
void minus(DLNode *head1,DLNode *head2,DLNode *head3)
{
int z=0,x=-1; int e; DLNode *p1,*p2; p1=head1->prior; p2=head2->prior; x=change(head1,head2); if (x==0) { while (p1!=head1&&p2!=head2) {
} p1->data=p1->data+z; if (p1->data>=p2->data) { } else { e=10000+p1->data-p2->data; ListInsert(head3,0,e); e=p1->data-p2->data; ListInsert(head3,0,e); p1=p1->prior;p2=p2->prior; z=0; p1=p1->prior;p2=p2->prior; } z=-1; p1->data=p1->data+z; while (p1!=head1) { e=p1->data;
ListInsert(head3,0,e);
p1=p1->prior; }
}
else if (x==1) { p2=head1->prior; p1=head2->prior; while (p1!=head2&&p2!=head1)
{ } p1->data=p1->data+z; p1->data=p1->data+z; if (p1->data>=p2->data) { } else { e=10000+p1->data-p2->data; ListInsert(head3,0,e); e=p1->data-p2->data; ListInsert(head3,0,e); p1=p1->prior;p2=p2->prior; z=0; p1=p1->prior;p2=p2->prior; } z=-1; while (p1!=head2) { e=p1->data;
ListInsert(head3,0,e);
p1=p1->prior; } head3->next->data=-1*head3->next->data; } else { head3->next->data=0;
}
}
此函数实现的是两个正数的减法运算。整个函数分为俩大部分，第一部分处理第一个数大于第二个数，第二部分是处理第二个数大于第一个数。在这个为题上我们想了好长时间，感觉俩部分可以 结合成一部分，但是由于知识所限没有想出更好的办法，这使得代码量增加了足足一倍之多。仍然模仿手算减法，先找到俩数字中最大的那个，用大的减去小的。最后判断符号位。
3.11整合八种情况函数：
void yunsuan(DLNode *head1,DLNode *head2,DLNode *head3,char ch)
{
DLNode *p1,*p2; p1=head1->next; p2=head2->next; if (head1->data==1&&head2->data==1) { } else if (head1->data==1&&head2->data==0) { if (ch=='+') { head2->next->data*=-1; if (ch=='+') add(head1,head2,head3); else minus(head1,head2,head3); minus(head1,head2,head3); } else { head2->next->data*=-1;
} } add(head1,head2,head3); else if (head1->data==0&&head2->data==1) { } else { if (ch=='+') { } head1->next->data*=-1; head2->next->data*=-1; add(head1,head2,head3); head3->next->data*=-1; if (ch=='+') { } else { } head1->next->data*=-1; head2->next->data*=-1; add(head1,head2,head3); head3->next->data*=-1; head1->next->data*=-1; minus(head2,head1,head3); else {
}
} } head1->next->data*=-1; head2->next->data*=-1; minus(head2,head1,head3);
此函数实现的是八种情况的整合。八种情况分别是正数加正数、正数加负数、正数减正数、正数减负数、负数加负数、负数加正数、负数减正数、负数减负数。此函数调用已经做好的正数加正数和正数减正数函数判断符号位，根据一定的规则实现八种运算。
3.12主函数：
void main()
{
char ch,ch1; while (1) { //int w=-1; DLNode *a,*b,*c; ListInitiate(&a); ListInitiate(&b); ListInitiate(&c); printf(" 请输入数A(以分号结束):"); InputNumber(a); //printf("\n"); printf(" 请输入数B(以分号结束):"); InputNumber(b); //w=change(a,b); printf(" 请选择操作符：:\n");
} } scanf("%s",&ch1); if (ch1=='+'||ch1=='-' ) { } else if (ch1=='*') chengfa(a,b); else printf(" 此版本不支持%c运算" ,ch1); printf(" 要继续吗？(y/n) :"); scanf("%s",&ch); if (ch=='Y' ||ch=='y' ) { } else exit(0); printf("\n"); continue ; yunsuan(a,b,c,ch1); OutputNumber(c,1);
此函数是主函数。主要的作用是为用户做一个提示，如何完成自己想要的运算。同时调用各个函数实现运算。
四、调试分析
4.1调试过程中遇到的问题
在函数编写之前我首先写出了所有函数的框架以及各个函数之间的关系，根据逐步求精的思想来完善整个程序。即使是这样我仍然遇到了不少错误。
例如：在实现正数减正数时，我一开始没有分为以上所说的俩个部分，而是把俩个部分整合到一起实现一个大函数，但是在我运行调试时结果大不如人意，出现的都是匪夷所思的数字，我根本就推算不出这些数字是怎么来的。没有办法我只好在另辟途径来完成函数的实现。于是我就分作两个部分来实现，这样逐步追踪可以使思绪更加清晰，所付出的代价是代码量增加。
五、使用说明和测试结果
5.1使用说明
用户在使用该程序时，只需按照程序中的规定进行即可实现长整数的加减运算，具体使用步骤如下：
1) 点击运行按钮，在DOS 窗口下按照规定输入的数字需要从低位开始数四位一组用
逗号隔开。输入第一个数字。
2) 同上输入第二个数；
3) 选择要对这两个长整数进行的运算。
4) 两个操作数与运算符选择完毕后，按回车键即可得到运算结果。
5.2测试结果
5) 考虑边界数字，输入0和0做加法运算，输出“0”，结果如下图：
6) 考虑加法进位（包括低位向高位的进位以及高位仍有进位情况），结果如下图：
7) 考虑减法进位并且数A 小于数B ，结果如下图：
8) 考虑减法进位并且数A 大于数B ，结果如下图：
9)连续输入两次数据测试；如下图：
10）较高要求
附录
程序的完整代码清单：
#include
#include
#include
typedef struct Node // 双向链表的结构体定义
{
int data; struct Node *prior; struct Node *next;
}DLNode;
void ListInitiate(DLNode **head) //双向链表的初始化
{
}
int ListLength(DLNode *head) //双向链表的表长
{
} DLNode *p=head; int size=0; while (p->next!=head) { } p=p->next; size++; if ((*head=(DLNode *)malloc(sizeof (DLNode)))==NULL) exit(0); (*head)->prior=*head; (*head)->next=*head; return size;
int ListInsert(DLNode *head,int i,int x) //双向链表的数据插入,i 表示是插入的第几个元素
{
}
int abs(int x)
{
} if (xnext; j=0; while (p!=head&&jdata=x; s->prior=p->prior;//插入 p->prior->next=s; s->next=p; p->prior=s; return 1; printf("\n插入位置不合法！" ); return 0; p=p->next; j++;
int InputNumber(DLNode *head) //读入输入的数据
{
int input,i=0;//第i 个节点 char c; scanf("%d%c",&input,&c); while (1) { } if (input=0&&i==0)//输入数为正且是第一个节点 { } else { } i++; if (c==';' ) break ; //遇到数据输入完成标志，跳出循环 scanf("%d%c",&input,&c); if (head->next->data>=0) { } //input=-1*input; ListInsert(head,i,input); ListInsert(head,i,input);//非第一个节点 else head->data=1;//将长整数的符号保存在头结点中 ListInsert(head,i,input);//插入数据 head->data=0;//将长整数的符号保存在头结点中 //input=abs(input);//取输入数字的绝对值 ListInsert(head,i,input);//插入数据
}
return 1;
void OutputNumber(DLNode *head,int sign) //从表尾输出数据元素 {
DLNode *r=head->next;
while (r->data==0&&r!=head->prior)
{
r=r->next;
}
if (sign==1)
{
printf(" 结果是:");
}
else
{
printf(" 结果是: -");
}
printf("%d",r->data);
r=r->next;
while (r!=head)
{
if (r->data
{
printf(",000" );
printf("%d",r->data);
}
else if (r->data
{
printf(",00" );
printf("%d",r->data);
} } } else if (r->datanext; printf(",%d",r->data); printf(",0" ); printf("%d",r->data); printf("\n");
void add(DLNode *head1,DLNode *head2,DLNode *head3){
int z=0;
int e; DLNode *p1,*p2;
p1=head1->prior;
p2=head2->prior; while (p1!=head1&&p2!=head2) { e=p1->data+p2->data+z; if (e>=10000) { } else z=0; ListInsert(head3,0,e); p1=p1->prior;p2=p2->prior; z=1; e=e%10000;
}
if (p1==head1&&p2!=head2)
{
while (p2!=head2) { e=p2->data+z; if (e>=10000) { } else z=0; ListInsert(head3,0,e); p2=p2->prior; z=1; e=e%10000; } if (z==1) ListInsert(head3,0,z);
}
else if (p1!=head1&&p2==head2){
while (p1!=head1) { e=p1->data+z; if (e>=10000) { } z=1; e=e%10000; else z=0; p1=p1->prior; ListInsert(head3,0,e); } if (z==1) ListInsert(head3,0,z);
}
else {
}
int change(DLNode *head1,DLNode *head2)
{
int length1,length2,r=2; length1=ListLength(head1); DLNode *p1,*p2; p1=head1->next; p2=head2->next; if (length1>length2) { } else if (length1data>p2->data) { r=1; return r; r=0; return r; if (z==1) ListInsert(head3,0,z); } length2=ListLength(head2);
} } } } r=0; return r; break ; else if (p2->data>p1->data) { } else { } p1=p1->next; p2=p2->next; r=2; r=1; return r; break ; return r;
void yunsuan(DLNode *head1,DLNode *head2,DLNode *head3,char ch) {
DLNode *p1,*p2; p1=head1->next; p2=head2->next; if (head1->data==1&&head2->data==1) { } else if (head1->data==1&&head2->data==0) { if (ch=='+') add(head1,head2,head3); else (head1,head2,head3);
} if (ch=='+') { } else { } head2->next->data*=-1; add(head1,head2,head3); head2->next->data*=-1; (head1,head2,head3); else if (head1->data==0&&head2->data==1) { } else { if (ch=='+') { head1->next->data*=-1; head2->next->data*=-1; if (ch=='+') { } else { } head1->next->data*=-1; head2->next->data*=-1; add(head1,head2,head3); head3->next->data*=-1; head1->next->data*=-1; (head2,head1,head3);
} } } { } add(head1,head2,head3); head3->next->data*=-1; else head1->next->data*=-1; head2->next->data*=-1; (head2,head1,head3);
void chengfa(DLNode *head1,DLNode *head2) {
}
void main()
{
char ch,ch1; int i; if ((head1->next->data*head2->next->data)next->data=abs(head1->next->data); head2->next->data=abs(head2->next->data); i=1; (head1,head2,i); head1->next->data=abs(head1->next->data); head2->next->data=abs(head2->next->data); i=0; (head1,head2,i);
} while (1) { } //int w=-1; DLNode *a,*b,*c; ListInitiate(&a); ListInitiate(&b); ListInitiate(&c); printf(" 请输入数A(以分号结束):"); InputNumber(a); //printf("\n"); printf(" 请输入数B(以分号结束):"); InputNumber(b); //w=change(a,b); printf(" 请选择操作符：:\n"); scanf("%s",&ch1); if (ch1=='+'||ch1=='-' ) { } else if (ch1=='*') chengfa(a,b); else printf(" 此版本不支持%c运算" ,ch1); printf(" 要继续吗？(y/n) :"); scanf("%s",&ch); if (ch=='Y' ||ch=='y' ) { } else exit(0); printf("\n"); continue ; yunsuan(a,b,c,ch1); OutputNumber(c,1);
设计总结
本次试验是我感觉到了理论应用与实践的意义，以前我们也做过类似的题目，所以在试验中我感觉还是比较顺利的但是还是花了我十七个小时左右才完成。根据模块化思想来把握整体结构会使自己的思路更加清晰，更加明了。得到的东西往往是说不出来的只有自己心理面最清楚。
参考文献
1．严蔚敏，吴伟民. 《数据结构（C 语言版）》. 清华大学出版社.
2．严蔚敏，吴伟民. 《数据结构题集（C 语言版）》. 清华大学出版社.
3．《DATA STRUCTURE WITH C++》. William Ford,William Topp .清华大学出版社（影印版）.
4. 谭浩强. 《c 语言程序设计》. 清华大学出版社.
5． 数据结构与算法分析（Java 版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 张铭, 刘晓丹译 电子工业出版社 2001 年1月
致谢
本次课程设计的成功完成，我首先感谢我的指导老师王连相，他自始至终都给予了我莫大的帮助，正是在王连相老师的悉心指导下我才能顺利完成本次课程设计中的每一个计划。在这次课程设计中，无论从课题选择，方案论证上，还是到具体的设计和调试，每一项安排他都提出了至关重要的建议，使我少走了许多弯路，节省了大量时间，可以说，我的课程设计的顺利完成凝聚着老师的大量心血，在此向王连相老师表示深深的感谢。
当然，我也要感谢我的同学和那些互联网上的朋友，他们毫不吝啬的将自己所掌握的知识拿出来资源共享，才能使我的部分功能模块得以实现，谢谢你们。
*******************
实践教学
*******************
兰州理工大学
技术工程学院
2013年春季学期
课程设计
题 目： 长整数的加减运算 专业班级：计算机科学与技术一班 姓 名： 郭利强 学 号： 11730108 指导教师： 王连相 成 绩：
计算机科学与技术专业
数据结构课程设计任务书
（11级）
题目：长整数的加减运算
学生姓名： 郭利强 学号： 11730108 班级： 11级计算机科学与技术一班
题目类型：软件工程（R ） 指导教师： 王连相
一． 题目简介
该设计要求学生设计程序，实现两个任意长的整数求和及差的运算问题。通过该题目的设计过程，可以加深理解线性表的逻辑结构、存储结构，掌握线性表上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。
二． 主要任务
第一部分：基本算法实现
1、线性结构基本算法实现（指导老师根据题目指定）； 2、树型结构基本算法实现（指导老师根据题目指定）； 3、图型结构基本算法实现（指导老师根据题目指定）； 4、查找基本算法实现（指导老师根据题目指定）； 5、排序基本算法实现（指导老师根据题目指定）； 第二部分：指定题目的设计与实现 1、查阅文献资料，一般在3篇以上； 2、建立数据的逻辑结构和物理结构； 3、完成相应算法的设计；
4、完成测试工作； 5、撰写设计说明书； 6、做好答辩工作。
三． 主要内容、功能及技术指标
（1）使用双向循环链表存储长整数，每个结点含一个整型变量，主要功能有：长整数输入（建立双向循环链表）、长整数的加法、长整数的减法及结果的显示输出等；
（2）至少要用10组测试数据，算法对于这些合法的输入数据都能产生满足规格说明要求的结果；
（3）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出有效信息；
（4）任何整型变量的范围是-(215-1)~（215-1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开，例1，0000，0000，0000；而输入为1，0001，0001和-1，0001，0000实现加法时，应输出"1" ；
（5）较高要求：使程序在整型量范围是-(2n-1)~(2n-1)的计算机上都能有效地运行。其中，n 是由程序读入的参量。
四． 提交的成果
1. 设计说明书一份，内容包括：
1) 中文摘要100字；关键词3-5个； 2) 序言；
3）采用类c 语言定义相关的数据类型 4）各模块的伪码算法 5）函数的调用关系图 6）调试分析
a 、调试中遇到的问题及对问题的解决方法； b 、算法的时间复杂度和空间复杂度。
7）测试结果 8）源程序（带注释）
9) 设计总结、参考文献、致谢等。 2. 刻制光盘一张。
五． 主要参考文献
1．严蔚敏，吴伟民. 《数据结构（C 语言版）》. 清华大学出版社. 2．严蔚敏，吴伟民. 《数据结构题集（C 语言版）》. 清华大学出版社.
3 ．《DATA STRUCTURE WITH C++》. William Ford,William Topp .清华大学出版社（影印版）.
4．谭浩强. 《c 语言程序设计》. 清华大学出版社.
5．数据结构与算法分析（Java 版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 张铭, 刘晓丹译 电子工业出版社 2001 年1月 六、各阶段时间安排（共2周）
2013年6月28日
摘要
数据结构解决实际应用中的问题，将学习的理论知识应用于实践，增强学生解决
实际问题的能力。采用的基本数据结构为线性表。计算机存储的数据是有范围限制的，对于超出存储限制的数据无法直接在计算机中计算，为此需要设计相应的程序来完成这种超出范围限制的长整数间的加减运算。实现任意长的整形数进行加减运算 的程序，要求完成长整数的加、减运算。在这里长整数没有范围限制，可任意长。运算后的进位、借位等都要进行正确处理，可实现动态的输入，实时的输出。
关键字：任意长整数，加、减运算
序言
课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次程序设计中我选择了长整数的代数计算这个题目，在一般的程序运算中，长整数是无法计算的，因为计算机一次能够运算的位数是有限，一旦整数很长，就需要一个程序来进行多次计算，通过这个程序，可一把一个长整数分成多个普通整数来进行计算，使得长整数也可以进行运算。我编写的这个程序就可以进行加减乘除的运算，各个数据也可以是负数。
目录
一、概要设计„„„„„„„„„„„„„„„„„„„„„„„
1.1数据结构„„„„„„„„„„„„„„„„„„„„„„ 1.2使用函数„„„„„„„„„„„„„„„„„„„„„„ 二、流程图„„„„„„„„„„„„„„„„„„„„„„„„ 三、详细设计„„„„„„„„„„„„„„„„„„„„„„„ 3.1数据结构详细设计„„„„„„„„„„„„„„„„„„
3.2链表初始化函数：„„„„„„„„„„„„„„„„„„ 3.3计算已知的链表长度：„„„„„„„„„„„„„„„„ 3.4插入函数：„„„„„„„„„„„„„„„„„„„„„ 3.5绝对值函数：„„„„„„„„„„„„„„„„„„„„ 3.6读入数据并插入对应的链表函数：„„„„„„„„„„„ 3.7输出函数„„„„„„„„„„„„„„„„„„„„„„ 3.8加法函数（正数加上正数）„„„„„„„„„„„„„„ 3.9判断俩正数大小函数：„„„„„„„„„„„„„„„„ 3.10减法函数：„„„„„„„„„„„„„„„„„„„„„ 3.11整合八种情况函数：„„„„„„„„„„„„„„„„„ 3.12主函数：„„„„„„„„„„„„„„„„„„„„„„ 四、调试分析„„„„„„„„„„„„„„„„„„„„„„„„ 4.1调试过程中遇到的问题„„„„„„„„„„„„„„„„ 五、使用说明和测试结果„„„„„„„„„„„„„„„„„„„ 5.1使用说明„„„„„„„„„„„„„„„„„„„„„„ 5.2测试结果„„„„„„„„„„„„„„„„„„„„„„ 附录„„„„„„„„„„„„„„„„„„„„„„„„„„„„ 设计总结„„„„„„„„„„„„„„„„„„„„„„„„„„ 参考文献„„„„„„„„„„„„„„„„„„„„„„„„„„ 致谢„„„„„„„„„„„„„„„„„„„„„„„„„„„„
一、概要设计
1.1数据结构
此实验采用的数据结构是双向循环链表。这样可以很容易的找到他的前驱以及它的后继。节点采用结构体类型，代码如下：
typedef struct Node // 双向链表的结构体定义 {
int data;
struct Node *prior; struct Node *next; }DLNode;
1.2使用函数
1) void ListInitiate(DLNode **head)
操作结果：初始化一个头结点为head 的双向循环链表； 2) int ListLength(DLNode *head)
操作结果：计算以head 为头结点的链表的长度 3) int ListInsert(DLNode *head,int i,int x) 操作结果：将节点数据为x 的节点插到第i 个位置上去。 4) int abs(int x)
操作结果：绝对值函数，返回x 的绝对值。 5) int InputNumber(DLNode *head)
操作结果：将从键盘中接收数据并把得到的数据存入以head 为头结点的链表中。四位一存，中间以逗号区分，结束符为分号。 6) void OutputNumber(DLNode *head,int sign)
操作结果：将以head 为头结点的链表中的所有数据输出到显示屏上，
7) void add(DLNode *head1,DLNode *head2,DLNode *head3) 操作结果：实现正数加正数的加法操作。 8) int change(DLNode *head1,DLNode *head2)
操作结果：判断存在俩个链表中的数的大小，如何head1中的数大于head2中的数那么返回值为0，反之返回值为1，相等时返回值为2；
9) void minus(DLNode *head1,DLNode *head2,DLNode *head3) 操作结果：计算正数减正数的减法运算。
10) void yunsuan(DLNode *head1,DLNode *head2,DLNode *head3,char ch) 操作结果：正数，负数，加法，减法。计算式共分为八种运算，在这之前我已经实现了二种运算，那么这个函数就是把这八种运算按照一定的规则转化成已经实现的二种运算来实现完整的加减法运算。 11) void main()
操作结果：主函数。调用以上的各个函数来引导用户进行长整数的加法运算，加法运算.
二、函数流程图
三、详细设计
3.1数据结构详细设计
typedef struct Node // 双向链表的结构体定义
{
int data; struct Node *prior; struct Node *next;
}DLNode;
双向循环链表的节点由三个部分组成，第一是数据部分data 存储此节点的数据，第二是此节点的前驱指针部分*prior指向此节点的前驱，第三是此节点的后继指针部分*next指向此节点的后继。数据部分我们约定它为整形变量，前驱后继指针均为结构体Node 类型。
3.2链表初始化函数：
void ListInitiate(DLNode **head) //双向链表的初始化
{
}
初始化之前需要定义一个类型为Node 型的头结点变量，经过函数后完成链表的初始化即：头节点的前驱指针指向自己，同时他的后继指针也指向自己。 if ((*head=(DLNode *)malloc(sizeof (DLNode)))==NULL) exit(0); (*head)->prior=*head; (*head)->next=*head;
3.3计算已知的链表长度：
int ListLength(DLNode *head) //双向链表的表长
{
DLNode *p=head;
int size=0; while (p->next!=head) { } p=p->next; size++;
return size;
}
此函数计算的是已知链表的长度。主要思想：从头结点开始寻找下一个节点，找到计数器加一。直到再次寻找到头结点时停止，计算完毕。
3.4插入函数：
int ListInsert(DLNode *head,int i,int x) //双向链表的数据插入,i 表示是插入的第几个元素
{
DLNode *p,*s; int j; p=head->next; j=0; while (p!=head&&jnext; j++;
} if ((s=(DLNode *)malloc(sizeof (DLNode)))==NULL) exit(0); s->data=x; s->prior=p->prior;//插入 p->prior->next=s; s->next=p; p->prior=s; return 1;
此函数是已知一双向链表实现在第i 个位置插入data 为x 的节点。函数需要注意的是在什么位置插入才是合法的，在就是在该节点指针时的顺序不要搞错。
3.5绝对值函数：
int abs(int x)
{
}
此函数是实现求一个整数的绝对值。设计这么一个函数主要是考虑到在存储负数的时候头结点应该变为正整数，然后通过其他手段变相实现那种运算。 if (x
3.6读入数据并插入对应的链表函数：
int InputNumber(DLNode *head) //读入输入的数据
{
int input,i=0;//第i 个节点 char c; scanf("%d%c",&input,&c); while (1) { if (input
} } { } else if (input>=0&&i==0)//输入数为正且是第一个节点 { } else { } i++; if (c==';' ) break ; //遇到数据输入完成标志，跳出循环 scanf("%d%c",&input,&c); if (head->next->data>=0) { } //input=-1*input; ListInsert(head,i,input); ListInsert(head,i,input);//非第一个节点 else head->data=1;//将长整数的符号保存在头结点中 ListInsert(head,i,input);//插入数据 head->data=0;//将长整数的符号保存在头结点中 //input=abs(input);//取输入数字的绝对值 ListInsert(head,i,input);//插入数据 return 1;
此函数实现的是从键盘上得到数据根据三种情况进行不同的处理，判断是否是头结点，判断是否是整数，判断输入的字符是否是“；”分号。并且如果是正整数它的头结点data 等于1否则为0。
3.7输出函数
void OutputNumber(DLNode *head,int sign) //从表尾输出数据元素 {
DLNode *r=head->next; while (r->data==0&&r!=head->prior) { } if (sign==1) { } else { } printf("%d",r->data); r=r->next; while (r!=head) { if (r->datadatadata); printf(" 结果是: -"); printf(" 结果是:"); r=r->next; printf(",00" ); printf("%d",r->data);
} } } else if (r->datanext; printf(",%d",r->data); printf(",0" ); printf("%d",r->data); printf("\n");
此函数实现的是将最后的结果输出到显示屏上，经过判断数据的正负和数据的范围来进行不同的处理，以保证在显示屏上显示的是正确的格式。
3.8加法函数（正数加上正数）
void add(DLNode *head1,DLNode *head2,DLNode *head3){
int z=0;
int e; DLNode *p1,*p2;
p1=head1->prior;
p2=head2->prior; while (p1!=head1&&p2!=head2) { e=p1->data+p2->data+z;
} if (e>=10000) { } else z=0; ListInsert(head3,0,e); p1=p1->prior;p2=p2->prior; z=1; e=e%10000;
if (p1==head1&&p2!=head2)
{
while (p2!=head2) { e=p2->data+z; if (e>=10000) { } else z=0; ListInsert(head3,0,e); p2=p2->prior; z=1; e=e%10000; } if (z==1) ListInsert(head3,0,z);
}
else if (p1!=head1&&p2==head2){
while (p1!=head1) {
e=p1->data+z; if (e>=10000) { } z=1; e=e%10000; else z=0;
ListInsert(head3,0,e);
p1=p1->prior; } if (z==1) ListInsert(head3,0,z);
}
else {
if (z==1) ListInsert(head3,0,z);
}
}
此函数实现的是两个正数之间的相加运算，主要的算法和我们手算加法是一样的，首先设置一个进位计数的变量，根据存储的特点从低位开始相加带上进位即可得出相应的位和，最后更新进位变量。处理边界状况：如果两个链表一样长同时他们最高位在计算完成时仍然会有进位，那么应该考虑到在数据的更高位插入一个1表示最后的计算结果，这样才可以保证数据的完整性。
3.9判断俩正数大小函数：
int change(DLNode *head1,DLNode *head2)
{
int length1,length2,r=2; length1=ListLength(head1);
length2=ListLength(head2);
DLNode *p1,*p2;
p1=head1->next; p2=head2->next; if (length1>length2) { } else if (length1data>p2->data) { } else if (p2->data>p1->data) { } r=1; return r; break ; r=0; return r; break ; r=1; return r; r=0; return r;
} } else { } p1=p1->next; p2=p2->next; r=2; return r;
}
此函数实现的是判断俩个正数的大小。考虑俩正数的在链表中所占存储单元的多少，多的一定大，当他们一样长时，一位一位的比较直到找到一个节点中的data 比另一个链表的对应节点的data 大为止。如果最后仍是一样大那么这两个数就是一样大的。返回值为自己约定的参数r 等于2表示俩数一样大，等于1表示第二个数大，等于 0表示第一个数大。
3.10 减法函数：
void minus(DLNode *head1,DLNode *head2,DLNode *head3)
{
int z=0,x=-1; int e; DLNode *p1,*p2; p1=head1->prior; p2=head2->prior; x=change(head1,head2); if (x==0) { while (p1!=head1&&p2!=head2) {
} p1->data=p1->data+z; if (p1->data>=p2->data) { } else { e=10000+p1->data-p2->data; ListInsert(head3,0,e); e=p1->data-p2->data; ListInsert(head3,0,e); p1=p1->prior;p2=p2->prior; z=0; p1=p1->prior;p2=p2->prior; } z=-1; p1->data=p1->data+z; while (p1!=head1) { e=p1->data;
ListInsert(head3,0,e);
p1=p1->prior; }
}
else if (x==1) { p2=head1->prior; p1=head2->prior; while (p1!=head2&&p2!=head1)
{ } p1->data=p1->data+z; p1->data=p1->data+z; if (p1->data>=p2->data) { } else { e=10000+p1->data-p2->data; ListInsert(head3,0,e); e=p1->data-p2->data; ListInsert(head3,0,e); p1=p1->prior;p2=p2->prior; z=0; p1=p1->prior;p2=p2->prior; } z=-1; while (p1!=head2) { e=p1->data;
ListInsert(head3,0,e);
p1=p1->prior; } head3->next->data=-1*head3->next->data; } else { head3->next->data=0;
}
}
此函数实现的是两个正数的减法运算。整个函数分为俩大部分，第一部分处理第一个数大于第二个数，第二部分是处理第二个数大于第一个数。在这个为题上我们想了好长时间，感觉俩部分可以 结合成一部分，但是由于知识所限没有想出更好的办法，这使得代码量增加了足足一倍之多。仍然模仿手算减法，先找到俩数字中最大的那个，用大的减去小的。最后判断符号位。
3.11整合八种情况函数：
void yunsuan(DLNode *head1,DLNode *head2,DLNode *head3,char ch)
{
DLNode *p1,*p2; p1=head1->next; p2=head2->next; if (head1->data==1&&head2->data==1) { } else if (head1->data==1&&head2->data==0) { if (ch=='+') { head2->next->data*=-1; if (ch=='+') add(head1,head2,head3); else minus(head1,head2,head3); minus(head1,head2,head3); } else { head2->next->data*=-1;
} } add(head1,head2,head3); else if (head1->data==0&&head2->data==1) { } else { if (ch=='+') { } head1->next->data*=-1; head2->next->data*=-1; add(head1,head2,head3); head3->next->data*=-1; if (ch=='+') { } else { } head1->next->data*=-1; head2->next->data*=-1; add(head1,head2,head3); head3->next->data*=-1; head1->next->data*=-1; minus(head2,head1,head3); else {
}
} } head1->next->data*=-1; head2->next->data*=-1; minus(head2,head1,head3);
此函数实现的是八种情况的整合。八种情况分别是正数加正数、正数加负数、正数减正数、正数减负数、负数加负数、负数加正数、负数减正数、负数减负数。此函数调用已经做好的正数加正数和正数减正数函数判断符号位，根据一定的规则实现八种运算。
3.12主函数：
void main()
{
char ch,ch1; while (1) { //int w=-1; DLNode *a,*b,*c; ListInitiate(&a); ListInitiate(&b); ListInitiate(&c); printf(" 请输入数A(以分号结束):"); InputNumber(a); //printf("\n"); printf(" 请输入数B(以分号结束):"); InputNumber(b); //w=change(a,b); printf(" 请选择操作符：:\n");
} } scanf("%s",&ch1); if (ch1=='+'||ch1=='-' ) { } else if (ch1=='*') chengfa(a,b); else printf(" 此版本不支持%c运算" ,ch1); printf(" 要继续吗？(y/n) :"); scanf("%s",&ch); if (ch=='Y' ||ch=='y' ) { } else exit(0); printf("\n"); continue ; yunsuan(a,b,c,ch1); OutputNumber(c,1);
此函数是主函数。主要的作用是为用户做一个提示，如何完成自己想要的运算。同时调用各个函数实现运算。
四、调试分析
4.1调试过程中遇到的问题
在函数编写之前我首先写出了所有函数的框架以及各个函数之间的关系，根据逐步求精的思想来完善整个程序。即使是这样我仍然遇到了不少错误。
例如：在实现正数减正数时，我一开始没有分为以上所说的俩个部分，而是把俩个部分整合到一起实现一个大函数，但是在我运行调试时结果大不如人意，出现的都是匪夷所思的数字，我根本就推算不出这些数字是怎么来的。没有办法我只好在另辟途径来完成函数的实现。于是我就分作两个部分来实现，这样逐步追踪可以使思绪更加清晰，所付出的代价是代码量增加。
五、使用说明和测试结果
5.1使用说明
用户在使用该程序时，只需按照程序中的规定进行即可实现长整数的加减运算，具体使用步骤如下：
1) 点击运行按钮，在DOS 窗口下按照规定输入的数字需要从低位开始数四位一组用
逗号隔开。输入第一个数字。
2) 同上输入第二个数；
3) 选择要对这两个长整数进行的运算。
4) 两个操作数与运算符选择完毕后，按回车键即可得到运算结果。
5.2测试结果
5) 考虑边界数字，输入0和0做加法运算，输出“0”，结果如下图：
6) 考虑加法进位（包括低位向高位的进位以及高位仍有进位情况），结果如下图：
7) 考虑减法进位并且数A 小于数B ，结果如下图：
8) 考虑减法进位并且数A 大于数B ，结果如下图：
9)连续输入两次数据测试；如下图：
10）较高要求
附录
程序的完整代码清单：
#include
#include
#include
typedef struct Node // 双向链表的结构体定义
{
int data; struct Node *prior; struct Node *next;
}DLNode;
void ListInitiate(DLNode **head) //双向链表的初始化
{
}
int ListLength(DLNode *head) //双向链表的表长
{
} DLNode *p=head; int size=0; while (p->next!=head) { } p=p->next; size++; if ((*head=(DLNode *)malloc(sizeof (DLNode)))==NULL) exit(0); (*head)->prior=*head; (*head)->next=*head; return size;
int ListInsert(DLNode *head,int i,int x) //双向链表的数据插入,i 表示是插入的第几个元素
{
}
int abs(int x)
{
} if (xnext; j=0; while (p!=head&&jdata=x; s->prior=p->prior;//插入 p->prior->next=s; s->next=p; p->prior=s; return 1; printf("\n插入位置不合法！" ); return 0; p=p->next; j++;
int InputNumber(DLNode *head) //读入输入的数据
{
int input,i=0;//第i 个节点 char c; scanf("%d%c",&input,&c); while (1) { } if (input=0&&i==0)//输入数为正且是第一个节点 { } else { } i++; if (c==';' ) break ; //遇到数据输入完成标志，跳出循环 scanf("%d%c",&input,&c); if (head->next->data>=0) { } //input=-1*input; ListInsert(head,i,input); ListInsert(head,i,input);//非第一个节点 else head->data=1;//将长整数的符号保存在头结点中 ListInsert(head,i,input);//插入数据 head->data=0;//将长整数的符号保存在头结点中 //input=abs(input);//取输入数字的绝对值 ListInsert(head,i,input);//插入数据
}
return 1;
void OutputNumber(DLNode *head,int sign) //从表尾输出数据元素 {
DLNode *r=head->next;
while (r->data==0&&r!=head->prior)
{
r=r->next;
}
if (sign==1)
{
printf(" 结果是:");
}
else
{
printf(" 结果是: -");
}
printf("%d",r->data);
r=r->next;
while (r!=head)
{
if (r->data
{
printf(",000" );
printf("%d",r->data);
}
else if (r->data
{
printf(",00" );
printf("%d",r->data);
} } } else if (r->datanext; printf(",%d",r->data); printf(",0" ); printf("%d",r->data); printf("\n");
void add(DLNode *head1,DLNode *head2,DLNode *head3){
int z=0;
int e; DLNode *p1,*p2;
p1=head1->prior;
p2=head2->prior; while (p1!=head1&&p2!=head2) { e=p1->data+p2->data+z; if (e>=10000) { } else z=0; ListInsert(head3,0,e); p1=p1->prior;p2=p2->prior; z=1; e=e%10000;
}
if (p1==head1&&p2!=head2)
{
while (p2!=head2) { e=p2->data+z; if (e>=10000) { } else z=0; ListInsert(head3,0,e); p2=p2->prior; z=1; e=e%10000; } if (z==1) ListInsert(head3,0,z);
}
else if (p1!=head1&&p2==head2){
while (p1!=head1) { e=p1->data+z; if (e>=10000) { } z=1; e=e%10000; else z=0; p1=p1->prior; ListInsert(head3,0,e); } if (z==1) ListInsert(head3,0,z);
}
else {
}
int change(DLNode *head1,DLNode *head2)
{
int length1,length2,r=2; length1=ListLength(head1); DLNode *p1,*p2; p1=head1->next; p2=head2->next; if (length1>length2) { } else if (length1data>p2->data) { r=1; return r; r=0; return r; if (z==1) ListInsert(head3,0,z); } length2=ListLength(head2);
} } } } r=0; return r; break ; else if (p2->data>p1->data) { } else { } p1=p1->next; p2=p2->next; r=2; r=1; return r; break ; return r;
void yunsuan(DLNode *head1,DLNode *head2,DLNode *head3,char ch) {
DLNode *p1,*p2; p1=head1->next; p2=head2->next; if (head1->data==1&&head2->data==1) { } else if (head1->data==1&&head2->data==0) { if (ch=='+') add(head1,head2,head3); else (head1,head2,head3);
} if (ch=='+') { } else { } head2->next->data*=-1; add(head1,head2,head3); head2->next->data*=-1; (head1,head2,head3); else if (head1->data==0&&head2->data==1) { } else { if (ch=='+') { head1->next->data*=-1; head2->next->data*=-1; if (ch=='+') { } else { } head1->next->data*=-1; head2->next->data*=-1; add(head1,head2,head3); head3->next->data*=-1; head1->next->data*=-1; (head2,head1,head3);
} } } { } add(head1,head2,head3); head3->next->data*=-1; else head1->next->data*=-1; head2->next->data*=-1; (head2,head1,head3);
void chengfa(DLNode *head1,DLNode *head2) {
}
void main()
{
char ch,ch1; int i; if ((head1->next->data*head2->next->data)next->data=abs(head1->next->data); head2->next->data=abs(head2->next->data); i=1; (head1,head2,i); head1->next->data=abs(head1->next->data); head2->next->data=abs(head2->next->data); i=0; (head1,head2,i);
} while (1) { } //int w=-1; DLNode *a,*b,*c; ListInitiate(&a); ListInitiate(&b); ListInitiate(&c); printf(" 请输入数A(以分号结束):"); InputNumber(a); //printf("\n"); printf(" 请输入数B(以分号结束):"); InputNumber(b); //w=change(a,b); printf(" 请选择操作符：:\n"); scanf("%s",&ch1); if (ch1=='+'||ch1=='-' ) { } else if (ch1=='*') chengfa(a,b); else printf(" 此版本不支持%c运算" ,ch1); printf(" 要继续吗？(y/n) :"); scanf("%s",&ch); if (ch=='Y' ||ch=='y' ) { } else exit(0); printf("\n"); continue ; yunsuan(a,b,c,ch1); OutputNumber(c,1);
设计总结
本次试验是我感觉到了理论应用与实践的意义，以前我们也做过类似的题目，所以在试验中我感觉还是比较顺利的但是还是花了我十七个小时左右才完成。根据模块化思想来把握整体结构会使自己的思路更加清晰，更加明了。得到的东西往往是说不出来的只有自己心理面最清楚。
参考文献
1．严蔚敏，吴伟民. 《数据结构（C 语言版）》. 清华大学出版社.
2．严蔚敏，吴伟民. 《数据结构题集（C 语言版）》. 清华大学出版社.
3．《DATA STRUCTURE WITH C++》. William Ford,William Topp .清华大学出版社（影印版）.
4. 谭浩强. 《c 语言程序设计》. 清华大学出版社.
5． 数据结构与算法分析（Java 版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 张铭, 刘晓丹译 电子工业出版社 2001 年1月
致谢
本次课程设计的成功完成，我首先感谢我的指导老师王连相，他自始至终都给予了我莫大的帮助，正是在王连相老师的悉心指导下我才能顺利完成本次课程设计中的每一个计划。在这次课程设计中，无论从课题选择，方案论证上，还是到具体的设计和调试，每一项安排他都提出了至关重要的建议，使我少走了许多弯路，节省了大量时间，可以说，我的课程设计的顺利完成凝聚着老师的大量心血，在此向王连相老师表示深深的感谢。
当然，我也要感谢我的同学和那些互联网上的朋友，他们毫不吝啬的将自己所掌握的知识拿出来资源共享，才能使我的部分功能模块得以实现，谢谢你们。