project1(2).cpp

民航公司自动订票系统 1、 了解线性表的逻辑结构特性； 2、 熟练掌握链表的特点； 3、 熟练掌握在双重链表中实现查找、插入、删除等的算法； 4、 掌握从时间和空间复杂度的角度综合分析线性表

#include<iostream>
#include<string>

#define DefaultListSize 100

using namespace std;

//doubly-linked list link node with freelist support
template<class Elem> class Link{
	private:
		static Link<Elem>* freelist;
	public:
		Elem element;
		Link *next;
		Link *prev;
		Link (const Elem& e, Link* prevp=NULL, Link*nextp = NULL)
			{	element = e; prev = prevp; next = nextp; }
		Link (Link* prevp=NULL, Link* nextp=NULL)
			{prev = prevp; next = nextp;}
		void*  operator new(size_t);
		void  operator delete(void*);
};

template<class Elem>
Link<Elem>* Link<Elem>::freelist=NULL;

template <class Elem>
void* Link<Elem>::operator new(size_t){
	if(freelist == NULL)	return ::new Link;
	Link<Elem>* temp = freelist;
	freelist = freelist->next;
	return temp;
}

template <class Elem>
void Link<Elem>::operator delete (void * ptr){
	((Link<Elem>*)ptr)->next = freelist;
	freelist = (Link<Elem>*)ptr;
}

//Linked list implementation
template <class Elem> class LList{
	private:
		Link<Elem>* head;
		Link<Elem>* tail;
		Link<Elem>* fence;
		int leftcnt;
		int rightcnt;
		void init(){
			fence =tail =head = new Link<Elem>;
			leftcnt=rightcnt=0;
		}
		
		void removeall(){
			while ( head != NULL){
				fence = head;
				head = head->next;	
				delete fence;
		}
	}
	public:
		LList (int size=DefaultListSize ) { init();}
		~LList() { removeall();}
		void clear() {  removeall();  init(); }
		bool insert( const Elem&);
		bool append( const Elem&);
		bool remove (Elem&);
		void setStart()
		{	fence = head; rightcnt+=leftcnt; leftcnt = 0;}
		void setEnd()
		{	fence = tail; leftcnt += rightcnt; rightcnt =0;}
		void prev();
		void next(){
			if ( fence != tail)
				{	fence = fence->next; rightcnt--; leftcnt++;}
			}
		int leftLength() const { return leftcnt;}
		int rightLength() const { return rightcnt;}
		bool setPos( int pos);
		bool getValue( Elem& it) const{
			if( rightLength() == 0)	return false;
			it = fence->next->element;
			return true;
			}
		void print() const;
};


template<class Elem> void LList<Elem>::prev(){
	if(fence != head)
	{ fence = fence->prev; leftcnt--; rightcnt++;}
}

template <class Elem> bool LList<Elem>::setPos( int pos){
	if ( ( pos < 0) || ( pos> rightcnt+leftcnt) ) return false;
	fence = head;
	for( int i=0; i<pos;i++) fence = fence ->next;
	return true;
}

template<class Elem> bool LList<Elem>::append(const Elem& item){
	tail = tail->next = new Link<Elem>(item,tail,NULL);
	rightcnt++;
	return true;
}


//以下是实现插入
template<class Elem>
bool LList<Elem>::insert(const Elem& item){  //insert the passenger at the right place according to the alphabet order;
	
	fence = head;
	while(fence->next!= NULL && fence->next->element < item)	fence = fence->next;
	
	fence->next = new Link<Elem>(item,fence,fence->next);
	if(fence->next->next != NULL)
		fence->next->next->prev = fence ->next;
	if( tail == fence)
		tail = fence->next;
	rightcnt++;
	return true;
}

//以下是实现删除
template<class Elem> bool LList<Elem>::remove(Elem& it){
	//let the fence->next pointed to  the passenger who want to the flight. 
	
	fence = head;
	while(fence->next!= NULL && fence->next->element < it)	fence = fence->next;	
	
	if(fence->next == NULL || fence->next->element != it )	return false; //can't fine the elem.
	
	Link<Elem>* ltemp = fence->next;
	if( ltemp->next != NULL) ltemp->next->prev = fence;
	else tail = fence;
	
	fence->next = ltemp ->next;
	delete ltemp;
	rightcnt--;
	return true;
}

//以下是实现打印链表
template <class Elem> void LList<Elem>::print() const{
	if(rightcnt+leftcnt){
	Link<Elem>*  temp= head;
	cout<<"****************************************"<<endl;
	cout<<" The Table  Of Passenger:"<<endl;
	cout<<"****************************************"<<endl;
	while( temp->next != NULL){
		cout<<temp->next->element<<endl;
		temp=temp->next;
  }
  cout<<"****************************************"<<endl;
  cout<<endl;
}
else
cout<<"there is no passengers"<<endl;
}


void printindex(){
	cout<<endl;
	cout<<"*************************************************************"<<endl;
	cout<<"*      Welcome to use this Flight  Booking Sytem.           *"<<endl;
	cout<<"*      Please type  '1' to book a tickect.                  *" <<endl;
	cout<<"*      Please type  '2' to cancel the flight ticket.        *" <<endl;
	cout<<"*      Please type  '3' to show the table of passenger.     *" <<endl;
	cout<<"*************************************************************"<<endl;
	
}

int main(void){
	
	LList<string> table;
	while(1){
		printindex();
		char item;
		cin>>item;
		if(item == '1'){
			  cout<<"Please input a name:";
			  string name;
			  cin>>name;
			  if(table.insert(name));
			  	cout<<"You have success to book a flight ticket."<<endl;
		}
		else if(item =='2'){
			  cout<<"Please input the name of the passenger who wanted to cancel the ticket:";
			  string name;
			  cin>>name;
			  if(table.remove(name))
			  		cout<<"You have success to cancel a flight ticket."<<endl;
			  else
			  		cout<<"It faild to find the name."<<endl;
		}	
		else if(item=='3'){
			table.print(); 
		}
		else
			continue;
	}
}