6-19 数据结构考题 - 链队列-Toy模板网

这篇具有很好参考价值的文章主要介绍了6-19 数据结构考题 - 链队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

用链队列作存储结构，实现队列（元素为整型）的基本运算。

链队列的类型定义：

typedef int ElemType;
typedef struct QNode
{
ElemType data;
struct QNode *next;
}QNode;
typedef struct
{
QNode *front;
QNode *rear;
}LinkQueue;

下面给出了 链队列操作 函数的大部分内容，但缺少了一部分（以下划线____标识出来的部分）。

请先将以下代码中画横线的部分补充完整，然后将完整的函数GetHead,EnQueue,DeQueue 提交系统，完成题目要求的功能。

函数接口定义：

bool GetHead (LinkQueue Q, ElemType &e)
{ if ( ____ )
{ cout<<"NULL"<<endl; return false; }
e= ____ ;
return true;
}

void EnQueue(LinkQueue &Q, ElemType e)
{ QNode *p;
p=new QNode;
p->data=e;
p->next=NULL;
Q.rear->next= ____ ;
Q.rear= ____ ;
}

bool DeQueue(LinkQueue &Q, ElemType &e)
{ QNode *p;
if ( ____ )
{ cout<<"NULL"<<endl; return false; }
p= ____ ;
e=p->data;
Q.front->next= ____ ;
if(Q.rear==p) Q.rear=Q.front;
delete p;
return true;
}

文章来源地址https://www.toymoban.com/news/detail-860548.html

该函数中的参数说明：

LinkQueue &Q ：链队列 Q
ElemType e ：用于存放入队或出队的数据元素 e

测试主程序样例：

int main()
{
LinkQueue Q;
ElemType x,e;
InitQNode(Q);
cin>>x;
while(x!=-1)
{
EnQueue(Q,x);
cin>>x;
}
cout<<"Head:";
if(GetHead(Q,e))
cout<<e<<endl;
cout<<"Pop:";
while(DeQueue(Q,e))
cout<<e<<' ';
return 0;
}

输入格式:

在一行输入若干个队列元素值，调用入队函数把输入的元素值入队，用−1表示输入结束（−1不属于队列）。

输出格式:

输出分两行：

第一行输出队头元素。如队列为空，输出NULL。

第二行依次输出出队元素，直到队列为空。元素间以空格分隔，队列为空时输出NULL。

输入样例:

1 3 5 7 9 -1

输出样例:

Head:1
Pop:1 3 5 7 9 NULL

bool  GetHead (LinkQueue  Q,  ElemType  &e)
{    
    if (Q.front == Q.rear) // 队列为空
    {  
        cout << "NULL" << endl;  
        return  false; 
    }
    e = Q.front->next->data; // 获取队头元素
    return  true;
}

void  EnQueue(LinkQueue  &Q, ElemType  e)
{   
    QNode *p;
    p = new  QNode;
    p->data = e;   
    p->next = NULL;
    Q.rear->next = p; // 将新节点插入到队尾
    Q.rear = p; // 更新队尾指针
}

bool  DeQueue(LinkQueue &Q,  ElemType &e)
{    
    QNode *p;
    if (Q.front == Q.rear) // 队列为空
    {  
        cout << "NULL" << endl;  
        return  false; 
    }
    p = Q.front->next; // 获取队头节点
    e = p->data; // 获取队头元素
    Q.front->next = p->next; // 将队头节点出队
    if (Q.rear == p) // 如果队列只有一个节点，更新队尾指针
        Q.rear = Q.front;
    delete p; // 释放队头节点的内存
    return  true;
}

到了这里，关于6-19 数据结构考题 - 链队列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！