programme not responding

[general2012]

please help .i have written this programme just to enter data to a linked list.but it isnt working.cant understand where the problem is.how can i make this work and how can i make this programme evev better

#include<stdio.h>
#include<stdlib.h>
#define NULL 0
 struct linked{

        char data[20];
         struct linked *next; //pointer to next node
        };

typedef struct linked node;
node *record;
void choice(int );  // function protoypes
void enter(node *);
void delete(node *);
void display(node *);    

int main()
{
    int n;

    node s;
    record=&s;
    printf("enter choice");
    scanf("%d",&n);
    choice(n);
    getch();
}


void choice(int n)
{

     do{
              switch(n){
               case 1:
                    record=(node *)malloc(sizeof(node));
                    enter(record);
                    break;
               default:
                       printf("try again");

                    }
                    }
           while(1); 
                    }


void  enter(node *first)
{
      printf(" enter data");
      printf("tupe END if finished");
     scanf("%[^\n]",first->data);
     if(strcmp(first->data,"END"))
            first->next=NULL;
     else 
       first->next=(node *)malloc(sizeof(node));
       enter(first->next);
       }

[Gonbe]

There's multiple things I'd change. First of all you're asking for input outside of the do-while loop you have in "choice". The user won't get the chance to re-enter input. I've moved that inside it.

Then, the head of your linked list is created on the stack in main, while you (attempt to) create the rest on the heap. You should make everything on the heap to keep things consistent for when you want to free stuff. You do later malloc a node and assign that to the head. I've removed the one in main.

You don't describe what you want your application to do.. So I am making assumptions here. I think you only want to loop asking for input as long as the user doesn't select option 1? And once that option is chosen the "enter" function asks all input after which the application finishes?

The enter function is a mess, so i've modified it based on the above..

The "not responding" part probably happens due to the scanset you are using in the second scanf. The first one reads an integer and will leave a newline, which is exactly what the scanset of the second scanf looks for. Add a space at the start of the format string to skip whitespaces at the beginning. (assuming this is okay for your program, you should have been more detailed if not..)

Results in:

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

// Includes the NULL character.
#define DATA_SIZE (20)

struct linked
{
    char data[DATA_SIZE];
    struct linked *next;
};

typedef struct linked node;

void choice (node** const list);
void enter  (node** const list);
void addNode(node** const list, const char data[]);

int main()
{
    node *list = NULL;
    node *listItem = NULL;
    int i;

    choice(&list);

    // Little test. Just show all linked list contents.
    printf("Linked list contents:\n\n");

    for (listItem = list, i = 1; listItem != NULL; listItem = listItem->next, i++)
    {
        printf("%d. \"%s\"\n", i, listItem->data);
    }

    // Freeing etc here. Yes, I am lazy..

    return 0;
}


void choice(node** const list)
{
    int n;

    do
    {
        printf("Enter choice: ");
        fflush(stdout);

        scanf("%d",&n);

        switch(n)
        {
            case 1:
                enter(list);
                break;

            default:
                printf("Try again.\n");
        }
    }
    while(n != 1);
}


void enter(node** const list)
{
    char entered[DATA_SIZE] = { '\0' };
    printf("Enter the data. Type END if finished.\n");

    scanf(" %[^\n]", entered);
    while (strcmp(entered,"END") != 0)
    {
       addNode(list, entered);
       scanf(" %[^\n]", entered);
    }
}

// Function to add a node to the linked list. data must be a C-string.
void addNode(node** const list, const char data[])
{
    // The list is empty.
    if ((*list) == NULL)
    {
        (*list) = (node*) malloc (sizeof(node));
        (*list)->next = NULL;
        strncpy((*list)->data, data, DATA_SIZE);
    }
    else
    {
        addNode(&((*list)->next), data);
    }
}

could be improved but I don't think there's a point to add more complexity at this point.

[general2012]

thanx.but can you tell why you used a double pointer here ???

[Gonbe]

Because you want the pointer address to change if something was added. Say you have your list and it is empty. This means the pointer is NULL. After calling the "addNode" function it adds a node to it and you'll want the pointer you passed to the function to be the address of that node.

-edit-

Say your function was this:

// Function to add a node to the linked list. data must be a C-string.
void addNode(node* list, const char data[])
{
    // The list is empty.
    if (list == NULL)
    {
        list = (node*) malloc (sizeof(node));
        list->next = NULL;
        strncpy(list->data, data, DATA_SIZE);
    }
    else
    {
        addNode(list->next, data);
    }
}

And you'd call it like:

