数据结构|链队列的实现（实验3.4）

约定不等于承诺〃 2022-06-07 10:36 140阅读 0赞

# 一、实验目的 #

1、   熟练掌队列的结构特点，掌握队列的顺序存储和实现。

2、      学会使用队列解决实际问题。

二、实验内容

1、自己确定结点的具体数据类型和问题规模，建立一个链队列，实现队列的入队和出队操作。

三、实验步骤

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

template <typename T>  
    class LinkQueue
    {
    	public:
    		LinkQueue();
    		~LinkQueue()
    		{
    			Node<T> *deleteNode = NULL;
    			while(!Empty()){
    				deleteNode = front->next;
    				front->next = deleteNode->next;
    				if(deleteNode->next == NULL){
    					rear = front;
    				}
    				delete deleteNode;
    			}
    			delete front;
    		}
    		void EnQueue(T x);
    		T DeQueue();
    		T GetQueue();
    		void print();
    		int Empty(){return front == rear ? true : false;}
    	private:
    		Node<T> *front,*rear;

2.、相关操作的算法表达；

2.1 构造函数 初始化空队列

2.2入队操作函数：  
 \* 1.创建一个结点 s ，申请空间   
 \* 2.把 x 存储在结点 s 的 data 域中   
 \* 3.结点 s 的 data 域置为 NULL   
 \* 4.原队尾结点的 next 域置为结点 s 的地址，即原队尾结点与结点 s 相连   
 \* 5.队尾指针 rear 指向结点 s ，即结点 s 成为新队尾

2.3出队操作函数：   
 1.判断是否队空，若是返回 -1，否则   
 \* 2.创建一个结点 p ，其指向队头   
 \* 3.定义一个变量 x ，其记录队头结点存储的元素   
 \* 4.队头指针 front 的 next 域置为原队头的下一个结点的地址，即头结点与新队头相连   
 \* 5.判断原队头是否也是队尾，即当前队是否只剩下一个结点（不包括头结点），若是则队尾指针 rear 和队头指针 front 指向同一个结点，即头结点   
 \* 6.删除原队头  
 \* 7.返回原队头存储的元素 x

2.4取队头元素操作函数：   
 \* 1.判断是否队空，若是则返回-1，否则  
 \* 2.返回队头元素

2.5输出操作函数：按照顺序，输出栈元素

3、完整程序；

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

源代码如下：

#include<iostream>
    using namespace std;
    
    template < typename T >
    struct Node{
    	T data;  
        Node<T> *next;  
    };
    
    template <typename T>  
    class LinkQueue
    {
    	public:
    		LinkQueue();
    		~LinkQueue()
    		{
    			Node<T> *deleteNode = NULL;
    			while(!Empty()){
    				deleteNode = front->next;
    				front->next = deleteNode->next;
    				if(deleteNode->next == NULL){
    					rear = front;
    				}
    				delete deleteNode;
    			}
    			delete front;
    		}
    		void EnQueue(T x);
    		T DeQueue();
    		T GetQueue();
    		void print();
    		int Empty(){return front == rear ? true : false;}
    	private:
    		Node<T> *front,*rear;
    };
     
    template <typename T>
    LinkQueue<T>::LinkQueue()
    {
    	Node<T> *s;
    	s=new Node<T>;
    	s->next=NULL;
    	front=rear=s;
    }
    
    template <typename T>
    void LinkQueue<T>::EnQueue(T x)
    {
    	Node<T> *s;
    	s=new Node<T>;
    	s->data=x;
    	s->next=NULL;
    	rear->next=s;
    	rear=s;
    }
    
    template <typename T>
    T LinkQueue<T>::DeQueue()
    {
    	if(Empty()){  
            cout<<"队空！"<<endl;  
            return -1;  
        }
    	Node<T> *p; int x;
    	if(rear==front) throw"下溢";
    	p=front->next;
    	x=p->data;
    	front->next=p->next;
    	if(p->next==NULL) rear=front;
    	delete p;
    	return x;
    }
    
    template <typename T>
    T LinkQueue<T>::GetQueue()
    {
    	if(Empty())
    	{  
            cout<<"队空！"<<endl;  
            return -1;  
        }  
        return front->next->data;
    }
    
    template <typename T>
    void LinkQueue<T>::print()
    {
    	if(Empty()){  
            cout<<"队空！"<<endl;  
            return;  
        }  
        Node<T> *p = front->next;  
        while(p->next != NULL){  
            cout<<p->data<<" ";  
            p = p->next;  
        }  
        cout<<p->data<<endl;  
    }
    
    void main()
    {
    	LinkQueue<int>a;
    	cout<<"按顺序把“1，2，3，4，5”进入链队列"<<endl;
    	for(int i=1;i<=5;i++) a.EnQueue(i);
    	cout<<"结果如下："<<endl;
    	a.print();
    	cout<<"出队一个元素"<<a.DeQueue()<<"结果如下："<<endl;
    	a.print();
    	cout<<"现在队头元素为："<<a.GetQueue()<<endl;
    }

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

①总结

在程序内定义对象为int型，将元素1~5按顺序入队。

通过调用成员函数，实现入队、出队、输出等基本功能。

②运行结果如下:

![Center][]

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

经过上一次实验，我对队的相关知识已经有所了解。本次实验较为简单，因为实验内容较少，且对书本知识掌握得有点熟悉。但本次试验还是发现了自己的不足之处。经过改进、询问同学，成功完成了实验。收获颇丰。总的来说，我对理论知识有了更充分的理解，也能较大程度明白运行原理。

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

[Center]: /images/20220607/92e55ed4b3fd4540bc91c24dcf6240d5.png