11.cpp

数据结构的线性链表的查找

#include <iostream>
typedef int ElemType;

using namespace std;

class LNode
{
public:
	ElemType data;
	LNode  *next;
};

class linklist
{
public:
	LNode *list;
private:
	int size;
public:
	linklist()
	{
		list=NULL;
		size=0;
	}
   int CreateList(ElemType data)
	{
		LNode *node=new LNode();
		node->data=data;
		node->next=NULL;
		if(list==NULL)
		{
			list=node;
		}
		else
		{
			LNode *p;
			p=list;
			while(p->next!=NULL)
			{
				p=p->next;
			}
			p->next=node;			
		}
		size++;
		return size;
	}
   bool ListDelete_data(LNode *List,ElemType &data)
	{
		LNode *p,*q;
		p=list;
		q=list;
		int x=size;
		while((p->next)!=NULL)
		{
			if(p->data!=data)
			{
				q=p;
				p=q->next;
			}
			else
			{
				q->next=p->next;
				free(p);
				size--;
				break;
			}
		}
    	if(x==size)
			return false;
		else
			return true;
	}
   bool ListDelete_dataes(LNode *list,int i,int j)
   {
	   LNode *p,*q;
	   p=list;
	   int x=size;
	   if(i+j>size)
	   {
		   cout<<"输入的长度超过链表的结点数!"<<endl;
	   }
	   else
	   {
		   for(int m=1;m<i;m++)
		   {
			   p=p->next;
			   q=p;
		   }
		   for(int k=0;k<j;k++)
		   {
			   p=q->next;
			   q->next=p->next;
			   free(p);
			   p=q;
			   size--;
		   }
	   }
	   if(x==size)
		   return false;
	   else
		   return true;

   }
   bool listDelete_overturn(LNode *list)
   {
	   LNode *p,*q,*m,*n;
	   p=list;
	   m=p;
	   while(p->next!=NULL)
	   {
		   q=p;
		   p=p->next;
	   }
	   q->next=NULL;
	   n=p;
	   list=p;
	   p->next=m;
	   while(m->next!=NULL)
	   {
		   while(p->next!=NULL)
		   {
			   q=p;
			   p=p->next;
		   }
		   q->next=NULL;
		   n->next=p;
		   n=p;
		   p->next=m;
	   }
	   p=list;
	   cout<<"逆转后链表为:";
	   while(p!=NULL)
	   {		   
		   int x=p->data;
		   cout<<x<<"  ";
		   p=p->next;		   
	   }
      return true;
   }

   bool ordertraverse(LNode *llist)
   {
	   LNode *p;
	   p=llist;
	   while(p!=NULL)
	   {
		   int x=p->data;
		   cout<<x<<"  ";
		   p=p->next;
	   }
	   return true;
   }
  
};

void main()
{
	int n,i,j,z,k=0;
	cout<<"输入结点个数n:";
	cin>>n;
	ElemType x,data;
	linklist *newlist=new linklist();
	cout<<"输入每个结点数据:"<<endl;
	for(int a=0;a<n;a++)
	{
		cin>>x;
		newlist->CreateList(x);
	}
	while(k!=1)
	{
		cout<<"输入1,2,3,4 选择你要的功能:"<<endl;
		cout<<"(1)   逆转该线性链表。"<<endl;
		cout<<"(2)   删除线性链表中从左往右第一个数据为data的链结点。"<<endl;
		cout<<"(3)   删除从第I个链结点开始的连续k个结点。"<<endl;
		cout<<"(4)   退出程序。"<<endl;
		cin>>z;
    	switch(z)
		{
		case 1:
			if(newlist->listDelete_overturn(newlist->list)==true)
			{
				cout<<"成功逆转链表!"<<endl;
			}
			else
			{
				cout<<"删除失败!"<<endl;
			}
			break;
		case 2:
			cout<<"请输入你要删除的结点数据:";
			cin>>data;
			if(newlist->ListDelete_data(newlist->list,data)==true)
			{
				cout<<"删除成功!"<<endl;
				cout<<"删除后的链表数据为:";
				newlist->ordertraverse(newlist->list);
			}
			else
			{
				cout<<"不存在该数据!请确认后重新输入!"<<endl;
			}
			break;
		case 3:
			cout<<"输入你要从第几个结点开始删除:";
			cin>>i;
			cout<<"输入要从该结点删除之后的几个结点元素:";
			cin>>j;
			if(newlist->ListDelete_dataes(newlist->list,i,j)==true)
			{
				cout<<"删除成功!"<<endl;
				cout<<"删除后的链表数据为:";
				newlist->ordertraverse(newlist->list);
			}
			else
			{
				cout<<"删除失败!"<<endl;
			}
			break;
		case 4:
			k=1;
			break;
		default:
			break;
		}
	}
}