/******************************************************************************
BBM201 - Week 7
Example code
*******************************************************************************/
#include <stdio.h>
#include <string.h>
#define MAX_LIST 6
#define TRUE 1
#define FALSE 0
#define NULL -1
typedef struct{
char name[5];
//other fields
int link;
} item;
item linkedlist[MAX_LIST];
int first;
int free_;
void initialise()
{
first = NULL;
free_ = 0;
for (int i = 0; i < MAX_LIST; i++)
linkedlist[i].link = i + 1;
linkedlist[MAX_LIST - 1].link = NULL;
}
int get_free_slot(int* slot) {
if (free_ == NULL) // All slots are occupied
return FALSE;
else // Return the first free slot
*slot = free_;
return TRUE;
}
int find_item(char name[]) {
if (first == NULL) // list is empty
return NULL;
else { // iterate over items
for (int p = first; p != NULL; p = linkedlist[p].link)
if (strcmp(linkedlist[p].name, name) == 0)
return p;
}
return NULL;
}
int insert_item(char name[]) {
int free_slot;
if (get_free_slot(&free_slot)) { // get_free_slot successful
strcpy(linkedlist[free_slot].name, name);
free_ = linkedlist[free_slot].link;
int p = first;
int prev = NULL;
while (p != NULL && strcmp(linkedlist[p].name, name) < 0) {
prev = p;
p = linkedlist[p].link;
}
if (prev == NULL) { // Insert as the first item
linkedlist[free_slot].link = first;
first = free_slot;
} else {
linkedlist[free_slot].link = p;
linkedlist[prev].link = free_slot;
}
printf("Item %s inserted. \n", name);
return TRUE;
}
else {
// No free slot exists
printf("No free slot exists.\n");
return FALSE;
}
}
int delete_item(char name[]) {
int p = first;
int prev = NULL;
while (p != NULL && strcmp(linkedlist[p].name, name) != 0) {
prev = p;
p = linkedlist[p].link;
}
if (prev == NULL) // Deleting the first item
first = linkedlist[first].link;
else if (p != NULL) // Deleting normal item
linkedlist[prev].link = linkedlist[p].link;
else
return FALSE;
linkedlist[p].link = free_;
free_ = p;
return TRUE;
}
void print_list() {
for(int i = 0; i < MAX_LIST; i++)
{
char title[] = "+-+-----+ ";
if (i == first)
title[4] = 'f';
if (i == free_)
title[4] = '0';
printf("%s", title);
}
printf("\n");
for(int i = 0; i < MAX_LIST; i++)
printf("| |%-5s| ", linkedlist[i].name);
printf("\n");
for(int i = 0; i < MAX_LIST; i++)
printf("|%d|-----| ", i);
printf("\n");
for(int i = 0; i < MAX_LIST; i++)
printf("| |->%3d| ", linkedlist[i].link);
printf("\n");
for(int i = 0; i < MAX_LIST; i++)
printf("+-+-----+ ");
printf("\n");
printf("\n");
}
void main(void)
{
initialise();
insert_item("A1");
print_list();
insert_item("B1");
insert_item("C1");
insert_item("D1");
insert_item("E1");
insert_item("F1");
insert_item("G1");
print_list();
printf("delete %s -> %d\n", "G1", delete_item("G1"));
print_list();
printf("delete %s -> %d\n", "F1", delete_item("F1"));
print_list();
insert_item("G1");
print_list();
printf("delete %s -> %d\n", "C1", delete_item("C1"));
print_list();
insert_item("A2");
print_list();
printf("delete %s -> %d\n", "A1", delete_item("A1"));
print_list();
}
