数据结构线性表的实现与应用完整版
实验报告课程名称数据结构实验项目线性表的实现及应用实验仪器PC机一台学 院专 业班级/学号姓名实验日期成 绩指导教师北京信息科技大学信息管理学院(数据结构课程上机)实验报告专业：班级：学号：姓名:成绩线性表的实现及应用实验地点实验时间2.实验要求:(1)学时为8学时;(2)能在机器上正确、调试运行程序;(3)本实验需提交实验报告;实验名称1.实验目的：(1)理解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会利用顺序表解决实际应用问题。(2) 熟练掌握单链表的使用；理解用链表实现线性表的特点；了解链表的多种形式；学会利用单链表解决实际应用问题。public in terface LList<T> /线性表接口，泛型参数boolea n isEmpty();int size();T get(int i);void set(i nt i, T x);void in sert(i nt i, T x);void in sert(T x);T remove(i nt i);(4)实验报告文件命名方法：数据结构实验信管16xx学号 姓名.doc。3. 实验内容和步骤:第一部分顺序表的实现与应用(1) 基于顺序表实现线性表的以下基本操作:T表示数据元素的数据类型判断线性表是否空/返回线性表长度/返回第i (i > 0)个元素 设置第i个元素值为x插入x作为第i个元素/在线性表最后插入x元素删除第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, 3n分别表示） 围坐在一张圆桌周围。从编号为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); 素/设置第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 ex1; publicin terfaceboolea n intT get(voidintintLList<T>/线性表接口，泛型参数 T表示数据元素的数据类型isEmpty();T remove(voidlen gth();int i);set( int i, T x);in sert(int i, T x);appe nd(T x);int i);int的位序removeAll();search(T key);/判断线性表是否空/返回线性表长度/返回第i (i >0)个元素/设置第i个元素值为x/插入x作为第i个元素/在线性表最后插入x兀素/删除第i个元素并返回被删除对象/删除线性表所有元素/查找，返回首次出现的关键字为key的元素类名：publicclassSeqList<T>impleme ntsLList<T> protected protectedObject int n;eleme ntpublic SeqList( int len gth 的空表len gth)/构造容量为this . element 储空间，元素为null 。/ 若length<0 java .Ian g.NegativeArraySizeExcepti on this . n = 0;new Objectle ngth;/申请数组的存,Java抛出负数组长度异常public SeqList()空表，构造方法重载/创建默认容量的this (64);指定参数列表的构造方法/调用本类已声明的public SeqList(T values)由values数组提供元素，忽略其中空对象/构造顺序表,this (values.len gth*2);values数组容量的空表/ 若values=null，用空对象调用方法,/创建2倍Java抛出空对象异常NullPoi nterExceptio n for 组元素。O(n)int i=0; i<values.len gth ; i+)/复制非空的数if(valuesi!= this.elementnull)this . n + = values"/对象引用赋值public boolea nisEmpty()/判断线性表是否空returnthis.n=0;publicreturnintlen gth() this . n;/返回线性表长度publicT get( inti)/返回第i (i >0)个元素if(i>=0 && i< return (T) 传递对象引用thisthis.n).element i;/返回数组元素引用的对象，/ return this.eleme nti;Object对象不能返回T对象retur nnull/编译错,publicvoid set(int i, T x)/设置第i个元素值为if(x= null )throw newNullPoi nterExceptio n("x=null" );/抛出空对象异常if(i>=0 && i<this else throw newthis . n).element i = x;java.la ng.In dexOutOfB oun dsExceptio n(i+ publicintin sert(int i, T x)if(x= n ull )throw new NullPoi nterExceptio n(对象异常if(i<0)i=0;"");/抛出序号越界异常/插入x作为第i个元素"x=null" );/抛出空/插入位置i容错，插入在最前if (i> this . n) i= this . n;/插入在最后Object source =this引用赋值，source 也引用element数组.element/数组变量if ( this . n= = element . length )则扩充顺序表的数组容量/若数组满,this . element = new Objectsource.请一个容量更大的数组for ( int j=0; j<i; j+)组前i-1个元素this . element j = sourcej;for ( int j= this . n-1; j>=i; j-)至表尾的元素向后移动，次序从后向前this . element j+1 = sourcej;length *2;/ 重新申/复制当前数/从i开始this . element i = x; this . n +;returnpublic inti;appe nd(T x)/返回x序号/在线性表最后插入x兀素return this.
