将一串数字顺序后移

                                                            将一串数字顺序后移

一、题目描述

　　有n个整数，使前面各数顺序向后移m个位置，最后m个数变成最前面m个数（m<n）。(更多内容，可参阅程序员在旅途)

二、分析解答

　　这道题主要是编程逻辑的训练。涉及到数组、指针的知识点，本道题目也能很好的表达出选用不同的数据结构，对同一道题目会有完全不同的解题思路，编程复杂度也会有很大的差别。
　　方法一：采用数组数据结构存储数据。思路：①使用一个临时数组，把原数组中的后m个数字先复制到这个新建的数组中，再把原数组中的元素向后移动m个位置，最后把临时数组中的元素复制到原数组的开头位置。②使用一个和原数组长度一样的临时数组，将原数组的后m个数字复制到临时数组的前m位，然后再把原数组的剩余的数字复制到临时数组的后面，然后返回临时数组。
　　值得注意的是思路①②的临时数组空间大小是不一样的，编程上略有区别。还要注意数组下标的计算，这点很容易出错。

#include<stdio.h>
void shift(int *a,int n,int m)
{
    int t[20];
	int i;
	for(i=0;i<n;i++)
	{
		t[i]=a[i];
	}
	for(i=0;i<m;i++)
	{
		a[i]=t[n-m+i];
	}
	for(i=m;i<n;i++)
	{
		a[i]=t[i-m];
	}	
}
int main()
{
	int a[20];
	int n,m;
	int i;
	
	scanf("%d",&n);

	for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}

	    scanf("%d",&m);
		shift(a,n,m);
		for(i=0;i<n;i++)
		{
			printf("%d \t ",a[i]);
		}
		printf("\n");


		return 0;
}

　　方法二：采用单链表数据结构存储数据。思路：将第（N - M）位置的元素作为首节点（也就是最后m个元素的首个元素节点），原链表首节点元素链接到原链表尾结点即可。

#include<stdio.h>
#include<stdlib.h>

typedef struct data_node{

	int data;

	struct data_node *next;

}Node;

int main(){

	Node *head = NULL , *tail =NULL,  *p = NULL;

	int n,m,i=0;

	//输入N个整数
	scanf("%d",&n);

	while(i++<n){
	
		//申请节点所占用的内存空间
		if( (p = (Node *)malloc(sizeof(Node))) == NULL){
		
			printf("memery is not available");
			exit(1);

		}

		scanf("%d", &(p->data));
		p->next = NULL;

		//当前申请的是第一个节点
		if(head == NULL){

			head = tail = p;
	
		}else{
			//链尾插值
		
			tail->next = p;
			tail = p;
		
		}	
	}


	//找到第(N-M)位置的前驱节点。
	scanf("%d",&m);

    i=0;
	p = head;
    while( i++<n -m -1){
	
      p = p->next;

	}

	//注意这几个元素的交换。是实现这个题目的核心所在
	//最后m个元素的首元素作为链头，原链表首节点元素链接到原链表尾结点。这样就实现了后移
	tail->next = head;
	head = p->next;
	
	tail = p;
	tail->next = NULL;

	//输出处理后的数
	p = head;
	while(p){
	
		printf("%d  ",p->data);

		p = p->next;
	}
	printf("\n");

	return 0;
}

　　程序运行结果示意图：

　　

三、小结

　　从上面的两种不同的方法解决同一问题我们可以看到，不同数据结构的选择，对编程思想的影响很大，数据结构的巧妙选择有时会大大的简化编程逻辑上的理解。同时，不同的数据结构还会对程序算法的时间复杂度和空间复杂度形成很大的差异。