4-11 若使用循环链表来表示队列，p是链表中的一个指针。试基于此结构给出队列的插入和删除算法，并给出p为何值时队列为空。
思路：我们可以考虑把p作为入口，每次加入的元素从p加入。而p->link就成为出口，每次出队，都读取p->link,并删去这个结点.
按照书p117的基本类声明改写
isEmpty():p==NULL;
4-12 若将一个双端队列顺序表示在一维数组V[m]中，两个端点设为end1和end2，并组织成一个循环队列。试写出双端队列所用指针end1和end2的初始化条件以及队列空和队列满的条件，并编写基于此结构的相应的插入和删除操作。
恩，双端队列，看了参考答案才明白什么叫双端队列。丫就一无赖双头栈～
思路：end1和end2为队列的两头，但不同于普通的循环队列，这两头不分first和rear，既能进，又能出，双向通道，类似于腔肠动物……
为了和参考答案保持一致，定义入队时end1向右，end2向左，简单点理解就好像某些时候数组的中间段空的。其实我更喜欢反过来。
那么很显然和循环队列一样，队空队满都是end1==end2，为了以示区别，可以定义end2永远指向第二个端口实际向前的一个位置，多出一个空位。如此我们有
队满：end1+1==end2 考虑到循环效果，end1可能会从V[0]恰好退到v[m]，而此时 end2指向v[0]，队列也是满的。所以表打成 (end1+1)%m==end2
队空:end1==end2
初始化，一定是置空队列和数组，所以有end1=end2=0 指向v[0]
同以前的题，我么假设判断队空和队满的函数以及类结构都已完成。
4-13 设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结构的队列的插入和删除算法，并给出队列空和队列满的条件。
思路：
先描述一个用链表表示的双端队列的数据结构，两端用指针first和last表示，其中first端允许删除。为使链表的操作简化一致，同样使first作为头结点，first->link指向第一个结点。初始化条件first=last;first->link=last->link=NULL;
队满？不是链表么？还考虑队满啊 哎 太麻烦 无视之
感觉参考答案有问题，首先它把这个链设计成了一个循环链，然后end1->link=end1,那么如果一直只是从空表的end2端插入，end2->link指向end1，但是这样的链却没法删除，因为end1->link依然=end1.没有元素，事实上已经从end2端插入了很多元素.并且是从NULL开始的，不知道这样的表有没有意义
队空条件 first==last
思路：我们可以考虑把p作为入口，每次加入的元素从p加入。而p->link就成为出口，每次出队，都读取p->link,并删去这个结点.
按照书p117的基本类声明改写
isEmpty():p==NULL;
template< class Type >void Queue< Type >::EnQueue(const Type& item){
//将新元素item插入到队列的入口.
QueueNode *out;
if(isEmpty()) //如果队空，则p作为第一个结点并且链向自身
p->link=p=new QueueNode(item,NULL);
else
{out=p->link; //保存出口指针
p->link=new QueueNode(item,NULL); //新元素到入口
p=p->link;p->link=out; //修改入口指针，并指向出口
}
}
template< class Type >Type Queue< Type >::DeQueue(){
//从出口取出元素，并返回该元素值.
assert(!IsEmpty());
QueueNode *out=p->link; //从出口取出元素
Type retvalue = out->data; //元素值
p->link=out->link; //修改出口指针
delete out;
return retvalue;
} 4-12 若将一个双端队列顺序表示在一维数组V[m]中，两个端点设为end1和end2，并组织成一个循环队列。试写出双端队列所用指针end1和end2的初始化条件以及队列空和队列满的条件，并编写基于此结构的相应的插入和删除操作。
恩，双端队列，看了参考答案才明白什么叫双端队列。丫就一无赖双头栈～
思路：end1和end2为队列的两头，但不同于普通的循环队列，这两头不分first和rear，既能进，又能出，双向通道，类似于腔肠动物……
为了和参考答案保持一致，定义入队时end1向右，end2向左，简单点理解就好像某些时候数组的中间段空的。其实我更喜欢反过来。
那么很显然和循环队列一样，队空队满都是end1==end2，为了以示区别，可以定义end2永远指向第二个端口实际向前的一个位置，多出一个空位。如此我们有
队满：end1+1==end2 考虑到循环效果，end1可能会从V[0]恰好退到v[m]，而此时 end2指向v[0]，队列也是满的。所以表打成 (end1+1)%m==end2
队空:end1==end2
初始化，一定是置空队列和数组，所以有end1=end2=0 指向v[0]
同以前的题，我么假设判断队空和队满的函数以及类结构都已完成。
template< class Type >void DblQueue< Type >::EnQueue(Type& item,const int end){
//元素进队，end为1或者2，表示进队的方向.
assert(!IsFull());
if (end == 1){
end1 = (end1+1)%m;
V[end1]=item;
}
else{ //end1和end2的操作有区别，原因在于end2实际指向空
V[end2]=item;
end2=(end2-1+m)%m;
//莫非模不能做负数？前面我好像有地方取负数的模了
}
}
template< class Type >Type DblQueue< Type >::DeQueue(const int end){
//元素出队，end为1或者2，表示出队的方向.
assert(!IsEmpty());
Type temp;
if(end==1){
temp=V[end1];
end1=(end1+m-1)%m;
}
else{
end2=(end2+1)%m;
temp=V[end2]; //从这里可以看出end2指向的位置
}
return temp;
}
4-13 设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结构的队列的插入和删除算法，并给出队列空和队列满的条件。
思路：
先描述一个用链表表示的双端队列的数据结构，两端用指针first和last表示，其中first端允许删除。为使链表的操作简化一致，同样使first作为头结点，first->link指向第一个结点。初始化条件first=last;first->link=last->link=NULL;
队满？不是链表么？还考虑队满啊 哎 太麻烦 无视之
感觉参考答案有问题，首先它把这个链设计成了一个循环链，然后end1->link=end1,那么如果一直只是从空表的end2端插入，end2->link指向end1，但是这样的链却没法删除，因为end1->link依然=end1.没有元素，事实上已经从end2端插入了很多元素.并且是从NULL开始的，不知道这样的表有没有意义
enum Direct{firstin,lastin}
EnQueue(const &item,Direct a){
//插入函数，a作为插入的方向，可选firstin或者lastin
QueueNode *p,*newnode;
newnode =new QueueNode(item,NULL); //新加入结点
p= a==firsin?first:last; //p作为指针
newnode->link=p->link; //仿照书p75页，统一各种情况
if(p->link == NULL)last=newnode;
p->link=newnode;
}
DeQueue(){
assert(first!=last); //确定队不空
QueueNode *q=first->link;
Type value=q->data; //懒得写模板了……用Type代替
first->link=q->link;
delete q;
if(first->link == NULL)last=first; //如果删最后一个元素
return value;
}
队空条件 first==last
Comments (0)