Hello, I am in a C programming class and I am lost at where to begin with this p

Question

Hello, I am in a C programming class and I am lost at where to begin with this problem.

Singly Linked List(ll.c) You already know about basic data types such as int, double, and char; as well as data structures such as C strings and arrays. There are more advanced data structures frequently employed in programing to do common tasks. Three of the most extensively used ones are linked lists, stack, and queue. For this program you will be implementing a linked list data structure. A linked list is one of the most common advanced data structured encountered in Computer Science and serves as the underlying data structure for many other advanced data structures such as stacks, queues, and trees; therefore, it is important to become comfortable with them. There are a few variations of linked lists and many programing languages provide a template from a standard library to use. C does not provide such integrated functionality so it will be necessary to create our own and a good learning opportunity. For the sake of simplicity we will be doing a singly linked list opposed to a doubly linked list. A singly linked list has a few characteristics that make them both better and worse than a basic array. A linked list can have data inserted easily at any point in the list and is dynamically allocated so there is no need to know how much storage will be needed up front or make re allocations like with dynamically allocated memory. The biggest disadvantages of linked list is that there is no random access to a specific element of the list (meaning that there is no [i] notation available) and there is more overhead incurred because of the extra pointer variable to each node in the list. Please consult the below provided links to learn more about the specific terminology used when talking about linked lists and to gain a more in-depth theoretical knowledge before starting on this problem. In short a linked list consists of several instances of a structure which we call a node. This node contains another instance of a node that is what is used to link the list and a variable to serve as storage this storage could be anything an integer, a double, a character array, another list, anything. For our purposes on this introductory assignment we will make it be a double. Sometime another node variable exists that links the list backwards as well as forwards, that makes the list a doubly linked list which we will not bother with on this assignment.

Implement these functions: void makeNode(node_t *head, double input); void printList(node_t *head); double removeNode(node_t *head); double sum(node_t *head); double avg(node_t *head); bool isFound(node_t *head, double input);

Sample Output

Enter value for first element: 1

1: Create Node

2: Print List

3: Remove Node

4: Sum List

5: Calculate Average

6: Search for Value

7: Exit

1

Enter value for new element: 2 2 1.000000 2.000000

5

Average of list elements is: 1.500000

4 Sum of list elements is: 3.000000

6 Enter a term to search for in the list:

7

Value 7.000000 was NOT found in the list.

7

The functions must be implemented exactly as they are given.

Thank you for your help.

Marty

Explanation / Answer

Sample Code:

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
#define ISEMPTY printf(" EMPTY LIST:");
/*
* Node Declaration
*/
struct node_t
{
    double value;
    struct node_t* next;
};

struct node_t* create_node(double);
struct node_t* makeNode(struct node_t *head, double input);
void printList(struct node_t *head);
void removeNode(struct node_t *head);
double sum(struct node_t *head);
double avg(struct node_t *head);
bool isFound(struct node_t *head, double input);

typedef struct node node_t;
struct node_t *newnode, *ptr, *prev, *temp;
node_t *head = NULL, *last = NULL;

/*
* Main :contains menu
*/

int main()
{
    int ch, i;
    char ans = 'Y'; bool foundFlag;
   double input, sum_vals, avg_vals;

   //newnode = (node_t *)malloc(sizeof(node_t));
   struct node_t* newnodes = NULL;
  
    while (ans == 'Y'||ans == 'y')
    {
        printf(" --------------------------------- ");
        printf(" Operations on singly linked list ");
        printf(" --------------------------------- ");
        printf(" 1.Create Node");
        printf(" 2.Print List");
        printf(" 3.Remove Node");
        printf(" 4.Sum List");
        printf(" 5.Calculate Average");
        printf(" 6.Search for Value");
        printf(" 7.Exit ");
        printf(" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ");
        printf(" Enter your choice");
        scanf("%d", &ch);

        switch (ch)
        {
        case 1:
            printf(" ...Enter value for new element... ");
           for(i=0; i<3; i++){
               scanf("%lf", &input);
               newnodes = makeNode(newnodes, input);
           }
            break;
        case 2:
            printList(newnodes);
            break;
        case 3:
            removeNode(newnodes);
            break;
        case 4:
            sum_vals = sum(newnodes);
           printf("%lf", sum_vals);
            break;
        case 5:
            avg_vals = avg(newnodes);
           printf("%lf", avg_vals);
            break;
        case 6:
           printf(" ...Enter value to found... ");
           scanf("%lf", &input);
           foundFlag = isFound(newnodes, input);
            break;
        case 7:
            printf(" ...Exiting... ");
            return 0;
            break;
        default:
            printf(" ...Invalid Choice... ");
            break;
        }
        printf(" YOU WANT TO CONTINUE (Y/N)");
        scanf(" %c", &ans);
    }
    return 0;
}

