Monash University > CSSE > CSE1303 > Part A > Lectures > Lecture A05 notes

CSE1303 Computer Science
Semester 3 (summer), 2003
Part A
Lecture A05 notes: Basic Data Structures - Lists

In this lecture

• Kruse 4.5, 4.6, 4.8
• Deitel & Deitel (2e) 12.1, 12.2, 12.4
• Standish 8.1 - 8.4
• Langsam 4.2 - 4.5
• King 17.5

• An ADT is the data structure along with the functions/operations that can manipulate that structure.
• Led to the development of Object Oriented Programming.
• Stacks, Queues, Lists, Trees, Databases, Rational Numbers, Unions, and Strings are all examples of ADTs.

• Procedural - decide what procedures you require.
• Modular - decide which modules you require, hide data in modules.
• Data abstraction - decide which types you want, describe those types and the operations on those types completely.
• Object Oriented - decide which classes you want, provides inheritance for commonality between classes.

• Is the list empty?
• Is the list full?
• How many elements are in the list?
• Initialize the list.
• Insert item at a position in the list.
• Delete item at a position in the list.
• Retrieve item at a position in the list.
• Replace item at a position in the list.

Comparison with Stacks and Queues:

• Insertions and deletions can be made at any point of the list.
• Stacks need to keep track of the top.
• Queues need to keep track of the front and the rear.
• Lists use position numbers to determine where operations should take place.

• The maximum size of the list must be given.
• Insertions and deletions involving a lot of copying of items.

• The maximum size of the list must be given.
• Insertions and deletions are easier than in the simple implementation.
• Several different implementations are used.
• Used for memory management in some operating systems.

Code for this lecture

/* list.h */
#ifndef LISTH
#define LISTH

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

#define MAXLIST 10

struct ListRec
{
	char list[MAXLIST];
	int count;
};

typedef struct ListRec List;

void Initialise(List *lptr);
void Insert(List *lptr, char item);
void Delete(List *lptr, int pos);
bool IsFull(List *lptr);
bool IsEmtpy(List *lptr);
int  Find(List *lptr, char item);

/* and any more functions you can think of) */

#endif

/* partial list.c */
#include <stdio.h>
#include "list.h"

void Initialise(List *lptr)
{
	lptr->count = 0;
}

bool isFull(List * lptr)
{
	if(lptr->count == MAXLIST)
		return true;
	else
		return false;
}

bool isEmpty(List *lptr)
{
	if(lptr->count == 0)
		return true;
	else
		return false;
}

void Insert(List *lptr, char item){
	int pos, current;

	if(IsFull(lptr))
	{
		fprintf(stderr, "List is full.");
		exit(1);
	}

	for(pos = 0; pos < lptr->count; pos++)
	{
		if(lptr->list[pos] > item)
			break;
	}

	current = lptr->count - 1;
	while (current >= pos)
	{
		/* Copy the element into the next position along */
		lptr->list[current+1] = lptr->list[current];
		current--;
	}
	lptr->list[pos] = item;
	lptr->count++;
}

/* llist.h */
#ifndef LLISTH 
#define LLISTH 

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

#define MAXLIST 10

typedef struct EntryRec
{
	char ch;
	int next;
} Entry;

typedef struct LinkedListRec
{
	Entry list[MAXLIST];
	int count;
	int start;
} LList;

void Initialise(LList *lptr);
void Insert(LList *lptr, char item);
void Delete(LList *lptr, int pos);
bool IsFull(LList *lptr);
bool IsEmtpy(LList *lptr);
int  Find(LList *lptr, char item);

/* and any more functions you can think of) */

#endif

/* partial llist.c */
#include <stdio.h>
#include "llist.h"

void Initialise(LList *lptr)
{
	lptr->count = 0;
	lptr->start = -1;
}

bool isFull(LList *lptr)
{
	if(lptr->count == MAXLIST)
		return true;
	else
		return false;
}

bool isEmpty(LList *lptr)
{
	if(lptr->count == 0)
		return true;
	else
		return false;
}

void Insert(LList *lptr, char item)
{
   int current, previous;

   if(IsFull(lptr)) 
   {
      fprintf(stderr, "Linked List is full.");
      exit(1);
   }

   lptr->list[lptr->count].ch = item;
   current = lptr->start;
   previous = -1;

   if (IsEmpty(lptr)) 
   {
      lptr->list[0].next = -1;
      lptr->start = 0;
   }
   else 
   {
      while(current!=-1 && lptr->list[current].ch < item) 
      {
         previous = current;
         current = lptr->list[current].next;
      }
      if (previous==-1) 
      { 
         lptr->list[lptr->count].next=lptr->start;
         lptr->start=lptr->count;
      }
      else 
      {                 
         lptr->list[lptr->count].next = lptr->list[previous].next;
         lptr->list[previous].next = lptr->count;
      }
   }
   lptr->count++;
}

[ Top | Home ]
Last Updated: Tuesday 02 December 2003 22:29:28