【数据结构】线性表——逆置

通用代码

下面是采用顺序存储和链式存储的线性表元素逆置的通用代码

顺序存储

变量解释:

上代码：

// 顺序存储
for(int i = left, j = right; i < j; ++i, --j)
{temp = a[i];a[i] = a[j];a[j] = temp;
}

直接交换即可，需要逆置的元素为奇数个时循环结束条件为 i 与 j 交错；元素偶数个时结束条件为 i 与 j 相等，综合起来为i<j

链式存储

变量解释：

上代码：

// 链式存储
// 逆置p->next到q之间的节点
while(p->next != q)
{t = p->next;p->next = t->next;t->next = q->next;q->next = t;
}

一个小小的过程图

考研真题

1.将一长度为n的数组的前端k(k<n)个元素逆序后移动到数组后端，要求原数组中数据不丢失
题中只要求了“数据不丢失”，因此只要前k个元素移动到数组末尾即可，其他元素在哪都无所谓（好坑！本来理解的是前k个逆序+移动到数组末尾后数组其他元素的顺序要保持…后来才发现题里只要求数组中数据不丢失就行了！！！）
代码只用加上条件：i < left+k，让 i 只扫描前k个元素
效果为前k个元素和后k个元素交换
示意图（k = 4）：
i 只扫描前4个元素，与 j 对应的元素交换

原始状态

交换后

/*参数说明：a[]:要改变的数组left:左边起点right:右边终点k:要移动的元素个数*/
void reverse(int a[],int left,int right,int k)
{int temp;for(int i = left,j = right; i < left+k && i < j; ++i,--j){temp = a[i];a[i] = a[j];a[j] = temp;}
}

2.将一长度为n的数组的前端k(k<n)个元素保持原序移动到数组后端，要求原数组中数据不丢失
同1题，操作后前k个元素保持原顺序移到数组末尾即可，其他元素无所谓！！
示意图（k=4）:

初始状态同1
将前4个逆置

前四个与后四个交换

void moveToEnd(int a[], int n, int k)
{reverse(a, 0, k-1, k); //reverse函数为第一题中的reverse(a, 0, n-1, k);
}

3.将数组中的元素(X₀, X₁, … , X_n-1)，经过移动后变为(X_p, X_p+1, … , X_n-1, X₀, X₁, … , X_p-1)，即循环左移p(0<p<n)个位置
示意图：

初始状态

逆置0 ~ p-1

逆置p ~ n-1

最后整体逆置

一个手画草图

void moveP(int a[], int n, int p)
{reverse(a, 0, p-1, p);reverse(a, p, n-1, n-p);reverse(a, 0, n-1, n);
}