导入：什么是数据结构，为什么要学习数据结构，约瑟夫环的数组实现

我们不知道怎么造轮子，但是我们起码要知道轮子为什么是圆的。在读这篇文章的你估计在想，为什么会有数据结构这门课，为什么我要学数据结构？现在我解释你们也不会听进去，我简短说一句，如果你是想考研，数据结构必考，如果你想去好一点的公司，数据结构必考，所以以后你也不用再纠结为什么要学数据结构，数据结构有什么用，学就对了。

我们以一个问题引入数据结构基础，先看题目

约瑟夫问题：

在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

问题分析：

我们先画两个圆圈，这两个圆圈内圈是排列顺序，而外圈是自杀顺序，如图1所示

图1 约瑟夫环

这题其实常用的解法就是数学推导或者循环链表，循环链表等到后面才讲，数学推导很多人容易看不懂，所以我们这里选用数组的方法来求解。

用数组求解的基本思想就是用一个一维数组去标记这n个人的状态，默认全为1，也就是都在圈子内，当喊道m的人出圈之后，他的标识则变为0（就是出圈了），同时报数器清0，下一个人从1开始。在每次报数之前要判断他是否在圈子内（也就是他的标识是否为1），如果在圈子里面才会继续报数。定义一个变量记录出圈的人数，出圈的人数等于 n-1时，则游戏结束。

注意：当m = 1的时候，如果没有if(count == m  - 1) break;的判断，会把1到n都输出出来。

代码（C语言）：

#include<stdio.h>
#define N 1000000
int flag[N] = {0};//标记每个人的状态
int main()
{
    int n = 0, m = 0;
    scanf("%d %d", &n, &m);//n是总人数，m是第m个人出列
    int i = 0;
    int count = 0;  //记录出圈的人数
    int num = 0;    //报数器
    for(i = 1; i <= n; i++)
        flag[i] = 1;
    while(count < n - 1)
    {
        for(i = 1; i <= n; i++ )
        {
            if (flag[i] == 1)
            {
                num++;
                if(num == m)
                {
                    printf("%d\n", i);
                    count++;
                    flag[i] = 0;
                    num = 0;
                }
                if(count == n - 1)
                    break;
            }
       
        }
    }
    for(i = 1; i <= n; i++)
        if(1 == flag[i])
            printf("The last one is : %d\n", i);
    return 0;
}

这道题就到这里了，代码实现也给了，不要自己直接复制运行过了就以为自己会了，应该看会，然后自己再敲一遍。另外，如果你真的想了解数据结构有什么用，左转知乎，我在这里不做过多讲解，知乎里大佬解释的肯定比我透彻。到这里还没完，为了方便大家能够更好理解后面的文章，我们先复习一些C语言和拓展一点C++的内容。

C语言复习

l 指针

    C语言的指针可以用于：函数的地址调用、动态分配内存、数组的地址引用

代码示例：

#include <stdio.h>
void main()
{ 
    int x ,*p;
    x = 55;
    p = &x;
    printf ("%d, %u",x,*p) ;
    *p = 65;
    printf ("%d, %u",x,*p) ;
}

注意：（1）指针必须指向对象后才能引用（2）&和*为互补运算

int *p; *p = 2;/*Error!*/

l 指针与数组

数组是同类型的变量的集合，各元素按下标的特定顺序占据一段连续的内存，各元素的地址也连续，指针对数组元素引用非常方便

通过指针引用数组元素可以分为以下三个步骤：

（1）说明指针和数组 int *p,a[10];

（2）指针指向数组 p = a;

（3）通过指针引用数组元素 当指针指向数组的首地址时，则下标为i的元素的地址为：p+i或a+i

引用数组元素也有三种方法：

（1）下标法 a[i]

（2）指针法 *(p+i)

（3）数组名法 *(a+i)

l C语言的动态存储分配函数(<stdlib.h>)

malloc(m)：开辟m字节长度的地址空间，并返回这段空间的首地址

sizeof(x)：计算变量x的长度

free(p)：释放指针p所指变量的存储空间，即彻底删除一个变量

l 结构体

在数据中，经常有一些既有联系，类型有不同的数据，因为类型不同，所以无法单纯的通过数组进行存储及操作，但是它们又需要一起处理。

例如：图书数据

图2 图书数据

    C语言允许用户按自己的需要将不同的基本类型构造成一种特殊类型，即结构体。

图3 结构体定义格式

图4 结构体定义示例

C++拓展

l C++的动态存储分配

格式：new类型名T (初值列表)

功能：申请用于存放T类型对象的内存空间，并依处置列表赋以初值

结果：成功返回指向新分配的内存地址，失败0（NULL）

delete指针p：释放指针p所指向的内存。P必须是new操作的返回值

示例：int *p = new int[10];delete[] p;

l C++中的参数传递

函数调用时传送给形参表的实参必须与形参在类型、个数、顺序上保持一致

参数传递有两种方式：

（1） 传值（参数为整型、字符型等）

把实参的值传给函数局部工作区相应的副本中，函数使用这个副本执行必要的功能，函数修改的是副本的值，实参的值不变

代码示例：

#include <iostream.h>
void swap(float m,float n)
{
    float temp;
    temp = m;
    m = n;
    n = temp;
}
void main()
{
    float a = 3,b = 5;
    swap(a,b);
    printf("%d,%d",a,b);//3,5
}

（2） 传地址（参数为指针变量、参数为引用变量、参数为数组）

1.参数为引用变量

什么是引用？它用来给一个对象提供一个替代的名字

代码示例：

#include<stdio.h>
void main()
{
    int i = 5;
    int &j = i;
    i = 7;
    printf("%d,%d",i,j);7,7
}

    j是一个引用类型，带表i的一个替代名，i值改变时，j值也跟着改变,再看一下传引用的方式作为函数参数

代码示例：

#include <stdio.h>
void swap(float &m,float &n)
{
    float temp;
    temp = m;
    m = n;
    n = temp;
}
void main()
{
    float a = 3,b = 5;
    swap(a,b);
    printf("%d,%d",a,b);//5,3
}

引用类型作为函数形参的几点说明：

（1）传递引用给函数与传递指针的效果是一样的，形参变化实参也发生变化

（2）引用类型做形参，在内存中并没有产生实参的副本，它直接对实参操作；而一般变量做参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本

2.参数为数组

传递的是数组的首地址，并且函数对形参组所做的任何改变都将直接反映到实参组中

代码示例：

#include<stdio.h>
void sub(char b[])
{
    b[0] = 'w';
}
void main()
{
    char a[10] = "h";
    sub(a);
    printf("%c",a[0]);
}