微光工作室

Appearance

标题

CS-EASY-02 基础数据结构 ​

什么是数据结构 ​

在计算机科学中，数据结构是一种数据组织、管理和存储的格式。它是相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术相关。

常用数据结构类型 ​

经常使用的基础数据结构主要包括：

  • 线性表
    • 顺序表（数组）
    • 链表
  • 栈
  • 队列
  • 图

请完成对以上数据结构的学习，尝试回答下列问题：

  1. 什么是随机存取？这个性质属于哪种线性表的特征？
  2. 什么是指针？如何在C语言中定义指针变量？指针变量的大小是固定的吗？
  3. 你能为不同的数据结构设想出适用的具体情况吗？
  4. 如何使用C语言保存一张图的信息？

以上仅作为导学用问题，深入理解和运用数据结构，需要在编程实践和认真思索中对它们的性质和实现加以深化。

相关资料：

C 指针 | 菜鸟教程 (runoob.com)

数据结构的应用 ​

没有人一直会是大学生，但一直会有人是大学生。小强就是一位刚刚考入格里姆（glimmer）大学的出色学子，为了让自己的大学生活更加丰富，在拿到新电脑后，小强越过重重困难，终于下载了正版”思题目“学习软件！可喜可贺可喜可贺！但是，思题目上的课程都是先收费再学习，这让小强打了退堂鼓。为了不给家里增添经济负担，小强决定在某宝低价购买“汽车工程与审美艺术”课程的盗版入库，但是，无良商家收到钱后，只给了他这样一条短信：

不要花钱买盗版游戏！

原来，这个无良卖家的账号已经被大黑阔小明盗走了。在原路退回小强花的冤枉钱之后，小明决定出一道题考考小强。

Part 1.圈圈圆圆圈圈 ​

在这一小节，你将实现一个环形链表，它的具体实现方式可以粗略地理解为在单链表的基础上，将链表尾节点的后继指向该链表的头节点。因此，你可以对单链表进行操作，并在最后完成环形链表的构建。要求如下：

  1. 对于每一个链表节点，仅存储一个正整数作为data信息
  2. 起始状态下，链表仅包含一个data等于1的节点作为头节点
  3. 你需要实现该链表的如下操作：

H操作：

H DATA1 DATA2 DATA3
H DATA1 DATA2 DATA3

该操作代表从链表的头部依次插入数据为DATA3、DATA2、DATA1的三个节点。

该操作进行后的示例为DATA1->DATA2->DATA3->XXX...

T操作：

T DATA1 DATA2 DATA3
T DATA1 DATA2 DATA3

该操作代表从链表的尾部依次插入数据为DATA1、DATA2、DATA3的三个节点。

该操作进行后的示例为...XXX->DATA1->DATA2->DATA3->NULL

D操作：

D LOCATION
D LOCATION

该操作代表删去链表中从头开始第LOCATION位的节点。

C操作：

C
C

该操作代表将尾节点的后继指向头节点。

命令操作输入依次为:

T 3 1 1
H 1 2 1
T 2 2 1
D 9
......(完整内容参见招新群文件CS-EASY-02-1.txt)
T 3 1 1
H 1 2 1
T 2 2 1
D 9
......(完整内容参见招新群文件CS-EASY-02-1.txt)

请将完成的代码文件保存，尝试按照一定顺序将该链表的元素进行输出。

Tips：对于较长的文件输入，除了直接将数据粘贴进终端以外，也可以采用文件流的形式进行程序的输入输出。感兴趣的同学可以学习。

Part 2.我和约瑟夫有个约会 ​

约瑟夫问题是小明很喜欢的一个数学问题，它的一种表述形式为：N个犯人围成环形，从某个位置开始报数，每次报到M的人出队接受刑罚，然后继续报数，求解最后剩下的犯人最早位于环的第几个位置。

小明决定将这个问题升级后作为第二部分的考验：

对于第一部分获得的环形链表，从唯一的数字3的位置开始“报数”，对于“报数”的第m轮，报到m的节点会从链表中删除并将其data输出。（可以发现data为3的这个节点一定会被首先删除掉）直到所有节点均被从环形链表中删除，停止该程序。

请编写模拟这个过程的代码，并尝试将文件的输出结果保存在Josephus.out文件中。

Part 3.栈个痛快 ​

这一小结主要围绕栈（zhan，四声）这一数据结构进行操作。在Josephus.out文件中，你已经获得了由一串数字组成的字符串（下称为数字串），现在请结合文件CS-EASY-02-2.txt文件中的字符信息（下称为密文串），完成下列操作。

栈的初始状态不含有任何一个元素

每次执行压入操作，将按照密文串字符的排列顺序依次进行压入，每个字符仅会被压入一次。

每次执行弹出操作，从栈顶将一个字符弹出并输出该字符，数据保证不会在空栈情况下进行弹出。

数字串的信息标示着栈的压入/弹出，具体而言

  • 奇数位置的数字a代表“执行a次压入操作”
  • 偶数位置的数字b代表“执行b次弹出操作”

请结合两串信息进行最终的解密。并将你的解密过程与最终的结果整理成文档提交至Github。

本题提交方式 ​

提交点这里

主题示例：2024090101012-张三-CS-02

本题出题人：奶绿丶（单艺豪） QQ：3073494764