node* list = NULL;
addNode(list, "hello");

// What would 'list' be now?

[general2012]

What would 'list' be now?

sorry i didnt understand what are you trying to say.
is it for because in your code you wanted to print the list in main function???

[Gonbe]

What I am trying to say is that "list" would still be NULL after adding the node "hello" in the last example. It's because the pointer is passed by value and not by reference. You could see the "double pointer" as a reference of a pointer if that makes it easier.

A small example:

#include <stdio.h>

typedef int* IntPtr;

void ChangePointerByValue (IntPtr value)
{
    // Random value, just as a test.
    value = 0xCAFEBABE;
}

void ChangePointerByReference (IntPtr* value)
{
    (*value) = 0xCAFEBABE;
}

int main(void)
{
    IntPtr pointer = NULL;
    printf("Pointer is: %p.\n", pointer);

    ChangePointerByValue(pointer);
    printf("Pointer is: %p.\n", pointer);

    ChangePointerByReference(&pointer);
    printf("Pointer is: %p.\n", pointer);

    return 0;
}

This will result in something like:

Pointer is: 00000000.
Pointer is: 00000000.
Pointer is: CAFEBABE.

The pointer to a pointer is basically the same without a typedef. So I could have written the above like this:

#include <stdio.h>

void ChangePointerByValue (int* value)
{
    // Random value, just as a test.
    value = 0xCAFEBABE;
}

void ChangePointerByReference (int** value)
{
    (*value) = 0xCAFEBABE;
}

int main(void)
{
    int* pointer = NULL;
    printf("Pointer is: %p.\n", pointer);

    ChangePointerByValue(pointer);
    printf("Pointer is: %p.\n", pointer);

    ChangePointerByReference(&pointer);
    printf("Pointer is: %p.\n", pointer);

    return 0;
}

When you pass a parameter by value it's value is copied and changes made to the function parameter within the function will remain local; they do not modify the parameter supplied to the function. A call by reference (although not really a reference, it's a pointer but the term is used widely) will pass the memory address of a parameter meaning that if a function dereferences the pointer it will access the variable passed to the function.

I'm not sure if this is clear; if anything is unclear let me know and I'll try to elaborate on it.

[general2012]

ok i undersa=tand your point .but

void ChangePointerByReference (IntPtr* value)

this means the function will exept a pointer and it is a IntPtr type.can you tell me how it is equivalent to a double pointer ???

[deceptikon]

this means the function will exept a pointer and it is a IntPtr type.can you tell me how it is equivalent to a double pointer ???

IntPtr is defined as

typedef int* IntPtr;

The second asterisk is hidden by the typedef, so IntPtr* becomes int** when evaluated. Your confusion on the matter is precisely why I generally recommend against hiding levels of indirection with a typedef.

[general2012]

thanx a lot

void enter(node** const list)

anyone can explain to me why const is needed here???

[deceptikon]

anyone can explain to me why const is needed here???

It's not needed, but if the function shouldn't reseat the pointer then adding const to enforce that behavior isn't a bad thing. Generally const is there to keep you as the programmer from doing something stupid. It's hard to remember the intended limitations of every object your code uses. ;)

[Gonbe]

If the double pointer thing confuses you too much you could also go for a different solution. For example, you could make the functions return the new version of a supplied list. Calls would then typically look something like:

list = DoSomethingWithList(list);

When applied to your code you get something like this:

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

// Includes the NULL character.
#define DATA_SIZE (20)

struct linked
{
    char data[DATA_SIZE];
    struct linked *next;
};

typedef struct linked node;

node* choice (node* list);
node* enter  (node* list);
node* addNode(node* list, const char data[]);

int main()
{
    node *list = NULL;
    node *listItem = NULL;
    int i;

    list = choice(list);

    // Little test. Just show all linked list contents.
    printf("Linked list contents:\n\n");

    for (listItem = list, i = 1; listItem != NULL; listItem = listItem->next, i++)
    {
        printf("%d. \"%s\"\n", i, listItem->data);
    }

    // Freeing etc here. Yes, I am lazy..

    return 0;
}


node* choice(node* list)
{
    int n;

    do
    {
        printf("Enter choice: ");
        fflush(stdout);

        scanf("%d",&n);

        switch(n)
        {
            case 1:
                list = enter(list);
                break;

            default:
                printf("Try again.\n");
        }
    }
    while(n != 1);

    return list;
}


