malloc - Plain C: Binary Heap Segmentation Faults/Reallocation Errors -


i new c, thought i'd learn while i'm learning basic data structures. anyway, i'm having problem wrapping head how/where errors coming in code.

basically, i'm getting 2 different kinds of errors:

  1. segmentation faults (@ binary heap length 2 , 3) when subtracting heap.
  2. malloc/realloc errors when add binary heap enough make length 4 (and beyond), , subtract length 2 (i non-valid binary heap structure @ length 3 when well).

basically, want see i'm doing wrong behavior. also, if there's in code downright appaling, i'd know too.

so, here's code:

void printarray(int array[], int size) {     printf("[");     (int = 0; < size; i++) {         if (i == (size - 1)) {             printf("%d", array[i]);         } else {             printf("%d, ", array[i]);         }     }     printf("]\n"); }  int getleftchild(int h_array[], int p_index, int size) { /* summary: obtains `left child` of parent @ given parent index (p_index)  *   * input: `h_array` - binary heap  *        `p_index` - index of parent looking @  *        `size` - size of binary heap.  *  * return: `0` if index given points out of bounds of array. returns child of parent @ p_index if not  */      int child = 0;     if (p_index * 2 + 1 < size) {         child = h_array[p_index * 2 + 1];     }     return child; }  int getrightchild(int h_array[], int p_index, int size) { /* summary: obtains `right child` of parent @ given parent index (p_index)  *   * input: `h_array` - binary heap  *        `p_index` - index of parent looking @  *        `size` - size of binary heap.  *  * return: `0` if index given points out of bounds of array. returns child of parent @ p_index if not  */      int child = 0;     if ((p_index * 2 + 2) < size) {         child = h_array[p_index * 2 + 2];     }     return child; }  void heapsort(int h_array[], int size, int min_max) { /* summary: performs heap sort on binary heap array; parents 2 children maximum.  *          used implement priority queue, node highest (or lowest)  *          priority @ root of list.  * input: `h_array` - heap array sort  *        `size` - size of heap array  *        `min_max` - input tell whether or not want return 'maxed', or 'min'd' binary heap.  *                      maxed have highest priority @ root, , min'd have lowest priority @ root  *   * returns: not return. performs sorting operations on input array.  **/     int parent, leftchild, rightchild, p_holder, = 0;     while (i < (size / 2)) {         parent = h_array[i];         leftchild = getleftchild(h_array, i, size);         rightchild = getrightchild(h_array, i, size);          if (min_max == 0 ) {             while (parent < leftchild || parent < rightchild) {                 p_holder = parent;                 if (parent < leftchild) {                     h_array[i] = leftchild;                     h_array[(i * 2) + 1] = p_holder;                 } else if (parent < rightchild) {                     h_array[i] = rightchild;                     h_array[(i * 2) + 2] = p_holder;                 }                 = 0;                 parent = h_array[i];                 leftchild = getleftchild(h_array, i, size);                 rightchild = getrightchild(h_array, i, size);             }         i++;         } else {             while ((leftchild != 0 && parent > leftchild) || (rightchild != 0 &&parent > rightchild)) {                 p_holder = parent;                 if ((leftchild != 0) && parent > leftchild) {                     h_array[i] = leftchild;                     h_array[(i * 2) + 1] = p_holder;                 } else if ((rightchild != 0) && parent > rightchild) {                     h_array[i] = rightchild;                     h_array[(i * 2) + 2] = p_holder;                 }                 = 0;                 parent = h_array[i];                 leftchild = getleftchild(h_array, i, size);                 rightchild = getrightchild(h_array, i, size);             }         i++;         }     } }  void heapadd(int h_array[], int *a_size, int value, int *min_max_ptr) { /* summary: adds value binary heap  * input: `h_array` - binary heap array  *        `a_size` - size of array. pointer `size` located in main().  *        `value` - value inserted in array  * returns: void function. performs operations on inputted array.  */      *a_size += 1;      int * a_copy = h_array;      h_array = realloc(h_array, *a_size * sizeof(int));     memcpy(h_array, a_copy, (*a_size - 2) * sizeof(int));      h_array[*a_size - 1] = value;      heapsort(h_array, *a_size, *min_max_ptr); }  void heapsub(int h_array[], int *a_size, int *min_max_ptr) { /* summary: subtracts root value binary heap  * input: `h_array` - binary heap array  *        `a_size` - size of array. pointer `size` located in main().  * returns: void function. performs operations on inputted array.  */     h_array[0] = h_array[*a_size - 1];      int * a_copy = h_array;      h_array = realloc(h_array, *a_size - 1 * sizeof(int));      memcpy(h_array, a_copy, (*a_size - 1) * sizeof(int));      *a_size -= 1; // put here in order not stupid calculations in calls.      heapsort(h_array, *a_size, *min_max_ptr); }  int main(void) {     char * user_input;     int user_value;     int debug = 0;      // min_max = 0 produce max-heap, min_max = 1 produce min-heap     int min_max = 0;     int *min_max_ptr = &min_max;      int size = 0;     int *size_ptr = &size;      // binary heap array, initialized here     int * main_array = malloc(size * sizeof(int));      // start building binary heap following loop.     while (strcmp(user_input, "q") != 0) {          printf("current heap:\n");         printarray(main_array, size);          // debug         if (debug) {             printf("current heap size: %i\n", size);         }          printf("what input?: ");         scanf("%s", user_input);          // debug         if (debug) {             printf("current user input is: %s\n", user_input);         }          if (strcmp(user_input, "add") == 0) {              printf("what # adding heap?: ");             scanf("%i", &user_value);             heapadd(main_array, size_ptr, user_value, min_max_ptr);          } else if (strcmp(user_input, "sub") == 0) {              printf("subtracting %i array\n", main_array[0]);             heapsub(main_array, size_ptr, min_max_ptr);          } else if (strcmp(user_input, "debug") == 0) {              printf("do want toggle debug mode(y/n): ");             scanf("%s", user_input);              if (strcmp(user_input, "y") == 0) {                  debug = (debug == 0) ? 1 : 0;                 printf("debug is: %i", debug);              } else {                  continue;             }         } else {              printf("incorrect input, please read instructions more\n\n");         }          printf("\n");     }      free(main_array);     return 0; }

so that's code, , here test cases:

  1. subtracting highest value heap @ length = 2 test case 1
  2. subtracting highest values heap starting @ length = 4 , going length = 2 test case 2

after seems every other test case works fine (past length = 4 can add , subtract binary heap fine , sorting process works great). thank :)

