adt.h

实现了任意长度整数的加减乘除以及成n次方运算

#include <stdio.h>
#include <stdlib.h>


struct node
{
	long data;
	struct node *llink;
	struct node *rlink;
	
	node()
	{
		data = 0;
		llink = NULL;
		rlink = NULL;

	}
};

struct head
{
	int noofdigit;
	int noofnode;
	bool sign;
	struct node *left;
	struct node *right;

	head()
	{
		noofdigit = 0;
		noofnode = 0;
		sign = true;
		right = NULL;
		left = NULL;
	}
};


void MakeNull(struct head *headnode)
{
	headnode->left = NULL;
	headnode->right = NULL;
}

bool Sign(struct head *headnode)
{
	return headnode->sign;
}

int Digits(struct head *headnode)
{
	return headnode->noofdigit;
}

void Assign(struct head *headnode, bool value)
{
	headnode->sign = value;
}

void Assign(struct head *headnode, int value)
{
	headnode->noofdigit = value;
}

bool Empty(struct head *headnode)
{
	if (headnode->left != NULL)
	{
		return false;
	}
	else return true;
}	


struct node *FirstRight(struct head *headnode)
{
	return headnode->right;
}

struct node *FirstLeft(struct head *headnode)
{
	return headnode->left;
}

struct node *NextLeft(struct node *nodetosearch)
{
	return nodetosearch->llink;
}

struct node *NextRight(struct node *nodetosearch)
{
	return nodetosearch->rlink;
}

void InsertLeft(struct head *headnode, struct node *nodetoinsert)
{
	if(headnode->left == NULL)
	{
		headnode->left = nodetoinsert;
		headnode->right = nodetoinsert;
		
	}

	else
	{
		struct node *pointer;
		pointer = headnode->left;
		
		while(pointer->llink != NULL)
		{	
			pointer=pointer->llink;
		}
		
		pointer->llink = nodetoinsert;
		nodetoinsert->rlink =pointer;
		headnode->right = nodetoinsert;
	}
}	

void InsertRight(struct head *headnode, struct node *nodetoinsert)
{
	if(headnode->right == NULL)
	{
		headnode->right = nodetoinsert;
		headnode->left = nodetoinsert;
		
		
	}

	else
	{
		struct node *pointer;
		pointer = headnode->right;
		
		while(pointer->rlink  != NULL)
		{	
			pointer=pointer->rlink;

		}
		pointer->rlink = nodetoinsert;
		nodetoinsert->llink =pointer;
		headnode->left = nodetoinsert;
		
	}
}
int Over_flow(long num)
{
	long int ovrflwdgt = 0;
	ovrflwdgt = num/100000000;
	if(ovrflwdgt != 0)
	{
		num = num - ovrflwdgt*100000000;
	}
	return ovrflwdgt;
}
int Over_flow4(long num)
{
	long int ovrflwdgt = 0;
	ovrflwdgt = num/10000;
	if(ovrflwdgt != 0)
	{

		num = num - ovrflwdgt*10000;

	}
	return ovrflwdgt;
}

long lpow(int x, int y)
{
	long result = 1;
	for(int i=0; i < y; i++)
	{
		result = result*x; 
	}
	return result;
}

int Digit(long num)
{
	int i;
	for(i=0; (num/lpow(10,7-i)) <= 0; i++)
	{
		if (i==7) break;
	}
	return 8-i; 
}



void SetNoofDigits(struct head *headnode)
{
	int i;
	struct node *nodepointer1;
	struct node *nodepointer2;
	nodepointer1 = headnode->left;
	if(nodepointer1 == NULL)
	{
		headnode->noofdigit = 0;
	}

	for (i=0; nodepointer1 != NULL; i++)
	{
		nodepointer2 = nodepointer1;
		nodepointer1 = nodepointer1->llink;
		
	}
	headnode->noofdigit = (i-1)*8+Digit(nodepointer2->data);
}

void SetNoofNode(struct head *headnode)
{
	struct node *nodepointer;
	int i;

	nodepointer = headnode->left;
	for(i=0; nodepointer!=NULL ;i++)
	{
		nodepointer = nodepointer->llink;
	}
	headnode->noofnode = i;
	
}


