微光工作室

Appearance

标题

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

Step 1. 指针与结构体 ​

什么是指针？ ​

指针是C语言提供的一种特殊变量类型，用于存储内存地址。C语言中为指针提供了取地址（&）和解引用（*）运算符，以及算术运算支持（通常都涉及数组）。尝试了解它们的用法以及指针的相关知识，回答下列问题：

  1. 如何在C语言中定义指针变量？指针变量的大小是固定的吗？其大小与什么有关？
  2. 写出以下代码的输出结果，并解释原因。
c
int x = 10;
int* p = &x;
*p = 20;

int arr[3] = {3, 6, 9};
int *q = arr;
int y = ++*arr  +  *++q;

printf("%d %d", x, y);
int x = 10;
int* p = &x;
*p = 20;

int arr[3] = {3, 6, 9};
int *q = arr;
int y = ++*arr  +  *++q;

printf("%d %d", x, y);

  1. 什么是野指针？简述其危害。如何避免产生野指针？

  2. 尝试设计一个真正有效的swap()函数

什么是结构体？ ​

结构体是用户自定义的复合数据类型，可包含不同数据类型的成员。请自行了解结构体的相关内容，回答下列问题：

  1. 请你完成一个PerInfo结构体的定义，成员组成如下。了解一下typedef关键字与结构体的一般用法，利用typedef为你刚刚定义的结构体取一个别名。提交最终的结构体定义。
1. 个人姓名（字符型数组，长度为10个字节）
2. 性别（字符型）
3. 年龄（整型）
4. 身高（双精度浮点型）
1. 个人姓名（字符型数组，长度为10个字节）
2. 性别（字符型）
3. 年龄（整型）
4. 身高（双精度浮点型）

  1. 了解并说明结构体指针的含义。

  2. 了解一下结构体的内存对齐规则，据此计算一下你刚刚定义的结构体占用字节的大小（可用sizeof运算符验证计算结果）。提交计算过程。(此外，你还可以尝试更改一下结构体中成员的定义顺序，看看对结构体占用字节数的影响)

Step 2. 基础数据结构 ​

什么是数据结构 ​

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

常用数据结构类型 ​

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

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

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

  1. 简述数组和链表的存取机制。
  2. 简述单向链表节点的结构特点。定义一个只存储一个整数的单向链表节点。
  3. 简述栈与队列的特点。了解栈基于数组的实现。
  4. 如何使用C语言保存一张图的信息？树呢？（在本题范围内，此内容简单了解即可）

Step 3. 综合应用 ​

没有人一直是大学生，但一直有人是大学生。小强就是一位刚刚考入格里姆（glimmer）大学的出色学子，为了提前应对大学学习，小强在学校论坛发表了一个帖子，希望可以有热心的学长学姐伸出援手。很快，就有“勤学部”的学长留言：“私我，有资料”。小强喜出望外，立刻私信了这位“热心”学长。学长语气亲切，自称是“勤学部”的骨干，手握大量内部复习资料、历年考题和教授讲义，打包价只要“一点点象征性的辛苦费”。为了学业，小强咬咬牙，按照学长的指示，通过一个隐蔽的链接支付了费用。钱刚转过去，学长发来了一个加密压缩包。小强满怀期待地解压，却发现里面空空如也！

他愤怒地截图质问，对方却已将他拉黑。小强的心沉到了谷底，刚入学就遭遇这种糟心事，学费还没交，生活费就先被骗走一笔！就在小强懊恼不已时，他的手机突然收到一条陌生短信：

不要轻信网络陌生转账要求！

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

By the way：在各个Q群中打着“勤学部”旗号的绝大部分是骗子，望周知。

Part 1. 链起来再说 ​

在Step 2中，你尝试定义了一个只存储一个整数的单向链表节点，接下来，我们将基于此实现一个单向链表及一些基本操作。要求如下：

  1. 使用你在上一步定义的单向链表节点作为链表节点。
  2. 链表初始状态为头指针Head指向一个data值为0的节点，此时该节点为链表唯一节点。
  3. 你需要实现该链表的如下操作：

H操作：

H DATA1 DATA2 DATA3
H DATA1 DATA2 DATA3

该操作代表从链表的头部依次插入数据为DATA3、DATA2、DATA1的三个节点，并将头指针最终指向数据为DATA1的节点。

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

T操作：

T DATA1 DATA2 DATA3
T DATA1 DATA2 DATA3

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

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

D操作：

D LOCATION
D LOCATION

该操作代表删去链表中从头指针指向节点开始第LOCATION位的节点。若删除节点为头节点，则头指针指向头节点的后继。

R操作：

R
R

该操作代表将链表反转。

假设原链表为Head → 1 → 2 → 3 → Ø， 则反转后为Head → 3 → 2 → 1 → Ø

命令操作输入依次为：

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

请将完成的代码文件保存，从头节点开始，遍历链表输出其节点的data值于Numbers.txt文件中。

Part 2. 一栈到底 ​

这一小节主要围绕栈进行操作，开始前，请自行学习掌握栈的具体实现。在上一小节操作得到的Numbers.txt文件中，你已经获得了一串由数字组成的字符串（下称为数字串），现在请结合文件CS-EASY-02-2.txt文件中的字符信息（下称为密文串），完成下列操作。

栈的初始状态为空

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

每次执行弹出操作，从栈顶将一个字符弹出并输出该字符；如果弹出时栈为空，则输出!。

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

  • 数字0代表“读取栈顶字符并输出该字符（当前栈顶字符不弹出）”，数据保证此时栈不为空。
  • 数字1代表“执行一次压入操作”
  • 数字2代表“执行两次弹出操作”

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

本题提交方式 ​

提交点这里

出题人联系方式 ​

你好......再见 QQ：195225527