实验报告

附：源程序：

#include<stdio.h>

#include<stdlib.h>

#define ERROR 0;

#define OK 1;

typedef struct node

{

       char data;

       struct node *next;

} Node ,*Linklist;

Linklist CreateList(void);

void Print(Linklist list);

Node *Locate(Linklist L,int key);

int Inslist(Linklist L,int i,int e);

int Dellist(Linklist L,int i,int *e);

void main()

{

       int flag1,flag2,key,x,i;

       Node *p;

       int *r;

       Linklist head;

       printf("输入元素\n");

       head=CreateList();

       printf("请按提示选择操作\n");

       printf("1、输出单链表，输入“1”；\n2、按值查找，输入“2”；\n3、插入元素，输入“3”；\n4、删除元素，输入“4”。\n");

       scanf("%d",&flag1);

       switch(flag1)

       {

       case'1':printf("单链表输出如下：\n");

              Print(head);

              break;

       case'2':printf("请输入要查找的元素\n");

              scanf("%d",&key);

              p=Locate(head,key);

              break;

       case'3':printf("请输入要插入的元素\n");

              scanf("%d",&x);

              printf("请输入插入位置\n");

              scanf("%d",&i);

              flag2=Inslist(head,i,x);

              if(!flag2) printf("插入失败！\n");

              break;

       case'4':printf("请输入要删除元素的位置\n");

              scanf("%d",&i);

              flag2=Dellist(head,i,r);

              if(flag2) printf("删除成功！\n");

              else printf("删除失败!\n");

       }

       Print(head); 

}  

/*创建单链表*/

Linklist CreateList(void)

{ 

       char ch; 

       Linklist head; 

       Linklist s,r; 

       head=NULL; 

       s=NULL;

       while((ch=getchar())!='\n')

       { 

              r=(struct node*)malloc(sizeof(struct node)); 

              r->data=ch; 

              if(head==NULL) head=r; 

              else s->next=r;

              s=r;  

       }   

       if(s!=NULL)   

       {    

              s->next=NULL;   

       }  

       return head;

}

/*输出*/

void Print(Linklist list)

{ 

       Linklist a,b; 

       a=list; 

       while(a!=NULL) 

       {

              printf("%c ",a->data);

              b=a;

              a=a->next;

              free(b);    

       }

       printf("\n");

} 

/*按值查找*/

Node *Locate(Linklist L,int key)

{

       Node *p;

       int k=0;

       p=L->next;

       while(p!=NULL)

              if(p->data!=key)

              {

                     p=p->next;

                     k++;

              }

              else printf(" %d 的位置为：\n",key,k+1);

              return p;

}

/*插入*/

int Inslist(Linklist L,int i,int e)

{

       Node *pre,*s;

       int k;

       if(i<=0) return ERROR;

       pre=L;

       k=0;

       while(pre!=NULL&&k<i-1)

       {

              pre=pre->next;

              k++;

       }

       if(!pre)

       {

              printf("输入位置不合理\n");

              return ERROR;

       }

       s=(struct node*)malloc(sizeof(struct node));

       s->data=e;

       s->next=pre->next;

       pre->next=s;

       return OK;

}

/*删除*/

int Dellist(Linklist L,int i,int *e)

{

       Node *pre,*r;

       int k;

       if(i<=0) return ERROR;

       pre=L;

       k=0;

       while(pre->next!=NULL&&k<i-1)

       {

              pre=pre->next;

              k++;

       }

       if(!(pre->next))

       {

              printf("删除位置不合理\n");

              return ERROR;

       }

       r=pre->next;

       pre->next=r->next;

       *e=r->data;

       free(r);

       return OK;

}

 

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

  管理  学院     信管  专业       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、    比较顺序存储结构和链式存储结构的优缺点。

顺序存储结构预先分配好内存，读写速度快，缺点是不可扩充容量，如果需要扩充则需要开辟一个更大存储空间把原来的数据重写进去。

链式存储结构无需担心容量的问题，读写速度要相对慢一些，因为是动态分配内存，由于要存储下一个结点的地址所以需要的存储空间比顺序存储大。