0

I want to insert a node int the end of the linked list, but I don't know how to achieve.

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

typedef struct Info* PtrToNode;
struct Info {
    int number;
    PtrToNode next;
};
typedef struct Info* list;

typedef struct HashNode* HashTable;
struct HashNode {
    list Heads;
    int size;
};

HashTable createTable(int size) {
    HashTable H = (HashTable)malloc(sizeof(struct HashNode));
    H->size = size;
    H->Heads = (PtrToNode)malloc(H->size * sizeof(struct Info));
    for (int i = 0; i < H->size; ++i)
    {
        H->Heads[i].number = 0;
        H->Heads[i].next = NULL;
    }
    return H;
}

int Hash(int n, int size) {
    return n % size;
}

void insert(HashTable H, int index, int number) {
    int pos = Hash(number, H->size);

    list check = H->Heads[pos].next;
    while (check) {
        check = check->next;
    }
    PtrToNode newNode = (PtrToNode)malloc(sizeof(struct Info));
    newNode->number = number;
    newNode->next = NULL;
    check = newNode;
}

I want append in the insert function, but the params "check" like temporary, and if I "while" the H->heads[pos], the node always in the head.

查伟昌
  • 9
  • 2
  • What is the problem with your actual code? Also, instead of `list check = H-Heads[pos].next;` you should first make sure the list is not empty, then poiunt to the head of the list; that is: `if(H->Heads[pos]) check=H->Heads[pos];` – PhoenixBlue Nov 21 '18 at 07:05
  • You are confusing arrays and lists. `H->Heads[i].number` is not the proper way to access a list. For a list you need `H->Heads->number` and `H->Heads->next`. The `next` pointer will point to the next element of the list – Rishikesh Raje Nov 21 '18 at 07:10
  • You are using `for (int i = 0; i < H->size; ++i)` to iterate across a list, which is totally wrong. – Rishikesh Raje Nov 21 '18 at 07:11
  • A list usually has a pointer to the first node (`head`) and a pointer to the last node (`tail`). But you are using a node to represent the whole list which obviously lacks `tail`. Without `tail` appending a node to a list is very inefficient. With tail: `tail->next = new_node; tail = new_node;` Look [here](https://stackoverflow.com/a/53380533/3975177) for a possible implementation. – Swordfish Nov 21 '18 at 07:16

1 Answers1

0

You are confusing arrays and lists. H->Heads[i].number is not the proper way to access a list. For a list you need H->Heads->number and H->Heads->next. The next pointer will point to the next element of the list

Basically you have an array of numbers with an extra unused pointer.

For the create function given to add an element at the end, you need to realloc the entire array with new size. However, this is probably not what you want.

You need to modify the create function to make a true list and then you can append.

Code below, inserts at the end, you can modify to insert at a particular index.

typedef struct Info* PtrToNode;
struct Info {
    int number;
    PtrToNode next;
};
typedef struct Info* list;

typedef struct HashNode* HashTable;
struct HashNode {
    list Heads;
    int size;
};

HashTable createTable(int size) {
    HashTable H = (HashTable)malloc(sizeof(struct HashNode));
    H->size = size;
    H->Heads = malloc(sizeof(struct Info));
    H->Heads->number = 0;
    H->Heads->next = NULL;

    list curr = H->Heads;
    list nextval;

    for (int i = 1; i < H->size; ++i)
    {
        nextval = malloc(sizeof(struct Info));
        nextval->number = 0;
        nextval->next = NULL;
        curr->next = nextval;
        curr = curr->next;
    }
    return H;
}

int Hash(int n, int size) {
    return n % size;
}


void insert(HashTable H, int index, int number) {
    int pos = Hash(number, H->size);

    list check = H->Heads;
    while (check->next)  {
        check = check->next;
    }
    PtrToNode newNode = (PtrToNode)malloc(sizeof(struct Info));
    newNode->number = number;
    newNode->next = NULL;
    check->next = newNode;

    (H->size)++;
}
Rishikesh Raje
  • 8,556
  • 2
  • 16
  • 31