优先级队列和堆（这对我来说很难。）

Question

我想完成此代码。请帮助我ㅠㅠ！

#include <stdio.h>
#include <stdlib.h>

#define HEAP_LEN 100
#define MAX_HEAP 20

struct heapElem{
  int priority;
  char* data;
};

struct _heap{
  int num_data;
  struct heapElem heapArr[HEAP_LEN];
};

int GetPriIdx(struct _heap* ph, int idx);
void swapD(char* a, char* b); 
void swapI(int* a, int* b);
void swap(struct heapElem a, struct heapElem b);
void Insert(struct _heap* ph, char* data, int priority);
void Delete(struct _heap* ph);
void Printout(struct _heap* ph);
void Retrieve(struct _heap* ph);
void KeyIncrease(struct _heap* ph, int priority, int n_priority);

int main(void) {
  struct _heap heap;
  heap.num_data = 0;

  char option_char;
  char name[20];
  int k_value;
  int new_k_value;

  do{
    printf("\n*********** MENU ***************\n");
    printf("I : Insert new element into queue\nD : Delete element with largest key from queue\nR : Retrieve element with largest key from queue\nK : Increase key of element in queue\nP : Print out all elements in queue\nQ : Quit\n\nChoose menu :");
    scanf("%c", &option_char);

    switch(option_char){
      case 'I' : //insert new element into queue
        printf("Enter name of element : ");
        scanf("%s", name);
        printf("Enter key value of element : ");
        scanf("%d", &k_value);
        Insert(&heap, name, k_value);

        break;

      case 'D' : 
        Delete(&heap);
        break;

      case 'R' : 
        Retrieve(&heap);
        break;

      case 'K' : 
        printf("Enter idx of element : ");
        scanf("%d", &k_value);
        printf("Enter new key value : ");
        scanf("%d", &new_k_value);
       KeyIncrease(&heap, k_value, new_k_value);
       break;

     case 'P' : 
        Printout(&heap);
        break;

     default:
          break;

    }


  }while(option_char != 'Q');
  return 0;
}


void swapD(char* a, char* b) {

    char temp = *a;
    *a = *b;
    *b = temp;

}

void swapI(int* a, int* b) {

    int temp = *a;
    *a = *b;
    *b = temp;

}


void Insert(struct _heap* ph, char* data, int priority){
  if(ph->num_data >= MAX_HEAP) return;

  int idx = ph->num_data+1;

  ph->heapArr[idx].data = data;
  ph->heapArr[idx].priority = priority;
  printf("?? instant %d: [%s, %s] \n", idx, ph->heapArr[idx].data, ph->heapArr[idx/2].data);



  while(idx >1 && ph->heapArr[idx].priority > ph->heapArr[idx/2].priority){
    if(priority > ph->heapArr[idx/2].priority){ 
      swapD(ph->heapArr[idx/2].data, ph->heapArr[idx].data);
      swapI(&ph->heapArr[idx/2].priority, &ph->heapArr[idx].priority);
      idx = idx/2;
    }
    else break;
  }

  ph->num_data += 1;
  printf("New element [%s, %d] is inserted.\n",data, priority);

}

我对函数“插入”有疑问在此

ph->heapArr[idx].data = data;
ph->heapArr[idx].priority = priority;

不是优先级，我只将'data放入idx（像这样！ph-> heapArr [idx] .data = data;），但是ph-> Arr中的所有数据都会改变值。在所有ph-> Arr中仅更改数据。

因此，首先插入[cat，5]，然后插入[dog，9]，然后打印[dog，9] [dog，5]

请帮助我ㅠㅠ

Answer 1

插入时，您执行以下操作：

ph->heapArr[idx].data = data;

您将pointer data分配给堆元素。但是您必须copy数据，因为否则所有堆元素都指向same data（在您的主目录中为name）。

所以您应该这样做：

ph->heapArr[idx].data = malloc(strlen(data)+1);
strcpy(ph->heapArr[idx].data, data);

或者您可以使用strdup，为您执行此操作：

ph->heapArr[idx].data = strdup(data);