list.h

数据结构的一些简单算法

//===========================================================================
//Project Descriprion
//===========================================================================
//Project name :  Multinomial Operation
//Author       :  Aries
//Description  :  rt
//Creat Date   :  2005/3/12
//Version      :  Ver#1.0 by Aries at 2005/3/12 0:30
//===========================================================================

//===========================================================================
//Thinking before coding...  
//===========================================================================
//Multinomial ax(n) + bx(n-1) + ... 
//Input  compositor hoho~
//Add..  add one list node by node to another
//Sub..  just like add ...
//Mul..  1 mul nodes of the list with list --> n lists
//       2 n list add 
//===========================================================================

//===========================================================================
//                               list.h
//===========================================================================
#ifndef _LIST_H_
#define _LIST_H_

#include "error_code.h"
#include <iostream.h>
#define NULL 0
//Data Stucture follows : 
struct moNode 
{
	//Data members
	float flCoef ;  //Coefficient --- float
	int   iExp   ;  //Exponent    --- int
	//constructors
	//moNode();
	moNode(float coef = 0,int exp = 999999)
	{
		flCoef = coef ;
		iExp = exp ;
	}
	bool operator >= (int Exp)
	{
		return ( this->iExp >= Exp );
	}
	bool operator == (int Exp)
	{
		return (this->iExp == Exp );
	}
	moNode operator + (moNode entry)
	{
		this->flCoef += entry.flCoef;
		return *this ;
	}
	moNode operator = (moNode entry)
	{
		this->flCoef = entry.flCoef;
		this->iExp   = entry.iExp  ;
		return *this;
	}
	bool operator - (float Coef)
	{
		return (this->flCoef == Coef);
	}
	moNode operator * (moNode entry)
	{
		moNode temp ;
		temp.flCoef = this->flCoef * entry.flCoef ;
		temp.iExp   = this->iExp   + entry.iExp   ;
		return temp ;
	}
	friend ostream& operator << (ostream& out, moNode entry)
	{
		out << entry.flCoef << 'X' << entry.iExp << ' ' ;
		return out;
	}
};
template <class Node_entry> struct Node
{
	//Data members
	Node_entry         entry ; //Node entry
	Node<Node_entry>*  next  ; //Node to next
	//constructors
	Node();
	Node(Node_entry tmpEntry,Node<Node_entry>* link = NULL)
	{
		entry = tmpEntry ;
		next  = link ;
	}
};


template <class list_entry> class list
{
public:
	list(list<list_entry> &copy) ;
	list(moNode &xNode);
	int size() const { return count; } ;
	bool ser_position (moNode xNode,int &position);
	//void operator = (const list<list_entry> &copy);

	int   count;
	Node<list_entry>*  head;
	Node<list_entry>*  set_position  (int position)const;
	
	Error_Code         add           (int position,list_entry  &xNode);
	Error_Code         add           (list<list_entry> &copyDesk,list<list_entry> &copySource);
	Error_Code         mul           (list<list_entry> &copyDesk,list<list_entry> &copySource);
	Error_Code         insert        (int position,const list_entry  &xNode);
	Error_Code         output        ();
	//Error_Code       remove        (int position,list_entry &xNode);
	//Error_Code	   replace       (int position,const list_entry &xNode);
	
};

template <class list_entry> 
list<list_entry>::list(list<list_entry> &copy)
//constructor
{
	head  = copy.head  ;
	count = copy.size();
};

template <class list_entry> 
list<list_entry>::list(moNode &xNode)
//constructor
{
	Node<list_entry>* new_node;
	new_node = new Node<list_entry>(xNode,NULL);
	head = new_node ;
	count = 1 ;
};

template <class list_entry>
Node<list_entry>* list<list_entry>::set_position(int position)const
//return a point to the Node in position
//if position == 0 return head ;
//if position == 1 return NULL or head->next ;
{
	Node<list_entry>* p = head ;
	for( int i = 0 ; i < position ; i++ ) 
		p = p->next;
	return p ;
};

template <class list_entry>
bool list<list_entry>::ser_position(moNode xNode,int &position)
//to search a position for new node for add or insert
{
	
	Node<list_entry>* p = head;
	int num = 0;
	while( p->entry >= xNode.iExp )
	{		
		if( p->entry == xNode.iExp )
		{
			position = num;
			return true;
		}
		p = p->next;
		if( p == NULL )
		{
			position = count;
			return false;
		}
		num++;
	}
	position = num;
	return false;
};

template <class list_entry>
Error_Code list<list_entry>::add(int position,list_entry &xNode)
//add one node to a node part of the list
{
	if(position <= 0 || position > count )
		return Position_Range_Error;
	Node<list_entry>* temp=NULL  ;
	Node<list_entry>* prev=NULL  ;
	temp = set_position(position);
	if(temp == NULL)
		return Position_Con_Error;
	prev = set_position(position - 1) ;
	xNode = temp->entry + (xNode);
	if( temp -> entry - 0 ) //overload "-" to "==" flCoef
	{
		prev->next = temp->next ;
		delete temp ;
		count--;            //the number of the list --
	}
	return Add_Success;	
};

template <class list_entry>
Error_Code list<list_entry>::add(list<list_entry> &copyDesk,list<list_entry> &copySource)
//add one list to another
{
	Node<list_entry>* tmpAdd = copySource.head->next ;
	while( tmpAdd != NULL )
	{
		int position; 
		bool SamExp  ;
		SamExp = copyDesk.ser_position(tmpAdd->entry,position);
		if(SamExp)
		{
			cout<< copyDesk.add(position,tmpAdd->entry) <<endl ;
		}
		else
		{
			cout<< copyDesk.insert(position,tmpAdd->entry) << endl ;
		}
		tmpAdd = tmpAdd->next ;
	}
	return Add_List_Success ;
};

template <class list_entry>
Error_Code list<list_entry>::mul(list<list_entry> &copyDesk,list<list_entry> &copySource)
{
	moNode* new_Node = new moNode ;
	list<list_entry>  BassList(*new_Node) ;
	Node<list_entry>* Desk   = copyDesk.head->next   ; 
	Node<list_entry>* Source = copySource.head->next ;
	moNode            tmpNode;
	for( int i = 1 ; i < copySource.count ; i++ )
	{
		new_Node = new moNode;
		list<list_entry>  AddList (*new_Node) ;
		for( int j = 1 ; j < copyDesk.count ; j ++ )
		{
			tmpNode = Desk->entry * Source->entry ;
			cout << AddList.add(AddList.count-1,tmpNode)   ;
			Desk = Desk -> next;
		}
		cout << BassList.add(BassList,AddList);
		Source = Source -> next ;
	}
	cout << BassList.output() << endl ;
	return Mul_Success ;
};

template <class list_entry>
Error_Code list<list_entry>::insert(int position,const list_entry &xNode)
//insert a node to the position
{
	if( position <= 0 || position > count )
		return Position_Range_Erro    ;
	Node<list_entry>* prev     ;
	Node<list_entry>* new_node ;
	Node<list_entry>* follow   ;
	prev   = set_position(position - 1);
	follow = prev->next   ;
	new_node = new Node<list_entry>(xNode,follow);
	if( new_node == NULL )
		return Overflow   ;
	prev->next = new_node ;
	count++;
	return Insert_Success ;
};
template <class list_entry>
Error_Code list<list_entry>::output()
{
	if( head->next == NULL )
		return List_Null_Error;
	Node<list_entry>* temp = head->next;
	while( temp != NULL )
	{	
		cout << temp->entry ;
		temp = temp->next ;
	}
	cout<< endl;
	return Output_Success ;
};

#endif _LIST_H_