Procedural Programming Languages

Assignment: Dynamically Allocated Linked Lists

Assignment Objectives

You should demonstrate that you can:

·        use published work to analyse the problem and identify and specify the required operations

·        reference published work

·        design appropriate data structures and operations

·        use functional decomposition diagrams to document control structures

·        use C/C++, or any other appropriate programming language, to implement your designs

·        devise appropriate test cases and apply and document them

·        build a library file

·        report on your work clearly and concisely

Introduction

Dynamically allocated variables are variables that do not exist when the program is loaded, but are created dynamically by the program as they are needed. By definition therefore these variables only exist at run-time. Thus it is possible, by using these techniques, to create as many variables as needed, use them, and when they are no longer needed deallocate their space for use by other variables

 

Before discussing memory allocation it is worth spending some time to explain some related terms such as heap and segmentation. All program code ultimately executes in the physical memory of a computer. The code is in binary format and it is the job of the compiler to convert our source code into an executable binary format for the hardware that we are using. Every compiler has a set of limitations on it as to how big the executable file can be, how many variables can be used, how long the source file can be, etc. The original IBM PC had a data bus which was 16 bits wide. As a result these computers use a microprocessor with a 64K segment size (216=64K), and they require special calls to use data outside of a single segment.

 

Text Box: One limitation placed on users by most MS-DOS C compilers is a limit of 64K for the executable code if you happen to be in the small memory model. In order to keep the program small and efficient, these calls are not used in some MS-DOS implementations of C, and the memory space is limited though it is still adequate for most programs.

 

A heap is an area outside of this 64K boundary which can be accessed by the program to store data and variables. Thus the heap is outside the segment that the code is in and access to the heap is through an inter-segment jump. The data and variables are put on the heap by the system as calls to malloc() are made. The system keeps track of where the data is stored.

 

During the course of the program execution data and variables can be deallocated and this will cause memory fragmentation or in simple terms it will cause holes in the heap. The system knows where the holes are and will use them for additional data storage as more malloc() calls are made. The structure of the heap is therefore a very dynamic entity, changing constantly.

 

 

Most C compilers give the user a choice of memory models to use. The user has a choice of using a model with a 64K limitation for either program or data leading to a small fast program or selecting a 640K limitation and requiring longer address calls leading to less efficient addressing.

 

Using the larger address space requires inter segment addressing, resulting in the marginally slower execution speed. Quite apart from the speed difference which at current processor speeds may be insignificant, there are other considerations. Namely, if a program uses less than 64K bytes of memory code and memory and if it does not use a stack, it can be made into a .COM file.

Since a .COM file is already in a memory image format, it can be loaded very quickly whereas a file in an .EXE format must have its addresses relocated as it is loaded, which slows it down. Therefore a tiny memory model can generate a program that loads faster than one generated with a larger memory model.

 

Just a reminder here, that a stack is an area in memory reserved for saving and retrieving data needed by the program as it is executing. The information stored usually consists of registers that need to be retrieved, for example following an interrupt etc.

 

Using dynamic allocation, it is possible to store the data on the heap and that may be enough to allow you to use the small memory model. Of course, you wouldn't store local variables such as counters and indexes on the heap, since the intra-segment jump overhead would not be justified for these variables. Where it will be necessary to use dynamic allocation is in very large arrays or structures.

The impact of dynamic allocation can be appreciated when programming data storage that occurs at different times in the program, and consequently allowing us to share the same area of memory for all data. Thus for example, if you had a program that used several large data storage areas, but not at the same time, you could load one block storing it dynamically, then overwrite the space with the next large block of data. Dynamically storing each block of data in succession, and using the same storage for each block may allow you to run your entire program in the computer without breaking it up into smaller programs.

 

A LINKED LIST

 

We finally come to linked lists, which is considered by some as the most challenging of all programming techniques. A simple example of an application of dynamically allocated linked lists is the file allocation table (FAT) used in DOS and Windows operating systems.

 

FAT 16 for example has 216=64K locations each 16-bit wide, that are used to store pointers to blocks which make up a file. Thus the locations do not store data blocks that belong to a file but rather they contain pointers linking one block to the next until the complete file is linked by however many blocks there are. Therefore, if say the standard size of the block was 512 bytes, then the FAT segment in the diagram would hold pointers to a file that was 10*512=5,120 bytes in size.

 

Clearly, the FAT would be able to hold information for more than one file and the file pointers that belong to any particular file do not need to be in consecutive locations.

 

