《数据结构-线性表的实现与应用完整版》由会员分享，可在线阅读，更多相关《数据结构-线性表的实现与应用完整版（53页珍藏版）》请在金锄头文库上搜索。
1、数据结构（Java版）-线性表的实 现与应用完整版实验报告课程名称数据结构实验项目线性表的实现及应用实验仪器PC机一台学 院专 业班级/学号姓名实验日期成 绩指导教师北京信息科技大学信息管理学院(数据结构课程上机)实验报告专业:_班级:_学号:_姓名:成绩：实验名称线性表的实现及应用实验地点实验时间1.实验目的：(1) 理解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会利 用顺序表解决实际应用冋题。(2) 熟练掌握单链表的使用；理解用链表实现线性表的特点；了解链表的多 种形式；学会利用单链表解决实际应用问题。2.实验要求：(1)学时为8学时；(2) 能在机器上正确、调试运行程序；(3
2、) 本实验需提交实验报告；(4) 实验报告文件命名方法：数据结构实验 信管16xx_学号J生名.doc。3.实验内容和步骤：第一部分顺序表的实现与应用(1)基于顺序表实现线性表的以下基本操作：public in terface LList /线性表接口，泛型参数T表示数据元素的数据类型boolean isEmpty();/判断线性表是否空int size();/返回线性表长度T get(int i);/返回第 i (i 0)个兀素void set(int i, T x);设置第i个兀素值为xvoid insert(int i, T x);插入x作为第i个兀素void insert(T x);在
3、线性表最后插入x兀素T remove(int i);/删除第i个兀素并返回被删除对象int search(T key); /查找，返回首次出现的关键子为 key的兀素的位序 void removeAII();删除线性表所有兀素public String toString();返回顺序表所有兀素的描述子符串，形式为要求：实现后应编写代码段对每个基本操作做测试。(2) 顺序表的简单应用a) 运用基本操作编写算法删除第i个开始的k个元素b) 编写高效算法删除第i个开始的k个元素c) 将两个顺序表合并为一个顺序表(表中元素有序)d) 若两个元素按值递增有序排列的顺序表 A和B，且同一表中的元素 值各不
4、相同。试构造一个顺序表 C,其元素为A和B中元素的交集，且 表C中的元素也按值递增有序排列；(3) 禾U用顺序表解决约瑟夫环问题：已知 n个人(以编号1, 2, 3n分别表示) 旨坐在一张圆桌周围。从编号为 k的人开始报数，数到 m的那个人出列；他的一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到。要求：输出出列次序单链表的实现与应用(4) 基于单链表实现线性表的以下基本操作(不需要建立接口，直接建立带头吉点的单链表类)：ADT List boolea n isEmpty(); int size(); T get(i nt i); void set(i nt i, T x);
5、Node in sert(i nt i, T x); Node in sert(T x);T remove(i nt i);象void removeAll(); Node search(T key);key元素public String toString();形式为“(，)”/判断线性表是否空/返回线性表长度返回第i (i 0)个元素/设置第i个元素值为x插入x作为第i个元素/在线性表最后插入x元素删除第i个元素并返回被删除对删除线性表所有元素查找，返回首次出现的关键字为返回顺序表所有元素的描述字符串，(5) 实现单链表的子类排序单链表，覆盖单链表如下方法：void set(int i, T
6、x);/设置第i个元素值为xNode insert(int i, T x);插入 x 作为第 i 个元素Node insert(T x);在线性表最后插入 x元素Node search(T key);/查找，返回首次出现的关键字为key（6）基于排序单链表实现线性表的以下综合应用：e）删除第i个开始的k个元素。f）删除递增有序单链表中所有值大于 mink且小于maxk的元素。g）将两个单链表合并为一个单链表，保持有序。h）若两个元素按值递增有序排列的单链表 A和B，且同一表中的元素值各 不相同。试构造一个单链表 C,其元素为A和B中元素的交集，且表C 中的元素也按值递增有序排列。要求利用原有链
7、表中的元素。（7）元多项式的基本运算用排序单链表表示一元多项式，并实现以下基本运算：一元多项式的建立一元多项式的减法运算（要求：在运算过程中不能创建新结点即A=A-B）（8）备份自己程序4.实验准备：复习教材第2章线性表的知识点熟悉Java编程环境提前熟悉实验内容，设计相关算法5.实验过程：第一部分：(1)package exl;publicin terfaceLList/线性表接口，泛型参数T表示数据元素的数据类型boolean isEmpty();/ 判断线性表是否空int length();/返回线性表长度T get( int i);/返回第i (i 0)个元素void set( int
8、 i, T x);/设置第i个元素值为xint in sert( int i, T x);/插入x作为第i个元素int append(T x);/ 在线性表最后插入x元素T remove( int i);/删除第i个元素并返回被删除对象void removeAII();/ 删除线性表所有元素int search(T key);/查找，返回首次出现的关键字为key的元素的位 序类名：public class SeqList impleme ntsLList protected Objectelement ;protected int n;public SeqList( int len gth)/
9、构造容量为length的空表this . element = newObjectlength;/ 申请数组的存储空间，元素为null 。/ 若 length0 ，Java抛出负数组长度异常java.la ng.NegativeArraySizeExceptionthis . n = 0;public SeqList()/创建默认容量的空表，构造方法重载this (64);/调用本类已声明的指定参数列表的构造方法public SeqList(T values)/构造顺序表，由values数组提供元素，忽略 其中空对象this (values.len gth *2);/创建2倍values数组容量
10、的空表/ 若values=null ，用 空对象调用方法，Java抛出空对象异常NullPoi nterExceptio nfor ( int i=0;i0)个元素i f (i=0 & i=0 & i this . n) this . element i = x;else throw newjava.la ng.ln dexOutOfBo un dsException(i+ ); /抛出序号越界异常public int in sert( int i, Tx) II插入x作为第i个元素if (x= n ull )throw newNullPoi nterExceptio n(x=nu II);/
11、抛出空对象异常if (i this . n) i= this . n;/插入在最后Object source =this . element ;/ 数组变量引用赋值，source也引用element数组 if (this . n= =element . length )/若数组满，则扩充顺序表的数组容量this . element = newObjectsource.length*2;/ 重新申请一个容量更大的数组for ( int j=0; j=i;j-)/从i开始至表尾的元素向后移动，次序从后向前this . element j+1= source。;this . element i =
12、x;this . n +;return i;/返回x序号public int appe nd(Tx)/在线性表最后插入x元素return this .insert(this . n,x);public T remove( int i)/删除第i个元素并返回被删除对象if ( this . n0 & i=0 &i this . n)T old =(T) this element /old中存储被删除元素for ( int j=i;j this . n-1; j+)this . element j=this . element j+1;/ 元素前移一个位置this . element this . n-1= null ;/设置数组元素对象为空，释放原引用实例this . n-;return old;/返回old局部变量引用的对象，传递对象引用
