a Resizable Table, a Linked List, and a Word Count Program.
Goal
In this lab you will practice dynamic memory, pointers, and strings by implementing a table and a linked list that can be used to store name, value pairs. Additionally, you will implement your own string routines and implement a word counter program.
Step 0. Copying the Initial Files
Copy the initial files:
cp /homes/cs240/2014Fall/lab3/lab3-src.tar.gz .
gunzip lab3-src.tar.gz
tar -xvf lab3-src.tar
The directory lab3-src created will contain the initial implementation of the table, linked list and string functions.
Type "make" to create the initial program. Also type "testall" to run the tests. Your goal is to implement the resizable table, linked list, and string operations so testall will be able to run correctly all the tests.
Step 1. Implementing your string functions.
Implement the functions described in mystring.c without using any of the string functions such as strlen, strcat, strcpy, strcmp, strdup etc. Implement your own functions and test them with the script testall. The program test_mystring.c tests your string implementation.
Step 2. Implementing a Resizable Table
In the file resizable_table.c, you will implement a table to store pairs name/value. The name could be for example the name of a person and value could be the home address.
The table is represented by the following struct in resizable_table.h:
typedef struct RESIZABLE_TABLE_ENTRY {
char * name;
char * value;
} RESIZABLE_TABLE_ENTRY;
typedef struct RESIZABLE_TABLE {
int maxElements; // Max number of elements in the array
int currentElements; // Number of elements used in the array
struct RESIZABLE_TABLE_ENTRY * array; // Array that stores the entries.
} RESIZABLE_TABLE;
The RESIZABLE_TABLE structure contains an array of RESIZABLE_TABLE_ENTRY entries that store name and value.
The array will be initially created with a capacity (maxElements) of 10. If the number of entries used exceed the maxElements, then the array will be doubled in size and the entries will be copied. to the new array.
The functions you have to implement are described in the file resizable_table.c. The functionality is tested by the program test_resizable_table. Run the script "testall" to test your implementation.
Turning In Steps 1 and Step 2
Step 1 and Step 2 are due on Monday September 15th, 11:59pm. This is an intermediate milestone. Turnin your code even if it is only partially working.
Follow these instructions to turnin lab3 Step 1 and Step2.
Login to data.cs.purdue.edu
Run make clean in your lab3-src folder.
Change to the directory above lab3-src.
Type "turnin -c cs240 -p lab3-1 lab3-src"
Type "turnin -c cs240 -p lab3-1 -v" to make sure you have submitted the right files
Step 3. Implementing a Double Linked List
In the file linked_list.c you will implement a double linked list to store pairs name/value. The name could be for example the name of a person and value could be the home address.
The linked list is represented by the following struct in linked_list.h:
typedef struct LINKED_LIST_ENTRY {
char * name; // name associated ot this entry
char * value; // value associated to this name
struct LINKED_LIST_ENTRY * next; // pointer to the next entry in the list.
struct LINKED_LIST_ENTRY * previous; // pointer to the previous entry in the list.
} LINKED_LIST_ENTRY;
typedef struct LINKED_LIST {
int nElements; // Number of elements stored in the list
LINKED_LIST_ENTRY * head; // Points to a dummy entry that simplifies implementation.
// This entry is not used to stored data. It is only used to
// delimit the list.
} LINKED_LIST;
The LINKED_LIST_ENTRY represents a node in the list. This structure contains the name and the value as well as a pointer to the next and a pointer to the previous element in the list. The struct LINKED_LIST contains a member nElelements with the number of entries in the list. It also contains a pointer called header to a dummy node (also called sentinel) that does not store any data but it is used to delimit the list. For example, head->next points to the first element in the list, and head->previous points to the last element in the list. Initially the list is empty so head->next points to head and head->previous points to head. See the implementation of llist_create() in llinked_list.c
The functions you have to implement are described in the file linked_list.c. The functionality is tested by the program test_linked_list. Run the script "testall" to test your implementation.
Step 4. Implementing a wordcount program
You will implement a wordcount program that displays the number of times a word is repeated in a text file.
A word is a sequence of alpha characters separated by non-alpha characters. An alpha character is a character in A-Z or a-z. The words are not case sensitive and the words are printed in lower case.
The usage of the wordcount program is the following.
wordcount [-w|-s] textfile
The options are as follows:
No options - The program displayes the occurrences sorted by word
-w - The program displays only the words contained in the text and not the count.
-s - The program displays the occurrences sorted by count
Example:
cs240@data $ ./wordcount hamlet.txt
======== Table =======
currentElements=170 maxElements=320
0: "a" 5
1: "ache" 1
2: "action" 1
3: "after" 1
4: "against" 1
5: "all" 2
6: "and" 12
7: "arms" 1
8: "arrows" 1
9: "awry" 1
cs240@data $ ./wordcount -s hamlet.txt
======== Table =======
currentElements=170 maxElements=320
0: "the" 22
1: "to" 15
2: "of" 15
3: "and" 12
4: "that" 7
5: "a" 5
6: "sleep" 5
7: "s" 5
8: "be" 4
9: "we" 4
10: "is" 3
11: "in" 3
cs240@data $ ./wordcount -w hamlet.txt
to
be
or
not
to
be
that
is
the
question
The script testall
A script testall has been provided to test your project. Make sure you to run this script since it will be used to grade your project. Follow the instructions at the end of the script to run individual tests.
Turning In your Project
Follow these instructions to turnin all your lab3:
Login to data.cs.purdue.edu
Run make clean in your lab3-src folder.
Change to the directory above lab3-src.
Type "turnin -c cs240 -p lab3-2 lab3-src"
Type "turnin -c cs240 -p lab3-2 -v" to make sure you have submitted the right files
The deadline for this lab is Monday September 22th, 11:59pm. All Steps should be working at this time.