数据结构设计1线性表长整数加法.cpp

数据结构课程设计：使用线性结构实现长整数的加法运算

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define OVER -1
typedef int ElemType;
typedef int Status;

typedef struct DuLNode{
	ElemType data;
	struct DuLNode *prior;
	struct DuLNode *next;
}DuLNode , *DuLinkList;
           //***************建表***********
Status InitList(DuLinkList &L)
{
	L=(DuLinkList )malloc(sizeof(DuLNode));
	if(!L)  return ERROR;
	L->prior=L;
	L->next=L;
    return OK;
}
          //***************插入****************
Status InsertList(DuLinkList &L,int e)
{
	DuLNode *p,*q;
	p=L;
	while(p->next!=L)
		p=p->next;                           //把指针p指向链表的最后一个结点
	if(!(q=(DuLinkList )malloc(sizeof (DuLNode))))
	     	return ERROR;
	q->data=e;                               //在表尾插入  
    p->next=q;  q->prior=p;                 
	q->next=L;  L->prior=q;
	return OK;
}

         //****************求链表长度*************
int lengthList(DuLinkList &L)
{   
	int count=0;
	DuLNode *p;
	p=L;
	while(p->next!=L)
	{
		p=p->next;
		count++;
	}
	return count;
}
       //************删除结点*********
Status DeleteList(DuLinkList &L)
{

	DuLNode *p;
	p=L->next;
	p->next->prior=p->prior;
	L->next=p->next;
	free(p);
	return OK;
}
         //*****************求绝对值*****************
int  fabs(int x)
{
	if(x<0)
		x=-x;
	return x;
}

            //************ 交换链表**************
void TempList(DuLinkList &L1,DuLinkList &L2)
{
	DuLinkList temp;
	temp=L1;
	L1=L2;
	L2=temp;
}

        //******************求加法******************
Status AddList(DuLinkList &L1,DuLinkList &L2,DuLinkList &L3)
{
    int jinwei=0;    //进位 
	int jiewei=0;    //借位
	DuLNode *s,*t,*w;
	s=L1;
	t=L2;
	if(lengthList(L1)<lengthList(L2))
		TempList(L1,L2);

	if(lengthList(L1)>lengthList(L2)){         //********如果L1的长度比L2长*************
		s=L1->prior;
		t=L2->prior;              //把t指向L2的最后一个结点,此时s也指向L1的最后结点 
		w=t;           //标记
		
		if(L1->data==L2->data){    //**********L1与L2是同号情况*************8
			L3->data=L1->data;
	        while(t->prior!=w)                          
			{ 
				if((s->data+t->data)>=10000){   //进位
			     	jinwei=1;
                    s->prior->data=(s->prior->data)+jinwei;
	    		    InsertList(L3,(s->data)+(t->data)-10000);
				}
		    	else InsertList(L3,(s->data)+(t->data));
    			s=s->prior;
	    		t=t->prior;
				if(s->data>=10000){
					s->data=s->data-10000;
					if(s->prior!=L1)//{
				    	s->prior->data=s->prior->data+1;
				}     
			}  //while                                   
			     // 循环结束时t指向L2
                 // 此时s指向和t等长的结点 	
    		while(s->prior!=L1){
				InsertList(L3,s->data);
    			s=s->prior;
			} //while
			if(s->data>=10000){
				InsertList(L3,s->data-10000); 
				InsertList(L3,1);
			}
			else InsertList(L3,s->data);
		}//if    //L1 L2为同号

		if(L1->data!=L2->data){  //**********L1 L2异号*****************
			L3->data=L1->data;
			while(t->prior!=w)
			{
    			if((s->data-t->data)<0){   //借位
    				jiewei=1;
    				s->prior->data=(s->prior->data)-jiewei;
	    		    InsertList(L3,(s->data)-(t->data)+10000);
				}
    			else InsertList(L3,(s->data)-(t->data));
    			s=s->prior;
    		    t=t->prior;
				if(s->data<0){
					s->prior->data=s->prior->data-1;
					s->data=s->data+10000;
				}
			}
				while(s->prior!=L1){
    				InsertList(L3,s->data);
    				s=s->prior;
				}
				if(s->data!=0)
    			InsertList(L3,s->data);		
			
		}  
	}//if     //************  以上L1与L2的结点数目不相等  ***********************
      
	if(lengthList(L1)==lengthList(L2)){     //************  L1与L2的结点数目相等**********
		s=L1->prior;
		t=L2->prior;              //把t指向L2的最后一个结点,此时s也指向L1的最后结点 
	
		if(L1->data==L2->data){   //L1与L2都是正号或者都是负号情况
			L3->data=L1->data;
	        while(t->prior!=L2)                          
			{ 
				if((s->data+t->data)>=10000){   //进位
			     	jinwei=1;
                    s->prior->data=(s->prior->data)+jinwei;
	    		    InsertList(L3,(s->data)+(t->data)-10000);
				}
		    	else InsertList(L3,(s->data)+(t->data));
    			s=s->prior;
	    		t=t->prior;            
			}  //while                              
			if((s->data+t->data)>=10000){
				InsertList(L3,s->data+t->data-10000);
                InsertList(L3,1);
			}else InsertList(L3,s->data+t->data);		
		} //if   //L1 L2同号
   	
		if((L1->data==0)&&(L2->data==1))
			TempList(L1,L2);
		if((L1->data==1)&&(L2->data==0)){
			s=L1->prior;t=L2->prior;
			if(L1->next->data < L2->next->data){
				L3->data=0;
				while(t->prior!=L2)                          
				{ 
					if((t->data - s->data)<0){   //借位
						jiewei=1;
                        t->prior->data=(t->prior->data)-jiewei;
            		    InsertList(L3,(t->data)-(s->data)+10000);
					}
	        		else InsertList(L3,(t->data)-(s->data));
        			s=s->prior;
            		t=t->prior;    
				}  //while
        		if((t->data - s->data)!=0)
         			InsertList(L3,t->data - s->data);
				else return OK;
			}
            
			if(L1->next->data > L2->next->data){
				L3->data=1;
				while(t->prior!=L2)
				{
					if((s->data - t->data)<0){   //借位
						jiewei=1;
                        s->prior->data=(s->prior->data)-jiewei;
            		    InsertList(L3,(s->data)-(t->data)+10000);
					}
	        		else InsertList(L3,(s->data)-(t->data));
        			s=s->prior;
            		t=t->prior;    
				}  //while
				if((t->data - s->data)!=0)
         			InsertList(L3,t->data - s->data);	
			}

			if(L1->next->data == L2->next->data){
				while(L1->next->data == L2->next->data){
					DeleteList(L1);
					DeleteList(L2);
				}
				if(L1->next==L1){
					InsertList(L3,0);
					return OK;
				}
				s=L1->prior;
				t=L2->prior;
			
				if(L1->next->data > L2->next->data){
					L3->data=1;
			    	while(t->prior!=L2)
					{
     					if((s->data - t->data)<0){   //借位
	    					jiewei=1;
                            s->prior->data=(s->prior->data)-jiewei;
                		    InsertList(L3,(s->data)-(t->data)+10000);
						}
    	        		else InsertList(L3,(s->data)-(t->data));
               			s=s->prior;
                		t=t->prior;    
					}  //while
    				if((s->data - t->data)!=0)
            			InsertList(L3,s->data - t->data);	
				}

				if(L1->next->data < L2->next->data){
    				L3->data=0;
    				while(t->prior!=L2)                          
					{ 
	     				if((t->data - s->data)<0){   //借位
	    					jiewei=1;
                            t->prior->data=(t->prior->data)-jiewei;
                		    InsertList(L3,(t->data)-(s->data)+10000);
						}
    	         		else InsertList(L3,(t->data)-(s->data));
            			s=s->prior;
                		t=t->prior;    
					}  //while
            		if((t->data - s->data)!=0)
            			InsertList(L3,t->data - s->data);
	    			else return OK;
				}
			}	
		}
	}
  return OK;          
}