void ClearZ(struct head *headnode)
{
	struct node *nodepointer;
	nodepointer = headnode->right;
	while(nodepointer->data == 0 && nodepointer->rlink != NULL)
	{
		nodepointer = nodepointer->rlink;
		nodepointer->llink = NULL;
		headnode->right = nodepointer;
	}
}

void CreatandStore(struct head *headnode, long num)
{
	struct node *nodepointer = new struct node;
	nodepointer->data = num;
	headnode->left = nodepointer;
	headnode->right = nodepointer;
	SetNoofDigits(headnode);
	SetNoofNode(headnode);
}

void CreatandStore(struct head *headnode, string str)
{

	// Input the sign of head
	string substring;
	struct node *nodepointer;
	MakeNull(headnode);
	if(str.at(0) == '-')
	{
		Assign(headnode, false);
		str.erase(0,1);
	}
	else if(str.at(0) == '+')
	{
		Assign(headnode, true);
		str.erase(0,1);
	}
	else
	{
		Assign(headnode, true);
	}

	// Put data into nodes and insert the nodes into the list 
	int i = str.length();

	for( ;i>8 ;i=i-8)
	{
		substring = str.substr(i-8,8);
		const char *a = substring.c_str();
		nodepointer = new struct node;
		nodepointer->data = strtol(a, NULL, 10);
		InsertLeft(headnode,nodepointer);
	}

	substring = str.substr(0,i);
	const char *a = substring.c_str();
	nodepointer = new struct node;
	nodepointer->data = strtol(a, NULL, 10);
	InsertLeft(headnode,nodepointer);
	ClearZ(headnode);

	// Input the number of digits
	SetNoofDigits(headnode);
	SetNoofNode(headnode);

}

void OutPutData(struct head *headnode)
{
	string result = "";
	struct node *nodepointer;

	if(headnode->left == NULL)
	{
		cout<<"0"<<endl;
	}
	else
	{
		nodepointer = headnode->left;
		int dig;
		int i;
		char a[9] = "";
		string buffer = "";

		while( nodepointer->llink != NULL)
		{
			ltoa(nodepointer->data, a, 10);
			buffer.assign(a);
			dig = Digit(nodepointer->data);
			for( ; dig<8; dig++)
			{
				buffer.insert(0,"0");
			}
			result.insert(0,buffer);

			
			nodepointer = nodepointer->llink;
		}
		
		ltoa(nodepointer->data, a, 10);
		buffer.assign(a);
		result.insert(0,buffer);
		

		if(headnode->sign == false)
		{
			result.insert(0,"-");
		}

		cout<<result<<endl;		
	}
}



void BasicAdd(struct head *oprnd1, struct head *oprnd2, struct head *result)
{
	struct node *n1, *n2, *rslt;
	long sum, ovrflwdgt = 0;

	n1 = FirstLeft(oprnd1);
	n2 = FirstLeft(oprnd2);
	MakeNull(result);

	while(n1 != NULL && n2 != NULL)
	{
		sum = n1->data+n2->data+ovrflwdgt;
		ovrflwdgt = Over_flow(sum);
		sum = sum - ovrflwdgt * 100000000;
		rslt = new struct node;
		rslt->data = sum;
		InsertLeft(result, rslt);
		n1 = NextLeft(n1);
		n2 = NextLeft(n2);
	}

	while(n1 != NULL)
	{
		sum = n1->data+ovrflwdgt;
		rslt = new struct node;
		ovrflwdgt = Over_flow(sum);
		sum = sum - ovrflwdgt * 100000000;
		rslt->data = sum;
		InsertLeft(result, rslt);			
		n1 = NextLeft(n1);
	}

	while(n2 != NULL)
	{
		sum = n2->data+ovrflwdgt;
		rslt = new struct node;
		ovrflwdgt = Over_flow(sum);
		sum = sum - ovrflwdgt * 100000000;
		rslt->data = sum;
		InsertLeft(result, rslt);
		n2 = NextLeft(n2);
	}

	if(ovrflwdgt>0)
	{
		rslt = new struct node;
		rslt->data = ovrflwdgt;
		InsertLeft(result, rslt);
	}

}

head *BasicAdd(struct head *oprnd1, struct head *oprnd2)
{
	struct head *headnode = new struct head;
	BasicAdd(oprnd1, oprnd2, headnode);
	SetNoofNode(headnode);
	SetNoofDigits(headnode);
	return headnode;
}