node* enter(node* list)
{
    char entered[DATA_SIZE] = { '\0' };
    printf("Enter the data. Type END if finished.\n");

    scanf(" %[^\n]", entered);
    while (strcmp(entered,"END") != 0)
    {
       list = addNode(list, entered);
       scanf(" %[^\n]", entered);
    }

    return list;
}

node* addNode(node* list, const char data[])
{
    // The supplied list is empty. This means this is where our new node belongs.
    if (list == NULL)
    {
        // Allocate the new node.
        list = (node*) malloc (sizeof(node));

        // Set the fields of the node.
        list->next = NULL;
        strncpy(list->data, data, DATA_SIZE);
    }
    // We received a list of atleast 1 node. Add a new node to the remaining section of the list in a recursive manner.
    else
    {
        list->next = addNode(list->next, data);
    }

    // The result of the function is the new list which now contains the new node.
    return list;
}

[general2012]

thanx again.but this means the pointer address is constant

void enter(node** const list)

if this pointer adress is const ,
then how can we assaign different address to it each time we call addnode()???

[Gonbe]

It means list itself may not be changed, but we can change (*list). If it was a const node** then way may not modify (*list) because that would be const. (but we would then be allowed to change list because it's not longer const. Then we'd need const node** const)

[general2012]

its clear now.but i tried your code,it ended up in inputting continous string ,not asking for input choice and no display for the input??

[Gonbe]

What compiler did you use and did you change anything? When my code is run it should result in something like the following. (The bold sections are user-input)

Enter choice: 1
Enter the data. Type END if finished.
Hello
World
This is text spread
across multiple
lines!
END
Linked list contents:

1. "Hello"
2. "World"
3. "This is text spread"
4. "across multiple"
5. "lines!"

[general2012]

thanx a lot .i forgot about the "END" thing.another thing is

• after first list input it will put list->next to null.
• and then it is rturned by(return list;)
• and in the main the for loop will be encountered
• and list->next will be null and data will be assigned to it and it will return and so on

*as list is returning everytime from called functions.it should be asking for input choice each time and every time after list data is inserted it will return to main,the code looks like this but why its not doing as listhis ??

[Gonbe]

I'm not realy sure what you mean and what code you are referring to. (I assume you are referring to the code where I replaced the "double pointer" with a return system) Are you asking of an explaination of how that code works, or are you looking for a way to modify the code as a whole to work differently?

[general2012]

actually i am loooking for an explanation of that last code of yours so that i can have a better understanding.after the first list is encountered where the return statement will take it?can you explain it for the first and subsequent list->next.i want to know how the retunt statement is working here??

[Gonbe]

Okay, clear. I'll start with explaining the idea of the function first. It's prototype is as follows:

node* addNode(node* list, const char data[])

We give it a linked list 'list' and data 'data' and the function will result in a new list which is the old list to which 'data' is added at the end.

I have implemented this as a recursive function meaning you express a problem using smaller cases of that problem and this continues until a simple base case is reached. The base case here is receiving an empty list. This means 'list' is NULL. So, we receive an empty list and data. Then what should we result in? We should then result in a list consisting of 1 node: the node that has 'data'. This is done in the following code:

    // The base case. We received an empty list to which we have to add a node.
    if (list == NULL)
    {
        // Allocate the new node.
        list = (node*) malloc (sizeof(node));

        // Set the fields of the node.
        list->next = NULL;
        strncpy(list->data, data, DATA_SIZE);
    }

The result it the address of this new node because this node is now the head of our list.

Then, the non-base case. This would be when we receive a list of size 1 or bigger. The question here would be: How can we reduce this to a smaller version of the problem? Well, a linked list is nothing more than a chain of nodes. Every sub chain is in itself also a linked list. This means we could define adding a node to a list that is not empty as adding it to "the rest" of the list because this in itself is a linked list. This is done in the following code:

// Adding a node to a list of size 1 or more: Add the list to the tail of 'list'.
list->next = addNode(list->next, data);

The result of this function is 'list'.

It's often easier to understand recursive functions on a abstract level than to attempt to understand them by following the recursive calls.

You did however request an example for the first 2 additions, so let's start with that. Say we have an empty list like:

node* list = NULL;

Then we want to add a node to the list so we call our function:

addNode(list, "a");

Because the list is empty, the base case is performed. So, this code:

 // The base case. We received an empty list to which we have to add a node.
 if (list == NULL)
 {
     // Allocate the new node.
     list = (node*) malloc (sizeof(node));

     // Set the fields of the node.
     list->next = NULL;
     strncpy(list->data, data, DATA_SIZE);
 }

At the end of this, 'list' will have the memory address returned by malloc. For example purposes let's say this is "0x1234". So, our current situation is as follows:

