成长随心记3

1，数据结构-队列
    1）特殊的顺序表，要求只能重队尾插入，队头删除
    2）例：

    a）静态存储，顺序存储的队列
    #define max 10
    typedef struct qlist {
        int data[max];
        int fornt;//队头
        int rear;//队尾
    }qlist;
    bool init(qlist& q) {//队列的初始化
        q.fornt = q.rear = 0;
        return true;
    }
    bool put(qlist& q, int e) {//队列的入队
        if (q.fornt== (q.rear + 1) % max)//如果队满，入队失败：就是队尾指向最后的空位时
            return false;
        q.data[q.rear] = e;
        q.rear = (q.rear + 1) % max;//队尾向后移一位
        return true;
    }
    bool del(qlist& q,int& e) {//队列的出队
        if (q.fornt == q.rear)//如果队空，出队失败
            return false;
        e = q.data[q.fornt];//用e返回出队的值
        q.fornt = (q.fornt + 1) % max;//队头向后移一位
    }
    bool show(qlist& q) {//队列的展示
        for (int i = q.fornt; i < q.rear; i++) {
            cout << q.data[i];
        }
        return true;
    }
    bool search(qlist& q, int& e) {//队列的查找队头
        if (q.fornt == q.rear)
            return false;
        e = q.fornt;
        return true;
    }    
    

    注意：a）最后一个空位不存储数据，如果想存储数据，需要再添加一个辅助指针记录
              b)  用(q.fornt+1)%max判断队满是为了在逻辑上实现循环
              c）如果想要知道队里有多少个元素，用(rear+max-front)%max;

    b）链式存储的队列

    typedef struct linknode {//节点
        int data;//节点的数据域
        struct linknode* next;//指向下一节点的指针
    }linknode;

    typedef struct qlist {//队列表
        struct linknode* front, *rear;//指向队头节点和队尾节点的指针
    }qlist;

    bool init(qlist& q) {//队列表的初始化
        q.front = q.rear = new linknode;//带头结点的队列
        q.front->next = NULL;//头结点指向空
        return true;
    }
    bool put(qlist& q ,int e) {//队列的入队
        linknode* s = new linknode;//定义一个新节点s
        s->data = e;//s的数据域放e
        s->next = NULL;
        q.rear->next = s;//节点的链接
        q.rear = s;//队尾向后移一位，也就是指向s
        return true;
    }
    bool show(qlist& q) {//队列的展示
        linknode* s = q.front->next;//定义一个节点s指向第一个数据域
        while (s) {//如果s为空则跳出循环
            cout <data;
            s = s->next;
        }
        return true;
    }
    bool del(qlist& q, int e) {//队列的出队
        if (q.front == q.rear)//如果空队，返回错误
            return false;
        linknode* s = q.front->next;//定义一个节点指向此次要出队的节点
        e = s->data;//用e返回
        q.front->next = s->next;//头结点指向下一个节点
        if (q.rear == s)//如果此处删除的是最后一个节点，置空
            q.rear = q.front;
        delete s;//注意释放空间s
        return true;
    }
    bool search(qlist& q, int e) {//查找队头元素
        if (q.front == q.rear)
            return false;
        e = q.front->next->data;
        return true;
    }
    int main()
    {
        qlist q;
        init(q);
        for (int i = 0; i < 10; i++) {
            put(q, i);
        }
        int e=0;
        show(q);
        //del(q,e);
        //show(q);
        //cout << e;
        search(q, e);
        cout << e;
    }

----------------------------------------------------------------------------------------------------------------------

个人心得：感觉队列和单链表差不多，只要单链表看的懂，还是挺简单的，单链表需要下功夫啊