Building a l inked l ist and traversing it iteratively and r ecursively Write a

ID: 3822390 • Letter: B

Question

Building a l

inked l

ist and

traversing

iteratively and r

ecursively

Write a C program that reads int

egers from the keyboard. Your program should then build a

linked list in the heap. Each node should be defined as a structure with two members: an integer

and a pointer to the next node in the list. The last node in the linked list points to NULL.

Your pr

ogram should

be able to

insert

an integer

into the

front

of the list

find an integer

and

return a pointer to the corresponding node, and

delete an integer

from the list (if found).

Also,

your

program

should be able to use

the list to

print out the integer

in the order in which they

were

entered

That is, you need to

print the tail of the list first

. This can be done either by using an

iterative strategy

or a

recursive strategy

for printing.

We ask you to implement both strategies.

You should provide the

user with a menu with

six

options to pick from:

Insert integer into linked list

Find integer in linked list

Delete integer from linked list

Print out integers backward

using the

iterative strategy

Print out integers backward using the

recursive

strategy

Quit

Enter

, or

Use a

switch

statement for controlling the menu. The menu is continually displayed until

option

is entered by the user.

You should manage properly an invalid choice.

Options

, and

If the user picks opt

ion

you should ask him/her to input an integer.

Option

If the user picks option

and the entered integer is not in the list,

the

find_node

function

should return

NULL

to the invoker

. Let the user know that the integer is not

in the list

Option

If the user picks option

, and the entered integer

is in the list

, the corresponding

node is deleted from the list and a pointer to the first node in the new linked list

should be returned

. Let the user know that the integer has been found and d

eleted

If the user picks option

, and the entered integer

not

in the list

, no node is deleted

and a pointer to the first node in the new linked list (which is still the same list)

should be returned

. Let the user know that the integer has not been fou

success_flag

_ptr

pointer to an integer

should

be used to indicate whether

the node was successfully deleted or not. Refer to Lecture 9, Slide 20.

Your program should have

five

functions

(operations on linked lists)

that implement respectively

the i

nsertion (

insert_node

the search (

find

_node

the deletion (

delete_node

the backward print iteratively (

backward_iteration

), and

the backward print recursively (

backward_recursion

Those functions will be called from

main

Structure of y

our program

code skeleton

(

assignment

) i

s available for you to download from the class

Blackboard shell

Fill this file

with your

code

You

must

use this skeleton as is.

You cannot

change the signature (i.e., header) of any of the provided function declarati

ons

Explanation / Answer

CODE:

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int data;
   struct node *next;
}*head;
void append(int num)
{
   struct node *temp,*right;
   temp= (struct node *)malloc(sizeof(struct node));
   temp->data=num;
   right=(struct node *)head;
   while(right->next != NULL)
   right=right->next;
   right->next =temp;
   right=temp;
   right->next=NULL;
}
void add( int num )
{
   struct node *temp;
   temp=(struct node *)malloc(sizeof(struct node));
   temp->data=num;
   if (head== NULL)
   {
   head=temp;
   head->next=NULL;
   }
   else
   {
   temp->next=head;
   head=temp;
   }
}
void addafter(int num, int loc)
{
   int i;
   struct node *temp,*left,*right;
   right=head;
   for(i=1;i<loc;i++)
   {
   left=right;
   right=right->next;
   }
   temp=(struct node *)malloc(sizeof(struct node));
   temp->data=num;
   left->next=temp;
   left=temp;
   left->next=right;
   return;
}
void insert(int num)
{
   int c=0;
   struct node *temp;
   temp=head;
   if(temp==NULL)
   {
   add(num);
   }
   else
   {
   while(temp!=NULL)
   {
       if(temp->data<num)
       c++;
       temp=temp->next;
   }
   if(c==0)
       add(num);
   else if(c<count())
       addafter(num,++c);
   else
       append(num);
   }
}
int delete(int num)
{
   struct node *temp, *prev;
   temp=head;
   while(temp!=NULL)
   {
   if(temp->data==num)
   {
       if(temp==head)
       {
       head=temp->next;
       free(temp);
       return 1;
       }
       else
       {
       prev->next=temp->next;
       free(temp);
       return 1;
       }
   }
   else
   {
       prev=temp;
       temp= temp->next;
   }
   }
   return 0;
}

void display(struct node *r)
{
   r=head;
   if(r==NULL)
   {
   return;
   }
   while(r!=NULL)
   {
   printf("%d ",r->data);
   r=r->next;
   }
   printf(" ");
}
void displayBackward(struct node *r)
{
   // Base case
if (r == NULL)
return;

// print the list after head node
displayBackward(r->next);

// After everything else is printed, print head
printf("%d ", r->data);
}

int find(struct node *r,int data)
{
int counter = 0;
r=head;

   if(r==NULL)
   {
   return;
   }
   while(r!=NULL)
   {
   counter++;
   if (data == r->data) {
return counter;
}
   r=r->next;
   }
   printf(" ");
}

int count()
{
   struct node *n;
   int c=0;
   n=head;
   while(n!=NULL)
   {
   n=n->next;
   c++;
   }
   return c;
}
int main()
{
   int i,num;
   struct node *n;
   head=NULL;
   while(1)
   {
   printf(" List Operations ");
   printf("=============== ");
   printf("1.Insert integer into linked list ");
   printf("2.Find integer in list ");
   printf("3.Delete integer from list ");
   printf("4.print backwards ");
   printf("5.print forward ");
   printf("6.Exit ");
   printf("Enter your choice : ");
   if(scanf("%d",&i)<=0){
       printf("Enter only an Integer ");
       exit(0);
   } else {
       switch(i)
       {
       case 1: printf("Enter the number to insert : ");
scanf("%d",&num);
insert(num);
break;
       case 2:   printf("Enter element to find: ");
       scanf("%d", &num);
       num = find(n,num);
       printf("Element found at %d ", num);
break;
       case 3:   if(head==NULL)
               printf("List is Empty ");
               else{
               printf("Enter the number to delete : ");
               scanf("%d",&num);
               if(delete(num))
                   printf("%d deleted successfully ",num);
               else
                   printf("%d not found in the list ",num);
               }
               break;
       case 4:   if(head==NULL)
               {
               printf("List is Empty ");
               }
               else
               {
               printf("Element(s) in the list are in backwards : ");
               }
               displayBackward(head);
               printf(" ");
               break;
       case 5:   if(head==NULL)
               {
               printf("List is Empty ");
               }
               else
               {
               printf("Element(s) in the list are in forward: ");
               }
               display(n);
               break;
       case 6:   return 0;
       default: printf("Invalid option ");
       }
   }
   }
   return 0;
}

Results

List Operations
===============
1.Insert integer into linked list
2.Find integer in list
3.Delete integer from list
4.print backwards
5.print forward
6.Exit
Enter your choice : 1
Enter the number to insert : 1

List Operations
===============
1.Insert integer into linked list
2.Find integer in list
3.Delete integer from list
4.print backwards
5.print forward
6.Exit
Enter your choice : 6

Navigate

Building a Starship. Eventually we might like to build a starship to send a mann

Building a protein from individual amino acids would be an example of which type

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

Building a l inked l ist and traversing it iteratively and r ecursively Write a

Question

Explanation / Answer

Related Questions

Navigate