数据结构--实验报告 线性表的基本操作

二、实验内容和要求

三、源代码

1)顺序表的代码

2)单链表的代码

四、测试结果

1)顺序表的测试结果  

2)单链表的测试结果  

五、心得体会 

实验一  线性表的基本操作及其应用

一、实验目的

1、帮助读者复习C++语言程序设计中的知识。

2、熟悉线性表的逻辑结构。

3、熟悉线性表的基本运算在两种存储结构上的实现。

4、掌握顺序表的存储结构形式及其描述和基本运算的实现。

5、熟练掌握动态链表结构及有关算法的设计

二、实验内容

题目一：顺序表的基本操作

[问题描述]

实现顺序表的建立、求长度，取元素、修改元素、插入、删除等顺序表的基本操作。

[基本要求]

（1）依次从键盘读入数据，建立带头结点的顺序表；

    （2）输出顺序表中的数据元素

（3）求顺序表的长度；

（4）根据指定条件能够取元素和修改元素；

（5）实现在指定位置插入和删除元素的功能。

（6）根据算法，将两个有序的顺序表合并成一个有序顺序表。 

[测试数据]   由学生任意指定。

题目二：单链表的基本操作

[问题描述]

实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。

[基本要求]

（1）依次从键盘读入数据，建立带头结点的单链表；

    （2）输出单链表中的数据元素

（3）求单链表的长度；

（4）根据指定条件能够取元素和修改元素；

（5）实现在指定位置插入和删除元素的功能。

（6）根据算法，将两个有序的单链表合并成一个有序单链表。 

[测试数据]   

由学生任意指定。

三、源代码

(一)顺序表的基本操作

#include

using namespace std;

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define OVERFLOW -2

typedef int Status;

typedef int ElemType;

#define LIST_INIT_SIZE  100

#define LISTINCREMENT  10

typedef struct  {          //结构体

    ElemType *elem;

    int length;

    int listsize;

}SqList;

SqList Lx;

Status InitList_Sq(SqList &L)      //分配空间

{    L.elem=new ElemType[LIST_INIT_SIZE];

     if(!L.elem)exit(OVERFLOW);

     L.length =0;

     L.listsize=LIST_INIT_SIZE;

     return OK;

}

Status ListInsert(SqList &L,int i,ElemType e)     //插入新元素

{    int *q,*p;ElemType *newbase;

if(i<1 || i>L.length+1) return ERROR;

if(L.length>=L.listsize)

    {        newbase=new ElemType[L.listsize+LISTINCREMENT];

         if(!newbase) exit(OVERFLOW);

        L.elem=newbase;

        L.listsize+=LISTINCREMENT;

    }

        q=&(L.elem[i-1]);

for (p=&(L.elem[L.length-1]);p>=q;--p)

          *(p+1)=*p;

     *q=e;

     ++L.length;

     return OK;

}

Status Listlength(SqList L)                     //长度

{    int *p=L.elem;                          //判断线形表是否存在

    while(p)

    {      return (L.length);    }

}

Status GetElem(SqList L, int i,ElemType &e)         //取元素

{ if(i<1 || i>L.length)

        return ERROR;

    else

    {    e=L.elem[i-1];

        return e;

    }

}

void MergeList(SqList La,SqList Lb,SqList &Lc)     //合并 

{    ElemType ai,bj;

    InitList_Sq(Lc);

    int i=1,j=1,k=0;

    int La_len,Lb_len;

    La_len=Listlength(La);

    Lb_len=Listlength(Lb);

while((i<=La_len)&&(j<=Lb_len))

    {    GetElem(La,i,ai);GetElem(Lb,j,bj);

     if(ai<=bj)

        {     ListInsert(Lc,++k,ai);++i;    }

        else

        {    ListInsert(Lc,++k,bj);++j;    }

    }

while(i<=La_len)

    {    GetElem(La,i++,ai);

        ListInsert(Lc,++k,ai);

    }

while(j<=Lb_len)

    {   GetElem(Lb,j++,bj);

        ListInsert(Lc,++k,bj);

    }

}

void show(SqList L,int i)                   //显示

