首页 > 代码库 > UVa 133 救济金发放

UVa 133 救济金发放

题意:所有n个人围成一个圈,一边从1号开始逆时针数k个,出局;一边从n号开始顺时针数m个,出局。两个同时发生。如果这两个数到同一个人,就这个人出局。

        facing inwards 面朝里; counter 相反地,clockwise 顺时针,counter-clockwise 逆时针

思路:双向循环链表来模拟。按以前书上介绍的实现的,有一个头指针,首尾都指向它。但这里由于要找第k个、第m个,需要进行头指针的判断,所以觉得这里不增加头指针比较好,或者头指针只指向头结点,而头结点和尾结点是互指的,不像这里实现的头结点和尾结点之间还有一个头指针结点。

           看很多人用数据模拟实现的。。

注意:if里的相等判断,用==

            free同一块内存多次发生未定义错误

           指向指针的引用形参的问题。

找不出错误时,可以跑一下别人AC的程序,对比相同输入的输出。

一般发现一组不一致的或错误的数据时,可以试图找到一组尽量简单的错误数据,除非只对该组数据错误。数据越简单,越容易调试。如果只有很大的数据才会出错,通常意味着程序在处理极限数据方面有问题。

#include<stdio.h>
#include<malloc.h>

struct Node
{
 int data;
 Node *next;
 Node *prior;      
};

Node* CreateList(Node* &head, int n);
Node* searchk(Node *ptr, Node* &head, int k);
Node* rsearchm(Node *ptr, Node* &head, int m);
void deletenode(Node *ptr);
void show(Node* ptr);

int main()
{
 int n,k,m;
 while(scanf("%d%d%d",&n,&k,&m)==3 && (n||k||m))   
 {
  Node *head=NULL;
  Node *mnode=CreateList(head,n); //show(head);
  Node *knode=head->next;
  bool flag=0;
  while(head->next!=head)
  {
   if(flag) printf(",");
   knode=searchk(knode,head,k); //printf("%d\n",knode->data);
   mnode=rsearchm(mnode,head,m);
   bool b=1;//标记最后两个deletenode别重复free 
   if(knode!=mnode) printf("%3d%3d",knode->data,mnode->data);
   else { printf("%3d",knode->data); b=0;}  
   flag=1;   
   Node *sk=knode,*sm=mnode;//下面两句考虑到next位置会不会恰好是要删除的结点 
   knode=knode->next; while(knode==sm) knode=knode->next;
   mnode=mnode->prior; while(mnode==sk) mnode=mnode->prior;
   
   deletenode(sk);
   if(b) deletenode(sm);                
  }  
  printf("\n");
  free(head);                               
 }//while
 return 0;
}

void show(Node* ptr)
{
 Node *p=ptr->next;
 while(p!=ptr)
 {
  printf("%d\n",p->data);                 
  p=p->next;
 }
}

void deletenode(Node *ptr)
{
 if(ptr==NULL) return;
 ptr->prior->next=ptr->next;
 ptr->next->prior=ptr->prior;
 free(ptr);    
 ptr=NULL;
}

Node* rsearchm(Node *ptr, Node* &head, int m)
{//逆序移动到当前位置的第m个元素,返回该元素位置 
 int i=1;
 Node *p=ptr;
 while(i<m)
 {
  if(p==head) p=p->prior;
  p=p->prior;
  i++;         
 }
 if(p==head) p=p->prior;
 return p;/*
 while(p!=head && i<m)
 {
  p=p->prior;
  i++;             
 }    
 if(p==head) p=p->prior;
 while(i<m)
 {
  p=p->prior;
  i++;         
 } 
 if(p==head) p=p->prior;
 return p;*/
}

Node* searchk(Node *ptr, Node* &head, int k)
{//顺序移动到当前位置ptr的第k个元素,返回该元素位置 (即数的这k个位置包括当前位置)
 int i=1;
 Node *p=ptr;
 while(i<k)
 {
  if(p==head) p=p->next;  //!!! if里面的== 
  p=p->next;
  i++;         
 }
 if(p==head) p=p->next;
 return p;
}

Node* CreateList(Node* &head, int n)
{//顺序创建n个结点,head为头指针,next指向头结点;并返回尾结点指针 
 head=(Node*)malloc(sizeof(Node));
 head->next=NULL; head->data=http://www.mamicode.com/0;>