文章目录[隐藏]
- 顺序表
- 1. 定义
- 2. 初始化
- 3. 打印顺序表
- 4. 插入元素
- 5. 删除指定位置的元素
- 6. 删除最小元素并用最后一个元素替换
- 7. 在无序表中删除值在范围 s 和 t 之间的元素（过滤法）
- 8. 在非递减顺序表中删除值在范围 s 和 t 之间的元素（偏移法）
- 9. 删除非递减顺序表中的重复元素
- 10. 顺序表 A 和 B 的元素个数分别为 m 和 n，表 A 升序排序，表 B 降序排序，两个表中都不存在相同的元素
- 11. 给定两个非空集合 A 和 B,分别用升序顺序表 La 和 Lb 存储，设计算法求解 A∩B（共同元素只能出现一次）
- 12. 给定两个非空集合 A 和 B,分别用升序顺序表 La 和 Lb 存储，设计算法求解 A-B
- 13. 逆置顺序表
- 14. 将顺序表 L 循环左移动 r
顺序表
1. 定义
1.1 静态
#define MAX_SIZE 100
typedef int ElemType
typedef struct SqList{
ElemType list[MAX_SIZE];
int length;
}SqList;1.2 动态
typedef int ElemType;
typedef struct SqList{
ElemType *pList;
int length;
int listSize;
}SqList;2. 初始化
#define N 10
typedef int ElemType;
// 初始化顺序表
void InitList(SqList &L){
L.pList = (ElemType *) malloc (sizeof(ElemType) * N);
L.length = 0;
L.listSize = N;
}3. 打印顺序表
void PrintList(SqList L) {
printf("当前列表长度: %d\n", L.length);
for (int i = 0; i < L.length; i++) {
printf("%d ", L.pList[i]);
}
printf("\n");
}4. 插入元素
bool ListInsert(SqList &L, int i, ElemType e){
// 1. 判断 i 是否合法
if(i < 1 || i > L.length + 1){
return false;
}
// 2. 判断插入空间是否充足，不充足申请新的空间，并将原数据复制过去
if(L.length >= L.listSize){
ElemType *pNew = (ElemType *) malloc (sizeof(ElemType) * (2 * L.listSize));
for(int index = 0; index < L.length; index++){
pNew[index] = L.pList[index];
}
L.pList = pNew;
L.listSize = 2 * L.listSize;
}
// 3. 插入 i
for(int j = L.length - 1; j >= i - 1; j--){
L.pList[j + 1] = L.pList[j];
}
L.pList[i - 1] = e;
L.length++;
return true;
}5. 删除指定位置的元素
bool ListDelete(SqList &L, int i, ElemType &e){
// 1. 判断删除位置是否合法
if(i < 1 || i > L.length){
return false;
}
// 2. 将第 i 个元素保存
e = L.pList[i - 1];
// 3. 将第 i 个元素向前移动
for(int j = i; j < L.length; j++){
L.pList[j - 1] = L.pList[i];
}
L.length--;
return true;
}6. 删除最小元素并用最后一个元素替换
void ListDeleteMinElem(SqList &L, ElemType &e){
// 1. 记录最小值元素索引
int minIndex = 0;
// 2. 循环查找最小值索引
for(int i = 1; i < L.length; i++){
if(L.pList[minIndex] > L.pList[i]){
minIndex = i;
}
}
// 3. 记录最小值并用最后一个元素替换
e = L.pList[minIndex];
L.pList[minIndex] = L.pList[L.length - 1];
L.length--;
}7. 在无序表中删除值在范围 s 和 t 之间的元素（过滤法）
void ListDeleteElemBetween1(SqList &L, ElemType s, ElemType t){
// 1. 记录结果子序列索引
int curLength = 0;
// 2. 遍历序列过滤
for(int i = 0; i < L.length; i++){
if(L.pList[i] < s || L.pList[i] > t){
L.pList[curLength] = L.pList[i];
curLength++;
}
}
// 3. 更新表长
L.length = curLength;
}8. 在非递减顺序表中删除值在范围 s 和 t 之间的元素（偏移法）
void ListDeleteElemBetween2(SqList &L, ElemType s, ElemType t) {
int start = 0, end = L.length - 1;
// 1. 找到第一个大于等于 s 的元素位置
while (start < L.length && L.pList[start] < s) {
start++;
}
// 2. 找到第一个小于等于 t 的元素位置
while (end >= 0 && L.pList[end] > t) {
end--;
}
// 3. 移动元素覆盖删除区间内的元素
for (int i = end + 1; i < L.length; i++) {
L.pList[start++] = L.pList[i];
}
// 4. 更新顺序表的长度
L.length = start;
}9. 删除非递减顺序表中的重复元素
void RemoveDuplicates(SqList &L){
if(L.length == 0) return;
// 1. 记录不重复元素的索引
int uniqueIndex = 0;
// 2. 循环删除
for(int i = 1; i < L.length; i++){
if(L.pList[uniqueIndex] != L.pList[i]){
uniqueIndex++;
L.pList[uniqueIndex] = L.pList[i];
}
}
// 3. 更新表长
L.length = uniqueIndex + 1;
}10. 顺序表 A 和 B 的元素个数分别为 m 和 n，表 A 升序排序，表 B 降序排序，两个表中都不存在相同的元素
10.1 将两表合并，两表中的元素都存储到表 C 中
void MergeList(SqList &A, SqList &B, SqList &C) {
int i = 0, j = B.length - 1, k = 0;
// 1. 使用双指针法
while (i < A.length && j >= 0) {
if (A.pList[i] < B.pList[j]) {
C.pList[k++] = A.pList[i++];
} else {
C.pList[k++] = B.pList[j--];
}
}
// 2. 将剩余的表 A 元素复制到表 C 中
while (i < A.length) {
C.pList[k++] = A.pList[i++];
}
// 3. 将剩余的表 B 元素复制到表 C 中
while (j >= 0) {
C.pList[k++] = B.pList[j--];
}
// 4. 更新表 C 的长度
C.length = k;
}10.2 表 A 有 m + n 个存储空间，将 A、B 两表合并，所有元素都存储到表 A 中
void MergeBIntoA(SqList &A, SqList &B){
int i = A.length - 1;
int j = 0;
int k = A.length + B.length - 1;
// 1. 合并 A 和 B 的元素，从最大的开始比较
while(i >= 0 && j < B.length){
if(A.pList[i] >= B.pList[j]){
A.pList[k--] = A.pList[i--];
} else{
A.pList[k--] = B.pList[j++];
}
}
// 2. 如果 B 还有剩余的元素，继续放入 A 中
while(j < B.length){
A.pList[k--] = B.pList[j++];
}
// 3. 更新 A 的长度
A.length += B.length;
}10.3 表 A 前 r 个元素递增有序，而表 A 中后 n - r 个元素递减有序，将表 A 进行升序排序
void InsertSort(SqList &A, int r) {
for(int i = r; i < A.length; i++){
// 1. 当前要插入的元素
ElemType key = A.pList[i];
int j;
// 2. 在已排序部分找到比key大的元素，并将其右移
for(j = i - 1; j >= 0 && A.pList[j] > key; j--){
A.pList[j + 1] = A.pList[j];
}
// 3. 插入key到正确位置
A.pList[j + 1] = key;
}
}11. 给定两个非空集合 A 和 B,分别用升序顺序表 La 和 Lb 存储，设计算法求解 A∩B（共同元素只能出现一次）
void Intersection(SqList &A, SqList &B) {
// 1. 初始化变量
int i = 0, j = 0;
int newLength = 0;
// 2. 遍历 A 和 B，寻找交集
while (i < A.length && j < B.length) {
if (A.pList[i] < B.pList[j]) {
i++;
} else if (A.pList[i] > B.pList[j]) {
j++;
} else {
// 如果交集列表为空，或者最后一个元素不是A.pList[i]
if (newLength == 0 || A.pList[newLength - 1] != A.pList[i]) {
A.pList[newLength] = A.pList[i];
newLength++;
}
i++;
j++;
}
}
// 3. 更新 A 的长度为交集的长度
A.length = newLength;
}12. 给定两个非空集合 A 和 B,分别用升序顺序表 La 和 Lb 存储，设计算法求解 A-B
void Difference(SqList &A, SqList &B) {
// 1. 初始化变量
int i = 0, j = 0;
int newLength = 0;
// 2. 遍历 A 和 B，寻找差集
while (i < A.length && j < B.length) {
if (A.pList[i] < B.pList[j]) {
// 当 A 的当前元素小于 B 的当前元素时，这个元素只存在于 A 中
A.pList[newLength] = A.pList[i];
newLength++;
i++;
} else if (A.pList[i] > B.pList[j]) {
j++;
} else {
i++;
j++;
}
}
// 3. 处理剩余的 A 中的元素
while (i < A.length) {
A.pList[newLength] = A.pList[i];
newLength++;
i++;
}
// 4. 更新 A 的长度为差集的长度
A.length = newLength;
}13. 逆置顺序表
void Reverse(ElemType *arr, int start, int end) {
while (start < end) {
ElemType temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}14. 将顺序表 L 循环左移动 r
void RotateLeft(SqList &L, int r) {
if (r <= 0 || r >= L.length) {
// 无需移动
return;
}
// 1. 将顺序表的前 r 个元素逆序
Reverse(L.pList, 0, r - 1);
// 2. 将顺序表的后 n - r 个元素逆序
Reverse(L.pList, r, L.length - 1);
// 3. 将整个顺序表逆序
Reverse(L.pList, 0, L.length - 1);
}
