数据结构(Java版)线性表的实现和应用[完整版]

实 验 报 告

课程名称 数据结构 实验项目 线性表的实现及应用 实验仪器 PC机一台

学 院_____ 专 业 班级/学号 姓名 实验日期 成 绩 指导教师

专业整理 知识分享

完美WORD格式

北京信息科技大学

信息管理学院

（数据结构课程上机）实验报告

专业: 班级: 学号: 姓名: 成绩: 实验名称 线性表的实现及应用 实验地点 实验时间 1. 实验目的： （1） 理解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会利用顺序表解决实际应用问题。 （2） 熟练掌握单链表的使用；理解用链表实现线性表的特点；了解链表的多种形式；学会利用单链表解决实际应用问题。 2. 实验要求： （1） 学时为8学时； （2） 能在机器上正确、调试运行程序； （3） 本实验需提交实验报告； （4） 实验报告文件命名方法：数据结构实验_信管16xx_学号_姓名.doc。 3. 实验内容和步骤： 第一部分 顺序表的实现与应用 （1）基于顺序表实现线性表的以下基本操作： public interface LList { //线性表接口，泛型参数T表示数据元素的数据类型 专业整理 知识分享

完美WORD格式

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中的元素也按值递增有序排列； 专业整理 知识分享

完美WORD格式

（3）利用顺序表解决约瑟夫环问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。要求：输出出列次序。 第二部分 单链表的实现与应用 （4）基于单链表实现线性表的以下基本操作（不需要建立接口，直接建立带头结点的单链表类）： ADT List { boolean isEmpty(); //判断线性表是否空 int size(); //返回线性表长度 T get(int i); //返回第i（i≥0）个元素 void set(int i, T x); //设置第i个元素值为x Node insert(int i, T x); //插入x作为第i个元素 Node insert(T x); //在线性表最后插入x元素 T remove(int i); //删除第i个元素并返回被删除对象 void removeAll(); //删除线性表所有元素 Node search(T key); //查找，返回首次出现的关键字为key元素 public String toString(); //返回顺序表所有元素的描述字符 专业整理 知识分享

完美WORD格式

串，形式为“（，）” } 要求：实现后应编写代码段对每个基本操作做测试。 （5）实现单链表的子类排序单链表，覆盖单链表如下方法： void set(int i, T x); //设置第i个元素值为x Node 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）一元多项式的基本运算 用排序单链表表示一元多项式，并实现以下基本运算：  一元多项式的建立  一元多项式的减法运算（要求：在运算过程中不能创建新结点 即A=A-B） 专业整理 知识分享

完美WORD格式

（8）备份自己程序 4. 实验准备： 复习教材第2章线性表的知识点 熟悉Java编程环境 提前熟悉实验内容，设计相关算法 5. 实验过程： 第一部分： （1） package ex1; public interface LList { //线性表接口，泛型参数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 implements LList { 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; 专业整理 知识分享

完美WORD格式

} public SeqList() //创建默认容量的空表，构造方法重载 { this(64); //调用本类已声明的指定参数列表的构造方法 } public SeqList(T [] values) //构造顺序表，由values数组提供元素，忽略其中空对象 { this(values.length*2); //创建2倍values数组容量的空表 //若values==null，用空对象调用方法，Java抛出空对象异常NullPointerException for (int i=0; i=0 && i完美WORD格式

if (i>=0 && ithis.n) i=this.n; //插入在最后 Object[] source = this.element; //数组变量引用赋值，source也引用element数组 if (this.n==element.length) //若数组满，则扩充顺序表的数组容量 { this.element = new Object[source.length*2]; //重新申请一个容量更大的数组 for (int j=0; j=i; j--) //从i开始至表尾的元素向后移动，次序从后向前 this.element[j+1] = source[j]; this.element[i] = x; this.n++; return i; //返回x序号 } public int append(T x){ //在线性表最后插入x元素 return this.insert(this.n, x); } public T remove(int i){ //删除第i个元素并返回被删除对象 if (this.n>0 && i>=0 && i完美WORD格式

象为空，释放原引用实例 this.n--; return old; //返回old局部变量引用的对象，传递对象引用 } return null; } public void removeAll(){ //删除线性表所有元素 this.n=0; } public int search(T key){ //查找，返回首次出现的关键字为key的元素的位 System.out.print(this.getClass().getName()+\".indexOf(\"+key+\")，\"); for (int i=0; i0) str += this.element[0].toString(); //执行T类的toString()方法，运行时多态 for (int i=1; i list=new SeqList(20); Integer values[]={10,1,2,3,4,5,6,7,8,9}; SeqList list1=new SeqList(values); System.out.print(\"输出顺序表:\"); System.out.println(list1.toString()); 专业整理 知识分享

完美WORD格式

System.out.println(\"顺序表List是否为空\"+list.isEmpty()+\是否为空\"+list1.isEmpty()); System.out.println(\"list的长度\"+list.length()+\的长度\"+list1.length()); System.out.println(\"返回list1的第7个元素是:\"+list1.get(6)); System.out.println(\"重新设置第5个元素为19:\"); list1.set(4, 19); list1.insert(2, 100); list1.append(20); System.out.println(\"删除8:\"+list1.remove(8)); System.out.print(\"修改后的顺序表:\"); System.out.println(list1.toString()); list1.removeAll(); System.out.println(\"删除后的顺序表：\"+list1.toString()); //为空 System.out.println(\"寻找元素50:\"+list1.search(50)); } } （2） a) package ex1; public class Del { public Del(int i,int k) { String values[]={\"A\",\"b\",\"C\",\"d\",\"e\",\"f\",\"g\",\"h\"}; int n =values.length; for(int j=0;j完美WORD格式

for(int j=i+k;j list=new SeqList(values); System.out.println(list.toString()); for(int j=1;j<=k;j++) { list.remove(i);} System.out.println(list.toString()); } public static void main(String args[]) { new Del2(2,3); } } 专业整理 知识分享

完美WORD格式

c) package ex1; public class Merge { public Merge(){ Integer values1[]={1,3,5,11}; SeqList list1=new SeqList(values1); Integer values2[]={2,4,5,22,23}; SeqList list2=new SeqList(values2); SeqList list3=new SeqList(); int i=0,j=0; while(i完美WORD格式

new Merge(); } } d) package test; import ex1.SeqList; public class Intersection { public Intersection(){ Integer values1[]={1,3,5,11,12,13,22,23,50}; SeqList list1=new SeqList(values1); Integer values2[]={2,4,5,12,19,20,22,23,}; SeqList list2=new SeqList(values2); SeqList list3=new SeqList(); int i=0,j=0; while(ilist2.get(j)){ j++; } else { list3.append(list1.get(i)); i++; j++; } } 专业整理 知识分享

完美WORD格式

} System.out.println(list1.toString()); System.out.println(list2.toString()); System.out.println(list3.toString()); } public static void main(String args[]) { new Intersection(); } 3. （1） package ex1; public class Josephus { public Josephus(int n, int k, int m) { System.out.println(\"Josephus(\"+n+\+k+\+m+\")，\"); SeqList list = new SeqList(n); //创建顺序表实例，元素类型是数字字符，只能排到n=9,否则达不到效果 for (int i=0; i1) //多于一个元素时循环，计数O(1) { i = (i+m-1) % list.length(); //按循环方式对顺序表进行遍历,圆桌循环 System.out.print(\"出列\"+list.remove(i).toString()+\"，\"); //删除i位置对象，O(n) 专业整理 知识分享

完美WORD格式

// System.out.println(list.toString()); } System.out.println(\"出列\"+list.get(0).toString());//get(0)获得元素，O(1) } public static void main(String args[]) { new Josephus(9,1,3); } } （2） package test; import ex1.SeqList; public class JosephusA { public JosephusA(int n, int k, int m) { System.out.println(\"Josephus(\"+n+\+k+\+m+\")，\"); SeqList list = new SeqList(n); //创建顺序表实例，元素类型是数字字符，只能排到n=9,否则达不到效果 for (int i=0; i1) //多于一个元素时循环，计数O(1) { i = (i+m-1) % list.length(); //按循环方式对顺序表进行遍历,圆桌循环 专业整理 知识分享

完美WORD格式

System.out.print(\"出列\"+list.remove(i).toString()+\"，\"); //删除i位置对象，O(n) // System.out.println(list.toString()); } System.out.println(\"出列\"+list.get(0).toString());//get(0)获得元素，O(1) } public static void main(String args[]) { new JosephusA(15,2,9); } } 第二部分： （4）、 package ex2; public class Node { public T data; //数据域 public Node next; //地址域，后继结点 //构造结点 public Node(T data,Node next){ this.data =data; this.next=next; } //构造空结点 public Node(){ this(null,null); } //描述字符串 专业整理 知识分享

完美WORD格式

public String toString(){ return this.data.toString(); } } package ex2; public class SinglyList { public Nodehead; //构造空单链表 public SinglyList() { head=new Node(); } //构造单链表，由values数组数组提供元素 public SinglyList(T[] values) { this(); Noderear=this.head; for(int i=0;i(values[i],null); rear=rear.next; } } public boolean isEmpty() //判断线性表是否空 { return this.head.next ==null; } public T get(int i) //返回第i（i≥0）个元素 { Nodep=head.next ; for(int j=0;p!=null&&j=0) ? p.data:null; } 专业整理 知识分享

完美WORD格式

public void set(int i, T x) //设置第i个元素值为x { if(x==null) throw new NullPointerException(\"x==null\"); //抛出空对象异常 Nodep=this.head.next; //0 for(int j=0;p!=null&&j0&&p!=null) p.data=x; } public int size() //返回线性表长度 { int i=0; for(Nodep=this.head.next;p!=null;p=p.next) i++; return i; } public Node insert(int i, T x) //插入x作为第i个元素 { if(x==null) throw new NullPointerException(\"x=null\"); Nodefront=this.head ; //指定头结点 for(int j=0;front.next!=null&&j(x,front.next ); return front.next; } public Node insert(T x) { if (x==null) throw new NullPointerException(\"x==null\"); //抛出空对象异常 Node front=this.head; //front指向头结点 for (; front.next!=null;) //寻找第i-1个或最后一个结点（front指向） front = front.next; front.next = new Node(x, front.next); //在front之后插入值为x结点，包括头插入、中间/尾插入 return front.next; } 专业整理 知识分享

完美WORD格式

public T remove(int i) //删除第i个元素并返回被删除对象 { Nodep=this.head; //让p指向头结点 for(int j=0;j search(T key) //查找，返回首次出现的关键字为key元素 { for(Node p =this.head;p.next!=null;p=p.next) if( key.equals(p.data)) return p; return null; } public String toString() //返回顺序表所有元素的描述字符串，形式为“（，）” { String str=this.getClass().getName()+\"(\"; //返回类名 for (Node p=this.head.next; p!=null; p=p.next)//p遍历单链表 { str += p.data.toString(); if (p.next!=null) str += \; //不是最后一个结点时，加分隔符 } return str+\")\"; } 专业整理 知识分享

完美WORD格式

} （5）、 package ex2; public class SortedSinglyList> extends SinglyList{ //构造空排序单链表 public SortedSinglyList() { super(); //默认调用父类构造方法SinglyList() } public SortedSinglyList(SinglyList list) { super(); //构造空单链表 for (Node p=list.head.next; p!=null; p=p.next)//直接插入排序，每趟插入1个元素 this.insert(p.data); //排序单链表按值插入 } //构造 ，将values数组中的所有对象按值插入 public SortedSinglyList(T values[]) { super(); for(int i=0;i完美WORD格式

} public Node insert(int i, T x) //插入x作为第i个元素 { throw new UnsupportedOperationException(\"set(int i, T x)\"); //不支持父类方法，覆盖并抛出异常 } public Node insert(T x) //在线性表最后插入x元素 { Nodep=this.head; for(;p.next!=null&& p.next.data.compareTo(x)>0;) p=p.next; p.next = new Node(x, p.next); return p.next; } public Node search(T key) //查找，返回首次出现的关键字为key元素 { for (Node p=this.head;p.next!=null&&key.compareTo(p.data)<=0;p=p.next) if(key.compareTo(p.next.data)==0) return p; return null; } } （6）、 e、 package ex2; public class Del1 { public Del1(int i,int k){ Integer[] values={1,5,6,10,13}; SinglyList list= new SinglyList(values); System.out.println( list.toString()); for(int j=0;j完美WORD格式

} public static void main(String[] args){ new Del1(2,2); } f、 package ex2; public class Del2 { public Del2(int mink,int maxk) { Integer[] values={1,3,9,17,34}; SortedSinglyList list = new SortedSinglyList(values); System.out.println(list.toString()); Node p=list.head; int j=0; while(p.next!=null && p.next.data<=mink) { p=p.next; j++; } while(p.next!=null &&p.next.data完美WORD格式

g、 package ex2; public class Meger{ public Meger() { Integer[] values1={1,2,5,7,9}; SortedSinglyList val1=new SortedSinglyList(values1); Integer[] values2= {1,0,5,8,9}; SortedSinglyList val2=new SortedSinglyList(values2); SortedSinglyList val=new SortedSinglyList(); int i=0;int j = 0; while(i完美WORD格式

} public static void main(String args[]) { new Meger(); } (7)、 package Poly; public interface Subible //可相加接口，T表示数据元素的数据类型 { public void sub(T t); //+=加法，约定两元素相加规则 public boolean removable(); //约定删除元素条件 } package Poly; //项类，一元多项式的一项，实现可比较接口和可相加接口 public class TermX implements Comparable, Subible { protected int coef, xexp; //系数，x指数（可为正、0） public TermX(int coef, int xexp) //构造一项 { this.coef = coef; this.xexp = xexp; } public TermX(TermX term) //拷贝构造方法 { this(term.coef, term.xexp); } //以“系数x^指数”的省略形式构造一元多项式的一项。 //省略形式说明：当系数为1或-1且指数>0时，省略1，-1只写负号“-”，如x^2、-x^3； //当指数为0时，省略x^0，只写系数；当指数为1时，省略^1，只写x。 public TermX(String termstr) { 专业整理 知识分享

完美WORD格式

if (termstr.charAt(0)=='+') //去掉+号 termstr=termstr.substring(1); int i = termstr.indexOf('x'); if (i==-1) //没有x，即指数为0 { this.coef = Integer.parseInt(termstr); //获得系数 this.xexp = 0; } else //有x，x之前为系数，x^之后为指数 { if (i==0) //以x开头，即系数为1 this.coef = 1; else { String sub=termstr.substring(0,i); //x之前子串表示系数 if (sub.equals(\"-\")) //系数只有-号，即系数为-1 this.coef=-1; else this.coef = Integer.parseInt(sub); //获得系数 } i = termstr.indexOf('^'); if (i==-1) this.xexp=1; //没有^，即指数为1 else this.xexp = Integer.parseInt(termstr.substring(i+1));//获得指数 } } //返回一元多项式的一项对应的“系数x^指数”的省略形式字符串，省略形式说明同TermX(String)构造方法。 public String toString() { String str=this.coef>0 ? \"+\" : \"-\"; //系数的符号位 if (this.xexp==0 || this.xexp>0 && this.coef!=1 && this.coef!=-1) str+=Math.abs(this.coef); //系数绝对值，省略系数1 if (this.xexp>0) str+=\"x\"; //指数为0时，省略x^0，只写系数 if (this.xexp>1) str+=\"^\"+this.xexp; //指数为1时，省略^1，只写x return str; 专业整理 知识分享

完美WORD格式

} public int compareTo(TermX term) //按x指数比较两项大小，实现Comparable接口 { if (this.xexp == term.xexp) //比较相等 return 0; //比较规则与equals(Object)不同 return this.xexp接口 { if (this.compareTo(term)==0) this.coef -= term.coef; else throw new IllegalArgumentException(\"两项的指数不同，不能相减。\"); } public boolean removable() //若系数为0，则删除元素；实现Subible接口 { return this.coef==0; //不存储系数为0的项 } //比较两项是否相等，比较系数和指数，比较规则与compareTo(term)==0不同 public boolean equals(Object obj) { if (this==obj) return true; if (!(obj instanceof TermX)) return false; TermX term=(TermX)obj; return this.coef==term.coef && this.xexp==term.xexp; } } package Poly; import ex2.Node; import ex2.SortedSinglyList; 专业整理 知识分享

完美WORD格式

public class PolySinglyList & Subible> extends SortedSinglyList { public PolySinglyList() //构造方法 { super(); //创建空单链表 } public PolySinglyList(T terms[]) //构造方法，由项数组指定多项式各项值 { super(terms); } public PolySinglyList(PolySinglyList list) //拷贝构造方法 { super(); //单链表深拷贝，复制所有结点，没有复制对象 } public void subAll(PolySinglyList list) //多项式相减，this-=list功能，不改变list { Node front=this.head, p=front.next; Node q=list.head.next; while (p!=null && q!=null) if (p.data.compareTo(q.data)==0) //两项大小相同 { p.data.sub(q.data); //两项相加，add()方法由Subible接口约定 if (p.data.removable()) //相加后元素满足删除条件 { //removable()方法由Subible接口约定 front.next=p.next; //相加后元素不需要存储，删除p结点 p=front.next; } else { front = p; //front是p的前驱结点 p = p.next; } q = q.next; } else if (p.data.compareTo(q.data)<0) { 专业整理 知识分享

完美WORD格式

front = p; p = p.next; } else { front.next = new Node(q.data, p); //复制q结点并插入到front结点之后 q = q.next; } while (q!=null) //将list单链表中剩余结点复制并插入到当前链表尾 { front.next = new Node(q.data, null); front = front.next; q = q.next; } } } package Poly; import ex2.Node; public class Polynomial { private PolySinglyList list; //多项式排序单链表，TermX表示一元多项式的一项 public Polynomial() //构造方法 { this.list = new PolySinglyList(); //创建空单链表，执行排序单链表默认构造方法 } public Polynomial(TermX terms[]) //构造方法，由项数组指定多项式各项值 { this.list = new PolySinglyList(terms); } public Polynomial(String polystr) //构造方法，参数指定多项式表达式字符串 { this(); if (polystr==null || polystr.length()==0) 专业整理 知识分享

完美WORD格式

return; Node rear = this.list.head; int start=0, end=0; //序号start～end的子串为一项 while (start(new TermX(polystr.substring(start,end)), null); //尾插入，以序号start～end的子串作为一项，创建结点，创建元素对象 rear = rear.next; start=end; } } public Polynomial(Polynomial poly) //深度拷贝构造方法，复制所有结点和对象 { this(); //创建空单链表，只有头结点 Node rear = this.list.head; for (Node p=poly.list.head.next; p!=null; p=p.next) //p遍历poly单链表 { rear.next = new Node(new TermX(p.data), null); //复制结点，复制对象 rear = rear.next; } } public String toString() //返回多项式的描述字符串 { String str=\"\"; 专业整理 知识分享

完美WORD格式

for (Node p=this.list.head.next; p!=null; p=p.next) str+=p.data.toString(); return str; } public void subAll(Polynomial poly) //多项式相加，this＋=poly { this.list.subAll(poly.list); } public Polynomial union(Polynomial poly) //减法 -，C=this-poly { Polynomial polyc=new Polynomial(this); //深度拷贝，复制所有结点和对象 polyc.subAll(poly); //cpoly-=poly return polyc; //返回对象引用 } public boolean equals(Object obj) //比较两个多项式是否相等 { return this==obj || obj instanceof Polynomial && this.list.equals(((Polynomial)obj).list); //比较两条单链表是否相等 } } package Poly; public class Polynomial_ex { public static void main(String args[]) { System.out.println(\"//一元多项式\"); TermX aterms[]={new TermX(-7,9), new TermX(2,7), new TermX(-9,4), new TermX(1,2), new TermX(-1,1)}; //图2.25A(x)，不要求数组排序 Polynomial apoly = new Polynomial(aterms); Polynomial bpoly = new Polynomial(\"-1+x-x^2+10x^4-3x^8+5x^10\");//图2.25B(x) Polynomial cpoly = apoly.union(bpoly); 专业整理 知识分享

完美WORD格式

System.out.println(\"A=\"+apoly.toString()+\"\\n\\nB=\"+bpoly.toString()+\"\\n\"); System.out.println(\"C=A-B，C=\"+cpoly.toString()); } } 6. 实验总结：（本次实验的收获、未解决的问题以及体会和建议等） 说明： 1. 实验名称、实验目的、实验内容、实验要求由教师确定，实验前由教师事先填好，然后作为实验报告模

版供学生使用；

2. 实验准备由学生在实验或上机之前填写，教师应该在实验前检查；

3. 实验过程由学生记录实验的过程，包括操作过程、遇到哪些问题以及如何解决等；

4. 实验总结由学生在实验后填写，总结本次实验的收获、未解决的问题以及体会和建议等； 5. 源程序、代码、具体语句等，若表格空间不足时可作为附录另外附页。

专业整理 知识分享