谁帮我做一下链表这道题 - 编程论坛

#2

hzh5122010-05-06 13:37

简单的约瑟夫环，楼主这也要别人写呀！

程序代码：

#include <stdio.h>
#include <stdlib.h>
typedef struct list
{

int num ;

struct list *next ;

}LIST ;
int main(void)
{

    LIST *head=NULL,*pre=NULL,*post=NULL, *start=NULL, *temp=NULL;
    long i, m, n, x;

printf("n=");
    scanf("%ld",&n);

printf("\nm=");
    scanf("%ld",&m) ;

printf("\n");
    if( n <= 1)

{
        printf("1 ");
        return 0;
    }

    /**//*建立循环链表*/
    pre = (LIST *)malloc(sizeof(LIST));
    pre->num = 1 ;
    pre->next = NULL ;

head = pre ;
    post = pre ;
    for(i=2 ; i<= n; i++)

{
  pre = (LIST *)malloc(sizeof(LIST));
  pre->num = i;
  pre->next= NULL ;
  post->next=pre ;
  post = pre ;
    }
    post -> next = head ; /**//*将最后一个结点的指向头，这样就构成了循不链表*/
    pre= head ;

i--;

while(i>0)

{
  printf(" %d ",pre->num);
  pre=pre->next;
  i--;

}

printf("\n");

printf("\n从第几个人开始：");

scanf("%d",&x);

int count=n;

while(count>0)

{
  if(head->num==x)
  {
   pre=post;
   start=head;
   break;
  }
  if(pre->next->num==x)
  {
   start=pre->next;
   break;
  }
  pre=pre->next;
  count--;

}

if(count==0)

{
  printf("\n  开始人错误\n");
  system("pause");
  exit(1);

}
    while (start->next != start)

{
  for(i=1; i < m ; i++)
  {
   pre = start ;
   start = start->next;
  }
  temp=start;
  start=start->next;
  pre->next=start;
  delete temp;
    }
    printf("last=%d \n",pre->num);

    return 0 ;

}

#3

2010-05-06 14:59

真受不了！

#4

hzh5122010-05-06 15:07

你有啥受不了的，

用数组不更好写吗！！

现在的学生真是没法说！！唉！！

#5

2010-05-06 16:27

如果只需要知道最后一个人是谁，可以用如下的方法：

#include <stdio.h>
int main(void)
{
   int n, m, i, s=0;
   printf ("N M = "); scanf("%d%d", &n, &m);
   for (i=2; i<=n; i++) s=(s+m)%i;
   printf ("The winner is %d\n", s+1);
}

#6

tfxanxing2010-05-08 19:31

楼上的这个求最后的程序太巧妙了，有什么算法的吗？

#7

tfxanxing2010-05-08 19:34

问一下二楼的
typedef struct list // 为什么要加 typedef，有什么作用吗，不加不是也行的吗？？？？、
{
int num ;
struct list *next ;

}LIST ;

#8

tfxanxing2010-05-08 20:54

我来试试：

#include<iostream>
using namespace std;

struct list{
    int num;
    list *next;
};
int main()
{
    //顺序存储结构用数组实现:

    int a[1000];            //申请较大的数组
    int n,m;
    int count,temp_m;        //count存储输出的编号个数,temp_m数数
    cout<<"Input n and m:";
    cin>>n>>m;
    if(n==1)
    {
        cout<<"the number is 1.\n";
        return 0;
    }
    int i;
    for(i=1;i<=n;i++)        //把1-n标记
    {
        a[i]=1;
    }
    i=1;
    count=n;
    temp_m=0;
    cout<<"用顺序结构实现输出顺序号码:"<<endl;
    while(count>0)
    {
        if(a[i]==1)
        {
            temp_m++;
            if(temp_m%m==0)
            {
                cout<<i<<" ";
                a[i]=0;
                count--;
            }
        }
        i++;
        if(i>n)            //循环的效果
            i=1;
    }
    cout<<endl;

    ///////用链表实现:///////////////////////////////
    cout<<"在循环链表上实现输出为:"<<endl;
    list *head,*p1,*p2;
    p1=p2=new list[1];
    head=p1;
    head->num=1;
    count=1;
    while(count<n)        //创建链表
    {
        p2=new list[1];
        p1->next=p2;
        p1=p2;
        count++;
        p1->num=count;
    }
    p1->next=head;

    temp_m=0;
    while(count>0)
    {
        if(head->num)
        {
            temp_m++;
            if(temp_m%m==0)
            {
                cout<<head->num<<" ";
                head->num=0;
                count--;
            }
        }
        head=head->next;
    }
    cout<<endl;
    cout<<"ok!\n";
    system("pause");        //系统程序
    return 0;
}

#9

hs20092010-05-09 16:28

#include<stdio.h>
typedef struct node
{
    int data;
    struct node*next;
}Lnode;
Lnode*creat(int n)
{
    Lnode*p,*r,*h;
    int i=0;
    h=(Lnode*)malloc(sizeof(Lnode));
    h->data=1;
    r=h;
    for(i=2;i<=n;i++)
    {

        p=(Lnode*)malloc(sizeof(Lnode));
        r->next=p;
        p->data=i;
        r=p;
    }
    r->next=h;
    return h;
}
jeseph(Lnode*p,int m)
{
    Lnode*q;int j=0;
    printf("outqueue order:");
    do
    {
        j++;
        if(j==m-1)
        {
            q=p->next;
            p->next=q->next;
            printf("%5d",q->data);
            j=0;
            free(q);
        }
        p=p->next;
    }while(p->next!=p);
    printf("%5d\n",p->data);
    free(p);
}
main()
{
    Lnode*h;
    int m,n;
    printf("Input n,m=");
    scanf("%d%d",&n,&m);
    h=creat(n);
    jeseph(h,m);
}

#10

2010-05-09 20:41

顺序结构
#include <stdio.h>
#define maxsize 100
void main()
{
int i,j,k,m,n;
int array[maxsize];
k=0;
for(i=0;i<maxsize;i++) array[i]=i+1;
i=0;
scanf("%d",&m);scanf("%d",&n);
if(m<=1||n<=1||m>maxsize) { printf("Error");exit(0); }
for(i=0;m>1;)
  {
   if(k==n-1)
    {
     printf("%d ",array[i]);
     for(j=i;j<m-1;j++) array[j]=array[j+1];
     m--;k=0;
     }
   k++;i=(i+1)%m;
   }
  printf("%d ",array[0]);
  getch();
}
链表：
#include <stdio.h>
#define maxsize 100
void main()
{
int i,j,k,m,n;
int array[maxsize];
k=0;
for(i=0;i<maxsize;i++) array[i]=i+1;
i=0;
scanf("%d",&m);scanf("%d",&n);
if(m<=1||n<=1||m>maxsize) { printf("Error");exit(0); }
for(i=0;m>1;)
  {
   if(k==n-1)
    {
     printf("%d ",array[i]);
     for(j=i;j<m-1;j++) array[j]=array[j+1];
     m--;k=0;
     }
   k++;i=(i+1)%m;
   }
  printf("%d ",array[0]);
  getch();
}