管理 学院 信管 专业 12（1）班 学号 3112004734
姓名 钟臻华 协作者： 无 教师评定_________________
实验题目 线性表的基本操作
实验评分表
实验报告
一、 实验目的与要求
1. 本实验通过对线性表各种操作的算法设计，理解和掌握线性表的概念、存储结构及操作要求，体会顺序和链式两种存储结构的特点；
2. 根据操作的不同要求，选择合适的存储结构，设计并实现算法，对算法进行时间复杂度分析，从而达到掌握数据结构的研究方法、算法设计和分析方法的目的。
二、 实验内容
1. 分别用顺序表、单链表、单循环链表实现约瑟夫问题的求解，并分析基于不同存储结构算法的时间复杂度。如果采用顺序表实现时，每个元素出环并不执行删除操作，而将相应位置元素值设置为空，但计数时必须跳过值为空的元素，实现这种算法，并分析执行效率。
1.顺序表的不删除出环元素算法实现
publicclass Josephus3{
public Josephus3(int number,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("约瑟夫环("+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.println(list.toString());
}
if(!list.get(j).equals("null"))
System.out.println("被赦免者是"+list.get(j).toString());
}
}
publicstaticvoid 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++){
list.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());
}
publicstaticvoid main(String args[]){
new Josephus1(5,1,2);
}
}
3．书本例题的约瑟夫环的算法
publicclass 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());
}
publicstaticvoid 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值均为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++)//若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_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.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不能为空,空则返回null
return null;//顺序查找关键字为x的元素,返回首次出现的元素,若查找不成功返回null
Node<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(int j=0;p.next!=null&&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;
}
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。MAX_VALUE,list);
}
public void concat(SinglyLinkedList<T> list){
}
public boolean contain(SinglyLinkedList<T> list){
}
}
三、 实验结果和数据处理
（截图说明实验结果的正确性，如果有错误分析错误原因）
四、 总结
（谈谈自己在实验中遇到的问题，解决的方法）
五、 问题与讨论
1、 什么是头结点？在链表中设置头结点有什么作用？
头结点是单链表第一个结点之前增加的一个特殊结点，
作用是使所有链表（包括空链表）的头指针非空，并使对单链表的插入、删除操作不需要区分是否为空表或是否在第一个位置进行，从而与其他的位置插入、删除操作一致
2、 比较顺序存储结构和链式存储结构的优缺点。
顺序存储结构预先分配好内存，读写速度快，缺点是不可扩充容量，如果需要扩充则需要开辟一个更大存储空间把原来的数据重写进去。
链式存储结构无需担心容量的问题，读写速度要相对慢一些，因为是动态分配内存，由于要存储下一个结点的地址所以需要的存储空间比顺序存储大。