速通数据结构顺序表代码题
2023-12-20 23:22:35
顺序表
- 顺序表递增有序，插入元素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 19
1、找位置 i
2、元素右移
*/
/*
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 10
5 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 9
9 3 16 7 4
4 7 16 3 9 1
1 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……am
1、将左边的一组逆置 am……a3,a2,a1
2、将右边的一组逆置 bm……b3,b2,b1
3、将a1到bn所有的元素逆置 bm……b3,b2,b1 am……a3,a2,a1
1 2 3 4 5 6 7 8 9 10
3 2 1 4 5 6 7 8 9 10
3 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-1
Reverse(A, m, m + n - 1);//左半边的初始位置为m 末端为m+n-1
Reverse(A, 0, m + n - 1);//右半边的初始位置为0 末端为m+n-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 3
12 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的初始值都是0
++k;
}
}
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;
else
L.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 17
12 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;
else
L.data[i - k] = L.data[i];
}
L.length -= k;//更新length
return 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 9
5 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循环i++，j++
}
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 9
5 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循环i++，j++
}
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 25
4 9 13
3 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++];
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 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 10
4 9 15 20
3 4 5 7 9 10 15 20
8
1、先合并这个两个递增序列
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++];
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++];
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];
else
return 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>
//#include<stdlib.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就是未出现的最小正整数
如果数组A：1 2 3 4 5
那么数组B：1 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)若存在主元素则输出，否则返回 - 1
A:2 3 3 6 3 5 3 3
B:0 1 5 0 1 1 0 0
3是主元素(5>8/2)
1、空间换时间 堆区申请一个数组
2、由于ai是小于n的 对于出现的数进行记数 出现一次+1
3、返回这个主元素 数组下标+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;
else
return -1;
}
int main11()
{
int A[8] = {2,3,3,6,3,5,3,3};
cout << fun(A, 8) << endl;
return EXIT_SUCCESS;
}
文章来源:https://blog.csdn.net/m0_69093426/article/details/135112275
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！