Linux 实验报告
班级
学号
姓名
硬件三班
161403323
李凤明
实验目的
1、 了解 Linux 编程环境。
2、 掌握在 Linux 环境下编程的常用工具，例如：shell，vim，make，gedit，git
及各种语言的集成开发环境。
3、 了解 Linux 系统的内存、进程、线程、同步、通信的基本原理和其程序在实际中的应用。
4、 掌握 Linux 环境下的应用程序设计、开发和项目管理。
5、 通过 8 学时的实验，在 Linux 环境下设计并实现一个代码量不少于 2000 行的项目。
实验背景
在 Linux 环境下运用 gedit 工具，通过 C 语言编程实现四个程序，分别为：堆排序、用栈实
现表达式求值、B+树和红黑树。
实验原理
1、堆排序
利用大顶堆（或小顶堆）堆顶记录的是最大关键字（或最小关键字）这一特性，使得每次从
无序中选择最大记录（或最小记录）变得简单。
以大顶堆为例，首先要根据该数组元素构建一个完全二叉树，之后构造初始堆，从最后一
个非终端节点调整到根结点，每次调整都是从父节点、左孩子节点和右孩子节点三者中选择最
大者跟父节点进行交换，交换之后可能造成呗交换孩子节点不满足堆的性质，因此每次交换之
后要重新对被交换的孩子节点进行调整。构造了初始堆之后再进行排序，程序完成。
2、用栈实现表达式求值
使用的算法叫做“算符优先法”。
根据算术四则运算规则得出相继出现的两个运算符 a 和 b 的优先关系，如下表所示
a>b 表示 a 的优先权高于 b
a<b 表示 a 的优先权低于 b
a=b 表示 a 的优先权等于 b
空白则表示该关系不存在
b
a
+
-
*
/
(
)
#
+
>
>
<
<
<
>
>
-
>
>
<
<
<
>
>
*
>
>
>
>
<
>
>
/
>
>
>
>
<
>
>
(
<
<
<
<
<
=
>
)
>
>
>
>
>
#
<
<
<
<
<
=
