顺序表应用4-2：元素位置互换之逆置算法(数据改进）

妖狐艹你老母 2023-03-01 13:54 5阅读 0赞

## 顺序表应用4-2：元素位置互换之逆置算法(数据改进） ##

Problem Description  
一个长度为len(1<=len<=1000000)的顺序表，数据元素的类型为整型，将该表分成两半，前一半有m个元素，后一半有len-m个元素（1<=m<=len)，设计一个时间复杂度为O(N)、空间复杂度为O(1)的算法，改变原来的顺序表，把顺序表中原来在前的m个元素放到表的后段，后len-m个元素放到表的前段。  
注意：交换操作会有多次，每次交换都是在上次交换完成后的顺序表中进行。

Input  
第一行输入整数len(1<=len<=1000000)，表示顺序表元素的总数；

第二行输入len个整数，作为表里依次存放的数据元素；

第三行输入整数t(1<=t<=30)，表示之后要完成t次交换，每次均是在上次交换完成后的顺序表基础上实现新的交换；

之后t行，每行输入一个整数m(1<=m<=len)，代表本次交换要以上次交换完成后的顺序表为基础，实现前m个元素与后len-m个元素的交换；

Output  
输出一共t行，每行依次输出本次交换完成后顺序表里所有元素。

Sample Input  
10  
1 2 3 4 5 6 7 8 9 -1  
3  
2  
3  
5  
Sample Output  
3 4 5 6 7 8 9 -1 1 2  
6 7 8 9 -1 1 2 3 4 5  
1 2 3 4 5 6 7 8 9 -1

#include <stdio.h>
    #include <stdlib.h>
    void nizhi(int  *list, int start, int last)//此为逆置函数，这里的start和last为数组角标位置，list为数组名称
    {
        
    	int t, i, j;
    	for (i = start, j = last; i < j; i++, j--)//头尾互换，头尾同时向里移一位，有条件（i<j；）
    	{
        
    		t = list[j];
    		list[j] = list[i];
    		list[i] = t;
    	}
    }
    int main()
    {
        
    	int i, len, m, list[1000010],t;
    	scanf("%d", &len);
    	for (i = 0; i < len; i++)//顺序表的建立
    	{
        
    		scanf("%d", &list[i]);
    	}
    	scanf("%d", &t);
    	while (t--)
    	{
        
    		scanf("%d", &m);//前m个元素
    		nizhi(list, 0, len - 1);
    		nizhi(list, 0, len - m - 1);
    		nizhi(list, len - m, len - 1);//逆置函数的调用
    		for (i = 0; i < len-1; i++)//下面的代码保证只输出t行
    		{
        
    			printf("%d ", list[i]);
    		}
    		printf("%d", list[len - 1]);
    		if (t != 0)
    		{
        
    			printf("\n");
    		}
    	}
    }

*此题的思路与“顺序表应用4：元素位置互换之逆置算法”相同，只是多了一个多组处理的操作*  
详细可见：[顺序表应用4：元素位置互换之逆置算法][4]

[4]: https://blog.csdn.net/qq_45885219/article/details/107597252