首页 > 试题广场 >

根据要求写出pqueue的工作原理

[问答题]
有pqueue.h如下 
#ifndef HEADER_PQUEUE_H
#define HEADER_PQUEUE_H
typedef struct_pqueue{
    pitem *items;
     int count;
}pqueue_s;
typedef struct_pqueue *pqueue;
typedef struct_pitem{
    unsigned char priority[8];
    void *data;
    struct_pitem *next;
}pitem;
typedef struct_pitem *piterator;
pitem *pitem_new(unsigned char *prio64be,void *data);
void pitem_free(pitem *item);
 
pqueue pqueue_new(void);
void pqueue_free(pqueue pq);
pitem *pqueue_insert(pqueue pq,pitem *item);
pitem *pqueue_peek(pqueue pq);
pitem *pqueue_pop(pqueue pq);
pitem *pqueue_find(pqueue pq,unsigned char *prio64be);
pitem *pqueue_iterator(pqueue pq);
pitem *pqueue_next(piterator *iter);
int pqueue_size(pqueue pq);
#endif /*! HEADER_PQUEUE_H */
pq_test.c如下： 
#include<stdlib.h>
#include<string.h>
#include"pqueue.h"
/*remember to change expected.txt if you change there values*/
unsigned char prio1[8]="supercal";
unsigned char prio2[8]="ifragili";
unsigned char prio3[8]="sticexpi";
static void
pqueue_print(pqueue pq)
{
     pitem *iter,*item;
     iter=pqueue_iterator(pq);
     for(item=pqueue_next(&iter);item!=NULL;
         item=pqueue_next(&iter)){
         printf("item\t%02x%02x%02x%02x%02x%02x%02x%02x\n",
             item ->priority[0],item->priority[1],
             item ->priority[2],item->priority[3],
             item ->priority[4],item->priority[5],
             item ->priority[6],item->priority[7],
         }
}
int main(void)
{
     pitem *item;
     pqueue pq;
     pq=pqueue_new();
     item=pitem_new(prio3,NULL);
     pqueue_insert(pq,item);
 
     item=pitem_new(prio1,NULL);
     pqueue_insert(pq,item);
 
     item=pitem_new(prio2,NULL);
     pqueue_insert(pq,item);
     item=pqueue_find(pq,prio1);
     fprintf(stderr,"found %p\n",item->priority);
     item=pqueue_find(pq,prio2);
     fprintf(stderr,"found %p\n",item->priority);
 
     item=pqueue_find(pq,prio3);
     fprintf(stderr,"found %p\n",item->priority);
     
     pqueue_print(pq);
     for(item=pqueue_pop(pq);item!=NULL;item=pqueue_pop(pq))
     pitem_free(item);
 
     pqueue_free(pq);
     return 0;
}
pq_test.sh如下： 
#!/bin/sh
set -e
./pq_test | cmp $srcdir/pq_expected.txt-
pq_expected.txt如下：
item 6966726167696c69
item 7374696365787069
item 737570657263616c
1.根据测试代码描述pqueue的工作原理。
2.请实现 pitem *pqueue_insert(pqueue pq,pitem *item);
添加回答
推荐
kuring头像 kuring
测试文件的内容输出的是struct_pitem结构中的priority字段的16进制形式，将其转换为字符串正好是通过pqueue_insert函数放入到pqueue结构中的prio3、prio1、prio2的值。通过观察测试文件中每一行的值可以发现对应的字符串序列为prio3、prio2、prio1，跟插入字符串的顺序并不一致，说明pqueue既不是先进先出（队列），也不是后进先出（栈）。

另外，通过观察测试文件可以发现测试文件中的字符串是按照从小到大排列的，而且struct_pitem中的priority字段含义可以理解，这是一个优先级队列，priority字段代表队列的优先级，priority字段越小，优先级越高。

理解了队列的结构后，就可以写出插入的代码了。

pitem *pqueue_insert(pqueue pq, pitem *item)
{
    if (!item)
    {
        return NULL;
    }
    
    if (pq->count == 0)
    {
        pq->items = item;
        count++;
        return pq->items;
    }
    
    // 查找要插入的位置
    pitem *iter, *item2, *item_before = NULL;
    iter = pqueue_iterator(pq);
    for(item2=pqueue_next(&iter); item2!=NULL; item2=pqueue_next(&iter))
    {
        int result = 0;
        for (int i=0; i<8; i++)
        {
            if (item[i] < item2[i])
            {
                result = -1;
            }
            else if (item[i] < item2[i])
            {
                result = 1;
            }
        }
        
        if (result == -1)
        {
            break;
        }
        item_before = item2;
    }
    
    if (!item_before)
    {
        // item需要插入到队列中的第一个位置
        item_before = pq->items;
        pq->items = item;
        item->next = item_before;
    }
    else
    {
        pitem *tmp = item_before->next;
        item_before->next = item;
        item->next = tmp;
    }
    pq->count++;
    return item;
}

编辑于 2015-01-30 11:29:30 回复(4)
追梦_吹吹风头像 追梦_吹吹风
pqueue是一个带有一个pitem哑结点的优先级队列
pitem *pqueue_insert(pqueue pq,pitem *item)
{
if(item==NULL)
        return NULL;
pitem *itbefore,*itcurr,*iter;
 iter=pqueue_iterator(pq);//由pqueue_print(pqueue pq)函数可知，此时的itbefore为pq中默认的一个哑结点
itbefore=iter;
  for(itcurr=pqueue_next(&iter);itcurr!=NULL;itcurr=pqueue_next(&iter))
 {
      if(strcmp(item->priority,itcurr->priority)<=0) 
      {
      break;
      } 
      itbefore=itcurr;
 }
 item->next=itbefore->next;
 itbefore->next=item;
 pq->count++;
 return item;
}
编辑于 2015-09-05 14:10:56 回复(4)
岩流佐佐木小次郎头像 岩流佐佐木小次郎
队列 先入先出  比自己字符小的放前面比自己字符大的放后面
pitem *pqueue_insert(pqueue pq,pitem *item);
{
    if(pq==NULL||item==NULL)
    {
        return NULL;
    }
   if( pq->items->priority[0]>=item->priority[0])
    {
        item->next = pq->items->next;
        pq->items->next = item;
    }
    else
    {
        item->next =  pq->items;
        pq->items = item;
    }
return item;
}

发表于 2018-03-28 16:13:12 回复(0)
DennisRitchie头像 DennisRitchie
<div> pqueue是一个queue的变体，pqueue存储有指向队列头结点的指针，以及队列中节点的个数，pqueue中节点是pitem，pitem中有三个变量，第一个变量是描述当前节点的优先级的，第二个变量存储的是节点的值，第三个变量是指向下一个节点的指针。测试程序中先初始化生成了一个pqueue然后再向其中插入了两个pitem节点，查入之后调用了查找函数，找出预先定义的优先级的节点在队中中是否存在，prio1和prio2都有，prio3没有找到。<span>pqueue_print 是一个遍历函数通过内部迭代器</span><span>iterator来遍历队列中的成员。</span> </div> <div> <span>这个pqueue是一个按照优先级来排列节点的结构，测试程序中，prio2&gt;prio3&gt;prio1,存入节点时，按照优先级顺序，将优先级高的存在前面，，优先级相同</span> </div> <div> <span>的按照存入的先后来存。</span> </div> <div> <span><br /> </span> </div> <div> <span><br /> </span> </div>
发表于 2015-09-01 09:46:58 回复(0)
登疯作极头像 登疯作极
<div> 1.pqueue利用链表完成先入先出的缓存方式。插入操作将当前pitem中的next指针设置为当前pqueue中items，弹出操作抛出链表的最后一个。 </div> <div> 2.pitem *pqueue_insert(pqueue pq,pitem *item) </div> <div> ｛ </div> <div> &nbsp; &nbsp; if(!item) return NULL;<br /> </div> <div> &nbsp; &nbsp; if(pq.items != NULL)<br /> </div> <div> &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; item-&gt;next=pq.items;<br /> </div> <div> &nbsp; &nbsp; pq.items=item;<br /> </div> <div> &nbsp; &nbsp; return item;<br /> </div> <div> ｝ </div>
发表于 2015-08-25 15:23:59 回复(0)
提交观点

问题信息

网易 算法工程师 队列 网易游戏 C++ 游戏研发工程师 2015 腾讯
来自：腾讯2015春招pc客...
上传者：小牧魔法袋
难度：
5条回答 10488浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号