8b.cpp

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

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

class ListNode {
	friend class List;
private:
	int data;
	ListNode* link; 
public:
	ListNode(int x, ListNode *p) { data = x; link = p; }
};
//-----------------------------------------------------
class List {
	ListNode *first, *last;
public:
 
	List(ListNode *f = NULL, ListNode *l = NULL);
	void Insert(const int x, const int i);
	void Romove(int i); 
	void Find(int x);
	void print();
};
//--------------------------------------------------------
List::List(ListNode *f, ListNode *l) { 
	first = f; last = l; 
	//first = new ListNode(0,NULL); 
}
//--------------------------------------------------------
void List::Insert(const int x, const int i) {

	ListNode *p = first;
	int k = 0; 
	while( p!=NULL && k < i-1 )
	{
		p = p->link;
		k++;
	}
	ListNode *newnode = new ListNode(x,NULL); 
	newnode->link = p->link;

	if( p->link==NULL ) last = newnode;
		
	p->link = newnode; 
}
//````````````````````````````````````````````````
void List::Romove(int i) {
	ListNode *p = first, *q;
	int k = 0;
	while(p!=NULL && k < i-1)
	{
		p = p->link;
		k++;
	}
	if( p->link==NULL )
	{
		cout<<"Invalid position for Deleting!\n" ;
		exit(-1);
	}
	q = p->link;
	p->link = q->link;
	delete q;
	if (p->link==NULL)
	{
		last = p;
	}
}
//---------------------------------------------------------
void List::Find(int x) {
	ListNode *p = first;
	int k = 0; 
	while(p!=NULL && p->data!=x )
	{
		p = p->link;
		k++;
	}
	if(p==NULL)
	{
		cout<<"Empty or didn't find!\n";
	}
	else
	{
		cout<<"x is in the position of "<<k<<endl;
	}
}
//```````````````````````````````````````
void List::print() {
	cout<<"当前的 LIST 为："<<endl;
	ListNode *p = first->link;
	while (p!=NULL)
	{
		cout<<p->data<<endl;
		p = p->link;
	}
}
//*******************************************
void main(int argc, char* argv[]) {
	List list;
	int x=0;
	int n=0;
	cout<<"你要输入 n 个数， n="<<endl;
	cin>>n;
	for (int i=0;i<n;i++)
	{
		cout<<"输入要插入的数"<<endl;
		cin>>x;
		list.Insert(x,i+1);
	}
	list.print();
//*
	cout<<"put in another one(数字，位置):\n";
	int p=0;
	cin>>x;
	cin>>p;
	list.Insert(x,p);
	list.print();

	cout<<"Find(x)\n";
	cin>>x;
	list.Find(x);

	cout<<"remove(position)\n";
	cin>>p;
	list.Romove(p);
	list.print();

}