Prompt the user to enter a string Call a function to insert that string, in alph

Question

Prompt the user to enter a string

Call a function to insert that string, in alphabetic order, into a linked list.

If the user did not enter a string, print the list in order and terminate.

Specifications

Use this structure and constant for the linked list node:

#define MAX_STR_LEN     80

struct link_node

{

char node_str[ MAX_STR_LEN ];

struct link_node *next;

};

Your solution should incorporate the following functions

// This function is used to compare two nodes.

// The return values are:

// -1: n1 < n2

// 0: n1 == n2

// +1: n1 > n2

int compare_node( struct link_node *n1, struct link_node *n2 );

// This function is used to add a new node into the

// alphabetically sorted linked list. The head of the

// list is pointed to by 'list'.

//

// The return value is the (possibly new) head pointer.

struct link_node *add_node( struct link_node *list,

                           struct link_node *node );

// Follow the linked list and print out each node along the way.

void display_list( struct link_node *head );

Use malloc() to create new link_node structures.

Use fgets() to read the user’s input string.

Pseudo-Code

Following is the start of some pseudo code for this lab. Expand on this to fully describe your solution:

Give the user some instructions on what to do.

WHILE ( the user doesn’t enter an “empty” string )

Get the user entered string.

Allocate a new node.

Initialize the node with the user’s string.

Add the node to the list in alphabetic order.

END-WHILE

Display the linked list of strings.

Example

Following is an example of running the program:

Please enter strings. When you are done, enter a blank line.

> Ken Arnold

> Tony Montiel

> Boba Fett

> Hoban Washburne

> Neil Armstrong

>

Boba Fett

Hoban Washburne

Ken Arnold

Neil Armstrong

Tony Montiel

Conditions

You used malloc() to allocate the nodes. Do the right thing, and use free() to release the memory.

With fgets(), you may have noticed that it copies over the new-line character. Get rid of that pesky extra character.

Explanation / Answer

/* Program to insert in a sorted list */
#include<stdio.h>
#include<stdlib.h>

/* Link list node */
struct node
{
    int data;
    struct node* next;
};

void sorted(struct node** head_ref, struct node* new_node)
{
    struct node* current;

    if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
    {
        new_node->next = *head_ref;
        *head_ref = new_node;
    }
    else
    {
        /* Locate the node before the point of insertion */
        current = *head_ref;
        while (current->next!=NULL &&
               current->next->data < new_node->data)
        {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
}

struct node *newNode(int new_data)
{
    /* allocate node */
    struct node* new_node =
        (struct node*) malloc(sizeof(struct node));

    /* put in the data */
    new_node->data = new_data;
    new_node->next = NULL;

    return new_node;
}

/* Function to print linked list */
void printList(struct node *head)
{
    struct node *temp = head;
    while(temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
}

int main()
{
    /* Start with the empty list */
    struct node* head = NULL;
    struct node *new_node = newNode(5);
    sorted(&head, new_node);
    new_node = newNode(10);
    sorted(&head, new_node);
    new_node = newNode(7);
    sorted(&head, new_node);
    new_node = newNode(3);
    sorted(&head, new_node);
    new_node = newNode(1);
    sorted(&head, new_node);
    new_node = newNode(9);
    sorted(&head, new_node);
    printf(" Created Linked List ");
    printList(head);

    getchar();
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.