数据结构|顺序表的建立（实验1）

超、凢脫俗 2022-06-08 07:41 173阅读 0赞

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

一、实验目的

1、熟练掌握线性表的结构特点，掌握顺序表的基本操作。

2、巩固 C++相关的程序设计方法与技术。

3、学会使用顺序表解决实际问题。

二、实验内容

1、顺序表的建立与操作实现 建立 n 个元素的顺序表（n 的大小和表里数据自己确定），实现相关的操作：输出，插入，删除，查找等功能。编写完整程序实现，程序语言不限定，使用技术形式不定。

三、实验步骤

1、依据实验内容分别说明实验程序中用到的数据类型的定义

SeqList () \{length=0;\}          //无参构造函数，建立空的顺序表

SeqList (T a\[\],int n);            //有参构造函数，建立长度为n的顺序表

~SeqList()\{\}                  //析构函数

TGet (int i);                  //按位查找函数

int Locate (T x);               //按值查找函数

void Insert(int i,T x);           //插入操作函数

T Delete (int i);               //删除操作函数

voidPrintList();               //输出操作函数

2、相关操作的算法表达

在代码中设定元素为float型，有6个元素。定义顺序表的数据类型——顺序表类SeqList，包括插入、删除、查找、输出等基本操作。

插入操作：1.如果表满了，则抛出上溢异常；

2.如果元素的插入位置不合理，则抛出位置非法；

3.将最后一个元素直至第i个元素分别向后移动一个位置；

4.将元素x填入位置i处；

5.表长加1。

删除操作：1.如果表空，则抛出下溢异常；

2.如果删除位置不合理，则抛出删除位置非法；

3.取出被删除元素；

4.将下标为i,i+1,…,n-1处的元素分别移到下标i-1,i,…,n-2处；

5.表长减1，返回被删除值。

查找操作：（1）按位查找

1. 在顺序表中查找第i个元素存储在数组中下标为i-1的位置；

2. 找到即输出数据。

（2）按值查找

1.从第一位开始依次查找与x值相同的元素；

2.找到即输出下标为i的元素的序号i+1；

3.查找失败即退出循环。

输出操作：1.按照下标，依次输出各元素。

源代码如下：

#include <iostream>
    using namespace std;
    
    const int MaxSize=100;
    template <typename T>
    class SeqList
    {
    public:
        SeqList () {length=0;}          //无参构造函数，建立空的顺序表
        SeqList (T a[],int n);          //有参构造函数，建立长度为n的顺序表
        ~SeqList(){}                    //析构函数
        int Length(){return length;}    //求线性表的长度
        T Get (int i);                  //按位查找
        int Locate (T x);               //按值查找
        void Insert(int i,T x);         //插入操作
        T Delete (int i);               //删除操作
        void PrintList();               //输出操作
    private :
        T data[MaxSize];                //存放数据元素的数组
        int length;                     //线性表长度
    };
    
    //构造函数
    template <typename T>
    SeqList<T>::SeqList(T a[],int n)
    {
        int i;
    	if(n>MaxSize) throw "参数非法";
        for(i=0;i<n;i++)
            data[i]=a[i];
        length=n;
    }
    
    //输出操作 PrintList
    template <typename T>
    void SeqList<T>::PrintList ()
    {
        int i;
    	for(i=0;i<length;i++)
            cout<<data[i]<<"  ";
    }
    
    //插入操作 Insert
    template <typename T>
    void SeqList<T>::Insert(int i,T x)
    {
        int j;
    	if(length>=MaxSize) throw "上溢";
        if(i<1||i>length+1) throw "位置非法";
        for(j=length;j>=i;j--)
            data[j]=data[j-1];
        data[i-1]=x;
        length++;
    }
    
    //删除操作 Delete
    template <typename T>
    T SeqList<T>::Delete (int i)
    {
        T x;
    	int j;
    	if(length==0) throw "下溢";
        if(i<1||i>length) throw "位置非法";
        x=data[i-1];
        for(j=i;j<length;j++)
            data[j-1]=data[j];
        length--;
        return x;
    }
    
    //查找操作
         //(1)按位查找 Get
    template <typename T>
    T SeqList<T>::Get(int i)
    {
        if(i<1&&i>length) throw "查找位置非法";
        else return data[i-1];
    }
        //(2)按值查找 Locate
    template <typename T>
    int SeqList<T>::Locate(T x)
    {
    	int i;
    	for(i=0;i<length;i++)
    		if(data[i]==x)return i+1;
    	return 0;
    }
    
    void main()
    {
        float score[6]={6.5,25.2,30,55,78,95};
        SeqList<float> List(score,6);  //类模板定义对象
    	cout<<"完整数据为："<<endl;
        List.PrintList();    //输出功能
    	cout<<endl<<"在位置3加入数据元素123，输出结果为："<<endl;
        List.Insert(3,123);   //插入功能
        List.PrintList();
    	cout<<endl<<"删除位置4的数据元素，输出结果为："<<endl;
        List.Delete(4);      //删除功能
        List.PrintList();
    	cout<<endl<<endl<<"--查找操作--"<<endl<<"“按位查找”查找位置2的数据元素值输出为："<<endl;
        cout<<List.Get(2)<<endl;         //按位查找
    	cout<<endl<<"“按值查找”查找值为25.2的数据元素的位置为：";
        cout<<List.Locate(25.2)<<endl;     //按值查找
    }

3、总结、运行结果和分析。

①总结

在程序内规定数组类型为float型，数组共有6个元素。float score\[6\]=\{6.5,25.2,30,55,78,95\};

定义了类模板的对象。 SeqList<float>List(score,6);

通过调用成员函数，实现输出、插入、查找、删除等基本功能。

②运行结果如下

![20170920231103430][]

③分析

顺序表是指用一组地址连续的存储单元依次存储数据元素的线性结构。有输出、插入、查找、删除等基本操作供用户使用。

4、总体收获和不足，疑问等。

在编写代码时，由于对顺序表不甚熟悉，构想代码花费了颇多时间。但通过多看书，回忆课堂内容，我顺利完成了顺序表的建立。

通过本次实验，我掌握了线性表的结构特点、顺序表的基本操作。 还巩固了 C++相关的程序设计方法。但我认为，下一步我还应该学会使用顺序表解决实际问题。