Creating and Merging Linked Lists in C programming-CodePudding

We are given the main function and structures, asked to create two different linked lists. One being in ascending order and another in descending order and then joined together without changing their order. To give an example,if we have L1: 1->3->4->6 and L2: 9->8->5->2, The final list would be 1->9->3->8->4->5->6->2. This below is my work. I'm having some problems.

This is the main function:

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

#include "function.h"

struct nodeFB *startFB = NULL;
struct nodeGS *startGS = NULL;
struct newNodeFB *startNewFB = NULL;

int main()
{
    int id, age;
    scanf("%d", &id);
    while(id!=-1)
    {       
        scanf("%d", &age);
        insertFB(&startFB, id, age);
        scanf("%d", &id);
    }
    
    scanf("%d", &id);
    while(id!=-1)
    {       
        insertGS(&startGS, id);
        scanf("%d", &id);
    }
    
    printFB(startFB); 
    printGS(startGS);   
    createFinalList(&startNewFB,startFB,startGS);   
    printAll(startNewFB); 
    
    return 0;
        
}

These are the given structures and the functions I've written:

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

struct nodeFB
{
    int id; 
    int age;
    struct nodeFB *next; 
};

struct nodeGS
{
    int id;
    struct nodeGS *next;
};

struct newNodeFB
{
    int id;
    int age;
    struct newNodeGS *next;
};

struct newNodeGS
{
    int id;
    struct newNodeFB *next;
};

struct nodeFB *startFB;
struct nodeGS *startGS;

//functions 

struct nodeFB *insertFB( struct nodeFB **startFB, int id, int age) 
{//address of the first node in the linked list of FB

    struct nodeFB *newnode, *ptr;

    newnode = (struct nodeFB*)malloc(sizeof(struct nodeFB));
    newnode->id = id;
    newnode->age = age;
    if (startFB == NULL) {
        newnode->next = NULL;
        *startFB = newnode;
    }
    else {
        ptr = *startFB;
        while(ptr->next!=NULL) {
            ptr=ptr->next;
            ptr->next= newnode;
            newnode->next = NULL;

        }
    }
    return *startFB;
}

void swap(struct nodeFB *a, struct nodeFB *b) {//function to swap two nodes
    int temp = a->id;
    a->id = b->id;
    b->id = temp;
}

void sortFB(struct nodeFB *startFB) { //function to bubble sort the given linked list
    int i;
    int swapped;
    struct nodeFB *ptr1;
    struct nodeFB *ptr2= NULL;
    if (startFB==NULL) { //checking for empty list
        return; }

    do {
        swapped = 0;
        ptr1=startFB;

        while (ptr1->next !=ptr2) {
            if (ptr1->id > ptr1->next->id) {
                swap (ptr1, ptr1->next);
                swapped = 1;
            }
            ptr1= ptr2->next;
        }
        ptr2=ptr1;
    }
    while (swapped);
    
}

void printFB(struct nodeFB *startFB) { //function to display the sorted list 
    struct nodeFB *ptr;
    ptr = startFB;
    sortFB(ptr);
    while(ptr != NULL) {

        printf("%d %d/n", ptr->id, ptr->age);
        ptr=ptr->next;

    }
}

struct nodeGS *insertGS(struct nodeGS **startGS, int id ) {
    struct nodeGS *newnode, *ptr;

    newnode = (struct nodeGS*)malloc(sizeof(struct nodeGS));
    newnode->id = id;
    if (startGS == NULL) {
        newnode->next = NULL;
        *startGS = newnode;
    }
    else {
        ptr = *startGS;
        while(ptr->next!=NULL) {
            ptr=ptr->next;
            ptr->next= newnode;
            newnode->next = NULL;

        }
    }
    return *startGS;
}

void swapGS(struct nodeGS *c, struct nodeGS *d) {//function to swap two nodes
    int temp = c->id;
    c->id = d->id;
    d->id = temp;
}

void sortGS(struct nodeGS *startGS) { //function to bubble sort the given linked list
    int i;
    int swapped;
    struct nodeGS *ptr1;
    struct nodeGS *ptr2= NULL;
    if (startGS==NULL) { //checking for empty list
        return; }

    do {
        swapped = 0;
        ptr1=startGS;

        while (ptr1->next !=ptr2) {
            if (ptr1->id < ptr1->next->id) {
                swapGS (ptr1, ptr1->next);
                swapped = 1;
            }
            ptr1= ptr2->next;
        }
        ptr2=ptr1;
    }
    while (swapped);
    
}
void printGS(struct nodeGS *startGS) {
    struct nodeGS *ptr;
    ptr = startGS;
    sortGS(startGS);
    while(ptr != NULL) {
        printf("%d/n", ptr->id);
        ptr = ptr->next;
    }

}

