当前位置:首页 > 高性能开发 > 数据结构与算法

数据结构与算法——链行列

优良自学吧提供数据结构与算法——链行列,数据结构与算法——链队列总结链队列 什么是链队?   队列的链式存储结构称为链队列。链队也有两个指针,队头指针和队尾指针,这样队头删除和队尾插入操作就会很方便,链式队列一般像单链表一样,有一个头结点。 图示: 具体实现: <span sty

数据结构与算法——链队列

总结链队列

什么是链队?

  队列的链式存储结构称为链队列。链队也有两个指针,队头指针和队尾指针,这样队头删除和队尾插入操作就会很方便,链式队列一般像单链表一样,有一个头结点。

图示:

数据结构与算法——链行列


具体实现:

<span style="font-family:Courier New;font-size:14px;">#include <iostream>

using namespace std;
template <class T>
struct Node {
    T data;
    struct Node<T> *next;
};

template<class T>
class LinkQueue {
private:
    Node<T> *front;  //队头指针
    Node<T> *rear;   //队尾指针
public:
    LinkQueue() {
        front = rear = new Node<T>;  //建立头结点 使其队头指针、队尾指针均指向该头结点
        front->next = NULL;
    }
    ~LinkQueue();
    void EnQueue(T x);   //入队
    T DeQueue();         //出队
    T GetFront();        //得到队头元素
    bool IsEmpty() {    //判断队列是否为空
        return front==rear?true:false;
    }
    void Print();       //遍历队列
};

template <class T>
void LinkQueue<T>::EnQueue(T x) {
    rear->next = new Node<T>;
    rear = rear->next;
    rear->data = x;
    rear->next = NULL;
}

template<class T>
void LinkQueue<T>::Print() {
    if(IsEmpty()) throw "空队列异常";
    Node<T> *s = front->next;  //工作指针 指向第一个结点
    while(s) {
        cout<<s->data<<" ";
        s= s->next;
    }
    cout<<endl;
}

/**
    析构函数 释放节点空间
    此处实现的方式是 从头结点开始挨个释放
    先将要释放结点的下一个节点地址赋值给一个指针,
    因为是有尾指针,所有直接可用尾指针,否则应该有一个临时工作指针
    然后释放该结点,再使头指针指向释放掉的结点的后继结点,循环执行。
*/
template <class T>
LinkQueue<T>::~LinkQueue() {
    while(front) {
        rear = front->next;
        delete front;
        front =rear;
    }
}

template <class T>
T LinkQueue<T>::DeQueue() {
    Node<T> *s = front->next;  //保存队头元素指针
    if(!s) throw "下溢异常";
    front->next = s->next;    //将队头出栈
    T x = s->data;           //保存队头元素
    delete s;
    if(!(front->next))  //若出队后 队列为空,则修改队尾指针 指向头结点
       rear = front;
    return x;
}

template <class T>
T LinkQueue<T>::GetFront() {
    if(IsEmpty()) throw "队空异常";
    return front->next->data;
}

int main()
{
    LinkQueue<int>linkQueue;
    for(int i=0;i<5;i++) {
        linkQueue.EnQueue(i);
    }
    linkQueue.Print();
    linkQueue.EnQueue(8);
    linkQueue.Print();
    cout<<"出栈"<<endl;
    cout<<linkQueue.DeQueue()<<"出栈"<<endl;
    linkQueue.Print();
    cout<<"对头元素为:"<<linkQueue.GetFront()<<endl;
    return 0;
}
</span>



(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