代写自排序的单链表，需要按照题目给定的格式，从文件中读入数据，并将结果输出回文件。
Overview
This project has a single program! In this program, you will implement a
sorted linked list. You will read a series of commands from stdin, which will
insert and delete elements, and do some other simple operations. You will also
implement a “print” feature, which will print the current contents of the list
(which will be critical for passing testcases - we’ll use it to see if you are
keeping the list properly).
Grading
In this project, we will not provide a grading script for you; instead, you
must run the tests manually. The reason for this is that we want you to learn
how to do your own testing - since in the Real World, you often will not have
some other programmer writing a test suite for you.
Thus, in this project, we will provide testcases (and an example executable),
but no grading script; you will have to test things yourself. Our current plan
is to not even provide the testcases on the next project.
Doing the Testing Yourself
Look through the grading script from Project 4 (you can open it with pico or
any other text editor). While there will be a fair bit which you won’t
understand, you will see that there are a number of things that we tested for:
comparing stdout (has to be exact), comparing stderr (more flexibility),
checking exit status from commands, and also checking to see if gcc produced
any warnings.
You are welcome to write your own grading script - or to adapt the one from
Project 4. But you are responsible for making it work in Project 5!
Point Distribution
In this project, your code will be graded by a script, with your score
determined by how many testcases you pass for each program. After that score
is calculated, a number of penalties may be applied.
Program - Linked List
In this program, you will implement a linked list of structs. Each struct will
have a pointer to the next node (of course), and two data fields. The first
data field will be an array of 20 bytes, which will hold a small string; it
represents the name of some person; the second will be an integer, which is
their favorite number.
(Although we call the first field a “name”, it should be a general string; it
might contain any character, including underscores, digits, or symbols. The
only limitation is that it will not contain any whitespace - and that it will
not be empty.)
At all times, you will keep the list sorted by the names; that is, when you
insert a new element into the list, you must place it in the correct position
(based on the name). Ignore the “favorite number” field when sorting the list.
When your program begins, the list will be empty; as you run through the
testcase, you will update the list (printing it out only when the testcase
asks for it).
Input Format
In this program, each line of input is a command. Each command is designated
by a string; some commands also have parameters which follow. Commands and
parameters are separted by spaces or tabs but not newlines; newlines should
only be used at the end of a command.
The commands are:
- print
Print the current contents of the list (see details below). - insert [name] [num]
Insert a new linked list element into the list, at the proper position. If the
name already existed on the list, then do not update the list; instead, print
out an error message to stderr.
Remember that the size of the name field is fixed. If the name given is too
long to fit into the name field in your linked list, report an error instead
of corrupting your memory.
However, when reading the name field with sscanf() make sure to leave some
space for extra characters. Take a look at testcase 25; if the user passes a
too-long name, they should get an error - even if the last few characters of
the name could be interpreted as an integer. - delete [name]
Search the list for the name. If it exists, delete that node from the list
(and do not print anything out). If the name does not exist in the list, then
report an error to stderr. - removeHead
Delete the first element from the list. If the list is already empty, then
print an error message to stderr.
Input Format - Other Details
Each line in the input is limited to 80 characters (including the newline at
the end). However, in this program (unlike Program 4), you must confirm this.
This will require you to check, after each call to fgets() or getline(),
whether you found a newline at the end of the string you read. If a line is
longer than 80 characters, you must print an error message to stderr and
terminate the program. (You may assume that every line in each testcase -
including the last - has a terminating newline.)
Within the line, there should be a command, and sometimes some parameters.
These elements (up to three of them) are separated by whitespace, and there
can be leading whitespace, trailing whitespace, etc. However, all of the
elements must be on the same line, meaning that you should never find a
newline in the middle of a command.
Empty lines are allowed, and should not be reported as an error. However, a
line which is not empty, but which is also not a valid line, should be
reported as an error. Remember that a line with only spaces and/or tabs is a
line that is non-empty!
Finally, for simplicity, we are not requiring you to detect (or handle) to any
junk at the end of the line, after the command and its parameters. If there is
junk at the end of a line, you must ignore it. (A more advanced program would
handle that as an error case.)
How to Read the Line
To read a line from input, you must go through two stages:
- Read the line from stdin
In this stage, call fgets() or getline() to read an entire line of input. This
ought to run to the end of the line, and then have a newline; however, if the
line was too long, you will need to report an error and kill the program. - Once the line has been read, break it into fields. For this, we strongly recommend that you use sscanf() to read from the buffer. See below for a quick introduction to sscanf().
A Trick for Reading Commands
Not all of the commands take parameters; some take zero, one, or two
parameters. However, you can read them all with a single call to sscanf().
Call it once, with the maximum number of format specifiers that you will need
for the longest command. Then you can simply check the return code from
sscanf() to see if you all of the pieces which the command requires are
present.
Output
None of the commands should print anything to stdout, except for print, which
prints the entire list. Some other commands print to stderr on error; you will
also sometimes print to stderr when an input line is not valid. (For details,
see
above.)
The output of the print command should be first an integer, which is the
current length of the list; then a colon. If the list is empty, the newline
should follow the colon; otherwise, print out a space-separated list of
name/number combinations. Each should be the name, then a slash, then the
number (see the examples below).
Output Example
Imagine that your input file looked like this:
print
insert Russ 42
print
insert Eric 8192
insert Rose 10
insert Em 35
print
In that case, the output should be as follows.
0:
1: Russ/42
4: Em/35 Eric/8291 Rose/10 Russ/42
Error Conditions
- Any line of input which is longer than 80 characters (including the newline) should cause your program to print an error and terminate.
- If malloc() ever fails, you should print an error and terminate.
- Any line of input which is not empty, but which does not have a command that you recognize from the list above, should cause your program to print an error message. However, keep going; do not terminate the program.
- Likewise, some of the commands listed above have situations where they must print an error message. If these happen, print an error message to stdin, but keep running.
Non-Errors
Blank lines of input (with nothing but a newline) are not errrors; ignore them
silently.
sscanf()
You have been using scanf() in the projects so far; that function reads data
from stdin. sscanf() (see the extra ‘s’ ?) reads data from a string, but works
in more or less the same way.
The first parameter to sscanf() is the buffer to read from; the next is the
format string, followed by the variables that you want sscanf() to read into.
(This is similar to how fprintf() takes the output stream as the first
parameter.)
Here’s a simple example of sscanf() in action:
char *buf = “foo bar 123 baz”;
char word1[20];
char word2[20];
int val;
char word3[20];
sscanf(buf, “%s %s %d %s”, word1, word2, &buf, word3);
// sscanf() returns 4
—|—
As with scanf(), sscanf() returns the number of format specifiers matched. It
will return 0 if it cannot match any of the specifiers; it can even match EOF
if it hits the end of the string!
However, sscanf() is a little different than scanf() in that it doesn’t have
any way to “consume” the string - so if you call sscanf() multiple times on
the same string, you will start the parsing over from scratch, at the
beginning. So generally, you will only call sscanf() once for each string.
(This is exactly how you will use it in this program - use fgets() or
getline() to read the initial string; then use sscanf() (once per line) to
break the line into fields.
And yes, as you may have guessed: there are similar other variants in the
printf() and scanf() families, such as sprintf(), which prints to a string,
and fscanf(), which reads from an arbitrary file!
