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

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

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

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

4、夫环("+number+","+start+","+distance+"),"); System.out.println(list.toString(); int i=start+distance-1; for(int j=1;j<list.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.

5、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)/创建约瑟夫环,参数指定环长度,起始位置,计数 /采用单链表

6、存储约瑟夫环的元素,元素类型是字符串，构造方法参数指定单链表的容量 SinglyLinkedList<String> list=new SinglyLinkedList<String>(number); for(int i=0;i<number;i+) list.append(char)('A'+i)+"");/添加字符串对象 System.out.print("约瑟夫环("+number+","+start+","+distance+"),");/

7、输出约瑟夫环的环长度,起始位置,计数 System.out.println(list.toString();/输出单链表的描述字符串A,B,C,D,E int i=start; while(list.length()>1)/多于一个对象时的循环 i=(i+distance-1)%list.length();/计数按循环规律变化,单链表可以看作是环形结构(循环单链表) System.out.print("删除"+list.remove(i)+","); System.out.println(list.toString(); System.out.pr

8、intln("被赦免者是"+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<String> list=new SeqList<String>(number);for(int i=0;i<number;i+)list.append(char)(&

9、#39;A'+i)+" ");System.out.print("约瑟夫环("+number+","+start+","+distance+"),");System.out.println(list.toString();int i=start;while(list.length()>1)i=(i+distance-1)%list.length();/循环顺序表System.out.print("删除"+list.remove(i).toString()+&qu

10、ot;,");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<T> implements LList<T> /带头结点的单链表类,实现线性表接口 public Node<T> head; /

11、头指针,指向单链表的头结点 public SinglyLinkedList(int number)/默认构造方法,构造空单链表。创建头结点,data和next值均为null this.head=new Node<T>(); public SinglyLinkedList(T element, int number)/由指定数组中的多个对象构造单链表,采用尾插入构造单链表this( number);/创建空单链表,只有头结点Node<T> rear=this.head;/rear指向单链表最后一个结点for(int i=0;i<element.length;i+)/

12、若element=null,抛出空对象异常/element.length=0时,构造空链表rear.next=new Node<T>(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<T> p=this.he

13、ad.next;/p从单链表第一结点开始while(p!=null)i+;p=p.next;return i;/返回单链表的所有元素的描述字符串,形式为"(,)",覆盖Object类额toString()方法,O(n)public String toString()String str="("Node<T> p=this.head.next;/p从单链表的第一结点开始while(p!=null)str+=p.data.toString();if(p.next!=null)str+=","p=p.next;return st

14、r+")"public T get(int i)/返回第i(i>=0)个元素,若i指定序号无效,则返回null 返回单链表的第i个元素的算法if(i>=0) Node<T> p=this.head.next;/p从单链表的第一个结点开始 头结点是单链表的第一个结点之前的一个特殊的结点，并非单链表的第一个结点for(int j=0;p!=null&&j<i;j+)p=p.next;if(p!=null)return p.data;/p指向第i个结点 return null; /设置第i(i>=0)个元素值为x,若i指定序号无

15、效则抛出序号越界异常public void set(int i,T x)if(x=null)return;/不能设置空对象 if(i>=0)Node<T> p=this.head.next;/p从单链表的第一个结点开始for(int j=0;p!=null&&j<i;j+)p=p.next;if(p!=null)p.data=x;/p指向第i个结点else throw new IndexOutOfBoundsException(i+"");/抛出序号越界异常/以下insert()、append()算法实现单链表插入操作public v

16、oid insert(int i,T x)/将x对象插入在序号为i结点前,也即插入在序号为i-1结点后,O(n)if(x=null)/不能插入空对象return; /p指向头结点Node<T> p=this.head;/寻找插入位置 头结点(i=0)for(int j=0;p.next!=null&&j<i;j+) p=p.next;/循环停止时,p指向第i-1结点或最后一个结点/插入x作为p结点的后继结点,包括头插入(i<=0)、中间/尾插入(i>0) p.next=new Node<T>(x,p.next);/在单链表的最后添加对象

17、,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<T> p=this.head;for(int j=0;p.next!=null&&j<i;j+)/定位到待删除结点(i)的前驱结点(i-1) 头结点(i=0)p=p.next;/遍历算法if(p.n

18、ext!=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)/关键字

19、x不能为空,空则返回nullreturn null;/顺序查找关键字为x的元素,返回首次出现的元素,若查找不成功返回nullNode<T> 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()函数声明如下,使

20、用顺序查找算法但未调用查找算法public void remove(T x)/删除首次出现的值为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.next;if(p!=null)front.next=p.next;/头删除,中间/尾删除 中间删除pub

21、lic 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<T> getFirst()if(this.head.next=null)return head;/单链表不能为空return this.head.next;/返回单链表的第一个结点，非头结点public Node<T> getNext(Node<

22、T> p)Node<T> p1=this.head;/p指向头结点while(p1!=null)p1=p1.next;return p1.next; public Node<T> getPrevious(Node<T> p)Node<T> p1=this.head;while(p1!=null)p1=p1.next;return p1;public Node<T> getLast()Node<T> p=this.head; while(p!=null) for(int j=0;p.next!=null&&am

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

24、return null;for(int i=0;i<n;i+)p=p.next;return p;public void remove(int i,int n)if(i>=0)Node<T> p=this.head;for(int j=0;p.next!=null&&j<i;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;i<n;i+)p=p.next;public voi

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