数据结构实验报告二线性表的顺序存储

时间:2024.3.23

实验报告二   线性表的顺序存储

班级: 2010XXX 姓名: HoogLe 学号: 2010XXXX  专业: XXXX

2858505197@qq.com

一、   实验目的:

(1)  掌握顺序表的基本操作的实现方法。

(2)  应用顺序表的基本算法实现集合A=AUB算法。

(3)  应用顺序表的基本算法实现两有序顺序表的归并算法。

二、   实验内容:

1、线性表顺序存储结构的基本操作算法实现(要求采用类模板实现)

[实现提示]  (同时可参见教材p5822-p60页算法、ppt)函数、类名称等可自定义,部分变量请加上学号后3位。

库函数载和常量定义:(代码)

#include<iostream>

using namespace std;

const int MaxSize=100;

(1)顺序表存储结构的定义(类的声明):(代码)

template <class datatype>      //定义模板类SeqList

class SeqList

{

public:

   SeqList( );       //无参构造函数

   SeqList(datatype a[ ], int n);       //有参构造函数

   ~SeqList(){};             //析构函数为空

   int Length();           //求线性表的长度

   datatype Get(int i);         //按位查找,取线性表的第i个元素

   int Locate(datatype item); //查找元素item

   void Insert(int i, datatype item); //在第i个位置插入元素item

   datatype Delete(int i);        //删除线性表的第i个元素

   void display();       //遍历线性表,按序号依次输出各元素

private:

   datatype data[MaxSize];      //存放数据元素的数组

   int length;            //线性表的长度

};

(2)初始化顺序表算法实现(不带参数的构造函数)

/*

*输    入:无

*前置条件:顺序表不存在

*功    能:构建一个顺序表

*输    出:无

*后置条件:表长为0

*/

实现代码:

template <class datatype>

SeqList<datatype>:: SeqList( )

{

  length=0;

}

(3)顺序表的建立算法(带参数的构造函数)

/*

*输    入:顺序表信息的数组形式a[],顺序表长度n

*前置条件:顺序表不存在

*功    能:将数组a[]中元素建为长度为n的顺序表

*输    出:无

*后置条件:构建一个顺序表

*/

实现代码:

template <class datatype>

SeqList<datatype>:: SeqList(datatype a[], int n)

{

    if (n>MaxSize)

    {

       cout<<"数组元素个数不合法"<<endl;

    }

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

       data[i]=a[i];

    length=n;

}(4)在顺序表的第i个位置前插入元素e算法

/*

*输    入:插入元素e,插入位置i

*前置条件:顺序表存在,i要合法

*功    能:将元素e插入到顺序表中位置i处

*输    出:无

*后置条件:顺序表插入新元素,表长加1

*/

实现代码:

template <class datatype>

void SeqList<datatype>::Insert(int i, datatype item)

{

    int j;

    if (length>=MaxSize)

    {

       cout<<"溢出"<<endl;

    }

    if (i<1 || i>length+1)

    {

       cout<<"i不合法!"<<endl;

    }

    for (j=length; j>=i; j--)

       data[j]=data[j-1];

    data[i-1]=item;

    length++;

}(5)删除线性表中第i个元素算法

/*

*输    入:要删除元素位置i

*前置条件:顺序表存在,i要合法

*功    能:删除顺序表中位置为i的元素

*输    出:无

*后置条件: 顺序表册除了一个元素,表长减1

*/

实现代码:

template <class datatype>

datatype SeqList<datatype>::Delete(int i)

{

    int item,j;

    if (length==0)

    {

       cout<<"表为空,无法删除元素!"<<endl;

    }

    if (i<1 || i>length)

    {

       cout<<"i不合法!"<<endl;

    }

    item=data[i-1];//获得要删除的元素值

    for (j=i; j<length; j++)

       data[j-1]=data[j];   //注意数组下标从0记

    length--;

    return item;

}(6)遍历线性表元素算法

/*

*输    入:无

*前置条件:顺序表存在

*功    能:顺序表遍历

*输    出:输出所有元素

*后置条件:无

*/

实现代码:

template<class datatype>

void SeqList<datatype>::display()

