1长整数四则运算+数据结构课程设计_数据结构课程设计1

1长整数四则运算+数据结构课程设计由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构课程设计1”。

[实验名称] 长整数四则运算

[需求分析] 设计一个实现任意长的整数进行减法运算的演示程序，要求完成长整数的加减运算，乘除运算可选做。在这里长整数没有范围限制，可任意长。运算后的进位、借位等都要进行正确处理，可实现动态的输入，实时的输出。

测试数据：0、0； 输出“0”

2345，6789、-7654，3211； 输出“1，0000，0000”

1，0000，0000，0000、9999，9999； 输出“9999，0000，0001” 1，0001，0001、；1，0001，0001； 输出“0”

自选数据：1,2345,6789;9,8765,4321； 输出“11,1111,1110”

[概要设计] 数据结构

利用双向循环链表来实现对长整数的存储。每个节点只存储四位十进制数字，即不超过9999的非负整数。双向链表有头指针，它的data值存储长整数的符号，1为正，-1为负，0代表长整数为0；它的over值存储除头节点外节点的个数。其他节点的data值存储四位整数，over存储该四位整数溢出0~~9999范围的情况，一般over>0表示四位数超出9999，over

选择该数据结构来完成长整数的加减运算是因为要对长整数进行运算，需要对长整数进行存储，所以选择用链表对长整数存储，又由于存储的顺序是从左到右，而运算的顺序则是从右到左，这样位了操作方便选择循环链表，在运算过程中有进位和借位的操作，所以最终选择双向循环链表的数据结构。

[详细设计] typedef struct DoubleNode //定义链表元素

void InitNode(DLNode **head)//初始化链表 int InsertNode(DLNode *head,int n,DataType x)//向链表第N个位置插入元素X int digit(int n)//判断整数N有几位

void PrintNode(DLNode *head)//打印链表 void DestroyNode(DLNode **head)//销毁链表 void add(DLNode *h1,DLNode *h2)//两数相加 void jian(DLNode *h1,DLNode *h2)//两数相减 int main()//入口函数

[调试分析] 调试过程中的困难：

在数据的运算中，应为是根据数的大小来选择运算的，所以过程相对比较繁琐。而且对于双向链表的两个指针的定位以及链表的插入和删除等操作花费的较多的时间。在这查阅参照了大量的网络资料。

[测试结果] 1)输入0和0做加法运算，输出“0”，结果如下图：

2)输入2345，6789和-7654，3211做减法运算，输出“1，0000，0000”，结果如下图：

3)输入1，0000，0000，0000和9999，9999做减法运算，输出“9999，0000，0001”，结果如下图：

4)输入1，0001，0001和1，0001，0001做减法运算，输出“0”，结果如下图：

5)输入1,2345,6789 和9,8765,4321做减法运算，结果如下图：

[心得体会] 关于实验本身的收获是掌握了双向链表。而实验外的就是更好的利用了网路资源，通过网络的搜索引擎等。加深了自己在这方面知识的补充。并且在于同学交流中分析了彼此算法的优劣程度。我觉得这是本次实验最大的收获。

[源代码]

#include “iostream.h” #include #include #include #include #define N 100 typedef int DataType;typedef struct DoubleNode //定义链表元素 { DataType data;struct DoubleNode *prior;struct DoubleNode *next;}DLNode;void InitNode(DLNode **head)//初始化链表 { if((*head=(DLNode*)malloc(sizeof(DLNode)))==NULL)exit(1);(*head)->prior=*head;(*head)->next=*head;} int InsertNode(DLNode *head,int n,DataType x)//向链表第N个位置插入元素X { DLNode *p,*nt;int i=0;p=head->next;while(p!=head&&inext;i++;} if(i!=n){ printf(“插入位置错误n”);return 0;} if((nt=(DLNode *)malloc(sizeof(DLNode)))==NULL)exit(1);nt->data=x;nt->prior=p->prior;nt->prior->next=nt;nt->next=p;p->prior=nt;return 1;} int digit(int n)//判断整数N有几位 { int i;for(i=1;;n/=10,i++){ if(n/10==0)return i;} } void PrintNode(DLNode *head)//打印链表 { DLNode *p=head->next;int i;while(p->data==0)//去掉前面的一串0 { p=p->next;if(p==head){ printf(“0n”);return;} } printf(“%d”,p->data);//最前面的一个数进行特殊处理,不用补零 p=p->next;while(p!=head)//打印后面的数字 { printf(“,”);if(p->data==0){ printf(“0000”);p=p->next;continue;} for(i=0;idata);i++)//补零

