IC2DA
S.B. Bosch C Programmeren
Programma-dossier WordStore Het ontwerpen en programmeren van de library WordStore.h
Ontvangen probleemstelling Voorwoord Er werd van ons verwacht een eigen versie van de module WordStore te te ontwikkelen in ANSI-C die weer gebruikt kan worden voor algemene doeleinden. Voor deze module is de header file gegeven. De module moet intern gebruik maken van een cylische dubbel gelinkte lijst. Ook de ander leerstof die aan bod is gekomen in de les komt terug in de functies, zoals functies die gebruik maken van call by value en call by reference, pointers, dynamisch geheugen vrij maken en geheugen weer vrijgeven.
Opgave Voor het uitwerken van de oefening was ik verplicht me te houden aan de opgegeven randvoorwaarden. De header file van WordStore.h moest precies op deze manier geimplementeerd worden en de beschrijving van de eindopdracht moest gevolgd worden.
Werkplan Programmaspecificaties De module moet voldoen aan de volgende specificatie: /*************************************/ /** **/ /** File: WORDSTORE.H **/ /** Author: F.H.J. Feldbrugge **/ /** Version: 1.0 **/ /** Date: Aug 12, 2001 **/ /** **/ /*************************************/ #ifndef WORDSTORE_H #define WORDSTORE_H #include "Boolean.h" #define MAXLEN_WORD 20 /* ** WordStore can be seen as a circular list of words. ** There is a virtual pointer, dubbed Current Word, which points to ** one of the words in the list (if the list is non-empty). */ void WordStore_Clear (void); /* ** Removes all words from WordStore. ** pre: ** post: WordStore_NrWords == 0 */ Boolean WordStore_FileRead (char sFileName[]); /* ** Reads all non-empty words from the file with name sFileName and ** inserts these words to WordStore (see function WordStore_WordInsert ** for a description of how a word is inserted). ** pre: sFileName contains syntactically valid file name. ** post: WordStore_FileRead (f) == TRUE ** ==> all words of file added to WordStore. */ Boolean WordStore_FileWrite (char sFileName[]); /* ** Writes all words (from the Current Word onwards) to a file with ** name sFileName. If the file could not be opened or created, ** the value FALSE is returned, TRUE otherwise. ** pre: sFileName contains syntactically valid file name. ** post: WordStore_FileWrite (f) == TRUE ** ==> File contains all words of WordStore. */ void WordStore_MoveBackward (void); /* ** Moves the Current Word pointer to the previous word in WordStore. ** pre: ** post: Current Word moved one position backward. */ void WordStore_MoveForward (void); /* ** Moves the Current Word pointer to the next word in WordStore. ** pre: ** post: Current Word moved one position forward. */
void WordStore_MoveRandom (void); /* ** Moves Current Word to random word. ** pre: ** post: If WordStore is not empty, Current Word is randomly ** selected word. */ int WordStore_NrWords (void); /* ** Returns the number of words in WordStore. ** pre: ** post: WordStore_NrWords () == number of words in WordStore */ void WordStore_Sort (void); /* ** Sorts all words in WordStore in ascending order and locates ** the Current Word on the lowest word. ** pre: ** post: Words sorted and Current Word is lowest word. */ char *WordStore_WordDelete (void); /* ** Returns Current Word to caller, deletes the word from WordStore ** and selects the next word to be the Current Word. ** If WordStore was empty, NULL is returned. ** pre: ** post: If WordStore_WordDelete () == NULL ** then WordStore is empty ** else WordStore_WordDelete () == pointer to former Current Word ** and former Current Word deleted from WordStore ** and next word in WordStore is new Current Word */ void WordStore_WordInsert (char *pcWord); /* ** Inserts word, pointed to by pcWord, to WordStore at the position ** after the Current Word. Afterwards the newly inserted word becomes ** the Current Word. ** Note that the pointer pcWord is stored; the ** word is not copied to newly allocated memory space! ** pre: Sufficient heap space available. ** post: pcWord inserted at position of Current Word. */ char *WordStore_WordRead (void); /* ** Returns Current Word to caller (without deleting the word ** from WordStore). ** If WordStore was empty, NULL is returned. ** pre: ** post: If WordStore_WordRead () == NULL ** then WordStore is empty ** else WordStore_WordRead () == pointer to Current Word */ #endif
Toepassingslayout Er is geen sprake van een toepassing, maar van een module, dus het is aleen mogelijk om globaal aan te geven waarom er voor bepaalde globale variabelen / structuren gekozen is. Omdat er sprake moet zijn van “circular list” zoals er in de headerfile staat, heb ik gekozen voor een structuur met daarin twee pointers van het type pointer naar dezelfde structuur. Ik heb ze Previous en Next genoemd. De structuur is alleen in de module bekend, daarbuiten is het niet nodig om te weten hoe het geimplementeerd is (static). In dezelfde structuur is ook een character pointer, die is nodig om de plaats bij te houden waar een woord in het geheugen staat, deze variabele heet Word. Het geheel ziet er zo uit:
typdef static Node Node char }
struct _node Node; struct _node { *Previous; *Next; *Word;
Daarnaast heb ik gebruik gemaakt van de volgende variabelen: • static int iNrOfWords: deze variabele wordt gebruikt om bij te houden hoeveel woorden er totaal zijn ingelezen. Buiten de module is het aantal op te vragen met de functie: int WordStore_NrWords(void) • static Node * First: een verwijzing naar het eerste element van de dubbele gelinkte lijst. • static Node * Last: een verwijding naar het laatste element van de dubbele gelinkte lijst, eigenlijk is deze niet nodig, maar vond het voor het overzicht wat leesbaarder overkomen als er een begin- en eindpunt is. • static Node * Current: de huidige node in de lijst is terug te vinden via deze variabele.
Stroomschema Er is geen algemeen stroomschema voor deze module, wel is het voor sommige functies handig om daar iets iets dieper op in te gaan of om een illustratie van de werking te geven. Zie de desbetreffende functies voor meer informatie.
Verdere informatie Het programma werd gecodeerd in Borland C++ Builder 5.0 en 6.0 als een console application. De werking van het programma werd getest aan de hand van een zelf geschreven programma en daarna door een programma dat geleverd werd door de docent. De testdata was een bestand met woorden, geleverd door de docent.
Programmastructuur void WordStore_Clear(void) Lokale variabelen: • int i: haalt het aantal woorden uit de lijst op. Wordt gebruikt in een loop om alle woorden uit de lijst te verwijderen. • char * cptr_Clear: tijdelijke opslag voor de pointer naar een woord in het geheugen, wordt iedere keer gebruikt om het geheugen weer vrij te geven. • Node * Temp: tijdelijke pointer naar een Node structuur, zodat de “Current” verwijderd kan worden uit het geheugen, na de functie wordt deze vanzelf opgeruimd. Bedoeling van de functie: Verwijderd alle woorden uit de WordStore module en zorgt dat de teller iNrOfWords weer op nul komt te staan.
Boolean WordStore_FileRead(char sFileName[ ]) Doorgegeven variabelen: • char sFileName: een character array met daarin de filename die geopend moet worden. Lokale variabelen: • Boolean bReturn: return waarde van de functie, gaat alles goed dan blijft deze op TRUE • Boolean bNull: als er een null-character gevonden of een newline-character wordt veranderd in een nul-character in de uitgelezen string van het bestand dan wordt deze op TRUE gezet. • int iWordLoop: teller die van het begin van het woord tot de maximum lengte van het woord loopt. • char sInputString[MAXLEN_WORD]: de headerfile heeft een define, die staat voor de maximale grootte van een in te lezen woord. Woorden mogen niet langer zijn dan deze lengte. Ik maak gebruik van deze define door de buffer de beperking op te leggen van deze grootte. • FILE *ptrFile: bevat de stream van het geopende bestand. Doel van de functie: De functie leest een ASCII text file in met op iedere regel een woord, als de woorden langer zijn dan “MAXLEN_WORD” dan worden deze afgekapt in de lijst opgenomen. Als de functie een bestand niet kan inlezen dan geeft deze functie de waarde FALSE terug.
Boolean WordStore_FileWrite(char sFileName[ ]) Doorgegeven variabelen: • char sFileName: een character array met daarin de filename waarnaar geschreven moet worden. Lokale variabelen: • Boolean bReturn: return waarde van de functie, gaat alles goed dan blijft deze op TRUE • int iNumber: interne teller voor de loop, krijgt bij het begin de waarde 0 en loopt door tot het aantal woorden in de lijst. • char * cptrOutput: tijdelijke pointer naar een woord in een Node. Had ook zonder gekund door meteen naar Current->Word te verwijzen. Ik vond dit iets leesbaarder. • FILE *ptrFile: bevat de stream van het geopende bestand. Doel van de functie:
Open een opgegeven bestand en schrijf daarin de woorden weg, vanaf het huidige woord Current->Word tot en met het einde van de lijst. Als er iets niet goed gaat geeft deze functie de waarde FALSE terug.
void WordStore_MoveBackward(void) Bedoeling van de functie: Het huidige woord moet het vorige woord uit de lijst worden.
void WordStore_MoveForward(void) Bedoeling van de functie: Het huidige woord moet het volgende woord uit de lijst worden.
void WordStore_MoveRandom(void) Lokale variabelen: • int i: random waarde die de functie rand() teruggeeft modulo het aantal woorden uit de lijst. Deze variabele zorgt voor een willekeurig nummer van 0 t/m het aantal woorden in de lijst. Deze variabele wordt in een loop gebruikt. • int n: bevat het aantal woorden in de lijst, zorgt ervoor dat de functie “WordStore_NrWords” maar 1x wordt aangeroepen. Doel van de functie: Verplaats het huidige woord naar een willekeurig woord uit de lijst
int WordStore_NrWords(void) Bedoeling van de functie: Haal het aantal woorden uit de lijst op.
void WordStore_Sort(void) Lokale variabelen: • int i: loop over het aantal woorden in de lijst • int n: binnenste loop die steeds kleiner wordt. • char *cptrHelp:tijdelijke variabele die gebruikt wordt bij het verplaatsen van een pointer naar een woord. Doel van de functie: Sorteer de lijst met een Bubblesort methode. Deze functie maakt direct gebruik van de static variabele iNrOfWords om te laten zien dat het ook op deze manier kan worden geimplementeerd. Zelf gaat mijn voorkeur uit naar een lokale variabele die de waarde opvraagt via de functie WordStore_NrWords() waar dan mee gewerkt wordt, zie bijvoorbeeld WordStore_MoveRandom().
char * WordStore_WordDelete(void) Lokale variabelen: • char * cptrReturn: pointer naar het woord in het geheugen die de functie teruggeeft • Node * Temp: tijdelijke verwijzing naar de huidige Node (Current) die na het aanpassen van de verwijzingen kan worden vrijgegeven. Doel van de functie: Verwijderen van de Current Node uit de lijst.
Laat een tijdelijke Node Temp naar de Current Node wijzen
Verander de vorige Node->Next en de volgende Node->Previous verwijzingen
Verander de Curren Node naar de Volgende Node
Verwijder de Temp Node
void WordStore_WordInsert(char *pcWord) Doorgegeven variabelen: • char * pcWord: een pointer naar een woord in het geheugen, alleen de pointer wordt opgeslagen in de Node. Doel van de functie: Toevoegen van een nieuwe Node aan de lijst op de positie na de Current Node. Aantal woorden in de lijst met 1 ophogen.
Begin
Nieuwe Node maken
Verwijzingen toevoegen aan nieuwe Node
Verwijzingen van Current->Next en Volgende->Previous aanpassen Daarna de Nieuwe Node de Current Node maken
Bijzondere situatie: Node aanmaken in het geheugen. De Nieuwe Node is de eerste Node. De Node moet dan naar zichzelf gaan verwijzen.
char * WordStore_WordRead(void) Doel van de functie: Ophalen van het huidige woord. Als er geen woorden zijn geeft deze functie de waarde NULL.
Programmacode /*****************************************************************************/ /** **/ /** File: WORDSTORE.C **/ /** Author: S.B. Bosch **/ /** Version: 1.0 **/ /** Date: 2004-10-14 (YYYY-MM-DD) **/ /** **/ /** Pre: **/ /** Post: usage: **/ /** #include "WordStore.h" **/ /** **/ /** the
is a ASCII-file containing one word **/ /** per line **/ /** **/ /** Desc: Library for generating a circular list of words **/ /** For more information see the header file **/ /** **/ /** Modified: **/ /** [YYYY-MM-DD] - <description> **/ /** [2004-10-16] S.B. Bosch - commented out some code in **/ /** WordStore_WordInsert because this module is **/ /** not allowed to use the keyboard and monitor **/ /** **/ /*****************************************************************************/ #include <string.h> #include <stdlib.h> #include <stdio.h> #include #include "WordStore.h" /* private variables */ typedef struct _node Node; static struct _node { Node *Previous; Node *Next; char *Word; }; static static static static
int Node Node Node
iNrOfWords = 0; *First; *Last; *Current;
/* Functions */ void WordStore_Clear (void) { int i; char *cptr_Clear; Node *Temp; i = WordStore_NrWords(); if (i) { for ( --i; i>0; i-- ) { Temp = Current->Next; cptr_Clear = Current->Word; free( Current ); free( cptr_Clear); if ( i>1 ) { Current = Temp; } } Last = NULL; First = NULL; Current = NULL; iNrOfWords = 0; } }
Boolean WordStore_FileRead(char sFileName[]) { Boolean bReturn = TRUE; Boolean bNull = TRUE; int iWordLoop; char sInputString[MAXLEN_WORD];
}
/* open file */ FILE *ptrFile; if ((ptrFile = fopen(sFileName, "r")) == NULL ) { bReturn = FALSE; return ( bReturn ); } /* read from file */ iNrOfWords = 0; fgets( sInputString, MAXLEN_WORD, ptrFile ); while (!feof(ptrFile)) { bNull = FALSE; for (iWordLoop=0; iWordLoop<MAXLEN_WORD; iWordLoop++) { if ( !bNull && (sInputString[iWordLoop] == '\n' || sInputString[iWordLoop] == '\0')) { sInputString[iWordLoop] = '\0'; bNull = TRUE; } } if ( bNull && strlen(sInputString) > 1 ) { WordStore_WordInsert( (char *) strdup(sInputString)); } fgets( sInputString, MAXLEN_WORD, ptrFile ); } /* close file */ fclose( ptrFile ); return (bReturn);
Boolean WordStore_FileWrite (char sFileName[]) { Boolean bReturn = TRUE; int iNumber; char *cptrOutput;
}
/* open file */ FILE *ptrFile; if ((ptrFile = fopen(sFileName, "w")) == NULL ) { bReturn = FALSE; return ( bReturn ); } /* write from Current node */ for ( iNumber=0; iNumberWord; WordStore_MoveForward(); fprintf( ptrFile, "%s\n", cptrOutput ); } /* close file */ fclose( ptrFile ); return (bReturn);
void WordStore_MoveBackward (void) { if (WordStore_NrWords()) { Current = Current->Previous; } } void WordStore_MoveForward (void) { if (WordStore_NrWords()) { Current = Current->Next; } }
void WordStore_MoveRandom (void) { int i, n; n = WordStore_NrWords(); if (n) { randomize(); for (i = ((rand()%n)+1); i>0; i--) { WordStore_MoveForward (); } } } int WordStore_NrWords (void){ return ( iNrOfWords ); } void WordStore_Sort (void) { int i, n; char *cptrHelp; for ( i=0; i<(iNrOfWords-1); i++ ) { Current = First; for ( n=0 ; n<(iNrOfWords-i-1); n++) { /* loop through the list using a bubblesort */ if ( strcmp( Current->Word, Current->Next->Word ) > 0 ) { cptrHelp = Current->Word; Current->Word = Current->Next->Word; Current->Next->Word = cptrHelp; } Current = Current->Next; } } Current = First; } char *WordStore_WordDelete (void) { char *cptrReturn; Node *Temp; if ( iNrOfWords == 0 ) { return ( NULL ); } else { Temp = Current; if ( iNrOfWords == 1 ) { /* special condition */ Current = NULL; Last = NULL; First = NULL; } else { /* previous node is connected to the next node and vice versa */ Current->Next->Previous = Current->Previous; Current->Previous->Next = Current->Next; Current = Current->Next; } cptrReturn = Temp->Word; free(Temp); iNrOfWords--; } /* user must free return value? */ return ( cptrReturn ); }
void WordStore_WordInsert (char *pcWord) { Node *ptrNew;
}
if ( (ptrNew = (Node *) malloc( sizeof(Node))) == NULL ) { /* Library is not allowed to use any means of output ** While testing the following code was used */ /*clrscr(); printf("Problem with allocating memmory.\n"); printf("Library WordStore.C\n"); printf("Function void WordStore_WordInsert (char *pcWord)\n"); printf("\n\nPress any key to exit..."); getch(); exit(0);*/ return; } if ( iNrOfWords == 0 ) { /* special condition there are is no current node ** point to self */ First = ptrNew; ptrNew->Previous = ptrNew; ptrNew->Next = ptrNew; } else { /* current node is connected to the new node ** new node becomes the current node with ** a connection to the next. ** Current node becomes the last if the previous ** node was the last*/ ptrNew->Previous = Current; ptrNew->Next = Current->Next; if ( Last == Current ) { Last = ptrNew; } Current->Next->Previous = ptrNew; Current->Next = ptrNew; } ptrNew->Word = pcWord; Current = ptrNew; iNrOfWords++;
char *WordStore_WordRead (void) { if ( iNrOfWords == 0 ) { return ( NULL ); } return ( Current->Word ); }
