code to copy contents of linked list into a character array-CodePudding

I have an assignment where I need to create a linked list, where each node has a string length of 1. I must then make a function that computes a string representing the contents of the linked list. the string should have a space in-between each node contents, but shouldn't have a space at the end. in this example each node has a letter and the output should look like this "A B C D....Z" (no space after Z). the function must have a prototype of

void concat_nodes(struct strnode * head, char * str);

all the function in my code are working I believe except for the concat nodes function, it doesn't seem to copy the data into the string. I believe the logic is correct and I think there's a syntax error somewhere. if someone can point me in the right direction I would greatly appreciate

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

// structure defintion

struct strnode{
    struct strnode *front;
    int data;
    struct strnode *next;
 };

void list_destroy(struct strnode *head);
 
void push(struct strnode *head, char value);

void concat_nodes(struct strnode *head,char * str);

// counter to keep track of length of linked list

int counter1 = 0;

struct strnode *make_list();



int main(){
struct strnode *head = make_list();

// for loop to add each letter to list 
   for(int i=65; i<=90;i  ){
     push(head,i);
     counter1  ;
   }

// array length must account for every letter plus spaces inbetween   
char alph[(counter1*2)-2];
scanf("%s",alph);


concat_nodes(head,alph);

//this for loop should print the array but nothing gets printed

     for(int j=0; j<50; j  ){
  printf("%c",alph[j]);
    }

// but the program doesnt fail which should mean this assert test passed right?    

assert(strcmp(alph,"A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ")==0);

list_destroy(head);

}

// function to create linked list

struct strnode *make_list(){
   struct strnode *head = malloc(sizeof(struct strnode));
   head->front = NULL;
   return head;
   counter1  ;
 }

// function to add to list

void push(struct strnode *head, char value){
  struct strnode  *new_node = malloc(sizeof(struct strnode));
  new_node->data = value;
  new_node->next = head->front;
  head->front = new_node;
  
  
}

// function that takes front of list and char array as arguements and copies the values stored in each node into array along with spaces inbetween
void concat_nodes(struct strnode *head,char * str){
strlen(str) == ((counter1*2)-2);
struct strnode *node = head->front;
int counter = 0;
    while(node){
    node->data = str[counter];
    counter  ;
    str[counter 1]=' ';
    printf("%c",str[counter]);
    counter  ;
    node = node->next;
    }

}

// function to free list
void list_destroy(struct strnode *head){
  struct strnode *curnode = head->front;
  struct strnode  *nextnode = NULL;
  while(curnode){
    nextnode = curnode->next;
    free(curnode);
    curnode = nextnode;
  }
  free(head);
}

CodePudding user response：

Initial Thoughts

There is no need to use a double-linked list (e.g. two node pointers front and next), your push() function fails to set new_node->front making the pointer to the previous node worthless. Just use a singly-linked list with a ->next pointer.
There is no need to allocate head before you add (push) your first node to the list. Simply initialize head to NULL.
char alph[(counter1*2)-2]; is too-short by 2 to hold 'A'-'Z' with a separator in between each character as a C-string with the nul-terminating character at the end. (too short by 3 if you add the superfluous space after 'Z' as shown in your example) You know how many letters are in the alphabet, just #define ABETSZ 26 and then declare char alph[ABETSZ * 2] = ""; (initialized all zero to provide the nul-terminating character through initialization).
Your ->next pointer doesn't point to head->front (which you set NULL) it simply points to head (the node itself). You are using a method called Forward-Chaning to add nodes to the list.
Because you have used Forward-Chaning, the elements of your list will be in the reverse-order they were pushed to the list. Ideally, you would keep both a head and tail pointer (which points to the last node in your list) so you can do an in-order add of elements to your list in (0)N time ¹ (but one step at a time).
To add the nodes, in-order, you simply iterate to the last node in your list and add the last node there (with node->next initialized NULL so you know where the end of the list is)
I have no idea what strlen(str) == ((counter1*2)-2); is in concat_nodes().
Avoid the use of global variables (counter1, head, alph, etc..). Declare the variables in the scope needed and pass the variables (or a pointer to them) as a parameter to any function that needs them.
int data; will work fine if you are only storing a character as the data in each node and not a 2-character string as your question states. If that is required char data[2]; will suffice (and yes, you can hack an int into holding a 2-character string, but addressing the strict-aliasing rule and pitfalls of endianness is for another day).
Avoid using MagicNumbers. 'A' is more readable than 65 and 'Z' is more readable than 90.

With that in mind, simply declare your struct nodestr with a single next pointer and use a typedef to avoid having to write struct where the type is required, e.g.

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

#define ABETSZ 26

