Lists

A popular type of project for A2 coursework is a database built from scratch. For each table, data is stored in an array of records which is saved to a file of records. Records in the one-dimensional array (list) are searched for, deleted, edited and sorted. New records may be created then inserted. The projects include visual programming in Delphi, but algorithms for searching, sorting, inserting, deleting, loading and saving do not require visual components and you can test their implementation in Pascal. Program ListDemo demonstrates typical basic routines required by such a project. We encourage you to include more efficient searching and sorting methods in your programs.

Program ListDemo is a prototype designed to store details of student programs contributed to this website and a test file (Progs.txt) available for download contains actual data. We store only the program name, programmer ID and program ID in this prototype. The following notes should help you to understand the code for some key procedures.

Procedure InsertRecord finds the position of the record based on its ID and moves all records with a greater ID up by one place in the array to make room for it. The search is conducted downwards for greater efficiency; records are shifted as the search proceeds.

Procedure Find employs a linear search and changes the variable parameter FoundRecord accordingly.

Procedure Delete calls the Find procedure and then if the record is found, deletion is achieved by decrementing the index of each record with a greater ID.

Procedure BubbleSort repeatedly compares adjacent pairs of record IDs and swaps the indices of the records if they are in the wrong order. A temporary record is needed to perform the swap. The first pass through the array ensures that the record with the greatest ID is correctly positioned with the maximum index. The next pass positions the penultimate record correctly, and so on. The variable LastCompare is decremented after each pass so that unnecessary comparisons are avoided. Comparisons are made up to the index LastCompare, provided that a swap was necessary on the preceding pass through the array.

Note that for the bubble sort, your code should take advantage of the fact that most of the code is the same regardless of the sort field. We use the following case statement in Program ListDemo so that we can extend the sort option to any number of sort fields.

case ChosenField of
  1: SwapNeeded := Programs[Count].ProgName > Programs[Count + 1].ProgName;
  2: SwapNeeded := Programs[Count].ProgramID > Programs[Count + 1].ProgramID;
end;


program ListDemo;
  {$APPTYPE CONSOLE}
uses
  SysUtils, StrUtils;
type
  TProg = record
    ProgramID : integer;
    ProgName : string[15];
    ProgrammerID : integer;
    Dummy : integer;  //to make this compatible with LinkedListDemo
  end;
const
  FILENAME = 'Progs.txt';
  MAX = 20;
var
  LastRecord, FoundRecord,  Choice, SelectedID : integer;
  Programs : array[1..MAX] of TProg;

procedure InsertRecord(InsertID : integer);
var
  Inserted : Boolean;
  TempRecord : TProg;
  CurrentRecord : integer;
begin
  Inserted := False;
  TempRecord.ProgramID := InsertID;
  write('Program Name? ');
  readln(TempRecord.ProgName);
  write('Programmer ID? ');
  readln(TempRecord.ProgrammerID);

  if LastRecord = 0 then
    begin
      Programs[1] := TempRecord;
      LastRecord := 1;
      writeln('Record added.  No others in list.');
    end
  else
    begin
      CurrentRecord := LastRecord;
      inc(LastRecord);
      while (CurrentRecord > 0) and not Inserted do
        begin
          if TempRecord.ProgramID > Programs[CurrentRecord].ProgramID then
            begin
              Programs[CurrentRecord + 1] := TempRecord;   //No shift needed
              Inserted := True;
              writeln('Record inserted at position ', CurrentRecord + 1);
            end
          else
            begin
              //Shift record one place
              Programs[CurrentRecord + 1] := Programs[CurrentRecord];
              dec(CurrentRecord);
            end;
        end;
      if not Inserted then
        begin
          Programs[1] := TempRecord;
          writeln('Record inserted at position 1');
        end;
    end;
end;

procedure DisplayRecord(RecNo : integer);
begin
  writeln(' Program ID: ', Programs[RecNo].ProgramID,
          '   Name: ', Programs[RecNo].ProgName,
          DupeString(' ', 14 - Length(Programs[RecNo].ProgName)),
          'Programmer ID: ', Programs[RecNo].ProgrammerID);
end;

procedure DisplayRecords;
var
  Count : integer;
begin
  if LastRecord = 0 then
    writeln('No records to display')
  else
    begin
      for Count := 1 to LastRecord do
        DisplayRecord(Count);
    end;
end;

procedure Find(ProgID: integer; var FoundRecord : integer);
var
  CurrentRecord : integer;
  Found : Boolean;
begin
  Found := False;
  if LastRecord = 0 then
    writeln('No records to search')
  else
    begin
      CurrentRecord := 1;
      repeat
        if Programs[CurrentRecord].ProgramID = ProgID then
          begin
            Found := True;
            FoundRecord := CurrentRecord;
            DisplayRecord(FoundRecord);
          end
        else
          inc(CurrentRecord);
      until Found or (CurrentRecord = LastRecord + 1);
      if not Found then
        begin
          FoundRecord := 0;
          writeln('Not found');
        end;
    end;
end;

procedure Delete(DeleteID : integer);
var
  Count : integer;
