算法:C语言实现 (3)数组和链表的使用

数组的使用:求素数 埃拉托色尼筛法:

/***************************************************************

  这个程序展示了数组的应用,快速的访问数组内的元素
  用数组的值作为标志位, 而使用了下表来保存素数, 这样的设计很奇妙
  
****************************************************************/

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

#define N 100

int main()
{
    int i,j;
    int *f = (int *)malloc(N*sizeof(int));

    for(i = 0; i < N; i ++) f[i] = 1;

    for (i = 2; i < N; i++)
        if (f[i])
            for (j = i; j*i < N; j++)
                f[i*j] = 0;

    for (i = 1; i < N; i++)
        if (f[i])
            printf("%4d
", i);

    return 0;
}

链表的使用:约瑟夫环:

/*******************************************************************************************************
    约瑟夫环问题(Josephus)
    用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。（约瑟夫环问题 Josephus）
    建立一个有N个元素的循环链表，然后从链表头开始遍历并记数，如果计数i==m(i初始为1)踢出元素，继续循环，
    当当前元素与下一元素相同时退出循环。
********************************************************************************************************/

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

typedef struct node *link;
struct node
{
    int item;
    link next;
};

int main(char argc, char* argv[])
{
    link t = (link) malloc(sizeof(*t)), p = t;
    t->item =1;    t->next = t;
    int i , N = atoi(argv[1]), M = atoi(argv[2]);

    for (i = 2; i <= N; i++)
    {
        p = (p->next=(link)malloc(sizeof(*p)));
        p->item = i;
        p->next = t;
    }

    while (p != p->next)
    {
        for (i = 1; i < M; i++)
            p = p->next;        
        printf("这次被杀掉的人是:%4d
", p->next->item);
        p->next = p->next->next;
    }
    
    printf(" %4d
",p->item);

    return 0;
}