skip to Main Content

I made linked list with struct.
The 1st string goes well, however the 2nd one isn’t "am", but random character appears.
And 3rd and later one, the pointer is broken and this flows exception, "Segmentation fault".
Here is the code.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef struct strliststruct{
    char* string;
    unsigned long long length;
    struct strliststruct* prior;
    struct strliststruct* later;
    int exist_prior;
    int exist_later;
}strlist;

strlist init_strlist(){
    strlist ans;
    ans.exist_later=0;
    ans.exist_prior=0;
    ans.length=0;
    return ans;
}

strlist init_strlist_with_string(char* str,char splitter){
    strlist ans=init_strlist(),next;
    unsigned long long i;
    for(i=0;1;i++){
        if(str[i]==splitter){
            next=init_strlist_with_string(&str[i+1],splitter);
            ans.later=&next;
            ans.exist_later=1;
            next.exist_prior=1;
            next.prior=&ans;
        }else if(str[i]!=''){continue;}
        ans.string=malloc(sizeof(char)*(i+1));
        ans.string[i]='';
        for(unsigned long long j=0;j<i;j++){
            ans.string[j]=str[j];
        }
        break;
    }
    return ans;
}
int main(){
    strlist sl=init_strlist_with_string("I am a human",' ');
    while(1){
        printf("%sn",sl.string);
        if(sl.exist_later){sl=*sl.later;}else break;
    }
    return 0;
}

I work on Visual Studio code, and compile it with gcc.

I tried to find why does it cause with breakpoint, and found the 4th pointer is deleted on 4th "ans.string=malloc".
And 2nd and later data was destroied on "sl=sl.later".
I have no idea of solution.

2

