辅导 CSE 30 Spring 2024 PA 5 & 6讲解 留学生R程序

CSE 30 Spring 2024 PA 5 & 6 - (Version 1.01)

PA5 Due Date: Tuesday May 14, 2024 @ 11:59PM

PA5 Final Submission Date: Friday May 17, 2024 @ 11:59PM

PA6 Due Date: Sunday May 19, 2024 @ 11:59PM

PA6 Final Submission Date: Wednesday May 22, 2024 @ 11:59PM

Difficulty Gauge 1 = Easy 2 3 4 5 = Hard

Grading PA5

You must complete all of the following items by the due date to get all points.

There are 30 points available for this PA that are distributed as follows:

  Up to 8 points (at our discretion) if the following files compile without warnings. This has to be a meaningful attempt to write the code that meets the specifications of the program. Random C  statements, or empty files will not be awarded any points:    freetickets.c (2 points),

dumpdb.c (2 points), vehlookup.c (2 points), sumlookup.c (2 points) Up to 12 points  for passing the tests 1 through test 3 in the text fixture.

  Up to 10 points for passing the gradescope tests (these will only be run after the late deadline).

  Minus 1 point for each submitted file that compiles with a warning (max of 4 points deducted). Minus 2 points at our discretion, for not following the C style guidelines:  CSE30 C Style Guide

Grading PA6

You must complete all of the following items by the due date to get all points.

There are 30 points available for this PA that are distributed as follows:

  Up to 8 points (at our discretion) if the following files compile without warnings. This has to be a meaningful attempt to write the code that meets the specifications of the program. Random C  statements, or empty files will not be awarded any points:    largest.c (2 points),

insticket.c (3 points), delticket.c (3 points)

  Up to 12 points  for passing the tests 1 through test 3 in the text fixture.

  Up to 10 points for passing the gradescope tests (these will only be run after the late deadline).

  Minus 1 point for each submitted file that compiles with a warning (max of 4 points deducted).   

Minus 2 points at our discretion, for not following the C style guidelines:  CSE30 C Style Guide

You are always welcome to go to either Instructor or TA office hours. Their hours are listed on both the Canvas calendar and the autograder calendar. In office hours, conceptual questions will be prioritized.

If you need help while working on this PA, make sure to attend labs hours with a tutor at:

https://autograder.ucsd.edu

You can also post questions on Piazza.

https://piazza.com/ucsd/spring2024/cse30_sp24_a00/home

Assignment – Pointers and Data Structures - a Memory based Database

In this two part project you will be working on an in-memory unpaid parking ticket database. The data is    derived from the NYC parking ticket database for the year 2019. In PA5 you will be writing four routines to replace ones provided with the starter code. In PA6 you will be writing three more.

1.   Practice in writing data structures in C using pointers combined with self-referential structures. 2.   Basic memory runtime memory allocation and deallocation with malloc() and free().

3.   Using the linux tool valgrind to testif your use of malloc() and free() is correct.

4.   Working with hash table chains and 2-dimensional linked lists.

5.   Writing code to traverse every record in a database to find a specific entry.

6.   Writing code to use a hash function to find a specific entry in the database.

7.   Writing code to insert and delete records in the hash table in the database.

8.   Practice doing incremental code development in the context of a fully operational program.

Both PA5 and PA6 use the same starter code. The starter code includes a fully operational database that will pass all the test harness tests without any additional code development. The database program that is created by make and is called parking. Included in the database program parking is an interactive (but very simplistic) command interface that allows you to run both a number of debugging commands (to help debug your code) as well as several basic database query and update commands.

