C语言将数组中的两个顺序表位置互换
这里涉及到数据结构中顺序表的实现、删除、插入、查找等知识,请查看:数据结构 -> 线性表
试编写一个函数,将数组中两个顺序表的位置互换,即将 (b1, b2, b3, …, bn) 放在 (a1, a2, a3, ..., am) 的前面。
本题代码如下:
问题描述:
已知在一维数组A[m+n]中依次存放着两个线性表 (a1, a2, a3, …, am) 和(b1, b2, b3, …, bn)。试编写一个函数,将数组中两个顺序表的位置互换,即将 (b1, b2, b3, …, bn) 放在 (a1, a2, a3, ..., am) 的前面。
问题解答:
算法思想:首先将数组A[m+n]中的全部元素 (a1, a2, a3, …, am, bi, b2, b3, …, bn) 原地逆置为 (bn, bn-1, bn-2, …, b1, am, am-1, am-2, …, a1),再对前n个元素和后m个元素分别使用逆置算法,就可以得到(b1, b2, b3, …, bn, a1, a2, a3, …, am),从而实现顺序表的位置互换。本题代码如下:
typedef int DataType; void Reverse(DataType A[], int left, int right, int arraySize){ //逆转(aleft, aleft+1, aleft+2,..., aright)为(aright, aright-1, ..., aleft) if(left>=right || right>=arraySize) return; int mid== (left+right)/2; for(int i=0; i<mid-left; i++) { Datatype temp=A[left+i]; A[left+i]=A[right-i]; A[right-i]=temp; } } void Exchange(DataType A[],int m,int n,int arraySize){ // 数组A[m+n]中,从0到m-1存放顺序表(a1, a2, a3, …, am) // 从m到m+n-1存放顺序表 (b1, b2, b3, ..., bn ),算法将这两个表的位置互换 Reverse(A, 0, m+n-1, arraySize); Reverse(A, 0, n-1, arraySize); Reverse(A, n, m+n-1, arraySize); }