数据结构|创建学生成绩的顺序表（实验2.1）

布满荆棘的人生 2022-06-08 13:07 211阅读 0赞

一、实验目的

巩固线性表的数据结构的存储方法和相关操作，学会针对具体应用，使用线性表的相关知识来解决具体问题。  
  
二、实验内容

建立一个由n个学生成绩的顺序表，n的大小由自己确定，每一个学生的成绩信息由自己确定，实现数据的对表进行插入、删除、查找等操作。分别输出结果。

三、实验步骤

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

SeqList(T score[],int n);        //构造函数，建立一个长度为n的顺序表
    ~SeqList(){}                       //析构函数
    void insert(int i,T x);          //插入操作，在位置i插入元素x
    T Delete(int i);                   //在位置i删除对应元素
    T get(int i);                         //按位查找，找位置i的元素
    int locate(T x);                   //按值查找，找数值为x的元素
    void print();                        //遍历操作，按序号依次输出各元素

2、相关操作的算法表达

在代码中设定元素为float型，有8个元素。定义顺序表的数据类型——顺序表类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 max=100;
    
    /*建立一个由n个学生成绩的顺序表，每一个学生的成绩信息由自己确定，实现数据的对表进行插入、删除、查找等操作。分别输出结果。*/
    
    template <typename T>
    class SeqList{
    	public:
    		SeqList(T score[],int n);     //构造函数，建立一个长度为n的顺序表
    		~SeqList(){}                  //析构函数
    		void insert(int i,T x);       //插入操作，在位置i插入元素x
    		T Delete(int i);              //在位置i删除对应元素
    		T get(int i);                 //按位查找，找位置i的元素
    		int locate(T x);              //按值查找，找数值为x的元素
    		void print();                 //遍历操作，按序号依次输出各元素
    	private:
    		T data[max];                  //存放数据元素的数组
    		int length;                   //线性表的长度
    };
    
    //构造函数
    
    template <class T>
    SeqList<T>::SeqList(T score[],int n)
    {
    	if(n>max)throw"参数非法";
    	for(int i=0;i<n;i++)
    		data[i]=score[i];
    	length=n;
    }
    
    //插入操作
    
    template <class T>
    void SeqList<T>::insert(int i,T x)
    {
    	int j;
    	if(length>max)throw"上溢";
    	if(i<1||i>=max)throw"位置非法";
    	for(j=length;j>=i;j--)
    		data[j]=data[j-1];
    	data[i-1]=x;
    	length++;
    }
    
    //删除操作
    
    template <class T>
    T SeqList<T>::Delete(int i)
    {
    	T p;int j;
    	if(length==0)throw"下溢";
    	if(i<1||i>=max)throw"位置非法";
    	p=data[i-1];
    	for(j=i;j<length;j++)
    		data[j-1]=data[j];
    	length--;
    	return p;
    }
    
    //查找操作
          //按位查找
    
    template <class T>
    T SeqList<T>::get(int i)
    {
    	if(i<1&&i>=length)throw"查找位置非法";
    	else return data[i-1];
    }
    
          //按值查找
    template <class T>
    int SeqList<T>::locate(T x)
    {
    	for(int i=0;i<length;i++)
    		if(data[i]==x) return i+1;    //返回元素序号
    		return 0;
    }
    
    //输出操作
    
    template <class T>
    void SeqList<T>::print()
    {
    	for(int i=0;i<length;i++)
    		cout<<data[i]<<"  ";
    }
    
    void main()
    {
    	float score[8]={95.5,78,87.5,65,100,84.5,75,69.5};
    	SeqList<float> student(score,8);
    	cout<<"              学生数据结构成绩"<<endl;
    	student.print();
    	cout<<endl<<endl<<"在位置3插入成绩66，结果如下："<<endl;
    	student.insert(3,66);
    	student.print();
    	cout<<endl<<endl<<"在位置5删除成绩为："<<student.Delete(5)<<endl<<"删除后结果如下:"<<endl;
    	student.print();
    	cout<<endl<<endl<<"位置6的成绩为："<<student.get(6)<<endl;
    	cout<<endl<<endl<<"成绩100所在位置为："<<student.locate(100)<<endl;
    }

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

①总结

在程序内规定成绩数组类型为float型，数组共有8个元素。float score\[8\]=\{95.5,78,87.5,65,100,84.5,75,69.5\};

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

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

②运行结果如下:

![Center][]

③分析

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

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

由于已经完成了实验一（顺序表的创建等），我对顺序表有了更深刻的了解，但经过反思，实验一对课本知识点的参考性比较大，所以在本次实验中增加了独立思考的时间。

一开始不明白为什么课本上的删除操作函数有返回值，后来创建对象，通过对象调用成员函数来完成一些操作时，才明白原因，原来这样可以更方便地输出所删除的元素。另外，在写代码时，还发现了需要搞清楚实现的流程，要注意上溢下溢以及位置非法等情况在不同功能中是否需要使用等。