C/C++代写 | 算法作业 | 数据结构| 分布式 – CSCI 2132 Software Development

C/C++代写 | 算法作业 | 数据结构 | 分布式: 这是一个通过C语言进行程序设计的作业,通过C语言完成软件设计的相关训练

CSCI 2132 Software Development

  1. The difficulty rating of this assignment isgold. Please read the course web page formore information about assignment difficulty rating, late policy (no late assignmentsare accepted) and grace periods before you start.
  2. Each question in this assignment requires you to create one or more regular files onbluenose. Use the exact names (case-sensitive) as specified by each question.
  3. C programs will be marked for correctness, design/efficiency, and style/documentation.Please refer to the following web page for guidelines on style and documentation forlarge C programs (which applies to this assignment):http://web.cs.dal.ca/~mhe/csci2132/assignments.htmYou will lose a lot of marks if you do not follow the guidelineson style anddocumentation.
  4. Create a directory nameda7that contains the following files (these are the files thatassignment questions ask you to create): makefile, unique.c, lines.c, match.c,lines.handmatch.h. Submit this directory electronically using the commandsubmit.The instructions of usingsubmitcan be found at:http://web.cs.dal.ca/~mhe/csci2132/assignments.htm
  5. Do NOT submit hard copies of your work.

As mentioned in the first lecture of this course, this assignment is a gold-level assignment.It also has a small number of bonus marks, to reward people whowork hard on assignmentsof gold level: Recall that we have the best 6 out of 7 policy forassignments.Since this assignment is supposed to be more difficult than previous assignments, startworking on this assignment early. As usual, the instructor and the TAs are there to help.To help you avoid losing marks, a draft of the marking scheme for the first question canbe found at (this is subject to minor changes):http://web.cs.dal.ca/~mhe/csci2132/assignments/a7q1.pdf

  1. [30 marks] When we learned how to use the UNIX utilityuniqin Lab 2, we learnedthat it can be used to display a file with all of its identical adjacent lines replaced bya single occurrence of the repeated line. In this question, we write a program that canperform a similar task, and the main difference is that it can detect identical lines thatare not necessarily adjacent.Thus, this question asks you to write a program that reads from stdin, filters matchinglines from the input, and writes the distinct lines to the standard output. More pre-cisely, when multiple lines in the input match, only the firstof these lines will be printedto the output. This program also handles command-line arguments that specify rulesthat determine whether two lines match.For example, we have the following text filefruits.txt:
navel orange
yellow banana
red apple
yellow banana
red apple
green apple
navel orange
green apple
green mango
navel orange
red apple
Red apple
We then run the following command:
./unique < fruits.txt
Without specifying any command-line options, we expect the program to print the
following to stdout:
navel orange
yellow banana
red apple
red apple
green apple
navel orange

green mangostrawberryRed appleapple

Either sub-question of this question will specify the exactbehavior of this programprecisely. The purpose of dividing this question into two sub-questions is to facilitatethe awarding of partial marks. You are expected to submit oneand only one set ofsource files and header files for the entire question. Thus the implementation andgeneral requirements will be given before the sub-questions which will give the syntaxof running the program.

Implementation Requirements: Read the input and store its distinct lines (thecommand-line arguments may be given to specify how to determine whether one lineis distinct) in a linked list. Each distinct line is stored inone node of this linked listas a string variable. Each line of the input is expected to have at most 80 characters,excluding the terminating newline character. When one lineof the input is too long,print an error message and terminate, without printing any line to stdout. This meansthat the string from each line can be stored in a character array of length 81.

You are expected to perform the task specified by each sub-question using this linkedlist. If your solution is not based-on such a linked list, you can get at most30% of the total marks for this question.

General Requirements: Divide your source code into the following five files:

  • unique.c: the file that contains the main function;
  • lines.candlines.h: the code for reading the lines from stdin and writing thelines to stdout (filtering matching lines can be done when youread the lines);
  • match.candmatch.h: the code for functions that determine whether two linesmatch, given options entered in the command-line.

In each module, divide your code into functions appropriately. In the header file, placeprototypes of only those functions that are shared by difference modules. Prototypes ofhelper functions that are used in one module only should be placed in the corresponding.cfile.

Write amakefile that will allow us to use the following command on bluenose tocompile your program to generate an executable file namedunique:

make unique

