数据结构|创建学生成绩的静态链表（实验2.4）

àì夳堔傛蜴生んèń 2022-06-07 02:58 183阅读 0赞

一、实验目的

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

二、实验内容

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

三、实验步骤

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

public:  
        SLL();//无参构造函数  
        SLL(T score[],int n);//带参构造函数  
        virtual ~SLL();//空的析构函数    
        void print();//遍历操作 
    	T get(int i);//按位查找操作
    	int Locate(T x);//按值查找操作
    	void insert(int i, T x);//插入操作
    	void Delete(int i);//删除操作
    private:  
        Node<T> node[Maxsize];//节点  
        int first;  
        int avail;//指向空闲链的头指针  
        int length;//当前静态链表的长度

2、相关操作的算法表达

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

插入操作：1.从空闲链最前端摘下一个结点，；

2.空闲链的头指针后移；

3.将摘下结点插入静态链表中；

删除操作：1.暂存被删结点下标；

2.摘链；

3.将结点插在空闲链最前端；

4.空闲链头指针指向结点；

由于结点元素类型不确定，因此采用C++模板机制。

源代码如下：

#include<iostream>
    #include<string>
    using namespace std;
    
    //静态链表的储存结构
    const int Maxsize = 100;
    template<typename T>
    class Node {
    public:
        T data;
        int next;      //存储指向下一个节点的数组下标
    };
    
    template <typename T>  
    class SLL {  
    public:  
        SLL();//无参构造函数  
        SLL(T score[],int n);//带参构造函数  
        virtual ~SLL();//空的析构函数    
        void print();//遍历操作 
    	T get(int i);//按位查找操作
    	int Locate(T x);//按值查找操作
    	void insert(int i, T x);//插入操作
    	void Delete(int i);//删除操作
    private:  
        Node<T> node[Maxsize];//节点  
        int first;  
        int avail;//指向空闲链的头指针  
        int length;//当前静态链表的长度
    };
    
    template<typename T>
    SLL<T>::SLL(T score[],int n)
    {
    	length = 0;
    	for(int i = 0; i<Maxsize; i++)
    	{
    		node[i].next=i+1;
    	}
    	node[Maxsize - 1].next = -1;  
        avail = 2;  
        first = 1;  
        node[first].next = -1;  
        for (int j = n-1; j >=0; j--)  
        {  
            if (avail == -1)  
            {  
                break;  
            }  
            int s = avail;  
            avail = node[avail].next;//空闲链的头指针后移  
            node[s].data = score[j];//将score[j]填入下标为S的节点  
            node[s].next = node[first].next;//将score[j]插到first后面  
            node[first].next = s;  
            length++;  
        }  
    }
    template<class T>  
    SLL<T>::~SLL()  
    {  
    }
    
    template<typename T>
    void SLL<T>::print()
    {
    	int s = node[first].next;
    	for (int i = 1; i <= length; i++)
    	{
    		cout << node[s].data << " ";
    		s = node[s].next;
    	}
    }	
    
    template<typename T>
    T SLL<T>::get(int i)
    {
    	if(i<=0 || i>length) throw"位置非法";
    	int p = first;
    	for(int j = 0; j<i; j++)
    	{
    		p=node[p].next;
    	}
    	return node[p].data;
    }
    
    template<typename T>
    int SLL<T>::Locate(T x)
    {
    	int count=0;
    	int p = first;
    	while(node[p].next != -1)
    	{
    		p=node[p].next;
    		if(node[p].data == x) return count+1;
    		count++;
    	}
    	return -1;
    }
    
    template<typename T>
    void SLL<T>::insert(int i, T x)
    {
    	if(i<0||i>length) throw"位置非法";
    	int p = first;
    	for(int j = 1; j<i; j++)
    	{   p=node[p].next;    /*或者p=node[p].next*/}
    	int s = node[avail].next;
    	node[avail].data = x;  
        node[avail].next = node[p].next;  
        node[p].next = avail;  
        avail = s;  
        length++;
    }
    
    template<typename T>
    void SLL<T>::Delete(int i)
    {
    	if(i<0||i>length+1) throw"位置非法";
    	int p = first;
    	for(int j = 1;j<=i; j++)
    	{    p=node[p].next;  }
    	int q = node[p].next;  
        T e = node[p].data;  
        node[p].next = node[q].next;  
        node[q].next = avail;  
        avail = q;  
    	length--;
    }
    
    void main()  
    {  
        float score[5]={95.7,68.2,37.8,84.5,76.5};  
        SLL<float> student(score,5);  
        cout<<"              学生数据结构成绩"<<endl;  
        student.print();  
        cout<<endl<<endl<<"在位置3插入成绩66，结果如下："<<endl;  
        student.insert(3,66);  
        student.print();  
        cout<<endl<<endl<<"在位置4删除成绩   删除后结果如下："<<endl;
    	student.Delete(3);
        student.print();  
        cout<<endl<<endl<<"位置2的成绩为："<<student.get(2)<<endl;  
        cout<<endl<<endl<<"成绩68.2所在位置为："<<student.Locate(68.2)<<endl;  
    }

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

①总结

在程序内规定成绩数组类型为float型，数组共有5个元素。 float score\[5\]=\{95.7,68.2,37.8,84.5,76.5\};

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

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

②运行结果如下:

![20171008175913163][]

③分析

静态链表使用数组来表示单链表，用数组元素的下标模拟单链表的指针。属于静态储存分配。

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

上次学习了静态链表后过了一段时间我才动手做实验，理论知识忘记了很多，通过查阅书本，网上浏览，虽然花费时间较多，但收获颇丰。总的来说，我对理论知识有了更充分的理解，也能较大程度明白运行原理。

俗话说“实践是检验真理的唯一标准”。在课堂上短短的学习时间，并不能很好地对所学知识有很好的理解，相反，我们更需要在课后多花时间上机实验，才能更大程度地掌握所学知识的原理。