单链表.cpp

用 C++做的一个单链表

#include<iostream.h>
class listnode//结点描述
{
public:
	int data;
	listnode *next;
	listnode(const int &itemval,listnode *ptrnext=NULL)//构造函数
	{
		data=itemval;
		next=ptrnext;
	}
	listnode(listnode *ptrnext=NULL)//构造函数重载
	{
		next=ptrnext;
	}
};
class linklist//建立链表类
{
public:
	listnode *head;//存放头结点
	listnode *tail;//存放尾结点
	listnode *currptr;//存放当前结点
public:
	linklist(void);//构造函数:ok
	void locate(int &itemval);//按值查找,将指针指向该结点:ok
	void findorder(int i);//按序号查找,将指针指向该结点:ok
	listnode* findprior(void);//找当前结点的直接前驱:ok
	void inserttail(int &itemval);//尾插入:ok
	void inserthead(int &itemval);//头插入:ok
	void insertafter(int &itemval);//在当前指针后插入:ok
	void insertbefore(int &itemval);//在当前指针前插入:ok
	int Delete(void);//删除当前结点,currptr指向NULL:ok
	int listsize(void);//求链表结点个数:ok
	void clearlist(void);//清空链表:ok
	int isempty(void);//判空:ok
	void print(void);//:ok
};
linklist::linklist()
{
	head=tail=currptr=NULL;
}
void linklist::locate(int &itemval)
{
	listnode *p;
	p=head;
	while(p!=NULL&&p->data!=itemval)
	{
		p=p->next;
	}
	if(p==NULL)
		cout<<"不存在此结点"<<endl;
	else
	{
		cout<<"ok"<<endl;
		currptr=p;
	}
}
void linklist::findorder(int i)
{
	listnode *p;
	p=head;
	int j;
	for(j=0;j<i-1;j++)
	{
		if(p==NULL)
		{
			cout<<"不存在此结点"<<endl;
			break;
		}
		p=p->next;
	}
	currptr=p;
}
listnode* linklist::findprior(void)
{
	listnode *p;
	p=head;
	if(currptr==NULL)
	{
		cout<<"当前结点为空"<<endl;
		return 0;
	}
	if(p==currptr)
	{
		cout<<"当前结点为头结点"<<endl;
		return p;
	}
	while(p->next!=currptr)
		p=p->next;
	return p;
}
void linklist::inserttail(int &itemval)
{
	listnode *p;
	p=new listnode(itemval,NULL);
	if(head==NULL)
	{
		head=p;
	}
	else
		tail->next=p;
	currptr=tail=p;
}
void linklist::inserthead(int &itemval)
{
	listnode *p;
	p=new listnode(itemval,NULL);
	if(head==NULL)
		tail=p;
	else
		p->next=head;
	head=currptr=p;
}
void linklist::insertafter(int &itemval)
{
	listnode *p;
	p=new listnode(itemval,NULL);
	if(currptr==NULL)
		inserthead(itemval);
	else
		if(currptr==tail)
		{
			tail=p;
			currptr->next=p;
		}
		else
		{
			p->next=currptr->next;
			currptr->next=p;
			currptr=p;
		}
}
void linklist::insertbefore(int &itemval)
{
	listnode *p;
	p=new listnode(itemval,NULL);
	if(currptr==NULL)
		inserthead(itemval);
	else
	{
		if(currptr==head)
		{
			p->next=head;
			head=p;
		}
		else
		{
			listnode *q;
			q=head;
			while(q->next!=currptr)
				q=q->next;
			q->next=p;
			p->next=currptr;
		}
		currptr=p;
	}
}
int linklist::Delete(void)
{
	listnode *p;
	if(currptr==NULL)
		return 0;
	if(currptr==head&&currptr==tail)
		currptr=head=tail=NULL;
	else
		if(currptr==head)
			head=head->next;
		else
		{
			p=head;
			while(p->next!=currptr)
				p=p->next;
			if(currptr==tail)
			{
				tail=p;
				p->next=NULL;
			}
			else
				p->next=currptr->next;
		}
		delete currptr;
		currptr=NULL;
		return 1;
}
int linklist::listsize(void)
{
	int n=0;
	listnode *p;
	p=head;
	while(p!=NULL)
	{
		p=p->next;
		n++;
	}
	return n;
}
void linklist::clearlist(void)
{
	while(head!=NULL)
	{
		currptr=head;
		head=head->next;
		delete currptr;
	}
	head=tail=currptr=NULL;
}	
int linklist::isempty(void)
{
	if(head==tail)
		return 1;
	else return 0;
}
void linklist::print(void)
{
	currptr=head;
	while(currptr!=NULL)
	{
		cout<<currptr->data<<" ";
		currptr=currptr->next;
	}
}
void main()//测试
{
	linklist a;
	int i,j,k;
	cin>>i>>j>>k;
	a.inserthead(i);
	a.inserthead(j);
	a.inserttail(k);
	a.insertbefore(i);
	a.print();
	cout<<endl;
	a.locate(k);
	a.findorder(1);
	cout<<a.findprior()<<endl;
	cout<<a.listsize();
	cout<<endl;
	a.Delete();
	a.print();
	cout<<endl;
	cout<<a.head<<endl;
	a.clearlist();
	cout<<a.isempty();
}