The largest amount of data that could be stored in the FAT shown here is approximately (216 * 29=225=32Mb). I say approximately because the first two pointers in the FAT are in fact used for disk information and therefore not available. To a programmer therefore linked lists are simply another programming technique made up of simple components that can be a powerful tool.

 

Assignment Requirements

You should create an abstract data type for a dynamically allocated linked list.  This will include the data structure and operations to be performed on the list.

 

You are given the following example of a linked list that you can use as a basis for your own design.

 

Example Linked List:

Consider the following program as an example of linked lists.

 

 

#include "stdio.h"    /* this is needed to define the NULL     */

#include "string.h"

#include "stdlib.h"

#define RECORDS 6

 

void main()

{

struct animal {

   char name[25];   /* The animals name                       */

   char breed[25];  /* The type of animal                  */

   int age;         /* The animals age                       */

   struct animal *next; /* pointer to next record of this type */

} *point, *start, *prior; /* this defines 3 pointers  */

int index;

 

             /* the first record is always a special case */

 

   start = (struct animal *)malloc(sizeof(struct animal));

   strcpy(start->name,"General");

   strcpy(start->breed,"Mixed Breed");

   start->age = 4;

   start->next = NULL;

   prior = start;

 

/* a loop can be used to fill in the rest once it is started */

 

   for (index = 0;index < RECORDS;index++) {

      point = (struct animal *)malloc(sizeof(struct animal));

      strcpy(point->name,"Frank");

      strcpy(point->breed,"Laborador Retriever");

      point->age = 3;

      prior->next = point;/* point last "next" to this record */

      point->next = NULL;/* point this "next" to NULL        */

      prior = point;        /* this is now the prior record  */

   }

 

       /* now print out the data described above */

 

   point = start;

   do {

      prior = point->next;

      printf("%s is a %s, and is %d years old.\n", point->name,

              point->breed, point->age);

      point = point->next;

   } while (prior != NULL);

 

 /* good programming practice dictates that we free up the */

 /* dynamically allocated space before we quit.            */

 

   point = start;            /* first block of group      */

   do {

      prior = point->next;   /* next block of data        */

      free(point);           /* free present block        */

      point = prior;         /* point to next             */

   } while (prior != NULL);  /* quit when next is NULL    */

}

 

 

 

/* Result of execution

 

General is a Mixed Breed, and is 4 years old.

Frank is a Laborador Retriever, and is 3 years old.

Frank is a Laborador Retriever, and is 3 years old.

Frank is a Laborador Retriever, and is 3 years old.

Frank is a Laborador Retriever, and is 3 years old.

Frank is a Laborador Retriever, and is 3 years old.

Frank is a Laborador Retriever, and is 3 years old.

 

*/

 

 

 

 

The assignment is divided into two phases, roughly equivalent to specification and design (phase 1) and implementation and testing (phase 2):

 

Phase 1:

·        Design a dynamically allocated structure that would identify computers on your network and for each computer specify  a computer account name (ie eent3), the operating system running on it (i.e Win98, Me, XP, 2000 etc) and also its CPU speed (ie 850 Mhz)

·        describe your linked list

 

Phase 2:

·        translate the data structures into C/C++

·        design the operations, documenting them using functional decomposition diagrams

·        implement and test your programme, identifying clearly your testing procedure

What you should hand in:

Both Phases of your assignment should be handed in together by Friday of week 12.

 

The report should however contain both phases, clearly identifiable, so that a separate mark can be suitably given to each.

You should provide a list of references for each phase and indicate in the text where you have used them.  Each phase should be in the form of a report on your work, listing any assumptions you made; giving an account of how you went about the work and justifying the decisions you made as well as the requirements listed below.

 

Phase 1: Maximum Length: 5 sides A4 (10%)

Design and description

Phase 2: Maximum Length: 10 sides A4 + listing (20%)

·        functional decompositions of the operations

·        full listing (including comments) of the code

·        evidence of testing

Deliverables for the coursework component:

  1. Log-book: All the lab exercises with dates. The log-book should have a structure to it: For example: Date:, Activity type:, discussions of problems encountered/solved, concluding remarks. This should be kept for every week of laboratory activity.

Work on your assignment and design considerations and trials to be documented in a log-book

 

  1. Formal report: A report including the planning, design and implementation details. It should include all the components of a formal report i.e.

Total For Assignment 1 (50 marks)

 

Over-length work will be penalised

Hand-in Dates:

Phase 1+2:                               Friday  teaching week 12