换位.cpp

经典算法之换位和工作安排

///////////////////////////////////////////////////////////
//           实验名称：p35_2_11 换位                     //
//           实验日期：2004。3。9                        //
//           何熠涵   01计算机班  11311049               //
///////////////////////////////////////////////////////////

#include<stdio.h>     
#define N 10          //宏定义数组长度

void change(int arg[],int k,int n)     
{   //用O(1)辅助空间和最坏情况下耗时O(n)对arg[0:k]和arg[k+1:n-1]

	int i;

	void arrangeL(int arg[],int k,int n,int ft);  //声明从左向右换位函数
	void arrangeR(int arg[],int k,int n,int ft);  //声明从右向做换位函数

	if(k<(n-1-k))                  //判断左右顺序
	{
		arrangeL(arg,k,n,0);       //调用从左向右换位函数
	    for(i=0;i<n;i++)
			printf("%3d",arg[i]);
	}
	else
	{
		arrangeR(arg,k,n,0);       //调用从右向做换位函数
		for(i=0;i<n;i++)
			printf("%3d",arg[i]);
	}
}

void arrangeL(int arg[],int k,int n,int ft)
{   //当arg[ft:k]的个数大于arg[k+1:n-1]的个数时的换位，ft为要排序的数组段的首号
	int nl;
    int i,j,m;

	m=k-ft;
	nl=(n-1-k)/(m+1);
    
	void swap(int *p,int *q);                 //函数声明
	void arrangeR(int arg[],int k,int n,int ft);

	for(i=0;i<nl;i++)                         //循环交换 
		for(j=0;j<=m;j++)
			swap(&arg[ft+i*(m+1)+j],&arg[ft+i*(m+1)+j+m+1]);

	if((((n-1)-k)%(k-ft+1))!=0)	              //对数组零散的数组段进行换位
		arrangeR(arg,((m+1)*(i+1)-1),n,i*(1+m));
}

void arrangeR(int arg[],int k,int n,int ft)
{   //当arg[ft:k]的个数小于arg[k+1:n-1]的个数时的换位，ft为要排序的数组段的首号
	int nr;       
	int i,j;
    int m;

	m=k-ft;
	nr=(m+1)/(n-1-k);        

	void swap(int *p,int *q);                    //函数声明
	void arrangeL(int arg[],int k,int n,int ft); 

	for(i=0;i<nr;i++)                            //循环交换 
		for(j=0;j<(n-1-k);j++)
			swap(&arg[ft+i*(n-1-k)+j],&arg[k+j+1]); 
 
	if(((k-ft+1)%(n-1-k))!=0)                    //对数组零散的数组段进行换位
		arrangeL(arg,k,n,(i*(n-1-m)));
}

void swap(int *p,int *q)
{   //交换函数交换数组中的两个数的地址
	
	int temp;       //利用O(1)的辅助空间

	temp=*p;
	*p=*q;
	*q=temp;
}

void main()
{   //主函数，输入有关数据
	
	int arg[N],i,k;

	void change(int arg[],int k,int n);   //声明change函数
	
	printf("Input data:\n");              //输入数组
	i=0;
    printf("%3d :",i);
	scanf("%d",&arg[i]);
	for(i=1;i<N;i++)
    {
		printf("%3d :",i);
		scanf("%d",&arg[i]);
    }

	printf("\ninput k value:\n");         //输入换位的界号
	scanf("%d",&k);

	change(arg,k,N);                      //调用change函数进行换位
	printf("\n");

}