Как правильно распределить память для этого связанного списка

Question

Кажется, я не могу понять, в чем проблема с распределением памяти. Все функции работают должным образом, но программа случайным образом аварийно завершает свою работу. Я знаю, что ошибка в том, как я распределяю память для связанного списка, но я просто не могу понять, какая часть неправильная.

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <cstring>

using namespace std;
void menu_function(void);
void command_execute(string command, string name1, string name2);
int hash_function(string str);
void insert_into_hashtable(int ascii_total, string name);
void add_friendship(int ascii_key, string name);
void print_friendships(int aascii_key);
void check_friendship(int ascii_key, string name);
void remove_friendship(int ascii_key, string name);

#define SIZE 125

struct friend_list {
    string name = "";
    struct friend_list * next;
};

typedef struct friend_list list;

struct user {
    string name;
    int key;
    friend_list * FriendList;
};

struct user * hashArray[SIZE];

int main(int argc,
    const char * argv[]) {

    menu_function();
    return 0;
}

void menu_function() {
    char user_input[100]; //this could limit the size of input
    string command;
    string name1 = "\0";
    string name2 = "\0";;
    char * token; ** strong text **
        int inputsize = 100;
    int i = 0;
    char delimit[] = " \t\r\n\v\f";
    while (1) {
        printf("\nP <Name> to create a person\n");
        printf("F <Name> <Name> record friendship\n");
        printf("U <Name> <Name> terminate friendship\n");
        printf("L <Name> print out friends of a specified person\n");
        printf("Q <Name> <Name>  check friendship status of two people\n");
        printf("X - terminate the progarm\n");

        // Determine user input and
        fgets(user_input, inputsize, stdin);
        //getline(&input, &inputsize, stdin);//takes in user input;

        //printf("input: %s", user_input);

        //parsing the string for the data within
        token = strtok(user_input, delimit);
        i = 0;
        while (token != NULL) {
            if (i == 0) {
                command = token;
                //cout<< command<<endl;
            }
            if (i == 1) {
                name1 = token;
                // cout<< name1<<":"<<endl;
            }
            if (i == 2) {
                name2 = token;
                //  cout<< name2<<":"<<endl;
                name1 = name1 + "\n";
            }
            token = strtok(NULL, " ");
            i++;
        }
        command_execute(command, name1, name2);
        command = '\0';
        name1 = '\0';
        name2 = '\0';
    }
}

void command_execute(string command, string name1, string name2) {
    //cout<<"command is: "<<command<<endl;

    switch (command[0]) {

    case 'P': //Create record of the person
        insert_into_hashtable(hash_function(name1), name1);
        break;
    case 'F': //Record friendship
        add_friendship(hash_function(name1), name2);
        add_friendship(hash_function(name2), name1);
        break;
    case 'U': //Terminate Friendship
        remove_friendship(hash_function(name1), name2);
        remove_friendship(hash_function(name2), name1);
        break;
    case 'L': //Print out the persons Friends
        print_friendships(hash_function(name1));
        break;
    case 'Q': //Check on friendship
        check_friendship(hash_function(name1), name2);
        break;
    case 'X': //Exit the program **** COMPLETED
        exit(1);
        break;

    default:
        cout << "Error occured based on your command please try again" << endl;
        break;
    }
}

int hash_function(string string) {
    //going to use the ASCI value of the name with different weights per array position to hash the names
    int ascii_key = 0;
    int ascii_total = 0;
    // cout<< string.length()<< endl;
    //cout<< string<< endl;
    for (int i = 0; i < string.length() - 1; i++) {
        ascii_total = (int) string[i] * (i * 3 + 1);
        //   cout<< string[i]<< endl;
    }
    ascii_key = ascii_total % SIZE;
    //deals with colisions through open hashing
    while (hashArray[ascii_key] != NULL && strcmp(hashArray[ascii_key] - > name.c_str(), string.c_str())) { //strcmp(hashArray[ascii_key]->name.c_str(), string.c_str())
        //hashArray[ascii_key] != NULL ||
        ascii_key++;
    }

    // ****** decide size of the hash table and then finished hashing function. Usually hash time is gonna be half full
    cout << ascii_key << endl;

    return ascii_key;
}

void insert_into_hashtable(int ascii_key, string name) {
    int k = 0;
    //get the hash key
    user * item = (user * ) malloc(sizeof(struct user));
    item - > name = name;
    item - > key = ascii_key;
    item - > FriendList = NULL;
    cout << ascii_key << endl;
    //collisions resolved by linear probing
    //store the user in the table

    hashArray[ascii_key] = item;
    k++;
    //free(item);
}