Like  PA4,  the  starter  code  uses  an  incremental  code  and  test  process,  and  uses  the  same  single  file development procedure like you did in PA4. A library file included with the download includes solutions for all the functions you will be writing for both PA5 and PA6. Also included in the library is a working version of the function selectrow(), the same function you developed in PA4. In this project, selectrow() is used to extract database rows from a csv file during the database load process (which is provided for you in source, and is not part of the code you will need to develop for these PA's).

Also included with the download are the source code for several functions that you will be using to develop your program.  You will be using the functions defined in helper.c. You are encouraged to examine these source files to help in your debugging process.

You can test your code these ways:

1.   interactively:

a.   With a database loaded : "./parking -d in/DB.csv" or "make simple"

b.   WIth an empty database: "./parking"

2.   WIth test harness. We supply 5 tests, test 1 through test 5 with increasing difficulty. The test harness is basically the same one you used in PA4 with only minor differences. You run and add tests to this test fixture the same way you did in PA4. The supplied tests are basic, but will get you started. I strongly encourage you to do the initial tests running in interactive mode.

Description of the Command Line Options

./parking [-d Tickets.csv] [-f Fines.csv] [-t size] [-s]

Overall Operation

At program startup, main() (in the file parking.c) first parses the command line arguments using getopt() to

1.   Optional summons dataset file name (if not provided, you get an empty database).

2.   Optional override of the hash table size (element count of pointers in the hash table).

3.   Optional override of the file that contains the fines data.

4.   Option to turn off interactive mode (used by the test harness and gradescope testing).

main() calls routines in the file loaddb.c (supplied starter code) to load the data files into memory. One datafile   type lists the various parking fines (one per row) by a fine code number, the amount of the fine (in US $) and a  brief description of the fine. The other file is the summons data, the summons number, the license plate of the vehicle and a fine code. Both types of data files are in CSV format. The fines table is processed first and if it has errors the program will not run. Next the summons dataset is loaded (if specified) and any bad records are rejected by selectrow() (from PA4).

Next, main() calls the command interpreter commands() (source is supplied in the file commands.c).

Commands() will allow you to interact with the database and includes commands to help you debug your code  and commands that do actual queries. Command() has a very simple interface that is typical of a prototype test interface. It contains a mix of debug functions and actual query functions. You leave the database command interface by entering the q command on the keyboard or typing cntrl-d to return to main().

The last part of main() frees up all the memory that was allocated on the heap. main() calls freeticketc() to free up all the entries in the database, and then frees up the hash table.

Version.h Controls the compilation process

In the starter file there is a file called Version.h. This file works the same way as it did in PA4. The contents are shown below:

The fines table (in/Fines.csv)

The fine table is one of the datasets read up into a fixed size global variable array at the start of execution. Each row in the fine table maps a fine code number to a fine amount in US $ and a short text description of the fine. The database will not run without this data. Encoding a summons type number in the ticket field saves space  as  all  you   need  to  store  with  each  summons  is  the  code   number,  you  do  not  have  to  store  the description text string or fine amount in every ticket.

The fines dataset is stored in a three field CSV file with the following format (in order):

Fine code:                      code number recorded in the summons dataset

Fine description:         text string describing the fine

Fine amount:                amount of the fine in US dollars.

Here  are  the  first few  records  in  that  file  (in/Fines.csv). The  first  record  is a header file. There are 99 different types of summons. You should assume there are no errors in this table.

VIOLATION CODE,VIOLATION DESCRIPTION,FINE (DOLLARS)

1,FAILURE TO DISPLAY BUS PERMIT,515

2,NO OPERATOR NAM/ADD/PH DISPLAY,515

3,UNAUTHORIZED PASSENGER PICK-UP,515

4,BUS PARKING IN LOWER MANHATTAN,115

5,BUS LANE VIOLATION,115

The fine table is an array of structs as defined in parking.h (and shown below).

struct fine {

char *desc;                   /* text description of code */

unsigned int fine;          /* value of the fine in $ */

};

The fineTab is a global variable defined in parking.c ( #ifdef CODES is in parking.h)  as:

struct fine fineTab[CODES]; /* table of fines by code 0 - 99 */

When the fine table is built by the supplied starter code at program start up, an empty element is inserted at index 0 into the table to make it easier to lookup fine codes. Since ticket code numbers assigned to actual tickets range from 1 to 99, you can use the code number directly to find the entry for the code rather than always having to subtract 1 to get the correct element. For example if you wanted the fine information for a summons with the fine code number value of 3, “unauthorized pickup”, you would write code similar to (adjust based on your code):

unsigned int finecost = fineTab[3].fine;

char *finestring = fineTab[3].desc;

The database files (in/DB.csv and Large.csv)

The summons datasets (parking tickets) all have the following structure (the first 10 records are shown and the first record is always a header record).

Summons Number,Plate ID,Registration State,Violation Code

100,GLS6003,NY,53

101,HXM7362,NY,36

102,GTR7949,NY,68

103,HH1842,NC,48

104,HDG7076,NY,67

105,GER9006,NY,17

106,HLC3177,NY,61

107,HZN6473,NY,40

108,HPC9135,NY,74

The names of the fields are (in order):

Summons Number:                    ticket/summons number (aunique value)

Plate ID (the license plate id):  License plate id (often called a number, but is a string of chars)

Registration State:                       Two letters for the US state that issued the plate

Violation Code number:             Number (1-99) that specifies the violation type

The summons database does NOT have any corrupt records in it. A summons is only with just one vehicle!

While  you  need  to  check  for  duplicate  insertions  into  the  database  you  can  always  assume  that  the summons,plate,state tuple will always be the same. A specific  summons number is only ever associated with one license plate and state.

There are 99 types of parking violations, each assigned a number from 1 to 99 (0 is in the table but is unused). By  using  an  index  number  you  can  record  the  violation  while  consuming  a  small  amount  of  space  in the database (versus storing the full information with every summons). The violation number is then used as an index into the fine table (described above) that has expanded details on each type of violation. This avoids repeating all the summon detail information in every entry in the database. It also allows details of the fines to be easily changed, like increasing the fine without having to update every record in the ticket database.

The various summons datasets included with the starter code repository are:

in/DB.csv       // a dataset with 28 rows (header + 27 summons)

in/Large.csv    // a dataset with 200,001 (header + 200,000 summons)

Helper functions (helper.c)

The starter code file helper.c contains the source of some of theimportant helper functions you will need to use. These are supplied in source form so you can read them in case you are having difficulty in using them.

int strtosumid(char *summ, unsigned long *summid);

This function is passed a pointer to a character string summ, and a pointer to an unsigned long output variable summid. This function converts the summons id in string form to an unsigned long, placing the result in the memory location pointed at by summid. Returns 0 on success in conversion, -1 otherwise.

uint32_t hash(char *str);

Converts the  string  into  a  hash  value.  The  source  to this function  is  not  provided.  Notice that it returns a uint32_t (unsigned 32 bit integer).  You will use this return value to locate a collision chain in the hash table.

unsigned int printvehicle(struct vehicle *vhpt);

Prints all the data about the vehicle specified at *vhpt (a pointer to a vehicle structure). You use this in the routines you write in dumpdb.c (where you have to traverse the database printing out entries on the collision chains). It returns 0 if it can print the vehicle, -1 otherwise (if it detects an error while printing).

void printsummons(struct vehicle *vhpt, unsigned long summid);

Prints  all  the  data  about  a  specific  summons  for  the  vehicle  specified   by   *vhpt  (a   pointer  to  a  vehicle structure). You  will  not  need  to  use  this  routine  in  the  code  you  write,  but  you may want to use it when debugging. It is normally  called by command.c (it is one of the debugging commands).