文章目录
- 一【题目类别】
- 二【题目来源】
- 三【题目描述】
- 四【解题思路】
- 五【时间频度】
- 六【代码实现】
- 七【程序测试】
一【题目类别】
二【题目来源】
- 本题目选自王道2023考研计算机数据结构复习指导18页中二、综合应用题之02题
三【题目描述】
- 设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为
O
(
1
)
O(1)
O(1)。
四【解题思路】
- 可以看到算法要求的时间复杂度为
O
(
1
)
O(1)
O(1)，所以肯定不能开辟新的空间去操作，只能在原顺序表操作。既然这样，我们只需要扫描顺序表的的前半部分，利用顺序表下标去交换两端对应位置元素即可
五【时间频度】
- 时间复杂度：
O
(
n
)
O(n)
O(n)，其中
n
n
n为顺序表长度
- 空间复杂度：
O
(
1
)
O(1)
O(1)
六【代码实现】
#define _CRT_SECURE_NO_WARNINGS
#include
#define MaxSize 50
typedef int ElemType;
typedef struct
{
ElemType data[MaxSize];
int length;
}SqList;
void Reverse(SqList L)
{
ElemType temp;
for (int i = 0; i < L.length / 2; i++)
{
temp = L.data[i];
L.data[i] = L.data[L.length - 1 - i];
L.data[L.length - 1 - i] = temp;
}
printf("逆置后的顺序表为：");
for (int i = 0; i < L.length; i++)
{
printf("%d ", L.data[i]);
}
printf("n");
}
int main()
{
SqList L;
L.length = 0;
int len;
printf("请输入顺序表长度（长度应≤50）：");
scanf("%d", &len);
printf("请输入顺序表元素：");
for (int i = 0; i < len; i++)
{
scanf("%d", &L.data[i]);
L.length++;
}
printf("初始顺序表为：");
for (int i = 0; i < L.length; i++)
{
printf("%d ", L.data[i]);
}
printf("n");
Reverse(L);
system("pause");
return 0;
}
七【程序测试】
- 顺序表长度为偶数
- 顺序表长度为奇数
