Question

数据结构题目，求大神解决。！~！

已知关键字序列为：
（46,74,16,53,14,26,40,38,86,65,27,34）
（1）请画出初始堆（大根堆）所对应的完全二叉树；
（2）在堆排序过程中，如果已知第2次调整堆疑惑得到的结果如下：（65 53 40 46 27 34 16 38 26 14）（74 86）请给出经第3次调整堆以后的结果

Answer 1

很简单，只是计算过程比较繁琐。我把它画出来了，画的比较丑你看不懂再追问！

（1）层次遍历是：86，74，40，53，65，36，16，38，46，14，27，26

（2）答案是：(53,46,40,38,27,34,16,14,26) (74,86,65)

Answer 2

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 100//散列表长度
struct Node
{
char* key; char* val;
Node* next;
}*heads[N];//散列表，用链处理冲突
int hash(char* key)//散列函数
{
unsigned long h=0;
while(*key)
{
h=(h<<4)+*key++;
unsigned long g=h & 0xF0000000L;
if(g)
h^=g>>24;
h&=~g;
}
return h&N;
}
Node* find(char* key)//查找
{
Node* cur=heads[hash(key)];
while(cur)
{
if(!strcmp(cur->key,key))
return cur;
cur=cur->next;
}
return NULL;
}
void insert(char* key,char* val)//插入
{
int i=hash(key);
Node* head=heads[i];
if(find(key)==NULL)
{
Node* tmp=(Node*)malloc(sizeof(Node));
tmp->key=(char*)malloc(strlen(key)+1);
tmp->val=(char*)malloc(strlen(val)+1);
strcpy(tmp->key,key);
strcpy(tmp->val,val);

tmp->next=head;
heads[i]=tmp;
}
}
main()
{
char tmp[100],*key,*val;
Node* cur;
FILE *fp=fopen("abc.txt","r");
if(fp==NULL)
{
printf("打开文件有问题\n");
exit(1);
}
while(fgets(tmp,100,fp)!=NULL)
{
if(tmp[strlen(tmp)-1]=='\n')
tmp[strlen(tmp)-1]='\0';
key=strtok(tmp,"\t");
val=strtok(NULL,"\t");
insert(key,val);
}

printf("输入你要查找的单词:\n");
while(gets(tmp))
{
cur=find(tmp);
if(cur==NULL)
printf("没找到\n");
else
printf("%s\n",cur->val);

}

}