华南农业大学数据结构java版实验二

1、实验报告线性表华南农业大学信息（软件）学院数据结构（JAVA）综合性、设计性实验成绩单班级16信管3班学号03xx姓名黄xx实验二线性表的基本操作成绩教师签名开设时间：2017学年第二学期实验目的:(1)理解线性表的逻辑结构、两种存储结构和数据操作，熟练运用 表的基本操作，分析各种操作算法特点和时间复杂度。掌握单链表的遍历、插入和删除等操作算法，实现多项式相加。JAVA语言实现线性实验内容:1、设计一个有序顺序表(元素已排序，递增或递减) 位置由其值决定。实现：(1)升序排序顺序表类名为：SortedSeqList，存成文件;(2 )另外编写文件来演示调用排序顺序表Public class S

2、ortedSeqList private int MAX_SIZE= 10;private int ary = new intMAX_SIZEI;private int length = 0;p ublic SortedSeqList(i nt array) if (array = null |= 0) =0; else ，实现插入、删除等操作，元素插入ary = array;len gth =;public void clear() len gth = 0;public boolean I isEmpty() return length = 0；public void delete( int

3、 index ) throws Exception if (length = 0) throw new Exception( "No elment to delete" ); int newAry = new int - 1; for (int i = 0, j = 0; i < ; i+) if (i = index ) continue ; else newAry j+ = ary i;ary = newAry ;length -;public int insert( int value ) throws Exception if (length = MAX_SI

4、ZE) throw new Exception( "List is full, can't insert more" ); int newAry = new int length + 1; int i = 0, j = 0;for (; i < ; i+, j+) if (aryi >= value ) newAry j = value ; break ; else newAry j = ary i;while (i < newAry +j = aryi; i+;ary = newAry ; length +; return value;publi

5、c void display() "nList now is: " );for (int i = 0; i < ; i+) + "t" );(2)文件来演示调用排序顺序表p ublic class SortedSeqList_ex p ublic static void main( Stri ng args) throws Exce pti on in t ary = 1,2, 3, 5, 7;SortedSeqList list = new SortedSeqList(ary);();；();(2);();(3 )实验结果wWrElrulHi.

6、Mil舸4|l砂 妙M帀“血|抽 0*±i-l II P4|iLlSl 2 1 碁1? J sL is-t new* if1丄4I Bl件1巧1J4B2、在SinglyLinkedList类中增加下列成员方法。Public SinglyLinkedList(E element);public class Test staticstaticstaticstaticstaticstaticIn teger x=3,5,8,11;In teger x1 =3,5,8,11;In teger x2=2,6,8,9,11,15,20;SinglyLinkedList<Integer>

7、; Listi =new SinglyLinkedList<Integer>( x);SinglyLinkedList<Integer> List2= new SinglyLinkedList<Integer>( x1);SinglyLinkedList<Integer> List3= new SinglyLinkedList<Integer>( x2);public static void disList(SinglyLinkedList List)"%-5d",;for (Node temp=public st

8、atic void concat() (List3);public static void Find()"请输入需要查找的数：")；Scanner scan=new Scanner; In teger eleme nt=();Node t=(eleme nt);if(t!= null)else"List1中找不到指定的数。“);public static void ContainO"请输入所需包含的数：")；Scanner scan=new Scanner;In teger eleme nt=();if(eleme nt)"List3

9、 包含指定的数 -5dn" ,element);else"List3 不包含指定的数 %-5dn" ,element);public static void remove()"请输入指定移除的数：");Scanner scan=new Scanner;In teger eleme nt=();if(eleme nt)"%-5d 已在 List3中移除 n" ,element);else "%-5d无法在List3中找到，无法移除n" ,element);public static void replace

10、()"请输入所需交换的两个数：");Scanner scan=new Scanner;In teger obj=();In teger eleme nt=();if(obj, eleme nt)"%-5d 与 %-5d两个数成功交换 n" ,obj,element);else "无法改动“)；public static void equals()if(List2)"List1与List2两个单链表相等“)；else "List1与List2两个单链表不相等 ");if(List3)"List1与List3

11、两个单链表相等“)；else "List1与List3两个单链表不相等 ");Public static void main(String args) disList(List1);disList(List2);disList(List3);con cat();disList(List1);Fin d();Co ntai n();remove ();rep lace();equals();(2 )实验结果电tdmmuted*1 Lkp Appliwtkjn 训忙gidm咅 D 砧3过ifAjdwdw出iw 门01晖5月 IDH 下工 1:QQQ出1467e913,先写出LL

12、ist接口并写上要实现的方法的方法头，再CircSinglyLinkedList类中继承该接口并实现其方法。(1)写出 LList接口 ；P ublic in terface LList<T> boolea n isE mp ty();int size();T get(i nt i);void set(i nt i,T x);Stri ng toStri ng();T remove(i nt i);void clear();int search(T key);boolea n contains(T key);T in sertDiffere nt(T x);T remove(T k

13、ey);boolea n equaIsQbject obj);结点类P ackage Lab2;public class Node<T> p ublic T data;p ublic Node<T> n ext;public Node(T data, Node<T> next)=data;=next;public Node() this(null, null);public Stri ng toStri ng()return (3)CircSinglyLinkedList 类public class CircSinglyLinkedListvTimpleme

