tradlink.c

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct thing
{
  char* item;
  struct thing* next;
} thing;

// create new list element of type 'thing' from the supplied text string
thing*
newelement(char* text)
{
  thing* newp = malloc(sizeof *newp);
  newp->item = (char*)malloc(strlen(text) + 1);
  strcpy(newp->item, text);
  newp->next = NULL;
  return newp;
}

// delelement: remove from list the first instance of an element
// containing a given text string
// NOTE!! delete requests for elements not in the list are silently ignored
thing*
delelement(thing* head, char* text)
{
  thing *prev = NULL;
  for (thing* p = head; p != NULL; p = p->next) {
    if (strcmp(text, p->item) == 0) {
      if (prev == NULL)
        head = p->next;
      else
        prev->next = p->next;
      free(p->item); // free off the the string field
      free(p);       // remove rest of thing
      break;
    }
    prev = p;
  }
  return head;
}

/* addfront: add new thing to front of list  */
thing*
addfront(thing* head, thing* newp)
{
  newp->next = head;
  return newp;
}

/* addend: add new thing to the end of a list  */
thing*
addend(thing* head, thing* newp)
{
  if (head == NULL)
    return newp;
  thing* p = head;
  // now find the end of list
  while(p->next) {
    p = p->next;
  }
  p->next = newp;
  return head;
}

// add element into middle of a list of 'things' based on alphabetical order
// of the 'item' strings within the 'thing' structures
thing*
addmiddle(thing* head, thing* newp)
{
  if (head == NULL) {
    return addfront(head, newp);
  }
  // Main loop. Use p2 to remember previous p1
  thing *p1, *p2;
  p2 = p1 = head;
  bool found = false;
  while (!found) {
    found = !!(strcmp(p1->item, newp->item) >= 1);
    if (found) {
      if (p1 == head) {
        return addfront(head, newp);
      } else {
        p2->next = newp;
        newp->next = p1;
        return head;
      }
    }
    // match not found before end of list so insert at end
    if (p1->next == NULL) {
      return addend(head, newp);
    }
    p2 = p1;
    p1 = p1->next;
  }
  return NULL;
}

void
printlist(thing* list)
{
  while (list != NULL) {
    printf("%s \n", list->item);
    list = list->next;
  }
}

int
main()
{
  thing* start = NULL;
  start = addmiddle(start, newelement("chips"));
  start = addmiddle(start, newelement("wine"));
  start = addmiddle(start, newelement("beer"));
  start = addmiddle(start, newelement("pizza"));
  start = addmiddle(start, newelement("zucchini"));
  start = addmiddle(start, newelement("burgers"));
  start = addmiddle(start, newelement("burgers"));
  start = addmiddle(start, newelement("slaw"));
  printf("Initial List:\n");
  printf("-------------\n");
  printlist(start);

  printf("\nRemoving 'pizza', 'zucchini' and 'burgers':\n");
  printf("-------------------------------------------\n");
  start = delelement(start, "pizza");
  start = delelement(start, "zucchini");
  start = delelement(start, "burgers");
  printlist(start);
}