单链表.cpp

该压缩文件夹内有诸多常用算法和数据结构的c++模板编程实现

#include<iostream.h>
class listNode
{
public:
	int info;
	listNode *next;
	listNode(int a,listNode *p=0)
	{
		info=a;
		next=p;
	}
};
class list
{
private:
	listNode *head,*tail;
public:
	list()
	{
		head=tail=NULL;
	}
	listNode* getHead(){return head;}
	void insert(int,int);					//在第二个参数表示的位置之前插入
	void del(int);
	listNode* findMax();
	void addToTail(int);
	void print();
	void rev(listNode*);
	list* gether(list* b);
	~list()
	{
		listNode *p;
		while(head==tail)
		{
			p=head;
			delete p;
			head=head->next;
		}
		delete head;
	}

};
list* list::gether(list* b)
{
	listNode *p1=b->head,*p2=head;
	int i=1,k=0;
	if(head->info<tail->info)
	{
		for(;p1!=NULL;p1=p1->next)
		{
			k=0;
			for(p2=head,i=1;p2!=NULL;p2=p2->next,i++)
			{
				if(p1->info<p2->info)
				{
					insert(p1->info,i);
					k=1;
					break;
				}
				
			}
			if(k==0)
				addToTail(p1->info);
		}
		return this;
	}
	else
	{
		for(p1=b->head;p1!=NULL;p1=p1->next)
		{
			k=0;
			for(p2=head, i=1;p2!=NULL;p2=p2->next,i++)
			{
				if(p1->info>p2->info)
				{
					insert(p1->info,i);
					k=1;
					break;
				}
				
			}
			if(k==0)
				addToTail(p1->info);
		}
		return this;
	}
}
void list::rev(listNode *p)
{
	if(p->next==NULL)
		cout<<p->info<<" ";
	else
	{
		rev(p->next);
		
		cout<<p->info<<" ";
	}
}
listNode* list::findMax()
{
	listNode* p=head->next,*tmp=head;
	while(p!=NULL)
	{
		if(p->info>tmp->info)
			tmp=p;
		p=p->next;
	}
	return tmp;
}

void list::del(int post)
{
	if(head==tail)
	{
		tail=NULL;
		delete head;
	}
	else if(post==1)
	{
		listNode* p=head;
		head=head->next;
		delete p;
	}
	else
	{
		listNode* p=head;
		for(int i=2;i<post&&p->next->next!=NULL;i++)
			p=p->next;
		listNode* p2=p->next;
		p->next=p->next->next;
		delete p2;
	}
}
void list::insert(int a,int post)
{
	if(post==1)
	{
		listNode *p=new listNode(a);
		p->next=head;
		head=p;
	}
	else
	{		
		listNode *p2=head;
		listNode *p=new listNode(a);
		for(double i=2;i<post&&p2->next!=NULL;i++)
			p2=p2->next;
		p->next=p2->next;
		p2->next=p;
	}
}
			

void list::addToTail(int a)
{
	if(head==NULL)
		head=tail=new listNode(a);
	else
	{
		tail->next=new listNode(a);
		tail=tail->next;
	}
}
void list::print()
{
	listNode* p=head;
	while(p!=0)
	{
		cout<<p->info<<" ";
		p=p->next;
	}
	cout<<endl;
}
void main()
{
	list a,b;
	a.addToTail(1);
	a.addToTail(3);
	a.addToTail(5);
	b.addToTail(2);
	b.addToTail(4);
	b.addToTail(6);
	a.print();
	b.print();
	a.gether(&b);
	
	a.print();
}