#include<iostream>

using namespace std;

struct SeList{//struct結(jié)構(gòu)體與class唯一的區(qū)別就是默認(rèn)訪問(wèn)權(quán)限不一樣 
	int *data;//struct默認(rèn)是public的訪問(wèn)權(quán)限，所以方便用于作為節(jié)點(diǎn)結(jié)構(gòu)體 
	int Max;//動(dòng)態(tài)數(shù)組的整體思想是在結(jié)構(gòu)體內(nèi)聲明指針，最大長(zhǎng)度，實(shí)際長(zhǎng)度，在外部函數(shù)中生成實(shí)際的數(shù)組，數(shù)組的這三個(gè)主要指標(biāo)放在了結(jié)構(gòu)體中 
	int length;
};

void initList(SeList &list,int x){//數(shù)組初始化 
	list.data=new int[x];
	list.Max=x;
	list.length=0; 
}

void setList(SeList &list){//給數(shù)組賦值 
	for(int i=0;i<list.Max;++i){
		list.data[i]=i+1;
		if(list.length<list.Max){
			list.length++;
		}
	}
}

void set_List(SeList &list){//給數(shù)組賦值 
	for(int i=0;i<list.Max/2;++i){
		list.data[i]=i+1;
		if(list.length<list.Max/2){
			list.length++;
		}
	}
}

void printList(SeList &list){//打印數(shù)組 
	for(int i=0;i<list.length;++i){
		cout<<list.data[i]<<" ";
	}
	cout<<endl;
}

void increaseList(SeList &list,int len){//增加數(shù)組長(zhǎng)度 
	int *p=list.data;
	list.data=new int[list.Max+len];
	for(int i=0;i<list.length;++i){
		list.data[i]=p[i];
	}
	list.Max=list.Max+len;
	delete[] p;
}

bool deleteMin(SeList &list,int &value){//數(shù)組最后一個(gè)值替代最小值 
	if(list.length==0){
		return false;
	}
	value=list.data[0];
	int a=0;//輔助變量，記錄最小元素的位置 
	for(int i=0;i<list.length;++i){
		if(value>list.data[i]){
			value=list.data[i];
			a=i;
		}
	}
	list.data[a]=list.data[list.length-1];
	return true;
}

bool reverseList(SeList &list){//逆置數(shù)組元素 
	if(list.length==0){
		return false;
	}
	int temp=0;//輔助變量 
	for(int i=0;i<list.length/2;++i){//無(wú)需考慮數(shù)組元素個(gè)數(shù)的奇偶性，因?yàn)閘ength/2取整 
		temp=list.data[i];
		list.data[i]=list.data[list.length-i-1];
		list.data[list.length-i-1]=temp;
	}
	return true; 
}

bool reverse_List(SeList &list,int m,int n){//逆置數(shù)組中指定位置范圍的元素
	if(list.length==0||m>=n){
		return false;
	}
	int temp=0,k=0;
	for(int i=m-1;i<=(n+m-2)/2;++i){
		temp=list.data[i];
		list.data[i]=list.data[n-1-k];
		list.data[n-1-k]=temp;
		++k;
	}
}

void deleteX(SeList &list,int x){//刪除數(shù)組中值為x的所有元素 
	int k=0;//記錄非x的元素個(gè)數(shù)，也就是保留下來(lái)的元素個(gè)數(shù) 
	for(int i=0;i<list.length;++i){//順序掃描數(shù)組，每判斷一個(gè)非x值就加入結(jié)果數(shù)組 
		if(list.data[i]!=x){//非x元素保留下來(lái)，這里利用了i的值一定大于等于k的值，所以在一個(gè)循環(huán)中就可以解決問(wèn)題 
			list.data[k]=list.data[i];
			++k;
		}
	}
	list.length=k;//修改數(shù)組長(zhǎng)度 
}

bool deleteST(SeList &list,int s,int t){//刪除所有介于s和t之間（包含s與t）的元素 
	if(s>=t){
		cout<<"輸入范圍錯(cuò)誤"<<endl; 
		return false;
	}
	if(list.length==0){
		cout<<"順序表為空"<<endl;
		return false;
	}
	int k=0;// 記錄不在范圍s與t之間的元素的個(gè)數(shù) 
	for(int i=0;i<list.length;++i){//順序掃描數(shù)組，每判斷到一個(gè)不屬于s與t之間的元素就加入結(jié)果數(shù)組 
		if(list.data[i]<s||list.data[i]>t){
			list.data[k]=list.data[i];
			++k;
		}
	}
	list.length=k;//修改數(shù)組長(zhǎng)度 
	return true;
} 

