Question

数据结构:设计一个高效算法，将顺序表中的所有元素逆置，要求算法空间复杂度为O(1)。

Answer 1

设计一个高效算法，将顺序表中的所有元素逆置，要求算法空间复杂度为O(1)扫描顺序表L的前半部分元素L.data[i] (0<=i<L.length/2)，将其与后半部分的对应元素L.data[L.length-1-i]进行交换即可。

顺序表的存储只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 　1≤i≤n 其中，L是元素占用存储单元的长度。

扩展资料：

数据的物理结构是数据结构在计算机中的表示，它包括数据元素的机内表示和关系的机内表示。由于具体实现的方法有顺序、链接、索引、散列等多种。

数据元素的机内用二进制位（bit）的位串表示数据元素。当数据元素有若干个数据项组成时，位串中与各个数据项对应的子位串称为数据域（data field）。

参考资料来源：百度百科-顺序表

Answer 2

数据结构的高效算法：for(int i = 0; i < array.length / 2; i++) {swap(array[i], array[array.length - i - 1])}

只有swap函数需要一个字节的内存，所以空间复杂度O（1）。

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

对每一个数据结构而言，必定存在与它密切相关的一组操作。若操作的种类和数目不同，即使逻辑结构相同，数据结构能起的作用也不同。不同的数据结构其操作集不同，但下列操作必不可缺:

1.结构的生成;

2.结构的销毁;

3.在结构中查找满足规定条件的数据元素;

4.在结构中插入新的数据元素;

5.删除结构中已经存在的数据元素;

6.遍历。

Answer 3

for(int i = 0; i < array.length / 2; i++) {
swap(array[i], array[array.length - i - 1])
}
只有swap函数需要一个字节的内存，所以空间复杂度O（1）

追问

短小精悍的算法 太牛逼了

追答

额。。。

Answer 4

• void Reverse(Sqlist &L){

• Elemtype temp;  //辅助变量

• for(i=0;i<L.length/2;i++){

• temp=L.data[i];  //交换 L.data[i]与 L.data[L.length-i-1]

• L.data[i]=L.data[L.length-i-1];

• L.data[L.length-i-1]=temp;

• }

• }