大数据结构线性表地实现与应用完整版.docx

实用标准文案实验报告课程名称 数据结构 实验项目 线性表的实现及应用实验仪器 学 院 专 业 班级/学号 实验日期 成 绩 指导教师 信息科技大学信息管理学院(数据结构课程上机)实验报告成绩:实验名称1.实验目的:线性表的实现及应用实验地点实验时间文档大全(1) 理解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会利用顺序表解决实际应用问题2) 熟练掌握单链表的使用；理解用链表实现线性表的特点；了解链表的多种形式；学会利用单链表解决实际应用问题2.实验要求：(1)学时为8学时;(2)能在机器上正确、调试运行程序;(3)本实验需提交实验报告;(4)实验报告文件命名方法：数据结构实验 信管16xx学号.doc3. 实验容和步骤:第一部分顺序表的实现与应用(1) 基于顺序表实现线性表的以下基本操作:public in terface LList{ //线性表接口，泛型参数T表示数据元素的数据类型boolea n isEmpty();〃判断线性表是否空int size();//返回线性表长度T get(int i);//返回第i (i >0)个元素void set(i nt i, T x);〃设置第i个元素值为xvoid insert（int i, T x）; 〃插入x作为第i个元素void insert（T x）; 〃性表最后插入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，且同一表中的元素值 各不相同试构造一个顺序表 C,其元素为A和B中元素的交集，且表 C中的元素也按值递增有序排列；（3） 利用顺序表解决约瑟夫环问题：已知 n个人（以编号1, 2, 3…n分别表示） 围坐在一圆桌周围从编号为k的人开始报数，数到m的那个人出列；他的下一 个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周 围的人全部出列要求：输出出列次序第二部分单链表的实现与应用（4） 基于单链表实现线性表的以下基本操作（不需要建立接口，直接建立带头结点的单链表类）：ADT List{boolea n isEmpty();〃判断线性表是否空int size();//返回线性表长度T get(i nt i);//返回第i （i >0）个元素void set(i nt i, T x);〃设置第i个元素值为xNode in sert(i nt i, T x);//插入x作为第i个元素Node in sert(T x);〃性表最后插入x元素T remove(i nt i);〃删除第i个元素并返回被删除对象void removeAII();〃删除线性表所有元素Node search(T key);//查找，返回首次出现的关键字为key儿糸public Stri ng toStri ng();//返回顺序表所有兀素的描述子符串，形式为}}要求：实现后应编写代码段对每个基本操作做测试。

5）实现单链表的子类排序单链表，覆盖单链表如下方法：void set(i nt i, T x);//设置第i个元素值为xNode in sert(i nt i, T x);//插入x作为第i个元素Node in sert(T x);//性表最后插入x元素Node search(T key);素〃查找，返回首次出现的关键字为 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 exl; public in terface {LListII线性表接口，泛型参数 T表示数据元素的数据类型boolea n isEmpty();int len gth();T get( int i); void set( int i, T x); int in sert( int i, T x);int appe nd(T x);T remove( int i); void removeAll(); int search(T key);的位序II判断线性表是否空II返回线性表长度II返回第i (i >0)个元素II设置第i个元素值为xII插入x作为第i个元素II性表最后插入x兀素II删除第i个元素并返回被删除对象II删除线性表所有元素II查找，返回首次出现的关键字为 key的元素类名:publicclass SeqListimpleme nts LList {protected Object[] eleme ntprotectedint n;II构造容量为II申请数组的存public SeqList( int len gth)len gth 的空表{this . element = new Object[length];储空间，元素为null 。

II若length<0 , Java抛出负数组长度异常java .Ian g.NegativeArraySizeExcepti onthis . n = 0;}II创建默认容量的II调用本类已声明的public SeqList()空表，构造方法重载{this (64);指定参数列表的构造方法}II构造顺序表,public SeqList(T [] values)由values数组提供元素，忽略其中空对象{this (values. len gth *2);values 数组容量的空表//若values==null ，用空对象调用方法,//创建2倍Java抛出空对象异常//复制非空的数for ( int i=0; i=0 && i0)个元素//返回数组编译错,//设置第i个元素值为x// return this.eleme nt[i]; //Object对象不能返回T对象return n ull ;}public void set( int i, T x){if (x== n ull )throw new NullPointerException( "x==null" ); // 抛出空对象异常if (i>=0 && i< this . n)this . element [i] = x;else throw newjava.lang.lndexOutOfBoundsException(i+ "" ); // 抛出序号越界异常}public int insert( int i, T x){ // 插入 x 作为第 i 个元素if (x== n ull )throw new NullPoi nterExceptio n("x==null" ); // 抛出空对象异常if (i<0) i=0;//插入位置i容错，插入在最前if (i> this . n) i= this . n;Object[] source = this引用赋值，source 也引用element数组.elementif ( this . n= = element . length )则扩充顺序表的数组容量//插入在最后//数组变量//若数组满,this . element = new Object[source. 请一个容量更大的数组for ( int j=0; j=i; j--)至表尾的元素向后移动，次序从后向前this . element [j+1] = source[j];len gth *2];//重新申//复制当前数II从i开始this . element [i] = x; this . n ++;II返回x序号return i;}publicint appe nd(T x){II性表最后插入x兀素return this .insert( this . n, x);}public T remove( int i){II删除第i个元素并返回被删除对象if ( this .n>0 && i>=0 && i< this . n){T old = (T) this . element [i]; IIold 中存储被删除元素f。