没有合适的资源?快使用搜索试试~ 我知道了~
数据结构(Java版) 线性表的实现与应用完整版.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 47 浏览量
2022-06-18
11:27:25
上传
评论
收藏 1.39MB PDF 举报
温馨提示
试读
27页
。。。
资源推荐
资源详情
资源评论
数据结构(Java 版) 线性表的实现与应用完整版
实 验 报 告
课程名称
数据结构
实验项目
线性表的实现及应用
实验仪器
PC 机一台
学 院_____
专 业
班级/学号
姓名
实验日期
成 绩
指导教师
北京信息科技大学
信息管理学院
(数据结构课程上机)实验报告
专业: 班级: 学号: 姓名: 成绩:
实验名称 线性表的实现及应用 实验地点 实验时间
1.实验目的:
(1) 理解用顺序表实现线性表的特点 ;熟练掌握顺序表的基本操作 ;学会
利用顺序表解决实际应用问题。
(2) 熟练掌握单链表的使用 ;理解用链表实现线性表的特点 ;了解链表的
多种形式;学会利用单链表解决实际应用问题。
数据结构(Java 版) 线性表的实现与应用完整版
2.实验要求:
(1) 学时为 8 学时;
(2) 能在机器上正确、调试运行程序;
(3) 本实验需提交实验报告;
(4) 实验报告文件命名方法:数据结构实验_信管 16xx_学号_姓名、doc。
3.实验内容与步骤:
第一部分 顺序表的实现与应用
(1)基于顺序表实现线性表的以下基本操作:
public interface LList<T>
{ //线性表接口,泛型参数 T 表示数据元素的数据类型
boolean isEmpty(); //判断线性表就是否空
int size(); //返回线性表长度
T get(int i); //返回第 i(i≥0)个元素
void set(int i, T x); //设置第 i 个元素值为 x
void insert(int i, T x); //插入 x 作为第 i 个元素
void insert(T x); //在线性表最后插入 x 元素
T remove(int i); //删除第 i 个元素并返回被删除对象
int search(T key); //查找,返回首次出现的关键字为 key 的元素的位序
void removeAll(); //删除线性表所有元素
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 的那个人又出列;依此规律重复下去,直到圆桌周围的人全部
出列。要求:输出出列次序。
第二部分 单链表的实现与应用
数据结构(Java 版) 线性表的实现与应用完整版
(4)基于单链表实现线性表的以下基本操作 (不需要建立接口 ,直接建立带头结点
的单链表类):
ADT List<T>
{ boolean isEmpty(); //判断线性表就是否空
int size(); //返回线性表长度
T get(int i); //返回第 i(i≥0)个元素
void set(int i, T x); //设置第 i 个元素值为 x
Node<T> insert(int i, T x); //插入 x 作为第 i 个元素
Node<T> insert(T x); //在线性表最后插入 x 元素
T remove(int i); //删除第 i 个元素并返回被删除对象
void removeAll(); //删除线性表所有元素
Node<T> search(T key); //查找,返回首次出现的关键字为 key
元素
public String toString(); //返回顺序表所有元素的描述字符串,形
式为“(,)”
}
要求:实现后应编写代码段对每个基本操作做测试。
(5)实现单链表的子类排序单链表,覆盖单链表如下方法:
void set(int i, T x); //设置第 i 个元素值为 x
Node<T> insert(int i, T x); //插入 x 作为第 i 个元素
Node<T> insert(T x); //在线性表最后插入 x 元素
Node<T> search(T key); //查找,返回首次出现的关键字为 key 元素
(6)基于排序单链表实现线性表的以下综合应用:
e) 删除第 i 个开始的 k 个元素。
f) 删除递增有序单链表中所有值大于 mink 且小于 maxk 的元素。
g) 将两个单链表合并为一个单链表,保持有序。
h) 若两个元素按值递增有序排列的单链表 A 与 B,且同一表中的元素值各不
相同。试构造一个单链表 C,其元素为 A 与 B 中元素的交集,且表 C 中的
元素也按值递增有序排列。要求利用原有链表中的元素。
(7)一元多项式的基本运算
用排序单链表表示一元多项式,并实现以下基本运算:
一元多项式的建立
一元多项式的减法运算(要求:在运算过程中不能创建新结点 即 A=A-B)
(8)备份自己程序
数据结构(Java 版) 线性表的实现与应用完整版
4.实验准备:
复习教材第 2 章线性表的知识点
熟悉 Java 编程环境
提前熟悉实验内容,设计相关算法
5. 实验过程:
第一部分:
(1)
package ex1;
public interface LList<T>
{ //线性表接口,泛型参数T表示数据元素的数据类型
boolean isEmpty(); //判断线性表就是否空
int length(); //返回线性表长度
T get(int i); //返回第i(i≥0)个元素
void set(int i, T x); //设置第i个元素值为x
int insert(int i, T x); //插入x作为第i个元素
int append(T x); //在线性表最后插入x元素
T remove(int i); //删除第i个元素并返回被删除对象
void removeAll(); //删除线性表所有元素
int search(T key); //查找,返回首次出现的关键字为key的元素
的位序
}
类名:
public class SeqList<T> implements LList<T> {
protected Object[] element;
protected int n;
public SeqList(int length) //构造容量为
length的空表
{
this、element = new Object[length]; //申请数组的
存储空间,元素为null。
//若length<0,Java抛出负数组长度异常 java、lang、
NegativeArraySizeException
this、n = 0;
}
public SeqList() //创建默认容量的
空表,构造方法重载
{
this(64); //调用本类已声明的
指定参数列表的构造方法
}
public SeqList(T [] values) //构造顺序表,
数据结构(Java 版) 线性表的实现与应用完整版
由values数组提供元素,忽略其中空对象
{
this(values、length*2); //创建2倍
values数组容量的空表
//若values==null,用空对象调用方法,Java抛出空对象异常
NullPointerException
for (int i=0; i<values、length; i++) //复制非空的
数组元素。O(n)
if (values[i]!=null)
this、element[this、n++] = values[i]; //对象引用赋
值
}
public boolean isEmpty() //判断线性表就是否空
{
return this、n==0;
}
public int length(){ //返回线性表长度
return this、n;
}
public T get(int i){ //返回第i(i≥0)个元素
if (i>=0 && i<this、n)
return (T)this、element[i]; //返回数组
元素引用的对象,传递对象引用
// return this、element[i]; //编译
错,Object对象不能返回T对象
return null;
}
public void set(int i, T x){ //设置第i个元素值为x
if (x==null)
throw new NullPointerException("x==null"); //抛出空
对象异常
if (i>=0 && i<this、n)
this、element[i] = x;
else throw new java、lang、
IndexOutOfBoundsException(i+"");//抛出序号越界异常
}
public int insert(int i, T x){ //插入x作为第i个元素
if (x==null)
throw new NullPointerException("x==null"); //抛出空
剩余26页未读,继续阅读
资源评论
xxpr_ybgg
- 粉丝: 6506
- 资源: 3万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功