管理学院信管专业12（1）班学号3112004734姓名钟臻华协作者：无教师评定_________________实验题目线性表的基本操作实验评分表实验报告一、实验目的与要求1.本实验通过对线性表各种操作的算法设计，理解和掌握线性表的概念、存储结构及操作要求，体会顺序和链式两种存储结构的特点；2.根据操作的不同要求，选择合适的存储结构，设计并实现算法，对算法进行时间复杂度分析，从而达到掌握数据结构的研究方法、算法设计和分析方法的目的。

二、实验内容1.分别用顺序表、单链表、单循环链表实现约瑟夫问题的求解，并分析基于不同存储结构算法的时间复杂度。

如果采用顺序表实现时，每个元素出环并不执行删除操作，而将相应位置元素值设置为空，但计数时必须跳过值为空的元素，实现这种算法，并分析执行效率。

1.顺序表的不删除出环元素算法实现public class Josephus3{public Josephus3(int number,int start,int distance){//创建约瑟夫环并求解,参数指定环长度,起始位置,计数//采用线性顺序表存储约瑟夫环的元素,元素类型是字符串,构造方法参数指定顺序表的容量S eqList<String> list=new SeqList<String>(number);S tring a=new String("null");f or(int i=0;i<number;i++)l ist.append((char)('A'+i)+"");S ystem.out.print("约瑟夫环("+number+","+start+","+distance+"),");S ystem.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.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<String> list=new SinglyLinkedList<String>(number);for(int i=0;i<number;i++){l ist.append((char)('A'+i)+"");//添加字符串对象}System.out.print("约瑟夫环("+number+","+start+","+distance+"),");//输出约瑟夫环的环长度,起始位置,计数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.println("被赦免者是"+list.get(0).toString());}public static void main(String args[]){n ew 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)('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()+",");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;//头指针,指向单链表的头结点public SinglyLinkedList(int number){//默认构造方法,构造空单链表。

创建头结点,data和next值均为nullthis.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++)//若element==null,抛出空对象异常{//element.length==0时,构造空链表rear.next=new Node<T>(element[i],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.head.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 str+")";}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指定序号无效则抛出序号越界异常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 void 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);}//在单链表的最后添加对象,O(n)public void append(T x){insert(Integer.MAX_V ALUE,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.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<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()函数声明如下,使用顺序查找算法但未调用查找算法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;//头删除,中间/尾删除中间删除}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<T> getFirst(){if(this.head.next==null)return head;//单链表不能为空return this.head.next;}//返回单链表的第一个结点，非头结点public Node<T> getNext(Node<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(intj=0;p.next!=null&&j<Integer.MAX_V ALUE;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;}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 void 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++)//定位于第i-1个结点p=p.next;p.next=new Node<T>(list,p.next);}public void append(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;}}insert(Integer。