优先队列，数组赋不了值 - 数据结构与算法

楼主

已结贴√ 问题点数：20 回复次数：10

优先队列，数组赋不了值

程序代码：

/*
*优先队列：大根堆
*/
#include<stdio.h>
#include<stdlib.h>

#define MAX_PQ_SIZE 100
#define element_type unsigned int
#define INI_MAX 0


typedef struct heap_struct
{   
    element_type max_heap_size;//堆中最大元素的个数
    element_type size;//存放在堆中的实际元素的个数
    element_type *elements;   
}*PRIORITY_QUEUE;

PRIORITY_QUEUE create_pq(unsigned int max_elements)
{
    PRIORITY_QUEUE H;

    if(max_elements>MAX_PQ_SIZE)
        printf("Priority queue size is too large!\n");

    H=(PRIORITY_QUEUE)malloc(sizeof(struct heap_struct));

    if(NULL==H)
        printf("Out of space!\n");

    /*Allocate the array+one extra for sentinel*/
    H->elements=(element_type *)malloc((max_elements+1)*sizeof(element_type));

    if(NULL==H->elements)
        printf("Out of space!\n");

    H->max_heap_size=max_elements;
    H->size=0;
    H->elements[0]=INI_MAX;//哨兵元素
    return H;
}
bool isEmptyPriorityQueue(PRIORITY_QUEUE H)
{
    return H->size==0;
}
/*H->element[0] is a sentinel*/
void insert(PRIORITY_QUEUE H,element_type x)
{
    unsigned int i;

    if(H->size==H->max_heap_size)
        printf("Prinority queue if full!\n");
    else
    {
        i=++H->size;    /*the position of the new element*/

        while(H->elements[i/2]<x)/*compare with the value of parent node*/
        {
            H->elements[i]=H->elements[i/2];/*swap down*/
            i/=2;/*one level up*/
        }
        H->elements[i]=x;/*the finial position*/
    }
}
element_type delete_max(PRIORITY_QUEUE H)
{
    unsigned int i,child;
    element_type max_element,last_element;

    if(0==H->size)
    {
        printf("Priority queue is empty!\n");
        return H->elements[0];
    }

    max_element=H->elements[1];/*first node is the*/
    last_element=H->elements[H->size--];/*delete one node*/

    for(i=1;i*2<=H->size;i=child)
    {
        /*find bigger child*/
        child=i*2;
        if((child!=H->size)&&(H->elements[child+1]>H->elements[child]))
            child++;

        if(last_element<H->elements[child])/*not yet the biggest*/
            H->elements[i]=H->elements[child];/*child move up*/
        else
            break;/*is the biggest*/
    }
    H->elements[i]=last_element;/*set here*/
    return max_element;
}
element_type topPriorityQueue(PRIORITY_QUEUE H)
{
    if(isEmptyPriorityQueue(H))
    {
        printf("Priority queue is empty!\n");
        return H->elements[0];
    }
    else
        return H->elements[1];
       
}
void printPriorityQueue(PRIORITY_QUEUE H)
{
    unsigned int i;
    while(!isEmptyPriorityQueue(H))
    {
        for( i=0;i<H->size;i++)
            printf("%d",H->elements[i]);           
    }

}   
int main()
{
    PRIORITY_QUEUE pq=NULL;
    unsigned int max_elements;


    printf("please input the number of max_elements:\n");
    scanf("%d",&max_elements);   
    create_pq(max_elements);
    while(max_elements)
    {
        pq->elements[max_elements]=max_elements--;
        insert(pq,pq->elements[max_elements]);
    }

    printf("Priority queue  initializtion finish!");
    printPriorityQueue(pq);
    printf("\n\n");

    return 0;
}

搜索更多相关主题的帖子: 100　

第 2 楼

得分:0

pq=create_pq(max_elements);

第 3 楼

得分:0

插入有问题，求解答

第 4 楼

得分:0

实现什么功能啊？？

第 5 楼

得分:20

程序的问题还是挺多的
    create_pq(max_elements);  调用不正确   这里是有返回值调用如果没有保存返回值  那么你调用这个函数其实什么事情都没有做对于main这个函数来讲

        while(H->elements[i/2]<x)/*compare with the value of parent node*/
        {
            H->elements[i]=H->elements[i/2];/*swap down*/
            i/=2;/*one level up*/
        }人为地构成了一个死循环  当第一次进行插入的时候堆顶是默认值最后加进来的是x 但是在堆的调整当中 i的最终值是0 根据你插入的数据值的情况是x=元素的输入个数
    所以x>0恒成立  while则出不来

    while(!isEmptyPriorityQueue(H))人为地构成了一个死循环
    {
        for( i=0;i<H->size;i++)
            printf("%d",H->elements[i]);
    }

第 6 楼

得分:0

以下是引用寒风中的细雨在2011-7-31 08:31:37的发言：

程序的问题还是挺多的
    create_pq(max_elements);  调用不正确   这里是有返回值调用如果没有保存返回值  那么你调用这个函数其实什么事情都没有做对于main这个函数来讲

        while(H->elementssize;i++)
            printf("%d",H->elements);
    }

那应该怎么解决这些死循环

第 7 楼

