数据结构|创建学生成绩的双链表（实验2.3）

Bertha 。 2022-06-07 02:48 203阅读 0赞

一、实验目的

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

二、实验内容

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

三、实验步骤

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

public：
            DLL();
    DLL(T score[], int n);  //有参构造函数
    ~DLL();  //析构函数
    int Length(); //返回单链表长度
    void insert(int i, T x); //插入操作，在位置i插入元素
    T get(int i);  //按位查找
    int locate(T x);  //按值查找
    T Delete(int i);  //删除操作
    void print();  //遍历操作
    private:
    Node<T> *first;  //双链表的头指针
    int length;   //链的长度计数

2、相关操作的算法表达

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

插入操作：1.工作指针p，s初始化；

2.查找第i-1个结点并使工作指针p指向该节点；

3.若查找不成功，说明插入位置不合理，抛出插入位置非法；

否则，3.1 生成一个元素值为x的新结点s；

3.2  将新结点插入到结点p之后(与单链表有所不同）；

删除操作：1.工作指针p初始化，累加器count初始化；

2.查找第i-1个结点并使工作指针p指向该节点；

3.若p不存在或p的后继结点不存在，抛出插入位置非法；

否则，3.1 暂存被删结点和被删元素值；

3.2  摘链，将结点p的后继结点从链表上摘下；

3.3  释放被删结点

3.4  返回被删元素值

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

1.工作指针p初始化，累加器count初始化；

2.从头指针出发顺next域逐个结点往下搜索直到某个结点，判断是否为第i个结点。

3. 若是，则查找成功；否则将工作指针p后移；

（2）按值查找

1.工作指针p初始化，累加器count初始化；

2.对单链表中各元素依次进行比较。查找成功则返回元素序号；否则，返回0表示查找失败；

输出操作：1.工作指针p初始化；

2.重复执行下述操作，直到p为空：

2.1 输出结点p的数据域；

2.2工作结点p后移

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

源代码如下：

#include<iostream>
    using namespace std;
    
    template <typename T>
    class  Node
    {
    public:
    	T data;
    	Node<T> *prior;
    	Node<T> *next;
    };
    
    template <typename T>
    class DLL {
    public:
    	DLL();
    	DLL(T score[], int n);  //有参构造函数
    	~DLL();  //析构函数
    	int Length(); //返回单链表长度
    	void insert(int i, T x); //插入操作，在位置i插入元素
    	T get(int i);  //按位查找
    	int locate(T x);  //按值查找
    	T Delete(int i);  //删除操作
    	void print();  //遍历操作
    private:
    	Node<T> *first;  //双链表的头指针
    	int length;   //链的长度计数
    };
    
    template <typename T>
    DLL<T>::DLL(T score[], int n)
    {
    	length=0;
    	first = new Node<T>;
    	first->next = NULL;
    	first->prior = NULL;
    	for (int i = 0; i<n; i++)
    	{
    		Node<T> *s = new Node<T>;
    		s->data = score[i];
    		s->next = first->next; 
    	    first->next = s;
    	}
    }
    
    template <typename T>
    DLL<T>::~DLL()
    {
    	while (first->next!=first->prior)
        {
            //临时指针，存储即将释放的节点的指针
            Node<T> *temp = first;
            //脱链
            first->prior->next = first->next;
            first->next -> prior = first->prior;
            //头指针后移
            first = first->next;
            //释放内存
            delete temp;
        }
        delete first;
    }
    
    template<typename T>
    int DLL<T>::Length()
    {
        Node<T> *p; int count;
    	p=first->next;  
        count=0;  
        while(p!=NULL)
    	{  
            p=p->next;  
            count++;  
         }  
        return length;
    }
    
    template <typename T>
    void DLL<T>::insert(int i,T x)
    {
    	Node<T>*p,*s;int count;  
        p=first;   
        count=0;  
        while(p!=NULL&&count<i-1)  
        {  
            p=p->next;  
            count++;          
         }  
         if(p==NULL) throw"位置";  
         else
    	 {  
           s=new Node<T>;  
           s->data=x;  
           s->next=p->next;  
           p->next=s;  
         }
    }
    
    template <typename T>
    T DLL<T>::get(int i)
    {
    	Node<T> *p;int count; count = 1;
    	p = first->next; 
    	while (p != NULL&&count<i)
    	{
    		p = p->next; count++;
    	}
    	if (p == NULL)throw"位置非法";
    	else return p->data;
    }
    
    template <typename T>
    int DLL<T>::locate(T x)
    {
    	Node<T> *p; int count;
    	p = first->next; count = 1;
    	while (p!= NULL)
    	{
    		if (p->data == x) return count;
    		p = p->next;
    		count++;
    	}
    	return 0;
    }
    
    template <typename T>
    T DLL<T>::Delete(int i)
    {
    	Node<T> *p,*q;
    	p = first->next; int count, x; count = 1;
    	while (p != NULL&&count<i-1)
    	{
    		p = p->next; count++;
    	}
    	if (p == NULL || p->next == NULL) throw"位置非法";
    	else
    	{  
            q = p->next;  
            x=q->data;  
            if (p->next != NULL)
    		{  
                if(q->next!=NULL)  
            q->next->prior = p;
                else
    			{
    				p->next=NULL;
    				p->next = q->next;
    				delete q;
    				q = NULL;
    				return x;
    			}
    		}
    		p->next = q->next;
    		delete q;  
            q = NULL;  
            return x;
    	}
    }
    
    template <typename T>
    void DLL<T>::print()
    {
    	Node<T> *p;
    	p = first->next;
    	while (p->next != NULL)
    	{
    		cout << p->data << " ";
    		p = p->next;
    	}
    	cout << p->data << endl;
    }
    
    void main()
    {
    	float score[8] = { 66.5,89.5,95,74.5,32.5,68,100,86.5 };
    	DLL<float>student(score, 8);
    	cout << "     学生数据结构成绩" << endl;
    	student.print();
    	cout << endl << endl << "在位置3插入成绩78，插入后结果如下：" << endl;
    	student.insert(3,66);
    	student.print();
    	cout << endl << endl << "在位置2删除成绩为：" << student.Delete(2) <<" , "<< "删除后结果如下:" << endl;
    	student.print();
    	cout << endl << endl << "位置3的成绩为：" << student.get(3) << endl;
    	cout << endl << endl << "成绩32.5所在位置为：" << student.locate(32.5) << endl;
    }

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

①总结

在程序内规定成绩数组类型为float型，数组共有8个元素。 float score\[8\] = \{ 66.5,89.5,95,74.5,32.5,68,100,86.5 \};

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

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

②运行结果如下:

![Center][]

③分析

双链表的每个数据结点中都有两个[指针][Link 1]，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。在双链表中求表长、查找、遍历等操作的实现与单链表基本相同，只有插入、删除有所不同。由于循环双链表是一种对称结构，在结点P之前或之后的插入和删除非常容易。

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

完成本次双链表的实验时间恰逢在国庆，假期之余花了较多时间完成本次实验。总的来说，双链表与单链表的功能实现基本相同，但也有不同之处，例如删除和插入的功能。实验之初，参考了课本上的部分代码，但没有仔细思考便使用了，导致程序一直无法运行，浪费了许多时间。后来经过百度提问，询问同学，终于将错误改正过来，完成了本次实验。

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

通过本次实验，我也加深了对双链表相关功能操作的理解。但我还需花更多的时间来学习这门课程。

[Center]: /images/20220607/394dd703133f470f9d1e78c00aed5ca8.png
[Link 1]: https://baike.baidu.com/item/%E6%8C%87%E9%92%88