14、nts LListvT>p ublic NodevT> head;Overridepublic boolean isEmpty（） .n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到 m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。运作原理：1、一群人围在一起坐成环状（如： N）2、 从某个编号开始报数（如：K）3、数到某个数（如： M）的时候，此人出列，下一个人重新报数4、一直循环，直到所有人出列，约瑟夫环结束(1)循环单链表P ublic class Jose phus_S in glyL in kedL

15、ist p ublic Jose phus_S in glyL in kedList(i nt nu mber, i nt start, int dista nee) Sin glyL in kedListvStri ng> list = new Sin glyL in kedListvStri ng>(); rint("约瑟夫环("+ number + "," + start + "," + distanee + ")，");int i = start - 1; oString() + ”，"

16、;);"被赦免者是 ” + (O).toString();p ublic static void main( Stri ng args) new Jose phus_S in glyL in kedList(5, 1,2);(2)循环双链表public classJosephus_CirDoublyLinkedList /*存储约瑟夫环中多个对象*/p rivate CirDoublyLinkedListvStringlist;/*创建约瑟夫环并求解，参数指定环长度、起始位置、计数* p aram number* p aram start* p aram distance*/p ub

17、lic Jose phus_CirDoublyLinkedList(int number, int start, int distance) =new CirDoublyLinkedList<String>();for (int i = 0; i < number; i+)String(char) ('A' + i) +.print("约瑟夫环("+ number + "," + start + "," + distance + ")，"); oStringO);public st

18、atic void main(String args) new Jose phus_CirDoublyLinkedList(5, 1,2);(3 )运行结果(A,C,D,E) (A,C,E) (C,E)(C)B，D，a，E，约瑟夫环(5,1,2), (A,B,C,D,E) 删除 删除 删除 删除 被赦免者是C(3)分析操作效率使用循环链表实现约瑟夫环是一种解法，但是效率不高。采用双向循环链表删除操作需要 维护2各指针。不需要记录 a的指针只要简单的指针维护即可，双向链表的查找可以在任 意位置开始查找，效率高了一些。8,先给该线性表创建一个迭代器，然后用hasNextO判断是否存在后继元素，再利

19、用next()方法来取得这个元素和形参比较。跟相似，只是这里是两个线性表，然后分别给他们创建一个迭代器，然后将他们的 元素对应的逐个逐个的比较，从而比较线性表是否相等。imp ort先给该线性表创建一个迭代器，然后用hasNextO判断是否存在后继元素，再利用next()方法来取得这个元素和形参比较。Public class ListIter public static int indexOf(Object s, Object obj)lteratorvObject> iter = (list<Object>) s) iterator。;int idx = 0;while (

20、)Object str =();if(str) return idx;idx+;return -1;跟相似，只是这里是两个线性表，然后分别给他们创建一个迭代器，然后将他们 的元素对应的逐个逐个的比较，从而比较线性表是否相等。Public static boolean equaIsQbject obj1, Object obj2) lteratorvObject> iter1 = (List<Object>) obj1).iterator(): Iterator<Object> iter2 = (List<Obiect>) obi2).iterator(

21、); while () && ()Object str1 =();Object str2 =();if(!(str2) return false:if(!() && !() return true :return false;9,算法实现：多项式相加一条单链表可以表示一个一元多项式，每个结点包含三个域：指数域、系数域和后继 结点链。表示多项式 3x4 6x2 5x 10的单链表如图1所示。给定两个多项式，实现两个 多项式相加算法。系数指数链实现代码：P ackage Q3;Public class Node<T> p ublic T base;p u

22、blic T in dex;p ublic Node<T> n ext;p ublic Node(T base,T in dex,Node<T> n ext)=base;=in dex;=n ext;public Node()this (null ,null ,null );package Q3;public class Polynomial public static Node<Integer> head;public static Node<Integer> Create( int t) Node<Integer> p= new

23、Node<Integer>(); head=p;for (int i=0;i<i+)=new Node<Integer>(ti0,ti1, null ); p=; print (head ); return head;public static void print(Node<Integer> a)a=;while !=null )"A" +" + ")； a=;"A"+;public static Node<Integer> Add(Node<Integer> a,N

24、ode<Integer> b) Node<Integer> p= new Node<Integer>();head=p;a=;b=; while (a!=null &&b!= null )if<= if=new Node<Integer>+, null );p=;a=;b=;else=new Node<Integer>, null );p=;a=; else=new NodevInteger>” null);P=；b=；if(a=null)while (b!=null)=new NodevInteger&g

25、t;, null);P=；b=;if(b=null)while =null)=new NodevInteger>, null);p=;a=;head;returnp ackage Q3;public class Test extends Polynomialpublic static void main(String args)int 叩 a=1,1,2,4,3,4,1,5,1,6,2,7;in t b=1,1,6,2,3,4,2,5;Nodev In teger>a1= new Nodev In teger>();Nodev In teger>b1= new Node

26、v In teger>(); a1=Create(a);b1=Create (b);prin t(Add(a1,b1);10,有效管理一个 1n的随机数序列，要求生成初始序列，保证序列中的元素值不重复，当增加或删除一个元素的时候，使序列元素值动态更新。例如，一个MP3播放器使用速记方式播放10首歌曲，曲目播放次序就是由110组成的一个随机数序列，当增加或删除一首歌的时候，要及时更新序列中元素值，不重复播放Public class RandomListvE> p ublic NodevE> head;p ublic Ran domListQ =new NodevE>();p ublic Ran domList(i nt n) this();NodevE> P =;int count = 0;while (co unt v n) int number = (in t) () * (n) + 1;E num = (E) new In teger( nu mber);