Good afternoon, Chegg Experts! I have written some code in C: This partially imp

Question

Good afternoon, Chegg Experts!

I have written some code in C:

This partially implemented program calls “insert” 10 times to create a doubly linked list of 10 link elements. Each link node has a “value” field. After calling insert 10 times, the linked list will have the 10 link nodes in sorted order from smallest to largest value. Then, the program calls “print list” which traverses the linked list and prints out all 10 link element values.

Here’s the expected output of the program:

0 2 3 4 4 7 7 8 9 100

I am trying to write the “insert” function. This function must use recursion to perform insertion!

Here are the specifications of the "insert" function:

The “insert” function takes 3 arguments: the head pointer (passed in by reference), a current node pointer, and a pointer to the new node to insert. This function inserts the new node into the list so that the list is ordered from smallest value to largest value. Note, the list is a doubly linked list, so when performing the insertion, my code must maintain both the “next” and “prev” pointers properly. The function should traverse the list recursively (following the cur->next field) to find the link node where the new node should be inserted. This is the first link node to have a value field larger than the new node’s value field (i.e., cur->value > p->value). Once the insertion point is found, I can follow the previous pointer, cur->prev, to reach the previous link node and access its “next” field (which needs to be modified for insertion). My code also needs to modify cur->prev to point to the newly inserted link node.

The challenge is that I must maintain all “next” and “prev” pointers in the linked list properly. Also, I must handle insertion for many special cases: empty list, head insertion (when head->value > p->value), and tail insertion (when p->value is the largest value in the list).

I really need help writing this function! I am very close, but polymorphism in C is difficult. I know you are experts in C, and I would really appreciate the help

Explanation / Answer

Here is the code for you. If you need any further clarification, just get back to me.

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

#define N 10

typedef struct node_ {
int value;
struct node_ *next;
struct node_ *prev;
} node;

void insert(node **head, node *cur, node *p);
void print_list(node *cur);

void print_list(node *cur)
{
if (!cur) {
    printf(" ");
    return;
} else {
    printf("%d ", cur->value);
    print_list(cur->next);
}
}

int
main(int argc, char *argv[])
{
int i;
int data[N] = {2, 7, 3, 9, 4, 4, 0, 8, 7, 100};
node *p, *head;

head = NULL;
for (i = 0; i < N; i++) {
    p = (node *)malloc(sizeof(node));
    p->value = data[i];
    insert(&head, head, p);
}

print_list(head);
}

void insert(node **head, node *cur,node *p) /*Insert function.*/
{
node *temp;
    if(*head==NULL)
{
p->next=NULL;
p->prev=NULL;
*head=p;
return;
}
if(p->value<=cur->value)
{
temp=cur->prev;
p->next=cur;
cur->prev=p;
if(temp!=NULL)
{
p->prev=temp;
temp->next=p;
}
else
{
p->prev=NULL;
*head=p;
}
return;
}
if(cur->next==NULL)
{
cur->next=p;
p->prev=cur;
p->next=NULL;
return;
}
insert(head, cur->next,p);
}
One more point to keep in mind is, there is no point in passing the same varible by address, and by value to the same function at the same time. But as you declared it, I just maintained it.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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