void deleteSame(SeList &list){//有序表中刪除相同元素
	int k=1;//非相同元素的個(gè)數(shù) 
	for(int i=1;i<list.length;++i){// 因?yàn)榈谝粋€(gè)肯定不重復(fù)，從第二個(gè)元素開始順序掃描數(shù)組，每判斷到一個(gè)不是相同的元素就將其加入結(jié)果數(shù)組 
		if(list.data[i]!=list.data[i-1]){
			list.data[k]=list.data[i];
			++k;
		}
	}
	list.length=k;//修改數(shù)組長(zhǎng)度 
}

bool addList(SeList list1,SeList list2,SeList &list){//合并兩個(gè)有序數(shù)組，合并結(jié)果存入第三個(gè)數(shù)組 
	if(list1.length+list2.length>list.Max){//如果前兩個(gè)數(shù)組的長(zhǎng)度之和大于第三個(gè)數(shù)組長(zhǎng)度最大值，無(wú)法合并，返回錯(cuò)誤 
		return false;
	}
	int i=0;//輔助變量，記錄第一個(gè)數(shù)組的下標(biāo) 
	int j=0;//輔助變量，記錄第二個(gè)數(shù)組的下標(biāo) 
	int k=0;//輔助變量，記錄第三個(gè)數(shù)組的下標(biāo) 
	while(i<list1.length&&i<list2.length){//這里使用while循環(huán)，對(duì)判斷條件的設(shè)置比較關(guān)鍵；當(dāng)兩個(gè)數(shù)組都沒有遍歷完時(shí)，比較兩個(gè)數(shù)組最前面的值，較小者加入結(jié)果數(shù)組 
		if(list1.data[i]<=list2.data[j]){
			list.data[k]=list1.data[i];
			k++;
			i++; 
		}else{
			list.data[k]=list2.data[j];
			k++;
			j++;
		}
	}
	while(i<list1.length){//若只有第一個(gè)數(shù)組還沒有遍歷完，第一個(gè)數(shù)組剩余數(shù)據(jù)是表中較大的了，按順序加入結(jié)果數(shù)組即可 
		list.data[k]=list1.data[i];
		k++;
		i++;
	}
	while(j<list2.length){
		list.data[k]=list2.data[j];
		k++;
		j++;
	}
	list.length=k;
	return true;
}

bool invertList(SeList &list,int m,int n){//將數(shù)組中的前m位與后n為的位置互換，可以看做先將數(shù)組整個(gè)逆置，之后對(duì)目前的兩個(gè)數(shù)組分別再逆置，調(diào)用指定范圍的逆置函數(shù)實(shí)現(xiàn) 
	 reverseList(list);
	 reverse_List(list,1,n);
	 reverse_List(list,n+1,n+m);
	 return true;
} 

bool insert_List(SeList &list,int x){//若查到值為x的元素，將其與其后的元素交換位置，若查不到，則將其插入順序表中使得，順序表仍然遞增 
	 int low=0;
	 int n=list.length-1;
	 int high=n;
	 int mid;
	 while(low<=high){
	 	mid=(low+high)/2;
	 	if(list.data[mid]==x){
	 		break;
		 }else if(list.data[mid]<x){
		 	low=mid+1;
		 }else{
		 	high=mid-1;
		 }
	 }
	 if(list.data[mid]==x&&mid!=n){
	 	list.data[mid]=list.data[mid+1];
	 	list.data[mid+1]=x;
	 	cout<<x<<endl;
	 }
	 if(low>high){
	 	for(int i=n;i>high;--i){
	 		list.data[i+1]=list.data[i];
	 		list.data[i+1]=x;
	 		cout<<x<<endl;
		 }
		 list.length++;
	 }
}

int main(){
	SeList list1;
	initList(list1,15);
	setList(list1);//初始化并設(shè)置第一個(gè)數(shù)組 
	printList(list1);
	
	SeList list2;
	initList(list2,15);
	set_List(list2);
	printList(list2);//初始化并設(shè)置第二個(gè)數(shù)組 
	
	SeList list3;
	initList(list3,30);
	addList(list1,list2,list3);
	printList(list3);
	
	invertList(list1,6,9);
	printList(list1);

	
	insert_List(list2,5);
	printList(list2);
	
	
	return 0;
}