华为笔试准备 --- 约瑟夫环

//问题：程序员面试宝典174

#include<stdio.h>

/*************************************************************
编程思路：
1.建立起n个节点的循环链表
2.找出开始报数的第k个人
3.不断的从链表删除节点，直到链表为空，可以就用节点数n做条件变量

出错的地方
1.控制变量选的不好
2.若删除一个节点，要把这个节点之前的节点用一个临时变量保存起来，
  我之前保存了是这个节点的备份，而不是之前的节点，所以出错。
3.在控制删除节点的时候，对于m为>2的情况应多一步处理，要是m为1，
那么直接跳过判断，所以取用了j=m-1
**************************************************************/
typedef struct node
{
    struct node *next;
    int data;
}node;

//n个人，k开始报数，m出列
void joseph(int n, int k, int m)
{
    //1.建立n个节点的循环链表
    node *p, *t, *cur, *pre;
    int i, j;

    p = (node *)malloc(sizeof(node));
    p->data = 0;
    p->next = p;

    printf("head established successful! data = %d\n", p->data);

    for(i = 1; i < n; i++)
    {
        t = (node *)malloc(sizeof(node));
        t->data = i;
        t->next = p->next;
        p->next = t;
        p = t;
        printf("Node established successful! data = %d\n", p->data);
    }

    //2.找出第k个人,用cur表示,准确说找到第k-1个人，用pre表示

    cur = NULL;

    while(k--)
    {
        pre = p;//因为p在上面申请循环链表的时候是指向最后一个节点,这个节点在这保存为下文删除时备份
    //    cur = p->next;
        p = p->next;
    }

    //printf("cur->data = %d\n",cur->data);
    while(n--)
    {
        j = m - 1;        //这一步很重要
        cur = pre->next;
        printf("n = %d\n", n);
        while(j--)
        {
            pre = cur;
            cur = cur->next;
        }
        pre->next = cur->next;
        printf("cur->data = %d\n",cur->data);
        free(cur);

    }
}

int main(int argc, char argv)
{
    joseph(10, 5, 6);
    while(1);

}

华为题目
 约瑟夫问题


问题描述： 
输入一个由随机数组成的数列（数列中每个数均是大于0的整数，长度已知），和初始计数值m。
从数列首位置开始计数，计数到m后，将数列该位置数值替换计数值m，并将数列该位置数值出列，
然后从下一位置从新开始计数，直到数列所有数值出列为止。如果计数到达数列尾段，则返回数列首位置继续计数。
请编程实现上述计数过程，同时输出数值出列的顺序


比如： 输入的随机数列为：3,1,2,4，初始计数值m=7，从数列首位置开始计数（数值3所在位置）
第一轮计数出列数字为2，计数值更新m=2，出列后数列为3,1,4，从数值4所在位置从新开始计数
第二轮计数出列数字为3，计数值更新m=3，出列后数列为1,4，从数值1所在位置开始计数
第三轮计数出列数字为1，计数值更新m=1，出列后数列为4，从数值4所在位置开始计数
最后一轮计数出列数字为4，计数过程完成。
输出数值出列顺序为：2,3,1,4。


 要求实现函数： 
void array_iterate(int len, int input_array[], int m, int output_array[])
【输入】 int len：输入数列的长度；
int intput_array[]：输入的初始数列
int m：初始计数值
【输出】 int output_array[]：输出的数值出列顺序
【返回】 无


//解题思路，倘若能将第一个问题写出来，那么对于华为的题目只是相当于多个数组当一层封装罢了
//另外还有一点是这里的m是根据输出变化的，当然实现起来也比较简单

/**********************************************************************
void array_iterate(int len, int input_array[], int m, int output_array[])
【输入】 int len：输入数列的长度；
int intput_array[]：输入的初始数列
int m：初始计数值
【输出】 int output_array[]：输出的数值出列顺序
【返回】 无
***************************************************************************/

#include<stdio.h>

typedef struct node{
    int data;
    struct node *next;
}node;

node *node_creat(int input_array[], int len)
{
    node *p, *t;
    int i;

    p = (node *)malloc(sizeof(node));
    p->next = p;

    for(i = 1;i < len; i++)
    {
        t = (node *)malloc(sizeof(node));
        t->next = p->next;
        p->next = t;
        p = t;
    }
    return p;
}

void array_iterate(int len, int input_array[], int m, int output_array[])
{
    int i, j, k;

    node *pre, *cur, *init, *tmp;

    init = node_creat(input_array, len);

    tmp = init->next;

    for(i = 0; i < len; i++)
    {
        tmp->data = input_array[i];
        tmp = tmp->next;
    }
    //根据输入的数组对循环链表进行初始化

    pre = init;
    k = 0;//k is used as output_array
    while(len--)
    {
        j = m - 1;
        cur = pre->next;

        while(j--)
        {
            pre = cur;
             cur = cur->next;
        }

        pre->next = cur->next;
        m = output_array[k]= cur->data;

        printf(" output_array[%d] = %d\n",k, output_array[k]);
        k++;
        free(cur);
    }
}

int main(int argc, char **argv)
{
    int input_array[]={3,1,2,4};
    int len=4;
    int m=7;

    int output_array[4];
    array_iterate(len, input_array, m, output_array);
    while(1);
}

最后，还有一种考法就是说刚开始从第k个，可见，就把我们第一种方法里的判断位置的方法应用进来即可。