顺序表
1.从顺序表中删除具有最小值的元素（假设最小值唯一）并由函数返回被删除元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行
typedef int ElemType;
ElemType Del_Min(SqList &L){
if(L.length==0){
printf("表为空\n");
return;
}
int pos=0; /*******/
min=L.data[pos]; /*******/
for(int i=1;i<L.length;i++){
if(L.data[i]<min){
min=L.data[i];
pos=i;
}
}
L.data[pos]=L.data[length-1];
L.length--;
return min;
}
2.设计一个高效率算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)
void Reverse(SqList &L){
ElemType temp;
for(i=0;i<L.length/2;i++){
temp=L.data[i];
L.data[i]=L.data[L.length-i-1]; /**交换L.data[i]与L.data[L.length-i-1]**/
L.data[L.length-i-1]=temp;
}
}
3.对长度为n的顺序表L,编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据
void Del_x(SqList &L,ElemType x)
{
int k=0;
for(i=0;i<L.lengtn;i++){
if(L.data[i]!=x){
L.data[k]=L.data[i];
k++;
}
}
L.length=k;
}
****或者：
int k=0;
for(i=0;i<L.length;i++){
if(L.data[i]==k){
K++;
}
else{
L.data[i-k]=L.data[i];
}
}
L.length=L.length-k；
4.从有序顺序表中删除其值在给定s与t之间（要求s<t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行
bool Del_s_t(SqList &L,ElemType s,ElemType t){
int i,j;
if(L.length==0)
return false;
if(s>t)
return false;
for(i=0;i<L.length&&L.data[i]<s;i++); /**寻找值大于等于s的第一个元素**/
if(i>=L.length)
return false; /**若所有元素均小于s，返回**/
for(j=i;j<L.length&&L.data[j]<=t;j++); /**寻找值大于t的第一个元素**/
for(;j<L.length;i++,j++){
L.data[i]=L.data[j]; /**前移，填补被删除位置**/
}
L.length=i;
return true;
}
5.从顺序表中删除其值在给定s与t之间（包含s和t，要求s<t）的所有元素，若s或t不合理或顺序表为空，则显示错误信息并退出运行
bool Del_s_t2(SqList &L,ElemType s,ElemType t){
int i,k=0;
if(s>=t||L.length==0)
return false;
for(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 true;
}
//或者
if(L.data[i]>=s&&L.data[i]<=t){
K++
}
else
L.data[i-k]=L.data[i];
L.length=L.length-k;
6.从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同
bool Del_same(SqList &L){
int i,j;
if(L.length==0)
return false;
for(i=0;j=1;j<L.length;j++){ //i开始存储下标为0的元素，j为工作指针开始存储下标为1的元素
if(L.data[i]!=L.data[j]) //若有序表中i，j元素不同，说明此时有序表中无和data[i]重复的元素
L.data[++i]=L.data[j]; //向data[++i]中写入下标为j的元素
}
L.length=i+1;
return true;
}
7.将二个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表
bool Merge(SqList A,SqList B,SqList &L){
if(A.Length+B.Length>L.MaxSize)
return false;
int i=0,j=0,k=0;
while(i<A.length&&j<B.length){ //循环两两比较
if(A.data[i]<B.data[j]){
L.data[k++]=A.data[i++];
}
else
L.data[K++]=B.data[j++];
}
if(i<A.length){ //还有一个顺序表未比较完成
L.data[k++]=A.data[i++];
}
if(j<B.length){
L.data[k++]=B.data[j++];
}
L.length=k;
return true;
8.已知在一维数组A[m+n]中依次存放二个线性表(a1,a2,a3,…,am)和(b1,b2,b3,…,bn)。试编写一个函数，将数组中的二个顺序表的位置互换，即将(b1,b2,b3,…,bn)放在(a1,a2,a3,…,am)的前面
typedef int DataType
void Reverse(DataType a[],int left,int right){
if(left>right||left<0||right>=m+n)
return;
int mid=(left+right)/2;
for(int i=0;i<mid-left;i++){
DataType temp=A[left+i];
A[left+i]=A[right-i];
A[right-i]=temp;
}
}
void Exchange(DataType A[],int m,int n){
Reverse(A,0,m+n-1);
Reverse(A,0,n-1);
Reverse(A,n,m+n-1);
}
9.线性表（a1,a2,a3,…,an）中的元素递增有序，且按顺序存储与计算机内。要求设计一个算法，完成用最少的时间在表中查找数值为x的元素，若找到，则将其与后继元素位置相交换，若找不到，则将其插入表中并使表中元素仍递增有序
void SearchExchange(ElemType a[],ElemType x){
int low=0,high=n-1,mid;
while(low<high){
mid=(low+high)/2;
if(a[mid]==x)
break;
else if(a[mid]<x)
low=mid+1;
else
high=mid-1;
}
if(a[mid]==x&&mid!=n-1){ //若最后一个元素与x相等则不存在后继，不交换
t=a[mid];
a[mid]=a[mid+1];
a[mid+1]=t;
}
if(low>high){
for(i=n-1;i>high;i--){ //插入x，并后移x之后元素
a[i+1]=a[i];
}
a[high+1]=x; //二分查找结束失败后，x应位于high之后的下一个元素；或者low的位置
}
}
10.设将n(n>1)个整数存放到一维数组R中。设计一个在时间和空间二方面都尽可能高效的算法。将R中保存的序列循环左移p(0<0<n)个位置，即将R中的数据由(x0,x1,…,xn-1)变换为(xp,xp+1,…,xn-1,x0,x1,…xp-1)
1）给出算法的基本设计思想
2）根据设计思想，采用C或C++或java语言描述算法，关键之处给出注释
3）说明你所设计算法的时间复杂度和空间复杂度
算法基本设计思想：可以将这个问题视为把数组ab转化为数组ba（a代表数组前p个元素，b代表数组余下的n-p个元素），可以先将a逆置得到a逆b，在将b逆置得到a逆b逆，最后对a逆b逆进行整个逆置得到ba；
eg.对abcdefgh向左循环移动3（p=3）的过程如下:
Reverse(from,to):表示将数组下标从from到下标为to的所有元素逆置
Reverse(0,p-1)得到：cbadefgh
Reverse(p,n-1)得到:cbahgfed
Reverse(0,n-1)得到：defghabc
代码实现：
void Reverse（int R[],int from,int to）{
int i,temp;
for(i=0;i<(to-from+1)/2;i++){ //下标从0开始，（to-from+1）表示从from到to元素个数。
temp=R[from+i];
R[from+i]=R[to-i];
R[to-i]=temp;
}
}
void Converse(int R[],int n,int p){
Reverse(R,0,p-1);
Reverse(R,p,n-1);
Reverse(R,0,n-1);
}
时间复杂度：上述三个Reverse函数的时间复杂度分别为O(p/2)，O((n-p)/2)和O(n/2)，故时间复杂度为O(n)
空间复杂度：空间复杂度为O(1)
11.一个长度为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）说明你所设计算法的时间复杂度和空间复杂度
算法思想：
分别求二个升序A、B的中位数，设为a和b，求序列A，B的中位数过程如下：
若a=b，则a或者b为所求中位数，算法结束
若a<b，则舍弃A中较小的一半，同时舍弃B中较大的一半，要求舍弃长度相同
若a>b，则舍弃A中较大的一半，同时舍弃B中较小的一半，要求舍弃长度相同
在保留的二个升序序列中，重复上述算法，直到二个序列中只含一个元素为止，较小者即为所求中位数。
代码实现：
int M_Search(int A[],B[],int n){
int s1=0,d1=n-1,m1; //分别表示A，B的首位数，末位数和中位数
int S2=0,d2=n-1;m2;
while(s1!=d1||s2!=d2){ //当A,B中元素个数均大于1时
m1=(s1+d1)/2;
m2=(s2+d2)/2;
if(A[m1]==B[m2])
return A[m1];
if(A[m1]<B[m2]){ //条件2
if((s1+d1)%2==0){ //若元素个数为奇数
s1=m1; //舍弃A，B中间点以前，以后的部分且保留中间点
d2=m2;
}
else{ //元素个数为偶数
s1=m1+1; //舍弃A中间点以及中间点以前
d2=m2; //舍弃B在中间点以后，保留中心点
}
}
else{ //条件3
if((s2+d2)%2==0){ //元素个数为奇数
d1=m1; //舍弃A，B在中间点以后，以前保留中心点
s2=m2;
}
else{ //元素个数为偶数
d1=m1; //舍弃A中间点以后，且保留中心点
s2=m2+1 //舍弃B中间点以及中间点以前
}
}
}
return A[s1]<B[s2]?A[s1]:B[s2]; //A，B中均只有一个元素，此时较小的元素为所求中位数
}
时间复杂度：O(log2n)
空间复杂度：O(1)
12.已知一个整数序列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，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）说明你所设计算法的时间复杂度和空间复杂度
算法思想：
选取候选的主元素。依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到x中，记录Num出选的次数为1；若遇到下一个整数仍等于Num，则计数加1，否则计数减1；当计数为0时，将遇到的下一个元素保存到x中，计数重新置为1，开始新一轮计数即从当前位置重复上述过程，直到扫描完全部数组。
判断x中元素是否为真正的主元，则再次扫描数组，统计x出现的次数与n/2之间的关系
int Majority(int A[],int n){
int i;
int x=A[0],count=1;
for(i=1;i<n-1;i++){
if(a[i]==x)
count++;
else
if(count>0)
count--;
else{
x=a[i];
count=1;
}
}
if(count>0)
for(i=count=0;i<n;i++){
if(a[i]==x)
count++;
}
if(count>n/2)
return x;
else
return -1;
}
时间复杂度：O(n)
空间复杂度：O(1)
13.给定一个含n(n>=1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5，3，2，3}中未出现的最小正整数为1；数组{1，2，3}中未出现的最小正整数为4
int findMissMin(int A[],int n){
int i,*B;
B=(int*)malloc(sizeof(int)*n);
memset(B,0,sizeof(int)*n);
for(i=0;i<n;i++){
if(A[i]>0&&A[i]<=n)
B[A[i]-1]=1;
}
for(i=0;i<n;i++)
if(B[i]==0)
break;
return i+1;
}
