说在前面：链表章节（22题之前)多处用到了二级指针，有些地方可以选择使用一级指针也可
题目目录
已知线性表（a1,a2,……,an)按顺序结构存储且每个元素为不相等的整数。
设计把所有奇数移动到所有偶数前边的算法。
例如，A=（1，2，3，4，5，6，7），移动后变为 A=（1，7，3，5，4，6，2）
(要求时间最少，辅助空间最少)
对于顺序表，从前往后找偶数，与从后往前找到的奇数进行对调（在原线性表上操作，减少 辅助空间）
#include <stdio.h>
/*
* 已知线性表（a1,a2,……,an)按顺序结构存储且每个元素为不相等的整数。
* 设计把所有奇数移动到所有偶数前边的算法。
* 例如，A=（1，2，3，4，5，6，7），移动后变为 A=（1，7，3，5，4，6，2）
* (要求时间最少，辅助空间最少)
*/
void move(int *array, int length);
int main() {
int array[] = { 1, 2, 3, 4, 5, 6, 7 };
int length = sizeof(array) / sizeof(array[0]); //求出线性表的长度
printf("length=%d\n", length);
move(array,length);
for (int i = 0; i < length; i++) {
printf("%5d", array[i]);
}
return 0;
}
void move(int *array, int length) {
int i = 0; //指向线性表的第一个元素
//求出线性表的长度（这个地方错误是因为数组名作为函数参数传递后会退化为指针，所以sizeof()计算实质上是一个指针的大小
//int j = sizeof(array) / sizeof(array[0]);
int j = length - 1;
int temp; //临时中间变量
while (i <= j) {
while (array[i] % 2 == 1) { //从前往后找偶数，与后面的奇数进行交换
i++;
}
while (array[j] % 2 == 0) { //从后往前找奇数，与前面的偶数进行交换
j--;
}
if (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}本着考研监督自己每天写 >=1道C代码题，也在此做一个记录！
设计一个高效算法，将顺序表L中所有元素逆置，要求算法的空间复杂度为O(1)
利用两个“指针”分别从前往后、从后往前对顺序表进行扫描，一一对应对调即可（在原顺序表上操作，未增加辅助空间），空间复杂度为O(1)
#include <stdio.h>
void reverse(int* array, int length); //函数声明
int main() {
int array[] = { 10,65,5,6,3,9,8,12,26,31,30,23 };
int length = sizeof(array) / sizeof(array[0]);
printf("reverse之前顺序表L中的元素：\n");
for (int i = 0; i < length; i++) {
printf("%5d", array[i]);
}
reverse(array, length);
printf("\n==================\n");
printf("reverse之后顺序表L中的元素：\n");
for (int i = 0; i < length; i++) {
printf("%5d", array[i]);
}
return 0;
}
/*
* 设计一个高效算法，将顺序表L中所有元素逆置，要求算法的空间复杂度为O(1)
*/
void reverse(int *array, int length)
{
int temp;
for (int i = 0, j = length - 1; i < length / 2; i++, j--) { //将顺序表中的元素前后对调，只需对半对调即可
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}so easy!
将两个有序表合并为一个新的有序顺序表，并由函数返回结果顺序表。
首先安顺序分别从两个顺序表中去除较小的元素存入新表，再看看哪个表还有剩余，将剩余的再加到新的顺序表后面
#include <stdio.h>
//这里的顺序表采用数组
bool Merge(int* array01, int length01, int* array02, int length02, int* MergeArray, int length03); //函数声明
int main()
{
int array01[] = { 1,2,3,5,7,12 };
int array02[] = { 4,7,10,13,16,38 };
int MergeArray[20] = { 0 }; //将合并后的元素存入该数组中,的初始化否则会报错
int length01 = sizeof(array01) / sizeof(array01[0]);
int length02 = sizeof(array02) / sizeof(array02[0]); //分别求出两个有序顺序表的长度
int length03 = sizeof(MergeArray) / sizeof(MergeArray[0]);
printf("======合并前两个有序顺序表的元素分别为===============\n");
printf("array01: ");
for (int i = 0; i < length01; i++) {
printf("%5d", array01[i]);
}
printf("\narray02: ");
for (int i = 0; i < length02; i++) {
printf("%5d", array02[i]);
}
bool result = Merge(array01, length01, array02, length02, MergeArray,length03);
if (result) {
printf("\n\n======合并后两个有序顺序表的元素分别为===============\n");
for (int j = 0; j < (length01 + length02); j++) {
printf("%5d", MergeArray[j]);
}
}
else {
printf("\n\n合并失败！超出表长!!!\n");
}
return 0;
}
/*
* 题目描述：
* 将两个有序表合并为一个新的有序顺序表，并由函数返回结果顺序表。
*
* 算法思想：
* 首先安顺序分别从两个顺序表中去除较小的元素存入新表，再看看哪个表还有剩余，将剩余的再加到新的顺序表后面
*/
//在外部先用sizeof(arr)/sizeof(arr[0])求出数组长度，然后将他的长度作为一个参数传递进去
bool Merge(int* array01, int length01, int* array02, int length02,int *MergeArray,int length03) {
if ((length01 + length02) > length03) {
return false;
}
int i = 0;
int j = 0;
int k = 0;
while (i < length01 && j < length02) {
if (array01[i] < array02[j]) {
MergeArray[k++] = array01[i++];
}
else {
MergeArray[k++] = array02[j++];
}
}
while (i < length01) {
MergeArray[k++] = array01[i++];
}
while (j < length02) {
MergeArray[k++] = array02[j++];
}
length03 = k;
return true;
}没难度！
从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删除元素的值。空出的位置由最后一个元素填补
搜索整个顺序表，查找最小值元素并记录其位置和value，搜索结束后用最后一个元素填补空出的原最小值元素的位置
#include <stdio.h>
int Delete_Min(int* array, int length);//函数声明
int main()
{
int array[] = { 5,6,9,15,32,64,8,9,5,7,21,53,69,1,2,8,67 };
int length = sizeof(array) / sizeof(array[0]); //计算出顺序表的长度
printf("顺序表array的元素如下：\n");
for (int j = 0; j < length - 1; j++) {
printf("%5d", array[j]);
}
int MinValueofArray = Delete_Min(array, length);
printf("\n\n顺序表array中的具有最小值的元素为: %5d",MinValueofArray);
return 0;
}
/*
* 题目描述：
* 从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删除元素的值。空出的位置由最后一个元素填补
*
* 算法思想：搜索整个顺序表，查找最小值元素并记录其位置和value，搜索结束后用最后一个元素填补空出的原最小值元素的位置
*/
int Delete_Min(int* array, int length)
{
if (length == 0) {
return -1;
}
int position = 0;//用于记录最小值元素的位置
int MinValue = array[position];//假设第一个元素最小
for (int i = 0; i < length - 1; i++) {
if (array[i] < MinValue) {
MinValue = array[i]; //更新最小值
position = i;
}
}
array[position] = array[length - 1]; //用最后一个元素填补空出的原最小值元素的位置
length = length - 1;//更新顺序表的长度
return MinValue;
}没难度！！
给定一个有n个元素的整数数组b，其中的连续的想等元素构成的子序列称为平台，设计一个算法求出b中最长平台的长度
从头扫描数组，用mlen保存b中最长平台的长度（初始值为1），冷保存当前平台的长度（初始值为1），当mlen<len时更新mlen的值，最后返回mlen
#include <stdio.h>
int Maxlength(int array[], int length);//函数声明
int main()
{
int array[] = { 5,5,6,5,9,6,6,3,6,6,6,6,6,8,8,9,1,4,7,2,2,3 };
int length = sizeof(array) / sizeof(array[0]);//求出数组的长度
printf("array[]数组的元素为:\n");
for (int i = 0; i < length; i++) {
printf("%5d", array[i]);
}
int Maxlen = Maxlength(array, length);
printf("\n array[]数组中最长平台的长度为: %5d", Maxlen);
return 0;
}
/*
* 题目描述：
* 给定一个有n个元素的整数数组b，其中的连续的想等元素构成的子序列称为平台，设计一个算法求出b中最长平台的长度
* 算法思想：
* 从头扫描数组，用mlen保存b中最长平台的长度（初始值为1），冷保存当前平台的长度（初始值为1），当mlen<len时更新mlen的值，最后返回mlen
*/
int Maxlength(int array[], int length) //值传递
{
int mlen = 1; //记录最长平台的长度，初始化为1
int curlen = 1; //记录当前平台的长度
int start = 0; //记录平台的第一个元素的下标
for (int i = 0; i < length; i++) {
if (array[i] == array[start]) {
curlen++;
}
else {
if (curlen > mlen) {
mlen = curlen;
}
//无论curlen 和 mlen比较结果如何都要重设start，并重置curlen
start = i;
curlen = 1;//重置当前平台长度
}
}
return mlen;
}其实题目实质就是让你找出数组中连续元素相等的最长长度！
已知长度为n的线性表L才用顺序存储结构，编写一个时间复杂度为O(n),空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素
从头扫描顺序表，如果遇到非x元素则往前挪，相等则跳过，实质就是用非x元素来按序填补已删除的x元素。没有增加额外的辅助空间，空间复杂度为O(1)。
#include <stdio.h>
void del_x(int* array, int x, int* length);//函数声明
int main()
{
int array[] = { 32,61,15,54,9,54,35,63,78,96,54 };
int length = sizeof(array) / sizeof(array[0]);
printf("顺序表array中原有的元素为：\n");
for (int i = 0; i < length; i++) {
printf("%5d", array[i]);
}
printf("\n请输入要删除的元素:");
int x; //要删除的元素
scanf_s("%d", &x); //用户输入
del_x(array, x, &length);
printf("\n删除元素 %3d 后顺序表array中的元素为：\n", x);
for (int i = 0; i < length; i++) {
printf("%5d", array[i]);
}
return 0;
}
/*
* 题目描述：
* 已知长度为n的线性表L才用顺序存储结构，编写一个时间复杂度为O(n),空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素
* 算法思想：
* 从头扫描顺序表，如果遇到非x元素则往前挪，相等则跳过，实质就是用非x元素来按序填补已删除的x元素。
*/
void del_x(int* array, int x, int* length)
{
int len = 0; //记录顺序表中元素值不等x的个数，也就是删除x后顺表的长度
for (int i = 0; i < *length; i++) {
if (array[i] != x) {
array[len] = array[i]; //如果当前元素不等于要删除的元素，则往前挪，即非x的元素将x元素覆盖，在原顺序表上操作，未增加辅助空间
len++;
}
}
*length = len; //更新顺序表的长度
}要注意的是题目要求空间复杂度为O(1)，所以不能在额外空间来辅助，只能在原顺序表中操作。其实只需从前往后扫描顺序表，将元素一个一个挪，如果遇到了要删除的元素就不挪，用后面的非要求删除的元素覆盖即可!
设计一个算法，从一给定的顺序表L中删除元素值在x到y(x<=y)之间的所有元素，要求以较高的效率来实现，空间复杂度为O(1)
从头扫描顺序表，如果遇到不是在x-y之间的元素，则往前挪，是的话则跳过，实质就是用不在x-y之间的元素来按序填补已删除的x-y之间的元素。没有增加额外的辅助空间，空间复杂度为O(1)。
#include <stdio.h>
void del_xy(int* array, int x, int y, int* length);//函数声明
int main()
{
int array[] = { 32,61,15,54,9,54,35,63,78,96,54 };
int length = sizeof(array) / sizeof(array[0]);
printf("顺序表array中原有的元素为：\n");
for (int i = 0; i < length; i++) {
printf("%5d", array[i]);
}
printf("\n请输入要删除的元素:");
int x,y; //要删除的元素
scanf_s("%d %d", &x,&y); //用户输入
del_xy(array, x,y, &length);
printf("\n删除元素值在%3d -- %3d 之间的元素后顺序表array中的元素为：\n", x,y);
for (int i = 0; i < length; i++) {
printf("%5d", array[i]);
}
return 0;
}
/*
* 题目描述：
* 设计一个算法，从一给定的顺序表L中删除元素值在x到y(x<=y)之间的所有元素，要求以较高的效率来实现，空间复杂度为O(1)
* 算法思想：
* 从头扫描顺序表，如果遇到不是在x-y之间的元素，则往前挪，是的话则跳过，实质就是用不在x-y之间的元素来按序填补已删除的x-y之间的元素。没有增加额外的辅助空间，空间复杂度为O(1)。
*/
void del_xy(int* array, int x, int y, int* length) {
int len = 0;
for (int i = 0; i < *length; i++) {
if (array[i] <= x || array[i] >= y) {
array[len] = array[i];
len++;
}
}
*length = len;//更新数组的长度
}这个题和上一题（顺序表06）的思路一样，只是此题是要求删除一个范围类的元素，但两个题目的实质没有区别！
设将n(n>1)个整数存放在一维数组array中。试着设计一个在时间复杂度和空间复杂度都尽可能高效的算法，将array中保存的序列循环左移p(0<p<n)个位置，即将array中的数据由(x0,x1,……,x n-1)变换为（xp,xp+1,……,x0,x1,……,xp-1)。
【举栗：（3，6，7，8，5，2，1）】
1. 先将整个数组逆置 --> （1，2，5，8，7，6，3）
2. 将后p个数逆置 --> （1，2，5，8，3，6，7）
3. 将前n-p个数逆置 --> （8，5，2，1，3，6，7）
注：第二个步骤和第三个步骤先后顺序不影响最后结果
#include <stdio.h>
void LeftShift(int* array, int left, int right); //函数声明
void Reserve(int* array, int left, int right);
int main()
{
int array[] = { 13,26,69,85,98,27,31,45,63,29 };
int length = sizeof(array) / sizeof(array[0]);//求出数组的长度
printf("循环左移前数组中的元素位置为：\n");
for (int i = 0; i < length; i++) {
printf("%5d", array[i]);
}
LeftShift(array, 0, length - 1);
printf("\n循环左移p位后数组中的元素位置为：\n");
for (int i = 0; i < length; i++) {
printf("%5d", array[i]);
}
return 0;
}
/*
* (2010年统考真题）
* 题目描述：
* 设将n(n>1)个整数存放在一维数组array中。试着设计一个在时间复杂度和空间复杂度都尽可能高效的算法，将array中保存的序列循环左移p(0<p<n)个位置，
* 即将array中的数据由(x0,x1,……,x n-1)变换为（xp,xp+1,……,x0,x1,……,xp-1)。
*
* 举栗：（3，6，7，8，5，2，1） 循环左移3位
*
* 算法思想：
* 1. 先将整个数组逆置 --> （1，2，5，8，7，6，3）
* 2. 将后p个数逆置 --> （1，2，5，8，3，6，7）
* 3. 将前n-p个数逆置 --> （8，5，2，1，3，6，7）
* 注：第二个步骤和第三个步骤先后顺序不影响最后结果
*
* 实质：循环左移p位，也就是将数组中的前p个数按原有顺序挪到数组的后p个位置去，所以我们可以先全部逆置，然后再分别逆置回来即可
*/
//循环左移
void LeftShift(int* array, int left, int right) {
int p;
printf("\n请输入循环左移多少p位:");
scanf_s("%d", &p);
if(p > 0 && p < right + 1) {
Reserve(array, left, right); //逆置整个数组 （对应步骤 1）
Reserve(array, left, right - p); //逆置数组后p个元素 （对应步骤 2）
Reserve(array, right - p + 1, right); //逆置数组前n-p个元素 （对应步骤 3）
}
}
//逆置数组
void Reserve(int* array, int left, int right){
int tmp;
while (left < right) {
tmp = array[left];
array[left] = array[right];
array[right] = tmp;
left++;
right--;
}
}1. 算法时间复杂度为O(n) ( O(p)+O(n-p)+O(n) );
2. 算法空间复杂度为O(1) （在原数组上操作未增加辅助空间，LeftShift()定义几个变量不影响）；
3. 算法思路简单明了挺好理解的。
（呜呜呜！