• list is 0x1234
• list contains 1 node (address 0x1234) and this node has the value "a".

Now, we want to add another item to this list. So we call our function again:

addNode(list, "b");

This time, 'list' is not empty so the recursive case is called. This means this code is called:

list->next = addNode(list->next, data);

We call addNode with list->next and our data.list->next will be NULL because our list only contained 1 item. So, what is the result of this call? Well this situation is basically the same as our first addition to the list: the base case is executed. This means the function results in the address of our new node. (our new sublist) Say that this is 0x9876. We then assign this value in our initial addNode call to list->next. This means 'list' is as follows:

    list:       0x1234
    list->next: 0x9876
    list->data: "a"

We are now done and we return our list. This means our list address in 'main' is unaltered as this was already 0x1234, but the list itself HAS changed because it now has 2 nodes instead of 1. (list->next used to be NULL but it is now 0x9876)

The key here is understanding that adding a node to a non-empty list at the end is the same as adding a node to the tail of an empty list at the end.

I hope this is clear!

[Gonbe]

I think your problem lies within understanding recursion. Maybe you should look at simple recursion first to get a feel for it. For example:

#include <stdio.h>

// This function returns (n + amount) by using a recursive solution.
// For this example 'amount' must be >= 0.
int add(const int n, const int amount)
{
    // Base case: Adding 0 to n.
    if (amount == 0)
    {
        // This is ofcourse n itself!
        return n;
    }
    // Recursive case: Adding something bigger than 0 to n.
    else
    {
        // This is the same as 1 plus the result of adding n and amount - 1.
        return 1 + add(n, amount - 1);
    }
}

int main(void)
{
    printf("%d\n", add(20,34));
    return 0;
}

I could also create a non-recursive solution by the way if this works better for you.

[deceptikon]

I think your problem lies within understanding recursion

Or just don't use recursion. Honestly, I think that's the better choice for a linked list because the risk of stack overflow is greater when the recursive growth is linear or worse. Also, the iterative form of linked list appending isn't more complex:

node *addNode(node *list, const char data[])
{
    node *temp = malloc(sizeof *temp);

    if (temp) {
        temp->next = NULL;
        temp->data[0] = '\0';
        strncat(temp->data, data, DATA_SIZE);

        if (!list)
            list = temp; // Special case for an empty list
        else {
            struct node *it = list;

            // Find the end of the list
            while (it->next)
                it = it->next;

            it->next = temp;
        }
    }

    return list;
}

There are a couple of things to note over the recursive implementation that aren't directly related to recursion:

• A direct translation would result in a potential memory leak if malloc() fails, so instead I used a second pointer to hold the new node until a location is determined. If malloc() fails, no changes are made to the list.

• strncpy() is often misunderstood, and that can result in inefficient code. For strncpy(dst, src, count), count characters are always copied into dst. If there aren't enough characters in src, the remaining spots will be filled with '\0'. If src tends toward being much shorter than count then strncpy() could spend a prohibitive amount of time copying useless null characters.

  I used strncat() instead, because its behavior is more consistent with what people expect strncpy() to do, but it's important that the destination string be empty, hence why I assigned '\0' to temp->data[0].

[Gonbe]

Or just don't use recursion.

This is what I offered in my previous post. Understanding how it (recursion) works is still beneficial, even if you don't plan to use it.

I think that's the better choice for a linked list because the risk of stack overflow is greater when the recursive growth is linear or worse.

Given the stack size of most modern day compilers this will not realistically be an issue here. (but still "greater", I guess) I'm not sure what you mean by the recursive growth but I assume you mentioned the "or worse" part to word it for a general case.

Also, the iterative form of linked list appending isn't more complex:

This differs from person to person. While it hardly matters for a trivial function like this one I still find the recursive approach easier to comprehend.

There are a couple of things to note over the recursive implementation that aren't directly related to recursion:

I didn't take malloc allocation errors into account because I didn't want to complex the case more than needed. (even though a check for it is minimal. It might raise questions though) It's generally tricky to decide when to post something robust that is more complex or when to post something easy that is easy to break. Especially when you only have a single post to base on.

For strncpy(dst, src, count), count characters are always copied into dst.

Ah, this is something I overlooked. While performance wasn't my main priority here strncat should be used here as it's "performance for free".

[deceptikon]

Understanding how it (recursion) works is still beneficial, even if you don't plan to use it.

That goes without saying. :)

Given the stack size of most modern day compilers this will not realistically be an issue here.

