数据结构实验指导(3) 下载本文

3、 冒泡排序

49

4、 快速排序

5、 简单选择排序

6、 堆排序

50

7、 二路归并

51

上机实验报告(仅供参考)

【实验目的和要求】 见实验任务书 【实验题目】

线性表的链式存储结构的实现及其应用

【实验内容】

1.需求分析

本演示程序用TC编写,完成单链表的生成,任意位置的插入、删除,以及确定某一元素在单链表中的位置。

① 输入的形式和输入值的范围:插入元素时需要输入插入的位置和元素的值;删除元素时输入删除元素的位置;查找操作时需要输入元素的值。在所有输入中,元素的值都是整数。

② 输出的形式:在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值,查找操作后显示要查找元素的位置。

③ 程序所能达到的功能:完成单链表的生成(通过插入操作)、插入、删除、查找操作。

④ 测试数据:

A. 插入操作中依次输入11,12,13,14,15,16,生成一个单链表 B. 查找操作中依次输入12,15,22返回这3个元素在单链表中的位置

C. 删除操作中依次输入2,5,删除位于2和5的元素

2.概要设计

1)为了实现上述程序功能,先定义线性表的抽象数据类型: ADT List {

数据对象:D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}

数据关系:R={|ai,ai+1 ∈D, i=1,2,…,n-1,n≥1} 基本操作: InitList(&L)

操作结果:构造一个空的线性表L. InsList(&L,pos,e)

初始条件:线性表L已存在

操作结果:将元素e插入到线性表L的pos位置

DelList(&L,pos,&e)

初始条件:线性表L已存在

52