| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 686 人关注过本帖
标题:新人求助~~请各位大神一定要帮忙~【双端队列】
只看楼主 加入收藏
Sundays
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2013-1-13
结帖率:0
收藏
已结贴  问题点数:20 回复次数:6 
新人求助~~请各位大神一定要帮忙~【双端队列】
数据结构的课程设计题目。
平时没怎么好好学疏解。现在蛋疼了。。
真心求解各位大神~~
双端队列
一、问题描述
双端队列是插入和删除操作可以在两端进行的线性表,表的两端分别作端点1和端点2。设计双端队列的数据结构,实现入队、出队等基本操作。
二、基本要求
1. 定义双端队列的抽象数据类型;
2. 设计存储结构存储双端队列;
3. 设计双端队列的插入和删除算法;
4. 分析算法的时间性能。
三、设计思想
    为便于双端队列的插入和删除操作,采用双链表存储双端队列,为使空表和非被代表的处理一致,双链表带头结点。在双链表中设指针end1指向头结点,指针end2指向终端结点。其顺序示意图如下:
 
入队操作的算法用伪代码描述如下:
1.    判断是插在端点1还是端点2:
1.1    若是在端点1插入,则将新结点插在头结点之后;
1.2    若是在端点2插入,则将新结点插在终端点之后;
出队操作的算法用伪代码描述如下:
1.    判断是在端点1还是端点2:
1.1    若是在端点1删除,则将开始结点删除;
1.2    若是在端点2删除,则将终端结点删除;
四、思考题
1. 设计并实现输出受限的双端队列,即一个端点允许插入和删除操作,另一端点只允许插入操作。
2. 设计并实现输入受限的双端队列,即一个端点允许插入和删除操作,另一端点只允许删除操作。
搜索更多相关主题的帖子: 线性表 设计 
2013-01-13 03:13
yaobao
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:蒙面侠
威 望:4
帖 子:1854
专家分:4121
注 册:2012-10-25
收藏
得分:5 
鉴定完毕,作业贴

认认真真的学习,踏踏实实的走路:戒骄戒躁!!!
2013-01-13 08:26
Sundays
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2013-1-13
收藏
得分:0 
回复 2楼 yaobao
大哥,你就帮一下吧,比较基本的,对你们应该是小case,我就蛋疼了。。马上要结课了。。过不了直接重修,连补考也没得机会。。希望大哥帮个忙啊,万分感谢~~
2013-01-13 10:34
不玩虚的
Rank: 9Rank: 9Rank: 9
来 自:四川
等 级:贵宾
威 望:10
帖 子:331
专家分:1301
注 册:2012-12-9
收藏
得分:5 
表示我要考试啊,要回家了,没有时间写了,本来17回家的,坑爹的票居然买的是15号的,考完试就得走人

同学习......同进步....你帮我......我帮你.....上善若水.....
2013-01-13 18:57
yaobao
Rank: 13Rank: 13Rank: 13Rank: 13
等 级:蒙面侠
威 望:4
帖 子:1854
专家分:4121
注 册:2012-10-25
收藏
得分:0 
楼上的很幸福啊,有的学校25号放假,会愁死人的

认认真真的学习,踏踏实实的走路:戒骄戒躁!!!
2013-01-13 23:16
peach5460
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:武汉
等 级:贵宾
威 望:30
帖 子:2780
专家分:6060
注 册:2008-1-28
收藏
得分:5 
自己做作业嘛,为虾米要求人哩?

我总觉得授人以鱼不如授人以渔...
可是总有些SB叫嚣着:要么给代码给答案,要么滚蛋...
虽然我知道不要跟SB一般见识,但是我真的没修炼到宠辱不惊...
2013-01-15 08:16
hahayezhe
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖南张家界
等 级:贵宾
威 望:24
帖 子:1386
专家分:6999
注 册:2010-3-8
收藏
得分:5 
程序代码:
#ifndef _DoubleQueue_H_
#define _DoubleQueue_H_
#include <iostream>
using namespace std;

