没有合适的资源?快使用搜索试试~ 我知道了~
数据结构线性表的实现与应用完整版.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 95 浏览量
2022-11-12
13:11:19
上传
评论
收藏 801KB PDF 举报
温馨提示
试读
31页
...
资源推荐
资源详情
资源评论
实验报告
课程名称
实验项目
实验仪器
数据结构 __________
线性表的实现及应用
PC
机一台 _________
学 院 ____________________________
专 业 ____________________________
班级/学号 __________________________
姓名 ______________________________
实验日期 ____________________________
成 绩 ____________________________
指导教师 ___________________________
北京信息科技大学
信息管理学院
(数据结构课程上机)实验报告
专业 _班级_学号_姓名
:
______ 成绩: _______
线性表的实现及应用 实验地点
实验时间
1.
实验目的:
(1) 理解用顺序表实现线性表的特点;熟练掌握顺序表的基本操作;学会
利用顺序表解决实际应用问题
(2) 熟练掌握单链表的使用;理解用链表实现线性表的特点;了解链表的
多种形式;学会利用单链表解决实际应用问题。
2.
实验要求:
(1)
(2)
(3)
(4)
学时为
8
学时;
能在机器上正确、调试运行程序;
本实验需提交实验报告;
实验报告文件命名方法:数据结构实验
—
信管
16xx_
学号
J
生名
.doc
。
3.
实验内容和步骤:
第一部分顺序表的实现与应用
(
1
)基于顺序表实现线性表的以下基本操作:
public in terface LList<T>
{ //
线性表接口,泛型参数
T
表示数据元素的数据类型
boolea n isEmpty();
〃判断线性表是否空
int size();
//
返回线性表长度
T get(int i);
//
返回第
i
(
i
>
0
)个元素 〃设置第
i
个元素值为
x
void set(i nt i, T x);
〃插入
x
作为第
i
个元素
void in sert(i nt i, T
//
在线性表最后插入
x
元素
x);
void in sert(T x);
〃删除第
i
个元素并返回被删除对象
T remove(i nt i);
〃查找,返回首次出现的关键字为
int search(T key); key
的元素的位序
void removeAII();
〃删除线性表所有元素
public String toString();//
返回顺序表所有元素的描述字符串,形式为
}
要求:实现后应编写代码段对每个基本操作做测试。
(2
)顺序表的简单应用
a)
运用基本操作编写算法删除第
i
个开始的
k
个元素。
b)
编写高效算法删除第
i
个开始的
k
个元素。
c)
将两个顺序表合并为一个顺序表(表中元素有序);
d)
若两个元素按值递增有序排列的顺序表
A
和
B
,且同一表中的元素值 各不相同。
试构造一个顺序表
C
,其元素为
A
和
B
中元素的交集,且表
C
中的元素也按值递增有序
排列;
(
3
)利用顺序表解决约瑟夫环问题:已知
n
个人(以编号
1
,
2
,
3…n
分别表示) 围坐在一
张圆桌周围。从编号为
k
的人开始报数,数到
m
的那个人出列;他的下 一个人又从
1
开始报数,
数到
m
的那个人又出列;依此规律重复下去,直到圆桌 周围的人全部出列。要求:输出出列次
序。
第二部分单链表的实现与应用
(
4
)基于单链表实现线性表的以下基本操作(不需要建立接口,直接建立带头
结点的单链表类):
ADT List<T>
{ boolea n isEmpty(); int size();
T get(i nt i); void set(i nt i,
T x);
Node<T> in sert(i nt i, T
x);
Node<T> in sert(T x);
T remove(i nt i); void
removeAll(); Node<T>
search(T key);
〃判断线性表是否空
//
返回线性表长度
//
返回第
i
(
i
>
0
)个元素
〃设置第
i
个元素值为
x
//
插入
x
作为第
i
个元素
〃在线性表最后插入
x
元素
〃删除第
i
个元素并返回被删除对象
〃删除线性表所有元素
//
查找,返回首次出现的关键字为
key
public Stri ng toStri ng();
式为
//
返回顺序表所有元素的描述字符串,形
“(,)”
}
要求:实现后应编写代码段对每个基本操作做测试。
(5
)实现单链表的子类排序单链表,覆盖单链表如下方法:
void set(i nt i, T x);
Node<T> in sert(i nt i, T
x);
Node<T> in sert(T x);
Node<T> search(T key);
e)
删除第
i
个开始的
k
个元素。
//
设置第
i
个元素值为
x
//
插入
x
作为第
i
个元素
//
在线性表最后插入
x
元素
〃查找,返回首次出现的关键字为
key
元
(
6
) 基于排序单链表实现线性表的以下综合应用:
f)
删除递增有序单链表中所有值大于
mink
且小于
maxk
的元素。
g)
将两个单链表合并为一个单链表,保持有序。
h)
若两个元素按值递增有序排列的单链表
A
和
B
,且同一表中的元素值各 不相同。试构造
一个单链表
C
,其元素为
A
和
B
中元素的交集,且表
C
中的元素也按值递增有序排列。
要求利用原有链表中的元素。
(
7
) —元多项式的基本运算
用排序单链表表示一元多项式,并实现以下基本运算:
一元多项式的建立
一元多项式的减法运算(要求:在运算过程中不能创建新结点 即
A=A-B
)
(
8
) 备份自己程序
4.
实验准备:
复习教材第
2
章线性表的知识点
熟悉
Java
编程环境
提前熟悉实验内容,设计相关算法
5.实验过程: 第一
部分:
(1)
package ex1;
public in terface
LList<T>
//线性表接口,泛型参数 T 表示数据元素的数据类型
{
boolea
isEmpty();
//判断线性表是否空
n int
len gth();
//返回线性表长度
int i);
//返回第 i (i
>0)
个元素
T get(
void
set( int i, T x);
//设置第 i 个元素值为 x
int i, T x);
int
in sert(
//插入 x 作为第 i 个元素
int
appe nd(T x);
//在线性表最后插入 x 兀素
int i);
T remove(
//删除第 i 个元素并返回被删除对象
void
removeAll();
//删除线性表所有元素
int
search(T key);
//查找,返回首次出现的关键字为 key 的元素
的位序
}
类
名:
impleme nts LList<T> {
class
SeqList<T>
public
protected Object[]
eleme
nt
int n;
protected
public SeqList( int len gth
len
//构造容量为
gth)
{
new Object[le ngth];
this . element 储空间,元素为
null
。
,Java 抛出负数组长度异常
// 若 length<0
java .Ian g.NegativeArraySizeExcepti on
this . n = 0;
}
public SeqList()
空表,构造方法重载
{
this (64);
指定参数列表的构造方法
}
public SeqList(T [] values)
由 values 数组提供元素,忽略其中空对象
的空表
//申请数组的存
//创建默认容量的
//调用本类已声明的
//构造顺序表,
{
剩余30页未读,继续阅读
资源评论
不吃鸳鸯锅
- 粉丝: 8296
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功