做设计转钱网站,中企动力企业邮箱登陆首页,网站开发哪些,游戏网页链接试题1#xff08;王道8.3.3节综合练习2#xff09;#xff1a;
编写双向冒泡排序算法#xff0c;在正反两个方向交替扫描。即第一趟把关键字最大的元素放在序列的最后面#xff0c;第二趟把关键字最小的元素放在序列最前面#xff0c;如此反复。
首先实现冒泡排序…试题1王道8.3.3节综合练习2
编写双向冒泡排序算法在正反两个方向交替扫描。即第一趟把关键字最大的元素放在序列的最后面第二趟把关键字最小的元素放在序列最前面如此反复。
首先实现冒泡排序
#includestdio.h
#includestdlib.h
#includestring.h#define ElemType intvoid BubbleSort(ElemType a[],int n){int x;bool flag false;for (int i 0; i n;i){flag false;for (int j n - 1; j i;j--){if(a[j-1] a[j]){x a[j - 1];a[j - 1] a[j];a[j] x;flag true;}}if (flag false)return;}
}int main(){int a[7] {4, 3, 2, 7, 6, 8, 9};BubbleSort(a, 7);for (int i 0; i 7;i){printf(%d , a[i]);}
}
输出
2 3 4 6 7 8 9
然后实现所谓的双向把i%2这个条件加上去即可
#includestdio.h
#includestdlib.h
#includestring.h#define ElemType intvoid BubbleSort(ElemType a[],int n){int x;bool flag false;for (int i 0; i n;i){if(i % 2 0){for (int j 0; j n - 1 - i; j){if(a[j] a[j1]){x a[j 1];a[j 1] a[j];a[j] x;flag true;}}if (flag false)return;}else{for (int j n - 1; j i;j--){if(a[j-1] a[j]){x a[j - 1];a[j - 1] a[j];a[j] x;flag true;}}if (flag false)return;}}
}int main(){int a[7] {4, 3, 2, 9, 8, 7, 6};BubbleSort(a, 7);for (int i 0; i 7;i){printf(%d , a[i]);}
}
试题2王道8.3.3节综合练习3
已知线性表按顺序存储且每个元素都是不相同的整数类型元素设计把所有奇数移动到所有偶数前边的算法要求时间最少辅助空间最少。
本题可使用类似快排的思想
#define ElemType int
void oddbeforeeven(ElemType a[],int n){int low 0;int high n - 1;int change;while(low high){while(a[low] % 2 ! 0){ //前面是奇数low low 1;}while(a[high] % 2 0){ //后面是偶数high high - 1;}change a[high];a[high] a[low];a[low] change;low low 1; //注意后面必须在移动一下指针high high - 1;}
}int main(){int a[7] {4, 3, 2, 9, 8, 7, 6};oddbeforeeven(a, 7);for (int i 0; i 7;i){printf(%d , a[i]);}
}输出
7 3 9 2 8 4 6
试题3王道8.3.3节综合练习5
试编写一个算法在数组中找到第k小的元素。
此题可参考王道第七章的二叉排序树的练习王道7.3.4节综合练习11
【试题再现】编写一个递归算法在一棵具有n个结点的二叉排序树上查找第k小的元素并返回该结点的指针。要求算法的平均时间复杂度是二叉排序树每个结点中除了data,lchild,rchild外增设一个count成员保存以该结点为根的子树的结点个数。
我们首先实现一下快速排序
#includestdio.h
#includestdlib.h
#includestring.h#define ElemType int
int Partition(ElemType a[],int low,int high){ElemType pivot a[low];while(low high){while(lowhigha[high]pivot)high high - 1;a[low] a[high];while(lowhigha[low]pivot)low low 1;a[high] a[low];}a[low] pivot;return low;
}
void QuickSort(ElemType a[],int low,int high){if(lowhigh){int pivotpos Partition(a, low, high);QuickSort(a, low, pivotpos - 1);QuickSort(a, pivotpos 1, high);}
}int main(){int a[7] {4, 3, 2, 9, 8, 7, 6};QuickSort(a, 0, 6);for (int i 0; i 7;i){printf(%d , a[i]);}
}当快速排序结果出来后依次输出可以直接得到答案。这里也可以递归
#define ElemType int
int Partition(ElemType a[],int low,int high){ElemType pivot a[low];while(low high){while(low high a[high] pivot)high high - 1;a[low] a[high];while(low high a[low] pivot)low low 1;a[high] a[low];}a[low] pivot;return low; //返回pivot的下标
}int QuickSortk(ElemType a[],int low,int high,int k){int pivotpos Partition(a, low, high);if(pivotpos k-1){printf(%d\n, a[pivotpos]);return a[pivotpos];}else if(pivotpos k-1){return QuickSortk(a, low, pivotpos - 1, k);}else{return QuickSortk(a, pivotpos 1, high, k);}
}int main(){int a[10] {4, 3, 2, 9, 8, 7, 6, 10, 14, 17};QuickSortk(a, 0, 9, 6);for (int i 0; i 10;i){printf(%d , a[i]);}
}
输出
8
2 3 4 6 7 8 9 10 14 17
试题4王道8.3.3节综合练习6
荷兰国旗问题。
分类讨论这题可能不是那么好想一点点调吧...
#includestdio.h
#includestdlib.h
#includestring.h#define ElemType int
int NetherlandsFlag(ElemType a[],int n){int red -1;int blue n;int x;for (int i 0; i n;i){if(i blue){if(a[i] 0){ //i之前全部是红或白x a[i];a[i] a[red 1];a[red 1] x;red red 1;}else if(a[i] 2){while(a[blue - 1] 2){blue blue - 1;}if(i blue){x a[i];a[i] a[blue - 1];a[blue - 1] x;blue blue - 1;if(a[i] 0){ //红色的交换到前面x a[i];a[i] a[red 1];a[red 1] x;red red 1;}}}}elsebreak;}
}int main(){int a[11] {2, 1, 0, 0, 2, 1, 1, 0, 0, 2, 1}; // 0,1,2代表红白蓝NetherlandsFlag(a, 11);for (int i 0; i 11;i){printf(%d , a[i]);}
}
输出
0 0 0 0 1 1 1 1 2 2 2
试题5王道8.3.3节综合练习7 解答把试题3的代码参数k换成即可。
试题6王道8.6.3节综合练习2
设顺序表用数组A[ ]表示表中元素存储在数组下标1到mn范围内前m个元素递增有序后n个元素也递增有序设计算法使得整个顺序表有序。
可以看成直接插入排序进行了m轮然后在进行n轮直接插入排序
#define ElemType int
int Sort(ElemType a[],int m,int n){int i,k;for (int i m 1; i m n;i){a[0] a[i]; //复制到a[0]for (k i - 1; a[k] a[0]; k--){ // 移动a[k 1] a[k];}a[k 1] a[0];}
}int main(){int a[9] {0,2,4,5,7,3,5,9,11}; Sort(a, 4, 4);for (int i 1; i 8;i){printf(%d , a[i]);}
}
输出
2 3 4 5 5 7 9 11
试题7王道8.6.3节综合练习3
有一种简单的排序算法叫做计数排序。这种排序算法对一个待排序的表进行排序并将排序结果存放在另一个新的表中。必须注意的是表中所有待排序的关键字互不相同。计数排序算法针对表中的每一个记录遍历待排序的表一遍统计表中有多少个记录的关键字比该记录的关键字小。假如针对某一个记录统计出计数值为c那么这个记录在新的有序表中合适的存放位置即为c。设计实现计数排序的算法。
#define ElemType int
int Sort(ElemType a[],ElemType b[]){int count 0;for (int i 0; i 10;i){count 0;for (int j 0; j 10;j){if(a[j]a[i])count;}b[count] a[i];}
}int main(){int a[10] {0,4,3,2,6,9,8,11,32,21}; int b[10];Sort(a, b);for (int i 0; i 9;i){printf(%d , b[i]);}
}
试题8王道8.6.3节综合练习4
设有一个数组的存放一个无序关键序列现在要求把最后一个元素放在将元素排序后的正确位置上试编写实现该功能的算法要求比较关键字的次数不超过n。
可以用上题的思路也可借助快速排序。