typedef struct strnode {     /* list node */
    int data;
    struct strnode *next;
} strnode;

Your add function (add() below, your push()) simply needs to preserve the order of the input. As mentioned above, just iterate to the end and add the new node there. (also note the use of a tail pointer avoids the need to iterate to the end on each addition). A simple add() for in-order insertion (not sort-order, just in the same order you add to the list) can be:

/** add node at end of list */
strnode *add (strnode **head, int v)
{
    strnode **ppn = head,                   /* pointer to pointer to head */
            *pn = *head,                    /* pointer to head */
            *node = malloc (sizeof *node);  /* allocate new node */

    if (!node) {                            /* validate allocation */
        perror ("malloc-node");
        return NULL;
    }
    node->data = v;                         /* initialize members values */
    node->next = NULL;

    while (pn) {                            /* iterate to end of list */
        ppn = &pn->next;                    /* with address of node */
        pn = pn->next;                      /* and pointer to node */
    }

    return *ppn = node;    /* add & return new node */
}

(note: the function takes the address of your list pointer as a parameter so the address held by the original list pointer can be changed (by malloc()) within the function and not be lost on function return)

By iterating with the address of the node (pointer-to-pointer to node ppn) in addition to the pointer to node (pn) when the iteration is done, you have the address of the node (where NULL is currently stored) to know where to add the new node. (without using the address of the node, you have to keep track of the previous and current nodes in order to set the new node at previous->next). See Linus on Understanding Pointers

The only other list function you need is a function to free all memory allocated to the list. That can be a simple as the following and there is no need to pass the address of your list pointer as a parameter, there won't be any list after the function is called.

/** delete all nodes in list */
void del_list (strnode *l)
{
    strnode *n = l;
    while (n) {
        strnode *victim = n;
        n = n->next;
        free (victim);
    }
}

Your concat_nodes() function should take a list pointer (can be const you are not changing any of the nodes), a pointer to the string to fill, and you may as well pass the separator character to use to make it reusable for something other than a space, and finally since you are filling a character string, you should pass the size of the string so you can protect your array bounds while you fill the string. You can do that with something like:

/** create string from chars in list separated by sep
 *  if sep > 0. (add ASCII validation if desired)
 */
void makestr (const strnode *n, char *str, char sep, size_t size)
{
    size_t ndx = 0;

    /* loop over each node in list */
    for (; n->next && ndx < size - 1; n = n->next) {
      if (sep && ndx) {         /* if sep nonzero and not 1st char */
        str[ndx  ] = sep;       /* add sep to string */
      }
      str[ndx  ] = n->data;     /* add data char to string */
    }

    str[ndx] = 0;               /* nul-terminate */
}

(note: since data is type int, you will want to check that it is in the range of an ASCII character (or at least unsigned char) to prevent undefined behavior. Since 'A'-'Z' are the only values added, that is left to you for the general case)

A short example program that fills the list with uppercase characters of the alphabet and uses the separator passed as the first character to your program (' ' space if no argument is provided) can be done similar to:

int main (int argc, char **argv) {

    char sep = argc > 1 ? *argv[1] : ' ', /* separator character for string */
         str[ABETSZ * 2] = "";            /* storage for final string */
    strnode *list = NULL;                 /* list pointer */

    for (int i = 'A'; i <= 'Z'; i  ) {    /* add uppercase chars to list */
      add (&list, i);
    }
    makestr (list, str, sep, ABETSZ * 2); /* fill string from list */

    del_list (list);                      /* free all allocated memory */

    puts (str);                           /* output string */
}

(note: that is the complete program above, just put it altogether in a single file, in the order shown above)

Example Use/Output

With no argument provided using the default ' ' (space) separator:

$ ./bin/lls-alphabet
A B C D E F G H I J K L M N O P Q R S T U V W X Y

Using a hyphen as a separator:

$ ./bin/lls-alphabet "-"
A-B-C-D-E-F-G-H-I-J-K-L-M-N-O-P-Q-R-S-T-U-V-W-X-Y

Or no separator at all, e.g.

$ ./bin/lls-alphabet ""
ABCDEFGHIJKLMNOPQRSTUVWXY

Memory Use/Error Check

In any code you write that dynamically allocates memory, you have 2 responsibilities regarding any block of memory allocated: (1) always preserve a pointer to the starting address for the block of memory so, (2) it can be freed when it is no longer needed.

It is imperative that you use a memory error checking program to ensure you do not attempt to access memory or write beyond/outside the bounds of your allocated block, attempt to read or base a conditional jump on an uninitialized value, and finally, to confirm that you free all the memory you have allocated.