The default stack size on Linux is about 8MB. On Windows it's 1MB. On OSX it's 512KB. Noting that the stack is used for a great deal more than just your recursive stack frames, it seems like a risky assumption that the stack size on a modern OS will save you from a poor choice of algorithm.

But even if the stack is sufficient or you go out of your way to make it sufficient, that's no reason to pessimize (opposite of optimize) your code. If the recursive implementation doesn't buy you at least a twofold reduction in complexity, and also includes what I would consider a probable risk of stack overflow, that sounds like a losing deal to me.

Besides, realistically C is more often used on systems where resources are very tight, so understanding the tradeoff is important.

I'm not sure what you mean by the recursive growth but I assume you mentioned the "or worse" part to word it for a general case.

Growth, depth, number of recursive calls before returning, whatever you want to call it. For a linked list the depth is linear and corresponds to the number of nodes. Compare this to a binary search tree where the average depth is logarithmic. When writing a binary search tree, the biggest issue is balancing the tree to avoiding the degenerate case where the structure approaches being linear.

If you look at things that way, a recursive linked list corresponds to a guaranteed most degenerate case of binary search tree. I think this is where my pet peeve of using recursion for linked lists comes from.

This differs from person to person.

In this case the difference is so small as to be nonexistent. I'm not talking about recursion versus iteration in general, I'm talking about recursion versus iteration in the case where it's trivial to replace recursion with a simple loop and the recursive option is inherently risky. "I find it easier to comprehend" doesn't hold up in a code review; trust me, I've tried. ;)

It's generally tricky to decide when to post something robust that is more complex or when to post something easy that is easy to break.

Indeed. I often omit such things in examples and leave a comment to make it clear that it was intentional.

While performance wasn't my main priority here strncat should be used here as it's "performance for free".

I like to pretend that strncpy() simply doesn't exist unless I'm working with fixed length fields. The name is unfortunate, because it's not consistent with the rest of the strn* functions. Sadly there are quite a few such inconsistencies in the standard library, but that's to be expected in an old language standard that favors backward compatibility.

[general2012]

thanx .but how i see it is reading your code ,we call

 node* addNode(node* list, const char data[])

it checks whether the list is null or not ,and it is null;then it adds data to the list

// The base case. We received an empty list to which we have to add a node.
      if (list == NULL)
              {
    // Allocate the new node.
    list = (node*) malloc (sizeof(node));
    // Set the fields of the node.
    list->next = NULL;
    strncpy(list->data, data, DATA_SIZE);
    }

then it avoid this portion cause data has been inserted to the list

 else
{
list->next = addNode(list->next, data);
}

and then retunr statement will be executed and will return to from where its been called

return list;

that is here

node* enter(node* list)

then

 scanf(" %[^\n]", entered);

it will be executed then

return list;

will be executed
thus return after return it will return to main((in my opinion)).if it returns to main then how other nodes will be executed.thats my problem.i think i made you understand where my problem is.your code is fine .im facing problem with undersatandings

[Taywin]

it checks whether the list is null or not ,and it is null;then it adds data to the list

That's partially correct. It actually serves 2 purposes here. If your original list is empty (null) -- call the function for the first time ever, then it creates the head node of the list. If your list is not null in the first place, then it creates a new node to be returned, and the node will be concatenated to your existing list (from the call in else). Somewhat confusing but you need to understand it because it is not exactly the same as a simple base case.

[general2012]

from @gonbe's recurssion example:
in this example there is no data input involved.so it can be called a simple recurssion example.but in the linked list there is a data input via scanf involved.so for this we need to go outside of the addnode function.so this can be called a discontinous recursive function unlike your last example.i just wanted to know how this happens
after reaching here (after first list is implemented)

list = addNode(list, entered);
scanf(" %[^\n]", entered);

what will happen??

[Taywin]

The part you are talking about is just a simple while-loop content... A similar step by step for your choice() could be as follows...

/*
list <- a pointer of linked list which is NULL & from the outside

in the choice() and other functions inside it
do
  read in a choice from user
  if the selected choice is equal to 1
    display a guiding message
    do
      ask user to enter a string
      entered <- an input string from user
      add entered as a node to the list   // using whatever approach
    end do-while when entered is not equal to "END"
  else
    display good bye message
  end if
end do-while when choice is not equal to 1
*/

[general2012]

i found out where my mistake is.i was overlapping these lines;

while (strcmp(entered,"END") != 0)
   {
      addNode(list, entered);
       scanf(" %[^\n]", entered);

now the programme is quite clear.thanks a lot to you guys