本文共 768 字，大约阅读时间需要 2 分钟。
问题.设计一个高效的算法，将顺序表所有元素逆置，要求算法的空间复杂度为O(1)。
算法思想：将第一个元素与最后一个元素互换，第二个元素与倒数第二个元素互换，以此类推。
伪代码：
void Reverse(SqList &L){ ElemType temp; //中间变量 for(i=0; i 解析：
- 空间复杂度是O(1)表示算法所需要的辅助空间是常数。
- 函数类型void，不返回任何值。函数名Reverse。使用时需要传递顺序表地址作为参数。
- L.data表示L中的数据，L.length表示数据的个数。
- 直接最后一个元素的值赋给第一个元素，第一个元素的值消失了，两个元素的值相同，不能完成交换。
- 不知道顺序表存储的是什么类型的数据，中间变量类型直接ElemType抽象表示。
- for循环，从i=0开始计数，如果满足i的值小于顺序表长度的一半，执行花括号的内容，执行完毕后i自增1。继续判断是否满足i的值小于顺序表长度的一半的条件。
- temp存放前面元素的值。
- 将后面元素的值赋给前面的元素。最初，最后一个元素的值赋给第一个元素。
- 数组这里顺序表的下标是从0开始。最后一个元素的下标比数组长度少1。
- 如果顺序表长度是奇数，比如9，C语言中9/2保留整数是4。执行到i=3时是最后一次循环，L.data[3] 表示第4个元素的值，L.data[9-3-1]表示第6个元素的值，交换它们。刚好第5个元素的值不用交换。
- 如果顺序表长度是偶数，比如8，执行到i=3时是最后一次循环，L.data[3] 表示第4个元素的值，L.data[8-3-1]表示第5个元素的值，交换它们。1和8互换，2和7互换，3和6互换，4和5互换。或者4+5 = 1+8，验证成功。
这里&L，给出的参数是L的地址，所以函数内部可以直接对L所在的存储空间进行操作。
转载地址：http://jeeii.baihongyu.com/