(i) First, implement thisuniqueprogram without considering command-line argu-
ments. In this case, two lines match each other if and only if they contain identical
To run the program from a UNIX terminal using input redirection, we will enter
the command
./unique < input_file
In this command line, input_fileis the name of a plain text file. Each line
is terminated by a trailing newline character, including the last line. You can
assume that there are no empty lines in the input.
Error Handling: Your program should print an appropriate error message and
terminate (without printing any lines from the input file) ifthere is at least one
line that has more than 80 characters.
Testing: To help you confirm your understanding and make sure that the
output format of your program is exactly what this question asks for, several files
are provided in the following folder on bluenose to show how exactly your program
will be automatically tested:
In this folder, open the filea7q1atest to see the commands used to test the
program with one test case. The output files, generated usingoutput redirection,
is also given.
To check whether the output of your program on any test case iscorrect, redirect
your output into a file, and use the UNIX utilitydiff(learned in Lab 3) to
compare your output file with the output file in the above folder, to see whether
they are identical.
Construct additional input files to fully test your program,as we will use different
cases when testing your program.
Since these files are given, we willapply a penalty to any program that
does not strictly meet the requirement on output format. Note thatit
is extremely important to use diff here, as the number of characters in
the output is large.
Hints:You can modify theread_linefunction given in class for your program,
so that when the end of file is reached, an empty string will be read. Recall that
thegetcharfunction returns a macroEOFwhen end of file is reached. Thus the
following logical expression might be helpful:
(ch = getchar()) != \n && ch != EOF

(ii) Next implement one more feature for this program by adding an option thatrequires the program to skip the firstffields of any line when determining whether

two lines match. If a certain line has fewer thanffields, treat this line as an emptystring, i.e. a string that only stores the null character, when matching it againstother strings.

For this we assume that each line of this file contains one or more fields separatedby one or more space characters. To simplify your work, you can assume thatother than the space characters used to separate the fields (there are no spacecharacters after the last field of each line), and the trailing newline character,there are no other while-space characters.

Thus, to run the program from a UNIX terminal using input redirection, we willenter the command

./unique f < input_file

In this command,fis a single digit between (and including) 0 and 9. Using theprevious example, if we run

./unique 1 < fruits.txt

The output will be:

navel orangeyellow bananared applegreen mangostrawberry

Note that the last line in the input file, i.e. apple, is not inthe output. This isnot because it matches any line that ends with apple, but because it matchesstrawberry! Find out why before starting the implementation.

Error Handling: In addition to the error case that you are supposed to handlein (i), your program should also print an appropriate error message and terminate(without printing any lines from the input file) if:

  • The user supplies illegal command-line arguments;
  • The number of command-line arguments supplied is incorrect(important:make sure that your program will still run without any command-line argu-ments as specified in (i)).

If there is more than one problem with user input, your program just has todetect one of them. You can assume that everything else regarding the input fileis correct.

Testing: In thea7testfolder, open the filea7q1btestto see the commandsused to test the program with three test cases. The output files, generated usingoutput redirection, are also given.

To check whether the output of your program on any test case iscorrect, redirectyour output into a file, and use the UNIX utilitydiff(learned in Lab 3) to

compare your output file with the output file in the above folder, to see whether
they are identical.
  1. [5 marks extra credit only] In this bonus question, you areasked to improve the im-plementation of your program by modifying it. Instead of creating new files, modifythe program you wrote for Question 1.Since during this process, you might introduce more bugs which you may or may nothave sufficient time to eliminate, you are strongly recommended to fully test yourprogram for Question 1 first and use thesubmitcommand to submit one version. Ifyou usegitto manage your source code (recommended, see Lab 7), also commit oneversion. If you do not usegit, at least make a copy of your program and store it in adifferent folder before modifying it. When you are ready to submit your work again,make sure to submit all the files that you are required to submit.One such improvement is based on the observation that many lines of the input filecontain fewer than 80 characters. However, the suggested implementation in Question1 mentioned that you can use a character array of length 81 to store the content of eachline, which may waste a lot of space for large files. To improvethe space efficiency, inthe node that stores one line of text, we can use a dynamically-allocated string thatis just large enough to store its content. Make sure that yourprogram still prints anerror message and exits if there is one line that is more than 80 characters long. Hint:one fixed-length string is still required for the entire file,but it is much less wastefulthan using a fixed-length string for each line.We learned that when a process terminates, the operating system will reclaim itsmemory. Thus, if we need the access to some of the dynamically-allocated variablesthroughout program execution, we do not have to deallocate the space of these variablesmanually in our program. However, it is still a good design choice to write code tofree all the dynamically-allocated memory space before theprogram terminates, asthis facilitates code reusing. Thus, in this question, you are asked to add code tofree memory storage for dynamically-allocated storage that is used throughout theexecusion of the program before the program terminates. Notethat to receive fullmarks, memory must be freed even for any error case.Be sure to fully test your program before you submit. Also use the sample input/outputgiven for Question 1 to make sure that your output format is correct.If you correctly implement only one of these two improvements, you will get partialmarks. Make sure to provide sufficient documentation, as documentation marks forQuestion 1 will be awarded according to the entire program you submit (see the mark-ing scheme). No bonus marks will be given if your solution doesnot use a linkedlist.


电子邮件地址不会被公开。 必填项已用*标注