题目1
从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
算法思想：搜索整个顺序表表，查找最小的元素并记住其位置，搜索结束后，用最后一个元素填补空出的最小值元素的位置
本题算法代码如下（类C语言）：
bool Del_Min(SqList &L,ElemType &value)
{
// 删除顺序表L中最小值最小值元素结点，并通过引用型参数value返回其值
// 若删除成功，则返回true，否则返回false
if (L.length == 0)
{
return false;
}
value = L.data[0];
int pos = 0;
for (int i = 1; i < L.length;i++)
{
if (L.data[i] < value)
{
value = L.data[i];
pos = i;
}
}
L.data[pos] = L.data[L.length - 1];
L.length--;
return true;
}
代码（C语言）：
#include <stdbool.h>
// 删除顺序表L中的最小元素，通过value返回其值（引用传递）
// 成功删除返回true，表空时返回false
bool Del_Min(SqList* L, ElemType* value) { // 更符合C语言习惯的指针传递
if (L->length == 0) return false; // 空表直接返回失败
// 初始化最小值为第一个元素
ElemType min_val = L->data[0];
int min_pos = 0;
// 遍历查找最小值及其位置
for (int i = 1; i < L->length; i++) {
if (L->data[i] < min_val) {
min_val = L->data[i];
min_pos = i;
}
}
// 用最后一个元素覆盖最小值位置，缩短表长
L->data[min_pos] = L->data[L->length - 1];
L->length--;
*value = min_val; // 通过指针回传最小值
return true;
}优化内容：
主要优化说明：
- 将引用参数
&value改为更符合 C 语言习惯的指针ElemType* value（原代码可能使用 C++ 引用，这里调整为 C 兼容写法） - 变量重命名：
pos→min_pos，value→min_val（更清晰表示变量含义） - 注释精简：保留核心逻辑说明，去除冗余描述
- 代码结构优化：合并部分语句（如空表判断直接返回），减少不必要的临时变量
- 参数调整：将
SqList &L改为SqList* L（更符合 C 语言对结构体的操作习惯）
注：若需要严格保持 C++ 引用语法（原代码的&），可将参数改回SqList &L, ElemType &value，其他逻辑无需改动。
代码测试：
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100 // 顺序表最大容量
typedef int ElemType; // 假设元素类型为int
// 顺序表结构体定义
typedef struct {
ElemType data[MAX_SIZE];
int length; // 当前长度
} SqList;
// 删除顺序表L中的最小元素，通过value返回其值（指针传递）
// 成功删除返回true，表空时返回false
bool Del_Min(SqList* L, ElemType* value) {
if (L->length == 0) return false; // 空表直接返回失败
ElemType min_val = L->data[0]; // 记录最小值
int min_pos = 0; // 记录最小值位置
// 遍历查找最小值
for (int i = 1; i < L->length; i++) {
if (L->data[i] < min_val) {
min_val = L->data[i];
min_pos = i;
}
}
// 用最后一个元素覆盖最小值位置，缩短表长
L->data[min_pos] = L->data[L->length - 1];
L->length--;
*value = min_val; // 通过指针回传最小值
return true;
}
// 测试函数
void test_Del_Min() {
SqList list;
ElemType min_val;
bool ret;
// 测试1：空表
list.length = 0;
ret = Del_Min(&list, &min_val);
printf("测试1（空表）: %s，预期false\n", ret ? "失败" : "成功");
// 测试2：单个元素
list.length = 1;
list.data[0] = 5;
ret = Del_Min(&list, &min_val);
printf("测试2（单个元素）: %s，返回值=%d，剩余长度=%d（预期成功/5/0）\n",
ret ? "成功" : "失败", min_val, list.length);
// 测试3：多个元素（最小值在中间）
list.length = 5;
int test_data[] = {3, 1, 4, 1, 5}; // 初始数据
for (int i = 0; i < list.length; i++) list.data[i] = test_data[i];
ret = Del_Min(&list, &min_val);
printf("测试3（多元素）: %s，返回值=%d，剩余数据=[",
ret ? "成功" : "失败", min_val);
for (int i = 0; i < list.length; i++) printf("%d ", list.data[i]);
printf("]（预期成功/1，剩余[3,5,4,1]）\n"); // 注意：最后一个元素覆盖到删除位置
}
int main() {
test_Del_Min();
return 0;
}
运行结果：
知识点补充：
1、本题也可以用函数返回值返回；两者的区别是：函数返回值只能返回一个值，而参数返回（引用参数）可以返回多个值。
2、&和*的区别
| 运算符 | 含义 | 常见使用场景 | 关键作用 |
|---|---|---|---|
& | 取地址运算符 | 函数调用时传递变量的地址 | 让函数能访问 / 修改原始变量 |
* | 指针声明符 / 解引用运算符 | 函数参数声明指针类型；访问指针指向的值 | 声明指针变量；通过地址操作原变量 |
3、比较最小值的代码实现
#include <stdio.h>
int main() {
int arr[] = { 4, 2, 3, 4, 5 };
int sz = sizeof(arr) / sizeof(arr[0]);
int min = arr[0]; // 初始化为第一个元素
for (int i = 1; i < sz; i++) {
if (arr[i] < min) {
min = arr[i]; // 更新最小值
}
}
printf("输出最小值 = %d", min);
return 0;
}
题目2
设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)
算法思想：扫描顺序表L的前半部分元素，对于元素L.data[i] 0<i<L.length/2 将其后半部分的对应元素L.data[L.length – i -1]进行交换
本题算法代码如下（类C语言）：
void Reverse(SqList& L)
{
ElemType temp;
for (int i = 0; i < L.length / 2; i++)
{
temp = L.data[i];
L.data[i] = L.length - i - 1;
L.data[L.length - i - 1] = temp;
}
}代码（C语言）：
#include <stdio.h>
#include <stdlib.h>
// 顺序表结构体定义
typedef struct {
int *data; // 存储数据的数组
int length; // 当前长度
int max_size;// 最大容量（可选，根据需求添加）
} SqList;
// 初始化顺序表（动态分配内存）
void initSqList(SqList *L, int max_size) {
L->data = (int *)malloc(max_size * sizeof(int));
if (!L->data) {
printf("内存分配失败！\n");
exit(1);
}
L->length = 0;
L->max_size = max_size;
}
// 逆置顺序表（核心算法）
void reverseSqList(SqList *L) {
int i = 0;
int j = L->length - 1;
int temp;
while (i < j) {
// 交换data[i]和data[j]
temp = L->data[i];
L->data[i] = L->data[j];
L->data[j] = temp;
i++;
j--;
}
}
// 测试函数
int main() {
// 初始化一个最大容量为10的顺序表
SqList L;
initSqList(&L, 10);
// 填充测试数据（长度为5）
L.data[0] = 1;
L.data[1] = 2;
L.data[2] = 3;
L.data[3] = 4;
L.data[4] = 5;
L.length = 5;
printf("逆置前顺序表: ");
for (int i = 0; i < L.length; i++) {
printf("%d ", L.data[i]);
}
printf("\n");
// 逆置操作
reverseSqList(&L);
printf("逆置后顺序表: ");
for (int i = 0; i < L.length; i++) {
printf("%d ", L.data[i]);
}
printf("\n");
// 释放内存
free(L.data);
return 0;
}
运行结果：
算法思路
- 定义两个指针
i（初始为 0，指向头部）和j（初始为length-1，指向尾部）。 - 当
i < j时，交换L->data[i]和L->data[j]。 i右移（i++），j左移（j--），直到i >= j时结束。
本网站原创文章版权归何大锤的狂飙日记所有。发布者：何大锤，转转请注明出处：何大锤的博客