printf(“0”);printf(“%d”,p->data);p=p->next;} printf(“n”);} void DestroyNode(DLNode **head){ DLNode *p,*p1;p=(*head)->next;while(p!=*head){ p1=p;p=p->next;free(p1);} free(p);head=NULL;} void add(DLNode *h1,DLNode *h2)//两数相加 { DLNode *p1=h1->prior,*p2=h2->prior;while(p1!=h1&&p2!=h2)//每个链表元素相加 { p1->data+=p2->data;p1=p1->prior;p2=p2->prior;} p1=h1->prior;while(p1!=h1->next)//处理链表元素 { if(p1->data>=10000){ p1->prior->data+=p1->data/10000;p1->data%=10000;} if(p1->datanext!=0){ p1->prior->data-=1;p1->data+=10000;} } p1=p1->prior;} if(h1->next->data>=10000)//处理最前面的数 { InsertNode(h1,0,h1->next->data/10000);h1->next->next->data%=10000;} if(h1->datanext->data/10000);h1->next->next->data%=-10000;} PrintNode(h1);} void jian(DLNode *h1,DLNode *h2)//两数相减 { DLNode *p1=h1->prior,*p2=h2->prior;while(p1!=h1&&p2!=h2)//每个链表元素相减 { p1->data-=p2->data;p1=p1->prior;p2=p2->prior;} p1=h1->prior;while(p1!=h1->next)//处理链表元素 { if(p1->data>=10000){ p1->prior->data+=p1->data/10000;p1->data%=10000;} if(p1->datanext!=0){ p1->prior->data-=1;p1->data+=10000;} } p1=p1->prior;} if(h1->next->data>=10000)//处理最前面的数 { InsertNode(h1,0,h1->next->data/10000);h1->next->next->data%=10000;} if(h1->datanext->data/-10000);h1->next->next->data%=-10000;} PrintNode(h1);} int main()//入口函数 { DLNode *head1,*head2;InitNode(&head1);InitNode(&head2);char data1[N],data2[N];char d1[10],d2[10];int i,j,k;int xun;while(1){ printf(“输入数据：n”);scanf(“%s %s”,data1,data2);InitNode(&head1);InitNode(&head2);i=0;k=0;while(data1[i]!=';')//将数1用链表储存 { for(j=0;j

j=-(int)fabs(atoi(d1));else j=atoi(d1);InsertNode(head1,k++,j);} i=0;k=0;while(data2[i]!=';')//将数2用链表储存 { for(j=0;j

d2[j]=0;j=0;while(data2[i]!=';'&&data2[i]!=',')d2[j++]=data2[i++];if(data2[i]==',')i++;if(data2[0]=='-')//处理正负数

j=-(int)fabs(atoi(d2));else j=atoi(d2);InsertNode(head2,k++,j);} printf(“选择加减法：1—加法，2-减法n”);scanf(“%d”,&xun);switch(xun){ case 1:if(strlen(data1)>strlen(data2))//较长的数作为被加数

add(head1,head2);else add(head2,head1);break;case 2:if(strlen(data1)>strlen(data2))//较长的数作为被减数

jian(head1,head2);else jian(head2,head1);break;default:break;} DestroyNode(&head1);DestroyNode(&head2);} return 0;}