osqlist.cpp

编辑一个顺序链表,在这个表中添加删除查找

/*
	源文件名：OSqList.cpp
	功能：静态线性表类
*/
#include <iostream.h>
#include <iomanip.h>
#include <conio.h>
#include <stdio.h>
#include <process.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

const max=10000;

class SqList
{
	private:
		int elem[max];         //存放元素的数组
		int length;            //当前长度
	public:
		void init();
		void display();
		void insert();
		void search();
		void del();
		void simpleSort();
		void quickSort();
		void binarySearch();
        void sort(int elem[],int low,int high);

};

//屏幕提示后，从键盘输入线性表长度和随机数种子，生成指定长度的线性表list
void SqList::init()
{
	int i;
	while (1)
	{
	    cout << "输入元素个数（0－" << max << "）：" << flush;
		cin >> length;
		if (length >= 0 && length <= max)
			break;
		cout << endl;
	}
	while (1)
	{
	    cout << "输入随机数种子（0－32767）：" << flush;
		cin >> i;
		if (i >= 0 && i <= 32767)
			break;
		cout << endl;
	}
	srand(i);  //指定随机数种子，相同的种子将产生相同的数据序列
	rand();

	for (i = 0; i < length; i++)
	{
		elem[i] = rand() % 10000;
	}
	for (i = length; i < max; i++)
		elem[i] = 0;
}

//在屏幕上依次显示线性表list中的元素个数和全部元素
//格式应便于观察
//如果需要指定输出的宽度，可以使用 cout << setw(W) << X ，其中 X 是输出的数值，W 是占据的列数
void SqList::display()
{
	for (int i = 0; i < length; i++)
	{
		cout << setw(6) << elem[i];
		if (i % 10 == 9)
			cout << endl;
	}
	cout << endl;
	cout << "\n\n请按任意键继续" << flush;
	getch();
}

//屏幕提示后，从键盘输入一个元素值，然后把这个新元素插到线性表list的末尾
//应有溢出判断和报告
void SqList::insert()
{
int x;
	cout<<"请输入一个数:"<<endl;
	cin>>x;
	length=length+1;
    elem[length-1]=x;
    for (int i = 0; i < length; i++)
	{
		cout << setw(6) << elem[i]<<"  ";
		if (i % 10 == 9)
			cout << endl;
	}
	
	cout<<endl;	
	cout << "\n\n请按任意键继续" << flush;
	getch();
}

//屏幕提示后，从键盘输入一个元素值，在线性表list中搜索这个元素
//屏幕显示搜索结果和搜索过程中的比较次数
void SqList::search()
{
 int x,s=0;
	cout<<"请输入一个数:"<<endl;
	cin>>x;
	for(int i=0;i<length;i++)
	{
		int j=i;
		if(elem[i]==x)
		{
			s=1;
			cout<<"成功!"<<" "<<"比较次数:"<<j<<endl;
		}
		
	}
	if(s==0)
		cout<<"查找失败!"<<endl;
    cout << "\n\n请按任意键继续" << flush;
	getch();
}

//屏幕提示后，从键盘输入一个元素值，在线性表list中删除这个元素
//屏幕显示删除成功与否的信息，并显示比较次数和移动次数
void SqList::del()
{
    int x;
    cout<<"请输入一个数:"<<endl;
	cin>>x;
	for(int i=0;i<=length;i++)
		
	{
		if(elem[i]==x)
		{
           for(int j=i;j<=length;j++)
		   {
			   elem[j]=elem[j+1];
		      
		        
		   }
          cout<<"成功!"<<" "<<"比较次数:"<<i<<" "<<"移动次数:"<<length-i-1<<endl;
          length=length-1;
		}
	}
	elem[length]=NULL;
    cout << "\n\n请按任意键继续" << flush;
	getch();
}

//对线性表list进行简单排序
//屏幕显示比较次数和移动次数
void SqList::simpleSort()
{
    int s=0,t,min,c=0,min_index;
	char x;
	cout<<"升序Y/N"<<"请选择"<<endl;
	cin>>x;
	if(x=='y'||x=='Y')
	{
	for(int i=0;i<length;i++)
	{
		min=elem[i];
		min_index=i;
		for(int j=i+1;j<length;j++)
		{
			if(min>elem[j])
			{
				min=elem[j];
				min_index=j;
			}
		}
		if(elem[i]>min)
		{
			t=elem[i];
			elem[i]=elem[min_index];
			elem[min_index]=t;
			c=c+1;
		}
	}
	}
	if(x=='n'||x=='N')
	{
		for(int i=0;i<length;i++)
		{
			min=elem[i];
			min_index=i;
			for(int j=i+1;j<length;j++)
			{
				if(min<elem[j])
				{
					min=elem[j];
					min_index=j;
				}
			}
			if(min>elem[i])
			{
				t=elem[i];
				elem[i]=elem[min_index];
				elem[min_index]=t;
				c=c+1;
			}
		}
	}
	cout<<"比较次数"<<length*(length-1)/2<<"移动次数"<<c<<endl;
	for(int k=0;k<length;k++)
	{
		cout<<setw(6)<<elem[k];
	}
	cout << endl;
	cout << "\n\n请按任意键继续" << flush;
	getch();
}

//对线性表list进行快速排序
//屏幕显示比较次数和移动次数
void SqList::sort(int elem[],int low,int high)
{
	int z,y,k;
	if(low<high)
	{
		z=low;
		y=high;
		k=elem[z];
		do{
			while((z<y)&&(elem[y]>=k))
				y--;
			if(z<y)
			{
			        elem[z]=elem[y];
				z=z+1;
			}
			while((z<y)&&(elem[z]<=k))
				z++;
			if(z<y)
				elem[y]=elem[z];
		}
		while(z!=y);
		elem[z]=k;
	    sort(elem,low,z-1);
		sort(elem,z+1,high);
		
	}
}
void SqList::quickSort()
{
	sort(elem,0,length-1);
	cout<<"快排成功!"<<endl;
	cout<<endl;
    cout << "\n\n请按任意键继续" << flush;
	getch();
}

//屏幕提示后，从键盘输入一个元素值，对经过排序的线性表list进行折半查找
//屏幕显示查找结果，并显示比较次数
void SqList::binarySearch()
{
    char a;
	cout<<"升序排列(y/n)"<<endl;
	cin>>a;
	if(a=='y'||a=='Y')
	{
	int x,t=0;
    cout<<"请输入一个数:";
	cin>>x;
	int mid,low=0,high=length-1;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(elem[mid]==x)
		{
		    cout<<"比较次数："<<t<<endl;
			break;
		}
		else 
		
			if(elem[mid]>x)
			high=mid-1;
		else 
			low=mid+1;
		t++;
		
	}
	if(low>high)
		cout<<"不存在这个数！"<<endl;

	 cout << "\n\n请按任意键继续" << flush;
	getch();
	}
	if(a=='n'||a=='N')
	{
    int x,t=0;
    cout<<"请输入一个数:";
	cin>>x;
	int mid,low=0,high=length-1;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(elem[mid]==x)
		{
		    cout<<"比较次数："<<t<<endl;
			break;
		}
		else 
		
			if(elem[mid]<x)
			high=mid-1;
		else 
			low=mid+1;
		t++;
		
	}
	if(low>high)
		cout<<"不存在这个数！"<<endl;

	 cout << "\n\n请按任意键继续" << flush;
	getch();
	}
}