南通专业网站建设公司,加盟网官方网站,wordpress 子菜单,广告优化师工作内容顺序表 顺序表递增有序#xff0c;插入元素x#xff0c;仍递增有序用顺序表最后一个元素覆盖整个顺序表中最小元素#xff0c;并返回该最小元素将顺序表的元素逆置将a1,a2,a3……am b1,b2,b3……bn转换成b1,b2,b3……bn a1,a2,a3……am删除顺序表中所有值为x的元素从顺序表中… 顺序表 顺序表递增有序插入元素x仍递增有序用顺序表最后一个元素覆盖整个顺序表中最小元素并返回该最小元素将顺序表的元素逆置将a1,a2,a3……am b1,b2,b3……bn转换成b1,b2,b3……bn a1,a2,a3……am删除顺序表中所有值为x的元素从顺序表中删除给定值再s到t之间(包括s和t)的所有元素删除有序表中所有值重复的元素删除有序表中所有值重复的元素将两个递增有序表 合并为 一个递增有序表求两个递增序列的中位数设计一个时间上尽可能高效的算法,找出数组中未出现的最小正整数若一个整数序列中有过半相同元素则称其为主元素设计算法找出数组A(a0,a1……an - 1)的主元素。(其中0 ai n)若存在主元素则输出否则返回 - 1 顺序表递增有序插入元素x仍递增有序
#include iostream
using namespace std;
#define maxsize 100
typedef struct
{int data[maxsize];int length;
} Sqlist;/*顺序表递增有序插入元素x仍递增有序2 5 8 11 19 此时插入一个9 插入的9插入的是原来10的数组下标2 5 8 9 11 191、找位置 i2、元素右移*//*1 3 5 7 9 9 7 5 3 1 2 4 6 8 8 6 4 2
*/
int find(Sqlist L, int x)//参数为:传入顺序表 和 要插入的那个数字
{int i 0; //要声明一下 不然for循环的局部变量会被释放掉//for (; i L.length; i)//{// if (x L.data[i])// break;//}//return i;for (int i 0; i L.length; i){if (L.data[i]x){continue;}else{return i;}}}void insert(Sqlist L, int x)//元素后移操作 这里需要加入引用符号 参数为:顺序表 和 插入的位置
{int j, p;//定义两个变量 p为记录找到的插入的位置 j的初值为顺序表末尾的数的下标p find(L, x);for (j L.length - 1; j p; --j)//从插入的位置开始(包括插入前的位置)依次往后进行移动{L.data[j 1] L.data[j];}L.data[p] x;//插入数据(L.length); //更新顺序表的长度
}void insert23(Sqlist L, int x)
{int pos L.data[0];for (int i 0; i L.length - 1; i){if (L.data[i] x) {pos i;}}pos 1;for (int j L.length-1; j pos; j--){L.data[j 1] L.data[j];}L.data[pos] x;L.length;
}void insert233(Sqlist L, int x)
{int i;for (i 0; i L.length - 1; i){if (L.data[i]x){break;//break掉的值就是第一个不满足的值}}cout i i;cout endl;for (int j L.length - 1; j i; j--){L.data[j 1] L.data[j];}L.data[i] x;L.length;
}int main01()
{Sqlist L { {1, 3, 5, 8, 9}, 5 };//定义了一个顺序表 和 5这个数 这个数代表着长度insert233(L, 6);for (int j 0; j L.length; j){cout L.data[j] endl;}cout endl;cout L.length;return EXIT_SUCCESS;
}用顺序表最后一个元素覆盖整个顺序表中最小元素并返回该最小元素
#include iostream
using namespace std;
#define maxsize 100
typedef struct
{int data[maxsize];int length;
} Sqlist;/*用顺序表最后一个元素覆盖整个顺序表中最小元素并返回该最小元素1、找最小元素的位置2、用最后一个元素覆盖掉最小元素5 13 3 7 105 13 10 7
*/int Del_Min(Sqlist L)
{int min L.data[0];//初始化最小值int pos 0;//初始化记录位置的值for (int i 0; i L.length; i){if (L.data[i] min){min L.data[i];pos i;}L.data[pos] L.data[L.length - 1];L.length--;}return min;
}int main02()
{Sqlist L { {5,13,3,7,10}, 5 };int min Del_Min(L);for (int j 0; j L.length; j){cout L.data[j] endl;}cout endl;cout min endl;return EXIT_SUCCESS;
}将顺序表的元素逆置
#include iostream
using namespace std;
#define maxsize 100
typedef struct
{int data[maxsize];int length;
} Sqlist;
/*将顺序表的元素逆置4 7 16 3 99 3 16 7 44 7 16 3 9 11 9 3 16 7 4
*/
void Reverse(Sqlist L)
{int temp, i 0, j L.length - 1;int mid (i j) / 2;//int temp;while (i mid j mid){temp L.data[i];L.data[i] L.data[j];L.data[j] temp;i;j--;}//for (int i 0, j L.length - 1; i L.length / 2 j L.length / 2; i, --j)//{// temp L.data[i];// L.data[i] L.data[j];// L.data[j] temp;//}
}int main03()
{Sqlist L { {4,7,16,3,9,1}, 6 };Reverse(L);for (int j 0; j L.length; j){cout L.data[j] endl;}return EXIT_SUCCESS;
}将a1,a2,a3……am b1,b2,b3……bn转换成b1,b2,b3……bn a1,a2,a3……am
#include iostream
using namespace std;
/*将a1,a2,a3……am b1,b2,b3……bn转换成b1,b2,b3……bn a1,a2,a3……am1、将左边的一组逆置 am……a3,a2,a12、将右边的一组逆置 bm……b3,b2,b13、将a1到bn所有的元素逆置 bm……b3,b2,b1 am……a3,a2,a11 2 3 4 5 6 7 8 9 103 2 1 4 5 6 7 8 9 103 2 1 10 9 8 7 6 5 4 4 5 6 7 8 9 10 1 2 3
*/
void Reverse(int A[], int m, int n)
{int mid (m n) / 2;for (int i m, j n; i mid; i, --j){int temp A[i];A[i] A[j];A[j] temp;}
}void change(int A[], int m, int n)
{Reverse(A, 0, m - 1);//起始位置为0 中止位置为m-1Reverse(A, m, m n - 1);//左半边的初始位置为m 末端为mn-1Reverse(A, 0, m n - 1);//右半边的初始位置为0 末端为mn-1
}int main04()
{int A[10] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };change(A, 3, 7);//参数为 数组名 左边元素的个数 右边元素的个数for (int i 0; i 10; i){cout A[i] ;}return EXIT_SUCCESS;
}删除顺序表中所有值为x的元素
#include iostream
using namespace std;
#define maxsize 100
typedef struct
{int data[maxsize];int length;
} Sqlist;/*删除顺序表中所有值为x的元素可以把这题理解为保留所有不为x的元素12 3 5 8 9 312 5 8 9 3 3 没更新length前12 5 8 9 更新length之后
*/
void del(Sqlist L, int x)//删除顺序表中所有值为x的元素
{int k 0;//这里的k是用来记录顺序表中所有值不为x的元素的个数for (int i 0; i L.length - 1; i){if (L.data[i] ! x){L.data[k] L.data[i];//覆盖操作 k和i的初始值都是0k;}}L.length k;//更新length 保留了所有不为x的元素 相当于删除了值为x的元素
}void Del(Sqlist L, int x)
{int k 0;//这里的k是用来记录顺序表中所有值为x的元素的个数for (int i 0; i L.length - 1; i){if (L.data[i] x)k;elseL.data[i - k] L.data[i];}L.length L.length - k;
}int main05()
{Sqlist L { {12, 3, 5, 8, 9, 3}, 6 };del(L, 3);for (int j 0; j L.length; j)cout L.data[j] endl;return EXIT_SUCCESS;
}从顺序表中删除给定值再s到t之间(包括s和t)的所有元素
#include iostream
using namespace std;
#define maxsize 100
typedef struct
{int data[maxsize];int length;
} Sqlist;/*从顺序表中删除给定值再s到t之间(包括s和t)的所有元素12 13 14 18 19 1712 19 删除13~18
*/bool del(Sqlist L, int s, int t)
{int k 0;//k是用来记数的if (L.length 0 || s t)//错误的情况直接排除return false;for (int i 0; i L.length; i){if (L.data[i] s L.data[i] t)k;elseL.data[i - k] L.data[i];}L.length - k;//更新lengthreturn true;
}int main06()
{Sqlist L { {12, 13, 15, 18, 19}, 5 };del(L, 13, 19);for (int j 0; j L.length; j)cout L.data[j] endl;return EXIT_SUCCESS;
}删除有序表中所有值重复的元素
#include iostream
using namespace std;
#define maxsize 100
typedef struct
{int data[maxsize];int length;
} Sqlist;
/*删除有序表中所有值重复的元素可以理解为保留第一个重复的元素5 5 6 7 7 95 6 7 9
*/
bool del(Sqlist L)
{int i, j;for (i 0, j 1; j L.length; j)//j负责遍历整个顺序表 不满足下面的if循环时 j{if (L.data[i] ! L.data[j]){L.data[i] L.data[j];//满足if循环ij}else{continue;}}L.length i 1;return true;
}int main07()
{Sqlist L { {12, 13, 13, 13, 19}, 5 };del(L);for (int j 0; j L.length; j)cout L.data[j] endl;return EXIT_SUCCESS;
}删除有序表中所有值重复的元素 #include iostream
using namespace std;
#define maxsize 100
typedef struct
{int data[maxsize];int length;
} Sqlist;
/*删除有序表中所有值重复的元素可以理解为保留第一个重复的元素5 5 6 7 7 95 6 7 9
*/
bool del(Sqlist L)
{int i, j;for (i 0, j 1; j L.length; j)//j负责遍历整个顺序表 不满足下面的if循环时 j{if (L.data[i] ! L.data[j]){L.data[i] L.data[j];//满足if循环ij}else{continue;}}L.length i 1;return true;
}int main07()
{Sqlist L { {12, 13, 13, 13, 19}, 5 };del(L);for (int j 0; j L.length; j)cout L.data[j] endl;return EXIT_SUCCESS;
}将两个递增有序表 合并为 一个递增有序表
#include iostream
using namespace std;
#define maxsize 100
typedef struct
{int data[maxsize];int length;
} Sqlist;/*将两个递增有序表 合并为 一个递增有序表3 7 10 18 254 9 133 4 7 9 10 13 18 25
*/bool merge(Sqlist A, Sqlist B, Sqlist C)
{int i 0, j 0, k 0;while (i A.length j B.length){if (A.data[i] B.data[j])C.data[k] A.data[i];elseC.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 true;
}int main08()
{Sqlist A { {2, 5, 9, 13, 19}, 5 };Sqlist B { {1, 6, 7, 10}, 4 };Sqlist C;merge(A, B, C);for (int j 0; j C.length; j)cout C.data[j] endl;return EXIT_SUCCESS;
}求两个递增序列的中位数
#include iostream
using namespace std;
#define maxsize 100
typedef struct
{int data[maxsize];int length;
} Sqlist;/*求两个递增序列的中位数3 5 7 104 9 15 203 4 5 7 9 10 15 20 81、先合并这个两个递增序列2、求其中位数 3、若该递增序列为奇数 则返回最中间的即可 4、若该递增序列为偶数 则返回中间的左右两边的算数平均数
*/
int Find(Sqlist A, Sqlist B)
{int i, j, k;i j k 0;Sqlist C;while (i A.length j B.length)if (A.data[i] B.data[j])C.data[k] A.data[i];elseC.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];if (C.length % 2 ! 0){return C.data[(A.length B.length - 1) / 2];}if (C.length % 2 0){return (C.data[(A.length B.length - 1) / 2] C.data[(A.length B.length - 1) / 2 1])/2;}
}//法一/* int find(Sqlist A, Sqlist B)
{int a0 0, b0 0, am, bm, an A.length - 1, bn B.length - 1;while (a0 ! an || b0 ! bn){am (a0 an) / 2;bm (b0 bn) / 2;if (A.data[am] B.data[bm])return A.data[am];else if (A.data[am] B.data[bm]){a0 a0 bn - bm;bn bm;}else{b0 b0 an - am;an am;}}if (A.data[a0] B.data[b0])return B.data[b0];elsereturn A.data[a0];
} //法二*/int main09()
{Sqlist A { {3,5,7,10}, 4 };Sqlist B { {4,9,15,20}, 4 };cout Find(A, B) endl;return EXIT_SUCCESS;
}设计一个时间上尽可能高效的算法,找出数组中未出现的最小正整数
#include iostream
//#includestdlib.h malloc头文件
using namespace std;
/*设计一个时间上尽可能高效的算法,找出数组中未出现的最小正整数由题意得 时间上尽可能高效的算法就要空间换时间数组A 1 2 4 -6 10 数组B 0 0 0 0 0 初始化数组B存储1 1 0 1 0 找未出现的最小正整数 要满足1、正整数 2、未出现的 3、最小数组B不为0的索引1表示数组A存在的数(索引理解为数组下标)第一个出现的0就是未出现的最小正整数如果数组A1 2 3 4 5那么数组B1 1 1 1 1
*/
int find(int A[], int n)//传入的数组和数组的长度
{int i;int *B new int[n];//int *B (int*)malloc(sizeof(int) * 10); C语言写法for (int k 0; k n; k){B[k] 0;}for (i 0; i n; i){if (A[i] 0 A[i] n)//A[i]n代表大于数组长度的元素直接不考虑了 这里存的是这范围里面的正整数{B[A[i] - 1] 1;}}for (i 0; i n; i){if (B[i] 0){break;}}cout i i;cout endl;delete[] B;//free(B); C语言写法return i 1;
}int main10()
{//int A[5] { 5, -2, 1, 4, 5 };int A[5] {1,2,3,4,5 };cout find(A, 5) endl;return EXIT_SUCCESS;
}若一个整数序列中有过半相同元素则称其为主元素设计算法找出数组A(a0,a1……an - 1)的主元素。(其中0 ai n)若存在主元素则输出否则返回 - 1
#include iostream
using namespace std;
/*若一个整数序列中有过半相同元素则称其为主元素设计算法找出数组A(a0,a1……an - 1)的主元素。(其中0 ai n)若存在主元素则输出否则返回 - 1A:2 3 3 6 3 5 3 3B:0 1 5 0 1 1 0 03是主元素(58/2)1、空间换时间 堆区申请一个数组2、由于ai是小于n的 对于出现的数进行记数 出现一次13、返回这个主元素 数组下标1就为该元素
*/int fun(int A[], int n)//参数为数组 n为数组的长度
{int *B new int[n];for (int i 0; i n; i) {B[i] 0;}int i, k, max 0;//max是用来记录B数组中最大的那个数(即A数组中出现频率最高的那个数) k是用来记录数组下标的for (i 0; i n; i) {if (A[i] 0 A[i] n) {B[A[i] - 1];}}for (i 0; i n; i) {if (B[i] max){max B[i];k i;}}delete[] B;if (max n / 2)//过半的元素return k 1;elsereturn -1;
}int main11()
{int A[8] {2,3,3,6,3,5,3,3};cout fun(A, 8) endl;return EXIT_SUCCESS;
}