得分:0

回复 6楼世界模型

这些就是你程序本身设计的问题

第 8 楼

得分:0

以下是引用寒风中的细雨在2011-7-31 14:19:08的发言：

这些就是你程序本身设计的问题

没有思路了

第 9 楼

得分:0

程序代码：

printf("print priority queue is as follows:");
    printPriorityQueue(pq);    

    printf("\n\n");
    printf("delete the biggest value:");
    delete_max(pq);
    printPriorityQueue(pq);

    printf("\n\n");
    printf("delete the bigger value:");
    delete_max(pq);
    printPriorityQueue(pq);
    printf("\n\n");

    printf("delete the value which data is 7:");
    insert(pq, 7);
    printPriorityQueue(pq);
    printf("\n\n");
    return 0;

It's done!!!

第 10 楼

得分:0

程序代码：

/*
*优先队列：大根堆
*/
#include<stdio.h>
#include<stdlib.h>

#define MAX_PQ_SIZE 100
/* 用typedef应该好些吧 */
typedef unsigned int element_type; 

#define INI_MAX 1000


typedef struct heap_struct
{   
    element_type max_heap_size;//堆中最大元素的个数
    element_type size;//存放在堆中的实际元素的个数
    element_type *elements;   
}*PRIORITY_QUEUE;

PRIORITY_QUEUE create_pq(unsigned int max_elements)
{
    PRIORITY_QUEUE H;

    if(max_elements>MAX_PQ_SIZE)
    {
        printf("Priority queue size is too large!\n");
        return NULL;
    }

    H=(PRIORITY_QUEUE)malloc(sizeof(struct heap_struct));

    if(NULL==H)
    {
        printf("Out of space!\n");
        return NULL;
    }

    /*Allocate the array+one extra for sentinel*/
    H->elements=(element_type *)malloc((max_elements+1)*sizeof(element_type));

    if(NULL==H->elements)
    {
        printf("Out of space!\n");
        free(H);
        return NULL;
    }

    H->max_heap_size=max_elements;
    H->size=0;
    H->elements[0]=INI_MAX;//哨兵元素
    return H;
}
bool isEmptyPriorityQueue(PRIORITY_QUEUE H)
{
    return H->size==0;
}
/*H->element[0] is a sentinel*/
void insert(PRIORITY_QUEUE H,element_type x)
{
    unsigned int i;

    if(H->size==H->max_heap_size)
        printf("Prinority queue is full!\n");
    else
    {
        i=++H->size;    /*the position of the new element*/

        while(H->elements[i/2]<x)/*compare with the value of parent node*/
        {
            H->elements[i]=H->elements[i/2];/*swap down*/
            i=i/2;/*one level up*/
        }
        H->elements[i]=x;/*the finial position*/
    }
}
element_type delete_max(PRIORITY_QUEUE H)
{
    unsigned int i,child;
    element_type max_element,last_element;

    if(0==H->size)
    {
        printf("Priority queue is empty!\n");
        return H->elements[0];
    }

    max_element=H->elements[1];/*first node is the*/
    last_element=H->elements[H->size--];/*delete one node*/

    for(i=1;i*2<=H->size;i=child)
    {
        /*find bigger child*/
        child=i*2;
        if((child!=H->size)&&(H->elements[child+1]>H->elements[child]))
            child++;

        if(last_element<H->elements[child])/*not yet the biggest*/
            H->elements[i]=H->elements[child];/*child move up*/
        else
            break;/*is the biggest*/
    }
    H->elements[i]=last_element;/*set here*/
    return max_element;
}
element_type topPriorityQueue(PRIORITY_QUEUE H)
{
    if(isEmptyPriorityQueue(H))
    {
        printf("Priority queue is empty!\n");
        return H->elements[0];
    }
    else
        return H->elements[1];
       
}
void printPriorityQueue(PRIORITY_QUEUE H)
{
    unsigned int i;
    /* 用if判断就行，不必用while吧 */
    if (!isEmptyPriorityQueue(H))

    {
        /* 应该从1开始吧，0是哨兵 */
        for( i = 1; i <= H->size; i++)
            printf("%d ",H->elements[i]);           
    }

}   
int main()
{
    PRIORITY_QUEUE pq=NULL;
    unsigned int max_elements;


    printf("please input the number of max_elements:\n");
    scanf("%d",&max_elements);   
    pq=create_pq(max_elements);
    while(max_elements)
    {
        /* 怎么能自己操作数据呢？应该调用接口操作，否则你写的接口还有什么用？ */
        /* pq->elements[max_elements]=max_elements--; */
        insert(pq,max_elements--);
    }
    printf("Priority queue initializtion finish!\n");
    printf("\n\n");

    printf("print priority queue is as follows:");
    printPriorityQueue(pq);    

    printf("\n\n");
    printf("delete the biggest value:");
    delete_max(pq);
    printPriorityQueue(pq);

    printf("\n\n");
    printf("delete the bigger value:");
    delete_max(pq);
    printPriorityQueue(pq);
    printf("\n\n");

    printf("delete the value which data is 7:");
    insert(pq, 7);
    printPriorityQueue(pq);
    printf("\n\n");
    return 0;
}