Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Write a Makefile that builds the program list from a C file list.c . Your Makefile should use the compiler flags discussed in class, and

Write a Makefile that builds the program list from a C file list.c. Your Makefile should
use the compiler flags discussed in class, and have the all and clean targets as shown
previously. You should also include the flag -Wextra as discussed in the lab.
Creating a List
Your list nodes will be defined as follows:
struct node {
int value ;
struct node * next ;
};
We will allocate all variable in our main() function.
As with Assignment 4, we will be using an array to allocate storage of our nodes (we will
create 100 nodes). struct node nodes[100]
Once we have our nodes allocated, we need to employ a method to track which nodes in our
array are in use, and which are free. To do this we will create two pointers. struct node
*list head and struct node *free list.
Storage Initialization
With these pieces in place we now need to initialize our allocated nodes. Create a func-
tion called struct node *list init(struct node nodes[]). This function takes the node
storage and iterates each node, connecting its next pointer to the next node in the array,
and for the last item setting the next pointer to
0(or NULL). The function should return a pointer to last node in the array. We know that
the start of the array is the first node in our free list.
Strictly speaking at this point we have created our first link-list.
2
List Operations
Insert
There are different types of insertion to a list (prepend, append, insert before, and insert
after). In this exercise we will only focus on prepend and append. For this we will need a
third pointer struct node *list tail that points to the last node in the list (which is why
our initialization function returns this).
Prepend Prepend adds a node to the beginning of the list. There are four steps for this
operation:
1. Get the node pointed to by the free list
2. Update free list to point at the new nodes next
3. Update the new nodes next to point at list head
4. Update list head to point at the new node
Append Append adds a node to the end of the list. There are four steps for this operation:
1. Get the node pointed to by free list
2. Update free list to point at the new nodes next
3. Update the new nodes next to point at NULL
4. Update list tail->next to point at the new node
Remove
As with insert there are several types of removal operations for a list (Pop, Pop Back, Remove
before, Remove after). In this exercise we will only focus on pop.
Pop Pop removes a node from the beginning of the list. There are four steps for this
operation:
1. Get the node pointed to by list head
2. Update list head to point at list head->next
3. Update the new nodes next to point at list free
4. Update free list to point at the removed node
3
Functions to write
You may have notices that there are several overlapping processes in the above operations.
Specifically, inserts require a pop from the free list, and pop requires a prepend to the free
list. For this reason it makes the most sense to create functions that can provide these
operations and then build up the more complex functionality. These are often called helper
functions
list internal prepend Create a function int list internal prepend(struct node **list,
struct node *node) which takes a pointer to a pointer list and a pointer to a node and
preforms a simple prepend:
1. Update the new nodes next to point at *list
2. Update *list to point at the new node
The function should return an int where 0 is success, and -1 is failure.
list internal pop Create a function int list internal pop(struct node **list, struct
node **node) which takes a pointer to a pointer list and a pointer to pointer to a node
preforms a simple pop:
1. Get the node pointed to by *list
2. Update *list to point at (*list)->next
3. Update *node to point at retrieved node
The function should return an int where 0 is success, and -1 is failure.
list prepend Create a function int list prepend(struct node **list head, struct
node **free list, int value) which performs the prepend steps described above using
the helper functions list internal prepend and list internal pop
list append Create a function int list append(struct node **list head, struct node
**free list, int value) which performs the append steps described above using the
helper functions list internal prepend and list internal pop
list pop Create a function int list pop(struct node **list head, struct node **free list)
which performs the pop steps described above using the helper functions list internal prepend
and list internal pop
list print Create a function int list print(struct node *list head) which prints the
current values of the list on a single line as 1->2->3->4...
4
main Create a main function that creates an array of list nodes, and initializes them, stor-
ing the struct node *list head, struct node *free list and struct node *list tail
pointers. The function should then run a loop which accepts from stdin a line conta

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

More Books

Students also viewed these Databases questions

Question

Design a cross-cultural preparation program. page 313

Answered: 1 week ago

Question

Evaluate employees readiness for training. page 289

Answered: 1 week ago