【王道数据结构】两个线性表位置原地互换

  • 时间:
  • 浏览:
  • 来源:互联网

文章目录

  • 题目
  • 思路
  • 伪码
  • c代码

题目

已知在一维数组A[m+n]中依次存放两个线性表 a 1 , a 2 , a 3 . . . a m a_1,a_2,a_3...a_m a1,a2,a3...am b 1 , b 2 , b 3 . . . b n b_1,b_2,b_3...b_n b1,b2,b3...bn。试编写一个函数将数组中两个顺序表的位置互换,即将 b 1 , b 2 , b 3 . . . b n b_1,b_2,b_3...b_n b1,b2,b3...bn放在 a 1 , a 2 , a 3 . . . a m a_1,a_2,a_3...a_m a1,a2,a3...am的前面

思路

  1. 将整个数组A原地逆置。得到 b n , b n − 1 , b n − 2 . . . b 1 , a m , a m − 1 , a m − 2 . . . a 1 b_n,b_{n-1},b_{n-2}...b_1,a_m,a_{m-1},a_{m-2}...a_1 bn,bn1,bn2...b1,am,am1,am2...a1
  2. 分别对前面n个元素(b数组)和后面m个元素(a数组)做逆置操作

伪码

bool reverse(ElemType a[], int left, int right, int maxSize){
	if(left >= right || right > maxSize)
		return false;
	int i = left, j = right;
	ElemType t;
	while(i < j){
		t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
	return true;
}
void Chg(int a[], int m, int n, int maxSize){
	reverse(a, 0, m+n, maxSize);
	reverse(a, 0, n, maxSize);
	reverse(a, n, m+n, maxSize);
}

c代码

#include<stdio.h>
#define N 9
_Bool reverse(int a[], int left, int right, int size){
	//对数组a[left,right)的元素做一次原地逆置
	int i = left, j = right-1, t;
	if(left >= right || right > size)
		return 0;
	while(i < j){
		t = a[i];
		a[i] = a[j];
		a[j] = t;
		i++;
		j--;
	}
	return 1;
}
int main(){
    int a[N]={1,2,3,4,5,2,4,6,8};
    int n = 4;//数组b的长度 
    int i = 0;
    reverse(a, 0, N, N);
    reverse(a, 0, n, N);
    reverse(a, n, N, N);
    //康康效果
    while(i < N)
    	printf("%d ",a[i++]);
    printf("\n");
    return 0;
}

本文链接http://www.dzjqx.cn/news/show-617489.html