{     int j;ElemType k;

cout<<"顺序表显示如下:"< for(j=0;j {    k=L.elem[j];

cout<"; }

if(j==i-1 && i>0)

{ k=L.elem[j]; cout< cout<}

void create(SqList &L,int n)                        //输入元素

{    int e;

for(int i=0;i { cin>>e;

        L.elem[i]=e;

        L.length=i+1;   }

}

Status ListDelete_Sq(SqList &L,int i,ElemType &e)          //删除

{    ElemType *p, *q;

if(i<1 || i>L.length) return ERROR;

    p=&(L.elem[i-1]);

    e=*p;

    q=L.elem+L.length-1;

for(++p;p<=q;++p) *(p-1)=*p;

    --L.length;

    return OK;

}

Status Listxiugei(SqList &L,int i,ElemType &e)           //修改

{ if(i<1 || i>L.length)

        return ERROR;

     else

    {    L.elem[i-1]=e;

         return OK;     }

}

void shuru(SqList &L1)                 //顺序表的创建

{    int a;

    InitList_Sq(L1);

cout<<"请输入顺序表的长度：";

cin>>a;

cout<<"请输入顺序表的元素(共"<    create(L1,a);

    show(L1,a);    

}

void chaxun(SqList &L1)                //取第i个位置的元素

{   int j;ElemType e1;

cout<<"请选择所要取出元素的位置:";

cin>>j;    

while(j<0||j>Listlength(L1))

{ cout<<"输入有误，请重新输入"<         cout<<"请选择所要取出元素的位置:";

     cin>>j; }

    GetElem(L1,j,e1);

cout<<"取出的元素为:"<void xiugai(SqList &L1)            //修改第i个位置的元素

{    int a;

    int j; ElemType e1;

    a=L1.length;

cout<<"请选择所要修改元素的位置:";

cin>>j;

while(j<0||j>Listlength(L1))

     { cout<<"输入有误，请重新输入"<         cout<<"请选择所要修改元素的位置:";

     cin>>j; }

cout<<"要修改成的元素:";

cin>>e1;

    Listxiugei(L1,j,e1);

cout<<"修改后的顺序表数据:"<    show(L1,a);    

}

void shanchu(SqList &L1)      //删除顺序表里的元素

{    int a;

    int j; ElemType e1;

    a=L1.length;

cout<<"请选择所要删除元素的位置:";

cin>>j;

while(j<0||j>Listlength(L1))

{ cout<<"输入有误，请重新输入"<         cout<<"请选择所要删除元素的位置:";

     cin>>j; }

    ListDelete_Sq(L1,j,e1);

cout<<"修改后的顺序表数据:"<    show(L1,a-1);

}

void charu(SqList &L1)                  //插入元素到顺序表里

{   int a; int j; ElemType e1;

    a=L1.length;

cout<<"请选择所要插入元素的位置:";

cin>>j;

while(j<0||j>Listlength(L1))

     { cout<<"输入有误，请重新输入"<         cout<<"请选择所要插入元素的位置:";

     cin>>j; }

cout<<"要插入的元素:";

cin>>e1;

    ListInsert(L1,j,e1);

cout<<"修改后的顺序表数据:"<    show(L1,a+1);

}

void hebing(SqList &L3)             //合并两个顺序表

{   SqList L1,L2;

    int a,b;

    InitList_Sq(L1);    InitList_Sq(L2); 

cout<<"请输入第一个有序表的长度："; cin>>a;

cout<<"请输入第一个有序表的元素(共"<    create(L1,a);

    show(L1,a);

cout<<"请输入第二个有序表的长度："; cin>>b;

cout<<"请输入第二个有序表的元素(共"<    create(L2,b);

    show(L2,b);

    MergeList(L1,L2,L3);

cout<<"合并后的有序表如下："; show(L3,a+b);

}

void main()                        //主菜单

{  int choice;

   for(;;)

{ cout<<" 顺序表的基本操作"< cout<<" 1.顺序表的创建"< cout<<" 2.顺序表的显示"< cout<<" 3.顺序表的长度"< cout<<" 4.取第i个位置的元素"< cout<<" 5.修改第i个位置的元素"< cout<<" 6.插入元素到顺序表里"< cout<<" 7.删除顺序表里的元素"< cout<<" 8.合并两个顺序表"< cout<<" 9.退出系统"< cout<<"请选择：";

cin>>choice;

       switch(choice)

      {   case 1:  shuru(Lx);break;

          case 2:  show(Lx,Lx.length);break;

case 3: cout<<"顺序表的长度:"<          case 4:  chaxun(Lx);break;

          case 5:  xiugai(Lx);break;

          case 6:  charu(Lx);break;    

          case 7:  shanchu(Lx);break;

          case 8:  hebing(Lx);break;

case 9: cout<<"退出系统!"< default : cout<<"输入有误，请重新选择"< }

}

(二)单链表的基本操作

#include

using namespace std;

#define true 1

#define false 0

#define ok 1

#define error 0

#define overflow -2

typedef int Status;

typedef int ElemType;

typedef struct LNode      //存储结构

{    ElemType data;

      struct LNode *next;

}LNode,*LinkList;

void CreateList(LinkList &L,int n)       //尾插法创建单链表

{    LinkList p;

      L=new LNode;

L->next=NULL; //建立一个带头结点的单链表

     LinkList q=L;          //使q指向表尾

for(int i=1;i<=n;i++)

     {    p=new LNode;

     cin>>p->data;

     p->next=NULL;

     q->next=p;

           q=p;     }

}

Status GetElem(LinkList L,int i,ElemType &e)//取第i个元素

{     LinkList p=L->next;

       int j=1;

      while(p&&j      {     p=p->next;

             ++j;    }

      if(!p||j>i) return error; //第i个元素不存在

     e=p->data;

      return ok;

}

Status LinkInsert(LinkList &L,int i,ElemType e)      //插入

{     LinkList p=L;

       int j=0;

       while(p&&j      {    p=p->next;

           ++j;     }                            //寻找第i-1个结点

      if(!p||j>i-1)

          return error;        //i小于1或者大于表长加1

      LinkList s=new LNode;     //生成新结点

      s->data=e;

      s->next=p->next; //插入L中

      p->next=s;

      return ok;

}

Status ListDelete(LinkList &L,int i,ElemType &e)    // 删除

{     LinkList p=L;

       LinkList q;

       int j=0;

       while(p->next&&j       {              //寻找第i个结点，并令p指向其前驱

            p=p->next;

            ++j;      }

     if(!(p->next)||j>i-1) return error; //删除位置不合理

q=p->next;

     p->next=q->next;                      //删除并释放结点

     e=q->data;

     delete(q);

     return ok;

}

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)         

{                                  //合并两个顺序链表

    LinkList pa,pc,pb;

pa=La->next;

pb=Lb->next;

    Lc=pc=La;

    while(pa&&pb)

    {   if(pa->data<=pb->data)

        {    pc->next=pa;

              pc=pa;

              pa=pa->next;   }

else

        {    pc->next=pb;

              pc=pb;

              pb=pb->next;   }

     }

     pc->next=pa?pa:pb;

    delete(Lb);

}  

void show(LinkList L)                 //显示

{    LinkList p;

     p=L->next;

     while(p)

    {     cout<data<<"-->";

         p=p->next;    }

cout<}

int Length(LinkList L,int i)                //表长

{     i=0;

       LinkList p=L->next;

       while(p)

      {      ++i;

               p=p->next;   }

     return i; 

}

void xiugai(LinkList L)                      //修改

{     int i,j=1;

       ElemType k;

       ElemType e,m;

       LinkList p=L->next;

       cout<<"请输入要修改的元素位置(0       cin>>i;

       GetElem(L,i,e);

       cout<<"该位置的元素:"<       cout<<"修改后的元素值:";

       cin>>k;

       while(p&&j       {     p=p->next;

               ++j;    }

       m=p->data;

       p->data=k;

       cout<<"修改后的单链表显示如下:"<      show(L);      

}

void hebing()                //合并两个单链表

{    int a,b;

     LinkList La,Lb,Lc; 

     cout<<"请输入第一个有序链表的长度:"<     cin>>a;

     cout<<"请输入第一个有序链表的元素共（"<     CreateList(La,a);

    show(La);

    cout<<"请输入第二个有序链表的长度:"<     cin>>b;

    cout<<"请输入第二个有序链表的元素共（"<     CreateList(Lb,b);

    show (Lb);

     MergeList(La,Lb,Lc);

     cout<<"合并后的有序链表如下："<    show(Lc);

}

void main()         //主函数

{     int select;

       int x;

       ElemType y;

       LinkList list;

      for(;;)

     {  cout<<" 单链表的基本操作"<        cout<<" 1.单链表的创建"<        cout<<" 2.单链表的显示"<        cout<<" 3.单链表的长度"<        cout<<" 4.取第i个位置的元素"<        cout<<" 5.修改第i个位置的元素"<        cout<<" 6.插入元素到单链表里"<       cout<<" 7.删除单链表里的元素"<        cout<<" 8.合并两个单链表"<        cout<<" 9.退出系统"<        cout<<"请选择:";

        cin>>select;

      switch(select)

     {  case 1:cout<<"请输入单链表的长度:"<               cin>>x;

               cout<<"请输入"<               CreateList(list,x);

               break;

       case 2: cout<<"单链表显示如下:"<              show(list);

               break;

       case 3: int s;

               cout<<"单链表的长度为:"<               break;

       case 4: cout<<"请选择所要取出元素的位置:";

               cin>>x;

               while(x<0||x>Length(list,s))

              {     cout<<"输入有误，请重新输入"<                    cout<<"请选择所要取出元素的位置:";

                   cin>>x;     }

              GetElem(list,x,y);

              cout<<"该位置的元素为:"<              break;

       case 5:  xiugai(list); break;

       case 6:  cout<<"请选择要插入的位置:"; cin>>x;

              while(x<0||x>Length(list,s))

             {    cout<<"输入有误，请重新输入"<                  cout<<"请选择所要插入元素的位置:";

                 cin>>x;      }

             cout<<"要插入的元素值:";

             cin>>y;

             LinkInsert( list,x,y);

             cout<<"插入后单链表显示如下:"<             show(list);

             break;

       case 7:  cout<<"请选择要删除的位置:";   cin>>x;

                while(x<0||x>Length(list,s))

               {       cout<<"输入有误，请重新输入"<                      cout<<"请选择所要删除元素的位置:";

                      cin>>x;      }

                ListDelete(list,x,y);

               cout<<"要删除的元素值:"<               cout<<"删除后的单链表显示如下:"<               show(list);

               break;

       case 8: hebing();

               break;

        case 9: exit(0);

                break;

         default : cout<<"输入有误，请重新输入"<                   break;

      }

    }

}

四、测试结果

1)顺序表 的测试结果

2)单链表的测试结果

五、心得体会

当听到老师说写数据结构实验报告时，我有点惊讶，才学了不到一个月，就要写实验报告。记得去年学习C++时，学了一个学期，程序设计用了三周，才完成的，这个实验报告居然要一周完成两个设计，觉得很难。但是现在一周过去了，我也写完了，自我感觉良好。

通过这次写实验报告，我深切的理解了这门课的本质。刚开始学这门课时，当时还不清楚这门课程的目的，现在，我真正的理解了：数据结构像是身体的骨骼，而C++是填充这骨骼的肉体，二者相结合才能使整个程序更加完整，健全。数据结构是个框架，模型，抽象数据类型中列举了各种操作，而所用的C++语言，将各种操作描述出来构成算法。数据结构+算法=程序设计。

在这次设计的过程中，我还遇到了，很多的问题。顺序表是按顺序存储的，用了一维数组来存储，又结合C++的程序设计，我又用了类，但是，在执行时出现了问题。后来问同学，指出我的错误，不过获益不少。我又重新整理思路，把顺序表的基本操作写好了。虽然走了很多弯路，但是让我认识到，一定要创新，大胆，不能按照旧的思路去干新的事情。

单链表写起来简单多了，这个很快就搞定了。但是细节上出了问题。比如说，有些变量的重复定义，有些变量又没有定义，在调用函数，就直接复制过来，没有改参数……通过修改，我深刻理解到：细节决定成败，在以后，不管做任何事情都要认真，细心。

这次的实验报告，让我受益匪浅，不仅有知识方面的，还有生活和精神上的。总之，我会继续我的兴趣编程，相信在编程的过程中，能不断的提高自己。