按结构对数组进行堆排序
Making heap sort array by struct
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#define maxelements 1000001
typedef struct {
int key;
} element;
int maxn=0;
int minn=0 ;
element maxheap[maxelements];
element minheap[maxelements];
element copyheap[maxelements];
void insertmaxheap(element item, int *maxn);
void insertminheap(element item , int *minn);
element deletemaxheap(int *maxn);
element deleteminheap(int *minn);
int main(int argc, char* argv[]){
double start,end;
start= (double)clock()/CLOCKS_PER_SEC;
//////////////////////////////////////////////////////////////
int get,num,j ;
int maxtemp,mintemp;
element newitem,item;//element to print
char arr[8];
char insert[] = "INSERT";
char ascend[] = "ASCEND";
char descend[] = "DESCEND";
if(argc !=2)
{
printf("usage: ./hw2 input_filename");
}
FILE *fp = fopen(argv[1],"r");
// FILE *result = fopen("hw2_result.txt", "w");
if(fp == NULL){
printf("The input file does not exist.\n");
}
while(!feof(fp)) {
get = fscanf(fp,"%s %d",arr,&num);
if (!strcmp(arr,insert)) { //putting num into maxheap and minheap
printf("%d is number to insert\n", num);
newitem.key = num ;
insertmaxheap(newitem, &maxn);
insertminheap(newitem, &minn);
}
if (!strcmp(arr,ascend)) {
//copy minheap to copyheap and then use
memcpy(©heap, &minheap,sizeof(minheap));
mintemp = minn;
printf("%d is total number and i will ascend\n", minn);
for(j = 0; j < minn; j++) {
item = deleteminheap(&minn);
printf("%d ",item.key);
}
minn = mintemp;
}
printf("\n");
if (!strcmp(arr,descend)) {
//copy maxheap to copyheap and then use
memcpy(©heap,&maxheap,sizeof(maxheap));
maxtemp = maxn;
printf("%d is total number and i will descend\n", maxn);
for(j = 0; j < maxn; j++) {
item = deletemaxheap(&maxn);
printf("%d ",item.key );
}
maxn = maxtemp;
}
printf("\n");
}
fclose(fp);
end = (((double)clock()) / CLOCKS_PER_SEC);
printf("output written to hw2_result.txt.\n");
printf("running time: %1f\n", (end-start));
}
void insertmaxheap(element item, int *maxn) {
int temp;
temp = ++(*maxn);
while((temp != 1) && (item.key > maxheap[temp/2].key)) {
maxheap[temp] = maxheap[temp/2];
temp /= 2;
}
maxheap[temp] = item;
printf("i put %d in %d and %d \n",item.key, temp,*maxn);
}
void insertminheap(element item , int *minn) {
int i;
i = ++(*minn);
while((i != 1) && (item.key < minheap[i/2].key)) {
minheap[i] = minheap[i/2];
i /= 2;
}
minheap[i] = item;
printf("i put %d in %d\n", item.key,i);
}
element deletemaxheap(int *maxn) {
//copy it to copyheap first
int parent, child;
element item,temp;
item = copyheap[1];
temp = copyheap[(*maxn)--];
parent = 1;
child = 2;
while(child <= *maxn) {
if((child < *maxn) && (copyheap[child].key < copyheap[child+1].key)) child++;
if(temp.key >= copyheap[child].key) break;
copyheap[parent] = copyheap[child];
parent = child;
child *= 2;
}
copyheap[parent] = temp;
return item;
}
element deleteminheap(int *minn){
//copy it to copyheap first
int parent,child;
parent = 1;
child = 2 ;
element item, temp;
item = copyheap[1];
temp = copyheap[(*minn)--];
while(child <= *minn){
if((child < *minn)&&(copyheap[child].key > copyheap[child+1].key)) child++;
if(temp.key <= copyheap[child].key) break;
copyheap[parent] = copyheap[child];
parent = child;
child *= 2 ;
}
copyheap[parent] = temp;
return item;
}
这是我从输入文件中获取数字并生成最大堆、最小堆的代码。
最大堆和最小堆的最大容量都应为 1000000。我想我差不多
制作了制作这两个堆的功能，但效果不佳。此外我做了
在打印出存储的数字之前，再用一个堆来存储最大和最小堆。
我认为这样的代码很好
- 它在输入中接受命令，如 INSERT、DESCEND、ASCEND
- 使用memcpy函数可以很好的复制堆
但我希望在命令为 ascend 时打印结果 1 2 3 4 5
和 5 4 3 2 1 当命令下降时。但是问题来了。
- 在函数“insertmaxheap”中，整数温度与 ++(*maxn) 不同，即使我写了 temp=++(*maxn)
- 在函数“deleteminheap”中，它应该打印所有 5 个数字，但它停止在 3 个剩余的 2 个数字上。
示例输入文件如下所示：
INSERT 1
INSERT 2
INSERT 3
INSERT 4
INSERT 5
ASCEND
DESCEND
第一次学c编程
在大学里，但这对我来说很难。我已经考虑了整整 3 天的代码，但不能
找到明确的解决方案。由于在韩国有cor-vid，我通过在线学习，我有朋友可以
帮我。抱歉给了太多问题和代码。
我重写了你的代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#define MAX_ELEMENTS 1000001
typedef struct {
int key;
}element;
int maxn=0;
int minn=0 ;
element maxheap[MAX_ELEMENTS];
element minheap[MAX_ELEMENTS];
element copyheap[MAX_ELEMENTS];
void insertmaxheap(element item, int *maxn);
void insertminheap(element item , int *minn);
element deletemaxheap(int *maxn);
element deleteminheap(int *minn);
int main(int argc, char* argv[]){
double start,end;
start= (double)clock()/CLOCKS_PER_SEC;
//////////////////////////////////////////////////////////////
int get,num,j ;
int maxtemp,mintemp;
element newitem,item;//element to print
char arr[8];
if(argc !=2)
{
printf("usage: ./hw2 input_filename");
}
FILE *fp =fopen(argv[1],"r");
// FILE *result= fopen("hw2_result.txt", "w");
if(fp==NULL){
printf("The input file does not exist.\n");
}
while(!feof(fp)){
get= fscanf(fp,"%s %d",arr,&num);
if (!strcmp(arr,"INSERT")){//putting num into maxheap and minheap
printf("%d is number to insert\n", num);
newitem.key=num ;
insertmaxheap(newitem, &maxn);
insertminheap(newitem, &minn);
}
if (!strcmp(arr,"ASCEND")){
//copy minheap to copyheap and then use
memcpy(©heap, &minheap,sizeof(minheap));
mintemp=minn;
printf("%d is total number and i will ascend\n", minn);
for(j=0; j<mintemp;j++){
item=deleteminheap(&minn);
printf("%d ",item.key);
}
printf("\nminn = %i\n", minn);
}
printf("\n");
if (!strcmp(arr,"DESCEND")){
//copy maxheap to copyheap and then use
memcpy(©heap,&maxheap,sizeof(maxheap));
maxtemp=maxn;
printf("%d is total number and i will descend\n", maxn);
for(j=0;j<maxtemp;j++){
item= deletemaxheap(&maxn);
printf("%d ",item.key );
}
printf("\nmaxn: %d\n", maxn);
}
printf("\n");
}
fclose(fp);
end=(((double)clock())/CLOCKS_PER_SEC);
printf("output written to hw2_result.txt.\n");
printf("running time: %1f\n", (end-start));
}
void insertmaxheap(element item, int *maxn){
int temp;
temp=*maxn;
(*maxn)++;
while((temp!=0)&&(item.key>maxheap[temp/2].key)){
maxheap[temp]=maxheap[temp/2];
temp/=2;
}
maxheap[temp]=item;
printf("i put %d in %d and %d \n",item.key, temp,*maxn);
}
void insertminheap(element item , int *minn){
int i;
i=*minn;
++(*minn);
while((i!=0)&&(item.key<minheap[i/2].key)){
minheap[i]=minheap[i/2];
i/=2;
}
minheap[i]=item;
printf("i put %d in %d\n", item.key,i);
}
element deletemaxheap(int *maxn){
//copy it to copyheap first
int parent, child;
element item,temp;
item=copyheap[0];
temp=copyheap[*maxn];
(*maxn)--;
parent=0;
child=1;
while(child<=*maxn){
if((child<*maxn)&&(copyheap[child].key<copyheap[child+1].key))child++;
if(temp.key>=copyheap[child].key){
break;
}
copyheap[parent]=copyheap[child];
parent=child;
child*=2;
}
copyheap[parent]=temp;
return item;
}
element deleteminheap(int *minn){
//copy it to copyheap first
int parent,child;
parent=0;
child=1 ;
element item,temp;
item = copyheap[0];
temp= copyheap[(*minn)-1];
(*minn)--;
while(child<=*minn){
if((child<*minn)&&(copyheap[child].key>copyheap[child+1].key))child++;
if(temp.key<=copyheap[child].key)break;
copyheap[parent]=copyheap[child];
parent=child;
child*=2 ;
}
copyheap[parent]=temp;
return item;
}
我确保两个数组都从索引 0 而不是 1 开始，这就是变量 tmp 这次达到 0 而不是 1 的原因。
回答你的第一个问题：
变量 tmp 只要达到 0（之前为 1）就会除以二。
回答你的第二个问题：
您的 maxheap 排序算法确实有效，但对于 minheap 则存在问题。它超出内存范围（超出 `copyheap` 数组）。这就是它没有打印所有数字的原因。
我在这里和那里更改了您的代码，以使其对我来说更加可见。希望它不会让您感到困惑。
如果您对这段代码有更多疑问，请将它们写下来，我很乐意回答。我也是学生所以我在纠正其他学生的乱码方面有一些经验所以随时问;D
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#define maxelements 1000001
typedef struct {
int key;
} element;
int maxn=0;
int minn=0 ;
element maxheap[maxelements];
element minheap[maxelements];
element copyheap[maxelements];
void insertmaxheap(element item, int *maxn);
void insertminheap(element item , int *minn);
element deletemaxheap(int *maxn);
element deleteminheap(int *minn);
int main(int argc, char* argv[]){
double start,end;
start= (double)clock()/CLOCKS_PER_SEC;
//////////////////////////////////////////////////////////////
int get,num,j ;
int maxtemp,mintemp;
element newitem,item;//element to print
char arr[8];
char insert[] = "INSERT";
char ascend[] = "ASCEND";
char descend[] = "DESCEND";
if(argc !=2)
{
printf("usage: ./hw2 input_filename");
}
FILE *fp = fopen(argv[1],"r");
// FILE *result = fopen("hw2_result.txt", "w");
if(fp == NULL){
printf("The input file does not exist.\n");
}
while(!feof(fp)) {
get = fscanf(fp,"%s %d",arr,&num);
if (!strcmp(arr,insert)) { //putting num into maxheap and minheap
printf("%d is number to insert\n", num);
newitem.key = num ;
insertmaxheap(newitem, &maxn);
insertminheap(newitem, &minn);
}
if (!strcmp(arr,ascend)) {
//copy minheap to copyheap and then use
memcpy(©heap, &minheap,sizeof(minheap));
mintemp = minn;
printf("%d is total number and i will ascend\n", minn);
for(j = 0; j < minn; j++) {
item = deleteminheap(&minn);
printf("%d ",item.key);
}
minn = mintemp;
}
printf("\n");
if (!strcmp(arr,descend)) {
//copy maxheap to copyheap and then use
memcpy(©heap,&maxheap,sizeof(maxheap));
maxtemp = maxn;
printf("%d is total number and i will descend\n", maxn);
for(j = 0; j < maxn; j++) {
item = deletemaxheap(&maxn);
printf("%d ",item.key );
}
maxn = maxtemp;
}
printf("\n");
}
fclose(fp);
end = (((double)clock()) / CLOCKS_PER_SEC);
printf("output written to hw2_result.txt.\n");
printf("running time: %1f\n", (end-start));
}
void insertmaxheap(element item, int *maxn) {
int temp;
temp = ++(*maxn);
while((temp != 1) && (item.key > maxheap[temp/2].key)) {
maxheap[temp] = maxheap[temp/2];
temp /= 2;
}
maxheap[temp] = item;
printf("i put %d in %d and %d \n",item.key, temp,*maxn);
}
void insertminheap(element item , int *minn) {
int i;
i = ++(*minn);
while((i != 1) && (item.key < minheap[i/2].key)) {
minheap[i] = minheap[i/2];
i /= 2;
}
minheap[i] = item;
printf("i put %d in %d\n", item.key,i);
}
element deletemaxheap(int *maxn) {
//copy it to copyheap first
int parent, child;
element item,temp;
item = copyheap[1];
temp = copyheap[(*maxn)--];
parent = 1;
child = 2;
while(child <= *maxn) {
if((child < *maxn) && (copyheap[child].key < copyheap[child+1].key)) child++;
if(temp.key >= copyheap[child].key) break;
copyheap[parent] = copyheap[child];
parent = child;
child *= 2;
}
copyheap[parent] = temp;
return item;
}
element deleteminheap(int *minn){
//copy it to copyheap first
int parent,child;
parent = 1;
child = 2 ;
element item, temp;
item = copyheap[1];
temp = copyheap[(*minn)--];
while(child <= *minn){
if((child < *minn)&&(copyheap[child].key > copyheap[child+1].key)) child++;
if(temp.key <= copyheap[child].key) break;
copyheap[parent] = copyheap[child];
parent = child;
child *= 2 ;
}
copyheap[parent] = temp;
return item;
}
这是我从输入文件中获取数字并生成最大堆、最小堆的代码。 最大堆和最小堆的最大容量都应为 1000000。我想我差不多 制作了制作这两个堆的功能，但效果不佳。此外我做了 在打印出存储的数字之前，再用一个堆来存储最大和最小堆。 我认为这样的代码很好
- 它在输入中接受命令，如 INSERT、DESCEND、ASCEND
- 使用memcpy函数可以很好的复制堆
但我希望在命令为 ascend 时打印结果 1 2 3 4 5 和 5 4 3 2 1 当命令下降时。但是问题来了。
- 在函数“insertmaxheap”中，整数温度与 ++(*maxn) 不同，即使我写了 temp=++(*maxn)
- 在函数“deleteminheap”中，它应该打印所有 5 个数字，但它停止在 3 个剩余的 2 个数字上。
示例输入文件如下所示：
INSERT 1
INSERT 2
INSERT 3
INSERT 4
INSERT 5
ASCEND
DESCEND
第一次学c编程 在大学里，但这对我来说很难。我已经考虑了整整 3 天的代码，但不能 找到明确的解决方案。由于在韩国有cor-vid，我通过在线学习，我有朋友可以 帮我。抱歉给了太多问题和代码。
我重写了你的代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#define MAX_ELEMENTS 1000001
typedef struct {
int key;
}element;
int maxn=0;
int minn=0 ;
element maxheap[MAX_ELEMENTS];
element minheap[MAX_ELEMENTS];
element copyheap[MAX_ELEMENTS];
void insertmaxheap(element item, int *maxn);
void insertminheap(element item , int *minn);
element deletemaxheap(int *maxn);
element deleteminheap(int *minn);
int main(int argc, char* argv[]){
double start,end;
start= (double)clock()/CLOCKS_PER_SEC;
//////////////////////////////////////////////////////////////
int get,num,j ;
int maxtemp,mintemp;
element newitem,item;//element to print
char arr[8];
if(argc !=2)
{
printf("usage: ./hw2 input_filename");
}
FILE *fp =fopen(argv[1],"r");
// FILE *result= fopen("hw2_result.txt", "w");
if(fp==NULL){
printf("The input file does not exist.\n");
}
while(!feof(fp)){
get= fscanf(fp,"%s %d",arr,&num);
if (!strcmp(arr,"INSERT")){//putting num into maxheap and minheap
printf("%d is number to insert\n", num);
newitem.key=num ;
insertmaxheap(newitem, &maxn);
insertminheap(newitem, &minn);
}
if (!strcmp(arr,"ASCEND")){
//copy minheap to copyheap and then use
memcpy(©heap, &minheap,sizeof(minheap));
mintemp=minn;
printf("%d is total number and i will ascend\n", minn);
for(j=0; j<mintemp;j++){
item=deleteminheap(&minn);
printf("%d ",item.key);
}
printf("\nminn = %i\n", minn);
}
printf("\n");
if (!strcmp(arr,"DESCEND")){
//copy maxheap to copyheap and then use
memcpy(©heap,&maxheap,sizeof(maxheap));
maxtemp=maxn;
printf("%d is total number and i will descend\n", maxn);
for(j=0;j<maxtemp;j++){
item= deletemaxheap(&maxn);
printf("%d ",item.key );
}
printf("\nmaxn: %d\n", maxn);
}
printf("\n");
}
fclose(fp);
end=(((double)clock())/CLOCKS_PER_SEC);
printf("output written to hw2_result.txt.\n");
printf("running time: %1f\n", (end-start));
}
void insertmaxheap(element item, int *maxn){
int temp;
temp=*maxn;
(*maxn)++;
while((temp!=0)&&(item.key>maxheap[temp/2].key)){
maxheap[temp]=maxheap[temp/2];
temp/=2;
}
maxheap[temp]=item;
printf("i put %d in %d and %d \n",item.key, temp,*maxn);
}
void insertminheap(element item , int *minn){
int i;
i=*minn;
++(*minn);
while((i!=0)&&(item.key<minheap[i/2].key)){
minheap[i]=minheap[i/2];
i/=2;
}
minheap[i]=item;
printf("i put %d in %d\n", item.key,i);
}
element deletemaxheap(int *maxn){
//copy it to copyheap first
int parent, child;
element item,temp;
item=copyheap[0];
temp=copyheap[*maxn];
(*maxn)--;
parent=0;
child=1;
while(child<=*maxn){
if((child<*maxn)&&(copyheap[child].key<copyheap[child+1].key))child++;
if(temp.key>=copyheap[child].key){
break;
}
copyheap[parent]=copyheap[child];
parent=child;
child*=2;
}
copyheap[parent]=temp;
return item;
}
element deleteminheap(int *minn){
//copy it to copyheap first
int parent,child;
parent=0;
child=1 ;
element item,temp;
item = copyheap[0];
temp= copyheap[(*minn)-1];
(*minn)--;
while(child<=*minn){
if((child<*minn)&&(copyheap[child].key>copyheap[child+1].key))child++;
if(temp.key<=copyheap[child].key)break;
copyheap[parent]=copyheap[child];
parent=child;
child*=2 ;
}
copyheap[parent]=temp;
return item;
}
我确保两个数组都从索引 0 而不是 1 开始，这就是变量 tmp 这次达到 0 而不是 1 的原因。
回答你的第一个问题：
变量 tmp 只要达到 0（之前为 1）就会除以二。
回答你的第二个问题：
您的 maxheap 排序算法确实有效，但对于 minheap 则存在问题。它超出内存范围（超出 `copyheap` 数组）。这就是它没有打印所有数字的原因。我在这里和那里更改了您的代码，以使其对我来说更加可见。希望它不会让您感到困惑。
如果您对这段代码有更多疑问，请将它们写下来，我很乐意回答。我也是学生所以我在纠正其他学生的乱码方面有一些经验所以随时问;D