Building a l

inked l

ist and

traversing

it

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

s

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:

1

Insert integer into linked list

2

Find integer in linked list

3

Delete integer from linked list

4

Print out integers backward

using the

iterative strategy

5

Print out integers backward using the

recursive

strategy

6

Quit

Enter

1

,

2

,

3

,

4

,

5

, or

6:

Use a

switch

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

option

6

is entered by the user.

You should manage properly an invalid choice.

Options

1

,

2

, and

3

:

If the user picks opt

ion

1

,

2

or

3

,

you should ask him/her to input an integer.

Option

2

:

If the user picks option

2

,

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

3

:

If the user picks option

3

, 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

3

, and the entered integer

is

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

nd

.

2

/2

A

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

:

1)

the i

nsertion (

insert_node

),

2)

the search (

find

_node

),

3)

the deletion (

delete_node

),

4)

the backward print iteratively (

print

_

backward_iteration

), and

5)

the backward print recursively (

print

_

backward_recursion

).

Those functions will be called from

main

.

Structure of y

our program

A

code skeleton

(

assignment

1

0

.c

) 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