ACM算法题——快捷键的难题

题目描述：

Windows 7系统有很多的快捷键，Y同学最喜欢的快捷键就是Alt+Tab组合键，可以进行方便的进行多窗口之间的切换。为了方便，去掉一些复杂规则后，Y同学进行了如下定义。

1.窗口队列：w1,w2,……wi……wn, (1<=i<=n, n为窗口数目)。队首w1表示当前为激活状态的窗口。

2.一次切换动作switch(x)：

（1）按住Alt键不放

（2）敲击x次Tab键

（3）放开Alt键

3.一次切换动作switch(x)产生的影响:举例说明

（1）窗口队列 1,2,3,4,5,6 经过switch(1)之后，成为2,1,3,4,5,6

（2）窗口队列 1,2,3,4,5,6 经过switch(2)之后，成为3,1,2,4,5,6

（3）窗口队列 1,2,3,4,5,6 经过switch(5)之后，成为6,1,2,3,4,5

（4）窗口队列 1,2,3,4,5,6 经过switch(6)之后，成为1,2,3,4,5,6

（5）窗口队列 1,2,3,4,5,6 经过switch(8)之后，成为3,1,2,4,5,6

那么Y同学想知道，对于初始窗口队列(1,2,3……n)进行多次switch(x)切换之后，当前激活窗口的ID是多少？请你帮助他解决这个问题。

输入：

第一行为一个正整数：T（T<30）。T表示有多少组测试数据

每一组测试数据

第一行：n m。(0< span="">，n表示窗口队列的长度，m表示有m次switch操作。

第二行：m个正整数x1,x2,……,xi,……xm。表示第i次进行switch(xi)操作;

输出：

对于每组数据，输出经过m次switch操作之后，当前激活窗口的ID。

样例输入：

2

6 2

3 8

8 3

4 3 14

样例输出：

2

7

----------------------------------------------------------------------------

操作系统：ubuntu

编译软件：gcc

结果截图：

源代码：

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

typedef struct Node
{
	int data;
	struct Node *pNext;
}NODE,*PNODE;

PNODE create_list(int);
bool insert_list(PNODE,int,int);
bool delete_list(PNODE,int,int *);

int main()
{
	int T,n,m;   //定义题目中要求的数字
	int i,j,t;   //定义循环用的变量
	int *p;      //动态数组，存储每一组的第二行需要输入数字
	int pdata;   //保存被删除的节点中的数字
	int *result; //动态数组，保存每一组测试数据的最终结果
	PNODE pHead =NULL;

	scanf("%d",&T);
	result = (int*)malloc(T*sizeof(int));
	if(NULL == result)
	{
		printf("result malloc failed!");
		exit(-1);
	}
	
	for(i=0;i<T;i++)
	{
	   //输入每一组的第一行数字
	   scanf("%d %d",&n,&m);

	   //输入每一组的第二行数字
	   p = (int *)malloc(m*sizeof(int));
	   for(j=0;j<m;j++)
	   {
	      scanf("%d",p+j);
	   }

	   //创建一个长度为n的单链表，存储窗口队列
	   pHead = create_list(n);

	   //执行m次题目中switch操作，先删除节点并保存数值，再讲数值插入头节点后面
	   for(t=0;t<m;t++)
	      {
	         delete_list(pHead,(*(p+t))%n+1,&pdata);
   	         insert_list(pHead,0,pdata);
	      }
	   //执行操作后的首节点中的数据即为所求的结果
	   *(result+i) = pHead->pNext->data;
	}

	//输出最终的结果
	for(i=0;i<T;i++)
	{
	   printf("%d\n",*(result+i));
	}

	return 0;
}

/*
  创建一个长度为n链表,并初始化，返回头指针
*/
PNODE create_list(int n)
{
	int i;
	PNODE pHead =(PNODE)malloc(sizeof(NODE));
	PNODE pCurrent = pHead;
	pCurrent->pNext = NULL;
	if(NULL == pHead)
	{
		printf("pHead malloc failed!");
		exit(-1);
	}
	for(i=0;i<n;i++)
	{
	   PNODE pNew = (PNODE)malloc(sizeof(NODE));
	   if(NULL == pNew)
	   {
	      printf("pNew malloc failed!");
	      exit(-1);
	   }
	   pNew->data = i+1;
	   pCurrent->pNext = pNew;
	   pNew->pNext = NULL;
	   pCurrent = pNew;
	}

	return pHead;	
}

/*
在第pos个节点的后面插入一个新的节点，该节点中的数据为val
*/
bool insert_list(PNODE pHead,int pos,int val)
{
	int i = 0;
	PNODE p = pHead;

        //i为0时，p指向第0个节点（这里指没有实际数据的头节点，不计入链表节点总数），
	//i为1时，p指向第1个节点，i为几，p就指向第几个节点
	while(p!=NULL && i<pos)
	{
	   p = p->pNext;
	   i++;
	}

	//当pos的值大于链表长度时，便会出现这种情况
	if(i>pos || p==NULL)
	   return false;

	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if(NULL == pNew)
	{
	   printf("pNew malloc failed!");
	   exit(-1);
	}
	pNew->data = val;
	pNew->pNext = p->pNext;
	p->pNext = pNew;

	return true;
}

/*
删除第pos个节点，并将删除的数据保存在pData指针所指向的位置
*/
bool delete_list(PNODE pHead,int pos,int *pData)
{
	int i = 0;
	PNODE p = pHead;

	//p最终指向第pos个节点前面的节点
	//如果下面两句分别改为while(p!=NULL && i<pos)和if(i>pos || p==NULL)，则p最终指向第pos个节点，
	//这样因为得不到第pos个节点前面的那个节点，因此无法将pos前后两个节点连结起来
	while(p->pNext!=NULL && i<pos-1)
	{
	   p = p->pNext;
	   i++;
	}

	//当pos的值大于链表长度时，便会出现这种情况
	if(i>pos-1 || p->pNext==NULL)
	   return false;

	PNODE q = p->pNext;
	*pData = q->data;
	p->pNext = p->pNext->pNext;
	free(q);
	q = NULL;
	return true;
}