C Programming: The linked list implementation covered in lecture allowed for ele

Question

C Programming:

The linked list implementation covered in lecture allowed for elements to only be added and removed from the top (i.e. the end nearest the head). As a result, the link list from class implemented a data structure known as a Stack. Sometimes Stacks are also referred to as “First In Last Out” buffers (i.e. a FILO). This is because items added to the list first will be the last items to be removed

Example________________________________________________________________________________

list.h:

#ifndef _list_h_
#define _list_h_

struct list {
   unsigned int x;
   unsigned int y;
  
   struct list* next;
};

void list init (struct list* head);
unsigned int list_count ( struct list* head);
void list_add_to_head (struct list* head, struct list* new_item);
struct list* list_pop_head (struct list* head);

#endif

list.c:
#include <stdlib.h>
#include "list.h"

void list_int (struct list* head)
{
   head->next = NULL;
}

void list_add_to_head (struct list* head, struct list* new_item)
{
   new_item->next = head->next;
   head->next = new_item;
}

struct list* list_pop_head (struct list* head)
{
   struct list* item;
  
   item = head->next;
  
   if (item != NULL) {
       head->next = item->next;
       item->next = NULL;
   }
   return item;
}

unsigned int list_count (struct list* head)
{
   struct list* item = head;
   int n=0;
  
   while (item->next) {
       n++;
       item = item->next;
   }
   return n;
}

test.c

#include <stdlib.h>
#include <stdio.h>
#include "list.h"

int main (int argc, char** argv)
{
   struct list* head;
   struct list* item;
  
   unsigned int i = 0;
  
   head = malloc(sizeof(struct list));
  
   list_init(head);
  
   for (i=5; i<500; i*= 10) {
       item = malloc(sizeof(struct list));
       item->x = i;
       item->y = 2*i;
       list_add_to_head(head, item);
   }
  
   printf("List contains %u items --- ", list_count(head));
   for (i=0, item = head->next; item != NULL; item = item->next) {
       printf("Item %u: ", i++);
       printf(" x = %u ", item->x);
       printf(" y = %u ", item->y);
   }
  
   printf("List contains %u items --- ", list_count(head));
   for (i=0, item = list_pop_head(head); item != NULL; item = list_pop_head(head)) {
       printf("Item %u: ", i++);
       printf(" x = %u ", item->x);
       printf(" y = %u ", item->y);
       free (item);
   }
  
   printf("List contains %u items ", list_count(head));
   free (head);
   return 0;
}

Another data structure that can be easily implemented using a linked list is a Queue. A Queue is also sometimes referred to as a “First in First Out” buffer (i.e. a FIFO). All you need are a pair of functions: one function should add new items to one end of the list and the other function should remove items from the opposite end of the list. Since you must traverse the entire linked list to find the end, deciding which end to add items to and which end to remove items from really depends on if it is more important for items to be added to the queue quickly or removed from the queue quickly.

Based on the linked list implementation, design a Queue similar to example that is faster at removing items than it is at adding new items.

Explanation / Answer

Modified code to Implement Queue:

List.h

#ifndef _list_h_
#define _list_h_

struct list {
    unsigned int x;
    unsigned int y;
  
    struct list* next;
};

void list_init (struct list* head);
unsigned int list_count ( struct list* head);
void list_add_to_queue (struct list* head, struct list* new_item);
struct list* list_remove_from_queue (struct list* head);

#endif

List.C

#include <stdlib.h>
#include <stdio.h>
#include "list.h"

void list_init (struct list* head)
{
    head->next = NULL;
}

void list_add_to_queue (struct list* head, struct list* new_item)
{
   struct list* item;

   item=head;

   /*while(head->next!=NULL)
   {
       printf("List contains");
       head=head->next;
   }*/
   head->next=new_item;
   new_item->next=NULL;
   new_item->next = head->next;
    head->next = new_item;
   head=item;
}

struct list* list_remove_from_queue (struct list* head)
{
    struct list* item;
  
    item = head;
  
    head=head->next;
    return item;
}

unsigned int list_count (struct list* head)
{
    int n=0;
   struct list* item;
   item=head;
    while (head!=NULL) {
        n++;
        head = head->next;
    }
   head=item;
    return n;
}

Queue.C

#include <stdlib.h>
#include <stdio.h>
#include "list.h"

int main (int argc, char** argv)
{
    struct list* head;
    struct list* item;
  
    unsigned int i = 0;
  
    head =(list *) malloc(sizeof(struct list));
  
    list_init(head);
  
    for (i=5; i<500; i*= 10)
   {
        item =(list *) malloc(sizeof(struct list));
        item->x = i;
        item->y = 2*i;
      
        list_add_to_queue(head, item);

    }
    printf("List contains %u items --- ", list_count(head));
    for (i=0, item = head->next; item != NULL; item = item->next) {
        printf("Item %u: ", i++);
        printf(" x = %u ", item->x);
        printf(" y = %u ", item->y);
    }
  
    printf("List contains %u items --- ", list_count(head));
    for (i=0, item = list_remove_from_queue(head); item != NULL;
       item = list_remove_from_queue(head))
   {
        printf("Item %u: ", i++);
        printf(" x = %u ", item->x);
        printf(" y = %u ", item->y);
        free (item);
    }
  
    printf("List contains %u items ", list_count(head));
    free (head);
   system("pause");
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.