template<class T> class CDoubleQueue;
template<class T>
class CNode
{
    friend class CDoubleQueue<T>;
public:
    CNode():m_front(NULL),m_after(NULL),m_type(0){};
    CNode(const CNode<T> &t):m_front(t.m_front),m_after(t.m_after),m_type(t.m_type){}
    CNode<T>& operator =(const CNode<T> &t)
    {
        if(this == &t)
            return *this;
        m_front = t.m_front;
        m_after = t.m_after;
        m_type = t.m_type;
        return *this;
    }

    friend ostream & operator<<(ostream &out,const CNode<T> &t)
    {
        out<<t.m_type;
        return out;
    }

    CNode<T> *GetAfter(){return m_after;}
    CNode<T> *GetFront(){return m_front;}
private:
    CNode<T>* m_front;
    CNode<T>* m_after;
    T m_type;
};

template<class T>
class CDoubleQueue
{
public:
    CDoubleQueue():m_end1(NULL),m_end2(NULL),m_Num(0){}
    ~CDoubleQueue()
    {
        DeleteAll(m_end1);
    }
    bool CreateHead(const T &t)
    {
        if(m_end1 != NULL)
            return false;
        CNode<T> *Phead = new CNode<T>();
        Phead->m_type = t;

        m_end1 = Phead;
        m_end2 = Phead;

        m_Num ++;
        return true;
    }
    bool InsertHead(const T &t)
    {
        if(m_end1 == NULL)
            return CreateHead(t);

        CNode<T> *Ph= new CNode<T>();
        Ph->m_type = t;

        Ph->m_after = m_end1;
        m_end1->m_front = Ph;
        m_end1 = Ph;

        m_Num ++;
        return true;
    }
    bool InsertEnd(const T &t)
    {
        if(m_end2 == NULL)
            return CreateHead(t);

        CNode<T> *PE= new CNode<T>();
        PE->m_type = t;

        PE->m_front = m_end2;
        m_end2->m_after = PE;
        m_end2 = PE;

        m_Num ++;
        return true;
    }

    bool DeleteHead()
    {
        if(m_end1 == NULL)
            return false;

        if(m_end1 == m_end2)
        {
            delete m_end1;
            m_end1 = NULL;
            m_end2 = NULL;
        }
        else
        {
            CNode *PH = m_end1->m_after;
            delete m_end1;
            m_end1 = PH;
        }

        m_Num --;
        return true;
    }
    bool DeleteEnd()
    {
        if(m_end2 == NULL)
            return false;

        if(m_end1 == m_end2)
        {
            delete m_end2;
            m_end1 = NULL;
            m_end2 = NULL;
        }
        else
        {
            CNode *PE = m_end2->m_front;
            delete m_end2;
            m_end2 = PE;
        }

        m_Num --;
        return true;
    }

    CNode<T> * GetHead(){return m_end1;}
    CNode<T> * GetEnd(){return m_end2;}
private:
    CDoubleQueue<T>(const CDoubleQueue<T> &t);
    CDoubleQueue<T> & operator=(const CDoubleQueue<T> &t);

    CNode<T> *m_end1;
    CNode<T> *m_end2;
    __int32 m_Num;//用此变量限制

    void DeleteAll(CNode<T> *P)
    {
        if(P != NULL)
        {
            DeleteAll(P->m_after);
            delete P;
        }
    }
};
#endif
测试用例
程序代码:
#include "DoubleQueue.h"
int _tmain(int argc, _TCHAR* argv[])
{
    CDoubleQueue<int> m_test;
    for(int i=0;i<100;i++)
    {
        if(i%2 == 0)
            m_test.InsertEnd(i);
        else
            m_test.InsertHead(i);
    }

    CNode<int> *m_head = m_test.GetHead();

    while(m_head != NULL)
    {
        cout<<*m_head<<endl;
        m_head = m_head->GetAfter();
    }
    return 0;
}

2013-01-15 10:42
快速回复:新人求助~~请各位大神一定要帮忙~【双端队列】
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017709 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved