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

管理学院信管专业12（1）班学号3112004734

姓名钟臻华协作者：无教师评定_________________

实验题目线性表的基本操作

实验评分表

实验报告

一、实验目的与要求

1.本实验通过对线性表各种操作的算法设计，理解和掌握线性表的概

念、存储结构及操作要求，体会顺序和链式两种存储结构的特点；

2.根据操作的不同要求，选择合适的存储结构，设计并实现算法，对

算法进行时间复杂度分析，从而达到掌握数据结构的研究方法、算法设计和分析方法的目的。

二、实验内容

1.分别用顺序表、单链表、单循环链表实现约瑟夫问题的求解，并分

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

1.顺序表的不删除出环元素算法实现

public class Josephus3{

public Josephus3(int number,int start,int distance){//创建约瑟夫环并求解,参数指定环长度,起始位置,计数

//采用线性顺序表存储约瑟夫环的元素,元素类型是字符串,构造方法参数指定顺序表的容量

S eqList list=new SeqList(number);

S tring a=new String("null");

f or(int i=0;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

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;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 list=new SeqList(number);

for(int i=0;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);

}

}