{

    if(length==0)

    {

       cout<<"表为空,无法输出!"<<endl;

    }

    for(int i=0;i<length;i++)

    {

       cout<<data[i]<<" ";

    }

}

(7)获得线性表长度算法

/*

*输    入:无

*前置条件:顺序表存在

*功    能:输出顺序表长度

*输    出:顺序表长度

*后置条件:无

*/

实现代码:

template <class datatype>

int SeqList<datatype>::Length()

{

    return Length;

}

(8)在顺序线性表中查找e值,返回该元素的位序算法

/*

*输    入:查询元素值e

*前置条件:顺序表存在

*功    能:按值查找值的元素并输出位置

*输    出:查询元素的位置

*后置条件:无

*/

实现代码:

template <class datatype>

int SeqList<datatype>::Locate(datatype item)

{    

      for (int i=0; i<length; i++)

            if (data[i]==item)

            return i+1 ; 

           //下标为i的元素等于item,返回其序号i+1

           return 0;  //查找失败

}

(9)获得顺序线性表第i个元素的值

/*

*输    入:查询元素位置i

*前置条件:顺序表存在,i要合法

*功    能:按位查找位置为i的元素并输出值

*输    出:查询元素的值

*后置条件:无

*/

实现代码:

template <class datatype>

datatype SeqList<datatype>::Get(int i)

{

    if (i<0||i>length)

    {

       cout<<"i不合法!"<<endl;

    }

    else return data[i-1];

}

(10)判表空算法

/*

*输    入:无

*前置条件:无

*功    能:判表是否为空

*输    出:为空返回1,不为空返回0

*后置条件:无

*/

实现代码:

template <class datatype>

bool SeqList<datatype>::Empty()

{

    if (length==0)

    {

       return 1;

    }

    else

    {

       return 0;

    }

}

 (11)求直接前驱结点算法

/*

*输    入:要查找的元素e,待存放前驱结点值e1

*前置条件:无

*功    能:查找该元素的所在位置,获得其前驱所在位置。

*输    出:返回其前驱结点的位序。

*后置条件:e1值为前驱结点的值

*/

实现代码:

template<class datatype>

int SeqList<datatype>::Pre(datatype item)

{

    int k=Locate(item)-1;

    if (k>0)

       return k;

    else

    {

       cout<<"无前驱结点!"<<endl;

       return 0;

    }

}

 (12)求直接后继结点算法

/*

*输    入:要查找的元素e,待存放后继结点值e1

*前置条件:无

*功    能:查找该元素的所在位置,获得其后继所在位置。

*输    出:返回其后继结点的位序。

*后置条件:e1值为后继结点的值

*/

实现代码:

template<class datatype>

int SeqList<datatype>::Suc(datatype item)

{

    int k=Locate(item)+1;

    if (k>length)

    {

       cout<<"无后继结点!"<<endl;

        return 0;

    }

    else

    {

       return k;

    }

}

上机实现以上基本操作,写出main()程序:

void main()

{

    SeqList<int> Seq;     //创建

    if(Seq.Empty())

    {

       cout<<"线性表为空!"<<endl; //判断是否为空操作

    }

    Seq.Insert(1,1);

    Seq.Insert(2,2);

    Seq.Insert(3,3);

    Seq.Insert(4,4);

    Seq.Insert(5,5);    //插入元素操作

    cout<<"输出插入的五个元素:"<<endl;

    Seq.display();      //按序号依次输出各元素

    cout<<endl;

    cout<<"2是第"<<Seq.Locate(2)<<"个元素"<<endl;  //查找元素位置

    cout<<"第五个元素是:"<<Seq.Get(5)<<endl;    //查找第五个元素

    cout<<"线性表的长度为:"<<Seq.Length()<<endl;  //输出线性表长度

    Seq.Delete(3);   //删除元素

    cout<<"删除第三个元素后的线性表为:"<<endl;

    Seq.display();      //输出删除元素后的线性表

    cout<<endl;

    cout<<"元素2前驱结点的位置为:"<<Seq.Pre(2)<<endl;              //获得前驱结点位置

    cout<<"元素2前驱结点的数值为:"<<Seq.Get(Seq.Pre(2))<<endl;      //获得前驱结点

    cout<<"元素4后继结点的位置为:"<<Seq.Suc(4)<<endl;               //获得后继结点位置

    cout<<"元素4后继结点的数值为:"<<Seq.Get(Seq.Suc(4))<<endl;       //获得后继结点

}