For Linux valgrind is the normal choice. There are similar memory checkers for every platform. They are all simple to use, just run your program through it.

$ valgrind ./bin/lls-alphabet
==8844== Memcheck, a memory error detector
==8844== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==8844== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==8844== Command: ./bin/lls-alphabet
==8844==
A B C D E F G H I J K L M N O P Q R S T U V W X Y
==8844==
==8844== HEAP SUMMARY:
==8844==     in use at exit: 0 bytes in 0 blocks
==8844==   total heap usage: 27 allocs, 27 frees, 1,440 bytes allocated
==8844==
==8844== All heap blocks were freed -- no leaks are possible
==8844==
==8844== For lists of detected and suppressed errors, rerun with: -s
==8844== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Always confirm that you have freed all memory you have allocated and that there are no memory errors.

Footnotes:

Example Using Both head And tail Pointer

CodePudding user response：

I copied in your code and tried it out. After using inserted "printf" statements to zero in on various issues causing program dumps, I did a bit of cleanup and revised the code such that it passes the "assert" test. Following is a copy of the revised code.

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

// structure defintion

struct strnode
{
    struct strnode *front;
    char data;              /* Since the program is dealing with characters use a character data element */
    struct strnode *next;
};

void list_destroy(struct strnode *head);

struct strnode * push(struct strnode *head, int value);

void concat_nodes(struct strnode *head, char * str);

void list_node(struct strnode *head);

// counter to keep track of length of linked list

int counter1 = 0;

struct strnode *make_list();

int main()
{
    struct strnode *head = make_list();

// for loop to add each letter to list
struct strnode *work = head;
    for(int i=(int)'B'; i<=(int)'Z'; i  )   /* Remove reference to "magic numbers" - use character values instead */
    {
        work = push(work,i);
        counter1  ;
    }

// array length must account for every letter plus spaces inbetween

    char alph[(counter1*2) 2];

    concat_nodes(head, alph);

    printf("Alph: %s\n", alph);

//this for loop should print the array but nothing gets printed

    for(int j=0; j<52; j  )
    {
        printf("%c",alph[j]);
    }
    printf("\n");

// but the program doesnt fail which should mean this assert test passed right?

    assert(strcmp(alph,"A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ")==0);

    list_destroy(head);

    return 0;
}

// function to create linked list

struct strnode *make_list()
{
    struct strnode *head = malloc(sizeof(struct strnode));
    head->front = NULL;
    head->data  = 'A';      /* Since this is the first node, set it up with the initial character 'A' */
    head->next  = NULL;
    counter1  ;
    return head;
}

// function to add to list

struct strnode * push(struct strnode *head, int value)
{
    struct strnode  *new_node = malloc(sizeof(struct strnode));
    head->next = new_node;          /* Revise setup of node chain population */
    new_node->data  =(char)value;
    new_node->front = head;
    new_node->next  = NULL;

    return new_node;
}

// function that takes front of list and char array as arguements and copies the values stored in each node into array along with spaces inbetween
void concat_nodes(struct strnode *head, char * str)
{

    struct strnode *node = head;
    int counter = 0;

    for (int i = 0; i < (int)strlen(str); i  )
    {
        str[i] = 0;
    }

    while(node)
    {
        str[counter] = node->data;      /* Cleaned up the index incrementing to avoid extra skips for character and space insertion */
        counter  ;
        str[counter]=' ';
        counter  ;
        node = node->next;
    }
    str[counter] = '\0';

    return;
}

// function to free list
void list_destroy(struct strnode *head)
{
    struct strnode *curnode = head;
    struct strnode *nextnode = NULL;

    while(curnode)
    {
        nextnode = curnode->next;
        free(curnode);
        curnode = nextnode;
    }
}

Following are some of the key bits of the cleanup.

Since this program is dealing with character placement, the "data" element in the structure was changed from and "int" to a "char" (very minor but reflects what the program is doing).
The initial node was not getting a character assigned, so that was revised in the making of the initial node.
In the creation of the additional nodes, the initial (head) node was always being referenced when calling the "push_node" function, so there was only a link between the initial node and the last node created. So the creation loop was revised to make sure a proper linked list was being created.
In the "concat_nodes" function, the statement "str[counter 1] = ' '" was changed to "str[counter] = ' '" as the counter had already been incremented prior this statement being executed.

There probably were some more minor tweaks but those were the significant ones. When I did a test run of the code the program passed the assertion test.

@Una:~/C_Programs/Console/Concatenation/bin/Release$ ./Concatenation 
Alph: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Fundamentally, most bits were sound. There just needed to be a proper setup of the linked list and proper identification as to which character position was to store a character and which character position was to store a blank.

Give that a try.