信管试验报告线性表基本操作

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

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

3、3( int number, int start, int distance) / 创建约瑟夫环并求解 , 参数 指定环长度 , 起始位置 , 计数/ 采用线性顺序表存储约瑟夫环的元素 , 元素类型是字符串 , 构造方法参数指定顺序表的容量SeqList list= new SeqList(number);String a= new String( null );f or ( int i=0;inumber;i+)l ist.append( char )( A +i)+ );System. out .print( 约瑟夫环 ( +number+ , +start+ , +distance+ )

4、, );System. out .println(list.toString();int i=start+distance-1;for ( int j=1;jlist.length();j+)int num=distance;list.set(i,a);while (num!=O)i=(i+1)%list.le ngth();if (!list.get(i).equals(null )n um-;System.out .println(list.toString();if (!list.get(j).equals(null)System. out .println(被赦免者是+list.get

5、(j).toString();public static void main( Stri ng args) new Josephus3(5,0,2);运行结果：(AjnullTCjDjE(AnullC,nullE)(AnullC,nulIE)石A黑寻幺匚JI(mjllJnullJCJnullJE)(nullnulljCjnulljE)(nuLljfiuLLjC nulljE(mjlljHullf C,nullj =)(nullnull C;nullrull)(null,nullCnull,null)(nullj nulljCj nullj nu11)(nullj rnilljCnull,nul

6、l)(nullj nulljCj nuUfnuU(nulLj nulljCjnulLf null)2.使用单链表实现的算法class Josephus1 public Josephus1( int number, int start, int distance)/ 仓U建约瑟夫环,参数指定环长度起始位置，计数/采用单链表存储约瑟夫环的元素，元素类型是字符串，构造方法参数指定单链表的容量Sin glyL in kedList list=new Sin glyL in kedList(n umber);for (int i=0;i1)/多于一个对象时的循环（循环i=(i+distance-1)%l

7、ist.length();/计数按循环规律变化，单链表可以看作是环形结构单链表)System. out .print( 删除+list.remove(i)+ ,);System. out .println(list.toString();System. out .println(被赦免者是+list.get(0).toString();public static void main(String args)new Josephus1(5,1,2);m 叽(d)3. 书本例题的约瑟夫环的算法public class Josephus public Josephus ( int number, i

8、nt start, int distance)SeqListvStri ng list=new SeqList(n umber);for (int i=0;i1)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();public static void main(String args)new J

9、osephus(5,0,2);亘站JA齐止）咄,(C)2. 实现教材 P74 实验内容( 3)的各成员方法。public class SinglyLinkedList implements LList / 带头结点 的单链表类 ,实现线性表接口public Node head;/头指针 ,指向单链表的头结点public SinglyLinkedList(int number)/ 默认构造方法 ,构造空单链表 创建头结点，data和next值均为nullthis.head=new Node();public SinglyLinkedList(T element, int number)/ 由指定

10、数组中的多 个对象构造单链表 ,采用尾插入构造单链表this( number);/创建空单链表，只有头结点Node rear二this.head;/rear指向单链表最后一个结点for(int i=0;ielement.length;i+)若 element=null,抛出空对象异 常/element.length=0 时,构造空链表rear.next=new Node(elementi,null);/ 尾插入 ,创建结点链 入rear结点之后rear二rear .n ext;/rear指 向新的链尾结点/判断单链表是否为空 ,O(1) public boolean isEmpty()retu

11、rn this.head.next=null;/ 以下 length()、 toString()、 get()、 set() 方法基于单链表遍历算 法public int length()int i=0;Node p=this.head.next;/p 从单链表第一结点开始 while(p!=null)i+;p=p.next;return i;/返回单链表的所有元素的描述字符串 ,形式为(,), 覆盖 Object 类额toStri ng()方法,O(n)public String toString()String str=(;Node p=this.head. next;/p从单链表的第一结

12、点开始 while(p!=null)7 / 18str+=p.data.toString();if(p.next!=null)str+=,;p=p.next;return str+);public T get(int i)返回第i(i=0)个元素，若i指定序号无效，则返回null 返回单链表的第 i 个元素的算法if(i=0)Node p=this.head.next;/p 从单链表的第一个结点开始 头结点是单链表的第一个结点之前的一个特殊的结点，并非单链表 的第一个结点for(int j=0;p!=null&j=0)个元素值为x,若i指定序号无效则抛出序号越界异常 public void s

13、et(int i,T x)if(x=null)return;/不能设置空对象if(i=0)Node p=this.head .n ext;/p从单链表的第一个结点开始for(int j=0;p!=null&ji;j+)p=p.next;if(p!=null)p.data=x;/p指向第i个结点else throw new IndexOutOfBoundsException(i+);/ 抛出序号越界异常/以下insert()、append(算法实现单链表插入操作public void insert(int i,T x)/ 将 x 对象插入在序号为 i 结点前 ,也即插 入在序号为 i-1 结点后

14、 ,O(n)if(x=null)/ 不能插入空对象return; /p 指向头结点Node p=this.head;寻找插入位置头结点(i=0)8 / 18for(int j=0;p.next!=null&ji;j+)p=p.next;/循环停止时,p指向第i-1结点或最后一个结点插入x作为p结点的后继结点，包括头插入(i0)p.next=new Node(x,p.next);/在单链表的最后添加对象 ,O(n)public void append(T x)insert(Integer.MAX_VALUE,x);/以下 remove()、 removeAll 算法实现单链表的删除操作/删除序号

15、为 i 的结点,也即删除序号为 i-1 的后继结点 ,若操作成功, 则返回被被删除的对象 ,否则返回 null,O(n)public T remove(int i)if(i=0)Node p=this.head;for(int j=0;p.next!=null&ji;j+) 定位到待删除结点(i)的前驱结点(i-1) 头结点(i=0)p=p .n ext;/遍历算法if(p.next!=null)T old=p. next.data;/获得原对象p.next=p.next.next;/删除 p 的后继结点10 / 18return old;return null;/删除单链表的所有元素 ,ja

16、va 将自动收回各结点的所占用的内存空 间public void removeAll()this.head=null;/查找,返回首次出现的关键字为 key 的元素,方法实现见 8.2.1节 public T search(T key)return key;/ 查找算法/以下声明对单链表元素进行查找,包含,替换 ,删除等方法 ,以查找算法为基础public T search_1(T x)if(x=null)/ 关键字 x 不能为空 ,空则返回 nullreturn null;顺序查找关键字为x的元素，返回首次出现的 元素 ,若查找不成功返回 nullNode P=this.head. next

17、;/头结点的下一个结点 while(p!=null)if(p.data.equals(x)retur n p.data;/返回首次出现的元素p=p.next;11 / 18return null;public boolean contain(T x)/ 判断线性表是否包含关键字为 x 的 元素return this.search(x)匸n ull;以查找的结果获得判断结果删除单链表中指定元素关键字x的remove()函数声明如下，使用顺序查找算法但未调用查找算法public void remove(T x)删除首次出现的值为x的结点，若没有找 到指定结点则不删除if(this.head.nex

18、t=null|x=null)/ 关键字 x 不能为空，且带有头 结点的单链表不能为空return;Node front=this.head,p=front.next;/p 指向头结点的下一个 结点 ,front 指向头结点while(p!=null&!p.data.equals(x)front=p;p=p.next;if(p!=null)front.n ext=p. next;/头删除冲间/尾删除中间删除11 / 18public void removeAll(T x)public void replace(T x,T y)if(this.head.next=null|x=null|y=nul

19、l) return;public void replaceAll(T x,T y)x=y;/以下声明按迭代方式遍历单链表的成员方法 public Node getFirst() if(this.head.next=null)return head;/单链表不能为空return this.head.next;/返回单链表的第一个结点，非头结点public Node getNext(Node p)Node p仁 this.head;/p 指向头结点while(p1!=null)13 / 18p1=p1.next;return p1.next;public Node getPrevious(Node

20、 p)Node p1=this.head;while(p1!=null)p1=p1.next;return p1;public Node getLast()Node p=this.head;while(p!=null)for(intj=0;p.next!=null&jInteger.MAX_V ALUE;j+)/ 定位于最后一个结 点之前的前一个结点p=p.next;/以下声明对单链表的子表进行操作的求子表、包含、插入、删除、替换等方法public SinglyLinkedList sub(int i,int n)if(i=0)Node p=this.head;for(int j=0;p.ne

21、xt!=null&ji;j+)/ 定位于 i-1 的结点 p=p.next;if(p.next!=null)T old=p.next.data;return old;return null;for(int i=0;i=0)Node p=this.head;for(int j=0;p.next!=null&ji;j+)/ 定位于 i-1 的结点if(p.next!=null)T old=p.next.data;p.next=p.next.next;return old;return null;for(int i=0;in;i+)p=p.next;public void insert(int i,

22、SinglyLinkedList list)list)/ 复制单链public SinglyLinkedList(SinglylinkedList 表所有结点的深拷贝构造方法this();/ 创建空单链表 ,只有头结点Node p=this.head.next;Node rear=this.head;while(p!=null)rear.next=new Node(p.data,null);rear=rear.next;p=p.next;16 / 18if(SinkedlinkedList=null)return;Node p=this.head;/p 指向头结点for(int j=0;p.next!=null&ji;i+)/ 定位于第 i-1 个结点p=p.next;p.next=new Node