王道课后题之线性表
1.搜索顺序表，查找最小值元素，用最后的元素代替它
2.顺训表逆序
3.删除顺序表中所有特定值的元素
4.删除有序表在s、t之间的所有数值,s
思路：先找到最小值，再替换
bool DelMin(sqlList &L,Elemtype &value){
if(L.length == 0)return false;
int min = L.data[0];
int index = 0;
for(int i=1; i<L.length; i++){
if(L.data[i] < min){
min = L.data[i];
index = i;
}
}
L.data[index] = L.data[L.length-1];
L.length--;
return true;
}
2.顺训表逆序
思路：二分法前后调换
void Rever(sqlList &L){
int i=0;
int j=L.length-1;
for(int i=0; i<L.length/2; i++){
int t = L.data[i];
L.data[i] = L.data[j];
L.data[j] = t;
}
}
3.删除顺序表中所有特定值的元素
要求：时间复杂O(n)，空间复杂O(1)
思路：在原数组上操作
void DelX(sqlList &L,int x){
int k=0;
for(int i=0; i<L.length; i++){
if(L.data[i] != x){
L.data[k] = L.data[i]; //相当于数组只存储除了x以为的数字，忽略x
k++; //新的长度递增
}
L.length = k;
}
}
4.删除有序表在s、t之间的所有数值,s<t
思路：找到两边的边界，然后前移
voide Del_S_T(sqlList &L,int s,int t){
if(s>=t || L.length==0)return false;
int i,j;
for(int i=0; i<L.length && L.data<s; i++){ //找到第一个大于等于S的值
if(i > L.length)return false;
}
for(int j=0; j<L.length && L.data<=t; j++){ //找到第一个大于t的值
if(j > L.length)return false;
}
for(; j<L.length; j++,i++){
L.data[i] = L.data[j]; //将s到t的数值进行覆盖(前移)
}
L.length = i; //当前i的值就是数组的长度
}
5.在顺序表中删除给定值s到t之间左右元素
思路和第四题类似，但是注意这个没有说有序哦！
voide Del_S_T(sqlList &L,int s,int t){
int k=0; //用于记录s到t中的元素的个数
for(int i=0; i<L.length; i++){
if(L.data[i]>=s && L.data[i]<=t){
k++; //说明在这个范围内
}else{
L.data[i-k] = L.data[i]; //当前元素移动K个位置
}
L.length -= k; //除去s-t之间的元素，就是删除后的数组长度
}
}
6.删除有序表中重复元素。
维护不重复序列，将不重复的数字查到序列后方
voide Del_S_T(sqlList &L,int s,int t){
for(int i=0,j=1; j<L.length; j++){
if(L.data[i] != L.data[j]){
L.data[++i] = L.data[j];
}
L.length = i+1;
}
}
7.合并两个表
思路：谁小先存谁
sqlList Del_S_T(sqlList a,sqlList b,sqlList &c){
int i=0,j=0,k=0; //分别为a b c当前的下表
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 c;
}
8.将一维数组前m和后n个元素对调
思路：先整体对调，再分别对小部分进行对调
//1 2 3 4 5 6 7 8
//8 7 6 5 4 3 2 1
//5 6 7 8 1 2 3 4
void Rever(SqList &L,int a,int b){
int t;
for(int i=0; i<(b-a+1)/2; i++){
t = L.data[a-1+i];
L.data[a-1+i] = L.data[b-1-i];
L.data[b-1-i] = t
}
}
void ans(SqList &L,int m,int n){
Rever(L,1,m+n); //换句话说 就是将AB求逆
Rever(L,1,n); //将A单独求逆
Rever(L,n+1,m+n); //将B单独求逆
}
9.有序表查找x，成功则与后一位数字交换位置；失败则插入x后依旧保持有序。
要求：最少时间。
思路：折半查找，找到则交换，找不到则插入x
void SerExcIns(int a[],int 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){ //查找成功并且不在最后
int t = a[mid];
a[mid] = a[mid+1];
a[mid+1] = t;
}
if(low > high){ //查找失败
for(int i=n-1; i>high; i--){
a[i+1] = a[i]; //一直后移
}
a[i+1] = x; //插入x
}
}
10.将表向左循环q个单位
思路：与第八题相同
void Rever(SqList &L,int a,int b){
int t;
for(int i=0; i<(b-a+1)/2; i++){
t = L.data[a-1+i];
L.data[a-1+i] = L.data[b-1-i];
L.data[b-1-i] = t
}
}
void ans(SqList &L,int s,int w){
Rever(L,1,s); //将 前s个求逆
Rever(L,s+1,w); //将 前s+1到w求逆
Rever(L,1,w); //将 全部求逆
}
11.求两个等长升序表的中位数
要求 时间和空间高效
二路归并，依次遍历找小的元素，找到索引为一个序列长度的时候，那么此时就是中位数
int SearBiNum(int a[],int b[],int len){
int i=0,j=0,index=0;
while(i<len && j<len){
index++; //index表示当前遍历的元素下标
if(a[i] < b[j]){
i++; //第一个序列往前走
if(index == len){ //下标到了一个序列的长度那么此索引对应的元素必为中位数
return a[i-1];
}
}else{
j++; //第二个序列往前走
if(index == len){
return b[j-1];
}
}
}
}
12.求表的众数(找出一个元素大于数组长度的一半)
思路：另外开辟一个新的数组，出现过的数字进行标记
int SearMain(int a[]){
int ans[a.length];
memset(ans, 0, sizeof(ans)); //默认都是0
for(int i=0; i<a.length; i++){
ans[a[i]]++; //用数组标记出现过的元素，在目标数组进行标记
}
for(int i=0; i<ans.length; i++){
if(ans[i] > a.length/2)return i; //返回下标就是主元素
}
return -1; //上面循环如果没有返回，则返回-1
}
13.求表中未出现的最小正整数
思路：仍然使用数组标记，出现的数字置为1，再重新遍历新的数组
int FindLost(int a[],int n){
int ans[n];
memset(ans, 0, sizeof(ans)); //默认都是0
for(int i=0; i<n; i++){
if(a[i]>0 && a[i]<=n){
ans[a[i]-1] = 1; //若 A[i］的值介于1～n,则标记数组置为1
}
}
for(int i=0; i<n; i++){
if(ans[i] == 0) break; //没出现过
}
return i+1; //返回数组下标+1就是未出现的值
}
线性表完美撒花