要求对每个算法都加以测试,判断是否正确;并测试不同类型数据的操作。

粘贴测试数据及运行结果:

2、用以上基本操作算法,实现A=AUB算法。(利用函数模板实现)

/*

*输    入:集合A,集合B

*前置条件:无

*功    能:实现A=AUB

*输    出:无

*后置条件:A中添加了B中的元素。

*/

实现代码:

template<class datatype>

SeqList<datatype> SeqList<datatype>::Add(SeqList<datatype>& item)

{

    if (item.Empty())

       return *this;

    else

    {

       int k=item.Length();

       int num=this->Length();

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

       {

           for(int j=0;j<num;j++)

           if (data[j]==item.Get(i))

           {

              break;

           }

           else if (num-1==j&&data[num-1]!=item.Get(i))

           {

              this->Insert(++num,item.Get(i));

           }

       }

       return *this;

    }

}

void main()

{

    SeqList<int> A,B;

    cout<<"A∪B的结果是:"<<endl;

    A.Insert(1,1);

    A.Insert(2,2);

    A.Insert(3,3);

    A.Insert(4,4);

    A.Insert(5,5);      //插入集合A中元素

    B.Insert(1,2);

    B.Insert(2,6);

    B.Insert(3,1);

    B.Insert(4,8);

    B.Insert(5,9);      //插入集合B中元素

    A.Add(B);

    A.display();

    cout<<endl;

}

粘贴测试数据及运行结果:

 


3、对以上顺序表类中的基本操作算法适当加以补充,实现向一个有序的(非递减)的顺序表中插入数据元素e算法。

/*

*输    入:插入元素e

*前置条件:顺序表已有序

*功    能:将元素e插入到顺序表中适当的位置,使顺序表依然有序

*输    出: 无

*后置条件:有序顺序表插入了新元素,且表长加1。

*/

实现代码:

template<class datatype>

void SeqList<datatype>::orderInsert(datatype item)

{

    int num=this->Length();

    for (int i=0;i<num;i++)

    {

       if ((data[i]<item&&data[i+1]>item))

       {

           for (int k=num;k>i;k--)

              data[k]=data[k-1];  

           data[i+1]=item;

           length++;

           break;

       }

       if (data[i]>item)

       {

           for(int k=num;k>i;k--)

              data[k]=data[k-1];

           data[i]=item;

           length++;

           break;

       }

    }

}

void main()

{

    SeqList<int> A,B;

    A.Insert(1,3);

    A.Insert(2,5);

    A.Insert(3,6);

    A.Insert(4,8);

    A.Insert(5,10);     //插入顺序表

    cout<<"原顺序表为:"<<endl;

    A.display();        //输出顺序表

    cout<<endl;

    A.orderInsert(2);  

    A.orderInsert(4);   //插入元素

    cout<<"插入新元素后的顺序表为:"<<endl;

    A.display();        //输出重新排序后的顺序表

}

粘贴测试数据及运行结果:

 

4、算法实现:La,Lb为非递减的有序线性表,将其归并为Lc,该线性表仍有序(未考虑相同时删除一重复值)(利用函数类板实现)

MergeList:

/*

*输    入:有序线性表La,有序线性表Lb

*前置条件:顺序表已有序

*功    能:将两线性表归并,不去掉相同元素

*输    出: 返回一个新的有序线性表Lc

*后置条件:无

*/

实现代码:

template<class datatype>

SeqList<datatype> SeqList<datatype>::ElseAdd(SeqList<datatype> Seq1,SeqList<datatype> Seq2)

{

    int num=Seq2.Length();

    for(int i=0;i<=num;i++){

       Seq1.orderInsert(Seq2.Get(i));

    }

    return Seq1;

}

void main()

