//问题一:删除最小元素,并用最后一个元素填补 bool delMin(SqList &L,elemType &val){ if(L.length==0){ printf("顺序表为空!\n"); 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; }