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

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

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

约瑟夫问题:

在罗马人占领乔塔帕特后,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 条评论
登录 后参与评论

相关文章

来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2498
来自专栏跟着阿笨一起玩NET

c# 使用timer定时器操作,上次定时到了以后,下次还未执行完怎么处理

------解决方案-------------------------------------------------------- 开始的时候,禁用定时器,你...

2641
来自专栏码匠的流水账

spring security reactive获取security context

本文主要研究下reactive模式下的spring security context的获取。

1762
来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2828
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

771
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

702
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1282
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1112
来自专栏一个会写诗的程序员的博客

java.sql.SQLException: connection holder is null

java.sql.SQLException: connection holder is null

1341
来自专栏JMCui

MongoDB系列五(地理空间索引与查询).

Volvo Today, Volvo announced i...

2712

扫码关注云+社区