{

    SeqList<int> La,Lb,Lc;

    La.Insert(1,2);

    La.Insert(2,4);

    La.Insert(3,6);

    La.Insert(4,8);   //插入La

    cout<<"La中元素为:"<<endl;

    La.display();     //输出La

    cout<<endl;

    Lb.Insert(1,3);  

    Lb.Insert(2,6);

    Lb.Insert(3,8);    //插入Lb

    cout<<"Lb中元素为:"<<endl;

    Lb.display();     //输出Lb

    cout<<endl;

    Lc=Lc.ElseAdd(La,Lb); //合并两线性表

    cout<<"合并后的Lc为:"<<endl;

    Lc.display();     //输出合并后的线性表

    cout<<endl;

}

粘贴测试数据及运行结果:

 


三、   心得体会:(含上机中所遇问题的解决办法,所使用到的编程技巧、创新点及编程的心得)

更多相关推荐:
数据结构 线性表操作实验报告

数据结构实验报告实验题目线性表的操作实验目的1掌握上机调试线性表的基本方法2掌握线性表的一些基本操作实验内容将两个有序链表合并为一个有序链表一需求分析1实验程序中先创建两个有序链表演示程序以用户和计算机的对话方...

数据结构线性表试验报告

线性表上机实习1实验目的1熟悉将算法转换为程序代码的过程2了解顺序表的逻辑结构特性熟练掌握顺序表存储结构的C语言描述方法3熟练掌握顺序表的基本运算查找插入删除等掌握顺序表的随机存取特性4了解线性表的链式存储结构...

数据结构线性表实验报告

数据结构实验报告院系应用科技学院专业电子信息工程姓名陈高雪学号班月日1实验目的1掌握线性表的基本运算2掌握顺序村存储的概念学会对顺序存储数据结构进行操作3加深对顺序存储数据结构的理解逐步培养解决实际问题的编程能...

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

一实验目的二实验内容和要求三源代码1顺序表的代码2单链表的代码四测试结果1顺序表的测试结果2单链表的测试结果五心得体会实验一线性表的基本操作及其应用一实验目的1帮助读者复习C语言程序设计中的知识2熟悉线性表的逻...

数据结构实验报告 线性表的顺序表示和实现

数学与计算科学学院实验报告实验项目名称线性表的顺序表示和实现所属课程名称数据结构A实验类型验证性实验日期20xx年4月5号班级信管1002班学号20xx44070218姓名张松涛成绩1234附录1源程序5678...

数据结构实验报告三线性表的链式存储

实验报告三线性表的链式存储班级20xxXXX姓名HoogLe学号20xxXXXX专业XXXX2858505197qqcom一实验目的1掌握单链表的基本操作的实现方法2掌握循环单链表的基本操作实现3掌握两有序链表...

数据结构线性表实验报告

浙江万里学院实验报告专业班级计算机111实验小组第十组实验日期20xx921

数据结构实验报告

专业年级学号学生姓名指导老师华中师范大学信息管理系编数据结构实验报告I实验要求1每次实验中有若干习题每个学生至少应该完成其中的两道习题2上机之前应作好充分的准备工作预先编好程序经过人工检查无误后才能上机以提高上...

川师数据结构实验报告(含截图)

数据结构实验教学大纲学时课程总64学分4实验学时24实验个数7实验学分15课程性质必做适用专业计算机科学与技术软件工程网络工程教材及参考书数据结构C语言版严蔚敏吴伟民清华大学出版社20xx年11月数据结构题集C...

数据结构实验报告

课程实验报告课程名称数据结构专业班级学号姓名指导教师报告日期计算机科学与技术学院目录1课程实验概述22实验一基于顺序结构的线性表实现21问题描述322系统设计323系统实现424效率分析113实验二基于链式结构...

北邮数据结构实验报告——线性表

北京邮电大学信息与通信工程学院线性表数据结构实验报告1实验要求一实验目的通过选择下面四个题目之一进行实现掌握如下内容熟悉C语言的基本编程方法掌握集成编译环境的调试方法学习指针模板类异常处理的使用掌握线性表的操作...

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

实验一线性表的基本操作及其应用一实验目的1帮助读者复习C语言程序设计中的知识2熟悉线性表的逻辑结构3熟悉线性表的基本运算在两种存储结构上的实现4掌握顺序表的存储结构形式及其描述和基本运算的实现5熟练掌握动态链表...

数据结构线性表实验报告(35篇)