//问题一：删除最小元素，并用最后一个元素填补
bool delMin(SqList &L,elemType &val){
if(L.length==0){
printf("顺序表为空!
");
return ERROR;
}
elemType min = L.elems[0];
int index = 0;
for(int i=1;i<L.length;i++){
if(L.elems[i]<min){
min=L.elems[i];
index=i;
}
}
val=L.elems[index];
L.elems[index]=L.elems[--L.length];
return OK;
}
//问题二：逆置元素
void reverse(SqList &L){
int i=0,j=L.length-1;
int t;
while(i<j){
t=L.elems[i];
L.elems[i]=L.elems[j];
L.elems[j]=t;
i++;
j--;
}
}
//问题三：删除所有值为x的数据元素
void delX(SqList &L,elemType x){
int k=0;
for(int i=0;i<L.length;i++){
if(L.elems[i]!=x){
L.elems[k++]=L.elems[i];
}
}
}
//方法二
void delX2(SqList &L,elemType x){
int l=0,r=L.length-1;
while(l<r){
while(l<r&&L.elems[l]!=x)
l++;
while(r>l&&L.elems[r]==x){
r--;
L.length--;
}
if(l<r){
L.elems[l]=L.elems[r];
r--;
L.length--;
}
}
}
//问题四：从有序顺序表中删除值在t-s之间的所有元素
bool delBetween(SqList &L,int t,int s){
if(L.length==0||t>s)
return ERROR; //错误
int i=0;
int d; //元素的值
int st=-1; //在范围内的开始元素的索引值
int k=0; //在范围内的元素的个数
for(i;i<L.length;i++){
d=L.elems[i];
if(d>=t&&d<=s){
if(st==-1)
st=i;
k++;
}
if(d>s)break; //因为是有序的，后面都不在范围内
}
if(k){ //如果有在范围内的
for(int j=st+k;j<L.length;j++){ //向前移K个位置
L.elems[j-k]=L.elems[j];
}
L.length-=k;
}
return OK;
}
//问题五：从顺序表（无序）中删除值在t-s之间的所有元素
bool delBetween2(SqList &L,int t,int s){
if(L.length==0||t>s)
return ERROR; //错误
int k=0;
int v;
for(int i=0;i<L.length;i++){
v=L.elems[i];
if(v<t||v>s){
L.elems[k]=v;
k++;
}
}
L.length=k;
return OK;
}
//问题六：从有序顺序表中删除值重复的元素
void delRepeat(SqList &L){
int k=0;
int len = L.length;
for(int i=1;i<len;i++){
if(L.elems[k]!=L.elems[i]){
L.elems[++k]=L.elems[i];
}
}
L.length = k+1;
}
/*问题七： 数组中存放着两个顺序表 (a1a2a3...am b1b2b3...bn),
交换他们的位置变为(b1b2b3...bn a1a2a3...am)
*/
void reverse(SqList &L,int st,int end){ //翻转位置st到end的元素
int t;
while(st<end){
t=L.elems[st];
L.elems[st]=L.elems[end];
L.elems[end]=t;
st++;
end--;
}
}
void exchange(SqList &L,SqList &A,SqList &B){
int la=A.length;
int lb=B.length;
reverse(L,0,la-1);
reverse(L,la,la+lb-1);
reverse(L,0,la+lb-1);
}
//问题九：有序顺序表，查找值为X的元素，若找到将他与后继元素交换，未找到则将其插入并仍然有序
void findX(SqList &L,int x){
int index = 0;
int i=0;
for(i;i<L.length;i++){
if(L.elems[i]==x){ //找到了x
if(i!=L.length-1){ //不是最后一个则有后继元素
int t=L.elems[i];
L.elems[i]=L.elems[i+1];
L.elems[i+1]=t;
return;
}
}else if(L.elems[i]>x){
index=i; //未找到，index为插入位置
break;
}
}
for(i=L.length;i>index;i--){
L.elems[i]=L.elems[i-1];
}
L.elems[index]=x;
L.length++;
}
//问题十：将一维数组A中的元素循环左移p个位置
void reverse(int a[],int st,int end){ //翻转位置st到end的元素
int t;
while(st<end){
t=a[st];
a[st]=a[end];
a[end]=t;
st++;
end--;
}
}
void moveP(int A[],int len,int p){
//思路与问题七类似，现将前p个翻转，并把剩余的翻转，最后全部翻转
reverse(A,0,p-1);
reverse(A,p,len-1);
reverse(A,0,len-1);
}
//问题十一：求两个上升序列合并后的中位数
float searchMid(int a[],int b[],int n){
int l1=0,m1,r1=n-1,l2=0,m2,r2=n-1; //分别表示数组a、b的开始、中间、结束位置
while(l1!=r1||l2!=r2){
m1=(l1+r1)/2;
m2=(l2+r2)/2;
if(a[m1]==b[m2])
return a[m1]*1.0;
else if(a[m1]<b[m2]){
if((l1+r1)%2==0){//奇数个
l1=m1; //舍弃a中间点以前的并保留中间点
r2=m2; //舍弃b中间点之后的并保留中间点
}else{
l1=m1+1; //舍弃a中间点之前的包括中间点
r2=m2; //舍弃b中间点之前的包括中间点
}
}else{
if((l1+r1)%2==0){//奇数个
r1=m1; //舍弃a中间点以后的并保留中间点
l2=m2; //舍弃b中间点之前的并保留中间点
}else{
r1=m1; //舍弃a中间点之后的包括中间点
l2=m2+1; //舍弃b中间点之前的包括中间点
}
}
}
return (a[l1]+b[l2])/2.0;
}
//问题十二：查找数组中是否有出现次数超过一半的元素，有则返回
bool check(int a[],int len,int c){
int cnt=0;
for(int i=0;i<len;i++){
if(a[i]==c)
cnt++;
}
return cnt>len/2;
}
int majority(int a[],int len){
int c=a[0];
int cnt=1;
for(int i=0;i<len;i++){
if(a[i]==c)
cnt++;
else{
if(cnt>0)
cnt--;
else{
c=a[i];
cnt=1;
}
}
}
if(cnt)
return check(a,len,c)?c:0;
else
return 0;
}
//方法二：快速排序的思路
int majority2(int a[],int len){
int temp=a[0];
int i=0;
int j=len-1;
while(i<j)
{
while(i<j && a[j]>=temp)
j--;
if(i<j)
a[i]=a[j];
while(i<j && a[i]<=temp)
i++;
if(i<j)
a[j]=a[i];
}
a[i]=temp;
return check(a,len,a[len/2])?a[len/2]:0;
}