📄 long integer.cpp
字号:
// Long Integer.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
typedef struct DuLNode{
int data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode,* DuLinkList;
//-----------------------------------------------------------------------
//creat.cpp
DuLinkList creat(){
//创建双链表，其每个结点存储长整数的四位（除第一个结点外）
char string[80],*p,*argv;
DuLinkList L,q;
int value;
gets(string);
p=string; //检查第一个，后是否4个一组
while(*p!=','&&*p!='\0') p++;//排除第一个，之后的数无四位的情况
if(*p=='\0') ;
else{
argv=p; //指到第一个，处
while(*p!='\0'){ //以，为界将长整数分段
p++;
if(*p=='\0'||*p==','){
if(p-argv!=5) return NULL;
else argv=p;
}
}
}
p=string;
L=(DuLinkList)malloc(sizeof(DuLNode));//头结点
L->next=L;L->prior=L;
if(*p!='-'&&(*p<48||*p>57)) return NULL; //检查第一个字符 ？？以0开始的情况
if(*p=='-'){
L->data=1; //负数是为1，非负数是为0
p++;
}
else {L->data=0; }
if(*p>57||*p<48) return NULL; //除-后第一个字符应为数字
argv=p;
while(*p!='\0'){ //以，为界将长整数分段
if((*p>57||*p<48)&&*p!=',') return NULL; //限定只能是数字与，
if(*p>=48&&*p<=57) p++;
if(*p==','||*p=='\0') { // *p=','
if(*p==',') {
*p='\0';
p++;
if(*p==','||*p=='\0') return NULL; //排除两符号连着出现
}
value=0; //将字符转化为整数
while(*argv!='\0') {
value=value*10+(*argv-'0');
argv++;}
if(value>=10000) return NULL; //针对第一个结点
q=(DuLinkList)malloc(sizeof(DuLNode));//新建一结点
q->data=value;
q->prior=L->prior; //插入链中
L->prior->next=q;
L->prior=q;
q->next=L;
argv=p; //argv++;
}//end else
}//end while
return(L);
}//end creat
//------------------------------------------------------------------
//-------------------------------------------------------------
//Add.cpp
DuLinkList Add(DuLinkList La,DuLinkList Lb)
{
//将两个链表各位进行相加运算
DuLinkList Lc,q;
DuLinkList p1,p2; //用来遍历两个链表
DuLinkList q1,q2;
int e,n1,n2;
Lc=(DuLinkList)malloc(sizeof(DuLNode));//头结点
Lc->next=Lc;Lc->prior=Lc;
p1=La->prior;
p2=Lb->prior;
//*******************************
// 同号
if(La->data==Lb->data){ ////两个长整数同号
Lc->data=La->data;
while(p1!=La&&p2!=Lb){
e=p1->data+p2->data;
q=(DuLinkList)malloc(sizeof(DuLNode));
q->data=e; //先插入表头后，如果超出再减
q->next=Lc->next;
Lc->next->prior=q;
Lc->next=q;
q->prior=Lc;
p1=p1->prior;p2=p2->prior;
if(e>=10000){ //超出情况
q->data=q->data-10000;
if(p1==La&&p2!=Lb){//讨论是否到表头
p2->data=p2->data+1;}// printf("%d",p2->data); }
else if(p1!=La&&p2==Lb){
p1->data=p1->data+1; }//printf("%d",p1->data);
else if(p1!=La&&p2!=Lb)
p1->data=p1->data+1;
else{
q=(DuLinkList)malloc(sizeof(DuLNode));
q->data=1;
q->next=Lc->next;
Lc->next->prior=q;
Lc->next=q;
q->prior=Lc;
}//end else
}//end if
}//end while
while(p1!=La){ // a链比b链长，要求不破坏原来的链
q=(DuLinkList)malloc(sizeof(DuLNode));
e=p1->data;
q->data=e;
q->next=Lc->next;
Lc->next->prior=q;
Lc->next=q;
q->prior=Lc;
p1=p1->prior;
if(e>=10000){ //超出情况
q->data=q->data-10000;
if(p1==La){
q=(DuLinkList)malloc(sizeof(DuLNode));
q->data=1;
q->next=Lc->next;
Lc->next->prior=q;
Lc->next=q;
q->prior=Lc;
}
else p1->data=p1->data+1;
}
}//end while
while(p2!=Lb){ //b链比a链长
q=(DuLinkList)malloc(sizeof(DuLNode));
e=p2->data;
q->data=e;
q->next=Lc->next;
Lc->next->prior=q;
Lc->next=q;
q->prior=Lc;
p2=p2->prior;
if(e>=10000){//超出情况
q->data=q->data-10000;
if(p2==Lb){
q=(DuLinkList)malloc(sizeof(DuLNode));
q->data=1;
q->next=Lc->next;
Lc->next->prior=q;
Lc->next=q;
q->prior=Lc;
}
else p2->data=p2->data+1;
}
}//end while
}//end if
//********************************
//********************************
// 异号
if(La->data!=Lb->data){ ////异号情况
n1=0;n2=0; //算出a,b链长
while(p1!=La){
p1=p1->prior;
n1++;
}
while(p2!=Lb){
p2=p2->prior;
n2++;
}
p1=p1->prior;
p2=p2->prior;
//printf("%d,%d",n1,n2);
if(n1<n2){ // b链较长
Lc->data=Lb->data;
while(p1!=La){
e=p2->data-p1->data;
q=(DuLinkList)malloc(sizeof(DuLNode));
q->data=e;//先插入再检验
q->next=Lc->next;
Lc->next->prior=q;
Lc->next=q;
q->prior=Lc;
p1=p1->prior;
p2=p2->prior;
if(e<0){ //不够减情况
q->data=q->data+10000;
p2->data=p2->data-1;
}//end if
}//end while
while(p2!=Lb){
if(p2->data==0&&p2->prior==Lb) break;//b只比a多一个结点，被减后b中元素为0
e=p2->data; //否则插入b中剩余结点
q=(DuLinkList)malloc(sizeof(DuLNode));
q->data=e;
q->next=Lc->next;
Lc->next->prior=q;
Lc->next=q;
q->prior=Lc;
p2=p2->prior;
if(e<0){// b中有一位为0且被借了位
q->data=q->data+10000;
p2->data=p2->data-1;
}//end if
}//end while
}//end if
if(n1>n2){ // a 链较长
Lc->data=La->data;
while(p2!=Lb){
e=p1->data-p2->data;
q=(DuLinkList)malloc(sizeof(DuLNode));
q->data=e;//先插入再检验
q->next=Lc->next;
Lc->next->prior=q;
Lc->next=q;
q->prior=Lc;
p1=p1->prior;
p2=p2->prior;
if(e<0){ //不够减情况
q->data=q->data+10000;
p1->data=p1->data-1;
}//end if
}//end while
while(p1!=La){
if(p1->data==0&&p1->prior==La) break;//a只比b多一个结点，被减后a中元素为0
e=p1->data; //否则插入b中剩余结点
q=(DuLinkList)malloc(sizeof(DuLNode));
q->data=e;
q->next=Lc->next;
Lc->next->prior=q;
Lc->next=q;
q->prior=Lc;
p1=p1->prior;
if(e<0){// b中有一位为0且被借了位
q->data=q->data+10000;
p1->data=p1->data-1;
}//end if
}//end while
}//end if
if(n1==n2){ //a,b链结点数相同
q1=La->next;
q2=Lb->next;
while(q1!=La&&q2!=Lb){ //q1 q2分别指到第一个不等的结点
if(q1->data>q2->data){
Lc->data=La->data;
while(p1!=q1->prior&&p2!=q2->prior){ //从最后一个结点一直减到第一个不等的结点
e=p1->data-p2->data;
if(p1==q1&&e==0) break; //第一个不等的结点相减结果为0
q=(DuLinkList)malloc(sizeof(DuLNode));
q->data=e;//先插入再检验
q->next=Lc->next;
Lc->next->prior=q;
Lc->next=q;
q->prior=Lc;
p1=p1->prior;
p2=p2->prior;
if(e<0){ //不够减情况
q->data=q->data+10000;
p1->data=p1->data-1;
}//end if
}//end while
break;
}//end if
if(q1->data==q2->data){
q1=q1->next;
q2=q2->next;
}//end if
if(q2->data>q1->data){
Lc->data=Lb->data;
while(p1!=q1->prior&&p2!=q2->prior){ //从最后一个结点一直减到第一个不等的结点
e=p2->data-p1->data;
if(p2==q2&&e==0) break; //第一个不等的结点相减结果为0
q=(DuLinkList)malloc(sizeof(DuLNode));
q->data=e;//先插入再检验
q->next=Lc->next;
Lc->next->prior=q;
Lc->next=q;
q->prior=Lc;
p1=p1->prior;
p2=p2->prior;
if(e<0){ //不够减情况
q->data=q->data+10000;
p2->data=p2->data-1;
}//end if
}//end while
break;
}//end if
}//end while
if(q1==La&&q2==Lb){//两数相加结果为0
Lc->data=0;
q=(DuLinkList)malloc(sizeof(DuLNode));
q->data=0;
q->next=Lc->next;
Lc->next->prior=q;
Lc->next=q;
q->prior=Lc;
}//end if
}//end if
}//end if
return(Lc);
}//end Add
//----------------------------------------------------------------
//----------------------------------------------------------------
//print.cpp
void print(DuLinkList L){
//将相加结果输出
DuLinkList p;
int e;
// int a[3]; //用数组来输出四个数字
if(L->data==1) printf("-");
p=L->next;
while(p!=L){ //从第一个结点起依次输出
if(p==L->next){ //第一个结点原样输出
printf("%d",p->data);
if(p->next!=L) printf(",");//若不是仅一个元素，输出数字后得加，
else printf("\n");
}
else{
e=p->data;
if(e>=1000) //输出补0
printf("%d",e);
else if(e>=100&&e<1000) { printf("0");printf("%d",e);}
else if(e>=10&&e<100) {printf("00"); printf("%d",e);}
else if(e>=1&&e<10) {printf("000"); printf("%d",e); }
else printf("0000");
if(p->next!=L)//不是最后一个结点时加，
printf(",");
else printf("\n");
}//end else
p=p->next; //p指向下一个结点
}//end while
}//end print
//---------------------------------------------------------------------
//---------------------------------------------------------------------
//free.cpp
void myfree(DuLinkList L){
//释放链表的结点
DuLinkList p;
p=L->next;
while(p!=L){
L->next=p->next;
p->next->prior=L;
free(p);
p=L->next;
}
free(p); //释放头结点
}
//----------------------------------------------------------------------
//----------------------------------------------------------------------
void main()
{
DuLinkList La,Lb,Lc;
DuLinkList creat();
DuLinkList Add(DuLinkList La,DuLinkList Lb);
void print(DuLinkList Lc);
void myfree(DuLinkList L);
//char c;
// while((c=getchar()))
printf("Please input the 1st integer(end by enter):\n");
La=creat();
if(La==NULL){
printf("input error!\n");
return;
}
print(La);
printf("Please input the 2nd integer(end by enter):\n");
Lb=creat();
if(Lb==NULL){
printf("input error!\n");
return;
}
print(Lb);
printf("Now Add the two integers!\n");
Lc=Add(La,Lb);
printf("The result is:\n");
print(Lc);
myfree(La);myfree(Lb);
myfree(Lc);
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -