好文档 - 专业文书写作范文服务资料分享网站

数据结构(Java版)线性表的实现与应用完整版 

天下 分享 时间: 加入收藏 我要投稿 点赞

实 验 报 告

课程名称

数据结构

实验项目

线性表的实现及应用

实验仪器

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 { boolean isEmpty();

int size(); T get(int i);

void set(int i, T x);

Node insert(int i, T x); Node insert(T x); T remove(int i); void removeAll();

Node search(T key);

元素

public String toString();

式为“(,)”

//判断线性表是否空

// 返回线性表长度

// 返回第 i ( i≥0)个元素

//设置第 i 个元素值为 x

// 插入 x 作为第 i 个元素

//在线性表最后插入 x 元素

//删除第 i 个元素并返回被删除对象 //删除线性表所有元素

//查找,返回首次出现的关键字为 key

//返回顺序表所有元素的描述字符串,形

}

要求:实现后应编写代码段对每个基本操作做测试。

(5)实现单链表的子类排序单链表,覆盖单链表如下方法:

void set(int i, T x);

Node insert(int i, T x); Node insert(T x);

Node search(T key); 素

//设置第 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 数组提供元素,忽略其中空对象

数据结构(Java版)线性表的实现与应用完整版 

实验报告课程名称数据结构实验项目线性表的实现及应用实验仪器
推荐度:
点击下载文档文档为doc格式
4jaul1588l9lpyv23wwc1symv1joq10079w
领取福利

微信扫码领取福利

微信扫码分享