实 验 报 告
课程名称
数据结构
实验项目
线性表的实现及应用
实验仪器
PC 机一台
学 专
院_____ 业
班级/ 学号 姓名
实验日期 成
绩
指导教师
北京信息科技大学
信息管理学院
(数据结构课程上机 )实验报告
专业:
班级: 学号: 姓名: 成绩:
实验名称 线性表的实现及应用 实验地点 实验时间
1. 实验目的:
(1) 理解用顺序表实现线性表的特点; 熟练掌握顺序表的基本操作; 学会利用顺序表解决实际应用问题。
(2) 熟练掌握单链表的使用; 理解用链表实现线性表的特点; 了解链表的多种形式;学会利用单链表解决实际应用问题。
2. 实验要求:
(1)
学时为 8 学时;
(2)
能在机器上正确、调试运行程序; 本实验需提交实验报告;
(3)
(4)
实验报告文件命名方法:数据结构实验 _信管 16xx_学号 _姓名 .doc。
3. 实验内容和步骤:
第一部分 顺序表的实现与应用
(1)基于顺序表实现线性表的以下基本操作:
public interface LList
{ // 线性表接口,泛型参数 T 表示数据元素的数据类型
//判断线性表是否空 boolean isEmpty();
//返回线性表长度 int size();
//返回第 i(i ≥0)个元素 T get(int i);
//设置第 i 个元素值为 x void set(int i, T x);
//插入 x 作为第 i 个元素 void insert(int i, T x);
//在线性表最后插入 x 元素 void insert(T x);
//删除第 i 个元素并返回被删除对象 T remove(int i);
int search(T key); //查找,返回首次出现的关键字为 key 的元素的位序
//删除线性表所有元素 void removeAll();
public String toString();// 返回顺序表所有元素的描述字符串,形式为 “(,)” }
要求:实现后应编写代码段对每个基本操作做测试。
(2)顺序表的简单应用
a) b) c)
运用基本操作编写算法删除第 i 个开始的 k 个元素。 编写高效算法删除第 i 个开始的 k 个元素。
将两个顺序表合并为一个顺序表(表中元素有序) ;
d) 若两个元素按值递增有序排列的顺序表 A 和 B,且同一表中的元素值各不相同。试构造一个顺序表 C,其元素为 A 和 B 中元素的交集,且表
C 中的元素也按值递增有序排列;
(3)利用顺序表解决约瑟夫环问题:已知
n 个人(以编号 1,2,3...n 分别表示)
围坐在一张圆桌周围。 从编号为 k 的人开始报数,数到 m 的那个人出列;他的下 一个人又从 1 开始报数,数到 m 的那个人又出列; 依此规律重复下去,直到圆桌
周围的人全部出列。要求:输出出列次序。
第二部分 单链表的实现与应用
(4)基于单链表实现线性表的以下基本操作(不需要建立接口,直接建立带头
结点的单链表类):
ADT List
int size(); T get(int i);
void set(int i, T x);
Node
Node
元素
public String toString();
式为“(,)”
//判断线性表是否空
// 返回线性表长度
// 返回第 i ( i≥0)个元素
//设置第 i 个元素值为 x
// 插入 x 作为第 i 个元素
//在线性表最后插入 x 元素
//删除第 i 个元素并返回被删除对象 //删除线性表所有元素
//查找,返回首次出现的关键字为 key
//返回顺序表所有元素的描述字符串,形
}
要求:实现后应编写代码段对每个基本操作做测试。
(5)实现单链表的子类排序单链表,覆盖单链表如下方法:
void set(int i, T x);
Node
Node
//设置第 i 个元素值为 x
//插入 x 作为第 i 个元素
//在线性表最后插入 x 元素
//查找,返回首次出现的关键字为
key 元
(6)基于排序单链表实现线性表的以下综合应用:
e) 删除第 i 个开始的 k 个元素。
f) 删除递增有序单链表中所有值大于
mink 且小于 maxk 的元素。
g) 将两个单链表合并为一个单链表,保持有序。
h) 若两个元素按值递增有序排列的单链表 A 和 B,且同一表中的元素值各不相
同。试构造一个单链表 C,其元素为 A 和 B 中元素的交集,且表 C 中的元素也按值递增有序排列。要求利用原有链表中的元素。
(7)一元多项式的基本运算
用排序单链表表示一元多项式,并实现以下基本运算:
一元多项式的建立
一元多项式的减法运算 (要求:在运算过程中不能创建新结点
即 A=A-B )
(8)备份自己程序
4. 实验准备:
复习教材第 2 章线性表的知识点熟悉 Java编程环境
提前熟悉实验内容,设计相关算法
5. 实验过程:第一部分:
( 1) package public
{
ex1;
interface LList
// 线性表接口,泛型参数
boolean
isEmpty(); int i);
int i, T x);
int i, T x); int i);
int length(); void set( int insert(
T 表示数据元素的数据类型
// 判断线性表是否空
// 返回线性表长度
// 返回第 i ( i ≥0)个元素 // 设置第 i 个元素值为 x // 插入 x 作为第 i 个元素 // 在线性表最后插入 x 元素
// 删除第 i 个元素并返回被删除对象 // 删除线性表所有元素
// 查找,返回首次出现的关键字为
T get(
int append(T x); void removeAll(); int search(T key);
T remove(
key 的元素
的位序
}
类名: public
class
SeqList
implements
LList
protected protected
Object[]
element
;
int n ;
public SeqList(
length
{
int length) // 构造容量为
的空表
this . element
。
= new Object[length];
// 申请数组的存
储空间,元素为 null
// 若length<0
java.lang.NegativeArraySizeException
this . n = 0;
}
public
, Java 抛出负数组长度异常
SeqList() // 创建默认容量的
空表,构造方法重载
{
this
(64); // 调用本类已声明的
指定参数列表的构造方法
}
public {
SeqList(T [] values)
// 构造顺序表,
由 values 数组提供元素,忽略其中空对象