studentlist.cpp

里面包括： 哈夫曼编码

//数据结构第一次实验单链表  054100919 汤杰
#include "iostream.h"
#include "string.h"

class student
{
public:
	int number;
	char *name;
	student *next;
	student(int a,char *b,student *c=0)
	{
		number=a;
		name=new char[strlen(b)+1];
		strcpy(name,b);
		next=c;
	}
	~student()
	{
		delete []name;
	}
};


class stulist
{
private:
	student *head,*tail;
public:
	stulist()
	{
		head=tail=0;
	}
	~stulist();
	int isempty()                       //空时返回1；不空返回0
	{
		return head==0;
		//if (head==0) return(1);
		//else return(0);
	}
	void clear()
	{
		for(student *p;!isempty();)
		{
			p=head->next;
			delete head;
			head=p;
		}
		head=tail=0;
	}

	void addtohead();
	void addtotail();
	void addtotail(int num,char *name);
	void delstu(int);
	bool isinstulist(int);
	void nizhi();
	void listcreat();
	void display();
	void orderlist();
	void addtoorder();
	void deloustu();
	friend void addlist(stulist &p1,stulist &p2);
	void delounum();
	
};
void choose(stulist &claslist,stulist &addlist);


stulist::~stulist()
{
	for(student *p;!isempty();)
	{
		
		p=head->next;
		delete head;
		head=p;
	}
}

void stulist::addtohead()
{
	int num;
	char na[20];
	while(1)
		{
			cout<<"请输入学号： ";
			cin>>num;
		    if(isinstulist(num)) 
				cout<<"学号已经存在"<<endl;
			else break;
		}
	cout<<"请输入姓名:  ";
	cin>>na;
	head=new student(num,na,head);
	if (tail==0) tail=head;
}
void stulist::addtotail()
{
	int num;
	char na[20];
	while(1)
		{
			cout<<"请输入学号： ";
			cin>>num;
		    if(isinstulist(num)) 
				cout<<"学号已经存在"<<endl;
			else break;
		}
	cout<<"请输入姓名:  ";
	cin>>na;
	if(tail!=0) 
	{
		tail->next=new student(num,na);
		tail=tail->next;
	}
	else head=tail=new student(num,na);
}



void stulist::addtotail(int num,char *na)
{
	if(tail!=0) 
	{
		tail->next=new student(num,na);
		tail=tail->next;
	}
	else head=tail=new student(num,na);
}

void stulist::delstu(int a)
{
	if(head!=0)
		if(head==tail&&a==head->number)
		{
			delete head;
			head=tail=0;                  //表中只有一个而且要删的就是这个
		}
		else if(a==head->number)
		{
			student *p=head;        //在第一个的时候
			head=head->next;
			delete p;
		}
		else
		{
			student *pre,*p;
			for(pre=head,p=pre->next;p!=0&&!(p->number==a);pre=pre->next,p=p->next);
			if(p!=0)                      //保证是因p->number==a而停止，即找到那个数
			{
				pre->next=p->next;
				if(p==tail) tail=pre;
				delete p;
			}
			else cout<<"这个学号不存在"<<endl;
		}
}
bool stulist::isinstulist(int a)
{
	student *p;
	for (p=head;p!=0&&!(p->number==a);p=p->next);
	return p!=0;
}


void stulist::nizhi()
{
	student *p,*p1,*p2,*p3;
	p=head;
	if(head)
		if (head==tail)
	{
		cout<<"只有一个元素，无需逆置！"<<endl;
		
	}
	else if (head->next==tail)
	{
		tail=head;
		p1=p;
		p2=p->next;

		p2->next=p1;
		p1->next=0;
		head=p2;
		
	}
	else
	{
		p1=p;
		p2=p1->next;
		p3=p2->next;
		tail=head;
		while(1)
		{
			
			p2->next=p1;
			if(p1==head) p1->next=0;

			if(p3==NULL) break;

			p1=p2;
			p2=p3;
			p3=p3->next;
		}
		head=p2;
	}
	else cout<<"空列表，无法逆置！"<<endl;
}
void stulist::listcreat()
{
	int num;
	char name[20];
	student *p,*p1;

	cout<<"请输入学号(以0结束)： ";
	cin>>num;
	while(num)
	{
		cout<<"请输入姓名:  ";
	    cin>>name;
		p=new student(num,name);
		if(head==0){p1=p;head=tail=p;}
		else 
		{
			p1->next=p;
			tail=p;
			p1=p;
			
		}
		while(1)
		{
			cout<<"请输入学号： ";
			cin>>num;
		    if(isinstulist(num)) 
				cout<<"学号已经存在"<<endl;
			else break;
		}
	
	}
}
void stulist::display()
{
	student *p=head;
	void display();
	while(p)
	{
		cout<<p->number<<"\t"<<p->name<<endl;
		p=p->next;
	}
}

