《数据结构》实验指导书(6)

六、选做实验内容

（可利用课外实验学时完成）

实验六 排序

一、实验目的

1、掌握常见的排序算法(插入排序、交换排序、选择排序、

归并排序、基数排序等)的思想、特点及其适用条件。 2、能够分析各种算法的效率

3、熟练掌握常见的排序算法的程序实现。 二. 实验学时：

课内实验学时：2学时 课外实验学时：4学时 三、备选实验题目

1．常见排序算法实现（实验类型：验证型）

1）问题描述：输入一组关键字序列分别实现下列排序: （1）实现简单选择排序、直接插入排序和冒泡排序。 （2）实现希尔排序算法。 （3）实现快速排序算法。 （4）实现堆排序算法。 *（5）快速排序的非递归算法。 （6）实现折半插入排序。

（7）在主函数中设计一个简单菜单，分别测试上述算法。

24

2) 实现提示：

? 数据类型定义（C语言）

# define MAXSIZE 100 /*参加排序元素的最大个数*/ typedef struct list { int key; }RedType; typedef struct {

RedType r[MAXSIZE+1];

int length; /*参加排序元素的实际个数*/ }SqList;

? 算法5可以借助栈实现。 3）注意问题：

? 在RedType中增加一个数据项验证各种排序算法的稳定性。

? 注意理解各种算法的思想、了解算法的适用情况及时间复杂度，能够根据实际情况选择合适的排序方法。

2．统计成绩：（实验类型：综合型）

1）问题描述：给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：

? 按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次； ? 按名次列出每个学生的姓名与分数。

2）基本要求：学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出进行格式控制。

25

实验七 数组和广义表

一、实验目的

1、掌握稀疏矩阵的表示方法及其运算的实现

2、实现稀疏矩阵在三元组、十字链表等表示下的各运算并

分析其效率

二. 实验学时：

课外实验学时：4学时 三、备选实验题目：

1．稀疏矩阵运算器（实验类型：综合型）

1）问题描述：稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。本实验的主要任务是实现一个能进行稀疏矩阵基本运算的运算器。

2）实验要求：

? 以“带行逻辑链接信息” 的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。 ? 测试数据：

10 0 0 0 0 0 10 0 0 0 0 9 + 0 0 -1 = 0 0 8 -1 0 0 1 0 -3 0 0 -3 10 0 0 0 10 0 0 9 + 0 -1 = 0 10 -1 0 1 -3 -2 3 26

3 0 0 4 -3 0 0 1 4 2 0 0 0 0 8 0 × 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 70 0 0 0 0 -6 0 = 8 0 0 0 1 0 0 0 0 3）实现提示 ? 首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20。

? 程序可以对三元组的输入顺序加以限制，例如，按行优先。注意研究教科书5.3.2节中的算法，以便提高计算效率。

? 在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放。

实验八 串

一、实验目的

1、理解串的模式匹配算法（包括KMP算法）。 2、明确串也是特殊的线性表，掌握其特殊性所在。 3、熟悉一般文字处理软件的设计方法、较复杂问题的分解

方法。

二. 实验学时：

课外实验学时：6学时 三、备选实验题目：

1．实现一个简单行编辑程序（实验类型：综合型）

27

1）问题描述：文本编辑程序利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序为行编辑程序。

被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的作法既不经济，也不总能实现。一种解决逐段编辑。任何时刻只把待编辑文件的一段放在内存，称为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不超过320个字符，很少超过80个字符。

2）实验要求：实现以下4条基本编辑命令：

? 行插入。格式：i<行号><回车><文本>，<回车>

将<文本>插入活区中第<行号>行之后。

? 行删除。格式：d<行号1>[<空格><行号2>]<回车>

删除活区中第<行号1>行（到第<行号2>行）。 例如：“d10Enter”和“d10 14Enter”。 ? 活区切换。格式：n<回车>

将活区写入输出文件，并从输入文件中读入下一

段，作为新的活区。

? 活区显示。格式：p<回车>

逐页地（每页20行）显示活区内容，每显示一页之后请用户决定是否继续显示以后各页（如果存在）。印出的每一行要前置行号和一个空格符，行号固定占4位，增量为1。

? 各条命令中行号均须在活区中各行行号范围之内，只有插入命令的行号要以等于活区第一行行号减1，表示插入当前屏幕中第一行之前，否则命令参数非法。 3）实现提示

? 设活区的大小用行数ActiveMaxLen（可设为100）来描述。考虑到文本文件行长通常为正态分布，且峰值

28

在60到70之间，用320×ActuveMaxLen大小的字符数组实现存储将造成大量浪费。可以以标准行块为单位为各行分配存储，每个标准行块可含81个字符。这些行块可以组成一个数组，也可以利用动态链表连接起来。一行文字可能占多个行块。行尾可用一个特殊的ASCII字符（如（012）8）标识。此外，还应记住活区起始行号。行插入半引起随后各行行号的顺序下推。

? 初始化函数包括：请用户提供输入文件名（空串表示无输入文件）和输出文件名，两者不能相同。然后尽可能多地从输入文件中读入各行，但不超过ActiveMaxLen-x。x的值可以自定，例如20。 ? 在执行行插入命令的过程中，每接收到一行时都要检查活区大小是否已达ActiveMaxLen。如果是，则为了在插入这行之后仍保持活区大小 不超过ActiveMaxLen,应将播入点之前的活区部分中第一行输出到输出 文件中，若插入点为第一行之前，则只得将新插入的这一行输出。

? 若输入文件尚未读完，活区切换命令可将原活区中最后几行留在活区顶部，以保持阅读连续性；否则，它意味着结束编辑或开始编辑另一个文件。 ? 可令前三条命令执行后自动调用活区显示。

29

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《数据结构》实验指导书(6)在线全文阅读。