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

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

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

约瑟夫问题:

在罗马人占领乔塔帕特后,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]);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Laoqi's Linux运维专列

Python for 循环语句

3528
来自专栏Android机动车

Java 基础(六)——集合源码解析 Queue

Queue继承自 Collection,我们先来看看类结构吧,代码量比较少,我直接贴代码了。

541
来自专栏云霄雨霁

Java--多态性之内部类和匿名类

1516
来自专栏数据结构与算法

约瑟夫环 队列+链表

设有n个人依次围成一圈,从第1个人开始报数,数到第m个人出列,然后从出列的下一个人开始报数,数到第m个人又出列,…,如此反复到所有的人全部出列为止。设n个人的编...

3397
来自专栏闵开慧

java概念2

1 文件操作 public class FileTest { public static void main(String[] args) throw...

3228
来自专栏java工会

Java HashMap 简介与工作原理

20110
来自专栏静默虚空的博客

查找三 哈希表的查找

要点 哈希表和哈希函数 在记录的存储位置和它的关键字之间是建立一个确定的对应关系(映射函数),使每个关键字和一个存储位置能唯一对应。这个映射函数称为哈希函数,根...

2015
来自专栏hbbliyong

c++ list, vector, map, set 区别与用法比较

List封装了链表,Vector封装了数组, list和vector得最主要的区别在于vector使用连续内存存储的,他支持[]运算符,而list是以链表形式实...

6949
来自专栏IT可乐

Java数据结构和算法(九)——高级排序

  春晚好看吗?不存在的!!!   在Java数据结构和算法(三)——冒泡、选择、插入排序算法中我们介绍了三种简单的排序算法,它们的时间复杂度大O表示法都是O(...

3456
来自专栏工科狗和生物喵

【计算机本科补全计划】Java学习笔记(五) 运算符

正文之前 本文属于流水账,因为早就在C++里面学过了。Java基本是继承了C++的那些,所以贴个代码应该就OK了?,当然,有点特有的运算符我还是得解释下的。毕竟...

3335

扫码关注云+社区