数据结构链队列算法

野性酷女 2022-06-18 01:56 229阅读 0赞

法一
    
    #include<iostream.h>
    #include<malloc.h>
    #define OK 1.0
    #define ERROR 0.0
    #define TRUE 1.0
    #define FALSE 0.0
    typedef int ElemType;
    typedef float Status;
    typedef struct QNode
    {
    	ElemType data;
    	struct QNode *next;
    }QNode, *QueuePtr;
    typedef struct
    {
    	QueuePtr front;//队头指针
    	QueuePtr rear;//队尾指针
    }LinkQueue;
    
    
    Status InitQueue(LinkQueue &Q)
    {
    	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    	Q.front->next = NULL;
    	return OK;
    }
    
    Status DestroyQueue(LinkQueue &Q)
    {
    	while (Q.front)
    	{
    		Q.rear = Q.front->next;
    		free(Q.front);
    		Q.front = Q.rear;
    	}
    	return OK;
    }
    
    
    Status ClearQueue(LinkQueue &Q)
    {
    	Q.front = Q.rear;
    	return OK;
    }
    
    Status QueueEmpty(LinkQueue &Q)
    {
    	if (Q.front == Q.rear) return TRUE;
    	return FALSE;
    }
    
    int QueueLength(LinkQueue &Q)
    {
    	QueuePtr p = Q.front->next;
    	int i = 0;
    	while (p != NULL)
    	{
    		i++;
    		p = p->next;
    	}
    	return i;
    }
    
    
    //若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR
    Status GetHead(LinkQueue &Q, ElemType &e)
    {
    	if (Q.front->next == NULL) return ERROR;
    	e = Q.front->next->data;
    	return OK;
    }
    
    
    //入队
    Status EnQueue(LinkQueue &Q, ElemType e)
    {
    	QueuePtr p;
    	p = (QueuePtr)malloc(sizeof(QNode));
    	p->data = e;
    	p->next = NULL;
    	Q.rear->next = p;
    	Q.rear = p;
    	return OK;
    }
    
    
    Status DeQueue(LinkQueue &Q, ElemType &e)
    {
    	QueuePtr p;
    	if (Q.front == Q.rear) return ERROR;
    	p = Q.front->next;
    	e = p->data;
    	Q.front->next = p->next;
    	if (Q.rear == p) Q.rear = Q.front;
    	free(p);
    	return OK;
    }
    
    
    Status PrintQueue(LinkQueue &Q)
    {
    	QueuePtr p;
    	p = Q.front->next;
    	while (p)
    	{
    		cout << p->data << endl;
    		p = p->next;
    	}
    	return OK;
    }
    
    int main()
    {
    	int a;
    	LinkQueue q;
    	InitQueue(q);
    	EnQueue(q, 1);
    	EnQueue(q, 2);
    	EnQueue(q, 3);
    	GetHead(q, a);
    	cout << a << endl;
    	return 0;
    }
    法二
    
    //LinkQueue.h
    #ifndef LINKQUEUE_H
    #define LINKQUEUE_H
    
    template <class T>
    struct Node
    {
    	T data;
    	Node<T> *next;  //此处<T>也可以省略
    };
    
    template <class T>
    class LinkQueue
    {
    public:
    	LinkQueue();          //构造函数，初始化一个空的链队列
    	~LinkQueue();      //析构函数，释放链队列中各结点的存储空间
    	void EnQueue(T x);  //将元素x入队
    	T DeQueue();       //将队头元素出队
    	T GetQueue();     //取链队列的队头元素
    	bool Empty();     //判断链队列是否为空
    private:
    	Node<T> *front, *rear;  //队头和队尾指针，分别指向头结点和终端结点
    };
    
    #endif;
    
    //LinkQueueMain.cpp
    #include<iostream>       //引用输入输出流
    using namespace std;
    #include"LinkQueue.cpp"  //引入成员函数文件
    
    void main()
    {
    	LinkQueue<int> a;         //创建模版类的实例 
    
    	if (a.Empty()){
    
    		cout << "队空,对10执行入队操作:\n";
    		try
    		{
    			a.EnQueue(10);             //入队操作
    		}
    		catch (char* wrong)
    		{
    			cout << wrong;
    		}
    		cout << "查看队头元素:" << endl;
    		cout << a.GetQueue() << endl;  //读队头元素
    
    		cout << "对15执行入队操作:" << endl;
    		try
    		{
    			a.EnQueue(15);
    		}
    		catch (char* wrong)
    		{
    			cout << wrong;
    		}
    		cout << "查看队头元素:" << endl;
    		cout << a.GetQueue() << endl;
    
    
    		cout << "执行出队操作:" << endl;  //出队操作
    		a.DeQueue();
    
    		cout << "查看队头元素:" << endl;
    		cout << a.GetQueue() << endl;
    	}
    	else{
    
    		cout << "队列不空";
    	}
    	a.~LinkQueue();
    }