#include"stdio.h"
#include <stdlib.h>
#include"string.h"
typedef struct dui
{
    int size;
    int maxsize;
    int *elem;
}dui;

dui *creat(int maxsize)
{
    dui *p;
    p=(dui*)malloc(sizeof(dui));
    if(p==NULL)
    {
        printf("分配内存出错");
        return NULL;
    }
    else
    {
        if(p==NULL)
        {
        printf("分配内存出错");
        return NULL;
        }
        else
        {
            p->elem=(int*)malloc((maxsize+1)*sizeof(int));
            p->maxsize=maxsize;
            p->size=0;
            p->elem[0]=0;
        }
        return p;
    }
}
int ax(int a,int b)  /*比较数的大小*/
{
    if(a>b)
        return a;
    else
        return b;
}



void insert(dui *p,int x)
{
    int b=(p->size+1)/2;
    int a,c;
    a=p->size+1;
    if(p->size>p->maxsize)
        printf("堆已经满了");
    else
    {
        while(p->elem[b]>x)
        {
            p->elem[a]=p->elem[b];
            a=b;
            b=b/2;
        }
        p->elem[a]=x;   
    }
    p->size++;
}


void delmin(dui *p)
{
    int i=1;
    int b,c;
    while(2*i<=p->size)
    {
        c=-1;
        if(2*i==p->size)
        {
            p->elem[i]=p->elem[2*i];
            i=2*i;
            c=0;
        }
        else
        {
            if(p->elem[2*i]<p->elem[2*i+1])
            {
            p->elem[i]=p->elem[2*i];
            i=2*i;
            c=1;
            }
            else
            {
            p->elem[i]=p->elem[2*i+1];
            i=2*i+1;
            c=2;
            }
        }
    }
    if(c!=1)
    {
        if(p->elem[i]>p->elem[p->size])
            p->elem[i/2]=p->elem[p->size];
        else
            p->elem[i]=p->elem[p->size];
    }
    p->size--;
}

void dayin(dui *p)
{
    int i;
    for(i=1;i<=p->size;i++)
        printf("%d\n",p->elem[i]);
}


main()
{
    int i,j;
    dui *p;
    printf("请输入堆的大小:\n");
    scanf("%d",&j);
    p=creat(j);
    printf("请输入堆的数据:\n");
    scanf("%d",&i);
    while(i!=0)
    {
        insert(p,i);
        printf("请输入堆的数据:\n");
        scanf("%d",&i);
    }
    delmin(p);
    dayin(p);
   
   
  
}

[ 本帖最后由 zhu224039 于 2012-8-7 02:37 编辑 ]

232

送给伸手党

shang