Очередь приоритетов и куча (мне сложно ..) - PullRequest
Новая
       39

Очередь приоритетов и куча (мне сложно ..)

0 голосов
/ 18 марта 2020

Я хочу завершить этот код. 

#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;

Не приоритет, я только помещать данные в idx (как это ph->heapArr[idx].data = data), но все данные в ph->Arr изменяют значение.

Только данные изменяются во всех ph->Arr.

Итак, сначала вставьте [cat, 5] second Вставьте [dog, 9], затем напечатайте [dog, 9] [dog, 5]

Пожалуйста, помогите мне 101

Ответы [ 2 ]

0 голосов
/ 18 марта 2020

Когда вы используете это ph->heapArr[idx].data = data;, вы не копируете какие-либо данные в

ph->heapArr[idx].data, а указываете на данные, на которые также указывает аргумент функции.

Если вы измените эти данные (in main function), то вы также измените ph->heapArr[idx].data, так как вы указали адрес переменной name в этом указателе ph->heapArr[idx], хотя вы можете изменить переменную name значение, но весь этот массив ph->heapArr[idx] будет по-прежнему указывать на значение, сохраненное в переменной name address, поэтому все они будут меняться.

используйте malloc, чтобы сначала выделить память для этого указателя, а затем вместо того, чтобы указывать на другую переменную, хранить в ней данные (копировать данные, а не просто помещать их в данные) 

ph->heapArr[idx].data = malloc(strlen(data)+1);
strcpy(ph->heapArr[idx].data, data);
0 голосов
/ 18 марта 2020

При вставке, когда вы делаете: 

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

, вы присваиваете указатель data элементу кучи. Но вы должны скопировать данных, потому что в противном случае все элементы кучи указывают на один и тот же data (который name в вашем основном).

Так что вам следует сделайте: 

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

или вы можете использовать strdup, который сделает это за вас: 

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