begin
  Find(DeleteID, FoundRecord);
  if FoundRecord <> 0 then
    begin
      dec(LastRecord);
      for Count := FoundRecord to LastRecord do
        Programs[Count] := Programs[Count + 1];
      writeln('Deleted');
    end;
end;

procedure Edit(EditID : integer);
var
  Response : char;
begin
  Find(EditID, FoundRecord);
  if FoundRecord <> 0 then
    begin
      write('Would you like to change the name y/n? ');
      readln(Response);
      if Response in ['Y', 'y'] then
        begin
          writeln('What should the name be? ');
          readln(Programs[FoundRecord].ProgName);
          writeln('New name entered');
        end;
      write('Would you like to change the programmer ID y/n? ');
      readln(Response);
      if Response in ['Y', 'y'] then
        begin
          writeln('What should the ID be? ');
          readln(Programs[FoundRecord].ProgrammerID);
          writeln('New ID entered');
        end;
    end;
end;

procedure BubbleSort(ChosenField : integer);
var
  NoSwaps, SwapNeeded : Boolean;
  Count, LastCompare : integer;
  TempRecord : TProg;
begin
  if LastRecord = 0 then
    begin
      writeln('No records to sort');
    end
  else
    begin
      if LastRecord = 1 then
        begin
          writeln('Cannot sort 1 record.')
        end
      else
        begin
          NoSwaps := False;
          LastCompare := LastRecord;
          while NoSwaps = False do
            begin  //start of loop comparing pairs of names
              NoSwaps := True;
              Count := 1;
              while (Count < LastCompare) do
                begin
                  case ChosenField of
                    1: SwapNeeded := Programs[Count].ProgName > Programs[Count + 1].ProgName;
                    2: SwapNeeded := Programs[Count].ProgramID > Programs[Count + 1].ProgramID;
                  end;
                  if SwapNeeded then
                    begin
                      NoSwaps := False;
                      TempRecord := Programs[Count + 1];
                      Programs[Count + 1] := Programs[Count];
                      Programs[Count] := TempRecord;
                      writeln('Swapping ', Count,' with ', Count + 1);
                    end
                  else  //No swap
                    begin
                      inc(Count);
                    end;
              end;//while
              dec(LastCompare);
            end; //while NoSwaps = False;
        end;
    end;
end;

procedure Init;
begin
  LastRecord := 0;
end;

procedure SaveRecords;
var
  ProgFile : file of TProg;
  Count : integer;
begin
  if LastRecord = 0 then
    writeln('No records to save')
  else
    begin
      assignFile(ProgFile, Filename);
      rewrite(ProgFile);
      for Count := 1 to LastRecord do
        write(ProgFile, Programs[Count]);
      closeFile(ProgFile);
    end;
end;

procedure LoadRecords;
var
  ProgFile : file of TProg;
begin
  assignFile(ProgFile, FILENAME);
  reset(ProgFile);
  LastRecord := 0;
  while not eof(Progfile) do
    begin
      inc(LastRecord);
      read(ProgFile, Programs[LastRecord]);
    end;
  closeFile(ProgFile);
end;

begin
  Init;
  repeat
    writeln(#13#10'Please type the number of your choice.');
    writeln('1 - Insert a record');
    writeln('2 - Save records');
    writeln('3 - Load records  (requires Progs.txt)');
    writeln('4 - Display records');
    writeln('5 - Find a record');
    writeln('6 - Edit a record');
    writeln('7 - Delete a record');
    writeln('8 - Sort by program name');
    writeln('9 - Sort by program ID');
    writeln('10 - Quit');
    readln(Choice);
    case choice of
      1 : begin
            write('Which program ID would you like to insert? ');
            readln(SelectedID);
            InsertRecord(SelectedID);
          end;
      2 : begin
            writeln('Saving records');
            SaveRecords;
          end;
      3 : begin
            writeln('Loading records');
            LoadRecords;
          end;
      4 : DisplayRecords;
      5 : begin
            write('What is the ID of the record to find? ');
            readln(SelectedID);
            Find (SelectedID, FoundRecord );
          end;
      6 : begin
            write('What is the ID of the record to edit? ');
            readln(SelectedID);
            Edit(SelectedID);
          end;
      7 : begin
            write('What is the ID of the record to delete? ');
            readln(SelectedID);
            Delete(SelectedID);
          end;
      8 : begin
            writeln('Sorting records');
            BubbleSort(1);
          end;
      9 : begin
            writeln('Sorting records');
            BubbleSort(2);
          end;
    end;//case
  until Choice = 10;
end.

Experimenting with Lists

  1. Add the following to program ListDemo:
    • procedure AppendRecord to add a record to the end of the list;
    • a bubble sort for the ProgrammerID field;
    • procedure QuickSort to execute a more efficient sort than a bubble sort;
    • procedure BinarySearch to execute a more efficient search than a linear search.
  2. Write a similar program for your own list of records. You could, for example, process contact details, books, music collections or films.
Programming - a skill for life!

Introduction to lists (including arrays of records), linked lists, stacks and queues