单链表[查找插入和删除].cpp

这个是我的大学作业哦 里面有些很经典的代码 出自清华大学的数据结构课本

#include<iostream>
using namespace std;
//####################
class List;

class ListNode {
	friend class List; 
private:
	int data;  ListNode *link;
public:
	ListNode():link(NULL){}
	ListNode(int D, ListNode *L = NULL):data(D),link(L){};
};

//-------------------- ------
class List {
	ListNode *first, *last;

public:
	List(int n);
	ListNode* find1(int i);
	int find2(int x);
	void set( int x,int i);
	int insert( int x, int i);
	int remove(int i);
	void print();
};
//----------------------------------------------------
List::List(int n) {
	ListNode *p = new ListNode(0,NULL);             
	first = p;
	while(n!=0)
	{
		ListNode *q = new ListNode(0,NULL);
		p->link = q;
		p = q;
		
		last = q;	n--;
	}

}

void List::set( int x ,int i) {
	 ListNode *p = find1(i-1);                    //#
	 if(p==NULL) cout<<"位置错误"<<endl;
	 else  p->data = x;
     
}
//""
ListNode* List::find1(int i) {
	if(i <-1)  return NULL;
	if(i==-1)  return first;
	ListNode *p = first->link;        int j = 0;
	while(p!=NULL && j < i) {  p = p->link; j++;  }
	return p;
}
   
int List::find2(int x) {

	ListNode *p = first; int k = 0;
	while(p!=NULL && p->data!=x)
	{
		  p = p->link;  k++;  
	}
	if(p==NULL) { cout<<"查找失败"<<endl;    return 0; }
	else  return k;
}
//----------------------------------------------------------------
int List::insert(int x, int i) {
	ListNode *p = find1(i-1);
	if(p==NULL) {  cout<<"位置错误"<<endl; return 0; }
    else
   {
	   ListNode *newnode = new ListNode( x , NULL );
	   newnode->link = p->link;

	   if(p->link==NULL) last = newnode;
	   p->link = newnode;
	   return 1;
	}
}
//----------------------------------------------------------------
int List::remove(int i) {
	ListNode *p = find1(i-1), *q;
    if(p==NULL) {  cout<<"位置错误"<<endl;  return 0; }
    else
   {
		if(p->link==NULL) last = p;
	   
		q = p->link;   p->link = q->link;   delete q;
	     
	   return 1;
	}
}
//----------------------------------------------------------------- 
void List::print() {
	int i=0;
	while(find1(i)!=NULL)
	{
		cout<<find1(i)->data<<",";
		i++;
	}
	cout<<endl; 
}

//#######################################
void main() {
	List L(5);int m,n;
    for(int j=1;j<=5;j++)  L.set(2*j,j);
	cout<<"原链表各结点的数据为："<<endl;
	L.print();

	cout<<"输入要找的数据："<<endl;  cin>>m;
	if(L.find2(m)!=0)
	cout<<"要找的数据在第"<<L.find2(m)<<"个数"<<endl;
	
	
	cout<<"输入插入的数据和位置："<<endl; cin>>m>>n;
	cout<<"插入结果为："<<endl;
	if(L.insert(m,n-1)==1)  L.print();
	

	cout<<"输入删除的位置："<<endl;  cin>>n;
	cout<<"删除后结果为："<<endl;
	if(L.remove(n-1)==1)	L.print();

}