【数据结构应用题】线性表的顺序表示（含统考真题）_线性表顺序存储结构的作业题

线性表的顺序表示详细讲解

第一题

题面：从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。
空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
审题：顺序表 删除 最小值元素（唯一） 返回元素值 最后一位填补 显示错误信息
思路：传入顺序表 判空 遍历找最小值 函数与最小值类型相同 和最后一位交换值
算法实现：

ElemType Del_Min(Sqlist &L){
	if ( L.length==0 ) {            	//判空并输出错误信息
		printf("警告：顺序表为空\n");
		return 0;
	}
	ElemType minn=L.data[0];            //假定0号元素值最小
	int miid=0;
	for ( int i=1 ; i<L.length ; i++ ){ //遍历寻找具有最小值的元素
		if ( L.data[i]<minn ){
			minn=L.data[i];
			miid=i;
		}
	}
	L.data[miid]=L.data[L.length-1];    //空出的位置由最后一个元素填补
	L.length--;                         //删除最后一个元素
	return minn;                        //由函数返回被删元素的值
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第二题

题面：设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。
审题：顺序表 所有元素逆置 空间复杂度为O(1) 高效算法
思路：不能借助新的数据结构存储，直接交换原有顺序表的值 每次交换两个只需要遍历一半
算法实现：

void Reverse(Sqlist &L){
	ElemType tmp;		//用于交换
	for ( int i=0 ; i<L.length/2 ; i++){	//遍历一半顺序表
		tmp=L.data[i];
		L.data[i]=L.data[L.length-1-i];
		L.data[L.length-1-i]=tmp;
	}
	return ;
}
1
2
3
4
5
6
7
8
9

第三题

题面：对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。
审题：顺序表 删除值为x的元素 时间复杂度为O(n) 空间复杂度为O(1)
思路：普通删除时间复杂度为O(n)，删除m个x时间复杂度为O(n*m)不可行。遍历一次删除所有x的同时找到所有不为x值元素所在位置
算法实现：

void Del_x(Sqlist &L,ElemType x){
	int k=0;        //记录当前是第几个不为x的元素
	for ( int i=0 ; i<L.length ; i++ ){
		if ( L.data[i]!=x ){
			L.data[k]=L.data[i];
			k++;
		}
	}
	L.length=k;		//修改顺序表长度
}
1
2
3
4
5
6
7
8
9
10

第四题

题面：从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素，若s或t不合理或顺序表为空,则显示出错信息并退出运行。
审题：有序顺序表 删除值为s与t之间的元素 显示出错信息
思路：顺序表有序，则只需要删除一段连续空间即可
算法实现：

void Del_s_t(Sqlist &L,ElemType s,ElemType t){
	if ( s > t ){
		printf("警告：s>t不合理\n");
		return ;
	}
	if ( L.length==0 ) {        //判空并输出错误信息
		printf("警告：顺序表为空\n");
		return ;
	}
	int k=0;      //记录当前是第几个不为s与t之间的元素
	for ( int i=0 ; i<L.length ; i++ ){
  	if ( L.data[i]<s ) k++;
		if ( L.data[i]>t ){
			L.data[k]=L.data[i];
			k++;
		}
	}
	L.length=k;	//修改顺序表长度
	return ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

第五题

题面：从顺序表片删除其值在给定值s与t之间(包含s和t，要求s<1)的所有元素,若s或t不合理或顺序表为空,则显示出错信息并退出运行。
审题：顺序表 删除值为s与t之间的元素 显示出错信息
思路：与第三题类似，找到小于s或大于t的元素的位置即可
算法实现：

void Del_s_t2(Sqlist &L,ElemType s,ElemType t){
	if ( s > t ){
		printf("警告：s>t不合理\n");
		return ;
	}
	if ( L.length==0 ) {            	//判空并输出错误信息
		printf("警告：顺序表为空\n");
		return ;
	}
	int k=0;        //记录当前是第几个不为s与t之间的元素
	for ( int i=0 ; i<L.length ; i++ ){
		if ( L.data[i]<s || L.data[i]>t ){
			L.data[k]=L.data[i];
			k++;
		}
	}
	L.length=k;
	return ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第六题

题面：从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
审题：有序顺序表 删除重复的元素
思路：顺序表有序则相同元素位置连续，保留其中一个即可
算法实现：

void Del_Same(Sqlist &L){
	if ( L.length==0 ) {            	//判空并输出错误信息
		printf("警告：顺序表为空\n");
		return ;
	}
	int k=1;        //记录当前是第几个不为重复的元素
	for ( int i=1 ; i<L.length ; i++ ){
		if ( L.data[i]!=L.data[i-1] ){
			L.data[k]=L.data[i];
			k++;
		}
	}
	L.length=k;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

第七题

题面：将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表
审题：两个有序顺序表 合并 一个新的有序顺序表 函数返回结果顺序表
思路：按顺序不断将两表头较小元素放入新表中
算法实现：

bool Merge(Sqlist A,Sqlist B,Sqlist &C){
	if ( A.length+B.length>MaxSize ) return false;	//合并后超过C的最大长度
	int i=0,j=0,k=0;	//分别为ABC的指针
	while ( i<A.length && j<B.length ){	//依次放入两表头较小元素
		if ( A.data[i]<B.data[j] )
			C.data[k++]=A.data[i++];
		else
			C.data[k++]=B.data[j++];
	}
	while ( i<A.length )	//A有剩余
		C.data[k++]=A.data[i++];
	while ( j<B.length )	//B有剩余
		C.data[k++]=B.data[j++];
	C.length=k;		//修改C的长度
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

第八题

题面：已知在一维数组 A[m+n]中依次存放两个线性表(a1, a2, a3,…, am)和(b1, b2,b3,…, bn)。试编写一个函数，将数组中两个顺序表的位置互换，即将(b1,b2, b3,…, bn,)放在(a1, a2,a3.…, am)的前面。
审题：一维数组 两个顺序表 位置互换
思路：要使(a,b,c,d,e,f,g) -> (e,f,g,a,b,c,d)
可以先(a,b,c,d,e,f,g) -> (g,f,e,d,c,b,a) 再 ((g,f,e),(d,c,b,a)) -> ((e,g,f),(a,b,c,d))需要进行三次逆置
算法实现：

void Reverse(ElemType A[],int left,int right){	//逆置函数
	ElemType tmp;
	int mid=(right+left)/2;
	for ( int i=0 ; i<=mid-left ; i++ ){
		tmp=A[left+i];
		A[left+i]=A[right-i];
		A[right-i]=tmp;
	}
	return ;
}

void Exchange(ElemType A[],int m,int n){
	Reverse(A,0,m+n-1);		//(a,b,c,d,e,f,g) -> (g,f,e,d,c,b,a) 
	Reverse(A,0,n-1);		//((g,f,e),(d,c,b,a)) -> ((e,g,f),(d,c,b,a))
	Reverse(A,n,m+n-1);		//((e,g,f),(d,c,b,a)) -> ((e,g,f),(a,b,c,d))
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第九题

题面：线性表(a, a2, a3,…, an)中的元素递增有序且按顺序存储于计算机内.要求设计一个算法,完成用最少时间在表中查找数值为x的元素，若找到，则将其与后继元素位置相交换，若找不到,则将其插入表中并使表中元素仍递增有序。
审题：线性表 递增有序 查找 数值为x的元素 与后继元素位置相交换 插入表中 仍递增有序 最少时间
思路：对于有序序列的高效查找可以采用二分法,找到第一个大于等于x的元素
算法实现：

void SearchExchangeInsert(ElemType A[],ElemType x,int length){
	int left=0,right=length-1,mid;
	while ( left!=right ){              //二分法查找
		mid=(left+right)/2;
		if ( A[mid]==x ) break;
		else if ( A[mid]<x ) left=mid+1;
		else right=mid-1;
	}
	if ( A[mid]==x && mid!=length-1 ){  //找到x 	与后继元素位置相交换
		ElemType t=A[mid+1];
		A[mid+1]=A[mid];
		A[mid]=t;
	}
	if ( A[mid]!=x ){                  //没找到x   插入表中
	}
	return ;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

第十题【2010统考真题】

题面：设将n(n>1)个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0<p<n)个位置，即将R中的数据由(Xo,X,…,Xn-)变换为(XmX+1,…,X-1，X,X,…,X-1)。
审题：数组 n(n>1)整数 循环左移 p(0<p<n)个位置 时间和空间都尽可能高效
思路：要使(1,2,3,4,5,6,7) p=3-> (5,6,7,1,2,3,4)
可以先(1,2,3,4,5,6,7) -> (7,6,5,4,3,2,1) 再 ((7,6,5),(4,3,2,1)) -> ((5,6,7),(1,2,3,4))
算法实现：

void Reverse(int A[],int left,int right){	//逆置
	int tmp,mid=(right+left)/2;
	for ( int i=0 ; i<=mid-left ; i++ ){
		tmp=A[left+i];
		A[left+i]=A[right-i];
		A[right-i]=tmp;
	}
	return ;
}

void Converse(int A[],int n,int p){
	Reverse2(A,0,n-1);		//(1,2,3,4,5,6,7) -> (7,6,5,4,3,2,1)
	Reverse2(A,0,p-1);		//((7,6,5),(4,3,2,1)) -> ((5,6,7),(4,3,2,1))
	Reverse2(A,p,n-1);		//((5,6,7),(4,3,2,1)) -> ((5,6,7),(1,2,3,4))
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

第十一题【2011统考真题】

题面：一个长度为L(L≥1)的升序序列S，处在第[L/2]个位置的数称为S的中位数。 例如，若序列S1=(11,13,15,17,19),则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。 例如,若S2=(2,4,6,8,20)，则S1和S2的中位数是11。现在有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。
审题：中位数 第[L/2]个位置 等长升序序列 找出两个序列A和B的中位数
思路一：先有序合并两序列，再找到中位数，时空复杂度均为O(n)

思路二：思路二：利用已知条件，可以快速找到A，B各自中位数a,b
若a==b,则序列A和B的中位数为 a或b
若a>b ,则删去A中较大的一半，B中较小的一半,删去相同的长度
若a<b ,则删去A中较小的一半，B中较大的一半,删去相同的长度
循环上述过程，直到A，B都只剩1个元素，取较小的一个
时间复杂度：O(log2n)，空间复杂度：O(1)
算法实现：

int M_Search1(int A[],int B[],int n){
    int C[n*2];
    int i=0,j=0,k=0;
	while ( i<n && j<n ){
		if ( A[i]<B[j] )
			C[k++]=A[i++];
		else
			C[k++]=B[j++];
	}
	while ( i<n )
		C[k++]=A[i++];
	while ( j<n )
		C[k++]=B[j++];

//    printf("\n");
//	for ( int i=0 ; i<n*2 ; i++) printf("C[%d]=%d\n",i+1,C[i]);
	
	return C[n-1];
}

int M_Search2(int A[],int B[],int n){
	int s1=0,e1=n-1,m1;
	int s2=0,e2=n-1,m2;
	while ( s1!=e1 || s2!=e2 ){
		m1=(s1+e1)/2;
		m2=(e2+s2)/2;
		if( A[m1]==B[m2] ) return A[m1];//若a==b,则序列A和B的中位数为 a或b
		else if( A[m1]>B[m2] ){	//若a>b ,则删去A中较大的一半，B中较小的一半
			if ((s1+e1)%2==0)	//保证删去相同的长度
				e1=m1,s2=m2;
			else
				e1=m1,s2=m2+1;
		}
		else{				// 若a<b ,则删去A中较小的一半，B中较大的一半
			if ((s1+e1)%2==0)	保证删去相同的长度
				s1=m1,e2=m2;
			else
				s1=m1+1,e2=m2;
		}
	}
	return A[s1]<B[s2] ? A[s1] : B[s2];//A，B都只剩1个元素，取较小的一个
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

第十二题【2013统考真题】

题面：已知一个整数序列A=(a0,a1,…,an-1)，其中0<ai<n(0<i<n)。若存在ap1=ap2=…=apm=X且m>n/2(0<=pk<n, 1<=k<=m),则称x为A的主元素。例如A=(0,5,5,3,5,7,5,5)，则5为主元素;又如A=(0,5,5,3,5,1,5,7)，则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素;否则输出-1。
审题：整数序列 主元素 众数个数大于n/2
思路：可以排序后，遍历一遍得答案时间复杂度O(nlog2n)；也可以遍历时记录当前能做主元素得值的个数时间复杂度O(n),比较难想到
算法实现：

int Majority(int A[],int n){
	int i,x=A[0],count=1;
	for ( i=1 ; i<n ; i++ ){
		if ( A[i]==x ) count++;
		else{
			if ( count ) count--;
			else {
				x=A[i];
				count++;
			}
		}
	}
	if ( count )
		for ( i=count=0 ; i<n ; i++ )
			if ( A[i]==x ) count++;
	if ( count>n/2 )	return x;
	else return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

第十三题【2018统考真题】

题面：给定一个含n(n>=1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中 未出现的最小正整数是1;数组{1,2,3}中未出现的最小正整数是4。
审题：整数数组 时间高效 未出现的 最小正整数
思路：利用一个新的数组记录当前出现过的1-n的数
算法实现：

int FindMissMin(int A[],int n){
	int i,B[n+5];	//B作为标记数组
	for ( i=0 ; i<n ; i++ )
		if ( A[i]>0 && A[i]<=n ) B[A[i]]++;//标记出现过的数
	for ( i=1 ; i<=n ; i++ )
		if ( B[i]==0 ) break;//找到第一个未出现的正整数
	return i;
}
1
2
3
4
5
6
7
8

第十四题【2020统考真题】

题面：定义三元组(a, b,c) (a、b、c均为正数)的距离D=|a-b|+|b-c+|c-a|。给定3个非空整数集合S1、S2和S3, 按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a,b,c) (a∈S1,b∈S2, c∈S3) 中的最小距离。例如S1={-1,0,9}， S2={-25,-10,10,11}， S3={2,9, 17,30, 41}，则最小距离为2，相应的三元组为(9, 10,9)。
审题：整数集合 升序数组 三元组(a,b,c) 最小距离
思路：对于一个三元组D的大小取决于最大值与最小值的差（建立自己举例理解这句话）。为了找最小的D可以固定最大值，每次改变最小值，计算并更新D
算法实现：

bool xls_min(int a,int b,int c){//判断a是否为3数中最小的一个
	return( a<=b && a<=c);
}

int FindMinofTrip(int A[],int n,int B[],int m,int C[],int p){
	int i=0,j=0,k=0,D_min=INF,D;
	while( i<n && j<m && k<p && D_min>0 ){
		D=fabs(A[i]-B[j])+fabs(B[j]-C[k])+fabs(A[i]-C[k]);//计算D
		D_min=min(D_min,D);//更新D
		if( xls_min(A[i],B[j],C[k]) ) i++;		//将最小值下标加一
		else if ( xls_min(B[j],A[i],C[k]) ) j++;
		else k++;
	}
	return D_min;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1-14题测试代码

#include<bits/stdc++.h>
using namespace std;

typedef int ElemType; //线性表元素数据类型

const int INF=0x3f3f3f3f;

//静态分配
#define MaxSize 50  //线性表最大长度
typedef struct{
	ElemType data[MaxSize];     //顺序表的元素
	int length;                 //顺序表的当前长度
}Sqlist;                        //顺序表的类型定义

ElemType Del_Min(Sqlist &L);
void Reverse(Sqlist &L);
void Del_x(Sqlist &L,ElemType x);
void Del_s_t(Sqlist &L,ElemType s,ElemType t);
void Del_s_t2(Sqlist &L,ElemType s,ElemType t);
void Del_Same(Sqlist &L);
bool Merge(Sqlist A,Sqlist B,Sqlist &C);
void Exchange(ElemType A[],int m,int n);
void SearchExchangeInsert(ElemType A[],ElemType x,int length);
void Converse(int A[],int n,int p);
int M_Search1(int A[],int B[],int n);
int M_Search2(int A[],int B[],int n);
int Majority(int A[],int n);
int FindMissMin(int A[],int n);
int FindMinofTrip(int A[],int n,int B[],int m,int C[],int p);

//1-7题
void test1(){
	//初始化
	Sqlist L;
	L.length=0;
	for ( int i=0 ; i<10 ; i++ ){
		L.data[i]=rand()%20;
		L.length++;
	}

	Sqlist LA;
	LA.length=0;
	for ( int i=0 ; i<5 ; i++ ){
		LA.data[i]=rand()%20;
		LA.length++;
	}
	Sqlist LB;
	LB.length=0;
	for ( int i=0 ; i<5 ; i++ ){
		LB.data[i]=rand()%20;
		LB.length++;
	}
	Sqlist LC;
	LC.length=0;

	sort(L.data,L.data+L.length);       //排序
	sort(LA.data,LA.data+LA.length);       //排序
	sort(LB.data,LB.data+LB.length);       //排序
	//输出
//	for ( int i=0 ; i<L.length ; i++ ) printf("L.data[%d]=%d\n",i+1,L.data[i]);
	for ( int i=0 ; i<LA.length ; i++ ) printf("LA.data[%d]=%d\n",i+1,LA.data[i]);
	for ( int i=0 ; i<LB.length ; i++ ) printf("LB.data[%d]=%d\n",i+1,LB.data[i]);

//	printf("删除了%d\n",Del_Min(L));
//	Reverse(L);
//	Del_x(L,18);
//	Del_s_t(L,10,20);
//	Del_s_t2(L,10,20);
//	Del_Same(L);
	Merge(LA,LB,LC);

	//输出
//	for ( int i=0 ; i<L.length ; i++ ) printf("L.data[%d]=%d\n",i+1,L.data[i]);
	for ( int i=0 ; i<LC.length ; i++ ) printf("LC.data[%d]=%d\n",i+1,LC.data[i]);
	return ;
}

//8-14题
void test2(){
	//初始化
//	ElemType A[50],B[50];
//	for ( int i=0 ; i<10 ; i++){
//		A[i]=rand()%10;
//		B[i]=rand()%10+8;
//	}
		
		
	//排序
//	sort(A,A+10);
//	sort(B,B+10);
    //输出
//    printf("\n");
//	for ( int i=0 ; i<10 ; i++) printf("A[%d]=%d\n",i+1,A[i]);
//    printf("\n");
//	for ( int i=0 ; i<10 ; i++) printf("B[%d]=%d\n",i+1,B[i]);
	
//	Exchange(A,4,6);
//	SearchExchangeInsert(A,5,10);
//	Converse(A,10,4);
//	printf("序列A和B的中位数是%d\n",M_Search1(A,B,10));
//	printf("序列A和B的中位数是%d\n",M_Search2(A,B,10));
//	printf("序列A主元素是%d\n",Majority(A,10));
//	printf("序列A中未出现的最小正整数是%d\n",FindMissMin(A,10));
	int A[3]={-1,0,9},B[4]={-25,-10,10,11},C[5]={2,9,17,30,41};
	printf("最小距离是%d\n",FindMinofTrip(A,3,B,4,C,5));

	//输出
//    printf("\n");
//	for ( int i=0 ; i<10 ; i++) printf("A[%d]=%d\n",i+1,A[i]);
}

int main(){
//	test1();
	test2();
	return 0;
}

//***14.【2020统考真题】定义三元组(a, b,c) (a、b、c均为正数)的距离D=|a-b|+|b-c+|c-a|。
//给定3个非空整数集合S、S2和S3, 按升序分别存储在3个数组中。请设计一个尽可能高效的算法，
//计算并输出所有可能的三元组(a,b,c) (a∈S1,b∈S2, c∈S3) 中的最小距离。
//例如S1={-1,0,9}， S2={-25,-10,10,11}， S3={2,9, 17,30, 41}，则最小距离为2，相应的三元组为(9, 10,9)。要求:
//1)给出算法的基本设计思想。
//2)根据设计思想，采用C语言或C++语言描述算法，关键之处给出注释。
//3)说明你所设计算法的时间复杂度和空间复杂度。
bool xls_min(int a,int b,int c){
	return( a<=b && a<=c);
}

int FindMinofTrip(int A[],int n,int B[],int m,int C[],int p){
	int i=0,j=0,k=0,D_min=INF,D;
	while( i<n && j<m && k<p && D_min>0 ){
		D=fabs(A[i]-B[j])+fabs(B[j]-C[k])+fabs(A[i]-C[k]);
		D_min=min(D_min,D);
		if( xls_min(A[i],B[j],C[k]) ) i++;
		else if ( xls_min(B[j],A[i],C[k]) ) j++;
		else k++;
	}
	return D_min;
}

//13.【2018统考真题】给定一个含n(n>=1)个整数的数组，请设计一个在时间上尽可能高效的算法，
//找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中 未出现的最小正整数是1;数组{1,2,3}中未出现的最小正整数是4。要求:
//1)给出算法的基本设计思想。
//2)根据设计思想,采用C或 C++语言描述算法关键之处给出注释。
//3)说明你所设计算法的时间复杂度和空间复杂度。
//审题：整数数组 时间高效 未出现的 最小正整数
int FindMissMin(int A[],int n){
	int i,B[n+5];
	for ( i=0 ; i<n ; i++ )
		if ( A[i]>0 && A[i]<=n ) B[A[i]]++;
	for ( i=1 ; i<=n ; i++ )
		if ( B[i]==0 ) break;
	return i;
}

//***12.【2013统考真题】已知一个整数序列A=(a0,a1,...,an-1)，其中0<ai<n(0<i<n)。若存在ap1=ap2=...=apm=X且m>n/2(0<=pk<n, 1<=k<=m),则称x为A的主元素。
//例如A=(0,5,5,3,5,7,5,5)，则5为主元素;又如A=(0,5,5,3,5,1,5,7)，则A中没有主元素。假设A中的n个元素保存在一个一维数组中，
//请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素;否则输出-1。要求
//1)给出算法的基本设计思想。
//2)根据设计思想,采用C或 C++或 Java语言描述算法，关键之处给出注释。
//3)说明你所设计算法的时间复杂度和空间复杂度。
//审题：整数序列 主元素 众数个数大于n/2
int Majority(int A[],int n){
	int i,x=A[0],count=1;
	for ( i=1 ; i<n ; i++ ){
		if ( A[i]==x ) count++;
		else{
			if ( count ) count--;
			else {
				x=A[i];
				count++;
			}
		}
	}
	if ( count )
		for ( i=count=0 ; i<n ; i++ )
			if ( A[i]==x ) count++;
	if ( count>n/2 )	return x;
	else return -1;
}

//***11.【2011统考真题】一个长度为L(L≥1)的升序序列S，
//处在第[L/2]个位置的数称为S的中位数。 例如，若序列S1=(11,13,15,17,19),则S1的中位数是15，
//两个序列的中位数是含它们所有元素的升序序列的中位数。 例如,若S2=(2,4,6,8,20)，则S1和S2的中位数是11。
//现在有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。要求:
//1)给出算法的基本设计思想。
//2)根据设计思想,采用C或C+或Java语言描述算法，关键之处给出注释。
//3)说明你所设计算法的时间复杂度和空间复杂度。
//审题：中位数 第[L/2]个位置 等长升序序列 找出两个序列A和B的中位数
//思路一：先有序合并两序列，再找到中位数，时空复杂度均为O(n)
//思路二：利用已知条件，可以快速找到A，B各自中位数a,b
//          若a==b,则序列A和B的中位数为 a或b
//          若a>b ,则删去A中较大的一半，B中较小的一半,删去相同的长度
//          若a<b ,则删去A中较小的一半，B中较大的一半,删去相同的长度
//          循环上述过程，直到A，B都只剩1个元素，取较小的一个
//          时间复杂度：O(log2n)，空间复杂度：O(1)
int M_Search1(int A[],int B[],int n){
    int C[n*2];
    int i=0,j=0,k=0;
	while ( i<n && j<n ){
		if ( A[i]<B[j] )
			C[k++]=A[i++];
		else
			C[k++]=B[j++];
	}
	while ( i<n )
		C[k++]=A[i++];
	while ( j<n )
		C[k++]=B[j++];

//    printf("\n");
//	for ( int i=0 ; i<n*2 ; i++) printf("C[%d]=%d\n",i+1,C[i]);
	
	return C[n-1];
}

int M_Search2(int A[],int B[],int n){
	int s1=0,e1=n-1,m1;
	int s2=0,e2=n-1,m2;
	while ( s1!=e1 || s2!=e2 ){
		m1=(s1+e1)/2;
		m2=(e2+s2)/2;
		if( A[m1]==B[m2] ) return A[m1];
		else if( A[m1]>B[m2] ){
			if ((s1+e1)%2==0)
				e1=m1,s2=m2;
			else
				e1=m1,s2=m2+1;
		}
		else{
			if ((s1+e1)%2==0)
				s1=m1,e2=m2;
			else
				s1=m1+1,e2=m2;
		}
	}
	return A[s1]<B[s2] ? A[s1] : B[s2];
}

//10.【2010统考真题】设将n(n>1)个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。
//将R中保存的序列循环左移p(0<p<n)个位置，即将R中的数据由(Xo,X,…,Xn-)变换为(XmX+1,…,X-1，X,X,…,X-1)。要求:
//1)给出算法的基本设计思想。
//2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
//3)说明你所设计算法的时间复杂度和空间复杂度。
//审题：数组 n(n>1)整数 循环左移 p(0<p<n)个位置 时间和空间都尽可能高效
//思路：要使(1,2,3,4,5,6,7) p=3-> (5,6,7,1,2,3,4)
//		可以先(1,2,3,4,5,6,7) -> (7,6,5,4,3,2,1) 再 ((7,6,5),(4,3,2,1)) -> ((5,6,7),(1,2,3,4))
void Reverse2(int A[],int left,int right){
	int tmp,mid=(right+left)/2;
	for ( int i=0 ; i<=mid-left ; i++ ){
		tmp=A[left+i];
		A[left+i]=A[right-i];
		A[right-i]=tmp;
	}
	return ;
}

void Converse(int A[],int n,int p){
	Reverse2(A,0,n-1);
	Reverse2(A,0,p-1);
	Reverse2(A,p,n-1);
}

//***9．线性表(a, a2, a3,…, an)中的元素递增有序且按顺序存储于计算机内.要求设计一个算法,
//完成用最少时间在表中查找数值为x的元素，若找到，则将其与后继元素位置相交换，若找不到,则将其插入表中并使表中元素仍递增有序。
//审题：线性表 递增有序 查找 数值为x的元素 与后继元素位置相交换 插入表中 仍递增有序 最少时间
//思路：对于有序序列的高效查找可以采用二分法,找到第一个大于等于x的元素
void SearchExchangeInsert(ElemType A[],ElemType x,int length){
	int left=0,right=length-1,mid;
	while ( left!=right ){              //二分法查找
		mid=(left+right)/2;
		if ( A[mid]==x ) break;
		else if ( A[mid]<x ) left=mid+1;
		else right=mid-1;
	}
	if ( A[mid]==x && mid!=length-1 ){  //找到x 	与后继元素位置相交换
		ElemType t=A[mid+1];
		A[mid+1]=A[mid];
		A[mid]=t;
	}
	if ( A[mid]!=x ){                  //没找到x   插入表中
	}
	return ;
}

//***8．已知在一维数组 A[m+n]中依次存放两个线性表(a1, a2, a3,…, am)和(b1, b2,b3,…, bn)。
//试编写一个函数，将数组中两个顺序表的位置互换，即将(b,b, bs,…, b,)放在(a, az,43.…, am)的前面。
//审题：一维数组 两个顺序表 位置互换
//思路：要使(a,b,c,d,e,f,g) -> (e,f,g,a,b,c,d)
//		可以先(a,b,c,d,e,f,g) -> (g,f,e,d,c,b,a) 再 ((g,f,e),(d,c,b,a)) -> ((e,g,f),(a,b,c,d))
//需要进行三次逆置
void Reverse(ElemType A[],int left,int right){
	ElemType tmp;
	int mid=(right+left)/2;
	for ( int i=0 ; i<=mid-left ; i++ ){
		tmp=A[left+i];
		A[left+i]=A[right-i];
		A[right-i]=tmp;
	}
	return ;
}

void Exchange(ElemType A[],int m,int n){
	Reverse(A,0,m+n-1);
	Reverse(A,0,n-1);
	Reverse(A,n,m+n-1);
}

//***7．将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表
//审题：两个有序顺序表 合并 一个新的有序顺序表 函数返回结果顺序表
//思路：按顺序不断将两表头较小元素放入新表中
bool Merge(Sqlist A,Sqlist B,Sqlist &C){
	if ( A.length+B.length>MaxSize ) return false;
	int i=0,j=0,k=0;
	while ( i<A.length && j<B.length ){
		if ( A.data[i]<B.data[j] )
			C.data[k++]=A.data[i++];
		else
			C.data[k++]=B.data[j++];
	}
	while ( i<A.length )
		C.data[k++]=A.data[i++];
	while ( j<B.length )
		C.data[k++]=B.data[j++];
	C.length=k;
	return true;
}

//6．从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
//审题：有序顺序表 删除重复的元素
//思路：顺序表有序则相同元素位置连续，保留其中一个即可
void Del_Same(Sqlist &L){
	if ( L.length==0 ) {            	//判空并输出错误信息
		printf("警告：顺序表为空\n");
		return ;
	}
	int k=1;        //记录当前是第几个不为x的元素
	for ( int i=1 ; i<L.length ; i++ ){
		if ( L.data[i]!=L.data[i-1] ){
			L.data[k]=L.data[i];
			k++;
		}
	}
	L.length=k;
}

//5．从顺序表片删除其值在给定值s与t之间(包含s和t，要求s<1)的所有元素,
//若s或t不合理或顺序表为空,则显示出错信息并退出运行。
//审题：顺序表 删除值为s与t之间的元素 显示出错信息
//思路：与第三题类似，找到小于s或大于t的元素的位置即可
void Del_s_t2(Sqlist &L,ElemType s,ElemType t){
	if ( s > t ){
		printf("警告：s>t不合理\n");
		return ;
	}
	if ( L.length==0 ) {            	//判空并输出错误信息
		printf("警告：顺序表为空\n");
		return ;
	}
	int k=0;        //记录当前是第几个不为s与t之间的元素
	for ( int i=0 ; i<L.length ; i++ ){
		if ( L.data[i]<s || L.data[i]>t ){
			L.data[k]=L.data[i];
			k++;
		}
	}
	L.length=k;
	return ;
}

//4．从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素，
//若s或t不合理或顺序表为空,则显示出错信息并退出运行。
//审题：有序顺序表 删除值为s与t之间的元素 显示出错信息
//思路：顺序表有序，则只需要删除一段连续空间即可
void Del_s_t(Sqlist &L,ElemType s,ElemType t){
	if ( s > t ){
		printf("警告：s>t不合理\n");
		return ;
	}
	if ( L.length==0 ) {            	//判空并输出错误信息
		printf("警告：顺序表为空\n");
		return ;
	}
	int k=0;        //记录当前是第几个不为s与t之间的元素
	for ( int i=0 ; i<L.length ; i++ ){
  	if ( L.data[i]<s ) k++;
		if ( L.data[i]>t ){
			L.data[k]=L.data[i];
			k++;
		}
	}
	L.length=k;
	return ;
}

//3．对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，
//该算法删除线性表中所有值为x的数据元素。
//审题：顺序表 删除值为x的元素 时间复杂度为O(n) 空间复杂度为O(1)
//思路：普通删除时间复杂度为O(n)，删除m个x时间复杂度为O(n*m)不可行
//遍历一次删除所有x的同时找到所有不为x值元素所在位置
void Del_x(Sqlist &L,ElemType x){
	int k=0;        //记录当前是第几个不为x的元素
	for ( int i=0 ; i<L.length ; i++ ){
		if ( L.data[i]!=x ){
			L.data[k]=L.data[i];
			k++;
		}
	}
	L.length=k;
}

//2．设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。
//审题：顺序表 所有元素逆置 空间复杂度为O(1) 高效算法
//思路：不能借助新的数据结构存储，直接交换原有顺序表的值 每次交换两个只需要遍历一半
void Reverse(Sqlist &L){
	ElemType tmp;
	for ( int i=0 ; i<L.length/2 ; i++){
		tmp=L.data[i];
		L.data[i]=L.data[L.length-1-i];
		L.data[L.length-1-i]=tmp;
	}
	return ;
}

//1．从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。
//空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
//审题：顺序表 删除 最小值元素（唯一） 返回元素值 最后一位填补 显示错误信息
//思路：传入顺序表 判空 遍历找最小值 函数与最小值类型相同 和最后一位交换值
ElemType Del_Min(Sqlist &L){
	if ( L.length==0 ) {            	//判空并输出错误信息
		printf("警告：顺序表为空\n");
		return 0;
	}
	ElemType minn=L.data[0];            //假定0号元素值最小
	int miid=0;
	for ( int i=1 ; i<L.length ; i++ ){ //遍历寻找具有最小值的元素
		if ( L.data[i]<minn ){
			minn=L.data[i];
			miid=i;
		}
	}
	L.data[miid]=L.data[L.length-1];    //空出的位置由最后一个元素填补
	L.length--;                         //删除最后一个元素
	return minn;                        //由函数返回被删元素的值
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446