Linked list

[borny86]

Hi I've been asked to convert


PROCEDURE Delete_Record(Key : INTEGER; VAR DB : TBookDB);

[html]

VAR
  i : INTEGER;

BEGIN
  i := 1;
  WHILE DB.Recs[i].Key <> Key DO
  BEGIN
    i := i + 1;
  END;
  DB.Recs[i] := DB.Recs[DB.Size];
  DB.Size := DB.Size - 1;
END {Delete_Record};

{ REQUIRES  TRUE }
{ RESULTS   IF record with key Key in DB
          BorrowerRec' = that record
          RETURNS TRUE
        ELSE
          RETURNS FALSE }

Using linked list


This is what ive done so far

PROCEDURE Delete_Record(Key : INTEGER; VAR DB : TBookDB);

VAR
  Current:TNodePtr;

BEGIN
  Current  := DB.Head;
 WHILE Current<> nil do
 IF Current^.Data.Key = Key THEN
  BEGIN
  Current^.Data = Current^.Data.Key +1;
  END;
  Current^.Data := Current^.Data;
  DB.Size := DB.Size - 1;
 END;

     { REQUIRES  Q_Present(Key, DB)}
{ RESULTS   DB' = DB - [Rec]
           WHERE Get_Key(Rec) = Key)
       AND Get_Size(DB)' = Get_Size(DB) - 1}

Im really stuck it wont work can some1 help me ?

Full code for the unit

{ SmallLibrary.dpr }
{ Ken Brownsey }
{ 19/9/05 }

{$APPTYPE CONSOLE}
PROGRAM SmallLibraryUNITs_AND_LinkedListTest;

uses
  SysUtils,
  Book_Rec in 'Book_Rec.pas',
  Book_DBtest in 'Book_DBtest.pas',
  Prompts in 'Prompts.pas';

{****************************************************
*** START MAIN PROGRAM OPERATIONS                ****
****************************************************}