/*
* Creating Node
*/
struct node_t* create_node(double val)
{
    struct node_t* newnode = (struct node_t *)malloc(sizeof(struct node_t));
    if (newnode == NULL)
    {
        printf(" Memory was not allocated");
        return 0;
    }
    else
    {
        newnode->value = val;
        newnode->next = NULL;
        return newnode;
    }
}

struct node_t* makeNode(struct node_t *head, double input)
{
   struct node_t* newnode = (struct node_t *)malloc(sizeof(struct node_t));
   struct node_t* temp=NULL;
    newnode = create_node(input);
    if (head == NULL)
    {
        head = newnode;
        head->next = NULL;
    }
    else
    {
        temp = head;
        head = newnode;
        head->next = temp;
    }
  
   return head;
}

/*
* Delete Node from specified position in a non-empty list
*/
void removeNode(struct node_t *head)
{
    int pos, cnt = 0, i;
   struct node_t *ptr = head;
  
    if (head == NULL)
    {
        ISEMPTY;
        printf(":No node to delete ");
    }
    else
    {
        printf(" Enter the position of value to be deleted:");
        scanf(" %d", &pos);
        ptr = head;
        if (pos == 1)
        {
            head = ptr->next;
            printf(" Element deleted");  
        }
        else
        {
            while (ptr != NULL)
            {
                ptr = ptr->next;
                cnt = cnt + 1;
            }
            if (pos > 0 && pos <= cnt)  
            {
                ptr = head;
                for (i = 1;i < pos;i++)
                {
                    prev = ptr;
                    ptr = ptr->next;
                }
                prev->next = ptr->next;
            }
            else
            {
                printf("Position is out of range");
            }
        free(ptr);
        printf(" Element deleted");
        }
    }
}
double sum(struct node_t *head){
   double sum_val;
   struct node_t *ptr = head;
   if (head == NULL)
    {
        ISEMPTY;
        printf(":No nodes in the list to display ");
    }
   else
    {
        for (ptr = head;ptr != NULL;ptr = ptr->next)
        {  
           sum_val += ptr->value;
        }
    }
   return sum_val;
}

double avg(struct node_t *head){
   double sum_val, avg_val;
   int count;
   struct node_t *ptr = head;
   if (head == NULL)
    {
        ISEMPTY;
        printf(":No nodes in the list to display ");
    }
   else
    {
        for (ptr = head;ptr != NULL;ptr = ptr->next)
        {  
           sum_val += ptr->value;
           count++;
        }
    }
   avg_val = sum_val/count;
   return avg_val;
}

bool isFound(struct node_t *head, double input)
{
   struct node_t *ptr = head;
    int flag = 0, pos = 0;

    if (head == NULL)
    {
        ISEMPTY;
        printf(":No nodes in the list ");
    }
    else
    {
        for (ptr = head;ptr != NULL;ptr = ptr->next)
        {
            pos = pos + 1;
            if (ptr->value == input)
            {
                flag = 1;
                break;
            }
        }
        if (flag == 1)
        {
            printf(" Element %d found at %d position ", input, pos);
           return true;
        }
        else
        {
            printf(" Element %d not found in list ", input);
           return false;
        }
    }  
}

void printList(struct node_t *head)
{
   struct node_t *ptr = head;
   double val;

    if (head == NULL)
    {
        ISEMPTY;
        printf(":No nodes in the list to display ");
    }
    else
    {
        if (ptr != NULL)
        {
            val = ptr->value;
            printList(ptr->next);
            printf("%lf ", ptr->value);
        }
    }
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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