dulinklist.cpp

数据结构实验一中的长整数的加法

//Dulinklist.cpp:functions for Dulinklist

#include "stdafx.h"
#include"stdio.h"
#include "Dulinklist.h"
#include"malloc.h"



void Initlist_Du(Dulinklist &L){
	L.head=(LinkType)malloc(sizeof(NodeType));
	L.head->next=L.head->prior=L.head;
	L.size=0;
}
void Appendlist_Du(Dulinklist &L,LinkType p){
	p->prior=L.head->prior;
	L.head->prior->next=p;
	p->next=L.head;
	L.head->prior=p;
	L.size++;
}


void Createlist_Du(Dulinklist &L){
    char c;
	int data;
	LinkType p;
	Initlist_Du(L);
	c=getchar();
	if(c=='-'){
		L.head->data=1;
		c=getchar();
	}
	else L.head->data=0;

	while(c!='\n'){
		data=0;//这句话要放在这儿，不是在while(c!='\n'){之前
		while(c!=','){
			data=data*10+c-48;
			c=getchar();
			if(c=='\n')break;//错误，c=='\n',不是c='\n',已改正
		}
		p=(LinkType)malloc(sizeof(NodeType));
		p->data=data;
		Appendlist_Du(L,p);
		if(c=='\n') break;//添加这句话，不然当输入'\n'时，不能正常退出
		c=getchar();
	}
}



void Add_a(Dulinklist &L1,Dulinklist &L2,Dulinklist &L3){
	int count=(L1.size<=L2.size)?L1.size:L2.size;
	int i,ca=0;
	LinkType p1,p2,p;
	Initlist_Du(L3);
	p1=L1.head->prior;
	p2=L2.head->prior;
	for(i=0;i<count;i++){
		p=(LinkType)malloc(sizeof(NodeType));
		p->data=p1->data+p2->data+ca;
		if(p->data>9999){
			ca=1;
			p->data=p->data-10000;
		} else ca=0;
		Appendlist_Du(L3,p);//错误，应该前插到双向链表第一个结点（InsertFirstList_Du(L3,p)）,下面有很多同样的错误，
		p1=p1->prior;
		p2=p2->prior;
	}
	if(count==L1.size)while(p2!=L2.head){
		p=(LinkType)malloc(sizeof(NodeType));
		p->data=p2->data+ca;
		if(p->data>9999){
			ca=1;
			p->data=p->data-10000;
		}
		else ca=0; //补充这句话
		p2=p2->prior;
		Appendlist_Du(L3,p);//错误，应该前插
	}
	else while(p1!=L1.head){
		p=(LinkType)malloc(sizeof(NodeType));
		p->data=p1->data+ca;
		if(p->data>9999){
			ca=1;
			p->data=p->data-10000;
		}
		else ca=0; //补充这句话
		p1=p1->prior;
		Appendlist_Du(L3,p);
	}
	
	if(ca==1){
		p=(LinkType)malloc(sizeof(NodeType));
		p->data=ca;
		Appendlist_Du(L3,p);
	}
	L3.head->data=L1.head->data;
}
			


	
void Add_s(Dulinklist &L1,Dulinklist &L2,Dulinklist &L3){
	int i,ca=0,count;
	LinkType p1,p2,p;
	count=(L1.size<=L2.size)?L1.size:L2.size;
	Initlist_Du(L3);//该函数没有考虑相减为零的情况
	if(L1.size==L2.size){
		for(i=0;i<count-1;i++){
			p=(LinkType)malloc(sizeof(NodeType));
			p->data=p2->data-p1->data+ca;
			if(p->data<0){
				ca=-1;
				p->data=p->data+10000;
			}
			else ca=0; //补充这句话
			Appendlist_Du(L3,p);//错误，应该前插
			p1=p1->prior;
			p2=p2->prior;
		}
		p=(LinkType)malloc(sizeof(NodeType));
		p->data=p1->data-p2->data+ca;//为什么p1->data-p2->data，而不是上面的p2->data-p1->data
		if(p->data<0){   //
				p->data=-p->data;
				L3.head->data=L2.head->data;
		}
		else L3.head->data=L1.head->data;
		Appendlist_Du(L3,p);//错误，应该前插
	}
	else if(L1.size>L2.size){
		for(i=0;i<count;i++){
			p=(LinkType)malloc(sizeof(NodeType));
			p->data=p1->data-p2->data+ca;
			if(p->data<0){
				ca=-1;
				p->data=p->data+10000;
			}
			Appendlist_Du(L3,p);
			p1=p1->prior;
			p2=p2->prior;
		}
			p=(LinkType)malloc(sizeof(NodeType));//从这儿
				if(ca==0)p->data=p1->data;//错误，要考虑连续借位，
				else p->data=p1->data-1;//到这儿，都不要
		while(p1!=L1.head){
				p=(LinkType)malloc(sizeof(NodeType));
				p->data=p1->data;//所以要像上面的一样，p->data=p1->data+ca; if(p->data<0) {ca=-1;p->data+=10000;}
				p1=p1->prior;       
				Appendlist_Du(L3,p);  
			}
		L3.head->data=L1.head->data;
	}
	else if(L1.size<L2.size){ //同样错误，同样修改
		for(i=0;i<count;i++){
			p=(LinkType)malloc(sizeof(NodeType));
			p->data=p2->data-p1->data+ca;
			if(p->data<0){
				ca=-1;
				p->data=p->data+10000;
			}
			Appendlist_Du(L3,p);
			p1=p1->prior;
			p2=p2->prior;
		}
			p=(LinkType)malloc(sizeof(NodeType));
				if(ca==0)p->data=p2->data;
				else p->data=p2->data-1;
		while(p2!=L1.head){
				p=(LinkType)malloc(sizeof(NodeType));
				p->data=p2->data;
				p2=p2->prior;
				Appendlist_Du(L3,p);
			}
		L3.head->data=L2.head->data;
	}
	//由于有可能出现前面几个4位数都是0，所以在这儿要删除，代码如下：
	//for(i=L3.size;i>1;i--) { //当L3存放的值全是0时，最多删除L3.size-1个零，因为还要留下一个零，
	//   p=L3.head->next;//指向第一个结点
	//   if(p->data!=0) break;
	//   DeleteFirstList_Du(L3,p); //删除双向链表的第一个结点
	//}       
}
void AddDulinklist(Dulinklist &L1,Dulinklist &L2,Dulinklist &L3){
	if(L1.head->data==L2.head->data)Add_a(L1,L2,L3);
	else Add_s(L1,L2,L3);
}