**struct newNodeFB *createFinalList(struct newNodeFB **startNewFB, struct nodeFB *startFB, struct nodeGS *startGS ) {
struct newNodeFB *temp1, *ptr1;
    temp1=(struct newNodeFB*) malloc(sizeof(struct newNodeFB));
    temp1->id= startFB->id;
    temp1->age=startFB->age;
    struct newNodeGS *temp2;
    temp2->id= startGS->id;
    struct newNodeFB *temp3 = NULL;
    struct newNodeGS *temp4 = NULL;
    while (temp1 != NULL && temp2 != NULL)
    {
        ptr1=temp1;
        while (ptr1->next!=NULL) {
            ptr1=ptr1->next;
            ptr1->next= temp2;
            temp2->next=NULL;
        }
    temp3=temp1->next;
    temp4= temp2->next;
    temp1->next=temp2;
    temp2->next=temp3;
    temp1=temp3;
    temp2=temp4;
    }
    startGS = temp2;
    return startNewFB;
}**

void printALL(struct newNodeFB *startNewFB){
    struct newNodeFB *ptr;
    ptr= startNewFB;
    while(ptr != NULL) {
    printf("%d %d/n%d", startNewFB->id, startNewFB->age, startNewFB->id);
    ptr=ptr->next;
    }
}

CodePudding user response：

The simplest way to create a merged list where the nodes alternate, is to simply iterate over both lists simultaneously and add each node from the two lists into a brand new list.

Because you want to alternate between the two lists, you need to use a single loop to iterate the lists, adding one node from the first list to the new merge-list, then adding one node from the second list. Stop when both lists are finished.

In pseudoish code it could look something like this:

Node *node1 = list1->head;  // Node from first list
Node *node2 = list2->head;  // Node from second list

// Loop while there are nodes in at least one of the lists
while (node1 != NULL || node2 != NULL)
{
    if (node1 != NULL)
    {
        list_add_tail(merge_list, node1->data);
        node1 = node1->next;
    }
    if (node2 != NULL)
    {
        list_add_tail(merge_list, node2->data);
        node2 = node2->next;
    }
}

As seen it's basically the same as iterating over a single list, copying data to a new list.

CodePudding user response：

Another consideration is if one is mixing struct nodeFB and struct nodeGS in one list, how could the programme tell if the node is an FB or GS? Unless the lists are of equal sizes, where they are alternating, one loses type information by mixing them together.

There are several ways to get around this. One could only allow one type of node in one list; one has to convert the types to mix the lists. One might as well convert on input and have one type of list. A more nuanced approach is to store a pointer telling what type it is with every node.

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

/* Circular definitions mean one has to forward declare. */
struct node;
static void foo_print(const struct node *);
static void bar_print(const struct node *);

/* Virtual table stores the type of node. */
typedef void (*print_fn)(const struct node *);
static const struct vt { print_fn print; }
    foo_vt = { &foo_print }, bar_vt = { &bar_print };

/* A list of nodes. */
struct node { struct node *next; const struct vt *vt; };
struct list { struct node *head; };

/* Subclasses of node. */
struct foo_node {
    struct node base;
    int id, age;
};
struct bar_node {
    struct node base;
    int id;
};

/* Implementations of the above. */
static void foo_print(const struct node *node) {
    const struct foo_node *ptr = (const struct foo_node *)node;
    printf("(foo)%d age %d", ptr->id, ptr->age);
}
static void bar_print(const struct node *node) {
    const struct bar_node *ptr = (const struct bar_node *)node;
    printf("(bar)%d", ptr->id);
}

static struct node *foo_input(void) {
    int id, age;
    struct foo_node *foo;
    if((printf("Id: "), scanf(" %d", &id) != 1) || id == -1
        || (printf("Age: "), scanf(" %d", &age) != 1)
        || !(foo = malloc(sizeof *foo))) return 0;
    foo->base.vt = &foo_vt;
    foo->id = id;
    foo->age = age;
    fprintf(stderr, "User entered %d, %d.\n", foo->id, foo->age);
    return &foo->base;
}
static struct node *bar_input(void) {
    int id;
    struct bar_node *bar;
    if((printf("Id: "), scanf(" %d", &id) != 1) || id == -1
        || !(bar = malloc(sizeof *bar))) return 0;
    bar->base.vt = &bar_vt;
    bar->id = id;
    fprintf(stderr, "User entered %d.\n", bar->id);
    return &bar->base;
}

//address of the first node in the linked list
static void push(struct list *start, struct node *node) {
    assert(start && node);
    node->next = start->head, start->head = node;
}

static void printAll(const struct list *list) {
    struct node *node;
    for(node = list->head; node; node = node->next)
    printf("%s", node == list->head ? "" : ", "), node->vt->print(node);
    printf(".\n");
}

/** Interleaves the list `bars` with the list `foos`. `bars` will be the empty
 list and `foos` will have all of the elements. */
static void createFinalList(struct list *foos, struct list *bars) {
    /* Create this function. */
    (void)foos, (void)bars;
}

int main(void) {
    struct list foos = { 0 }, bars = { 0 };
    struct node *node;
    while(node = foo_input()) push(&foos, node);
    while(node = bar_input()) push(&bars, node);
    printf("foos: "), printAll(&foos);
    printf("bars: "), printAll(&bars);
    createFinalList(&foos, &bars);
    printf("now,\n");
    printf("foos: "), printAll(&foos);
    printf("bars: "), printAll(&bars);
    /* fixme: Memory leak, clean up. */
    return 0;
}

If one really cannot modify the nodes, maybe encompass them in a union?

struct node {
    const struct vt *vt;
    union { struct nodeFB fb; struct nodeGS gs; };
};