Node and Linked List assignment
PS3.0: Node and List
Before you can work on the list operations, you'll need to write a c assignment that creates both a node and a list. The node should be responsible for node-y things, and the list for list-y things, in other words, they won't know much about each other. The list will accept a filled-in node and add it to the list.
The node should be a struct, and it looks about the same as the one we've seen in lectures:
typedef struct node { int value; node* next;
}
Here are the signatures for both node's and list's functions. Note that this is just the starting set of functions; each problem will require you to (possibly) add new functions to one or both of list and node.
For nodes:
node* createNode(int value); //Create a new node with a given value
For lists:
bool addNode(node* node); //Add a node to the list node* findNode(int value); //Find a node in the list bool deleteNode (node* node); //Delete a node in the list
void printList(void); //Print the values in the list
The returned boolean values should indicate the success or failure of the operation.
PS3.1 Add a set of nodes (in main. c)
Create a singly linked list from this array:
[89, 39, 18, 96, 71, 25, 2, 55, 60, -8, 9, 42, 69, 96, 24]
Read each value in turn and call created, then addNode. Nodes must be dynamically allocated using malloc().
Print the list.
PS3.2 Delete the largest nodes
From main, ask the list to delete all of the nodes that contain the largest value in the list.
The signature for this function will be similar to void deleteLargest(void);
On the listing side, deleteLargest should call an internal list function to find *all* nodes that contain the same largest value (there should be more than one), and then call the internal deleteNode function to delete all of the nodes found. Hint: You can use an array to collect the largest nodes as you find them.
Print the list.
PS3.3 Count the nodes in the list
From the main, ask the list to return the number of nodes in the list, and print the value.
PS3.4 Sort the list
From main, ask the list to sort itself. Use a bubble-sort algorithm:
- Starting from the top of the list, compare the value in the first node with the value in the second node
- If the value in the second node is smaller, swap the two nodes, otherwise leave them in place
- Move to the second node and compare its value with the third node, swapping them if necessary
- Repeat this until you've reached the end of the list
- Next, go back to the top and do it all over again
- The list is sorted when you walk the entire list from top to bottom and do not perform any swaps
The list should be sorted in place. In other words, don't use a second list. Print the list
Solution:
List:
#include < stdio.h>
#include < stdlib.h>
#include "list.h"
node *head = NULL;
//Add a node to the list
bool addNode(node *new_node)
{
if (head == NULL)
{
// This is add node to empty list. Just assign head to new node
head = new_node;
}
else
{
// This is list with elment. Try to add new node to end of list
node *current_node = head;
while (current_node->next != NULL)
{
current_node = current_node->next;
}
// Now we are in end of list. Just add next to current node
current_node->next = new_node;
}
return true;
}
//Find a node in the list
node* findNode(int value)
{
node *current_node = head;
while (current_node != NULL)
{
if (current_node->value == value)
{
// If this node contain value is the same. Just return it
return current_node;
}
// Go the next node for next check
current_node = current_node->next;
}
// Go to end of node. And we can not found anything. Just return null.
return NULL;
}
//Delete a node in the list
bool deleteNode(node *del_node)
{
if (head == NULL)
{
// Current list is empty. We can not delete any more
return false;
}
else if (head->value == del_node->value)
{
// If this is delete the head node.
node *tmp = head->next;
free(head);
head = tmp;
return true;
}
else
{
// If this is delete the middle node
node *current_node = head;
node *prev_node = NULL;
while (current_node != NULL)
{
if (current_node->value == del_node->value)
{
// Find the node to be delete.
prev_node->next = current_node->next;
free(current_node);
return true;
}
// If this is not a node delete. Just move to next node for checking.
prev_node = current_node;
current_node = current_node->next;
}
}
// Can not found any node in list for remove.
return false;
}
//Print the values in the list
void printList(void)
{
node *current_node = head;
while (current_node)
{
printf("%d ", current_node->value);
current_node = current_node->next;
}
printf("\n");
}
void deleteLargest(void)
{
// First step is find the largest node
int largest_value = head->value;
node *current_node = head->next;
while (current_node)
{
if (current_node->value > largest_value)
{
// If found new node largest. Just keep track it.
largest_value = current_node->value;
}
// Move to next node for check
current_node = current_node->next;
}
// Now try to delete all node largest node.
node *del_node = malloc(sizeof(node));
del_node->value = largest_value;
del_node->next = NULL;
// Loop until no more largest value in node.
while (findNode(largest_value) != NULL)
{
deleteNode(del_node);
}
free(del_node);
}
int count(void) {
int cnt = 0;
node* current_node = head;
while(current_node) {
cnt++;
current_node = current_node->next;
}
return cnt;
}
void sort(void) {
if(head == NULL) {
// Don't need to sort the empty list
return;
} else {
node* current_node = head;
node* compare_node = NULL;
while(current_node) {
compare_node = current_node->next;
while(compare_node) {
if(compare_node->value < current_node->value) {
// We need to swap 2 node
int tmp_value = current_node->value;
current_node->value = compare_node->value;
compare_node->value = tmp_value;
}
compare_node = compare_node->next;
}
current_node = current_node->next;
}
}
}
Node:
#include < stdio.h>
#include < stdlib.h>
#include "node.h"
//Create a new node with a given value
node* createNode(int value)
{
// Allocate a new node
node *new_node = (node*) malloc(sizeof(node));
if (new_node)
{
// Check the allocated is successfull
new_node->value = value;
new_node->next = NULL;
}
return new_node;
}
Main:
#include < stdio.h>
#include < stdlib.h>
#include "node.h"
#include "list.h"
int main(int argc, char** argv) {
// PS3.1 - Add a set of nodes.
// Create a signly linked list from this array. [89, 39, 18, 96, 71, 25, 2, 55, 60, -8, 9, 42, 69, 96, 24]
int array[15] = {89, 39, 18, 96, 71, 25, 2, 55, 60, -8, 9, 42, 69, 96, 24};
for(int i = 0; i < 15; i++) {
node* new_node = createNode(array[i]);
addNode(new_node);
}
// Print list
printf("PS3.1 - List after add: ");
printList();
printf("===========================================\n");
// PS3.2 Delete the largest nodes
printf("PS3.2 - Try to delete the largest node.\n");
deleteLargest();
printf("List after delete: ");
printList();
printf("===========================================\n");
// PS3.3 - Count the nodes in the list
printf("PS3.3 - Count the nodes in the list\n");
int list_size = count();
printf("Count nodes in list: %d\n", list_size);
printf("===========================================\n");
// PS3.4 - Sort the list
printf("PS3.4 - List after sort: ");
sort();
printList();
// j o h n n y t u o t - g m a i l - c o m
return 0;
}