0

I'm busy with implementation of singly linked list and have 2 functions: insert_back and insert_after.

Here is the listing of them:

void insert_back(int data)
{
    node *temp1;

    temp1 = (node*)malloc(sizeof(node));
    temp1 = head;

    while (temp1->next != NULL) {
        temp1 = temp1->next;
    }

    node *temp;

    temp = (node*)malloc(sizeof(node));
    temp->data = data;
    temp->next = NULL;
    temp1->next = temp; 
}

void insert_after(int pos, int data)
{
    node *temp1;

    temp1 = (node*)malloc(sizeof(node));
    temp1 = head;

    for (int i = 1; i < pos; i++) {
        temp1 = temp1->next;

        if (temp1 == NULL) {
            return;
        }
    }

    node *temp;

    temp = (node*)malloc(sizeof(node));
    temp->data = data;
    temp->next = temp1->next;
    temp1->next = temp; 
}

As you can see they are almost the same and for insert back I want to write insert_after(null, 10). I can solve it by adding if condition and choose one of the loops, but it's not my aim.

Is it possible somehow to use one while or for loops together for serial numbers and null?

Also I see that param int pos is int. Should I use 0 instead of null?

4

2 回答 2

1

You unnecessarily allocate memory in the following lines.

temp1 = (node*)malloc(sizeof(node));
temp1 = head;

This allocated memory will leak as you overwrite the returned address in temp1. You just need temp1 to walk over the list, so there is also no need to allocate any node itself. temp1 can point to any node.

I've taken the liberty to kind of from scratch write a routine doing both things in one go. If pos < 0 it will add the element to the end of the list, otherwise it will add it after the pos-th element, where the first element corresponds with pos == 1. If pos == 0 the element is added at the start of the list.

Also a small main is added to test the routine. new_node has been added to test if memory is not exhausted.

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

typedef struct node
{
        struct node     * next;
        int             data;
} node;

node * head = NULL;

node * new_node(void)
{
        node * result = malloc(sizeof(*result));
        if (result == NULL)
        {
                fprintf(stderr, "Out of memory.\n");
                exit(10);
        }
        return result;
}

void insert_after(int pos, int data)
{
        node    *walk, * prev;
        int     i;

        prev = NULL;
        walk = head;

        for (i = 0; walk != NULL && i != pos; i++)
        {
                prev = walk;
                walk = walk->next;
        }

        if (i != pos && pos > 0)
        {
                fprintf(stderr, "Location not found.\n");
                exit(9);
        }
        else
        {
                walk = new_node();
                walk->data = data;

                if (prev == NULL)
                {
                        walk->next = head;
                        head = walk;
                }
                else
                {
                        walk->next = prev->next;
                        prev->next = walk;
                }
        }
}

int main(void)
{
        int     i;
        node    * wlk;

        for (i = 0; i < 10; i++)
        {
                insert_after(-1, i);
        }
        for (i = 0; i < 10; i++)
        {
                insert_after(3, i+10);
        }

        for (wlk = head; wlk != NULL; wlk = wlk->next)
        {
                printf("%d\n", wlk->data);
        }
        return 0;
}
于 2013-06-11T16:05:22.273 回答
0

Since you are testing for the end of the chain with insert_after(pos,...) anyway, you could go for:

void insert_after(int pos, int data)
{
    node *temp1= head;

    for (int i=1; i<pos; i++) {
        if (temp1->next==NULL) {
            if (pos==INT_MAX) 
                break;   // pos of INT_MAX means insert at end
                         // so we continue with this last item and append
            else 
                return;  // pos higher than length of chain
        }
        temp1 = temp1->next;
    }

    ...
}

Or slightly more compact:

void insert_after(int pos, int data)
{
    node *temp1= head;

    for (int i=1; i<pos && temp1->next!=NULL; i++) {
        temp1 = temp1->next;
    }

    if (temp1->next==NULL && pos!=INT_MAX) 
        return;  // pos higher than length of chain, except for 
                 // INT_MAX (for that we just want to continue)

    ...
}

Then you could use 

void insert_back(int data)
{
      insert_after(INT_MAX, data);
}
于 2013-06-11T16:04:51.017 回答