Adding and Sorting a Linked List in C

In my assignment, I have to write a function that takes a pointer to the "LNode" structure and an integer argument as arguments. Then I have to not only add that integer to the linked list, but also position it so that the list is in the correct ascending order. I have tried several different attempts and this is my post code.

LNode*  AddItem(LNode  *headPtr, int  newItem)
{
    auto    LNode   *ptr = headPtr;

    ptr = malloc(sizeof(LNode));

    if (headPtr == NULL)
    {
        ptr->value = newItem;
        ptr->next = headPtr;
        return ptr;
    }
    else
    {

        while (headPtr->value > newItem || ptr->next != NULL)
        {
            printf("While\n"); // This is simply to let me know how many times the loop runs
            headPtr = headPtr->next;
        }
        ptr->value = newItem;
        ptr->next = headPtr;
        return ptr;
    }

}  // end of "AddItem"

      

When I run it and try to insert, say, 5 and then 3, 5 comes up, but then the while loop runs once and I get a segmentation error.

Also I cannot change the arguments as part of the skeleton code for this project. Thanks to everyone who can help.

If it helps, it looks like this:

typedef struct  LNode
{
    int                 value;
    struct  LNode      *next;

} LNode;

      

+3


source to share


4 answers


In your loop

while (headPtr->value > newItem || ptr->next != NULL)
    {
    printf("While\n"); // This is simply to let me know how many times the loop runs
    headPtr = headPtr->next;

      

you are checking if uninitialised ptr->next

(not) is NULL

. This is unreasonable and can lead to chaos assuming that the bit pattern in that part ptr

does not match the pointer NULL

, because in the condition ||

in the condition, then the loop condition is always true and you run the end of your list.

Either way ||

is wrong, you need &&

both conditions must be met, something is wrong NULL

, and the relationship between these values ​​must be met.



And, since you want the list to be in ascending order, you must traverse the list, and the value in the list is less than the value to be inserted.

But you must stop before the specified value is greater or greater than the new value, because you must change the next

node pointer , after which you will enter the new value.

if (headPtr->value >= newItem) {
    ptr->value = newItem;
    ptr->next = headPtr;
    return ptr;
}
while(headPtr->next != NULL && headPtr->next->value < newItem) {
    headPtr = headPtr->next;
}
// Now headPtr is the node behind which the new item is to be inserted
ptr->value = newItem;
ptr->next = headPtr->next;
headPtr->next = ptr;
return ??

      

But which pointer will you return? If the new item is the first in the list, you return a pointer to the first node. If you also want to do this, if a new item is inserted later, you need to keep (a copy of) the original headPtr

and put it back.

+3


source


Wrong condition for your cycle. You never install ptr->next

, but use it to test ptr->next!=NULL

, which means it headPtr=headPtr->next

goes in a loop. Therefore, you must set: ptr->next=NULL

after setting its value.

You can also print these lines and put them at the top:

   ptr->value = newItem;
   ptr->next = headPtr;

      



Try the following:

LNode*  AddItem(LNode  *headPtr, int  newItem)
{
    auto    LNode   *ptr, *temp, *orghead;
    orghead = headPtr;
    int fl=0;
    ptr = malloc(sizeof(LNode));
    ptr->value = newItem;
    ptr->next = NULL;
    temp = ptr;

    if (headPtr == NULL)
        return ptr;
    else
        {

        while(headPtr != NULL && headPtr->value < newItem)
            {
            printf("While\n");
            fl =1;
            temp = headPtr;
            headPtr = headPtr->next;
            }
        temp->next = ptr;
        ptr->next = headPtr;
        if(fl) return orghead;
        else return temp;
        }

}  // end of "AddItem"

      

+2


source


Your while loop continues to the end of your linked list, and your last element is null. So, in your state, you are dereferencing a null node (headPtr), thus getting a segmentation fault. I think you need to check if your node is null or not:

while (headPtr != NULL && (headPtr->value > newItem || ptr->next != NULL))

      

0


source


so true of all of the above

while (headPtr->value > newItem || ptr->next != NULL)
        {
            printf("While\n"); // This is simply to let me know how many times the loop runs
            headPtr = headPtr->next;
        }

      

You are not checking for null Condition for headPtr inside While

at this point

headPtr = headPtr->next;

      

headPtr-> next may be null, causing your program to crash

bit more

LNode*  AddItem(LNode  *headPtr, int  newItem)
{

auto    LNode   *ptr = headPtr; ?

    ptr = malloc(sizeof(LNode));

    if (headPtr == NULL)
    {
        ptr->value = newItem;
        ptr->next = headPtr;
        return ptr;
    }

      

consider headPtr not NULL, now ptr points to some heap malloc ptr-> next may or may not be NULL in this case

while (headPtr->value > newItem || ptr->next != NULL)

      

will be unpredictable

Maybe you need to take a little look at your logic

see below for pseudo logic if you like

LNode* add_time(LNode *headptr , data){

    LNode   *ptr =  headptr, *temp;        

    temp = malloc(sizeof(LNode));

    if(!temp) 
      return ptr;

    temp->next = NULL;
    temp->value= data;

    if(ptr == NULL){ 
        /** There is no list**/
        ptr = temp;
        return ptr;
     }

    /* go to last node*/
    while(ptr->next)
        ptr = ptr->next;

    ptr->next = temp;

    return ptr;

}

      

0


source







All Articles