第四次作业参考代码

顺序存储示例代码：

/**********************************************************/       
  //Class                                   :   List 顺序存储操作类   
  //parm                                    :         
  //comment                                 :          
  //return                                  :   void      
  //Author                                  :          
  //date                                    :   2011.10.30      
/**********************************************************/  

#include <iostream.h>

const int MAXSIZE = 20;

class List{
public:
	List()
	{
		arr = new int[MAXSIZE];   //Allocation the space
		length = 0;               //the length of current array
		cout<<"Please input the data into the array:"<<endl;
		for(int i = 0;i < 15; i++)
		{
			cin>>*(arr + i);
			length ++;
		}
	}
	~List()
	{
		delete []arr;
	}
	void Insert(int i,int x);   //Insert a data into the array
	void Delete(int i);         //Delete a data from the array
	int Find(int x);            //Search a data from the array return the position of the data
	void Show();                //Print the data to SCR
private:
	int *arr;
	int length;
};

void List::Insert(int i,int x)
{
	if(i < 1 || i > length + 1)
	{
		cout<<"插入位置非法！"<<endl;
		return;
	}
	cout<<"The Inserted data is:"<<x<<endl;
	int *q = arr + i - 1;   //q为插入位置
	for(int *p = arr + length - 1; p >= q; --p)
		*(p + 1) = *p;   //插入位置及之后的数据后移
	*q = x;  //插入x
	++length;  //长度加1
	return;
}

void List::Delete(int i)
{
	if( i < 1 || i > length)
	{
		cout<<"删除位置非法！"<<endl;
		return;
	}
	cout<<"The Deleted data's position is:"<<i<<endl;
	int *p = arr + i - 1;  //p为删除位置
	int *q = arr + length - 1;  //最后一个数据位置
	for(++p;p <= q;++p)
		*(p - 1) = *p;   //被删除数据后的数据左移
	--length;   //长度减1
	return;
}

int List::Find(int x)
{
	int i = 1;
	int *p = arr;
	while(i <= length && *p++ != x)
		i++;
	if(i <= length)
		return i;
	else
		return -1;
}
void List::Show()
{
	cout<<"The data is:"<<endl;		
	for(int i = 0;i < length; i++)
	{
		cout<<*(arr + i)<<"\t";
		if((i + 1) % 5 == 0)   //每输出五个元素后换行
			cout<<endl;
	}
	cout<<endl;
}

void main()   //主函数可以自行改写验证上述类的成员函数
{
	List obj;
	obj.Show();
	obj.Insert(8,200);
	obj.Show();
	obj.Delete(5);
	obj.Show();
	cout<<"The positon is:"<<obj.Find(58)<<endl;
}

链式存储示例代码：

/**********************************************************/         
  //Class                                   :   Link 链式存储操作函数     
  //parm                                    :           
  //Function                                :      
  //  Create:创建带头结点的链表；Insert：插入数据；Delete：删除数据；
  //  Show：显示数据;Find：查找数据      
  //return                                  :   void        
  //Author                                  :            
  //date                                    :   2011.10.30        
/**********************************************************/ 
#include<iostream.h>  
  
struct Arr  
{  
    int data;  //数据
    struct Arr *next;  //链表指针  
}; 

class Link{
private:
	Arr *head;
public:
	Link();
	void Create();
	void Insert(int n,Arr *Insdata);
	void Delete(int m);
	void Show();
	int Find(int x);
	static int num;
};

int Link::num = 0;  //静态变量初始化

Link::Link()  //构造函数
{
	head = new Arr;
	head->next = NULL;
}

void Link::Create()  //创建链表
{
	Arr *p1,*p2;
	p1 = p2 = new Arr;
	cout<<"Please input the data:"<<endl;
	cin>>p1->data;
	while(p1->data != 0)
	{
		if(head->next == NULL)
		{
			head->next = p1;
		}
		else
		{
			p2->next = p1;
		}
		p2 = p1;
		num++;
		p1 = new Arr;
		cin>>p1->data;
	}
	p2->next = NULL;
	return;
}

void Link::Show()  //显示链表的数据
{
	Arr *p;
	p = head->next;
	cout<<"the Link's data:"<<endl;
	while(p != NULL)
	{
		cout<<p->data<<"  ";
		p = p->next;
	}
	cout<<endl;
}

void Link::Insert(int n,Arr *Insdata)//在第n个元素之前插入数据
{
	Arr *p1,*p2;
	p1 = head;
	for(int i = 1;i < n;i++)
		p1 = p1->next;
	p2 = p1->next;
	cout<<"Please input the data that you want to insert:"<<endl;
	cin>>Insdata->data;
	p1->next = Insdata;
	Insdata->next = p2;
	num++;
}

void Link::Delete(int m)//删除第m个数据元素
{
	Arr *p1,*p2;
	p1 = head;
	for(int i = 1;i < m;i++)
		p1 = p1->next;
	p2 = p1->next;
	p1->next = p2->next;
	delete p2;
	num--;
}

int Link::Find(int x)//查找数据为x的节点的位置
{
	Arr *p;
	int n = 1;
	p = head->next;
	while(p != NULL)
	{
		if(p->data == x)
			return n;
		else
			p = p->next;
		n++;
	}
	return -1;
}

void main()
{
	Link obj;
	obj.Create();
	obj.Show();
	Arr *p = new Arr;;
	int n,m;
	cout<<"Please input the position that you want insert data:"<<endl;
	cin>>n;
	if(n > obj.num + 1 || n < 1)
	{
		cout<<"The position is invalid!"<<endl;
		return;
	}
	obj.Insert(n,p);
	obj.Show();
	cout<<"Please input the position that you want delete data:"<<endl;
	cin>>n;
	if(n > obj.num || n < 1)
	{
		cout<<"The position is invalid!"<<endl;
		return;
	}
	obj.Delete(n);
	obj.Show();
	cout<<"Please input the data that you want find:"<<endl;
	cin>>n;
	m = obj.Find(n);
	if(m == -1)
		cout<<"Not Found!"<<endl;
	else
		cout<<"The position that you want to find is:"<<m<<endl;
}