void stulist::orderlist()
{
	int a;
	char *na;
	student *stop=tail;
	student *p,*p1,*p2;
	for(p=head;p!=tail;p=p->next)//仅仅为计次
	{
		p1=head;
		p2=p1->next;
		while(p2!=stop)
		{
			if(p1!=head)
				p2=p2->next;
			
			if(p1->number>p2->number)
			{
				a=p1->number;
				p1->number=p2->number;
				p2->number=a;

				na=p1->name;
				p1->name=p2->name;
				p2->name=na;
			}
			p1=p2;
		}
		stop=p1;
	}
}

void stulist::deloustu()
{
	int f=0;
	student *p=head;
	student *p1;
	while(p)
	{
		if(f==1) 
		{
			p1=p->next;
			delstu(p->number);
			f=0;
			p=p1;
		}
		else
		{
			f=1;
			p=p->next;
		}
	}
}
void stulist::delounum()
{
	int f=0;
	student *p=head;
	student *p1;
	while(p)
	{
		f=p->number;
		if((f%2)==0) 
		{
			p1=p->next;
			delstu(p->number);
			p=p1;
		}
		else
			p=p->next;
	}
}

void stulist::addtoorder()
{
addtotail();
orderlist();
}

void addlist(stulist &p1,stulist &p2)
{
	//p2.clear();
	p2.listcreat();
	cout<<"新链表为"<<endl;
	p2.display();

	student *p;
	p=p2.head;
	while(p)
	{
		if(p1.isinstulist(p->number))
			p=p->next;
		else
		{
			p1.addtotail(p->number,p->name);
			p=p->next;
		}
	}
}






void main()
{
   stulist claslist;
   stulist claslist2;
   claslist.listcreat();
   claslist.display();
   
	int select;
	
	while(1)
	{
	cout<<"输入 1  把单向链表中元素逆置"<<endl;
	cout<<"输入 2  在单向链表中删除所有的偶结点。"<<endl;
	cout<<"输入 3  在单向链表中删除所有的学号为偶数的结点。"<<endl;
	cout<<"输入 4  在头部插入一个学号"<<endl;
	cout<<"输入 5  在尾部插入一个学号"<<endl;
	cout<<"输入 6  按顺序插入一个学号"<<endl;
	cout<<"输入 7  按学号进行排序"<<endl;
	cout<<"输入 8  创建一个新链表并合并到原来的链表中"<<endl;
	cout<<"输入 0  结束"<<endl;
		cin>>select;
	switch(select)
	{
		case 0://结束
		{
			break;
		}
	case 1://元素逆置
		{
			claslist.nizhi();
			break;
		}
	case 2://删除所有的偶数元素结点
		{
			claslist.deloustu();
			break;
		}
	case 3://删除所有的学号为偶数的结点
		{
			claslist.delounum();
			break;
		}
	case 4://头部插入一个学号
		{
			claslist.addtohead();
			break;
		}
	case 5://尾部插入一个学号
		{
			claslist.addtotail();
			break;
		}
	case 6://顺序插入一个学号
		{
			claslist.addtoorder();
			break;
		}
	case 7://学号进行排序
		{
			claslist.orderlist();
			break;
		}
	case 8://创建一个新链表并合并到原来的链表中
		{
			claslist2.clear();//保证claslist2为空，否则只能运行一次
			addlist(claslist,claslist2);
			cout<<"合并后的链表为"<<endl;
			break;
		}
	
	}
	cout<<endl;
	claslist.display();
	cout<<endl;
	if(select==0) break;
	}
   
}