i able reach solution problems making following changes code:

void heapadd(int h_array[], int *a_size, int value, int *min_max_ptr) { /* summary: adds value binary heap  * input: `h_array` - binary heap array  *        `a_size` - size of array. pointer `size` located in main().  *        `value` - value inserted in array  * returns: void function. performs operations on inputted array.  */      *a_size += 1;     h_array[*a_size - 1] = value;     heapsort(h_array, *a_size, *min_max_ptr); }  void heapsub(int h_array[], int *a_size, int *min_max_ptr) { /* summary: subtracts root value binary heap  * input: `h_array` - binary heap array  *        `a_size` - size of array. pointer `size` located in main().  * returns: void function. performs operations on inputted array.  */     h_array[0] = h_array[*a_size - 1];     h_array[*a_size - 1] = 0;     *a_size -= 1; // put here in order not stupid calculations in calls.     heapsort(h_array, *a_size, *min_max_ptr); }  int main(void) {     char * user_input;     int user_value;     int debug = 0;      // min_max = 0 produce max-heap, min_max = 1 produce min-heap     int min_max = 0;     int *min_max_ptr = &min_max;      int size = 0;     int *size_ptr = &size;      int alloc_size = 1000;     int * main_array = malloc(alloc_size * sizeof(int));      {         if (alloc_size - size < 2) {             printf("reallocating main_array size");             alloc_size += 1000;             main_array = realloc(main_array, alloc_size * sizeof(int));             if (main_array == null) {                 printf("realloc addition failed, exiting");                 exit(1);             }         } else if (alloc_size - size > 1002) {             alloc_size -= 1000;             main_array = realloc(main_array, alloc_size * sizeof(int));             if (main_array == null) {                 printf("realloc subtraction failed, exiting");                 exit(1);             }         }         printf("current heap:\n");         printarray(main_array, size);         // debug         if (debug) {             printf("current heap size: %i\n", size);         }         printf("what input?: ");         scanf("%s", user_input);         // debug         if (debug) {             printf("current user input is: %s\n", user_input);         }         if (strcmp(user_input, "add") == 0) {             printf("what # adding heap?: ");             scanf("%i", &user_value);             heapadd(main_array, size_ptr, user_value, min_max_ptr);         } else if (strcmp(user_input, "sub") == 0) {             if (size == 0) {                 printf("can't subtract more heap.\n");                 continue;             } else {                 printf("subtracting %i array\n", main_array[0]);                 heapsub(main_array, size_ptr, min_max_ptr);             }         } else if (strcmp(user_input, "debug") == 0) {             printf("do want toggle debug mode(y/n): ");             scanf("%s", user_input);             if (strcmp(user_input, "y") == 0) {                 debug = (debug == 0) ? 1 : 0;                 printf("debug is: %i", debug);             } else {                 continue;             }         } else {             printf("incorrect input, please read instructions more fully\n\n");         }         printf("\n");     } while (strcmp(user_input, "q") != 0);     free(main_array);     return 0; }

Comments

Post a Comment

Popular posts from this blog

android - InAppBilling registering BroadcastReceiver in AndroidManifest -

i'm implementing inapp billing in android app. works well, however, i'm trying decouple broadcast receiver activity manifest. suggestion in android's trivialdrive sample: // important: dynamically register broadcast messages updated purchases. // register receiver here instead of <receiver> in manifest // because call getpurchases() @ startup, therefore can ignore // broadcasts sent while app isn't running. // note: registering listener in activity bad idea, done here // because sample. regardless, receiver must registered after // iabhelper setup, before first call getpurchases(). currently there's class extends broadcastreceiver : public class iabbroadcastreceiver extends broadcastreceiver { /** * intent action receiver should filter for. */ public static final string action = "com.android.vending.billing.purchases_updated"; private final iabbroadcastlistener mlistener; public iabbroadcastreceiver(iabbroadcastlistener listener) { m...
Read more

python Tkinter Capturing keyboard events save as one single string -

is possible store keyboard events 1 string? code below stores 1 char , prints it. card reader or bar code reader, contains collection of character/ string not 1 character @ time. goal save char pressed text variable. from tkinter import * root = tk() def key(event): text= event.char text+= event.char print ("pressed", text) def callback(event): frame.focus_set() print ("clicked at", event.x, event.y) frame = frame(root, width=100, height=100) frame.bind("<key>", key) frame.bind("<button-1>", callback) frame.pack() root.mainloop() currently, creating text variable , everytime key() function gets called, , text stores last character typed. you can define text module level variable , , use module level text inside key function - text = '' def key(event): global text text+= event.char print("pressed", text)
Read more

sql server - Why does Linq-to-SQL add unnecessary COUNT()? -

here tables: create table customer ( cid int primary key, name varchar(32) ) create table ord ( oid int primary key, cid int foreign key references customer, address varchar(20) ) here's linq-to-sql statement: var aaa = c in db.customer select new { c, o = c.ord.tolist() }; and here's inexplicable query generated linq-to-sql: select [t0].[cid] [cid], [t0].[name] [name], [t1].[oid] [oid], [t1].[cid] [cid2], [t1].[address] [address], (select count(*) [dbo].[ord] [t2] [t2].[cid] = [t0].[cid]) [value] [dbo].[customer] [t0] left outer join [dbo].[ord] [t1] on [t1].[cid] = [t0].[cid] order [t0].[cid], [t1].[oid] i want understand how rid of count(*) part. it's entirely uncalled for! linq needs count(*) in order determine number of entries returned o = c.ord.tolist() .
Read more