{ REQUIRES  TRUE}
{ RESULTS   User is prompted for book key Key
       IF Q_Present(Key, BooksDB, _) :
         NOT Q_OK'
         AND user is asked if they want details
         IF they do
           details are printed out
       ELSE
         user prompted for other book details
         AND Q_OK'
         AND Book' is record made from details}
PROCEDURE Read_Book(VAR Book : TBookRec;
                    BooksDB : TBookDB;
                    VAR Q_OK : BOOLEAN);

VAR
  Key : INTEGER;
  Title,
  Author : STRING;
  ExistingBook : TBookRec;
  Q_Details : BOOLEAN;

BEGIN
  Get_Int_From_Prompt('Book key', Key, Q_OK);
  IF Q_OK THEN
  BEGIN
    IF Q_Present(Key, BooksDB, ExistingBook) THEN
    BEGIN
      Q_OK := FALSE;
      WRITELN('Book database already contains book with key ', Get_Key(ExistingBook));
      Get_Bool_From_Prompt_TRUEDefault('Do you want details? ', Q_Details);
      IF Q_Details THEN
      BEGIN
        WRITELN('Book database already contains ', BookTo_String(ExistingBook));
      END
    END
    ELSE
    BEGIN
      Get_String_From_Prompt('Title', Title);
      Get_String_From_Prompt('Author', Author);
      Book := Make_Book(Key, Title, Author);
      Q_OK := TRUE
    END
  END
  ELSE
  BEGIN
    WRITELN('ERROR - Non-numeric string');
  END
END;


{ REQUIRES  TRUE}
{ RESULTS   IF NOT Q_Full(BooksDB)
              user is prompted for new book details
              IF key of new book not key of record in the BooksDB
                BooksDB' = BooksDB + [record of new details]
                AND Get_Size(BooksDB)' = Get_Size(BooksDB) + 1
              ELSE
                message
            ELSE
              message}
PROCEDURE User_Add_BookRecord(VAR BooksDB : TBookDB);

VAR
  NextBook : TBookRec;
  Q_OK : BOOLEAN;

BEGIN
  IF NOT Q_Full(BooksDB) THEN
  BEGIN
    Read_Book(NextBook, BooksDB, Q_OK);
    IF Q_OK THEN
    BEGIN
      Add_Record(NextBook, BooksDB);
    END
  END
  ELSE
  BEGIN
    WRITELN('No room in database!');
  END
END;

{ REQUIRES  TRUE}
{ RESULTS   IF NOT Q_Empty(BooksDB)
              user prompted for Key of record to be deleted
              IF Q_Present(Key, BooksDB)
                BooksDB' = BooksDB - [record with that key]
                AND Get_Size(BooksDB)' = Get_Size(BooksDB) - 1
              ELSE
                message
            ELSE
              message}
PROCEDURE User_Delete_Record_From_BookDB(VAR BooksDB : TBookDB);

VAR
  Key : INTEGER;
  Q_OK : BOOLEAN;
  Dummy : TBookRec;

BEGIN
  IF Get_Size(BooksDB) > 0 THEN
  BEGIN
    Get_Int_From_Prompt('Key of book to be deleted', Key, Q_OK);
    IF Q_OK THEN
    BEGIN
      IF Q_Present(Key, BooksDB, Dummy) THEN
      BEGIN
        Delete_Record(Key, BooksDB);
      END
      ELSE
      BEGIN
        WRITELN('No record with key ', Key, ' in database!');
      END
    END
    ELSE
    BEGIN
      WRITELN('ERROR - Non-numeric string');
    END
  END
  ELSE
  BEGIN
    WRITELN('Database of books is empty!');
  END
END;

{ REQUIRES  TRUE}
{ RESULTS   IF NOT Q_Empty(BooksDB)
         all book records printed to screen
       ELSE
         message}
PROCEDURE User_Print_BookRecords(BooksDB : TBookDB);

BEGIN
  IF NOT Q_Empty(BooksDB) THEN
  BEGIN
    WRITELN(BookDBTo_String(BooksDB));
  END
  ELSE
  BEGIN
    WRITELN('No books');
  END
END;

{ REQUIRES 	TRUE }
{ RESULTS  	Prompts user for file name
     IF file exists
       User prompted for whether to overwrite or not
       IF user chooses to overwrite
         data from book database saved in text format
    ELSE
      data from book database saved in text format}
PROCEDURE User_Save_BookDatabaseTo_TextFile(BooksDB : TBookDB);

VAR
  FileName : STRING;
  Q_Continue : BOOLEAN;
  FileHandle  : TextFile;

BEGIN
  IF NOT Q_Empty(BooksDB) THEN
  BEGIN
    Write('Please type in the name of the file to save to ==> ');
    ReadLn(FileName);
    FileName := FileName + '.txt';
    Q_Continue := TRUE;
    IF FileExists(FileName) THEN
    BEGIN
      Get_Bool_From_Prompt_TRUEDefault(FileName + ' already exist my friend - overwrite? ', Q_Continue);
    END;
    IF Q_Continue THEN
    BEGIN
      AssignFile(FileHandle, FileName);
      Rewrite(FileHandle);
      Save_To_TextFile(BooksDB, FileHandle);
      CloseFile(FileHandle);
    END
  END
  ELSE
  BEGIN
    WRITELN('Empty database - nothing to save!');
  END
END {User_Save_BookDataBaseTo_TextFile};


{ REQUIRES 	TRUE }
{ RESULTS  	Prompts user for file name
     IF file exists
      IF data is text format for TBookRecs
        data from file loaded
        IF not enough room
          message
      ELSE
        exception
    ELSE
      message}
PROCEDURE User_Load_BookDataBaseFrom_TextFile(VAR BooksDB : TBookDB);

VAR
  FileName    : String;
  FileHandle  : TextFile;

  BEGIN
  WRITE('Please type in the name of the file to load ==> ');
  READLN(FileName);
  FileName := FileName + '.txt';
  Initialise(BooksDB);
  IF FileExists(FileName) THEN
  BEGIN
    AssignFile(FileHandle, FileName);
    Reset(FileHandle);
    Load_From_TextFile(BooksDB, FileHandle);
  END
  ELSE
  BEGIN
    WRITELN('No file called ', FileName)
  END
END {User_Load_BookDataBaseFrom_TextFile};

{ REQUIRES  TRUE}
{ RESULTS   Q_Empty(BooksDB'}
PROCEDURE User_ReInitialise(VAR BooksDB : TBookDB);

BEGIN
  WRITELN('Reinitialising the Pooter Small Library');
  Initialise(BooksDB);
END;

{****************************************************
*** END MAIN PROGRAM OPERATIONS                ****
****************************************************}


{****************************************************
*** START TOP LEVEL CONTROL                      ****
****************************************************}

PROCEDURE Menu();

BEGIN
  WRITELN;
  WRITELN('*************Menu ******************************');
  WRITELN('* (z) reinitialise all databases to empty     **');
  WRITELN('* (a)dd book to DB                            **');
  WRITELN('* (w)rite book DB                             **');
  WRITELN('* (d)elete from book DB                       **');
  WRITELN('* (s) save BooksDB to text file             **');
  WRITELN('* (k) load BooksDB from text file           **');
  WRITELN('* (m)enu                                      **');
  WRITELN('* e(x)it                                      **');
  WRITELN('*************Menu*******************************')
END {Menu};


PROCEDURE UserInterfaceLoop(VAR BooksDB : TBookDB);

VAR
  Option : CHAR;
  Q_Exit : BOOLEAN;

BEGIN
  Option := 'm';
  WHILE Option <> 'x' DO
  BEGIN
    CASE Option OF
      'm', 'M' 	: Menu();
      'z', 'Z'  : User_ReInitialise(BooksDB);
      'a', 'A'  : User_Add_BookRecord(BooksDB);
      'w', 'W'  : User_Print_BookRecords(BooksDB);
      'd', 'D'  : User_Delete_Record_From_BookDB(BooksDB);
      's', 'S'  : User_Save_BookDataBaseTo_TextFile(BooksDB);
      'k', 'K'  : User_Load_BookDataBaseFrom_TextFile(BooksDB);
    ELSE
      WRITELN('Unidentified option')
    END;
    WRITELN;
    WRITE('Next option please ==> ');
    ReadLn(Option);
    IF Option = 'x' THEN
    BEGIN
      Get_Bool_From_Prompt_FALSEDefault('Do you really want to exit ? ', Q_Exit);
      IF NOT Q_Exit THEN
      BEGIN
        Option := 'm';
      END
    END
  END
END {Main_Loop};


{ REQUIRES	TRUE }
{ RESULTS   Finalisation process executed }
PROCEDURE Finalise();

BEGIN
  WRITELN('YOU COULD ADVERTISE YOUR PRODUCTS HERE - e-mail kwb@brookes.ac.uk');
  READLN
END {Finalise};

{****************************************************
*** END TOP LEVEL CONTROL                        ****
****************************************************}

{****************************************************
*** MAIN PROGRAM                                 ****
****************************************************}

VAR
  BookLib : TBookDB;

BEGIN
  Initialise(BookLib);
  UserInterfaceLoop(BookLib);
  Finalise();
END {SmallLibrary}.

If someone could help me I would be so grateful.

[WingedPanther]

You have included some data types without definition, such as TBookDB and TBookRec. Not knowing their properties makes it difficult to know what is going wrong. However,
BEGIN
Current^.Data = Current^.Data.Key +1;
END;
looks very suspicious. It should probably be something like:
BEGIN
Current^.Data = Current^.Data.Next;
END;

[borny86]

Thanks for the reply.

The program is diveded in to 3 units. Prompts,TBOOK_rec and TBookdb.

TYPE
  TNodePtr = ^TNode;

  TNode = RECORD
    Data : TBookRec;
    Next : TNodePtr;
  END;

  TBookDB = RECORD
    Head : TNodePtr;
    Size : INTEGER;
  END;

From TBook_DB unit

TYPE
  TBookRec = RECORD
    Key : INTEGER;
    Title : STRING;
    Author : STRING;
  END;

From TBook_REC unit


I tried using Current^.Data := Current^.Current.Next; but still dosent work.


There seem to be a problem in

While Current^.Data.Key <> Key Do

that code should represent

WHILE DB.Recs[i].Key <> Key DO

But it dosent work, it just skips.

[WingedPanther]

Have you done a trace on your code to monitor the values of Key and Current^.Data.Key?

[WingedPanther]

Also, I don't see While Current^.Data.Key <> Key Do in the code you've pasted in.

[borny86]

Ok, ive realised that after i was tracing it, I was writing the code the wrong way.

It should be

PROCEDURE Delete_Record(Key : INTEGER; VAR DB : TBookDB);

Var previous,current:TnodePtr;

  Begin
    IF DB.Head^.Data.Key = Key then
    dispose(DB.Head)
    Else
    begin
     previous := DB.Head;
     current := DB.Head^.Next;
    WHILE Current^.Data.Key <> Key do
        previous := current;
        current := current^.next;
    end;
    previous^.next := current^.next;
    dispose(current);
END {Delete_Record};

Post conditions
{ REQUIRES Q_Present(Key, DB)}
{ RESULTS DB' = DB - [Rec]
WHERE Get_Key(Rec) = Key)
AND Get_Size(DB)' = Get_Size(DB) - 1}


Im getting so annoyed with this code.

It wont work, ive traced it, and it goes in a endless loop in WHILE

Current^.Data.Key <> Key do
        previous := current;
        current := current^.next;

Its really hard to explain as it is quiet complex, any chance I can sen dyou the source code(Units & Including main program) in order for you to take a look at it?
I need to get it done before the weekend ..

Thanks for the help give so far.

[borny86]

Also While Current^.Data.Key <> Key is suppose to find the number of the record that is to be deleted. I did manage that in the end, but I need to know the previous node in order to delete and link up the pointers.

The whole point of the procedure is to find and match up the key entred by the user to the record stored, and then delete it, using pointer (linked list).

The code that was previously given

VAR
  i : INTEGER;

BEGIN
  i := 1;
  WHILE DB.Recs[i].Key <> Key DO
  BEGIN
    i := i + 1;
  END;
  DB.Recs[i] := DB.Recs[DB.Size];
  DB.Size := DB.Size - 1;
END {Delete_Record};

were using Arrays rather than linked list.

[WingedPanther]

If you post the source I should be able to take a look at it. I may not be able to help much without data to test against, however. I've written a lot of "brilliant" code that failed because the data wasn't what I expected it to be.

[borny86]

thanks for the help, ive managed to solve the problem now.

it was a problem with the while loop and I had to add a if statement,thanks.

/Borny

[WingedPanther]

glad to hear you got it fixed