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

ゞ浴缸里的玫瑰 2022-06-08 14:20 136阅读 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、相关操作的算法表达

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

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

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后移

源代码如下：

#include<iostream>
    using namespace std;
    
    template <typename T>
    struct Node  
    {  
        T data;  
        Node<T> *next;  
    };
    
    /*建立一个由n个学生成绩的顺序表，实现数据的对表进行插入、删除、查找等操作。分别输出结果。*/
    
    template <typename T>
    class LinkList{
    	public:
    		LinkList(); //无参构造函数，建立只有头结点的空链表
    
    		LinkList(T score[],int n);    //构造函数
    
    		~LinkList()                 //析构函数
    		{
    			Node<T> *q;
    			while(first!=NULL)
    			{
    				q=first;
    				first=first->next;
    				delete q;
    			}
    		}
    
    		void insert(int i,T x); //插入操作，在位置i插入元素x
    
    		T Delete(int i);//删除操作，删除位置i的元素
    
    		T get(int i);//按位查找
    
    		int locate(T x); //按值查找
    
    		void print();//输出操作
    	private:
    		Node<T> *first; //头指针  
    };
    
    template<class T>  
    LinkList<T>::LinkList()  
    {  
        first = new Node<T>;  
        first->next = NULL;  
    }
    
    template<typename T>  
    LinkList<T>::LinkList(T score[],int n)
    {
    	Node<T>*s;
    	first=new Node<T>; first->next=NULL; //初始化一个空链表
    	for(int i=0;i<n;i++)
    	{
    		s=new Node<T>;s->data=score[i];  //为每个数组元素建立一个结点
    		s->next=first->next;first->next=s;  //将结点s插入头结点之后
    	}
    }
    
    template<typename T>  
    void LinkList<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 LinkList<T>::Delete(int i)
    		{
    			Node<T> *q,*p; T x; int count;
    			p=first;count=0; //注意P指针要指向头结点
    			while(p!=NULL&&count<i-1)   //此操作目的是找到i-1个结点
    			{
    				p=p->next;
    				count++;
    			}
    			if(p==NULL||p->next==NULL)throw"位置";  //结点p不存在或p后继结点不存在
    			else{
    				q=p->next;x=q->data;  //暂存被删结点
    				p->next=q->next;
    				delete q;
    				return x;
    			}
    		}
    
    template<typename T>  
    T LinkList<T>::get(int i)
    		{
    	        Node<T>*p;int count;
    			p=first->next;count=1;
    			while(p!=NULL&&count<i)
    			{p=p->next;count++;}
    			if(p==NULL)throw"位置非法";
    			else return p->data;
    		}
    
    template<typename T>  
    int LinkList<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>  
    void LinkList<T>::print()
    		{
    	        Node<T>*p;
    			p=first->next;
    			while(p!=NULL)
    			{cout<<p->data<<"  ";;
    			p=p->next;
    			}
    		}
    
    void main()
    {
    	int score[5]={69,52,99,85,76};
    	LinkList<int>student(score,5);    //创建对象
    	cout<<"              学生数据结构成绩"<<endl;  
        student.print();  
        cout<<endl<<endl<<"在位置3插入成绩66，结果如下："<<endl;  
        student.insert(3,66);  
        student.print();  
        cout<<endl<<endl<<"在位置2删除成绩为："<<student.Delete(2)<<endl<<"删除后结果如下:"<<endl;  
        student.print();  
        cout<<endl<<endl<<"位置3的成绩为："<<student.get(3)<<endl;  
        cout<<endl<<endl<<"成绩99所在位置为："<<student.locate(99)<<endl;
    }

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

①总结

在程序内规定成绩数组类型为int型，数组共有5个元素。 int score\[5\]=\{69,52,99,85,76\};

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

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

②运行结果如下:

![Center][]

③分析

单链表是一种链式存取的数据结构，用一组地址任意的[存储单元][Link 1]存放线性表中的[数据元素][Link 2]。有输出、插入、查找、删除等基本操作供用户使用。

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

完成前一个实验，我以为对单链表也有一样的熟悉，可是当真正地开始写代码，才意识到许多课堂上被我忽略的一些问题，例如删除功能的返回值是元素值，例如指针的定义与之前所学的有所不同，又例如不同的功能对 while(p!=NULL)和while(p!=0&&count<i)的的使用不一样等等。

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

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

[Center]: /images/20220608/e5aefdf721b54e18b8ea17b46b0caf48.png
[Link 1]: https://baike.baidu.com/item/%E5%AD%98%E5%82%A8%E5%8D%95%E5%85%83
[Link 2]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0