以下问题都简述!
1.搜索顺序表，查找最小值元素，用最后的元素代替它。
思想：初始为第一个元素为最小值，遍历第2-n个元素，寻找最小值，并记录位置，遍历完成后替换。（为空则退出）
bool delete_min(SqList &L) { int i; int Min,pos; if(L.length==0) return false; Min=L.data[0]; pos=0; for(i=1; i<L.length; i++) if(L.data[i]<Min) { Min=L.data[i]; pos=i; } L.data[pos]=L.data[L.length-1]; return true; }2.顺训表逆序
要求：高效和空间复杂度O(1)
思想：只遍历前一半，每次对调（奇偶问题大家应该都明白，不需要考虑）
void Reverse(SqList &L) { EleType temp; int i; for(i=0;i<L.length/2;i++) { //交换三部曲 temp=L.data[i]; L.data[i]=L.data[L.length-1-i]; L.data[L.length-i-1]=temp; } return ; }3.删除顺序表中所有特定值的元素
要求：时间复杂O(n)，空间复杂O(1)
思路：遍历搜索，由于时间复杂要求O(n)，所有查找过程中，每查到一个就添加到表中，由于空间复杂限制，无法新建表，只能再原表操作。
void delete_x(SqList &L,EleType x) { int k=0; int i; for(i=0;i<L.length;i++) { if(L.data[i]!=x) { L.data[k]=L.data[i]; k++; } } L.length=k; return; }4.删除有序表在s、t之间的所有数值,s<t
要求：如果s、t不合理或者顺序表为空，显示错误信息并推出。
思路：1.和第三题一起相结合考虑，只需要将特定元素k=x改为s>k或k>t以及前提条件即可。
2.因为是有序表，可以找到小于s的数值和t数值的位置，然后删除之间的数值即可。
思路1:
void delete_x(SqList &L,EleType s,EleType t) { int k=0; int i; if(L.length==0) printf("有序表为空"); if(s>t)//默认s=t为删除某个元素 printf("s、t不合法"); 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; }思路2:
void delete_x(SqList &L,EleType s,EleType t) { int i,j; if(L.length==0) printf("有序表为空"); if(s>t)//默认s=t为删除某个元素 printf("s、t不合法"); //寻找小于s的最大元素 for(i=0;i<L.length&&L.data[i]<s;i++); if(i>=L.length) return; //寻找大于t的最小元素 for(j=i;j<L.length&&L.data[j]<=t;j++); for(;j<L.length;j++,i++) L.data[i]=L.data[j]; L.length=i; return; }
5.和第四题几乎一样（不做重述！）
6.删除有序表中重复元素。
思路：这类题都是边删除边移动，可以继续采取记录非重复元素个数k，后续向前移动到第k个位置。
void delete_Same(SqList &L) { int k=1; int i; if(L.length==0) printf("有序表为空"); //默认第一个元素不重复 for(i=1;i<L.length;i++) { if(L.data[i]!=L.data[i-1]) { L.data[k]=L.data[i]; k++; } } L.length=k; return; }7.合并两个表
要求：用函数返回值返回新表
思路：建立新表，长度为两表之和，为0则之间返回；两两比较，小的存入新表，某一个表遍历完后，将另一个表直接存入新表
SqList delete_Merge(SqList &L1,SqList &L2) { SqList s; s.length=L1.length+L2.length; int i=0,j=0,k=0; if(s.length==0) return s; while(i<L1.length&&j<L2.length) { if(L1.data[i]<=L2.data[j]) { s.data[k++]=L1.data[i++]; } else { s.data[k++]=L2.data[j++]; } } while(i<L1.length) { s.data[k++]=L1.data[i++]; } while(j<L2.length) { s.data[k++]=L2.data[j++]; } return s; }8.理解为将一维数组前m和后n个元素对调或者理解为将线性表的前m和后n个元素对调
思路：数组全部逆置，前n个元素逆置，后m个元素逆置即可,写一个指定位置间排序，调用三次即可。
//逆序 void Reverse(SqList &L,int a,int b) { EleType temp; int i; for(i=0;i<(b-a+1)/2;i++) { //交换三部曲 temp=L.data[a-1+i]; L.data[a-1+i]=L.data[b-1-i]; L.data[b-1-i]=temp; } return ; } void Reverse_mn(SqList &L,int m,int n) { Reverse(L,1,m+n);//1,8 Reverse(L,1,n);//1,5（原本的后五个） Reverse(L,n+1,m+n);//6,8（原本的前三个） //测试：Reverse_mn(L,3,5); }9.有序表查找x，成功则与后一位数字交换位置；失败则插入x后依旧保持有序。
要求：最少时间。
思路：最少时间---->二分法，成功则交换三部曲，失败则执行插入。
void Search_x(SqList &L,EleType x) { int low=0,high=L.length-1; int mid; int temp,i; while(low<=high) { mid=(low+high)/2; if(L.data[mid]==x) break; else if(L.data[mid]<x) low=mid+1; else high=mid-1; } //找到了，且不是最后一个 if(L.data[mid]==x&&mid!=L.length-1) { //交换三部曲 temp=L.data[mid]; L.data[mid]=L.data[mid+1]; L.data[mid+1]=temp; } //查找失败,插入地方位于high后 if(low>high) { for(i=L.length-1;i>high;i--) L.data[i+1]=L.data[i]; L.data[i+1]=x; L.length++; } return ; }10.
(1).将表向左循环q个单位
(2).并给出注释，要求高效
(3).分析时间复杂度和空间复杂度
思路：与8相同原理，对1到q倒置，对q+1到n倒置，全部倒置即可。
//逆序 void Reverse(SqList &L,int a,int b) { EleType temp; int i; for(i=0;i<(b-a+1)/2;i++) { //交换三部曲 temp=L.data[a-1+i]; L.data[a-1+i]=L.data[b-1-i]; L.data[b-1-i]=temp; } return ; } void Reverse_mn(SqList &L,int p,int n) { Reverse(L,1,p);//前m倒置 Reverse(L,p+1,n);//m+1到n倒置 Reverse(L,1,n);//全部倒置 //测试：Reverse_mn(L,3,8); }时间复杂度：分别为O(p/2)、O((n-p)/2)、O(n/2)，根据加法规则，所以时间复杂度为O(n/2)。
空间复杂度：因为仅有交换时使用了一个辅助空间（共三次），为常数次，所以空间复杂度为O(1)。
11.
(1).求两个等长升序表的中位数
(2).并给出注释，要求高效
(3).分析时间复杂度和空间复杂度
思路：如果直接查找顺序查找时间复杂度为O(n)（n为升序表长度）。（不可取）
采取折半的方式，取两者中位数分别为a、b比较，规则如下：1.a=b算法结束；2.a<b，舍弃A较小部分和B较大部分；3.a>b，舍弃A较大部分和B较小部分；每次舍弃部分个数相同;重复执行，直到最后仅剩一个元素。（更优）
简单说如果a、b不相等，则中位数一定介于a、b之间。
int list_middle(SqList &L1,SqList &L2) { //表头表尾中位数 int first1=0,first2=0,end1=L1.length-1,end2=L2.length-1,mid1,mid2; while (first1!=end1||first2!=end2) { mid1=(first1+end1)/2; mid2=(first2+end2)/2; //条件1 if(L1.data[mid1]==L2.data[mid2]) return L1.data[mid1]; if(L1.data[mid1]<L2.data[mid2]) { //奇数,直接舍弃 if((first1+end1)%2==0) { first1=mid1; end2=mid2; } else { first1=mid1+1; end2=mid2; } } else { //奇数,直接舍弃 if((first1+end1)%2==0) { end1=mid1; first2=mid2; } else { first1=mid1; end2=mid2+1; } } } return L1.data[first1]>L2.data[first2]?L1.data[first1]:L2.data[first2]; }时间复杂度：O(log2n)
空间复杂度：O(1)
12.
(1).求表的众数
(2).并给出注释，要求高效
(3).分析时间复杂度和空间复杂度
思路：1.排序后查找（排序O(log2n)），判断存在还要遍历（或者有其他方法，我可能还没接触到）。
2.遍历过程中统计出现次数，如果是众数一定满足个数最多且>n/2。
int Majority(SqList &L) { //x用于存主元素,count用于记录当前主元素次数，如果存在中枢，则主元素最后一定是众数 int x=L.data[0],count=1; int i; for(i=1;i<L.length;i++) { if(L.data[i]==x) count++; else { if(count>0) count--; else x=L.data[i]; count=1; } } if(count>0) for(i=count=0;i<L.length;i++) if(L.data[i]==x) count++; if(count>(L.length+1)/2) return x; return -1; }时间复杂度：O(n)
空间复杂度：O(1)
12.
(1).求表中未出现的最小正整数
(2).并给出注释，要求时间高效
(3).分析时间复杂度和空间复杂度
思路：只要求时间高效，采取空间换时间的方法，开辟辅助空间，将表遍历一次，统计所以正整数出现的次数，最后将遍历记录表即可。
int findMin(SqList &L) { int i; int n=L.length; int b[n]; for(i=0;i<L.length;i++) { b[i]=0; } for(i=0;i<L.length;i++) { if(L.data[i]>0&&L.data[i]<L.length) b[L.data[i]-1]++; } for(i=0;i<L.length;i++) if(b[i]==0) break; return i+1; }时间复杂度：O(n)
时间复杂度：O(n)
