list1.cpp

一个简单的LINK连表算法

// List1.cpp : Defines the entry point for the console application.
//

#include<iostream.h>
#include<malloc.h>
typedef int elemtype;
typedef struct linknode
{
	elemtype data;
	struct linknode *next;
}nodetype;
class List
{
	nodetype *head;
public:
	List(){
		head=NULL;
	}
	void creatlist();
	void displist();
	int listlen();
	nodetype *findnode(int i);
	void insnode(int i,elemtype x);
	void delnode(int i);
	List::~List();
};
void List::creatlist()
{
	elemtype d;
	nodetype *h=NULL,*s,*t;
	int i=1;
	cout<<"Set up a single list:"<<endl;
	while(1)
	{
		cout<<"Input "<<i<<" node :";
		cin>>d; 
		if(d==0)break;
		if(i==1)
		{
			h=(nodetype *)malloc(sizeof(nodetype));
			h->data=d;
			h->next=NULL;
			t=h;
		}
 		else{
			s=(nodetype *)malloc(sizeof(nodetype));
			s->data=d;
			s->next=NULL;
			t->next=s;
			t=s;
		}
		i++;
		if(i>10)break;
	}
	head=h;
}
void List::delnode(int i)
{
	nodetype *p=head;
	cout<<"Output:"<<endl<<" ";
	if(p==NULL)
		cout<<"NOT EXIST";
	while(p!=NULL)
	{
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<endl;
}
int List::listlen()
{
	int i=0;
	nodetype *p=head;
	while(p!=NULL)
	{
		p=p->next;
		i++;
	}
	return i;
}
nodetype *List::findnode(int i)
{
	nodetype *p=head;
	int j=1;
	if(i>listlen()||i<0)
		return NULL;
	else{
		while(p!=NULL&&j<i)
		{
			j++;
			p=p->next;
		}
		return p;
	}
}
void List::insnode(int i,elemtype x)
{
	nodetype *h=head,*p,*s;
	s=(nodetype *)malloc(sizeof(nodetype));
	s->data=x;
	s->next=NULL;
	if(i==0){
		s->next=h;
		h=s;
	}
	else{
		p=findnode(i);
		if(p!=NULL){
			s->next=p->next;
			p->next=s;
		}
		else
			cout<<"Error!"<<endl;
	}
	head=h;
}
void List::displist()
{
	nodetype *h=head,*p=head,*s;
	int j=1;
	if( j==1)
	{
		h=h->next;
		free(p);
	}
	else{
		p=findnode(j);
		if(p!=NULL&&p->next!=NULL)
		{
			s=p->next;
			p->next=s->next;
			free(s);
		}
		else
			cout<<"Error!"<<endl;
	}
	head=h;
}
List::~List()
{
	nodetype *pa=head,*pb;
	if(pa!=NULL){
		pb=pa->next;
		if(pb==NULL)free(pa);
		else{
			while(pb!=NULL)
			{
				free(pa);
				pa=pb;
				pb=pb->next;
			}
			free(pa);
		}
	}
}
void main()
{
	List L1;
	int i,j,n=0, num;
	nodetype *p;
	L1.creatlist();
	L1.displist();
	cout<<"The length of the list:"<<L1.listlen()<<endl;
	cout<<"Which node do you want to delete:"<<endl;
	cin>>i;

	L1.delnode(i);
	L1.displist();
	cin>>j;
	cin>>num;
	cout<<"Insert the node "<<num<<" below the node "<<j<<endl;
	L1.insnode(j,num);
	cout<<"Find the "<<n<<"node"<<endl;
	p=L1.findnode(n);
	if(p!=NULL)
		cout<<"Find the node!"<<endl;
	else
		cout<<"Can't find!"<<endl;
}