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

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

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

约瑟夫问题:

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

相关文章

来自专栏Java学习网

Java 8的函数式编程学习

Java 8的函数式编程学习 函数式编程语言是什么? 函数式编程语言的核心是它以处理数据的方式处理代码。这意味着函数应该是第一等级(First-class)的...

2557
来自专栏SHERlocked93的前端小站

JS 原型模式

原型模式(Prototype pattern),用原型实例指向创建对象的类,使用于创建新的对象的类的共享原型的属性与方法。

1191
来自专栏分布式系统和大数据处理

四种简单的排序算法

我觉得如果想成为一名优秀的开发者,不仅要积极学习时下流行的新技术,比如WCF、Asp.Net MVC、AJAX等,熟练应用一些已经比较成熟的技术,比如Asp.N...

1172
来自专栏闰土大叔

闰土说JS进阶之变量

前言 前端世界如此喧嚣,能进阶的何其稀少。大家好,你们的闰土哥在沉寂了数月之后又回来了!(此处应有掌声~~~) 前段时间在群里关于“闰土去哪儿了”的话题,让我既...

34410
来自专栏编程

Python读书笔记9

我们针对列表需要进行整体的排序,今天就和大家聊一聊列表的排序应用。 一、永久性排序 什么是永久性排序呢,之前很多方法比如针对字符串的title方法,针对列表的重...

1798
来自专栏微信公众号:Java团长

JAVA之旅(一)——基本常识,JAVA概念,开发工具,关键字/标识符,变量/常量,进制/进制转换,运算符,三元运算

比如6:6/2 = 3 余 0 3 / 2 = 1 余 1 那就是从个位数开始011,读起来就是110了

1471
来自专栏java学习

每日一练(2017/5/18)

Java基础 | 数据库 | Android | 学习视频 | 学习资料下载 课前导读 ●回复"每日一练"获取以前的题目! ●答案公布时间:为每期发布题目的第二...

2525
来自专栏用户2442861的专栏

sizeof小览

http://blog.csdn.net/scythe666/article/details/47012347

651
来自专栏猿人谷

怎样写解释器

解释器是比较深入的内容。虽然我试图从最基本的原理讲起,尽量让这篇文章不依赖于其它的知识,但是这篇教程并不是针对函数式编程的入门,所以我假设你已经学会了最基本的 ...

2047
来自专栏java学习

Java每日一练(2017/7/21)

聊天系统 ●我希望大家积极参与答题!有什么不懂可以加小编微信进行讨论 ★珍惜每一天,拼搏每一天,专心每一天,成功每一 如果你是初学者,或者是自学者!你可以加小编...

3324

扫码关注云+社区