Answers


  1. Chosen as BEST ANSWER

    I had to avoid to return local variables as pointer, which destroy after the function ended. So, instead of this, using malloc to reserve memories would be the solution. Here is the improved code.

    #include <stdlib.h>
    #include <string.h>
    #include <stdio.h>
    typedef struct strliststruct{
        char* string;
        unsigned long long length;
        struct strliststruct* prior;
        struct strliststruct* later;
        int exist_prior;
        int exist_later;
    }strlist;
    
    strlist* init_strlist(){
        strlist *ans=malloc(sizeof(strlist));
        ans->exist_later=0;
        ans->exist_prior=0;
        ans->length=0;
        return ans;
    }
    
    strlist* init_strlist_with_string(char* str,char splitter){
        strlist *ans=init_strlist(),*next;
        unsigned long long i;
        /*for(i=0;1;i++){
            if(str[i]==splitter){
                next=init_strlist_with_string(&str[i+1],splitter);
                ans->later=next;
                ans->exist_later=1;
                next->exist_prior=1;
                next->prior=ans;
            }else if(str[i]!=''){
                continue;
            }
            ans->length=j;
            ans->string=malloc(sizeof(char)*(i+1));
            ans->string[i]='';
            for(unsigned long long j=0;j<i;j++){
                ans->string[j]=str[j];
            }
            break;
        }*/
    
        unsigned long long nextspl=strchr(str,'')-str;
        if(strchr(str,splitter)){
            nextspl=strchr(str,splitter)-str;
            next=init_strlist_with_string(&str[nextspl+1],splitter);
            ans->later=next;
            ans->exist_later=1;
            next->exist_prior=1;
            next->prior=ans;
        }
        ans->length=nextspl;
        ans->string=malloc(sizeof(char)*(nextspl+1));
        memcpy(ans->string,str,nextspl);
        ans->string[nextspl]='';
    
        return ans;
    }
    int main(){
        strlist *sl=init_strlist_with_string("I am a human",' ');
        while(1){
            printf("%sn",sl->string);
            if(sl->exist_later){
                sl=sl->later;
            }else{
                break;
            }
        }
        return 0;
    }
    

  2. Well, your program fails due to the use of memory addresses that are out of scope, as you may have learned from the comments.

    I made linked list with struct. The 1st string goes well, however the 2nd one isn’t "am", but random character appears. And 3rd and later one, the pointer is broken and this flows exception, "Segmentation fault"

    IMHO here is the center issue: as you can see in any text book on data structures, a linked list is a set — pssibly empty — of nodes. The linked list is not of data. The node is not the data. The list is not a node. The node is not the list. Although is possible to mix this, and very very common, you will end up with code that is not reusable and is very hard to test and maintain.

    I will show a common way to write this kind of things, a way that can make life easier and your code reusable. And a more convenient abstraction.

    encapsulation is essential and you need a better abstraction.

    TL;DR;

    This can be a long post since I am adding comments, code and arguments. For the code you can jump to 3.2: a second example

    1: the original data

    Here is all you have in the original code:

    typedef struct strliststruct{
        char* string;
        unsigned long long length;
        struct strliststruct* prior;
        struct strliststruct* later;
        int exist_prior;
        int exist_later;
    }strlist;
    

    So this single struct is the model and is

    • the data
    • the node
    • the list

    And there is no metadata, not even the minimum: to take account of the head and the size of the list.

    2: a normal abstraction

    A linked list is just that: a list of nodes with links. There is no linked list of strings, of movies, of tickets, of musics. A node is an abstraction that points to or contains one record of data. A list is generic. Is reusable as a map, a set, a stack, an array or a dictionary are.

    2.1: the list List

    typedef struct
    {
        size_t size;
        Node*  tail;
        Node*  head;
    } List;  // a (possibly empty) list of nodes
    

    This is a possible list. It can be empty, but is has control of its size internally. Has pointers to tail and head so is is trivial to insert or extract nodes from either end. As in a queue or stack, for example. A linked list can abstract these things.

    2.2: a node Node

    typedef struct st_node
    {
        struct st_node* prev;  // links
        struct st_node* next;
    
        Info* info;  // data
    } Node;
    

    This is a possible node: the links and a pointer to a data record.

    2.3: some operations on List

    List* so_create_list();
    List* so_delete_list(List*);
    int   so_insert_back(Info*, List*);
    int   so_insert_front(Info*, List*);
    int   so_print_list(List*, const char* msg);
    

    Using encapsulation of the list and data — and operations on data — we see no mention of the data in the definition so far. This way the code will work for lists of anything, so it can be reused with no change.

    • so_insert_back(Info* info, List* list) gets a record and inserts into the list. At the back of the list
    • so_insert_front(Info* info, List* list) does he same but at the front of the list
    • so_print_list(List*, const char* msg) displays the list at the screen, and accepts an optional message.

    2.4: the data record

    typedef struct
    {
        size_t length;
        char*  string;
    } Info;
    

    This Info is the unit of data in the nodes for this particular List implementation. But each node has only a pointer to such struct.
    The operations defined below permits the list to manage nodes without knowing what they are, sort of a mediator design pattern.

    2.5: some operations on data

    Info* so_copy_info(Info*);
    Info* so_delete_info(Info*);
    Info* so_factory_info();
    int   so_print_info(Info*, const char* msg);
    

    In the example code it will become clear why these exist and how to use it. It is the same concept: encapsulation.

    • Info* so_copy_info(Info*) is called a copy constructor and get an Info and returns a copy of it.
    • Info* so_delete_info(Info*) is called a destructor and gets the adrress of a record and delete it.
    • Info* so_factory_info() is called a constructor and here is a factory function: each time it is called is returns a new Info record, with known data: "Element nnnnnn" is the string, numbered from 1 up. This way it is trivial to test for 10 or 10,000 records in the list.
    • so_print_info(Info*, const char* msg) will display the list on screen, with metadata and all records

    3: a 1st example: main1.c

    #include "stuff.h"
    
    int main(void)
    {
      List* my_list = so_create_list();
      Info* temp    = NULL;
    
      for (int i = 0; i < 3; i += 1)
      {
          temp = so_factory_info();
          so_insert_back(temp, my_list);
          free(temp);
      }
      so_print_list(my_list, "n3 elements back-insertedn");
    
      for (int i = 0; i < 3; i += 1)
      {
          temp = so_factory_info();
          so_insert_front(temp, my_list);
          free(temp);
      }
      so_print_list(
          my_list, "n3 elements inserted at frontn");
      so_delete_list(my_list);
      return 0;
    }
    

    3.1: output

        list created
    
    3 elements back-inserted
        #3 elements in list.
        head element: Element 000001
        tail element: Element 000003
        "Element 000001" [15]
        "Element 000002" [15]
        "Element 000003" [15]
    
    [-----]
    
    
    3 elements inserted at front
        #6 elements in list.
        head element: Element 000006
        tail element: Element 000003
        "Element 000006" [15]
        "Element 000005" [15]
        "Element 000004" [15]
        "Element 000001" [15]
        "Element 000002" [15]
        "Element 000003" [15]
    
    [-----]
    
        list deleted
    

    Notes:

    • Since so_factory_info() returns elements numbered the program is easy to follow: back insertion preserves the order, front insertion inverts them.
    • since head, tail and size are part of the list we can display them at printing, easily. To print a node a function is supplied with the data operations.
    • so_print_list accepts a message so we can identify the tests at the call
    • we use only pointers: no crash by freeing static data by mistake is possible.
    • data is encapsulated inside list and nodes
    • operations are defined in advance
    • SRP — single responsibility principle — is used in the operations so each function does a minimum and most have no more than a dozen lines
    • all data inside the list is owned by the list, so data is independent from the input
    • operations on data use sort of a mediator pattern. AS an example, to insert data in the list a function is supplied for this use, so the list does not manipulate the data in the nodes directly

    3.2: a second example, using the idea in the original code: main2.c

    #include "stuff.h"
    
    //
    // helpers to build a list
    //
    int so_line_insert(
      const char* string, const char delim, List* list);
    int so_multi_insert(
      List* list, const char delim, const unsigned N, ...);
    
    int main(void)
    {   // now test the multi insert
      List* my_list = so_create_list();  // a new list
      so_multi_insert(
          my_list, ' ', 4, "1 2 3 4",
          "              5           6         7         8 ",
          "9 10 11 12", "I am a human");
      so_print_list(my_list, "nafter multi insertn");
      so_delete_list(my_list);
      return 0;
    }
    
    //
    // helper functions:
    //
    
    #define ST_OUT 0
    #define ST_IN 1
    #define MAX_SIZE 255
    
    //
    // insert string into list, word by word
    //
    
    int so_line_insert(
      const char* string, const char delim, List* list)
    {
      if (list == NULL) return -1;
    
      char state                = ST_OUT;
      char a_word[1 + MAX_SIZE] = {0};  // buffer for word
      Info data   = {.length = 0, .string = (char*)&a_word};
      data.length = 0;
      Info* temp  = NULL;
      // break string into words and put on list
      const char* p_in  = string;
      char*       p_out = data.string;
      while (*p_in != 0)
      {
          switch (state)
          {
              case ST_OUT:  // out of word
                  if (*p_in == delim)
                  {  // not in word
                      ++p_in;
                  }
                  else
                  {  // new word starting here
                      p_out       = data.string;
                      *p_out      = *p_in;
                      state       = ST_IN;
                      data.length = 1;
                      ++p_in;
                      ++p_out;
                  }
                  break;
              case ST_IN:  // in a word
              default:     // in a word
                  if (*p_in == delim)
                  {                // end of word
                      *p_out = 0;  // end string
                      temp   = so_copy_info(&data);
                      so_insert_back(temp, list);
                      free(temp);
                      state =
                          ST_OUT;  // in search for another
                      ++p_in;
                  }
                  else
                  {  // just another letter
                      *p_out = *p_in;
                      data.length += 1;
                      ++p_in;
                      ++p_out;
                  }
                  break;
          };  // switch(state)
      };      // while()
      // now *p_in == 0, end of line
      if (state == ST_OUT) return 0;
      // state was ST_IN and reached end of input
      if (p_out == data.string) return 0;  // was empty
      // inserts last word into list
      *p_out = 0;
      temp   = so_copy_info(&data);
      so_insert_back(temp, list);
      free(temp);
      return 0;
    }
    
    int so_multi_insert(
      List* list, const char delim, const unsigned N, ...)
    {
      if (list == NULL) return -1;
      va_list args;
      va_start(args, N);
      for (size_t i = 0; i < N; i += 1)
          so_line_insert(va_arg(args, char*), ' ', list);
      va_end(args);
      return 0;
    }
    

    Again the code is simple:

    • so_line_insert( const char* string, const char delim, List* list) does the expected: gets a string and a delimiter and parse the string into words and inserts them into the list.
    • so_multi_insert(List* list, const char delim, const unsigned N, ...) uses the function above and inserts all lines into the list

    3.4: parsing the line

    Instead of using library functions like strchr or sscanf a minimalist state machine with 2 states are used to parse the line, extract the words and insert into the list. Is is the only function in the example with more than 20 lines of code but has less than 40. It is a single loop with a switch, a classic FSM.

    3.4: output of the 2nd example

        list created
    
    after multi insert
      #16 elements in list.
      head element: 1
      tail element: human
      "1" [1]
      "2" [1]
      "3" [1]
      "4" [1]
      "5" [1]
      "6" [1]
      "7" [1]
      "8" [1]
      "9" [1]
      "10" [2]
      "11" [2]
      "12" [2]
      "I" [1]
      "am" [2]
      "a" [1]
      "human" [5]
    
    [-----]
    
      list deleted
    

    Here some tests are run with the delimiters in many positions and then the example string is inserted also (see the code above).

    4: The data, node and list example implementation

    4.1: header file stuff.h

    #include <stdarg.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    // info, node and list
    
    typedef struct
    {
        size_t length;
        char*  string;
    } Info;
    
    Info* so_copy_info(Info*);
    Info* so_delete_info(Info*);
    Info* so_factory_info();
    int   so_print_info(Info*, const char* msg);
    
    typedef struct st_node
    {
        struct st_node* prev;  // links
        struct st_node* next;
    
        Info* info;  // data
    } Node;
    
    typedef struct
    {
        size_t size;
        Node*  tail;
        Node*  head;
    } List;  // a (possibly empty) list of nodes
    
    List* so_create_list();
    List* so_delete_list(List*);
    int   so_insert_back(Info*, List*);
    int   so_insert_front(Info*, List*);
    int   so_print_list(List*, const char* msg);
    

    4.2: a possible implementation stuff.c

    #include "stuff.h"
    
    
    // data related functions
    
    Info* so_copy_info(Info* orig)
    {
        if (orig == NULL) return NULL;
        Info* cp = malloc(sizeof(Info));
        if (cp == NULL) return NULL;
        cp->string = malloc(1 + orig->length);
        if (cp->string == NULL)
        {
            free(cp);
            return NULL;
        }
        strcpy(cp->string, orig->string);
        cp->length = orig->length;
        return cp;  // returns the address of the copy
    }
    
    Info* so_delete_info(Info* del)
    {
        if (del == NULL) return NULL;
        if (del->string != NULL) free(del->string);
        free(del);
        return NULL;
    }
    
    Info* so_factory_info()
    {
        Info* one = malloc(sizeof(Info));
        if (one == NULL) return NULL;
        static int len = 1;
        one->string    = malloc(30);
        one->length =
            1 + sprintf(one->string, "Element %06d", len);
        ++len;
        return one;
    }
    
    int so_print_info(Info* info, const char* msg)
    {
        if (info == NULL) return -1;
        if (msg != NULL) printf("%s", msg);
        printf(
            "    "%s" [%llu]n", info->string, info->length);
        return 0;
    }
    
    // list related functions
    
    List* so_create_list()
    {
        List* list = malloc(sizeof(List));
        if (list == NULL) return NULL;
        list->head = NULL;
        list->tail = NULL;
        list->size = 0;
        fprintf(stderr, "    list createdn");
        return list;
    }
    
    List* so_delete_list(List* del)
    {
        if (del == NULL) return NULL;  // no list
        for (size_t i = 0; i < del->size; i += 1)
        {  // delete nodes, 1 by 1
            Node* save = del->head->next;
            so_delete_info(del->head->info);
            free(del->head);
            del->head = save;
        };
        free(del);  // delete list
        fprintf(stderr, "    list deletedn");
        return NULL;
    }
    
    // inserts 'info' at the tail of the list
    int so_insert_back(Info* info, List* list)
    {
        if (list == NULL) return -1;  // no list
        Node* node = (Node*)malloc(sizeof(Node));
        if (node == NULL) return -2;  // no alloc
        node->info = so_copy_info(info);
        if (list->size == 0)  // first node
        {
            node->next = NULL;
            list->size = 1;
            list->head = node;
            list->tail = node;
            return 0;  // 1st node
        };
        node->next       = NULL;
        list->tail->next = node;
        list->tail       = node;
        list->size += 1;
        return 0;
    }
    
    // inserts 'info' at the head of the list
    int so_insert_front(Info* info, List* list)
    {
        if (list == NULL) return -1;  // no list
        Node* node = (Node*)malloc(sizeof(Node));
        if (node == NULL) return -2;  // no alloc
        node->info = so_copy_info(info);
        if (list->size == 0)
        {
            node->next = NULL;
            list->size = 1;
            list->head = node;
            list->tail = node;
            return 0;  // 1st node
        };
        node->next = list->head;
        list->head = node;
        list->size += 1;
        return 0;
    }
    
    int so_print_list(List* list, const char* msg)
    {
        if (list == NULL)
        {
            printf("No valid list!n");
            return 0;
        }
        if (list->size == 0)
        {
            printf("list is emptyn");
            return 0;
        }
        if (msg != NULL) printf("%s", msg);
        printf(
            "
        #%llu elements in list.n
        head element: %sn
        tail element: %sn",
            list->size, list->head->info->string,
            list->tail->info->string);
        Node* p = list->head;
        for (size_t i = 0; i < list->size; i += 1)
        {
            so_print_info(p->info, NULL);
            p = p->next;
        }
        printf("n[-----]nn");
        return 0;
    }
    

    Conclusion

    This is a long post, I was coding along. It is just a mock up to show some possible uses.

    But is almost a generic list, easily expandable.

    To use just copy header and implementation and add code for main.

    HIH

    Login or Signup to reply.
Please signup or login to give your own answer.
Back To Top
Search