Status PrintList(DuLinkList L)   //*********打印链表*************
{
	DuLNode *p;
	p=L;
	if(!L)  exit(OVER);
	printf("存入结点的情况:   ");
	if(L->data==0)  printf("-");
	if(L->data==1)  printf(" ");
	while(p->next!=L)
	{
		p=p->next;
		printf("%04d,",p->data);	
	}
	printf("\n\n");
	return OK;
}

void printfList(DuLinkList &L)    //*********打印结果********
{
	printf("计算的结果是：   ");
	
	if(L->data==0)  printf("-");
	if(L->data==1)  printf(" ");
	printf("%d",L->prior->data);
	DuLNode *q;
	q=L->prior->prior;
	while(q!=L){
		printf(",%04d",q->data);
		q=q->prior;
	}
	printf("\n\n");
}
  
//*****************主函数**********************
void main()
{
	DuLinkList List1,List2,List3;
	InitList(List1);
	InitList(List2);
	List1->data=1;
	List2->data=1;
    InitList(List3);

	int s=0;
	char c=',';
	char a=',';
	printf("输入规则: 数与数之间用逗号隔开,结束用; ****,****,****;\n\n");
    printf("请输入第一个长整数:         ");
    while(c!=';')
	{
	    if(c==',')
		{
			scanf("%d%c",&s,&c);
		    if(s<0){
			          List1->data=0;
			          s=fabs(s);				  
			}
		InsertList(List1,s);
		}
		else{
			    printf("    ERROR,请重新输入\n");
				break;
		}	
	}
	printf("请输入第二个长整数:         ");
    while(a!=';')
	{
	    if(a==',')
		{
			scanf("%d%c",&s,&a);
		    if(s<0){
			          List2->data=0;
			          s=fabs(s);			  
			}//if
		InsertList(List2,s);
		}//if
		else{
			    printf("    ERROR,请重新输入\n");
				break;
		}	
	}
	PrintList(List1);
	PrintList(List2);
    AddList(List1,List2,List3);
	printfList(List3);
}