void add_friendship(int ascii_key, string name) {
    //gonna have to check for valid input on users
    list * add = (list * ) malloc(sizeof(struct friend_list));
    add - > name = name;
    add - > next = NULL;
    if (ascii_key == 13) {
        ascii_key = ascii_key;
    }
    /* if( hashArray[ascii_key]->FriendList->next == NULL )
     {
     cout<<hashArray[ascii_key]->FriendList<<endl;
     hashArray[ascii_key]->FriendList = temp;
     }
     else*/
    {
        add - > next = hashArray[ascii_key] - > FriendList;
        hashArray[ascii_key] - > FriendList = add;

    }
    free(add);
}

void print_friendships(int ascii_key) {
    friend_list * temp = (friend_list * ) malloc(sizeof(friend_list));
    temp = hashArray[ascii_key] - > FriendList;
    while (temp != NULL) {

        cout << temp - > name << endl;
        if (temp - > next == NULL) {
            free(temp);
            return;
        }
        temp = temp - > next;

    }
    //free(temp);
}

void check_friendship(int ascii_key, string name) {
    list * temp = (list * ) malloc(sizeof(struct friend_list));
    temp = hashArray[ascii_key] - > FriendList;
    while (temp != NULL) {
        if (strcmp(temp - > name.c_str(), name.c_str()) == 0) {
            cout << "Friendship exist" << endl;
            return;
        }
        temp = temp - > next;
    }
    cout << "No Record of Friendship" << endl;
    free(temp);
}

//need to finish
void remove_friendship(int ascii_key, string name) {
    list * temp = (list * ) malloc(sizeof(struct friend_list));
    list * prev = (list * ) malloc(sizeof(struct friend_list));
    temp = hashArray[ascii_key] - > FriendList;

    if (temp != NULL && temp - > name == name) {
        hashArray[ascii_key] - > FriendList = temp - > next; // Changed head
        // free old head
        return;
    }

    //not the head
    while (temp != NULL && temp - > name != name) {
        prev = temp;
        temp = temp - > next;
    }
    if (temp == NULL) return;

    // Unlink the node from linked list
    prev - > next = temp - > next;
    free(temp);
    free(prev);
}

Answer 1

Вероятно, есть много ошибок, но это большая ошибка

    user *item = (user*) malloc(sizeof(struct user));

должно быть

    user *item = new user;

В C ++ вы должны всегда использовать new,Разница между new и malloc заключается в том, что malloc не вызывает никаких конструкторов.Таким образом, в вашем user объекте конструктор для string name не вызывается.Таким образом, у вас есть неопределенное поведение (то есть потенциальные сбои) всякий раз, когда вы пытаетесь использовать name.И, как указано в комментариях, вы также должны использовать delete, а не free, в основном по той же причине.

Посмотрев немного больше на код, вы обнаружите множество ошибок, связанных с указателями.Например, как насчет этого

list* temp  = (list*)malloc(sizeof(struct friend_list));
temp = hashArray[ascii_key]->FriendList;

Забудьте немного о malloc против new, и просто посмотрите на приведенный выше код.У вас есть указатель temp, который вы указываете на некоторую выделенную память.Затем вы выбрасываете эту память и вместо нее ставите temp на hashArray[ascii_key]->FriendList.Какой смысл выделять память, если вы ею не пользуетесь?Затем вы усугубляете ошибку, освобождая память в конце функции.

free(temp);

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

Вот как вы должны написать эту функцию

void check_friendship( int ascii_key, string name)
{
    list* temp = hashArray[ascii_key]->FriendList;
    while( temp != NULL)
    {
        if(strcmp(temp->name.c_str(), name.c_str()) == 0)
        {
            cout<<"Friendship exist"<<endl;
            return;
        }
        temp = temp->next;
    }
    cout<<"No Record of Friendship"<<endl;
}

См. нет выделения вообще .Я полагаю, у вас в голове есть какое-то правило, где бы ни был указатель, я должен выделить немного памяти.Это не правда, распределение - это создание новых объектов.check_friendship не создает никаких новых объектов (он только проверяет существующие), поэтому ему не нужно ничего выделять или освобождать.

remove_friendship имеет ту же проблему, так как он удаляет дружбу, которую он долженdelete один объект (дружба удаляется), но для него нет причин выделять что-либо.

add_friendship имеет ту же ошибку, но в обратном порядке.add_friendship должен выделить один новый объект для добавляемой дружбы, вы делаете это, но затем вы пытаетесь освободить объект в конце функции.Вы действуете в соответствии с неким общим правилом, согласно которому каждая переменная-указатель должна быть выделена, а затем освобождена, вместо того, чтобы логически думать о том, какие объекты должна создавать или уничтожать каждая функция.