试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。
时间: 2023-05-12 11:05:00 浏览: 134
以下是实现顺序表就地逆置的算法:
```
void reverse(int* arr, int n) {
int i, temp;
for (i = 0; i < n / 2; i++) {
temp = arr[i];
arr[i] = arr[n - i - 1];
arr[n - i - 1] = temp;
}
}
```
这个算法的时间复杂度为 O(n),其中 n 是线性表的长度。
相关问题
试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1
可以使用链表来实现顺序表的地位逆置,即利用原表的存储空间将其改造成线性表(a1,a2,…,an-1,an)的存储空间,则线性表中元素的前后关系与原表恰好相反。利用链表实现时,可以新建一个头节点,将原表中的元素逆序存储在头节点之后的位置上,从而使得头节点之后的链表满足线性表逆置的要求。
试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1,a2,……,an)逆置为(an,an-1,……,a2,a1)
算法如下:
1. 定义两个指针i和j,分别指向顺序表的第一个元素和最后一个元素。
2. 循环执行以下步骤,直到i>=j:
a. 交换i和j指向的元素。
b. i指针向后移动一位。
c. j指针向前移动一位。
3. 完成逆置。
代码实现:
void reverse(SqList &L)
{
int i = , j = L.length - 1;
while (i < j)
{
int temp = L.data[i];
L.data[i] = L.data[j];
L.data[j] = temp;
i++;
j--;
}
}
其中,SqList为顺序表的结构体,包含data数组和length长度属性。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)