dynamicinput.cpp

实现对列表的动态操作

#include<iostream>
#include<string>
#include<iomanip>
using namespace std;

//设置：memset( void *dest, void *src, int len )
//拷贝：memcpy( void *dest, void *src, int len )
//            目的指针     原指针   字节数

//////////////////////////// 破指针 ////////////////////////////
class List
{
public:
	//构造函数
	List( int ListSize )	//创建动态数组
	{
		elements = new int [ ListSize ];
		memset( elements, 0, sizeof(int)*ListSize );
		MaxSize = ListSize;
		length = 0;
	}
	//拷贝构造函数
	List( List &L )
	{
		length = L.length;
		MaxSize = L.MaxSize;
		elements = L.elements;
	}
	void Insert( const int x);	//插入元素x，由小到大排列
	int Delete( int k, int &x );	//删除第k个位置元素，并返回给x
	void Display();
	bool IsEmpty();
	void Search( const int x);	//查找元素x，并返回位置
	bool Find( int k, int &x );	//查找第k个元素，并返回给x
	// 析构函数，释放内存，全部清零
	~List()
	{
		delete [] elements;
		length = 0;
		MaxSize = 0;
	}
private:
	int length;
	int MaxSize;
	int *elements;
};
//end class List

void List::Insert( const int x)
{
	// 每调用一次Insert()，length加1
	length++;
	// 如果存储满员，则动态增加内存空间
	if( length == MaxSize )
	{
		MaxSize += 20;		//增加20个元素的内存空间
		int *another = new int[MaxSize];	//给新指针another分配空间并清零
		memset( another, 0, sizeof(int)*MaxSize );
		memcpy( another, elements, length*sizeof(int) );	//拷贝elements的元素到another中
		delete [] elements;		//释放elements
		elements = another;	    //elements指向another
		another = NULL;			//another指向空地址
	}
	
	//插入元素，使数组由小到大排列
		int i=0;
		for(;i<length;i++)
		{
			if (elements[i]<= x )
			{
				continue;
			}
			else
			{
				for (int j = length - 1; j >= i; --j)
				{
					elements[j] = elements[j-1];
				}
				elements[i] = x;
				return;
			}
		
		}
		if(i == length)
		{
			elements[i-1] = x;
		}
}
//end function Insert()

int List::Delete( int k, int &x )
{
	if( k>length )
	{
		cout << "Error: length < k" << endl;
	}
	else
	{
		x = elements[k];
		
		while( (length-k)>0 )
		{
			elements[k] = elements[k+1];
			k++;
		}
		length--;
		return x;
	}	
}
//end function Delete()

void List::Display()
{
	cout << setw(10) << left << "Length" << setw(10) << left << "MaxSize" 
		<< setw(10) << left << "Elements" << endl;
	for( int i = 0; i < length; i++ )
	{
		cout<< setw(10) << left << i+1 << setw(10) << left << MaxSize 
			<< setw(10) << left << elements[i] << endl;
	}
}
//end function Display()

bool List::IsEmpty()
{
	if( length == 0 )
	{
		return 0;
	}
	else
	{
		return 1;
	}
}
//end function IsEmpty()

void List::Search( const int x )
{
	int j = 0;
	cout << "Poistion: ";
	for( int i=0;i<=length;i++ )
	{
		if( x == elements[i] )
		{
			cout << i+1 << ends;
			j++;
		}
	}
	if(j == 0)
	{
		cout << "not found!" << endl;
	}
}
//end function Search()

bool List::Find( int k, int &x )
{
	if( k <= length )
	{
		x = elements[k-1];
		return 1;
	}
	else
	{
		return 0;
	}
}
//end function Find()

void main()
{
	int n;
	int &x = n;
	List L1(10);
	
	L1.Insert(5);
	L1.Display();
	cout << endl;

	L1.Insert(3);
	L1.Insert(3);
	L1.Insert(3);
	cout << endl;
	L1.Display();

	L1.Insert(2);
	cout << endl;
	L1.Display();

	L1.Insert(3);
	L1.Insert(9);
	cout << endl;
	L1.Display();

	L1.Delete(2,x);
	cout << "\nDeleted element: " << x << endl << endl;
	L1.Display();

	if( L1.Find(2,x) == 1 )
	{
		cout << "\nelements found: " << x << endl << endl;
	}
	else
	{
		cout << "\nFound nothing!" << endl << endl;
	}

	L1.Search(3);
	cout << endl;
	L1.Search(4);
	
	if( L1.IsEmpty() == 1 )
	{
		cout << "\nIt's not empty!" << endl << endl;
	}
	else
	{
		cout << "\nIt's empty!" << endl << endl;
	}
}