#2
yuccn2013-03-06 12:23
|
程序代码:
麻烦看一下,基本逻辑上我觉得是没问题的,但是总调试不出来,不知道哪里出问题了
#include<stdio.h>
#define maxdata 50
typedef struct priority
{
int data;
int priority;
}priorityqueue;
priorityqueue a[maxdata];
int n=0;
void minheapfixup(priorityqueue a[],int i)
{
int j;
priorityqueue temp;
temp.priority=a[i].priority;
temp.data=a[i].data;
j=(i-1)/2;
while(j>=0&&i!=0)
{if(a[i].priority<=temp.priority)
break;
a[i].data=a[j].data;
a[i].priority=a[j].priority;
i=j;
j=(i-1)/2;
}
a[i].priority=temp.priority;
a[i].data=temp.data;
}
void minheapadd(priorityqueue a[],int n,int ndata,int npriority)
{
a[n].data=ndata;
a[n].priority=npriority;
minheapfixup(a,n);
n++;
}
void minheapfixdown(priorityqueue a[],int i,int n)
{
int j;
priorityqueue temp;
j=2*i+1;
while(j<n)
{
if(j+1<n&&a[j+1].priority<a[j].priority)
j++;
if(a[j].priority>temp.priority)
break;
a[i].priority=a[j].priority;
a[i].data=a[j].data;
i=j;
j=2*i+1;
}
a[i].priority=temp.priority;
a[i].data=temp.data;
}
void swap(int i,int j)
{priorityqueue temp;
temp.data=a[i].data;
temp.priority=a[i].priority;
a[i].data=a[j].data;
a[i].priority=a[j].priority;
a[j].data=temp.data;
a[j].priority=temp.priority;
}
void minheapdelete(priorityqueue a[],int n)
{swap(0,n-1);
minheapfixdown(a,0,n-1);
}
void makeminheap(priorityqueue a[],int n)
{
for(int i=n/2-1;i>=0;i--)
minheapfixdown(a,i,n);
return;
}
void minheapsortTodescendarray(priorityqueue a[],int n)
{
for(int i=n-1;i>=1;i--)
{
swap(i,0);
minheapfixdown(a,0,i);
}return ;
}
int main()
{ int e,d,p;
printf("请输入数据:\n");
printf("你要输入数据的个数?");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("请输入数据的值");scanf("%d",&a[i].data);
printf("请输入数据的权值");scanf("%d",&a[i].priority);
}
printf("输入完成!请选择");
makeminheap(a,n);
minheapsortTodescendarray(a,n);
do
{printf("\n1查找\n");
printf("2插入\n");
printf("3删除\n");
printf("4退出\n");
scanf("%d",&e);
switch(e)
{
case 1:{printf("最小权值数据为:");printf("%d\n",a[0].data);}break;
case 2:{printf("请输入插入的数据和权值");scanf("%d%d",&d,&p);minheapadd(a,n,d,p); minheapsortTodescendarray(a,n);}break;
case 3:{printf("%d",a[0].data);minheapdelete(a,n); minheapsortTodescendarray(a,n);}break;
case 4:return 0;
}
}while(1);
return 0;
}
#include<stdio.h>
#define maxdata 50
typedef struct priority
{
int data;
int priority;
}priorityqueue;
priorityqueue a[maxdata];
int n=0;
void minheapfixup(priorityqueue a[],int i)
{
int j;
priorityqueue temp;
temp.priority=a[i].priority;
temp.data=a[i].data;
j=(i-1)/2;
while(j>=0&&i!=0)
{if(a[i].priority<=temp.priority)
break;
a[i].data=a[j].data;
a[i].priority=a[j].priority;
i=j;
j=(i-1)/2;
}
a[i].priority=temp.priority;
a[i].data=temp.data;
}
void minheapadd(priorityqueue a[],int n,int ndata,int npriority)
{
a[n].data=ndata;
a[n].priority=npriority;
minheapfixup(a,n);
n++;
}
void minheapfixdown(priorityqueue a[],int i,int n)
{
int j;
priorityqueue temp;
j=2*i+1;
while(j<n)
{
if(j+1<n&&a[j+1].priority<a[j].priority)
j++;
if(a[j].priority>temp.priority)
break;
a[i].priority=a[j].priority;
a[i].data=a[j].data;
i=j;
j=2*i+1;
}
a[i].priority=temp.priority;
a[i].data=temp.data;
}
void swap(int i,int j)
{priorityqueue temp;
temp.data=a[i].data;
temp.priority=a[i].priority;
a[i].data=a[j].data;
a[i].priority=a[j].priority;
a[j].data=temp.data;
a[j].priority=temp.priority;
}
void minheapdelete(priorityqueue a[],int n)
{swap(0,n-1);
minheapfixdown(a,0,n-1);
}
void makeminheap(priorityqueue a[],int n)
{
for(int i=n/2-1;i>=0;i--)
minheapfixdown(a,i,n);
return;
}
void minheapsortTodescendarray(priorityqueue a[],int n)
{
for(int i=n-1;i>=1;i--)
{
swap(i,0);
minheapfixdown(a,0,i);
}return ;
}
int main()
{ int e,d,p;
printf("请输入数据:\n");
printf("你要输入数据的个数?");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("请输入数据的值");scanf("%d",&a[i].data);
printf("请输入数据的权值");scanf("%d",&a[i].priority);
}
printf("输入完成!请选择");
makeminheap(a,n);
minheapsortTodescendarray(a,n);
do
{printf("\n1查找\n");
printf("2插入\n");
printf("3删除\n");
printf("4退出\n");
scanf("%d",&e);
switch(e)
{
case 1:{printf("最小权值数据为:");printf("%d\n",a[0].data);}break;
case 2:{printf("请输入插入的数据和权值");scanf("%d%d",&d,&p);minheapadd(a,n,d,p); minheapsortTodescendarray(a,n);}break;
case 3:{printf("%d",a[0].data);minheapdelete(a,n); minheapsortTodescendarray(a,n);}break;
case 4:return 0;
}
}while(1);
return 0;
}
[ 本帖最后由 c764193441 于 2013-3-6 12:39 编辑 ]