Day 20 - Dynamic Data Structures

CLASSWORK:
Getting the linked list nodal functions to work:
/*¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C*/
/*¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C*/
/* This program tests the functions to insert and delete */
/* items in a linked list. */
#include <stdio.h>
#include <stdlib.h>
/* Define structure to represent a node in a linked list. */
struct node
{
int data;
struct node *link;
};

/*¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C*/
/* This function returns a value of one if the linked list */
/* is empty. */
int empty(struct node *head)
{
/* Declare variables. */
int k = 0;
/* Determine if the list is empty. */
if (head == NULL)
k = 1;
/* Return integer. */
return k;
}
/*¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C*/


/*¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C*/
/* This function prints a linked list. */
void print_list(struct node *head)
{
/* Declare variables. */
struct node *next;
/* Print linked list. */
if (empty(head))
printf("Empty list \n");
else
{
printf("List Values: \n");
next = head;
while (next->link != NULL)
{
printf("%d \n", next->data);
next = next->link;
}
printf("%d \n", next->data);
}
/* Void return. */
return;
}
/*¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C*/


/*¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C*/
/* This function inserts a new node in a linked list. */
void insert(struct node **ptr_to_head, struct node *nw)
{
/* Declare variables and function prototypes. */
struct node **next;
/* Check for insert to empty list. */
if (empty(*ptr_to_head))
*ptr_to_head = nw;
else
/* Traverse list to find location for insert. */
{
next = ptr_to_head;
while (((*next)->data < nw->data) &&
((*next)->link != NULL))
next = &(*next)->link;
/* Check for duplicate data. */
if ((*next)->data == nw->data)
printf("Node already in list. \n");
else
/* Check for insert after last node. */
if ((*next)->data < nw->data)
(*next)->link = nw;
else
{
nw->link = *next;
*next = nw;
}
}
/* Void return. */
return;
}
/*¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C*/

/*¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C*/
/* This function deletes a node from a linked list. */
void remove_e(struct node **ptr_to_head, int old)
{
/* Declare variables and function prototypes. */
struct node *next, *last, *hold, *head;
/* Check for delete to empty list. */
head = *ptr_to_head;
if (empty(head))
printf("Empty list. \n");
else
/* Check for deletion of first node. */
{
if (head->data == old)
{
/* Delete first node. */
hold = head;
*ptr_to_head = head->link;
free(hold);
}
else
/* Traverse list to find old node. */
{
next = head->link;
last = head;
while ((next->data < old) && (next->link != NULL))
{
last = next;
next = next->link;
}
/* Delete node if found. */
if (next->data == old)
{
hold = last;
last->link = next->link;
free(hold);
}
else
printf("Value %d not in list. \n", old);
}
}
/* Void return. */
return;
}

int main(void)
{
/* Declare variables and function prototypes. */
int k = 0, old, value;
struct node *head, *next, *previous, *nw, **ptr_to_head = &head;
void insert(struct node **ptr_to_head, struct node *nw);
void remove_e(struct node **ptr_to_head, int n);
int empty(struct node *head);
void print_list(struct node *head);
/* Generate and print a linked list with five nodes. */
head = (struct node *)malloc(sizeof(struct node));
next = head;
for (k = 1; k <= 5; k++)
{
next->data = k * 5;
next->link = (struct node *)malloc(sizeof(struct node));
previous = next;
next = next->link;
}
previous->link = NULL;
print_list(head);
/* Allow user to insert or delete nodes in the list. */
while (k != 2)
{
printf("Enter 0 to delete node, 1 to add node, 2 to quit. \n");
scanf("%d", &k);
if (k == 0)
{
printf("Enter data value to delete: \n");
scanf("%d",&old);
remove_e(ptr_to_head, old);
print_list(head);
}
else
if (k == 1)
{
printf("Enter data value to add: \n");
scanf("%d",&value);
nw = (struct node *)malloc(sizeof(struct node));
nw->data = value;
nw->link = NULL;
insert(ptr_to_head, nw);
print_list(head);
}
}
/* Exit program. */
return 0;
}
/*¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C¨C*/


HOMEWORK:
Quick Sort Program:
#include <stdio.h>

int partition(int a[], int p, int r)
{
int i, j, pivot, temp;
pivot = a[p]; //pivot value is a[initial] = 25
i = p; // i = 0 (initially)
j = r; // j = 7 (initially)
while(1) //while previous statements are true
{ //Start at a[initial]
while(a[i] < pivot && a[i] != pivot) //if the array element is less than & not equal to the pivot...
i++; //...increment i by one, moving to next array element
while(a[j] > pivot && a[j] != pivot) //Starting at a[final], if the array element is greater than &
j--; //not equal to the pivot, then decrement j by one
if(i < j) //if i is less than j...
{ //...and neither of the previous conditions are met...
temp = a[i]; //Set the variable temp equal to the ith array element
a[i] = a[j]; //Set the ith array element equal to the jth array element
a[j] = temp; //Set the jth array element equal to the variable temp
} //In other words... we swap the values a[i] and a[j]
else //if (i !< j) && other conditions are not met...
{
return j; //print out j
}
}
}
/*--------------------------------------------------*/
/* a[] is the array, p is starting index, that is 0,
and r is the last index of array. */
void quicksort(int a[], int p, int r)
{
//printf("Starting Index: %i Ending Index: %i \n", p, r);
if(p < r)
{
int q = partition(a, p, r);
quicksort(a, p, q);
quicksort(a, q+1, r);
}
}

void display(int a[], int size)
{
for (int k=0; k<size; k++)
{
printf("%i ", a[k]);
}
printf("\n");
}

int main(void)
{
int a[] = {25,52,37,63,14,17,8,6};
int n = sizeof(a)/sizeof(a[0]);
printf("Input Array: \t");
display(a, n);
quicksort(a, 0, n-1);
printf("Output Array: \t");
display(a, n);
return 0;

}