完整版信管实验报告

1、管理学院信管专业12(1)班学号3112004734姓名钟臻华协作者:无教师评定实验题目线性表的基本操作实验评分表指导教帅评分标准序号评分项目评分标准满分打分1完成度按要求独立完成实验准备、程序调试、实验报告撰写。202实验内容(1) 完成功能需求分析、存储结构设计；(2) 程序功能完善、可止常运行；(3) 测试数据正确，分析正确，结论正确。303实验报告内容齐全，符合要求，文理通顺，排版美观。404总结对实验过程遇到的问题能初步独立分析，解决后能总结问题原因及解决方法，有心得体会。10实验报告1. 实验目的与要求本实验通过对线性表各种操作的算法设计，理解和掌握线性表的概念、存储结构及操作要求

2、，体会顺序和链式两种存储结构的特点；根据操作的不同要求，选择合适的存储结构，设计并实现算法，对算法进行时间复杂度分析，从而达到掌握数据结构的研究方法、算法设计和分析方法的目的。1. 实验内容分别用顺序表、单链表、单循环链表实现约瑟夫问题的求解，并分析基于不同存储结构算法的时间复杂度。如果采用顺序表实现时，每个元素出环并不执行删除操作，而将相应位置元素值设置为空，但计数时必须跳过值为空的元素，实现这种算法，并分析执行效率。1. 顺序表的不删除出环元素算法实现publicclassJosephus3(publicJosephus3(intnumber,intstart,intdistance)(/

3、仓U建约瑟夫环并求角犁，参数指定环长度,起始位置，计数/采用线性顺序表存储约瑟夫环的元素，元素类型是字符串，构造方法参数指定顺序表的容量SeqList<String>list=newSeqList<String>(number);Stringa=newString("null");for(inti=0;i<number;i+)list.append(char)('A'+i)+"");System.out.print("约瑟夫环("+number+","+start+&q

4、uot;,"+distance+"),");System.out.println(list.toString();inti=start+distance-1;for(intj=1;j<list.length();j+)(intnum=distance;list.set(i,a);while(num!=0)(i=(i+1)%list.length();if(!list.get(i).equals("null")(num-;System.out.println(list.toString();if(!list.get(j).equals(&q

5、uot;null")System.out.println("被赦免者是"+list.get(j).toString();publicstaticvoidmain(Stringargs)(newJosephus3(5,0,2);运行结果：DjE)(AnullC,nullE)(AnullC,nulIE)SA鎏名号匚JI(inuUBnullJC?mullE)(nullnulljCjnulljE)(nuLljfiuLLjCnulljE(mjlljHullfC,nullj=)(nullnull/C;nullrull)I'rr、(null,nullCnull,null

6、)(nullriullCnull,null)(nulljrnilljCnull,null)(rnjlljnulljCjnulljnuH)(nulLjnulljCjnulLfnull)2. 使用单链表实现的算法classJosephus1(publicJosephus1(intnumber,intstart,intdistance)(/仓U建约瑟夫环,参数指定环长度起始位置，计数/采用单链表存储约瑟夫环的元素，元素类型是字符串，构造方法参数指定单链表的容量SinglyLinkedList<String>list=newSinglyLinkedList<String>(nu

7、mber);for(inti=0;i<number;i+)(list.append(char)('A'+i)+"");/添加字符串对象System.out.print("约瑟夫环("+number+","+start+","+distance+"),");/输出约瑟夫环的环长度，起始位置，计数System.out.println(list.toString();/输出单链表的描述字符串A,B,C,D,Einti=start;while(list.length()>1)

8、(/多于一个对象时的循环i=(i+distance-1)%list.length();/计数按循环规律变化，单链表可以看作是环形结构(循环单链表)System.out.print("删除”+list.remove(i)+",");System.out.println(list.toString();System.out.println("被赦免者是"+list.get(0).toString();publicstaticvoidmain(Stringargs)(newJosephus1(5,1,2);兰*(加SD(A,D)2A")毓站

9、者是n书本例题的约瑟夫环的算法publicclassJosephus(publicJosephus(intnumber,intstart,intdistance)(SeqList<String>list=newSeqList<String>(number);for(inti=0;i<number;i+)list.append(char)('A'+i)+"");System.out.print("约瑟夫环("+number+","+start+","+distance+&

10、quot;),");System.out.println(list.toString();inti=start;while(list.length()>1)(i=(i+distance-1)%olist.length();/循环顺序表System.out.print("删除"+list.remove(i).toString()+",");System.out.println(list.toString();System.out.println("被赦免者是"+list.get(0).toString();publics

11、taticvoidmain(Stringargs)(newJosephus(5,0,2);2. 实现教材P74实验内容(3)的各成员方法。publicclassSinglyLinkedList<T>implementsLList<T>带头结点的单链表类，实现线性表接口publicNode<T>head;头指针,指向单链表的头结点publicSinglyLinkedList(intnumber)/默认构造方法，构造空单链表创建头结点,data和next值均为nullthis.head=newNode<T>();publicSinglyLinkedL

12、ist(Telement,intnumber)/由指定数组中的多个对象构造单链表，采用尾插入构造单链表this(number);/创建空单链表，只有头结点Node<T>rear=this.head;/rear指向单链表最后一个结点for(inti=0;i<element.length;i+)/若element=null,抛出空对象异常/element.length=0时，构造空链表rear.next=newNode<T>(elementi,null);/尾插入，创建结点链入rear结点之后rear=rear.next;/rear指向新的链尾结点/判断单链表是否为空

13、,0(1)publicbooleanisEmpty()(returnthis.head.next=null;以下length。、toString()、get()、set()方法基于单链表遍历算法publicintlength()(inti=0;Node<T>p=this.head.next;/p从单链表第一结点开始while(p!=null)(i+;p=p.next;returni;返回单链表的所有元素的描述字符串，形式为"(,)”，覆盖Object类额toString()方法,O(n)publicStringtoString()(Stringstr="(&qu

14、ot;Node<T>p=this.head.next;/p从单链表的第一结点开始while(p!=null)(str+=p.data.toString();if(p.next!=null)str+=",”;p=p.next;returnstr+")"publicTget(inti)/返回第i(i>=0)个元素，若i指定序号无效，则返回null返回单链表的第i个元素的算法(if(i>=0)(Node<T>p=this.head.next;/p从单链表的第一个结点开始头结点是单链表的第一个结点之前的一个特殊的结点，并非单链表的第一个

15、结点for(intj=0;p!=null&&j<i;j+)p=p.next;if(p!=null)returnp.data;/p指向第i个结点returnnull;/设置第i(i>=0)个元素值为x,若i指定序号无效则抛出序号越界异常publicvoidset(inti,Tx)(if(x=null)return;/不能设置空对象if(i>=0)(Node<T>p=this.head.next;/p从单链表的第一个结点开始for(intj=0;p!=null&&j<i;j+)p=p.next;if(p!=null)p.data=

16、x;/p指向第i个结点elsethrownewIndexOutOfBoundsException(i+"");/抛出序号越界异常以下insert()、appendQB法实现单链表插入操作publicvoidinsert(inti,Tx)(/将x对象插入在序号为i结点前，也即插入在序号为i-1结点后,O(n)if(x=null)/不能插入空对象return;/p指向头结点Node<T>p=this.head;/寻找插入位置头结点(i=0)for(intj=0;p.next!=null&&j<i;j+)p=p.next;/循环停止时，p指向第i

17、-1结点或最后一个结点插入x作为p结点的后继结点，包括头插入(i<=0)、中间/尾插入(i>0)p.next=newNode<T>(x,p.next);在单链表的最后添加对象，O(n)publicvoidappend(Tx)insert(Integer.MAX_VALUE,x);以下remove。、removeAll算法实现单链表的删除操作删除序号为i的结点，也即删除序号为i-1的后继结点，若操作成功,则返回被被删除的对象，否则返回null,O(n)publicTremove(inti)if(i>=0)Node<T>p=this.head;for(in

18、tj=0;p.next!=null&&j<i;j+)/定位到待删除结点(i)的前驱结点(i-1)头结点(i=0)p=p.next;/遍历算法if(p.next!=null)Told=p.next.data;/嵌得原对象p.next=p.next.next;/删除p的后继结点returnold;returnnull;删除单链表的所有元素,java将白动收回各结点的所占用的内存空间publicvoidremoveAll()(this.head=null;查找，返回首次出现的关键字为key的元素，方法实现见8.2.1节publicTsearch(Tkey)(returnkey;

19、/查找算法以下声明对单链表元素进行查找，包含，替换，删除等方法，以查找算法为基础publicTsearch_1(Tx)(if(x=null)/关键字x不能为空，空则返回nullreturnnull;/顺序查找关键字为x的元素，返回首次出现的元素，若查找不成功返回nullNode<T>P=this.head.next;/佚结点的下一个结点while(p!=null)if(p.data.equals(x)returnp.data;/返回首次出现的元素returnnull;publicbooleancontain(Tx)(/判断线性表是否包含关键字为x的兀素returnthis.sear

20、ch(x)!=null;/以查找的结果获得判断结果删除单链表中指定元素关键字x的remove()函数声明如下，使用顺序查找算法但未调用查找算法publicvoidremove(Tx)(/删除首次出现的值为x的结点，若没有找到指定结点则不删除if(this.head.next=null|x=null)/关键字x不能为空，且带有头结点的单链表不能为空return;Node<T>front=this.head,p=front.next;/p指向头结点的下一个结点,front指向头结点while(p!=null&&!p.data.equals(x)(front=p;p=p.

21、next;if(p!=null)front.next=p.next;/头删除,中间/尾删除中间删除publicvoidremoveAll(Tx)(publicvoidreplace(Tx,Ty)(if(this.head.next=null|x=null|y=null)return;publicvoidreplaceAll(Tx,Ty)(x=y;以下声明按迭代方式遍历单链表的成员方法publicNode<T>getFirst()if(this.head.next=null)returnhead;/单链表不能为空returnthis.head.next;/返回单链表的第一个结点，非头

22、结点publicNode<T>getNext(Node<T>p)Node<T>p1=this.head;/p指向头结点while(p1!=null)p1=p1.next;returnpl.next;publicNode<T>getPrevious(Node<T>p)(Node<T>p1=this.head;while(p1!=null)(p1=p1.next;returnp1;publicNode<T>getLast()Node<T>p=this.head;while(p!=null)for(int

23、j=0;p.next!=null&&j<Integer.MAX_VALUE;j+)/定位于最后一个结点之前的前一个结点p=p.next;returnp.next;以下声明对单链表的子表进行操作的求子表、包含、插入、删除、替换等方法publicSinglyLinkedList<T>sub(inti,intn)(if(i>=0)(Node<T>p=this.head;for(intj=0;p.next!=null&&j<i;j+)/定位于i-1的结点p=p.next;if(p.next!=null)(Told=p.next.

24、data;returnold;returnnull;for(inti=0;i<n;i+)p=p.next;returnp;publicvoidremove(inti,intn)(if(i>=0)(Node<T>p=this.head;for(intj=0;p.next!=null&&j<i;j+)/定位于i-1的结点if(p.next!=null)(Told=p.next.data;p.next=p.next.next;returnold;returnnull;for(inti=0;i<n;i+)p=p.next;publicvoidinse

25、rt(inti,SinglyLinkedList<T>list)(publicSinglyLinkedList(SinglylinkedList<T>list)(/复制单链表所有结点的深拷贝构造方法this();/创建空单链表，只有头结点Node<T>p=this.head.next;Node<T>rear=this.head;while(p!=null)(rear.next=newNode<T>(p.data,null);rear=rear.next;if(SinkedlinkedList=null)return;Node<T>p=this.head;/p指向头结点for(intj=