/*
	源文件名：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();
	}
}