Introduction
代写一个YELP的数据库程序，涉及到Data Structure的Map实现。
相比C++，用C语言来实现Data Structure和Algorithm会复杂很多，几乎所有的基础结构都需要自己写。
Purpose
The purpose of this assignment is for you to:
- Increase your proficiency in C programming, your dexterity with dynamic memory allocation and your understanding of linked data structures, through programming a dictionary.
- Increase your understanding of how computational complexity can affect the performance of an algorithm by conducting orderly experiments with your program and comparing the results of your experimentation with theory.
- Increase your proficiency in using UNIX utilities.
Background
A dictionary is an abstract data type that stores and supports lookup of key, value pairs. For example, in a telephone directory, the (string) key is a person or company name, and the value is the phone number. In a student record lookup, the key would be a student ID number and the value would be a complex structure containing all the other information about the student.
A dictionary can be implemented in C using a number of underlying data structures. Any implementation must support the operations: makedict a new dictionary; insert a new item (key, value pair) into a dictionary; search for a key in the dictionary, and return the associated value. Most dictionaries will also support the operation delete an item.
Your task
In this assignment, you will create a simplified UNIX yelp.com (local business directory) as a concrete instance of a dictionary, and will use it to look up information about a specific business name, such as full address or opening times.
There are two stages in this project. In each stage you will code a dictionary in the C programming language. A binary search tree will be the underlying data structure for both stages.
In this assignment the search keys are not guaranteed to be unique. In this assignment we use variants of the binary search tree designed to handle duplicates, i.e. by either dividing nodes using <= >, or by using < > and a linked list for items with same key. You will use a Makefile to direct the compilation of two separate executable programs, one for Stage 1 and one for Stage 2, each of which uses a different variant of the binary search tree.
In both stages of the assignment, you will insert records into the dictionary from a file. You will then look up and output the records (business) contained by the dictionary, counting and outputting the number of key comparisons used in the search.
You will report on the number of key comparisons used for search, compare the number of key comparisons used by each stage, and analyse what would have been expected theoretically. The report should cover each file used to initialize the dictionary.
You are not required to implement the delete functionality.
Stage 1
In Stage 1 of this assignment, your Makefile will direct the compilation to produce an executable program called yelp1. The program yelp1 takes two command line arguments: the first argument is the name of the data file used to build the dictionary; the second argument is the name of the output file, containing the data located in the searches. The file consists of an unspecified number of records, one per line, where the format of each record is:
<name> <data>
The field name is an alphabetic string of varying length, containing the name of the business or the user. You may assume that this field contains no more than 64 characters. The data field is a string containing all the data collected about the business or the user. Although the average size of this field is around 430 characters, the maximum size of this field can be 1,465 characters. Each field is separated by a semicolon “,”. It is a standard csv format where the delimiter used is a comma.
The dictionary key consists of the name field. The data is the information sought during lookup.
For the purposes of this assignment, you may assume that the input data is well-formatted, that the input file is not empty, and that the maximum length of an input record is 1,465 characters. This number could help you fixing a reading buffer size.
In this first stage of the assignment, you will:
- Construct a binary search tree to store the information contained in the file specified in the command line argument. Each record should be stored in a separate Node.
- Search the binary search tree for records, based on their keys. The keys are read in from stdin, i.e. from the screen.
For testing, it is often convenient to create a file of keys to be searched, one per line, and redirect the input from this file. Use the UNIX operator for redirecting input from a file. - Examples of use:
yelp1 datafile outputfile then type in keys; or
yelp1 datafile outputfile < keyfile
- Your program will look up each key and output the information (the data found) to the output file specified by the second command line parameter. If the key is not found in the tree, you must output the word NOTFOUND.
The number of key comparisons performed during both successful and unsuccessful lookups have to be written to stdout. - Remember that the entries in the file do not necessarily have unique keys. Your search must locate all keys matching the search key, and output all the data found.
In Stage 1 of the assignment you will locate the duplicates by continuing your search until you reach a leaf node, regardless of whether or not you have already found a match or matches.
Note that the key is output to both the file and to stdout, for identification purposes. Also note that the number of comparisons is only output at the end of the search, so there is only one number for key comparisons per key, even when multiple records have been located for that key.
The format need not be exactly as above. Variations in whitespace/tabs are permitted.
Stage 2
In Stage 2, you will code a dictionary where all the duplicate keys in the dictionary are returned, as previously, and additionally where the search is more efficient than in Stage 1. Input and output are as for Stage 1, with the information or NOTFOUND written to a file and the number of comparisons made during the search written to stdout.
In Stage 2, however, you will structure your tree so that once a key is found, all duplicate keys can be found without further key comparisons. Note that comparing a key to NULL is not a full (costly) key comparison, and is not counted as a key comparison in Stage 2 of this assignment when building the report.
Experimentation
You will run various files through your program to test its accuracy and also to examine the number of key comparisons used when searching different files. You will report on the key comparisons used by your Stage 1 dictionary yelp1 for various data inputs and the key comparisons used by your Stage 2 dictionary yelp2 for various data inputs too. You will compare these results with each other and, importantly with what you expected based on theory (big-O).
Your experimentation should be systematic, varying the size and characteristics of the files you use (e.g. sorted, random, duplicates, etc.), and observing how the number of key comparisons varies. Repeating a test case with different keys and taking the average can be useful.
Some useful UNIX commands for creating test files with different characteristics include sort, sort -R (man sort for more information on the -R option), and shuf. You can randomize your input data and pick the first x keys as the lookup keywords.
You will write up your findings and submit your results separately through the Turnitin system. You will compare your results with the two dictionary implementations (stage1 and stage2) and also compare these results to what you know about the theory of binary search trees.
Tables and graphs are useful presentation methods. Select only informative data; more is not always better.
You should present your findings clearly, in light of what you know about the data structures used in your programs and in light of their known computational complexity. You may find that your results are what you expected, based on theory. Alternatively, you may find your results do not agree with theory. In either case, you should state what you expected from the theory, and if there is a discrepancy you should suggest possible reasons. You might want to discuss space-time trade-offs, if this is appropriate to your code and data.
You are not constrained to any particular structure in this report, but a useful way to present your findings might be:
- Introduction: Summary of data structures and inputs.
- Stage 1 and Stage 2:
- Data (number of key comparisons)
- Comparison of the two stages
- Comparison with theory
- Discussion
Implementation Requirements
The following implementation requirements must be adhered to:
- You must code your dictionary in the C programming language.
- You must code your dictionary in a modular way, so that your dictionary implementation could be used in another program without extensive rewriting or copying. This means that the dictionary operations are kept together in a separate .c file, with its own header (.h) file, separate from the main program. The main.c of stage1 can perfectly be the same main for stage2, in terms of dictionary operations.
- Your code should be easily extensible to allow for multiple dictionaries. This means that the functions for insertion, search, and deletion take as arguments not only the item being inserted or a key for searching and deleting, but also a pointer to a particular dictionary, e.g. insert(dict, item).
- In each stage, you must read the input file once only.
- Your program should store strings in a space-efficient manner. If you are using malloc() to create the space for a string, remember to allow space for the final end of string ‘\0’ (NULL).
- A Makefile is not provided for you. The Makefile should direct the compilation of two separate programs: yelp1 and yelp2. To use the Makefile, make sure is in the same directory of your code, and type make yelp1 to make the dictionary for Stage 1 and make yelp2 to make the dictionary for Stage 2. You must submit your makefile with your assignment.
Hint: If you havent used make before, try it on simple programs first. If it doesnt work, read the error messages carefully. A common problem in compiling multifile executables is in the included header files. Note also that the whitespace before the command is a tab, and not multiple spaces. It is not a good idea to code your program as a single file and then try to break it down into multiple files. Start by using multiple files, with minimal content, and make sure they are communicating with each other before starting more serious coding.