完整版12信管实验报告(线性表基本操作).docx

管理 学院 信管 专业 12（1） 班 学号 3112004734 姓名 钟臻华 协作者： 无 教师评定_实验题目 线性表的基本操作 实验评分表指导教师评分标准序号评分项目评分标准满分打分1完成度按要求独立完成实验准备、程序调试、实验报告撰写。202实验内容（1） 完成功能需求分析、存储结构设计；（2） 程序功能完善、可正常运行；（3） 测试数据正确，分析正确，结论正确。303实验报告内容齐全，符合要求，文理通顺，排版美观。404总结对实验过程遇到的问题能初步独立分析，解决后能总结问题原因及解决方法，有心得体会。10实验报告一、 实验目的与要求1. 本实验通过对线性表各种操作的算法设计，理解和掌握线性表的概念、存储结构及操作要求，体会顺序和链式两种存储结构的特点； 2. 根据操作的不同要求，选择合适的存储结构，设计并实现算法，对算法进行时间复杂度分析，从而达到掌握数据结构的研究方法、算法设计和分析方法的目的。 二、 实验内容1. 分别用顺序表、单链表、单循环链表实现约瑟夫问题的求解，并分析基于不同存储结构算法的时间复杂度。如果采用顺序表实现时，每个元素出环并不执行删除操作，而将相应位置元素值设置为空，但计数时必须跳过值为空的元素，实现这种算法，并分析执行效率。1.顺序表的不删除出环元素算法实现public class Josephus3public Josephus3(int number,int start,int distance)/创建约瑟夫环并求解,参数指定环长度,起始位置,计数 /采用线性顺序表存储约瑟夫环的元素,元素类型是字符串,构造方法参数指定顺序表的容量 SeqList list=new SeqList(number); String a=new String(null); for(int i=0;inumber;i+) list.append(char)(A+i)+); System.out.print(约瑟夫环(+number+,+start+,+distance+),); 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!=0) i=(i+1)%list.length(); if(!list.get(i).equals(null) num-; System.out.println(list.toString(); if(!list.get(j).equals(null) System.out.println(被赦免者是+list.get(j).toString(); public static void main(String args) new Josephus3(5,0,2); 运行结果:2.使用单链表实现的算法class Josephus1 public Josephus1(int number,int start,int distance)/创建约瑟夫环,参数指定环长度,起始位置,计数 /采用单链表存储约瑟夫环的元素,元素类型是字符串，构造方法参数指定单链表的容量 SinglyLinkedList list=new SinglyLinkedList(number); for(int i=0;i1)/多于一个对象时的循环 i=(i+distance-1)%list.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); 3书本例题的约瑟夫环的算法public class Josephus public Josephus (int number,int start,int distance)SeqList list=new SeqList(number);for(int i=0;i1)i=(i+distance-1)%list.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 Josephus(5,0,2);2. 实现教材P74 实验内容（3）的各成员方法。public class SinglyLinkedList implements LList /带头结点的单链表类,实现线性表接口 public Node head; /头指针,指向单链表的头结点 public SinglyLinkedList(int number)/默认构造方法,构造空单链表。创建头结点,data和next值均为null this.head=new Node(); public SinglyLinkedList(T element, int number)/由指定数组中的多个对象构造单链表,采用尾插入构造单链表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.next;/rear指向新的链尾结点/判断单链表是否为空,O(1)public boolean isEmpty()return 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类额toString()方法,O(n)public String toString()String str=(;Node p=this.head.next;/p从单链表的第一结点开始while(p!=null)str+=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 set(int i,T x)if(x=null)return;/不能设置空对象 if(i=0)Node p=this.head.next;/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结点后,O(n)if(x=null)/不能插入空对象return; /p指向头结点Node p=this.head;/寻找插入位置 头结点(i=0)for(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算法实现单链表的删除操作/删除序号为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.next;/遍历算法if(p.next!=null)T old=p.next.data;/获得原对象p.next=p.next.next;/删除p的后继结点return old; return null;/删除单链表的所有元素,java将自动收回各结点的所占用的内存空间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;/头结点的下一个结点while(p!=null)if(p.data.equals(x)return p.data;/返回首次出现的元素p=p.next; return null;public boolean contain(T x)/判断线性表是否包含关键字为x的元素return this.search(x)!=null;/以查找的结果获得判断结果/删除单链表中指定元素关键字x的remove()函数声明如下,使用顺序查找算法但未调用查找算法public void remove(T x)/删除首次出现的值为x的结点,若没有找到指定结点则不删除if(this.head.next=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.next=p.next;/头删除,中间/尾删除 中间删除public void removeAll(T x)public void replace(T x,T y)if(this.head.next=null|x=null|y=null)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 p1=this.head;/p指向头结点while(p1!=null)p1=p1.next;return p1.next; public Node getPrevious(Node p)Node p1=this.head;while(p1!=null)p1=p1.next;return p1;public Node getLast()Node p=this.head; while(p!=null) for(int j=0;p.next!=null&jInteger.MAX_VALUE;j+)/定位于最后一个结点之前的前一个结点 p=p.next; return p.next;/以下声明对单链表的子表进行操作的求子表、包含、插入、删除、替换等方法public SinglyLinkedList sub(int i,int n)if(i=0)Node p=this.head;for(int j=0;p.next!=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的结点p=p.next;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,SinglyLinkedList list) public SinglyLinkedList(SinglylinkedList list)/复制单链表所有结点的深拷贝构造方法 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; if(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(list,p.next);public void append(