关于算法:EIE110数据结构

EIE110
Homework 3 — String Functions
CS110/EIE110/LP101 2020 Fall
1 Introduction
There are many interesting functions on strings that we can implement, for example the famous
Caesar Cipher can encrypt and decrypt strings, whose idea is simply adding or subtracting a fixed
value from each character, as depicted by the above graph found from the internet
[1]
.
We will write a C program that will perform different operations on strings. The program is organized
using multiple functions and files. The emphasized knowledge aspects in this homework include the
following:
Function design and implementation
.c and .h files. A program with multiple files.
Friendly interaction between the computer and the user.
User’s menu of choices
Show friendly and clear messages to a user.
Clear input queue when needed. This is a technique to avoid input confusion.
When user’s input is wrong, show some error message, and ask the user to do input again.
Algorithms. We will implement some simple encryption and decryption algorithms.
2 Tasks of this homework
2.1 prepare multiple source files.
The program should have multiple files, whose names and brief descriptions are listed below.
myStrLib.h : function declarations (prototypes) of Section 2.2.
strShape.h : function declarations of Section 2.3.
strCypher.h : function declarations of Section 2.4.
strShape.c : function definitions of Section 2.2.
myStrLib.c : function definitions of Section 2.3.
strCypher.c : function definitions of Section 2.4.
driver.c : function definitions of Section 2.5
With these .h and .c files, a function defined in one .c file can be used by another .c file where the
corresponding .h file is included (#included).
2.2 Implement several string library functions
C standard library provide many helpful functions on string computation, they can be used including
the head string.h which contains the prototypes of these functions. In this homework we will
implement our versions of some string library functions, with the same parameters, return value, and
computation process as the standard library functions. At least three library functions should be
implemented, which are described by their prototype and comments as follows:
unsigned int my_strlen(const char str[]);
/ my version of the strlen() function./
char my_strcpy(char dest, const char *src);
/* my version of the strncpy() function
https://en.cppreference.com/w… */
int my_strcmp(const char str1, const char str2);
/* my version of the strcmp() function.
https://en.cppreference.com/w… */
In your program, the three library functions strlen , strcpy , and strcmp should not be used, they
should all be replaced by your versions.
In addition, you can implement other functions in string.h as you like Detailed documents of the
string library functions can be found online at some websites [2]
like www.cppreference.com .
2.3 Some design and implement several other tool functions
We wll design several functions related to string input and output. Their prototypes and computation
descriptions are as follows.
int input_long_str(char storage[], unsigned int sizeLimit, int endMark)
The function will record user’s input from the keyboard. The input can contain white spaces
and multiple lines.
The recorded input is saved in the array storage as a true C string.
sizeLimit should be the size (number of elements) of storage . So, at most
sizeLimit – 1 characters of user’s input can be recorded in storage , one more space
for the null character (\0) of a C string.
Recording the input will end in two cases:
a) The endMark signal appears (returned by getchar() ), which is chosen by user of this
function. It could be some special character , or the EOF signal.
b) Or, the number of input characters recorded is more than sizeLimit – 1 .
void clear_input_queue(void)
This function will try to clear the input queue of the stream stdin , as discussed in class.
void print_str_at_center(const char str[]);
Given a string, which can contain multiple lines, print these lines in some centered way. For
example, when the augment is a string of three lines:
123456789
abc
good
the function will prints:
123456789
abc
good
The longest line does not need to indent, but the shorter lines need to indent for some spaces.
void print_str_in_rectangle(const char str[], unsigned int row_width);
Given a string str , print its characters in a rectangle where each row contains row_width
characters.
Each newline characters and Tab character in str is printed as a space in the printing. The
reason of this requirement is that, the newlines make the square less compact, not good
looking; and the width of a Tab character on different systems is different, making the
printing effect less predictable.
For example, given the argument string
long long time ago
I can still remember
how the music used to make me smile
With row_width as 7, the printing will be :

long lo
ng time
ago I
can sti
ll reme
mber ho
w the m
usic us
ed to m
ake me
smile

You can design some other interesting functions about printing a string.
The “my” versions of these standard library functions should behave exactly the same as the original
library functions.
2.4 Implement cypher functions for strings.
We will implement some cypher functions. A simple encryption of a string is sorting its characters.
Correspondingly, the decryption function is to recover the original string from the sorted string. For
example, given a string:
long long time ago
After sorting, the sorted string (cyphertext) will look like the following, where the three spaces are on
the left end.
aegggillmnnooo
We have the following observations
By this kind of sorting, the ending null character is not moved, still appears at the last position in
the string.
The sorted string and the original string have the same number of characters. No character is
added or removed.
The operation of a sorting string can be understood as sorting its characters around.
The sorting is “in-space”, which means changing the array in its space, no separate array is
generated.
2.4.1 Cypher by selection sort
selection sort is an efficient and simple sorting algorithm. We can find good explanation of the
selection sort at wikipedia .
[3]
We use the selection sort to do encryption. However, in order to recover the original string, we have
to remember the history of how a character is moved in the process of sorting.
The following pseudo-code describe a modified version of selection sort so that the history of
moving characters is recorded.
Algorithm Name : Selection sort with history
Parameters:
arr : A character array
arrlen : The number of elements in arr . Especially, if arr is a C string, then arrlen is
the string length (not counting the ending ‘\0’).
history : An array of integers, whose space should be large enough to save arrlen – 1
integers.
Computation：
j = 0 / array index start from 0 to arrlen-1/
while j < arrlen-1 / only need to move arrlen – 1 times /
find a smallest item in the inclusive range arr[j] … arr[arrlen-1] , which means
from the j
th element of arr, and the last element of arr. Record the position v of this
smallest item.
swap arr[j] and arr[v] .
history[j] = v
j = j + 1
The following algorithm can recover a sorted array of characters back to its original sequence
according to some history of the sorting.
Algorithm Name : Recover sorted array of selection sort by history of sorting
Parameters:
arr : A character array, the sorted array to be recovered.
arrlen : The number of elements in arr . Especially, if arr is a C string, then arrlen is
the string length (not counting the ending ‘\0’).
history : An array of integers, whose space should be large enough to have arrlen – 1
integers.
Computation：
Using the history, the the characters of arr move back to their original positions before
the sorting. You can have to provide the details of doing so.
You need to write two functions that implement the encryption and decryption algorithm described
above.
ss_encrypt(char arr[], unsigned int arrLen, unsigned int history[]);
ss_dncrypt(char arr[], unsigned int arrLen, unsigned int history[]);
Put their definitions in strCypher.c , and prototypes in strCypher.h .
2.5 Design the user interface and test the functions
The driver.c file will implement the user interface and test all the functions that you created.
When the program is running, the user will repeatedly see a menu, and the program will respond to
the choice of the user, until the user choose to quit. The choice of the menu and the corresponding
computation of the program is described as follows:
a: Input two strings.
The user is asked to provide two strings and they are recorded. This is to test the
input_long_str() function. Then the three functions of my_strlen() , my_strcpy() , and
my_strcmp() are called using the two recorded input strings, and the results are printed. You
can decided the computation details. As long as the the three functions are called it will be fine.
b: Print strings in shapes
Print the first string centered, and the second string in rectangle. This is to test the two functions
print_str_centered() and print_str_in_rectangle() .
c: Use the cypher
Call the function ss_encrypt() with the recorded strings, and show the results of encryption.
Call ss_decrypt() with the cypher text, show that the original string can be recovered.
q: quit the program.
If you have designed and implemented some other functions, make sure that they are also tested.
Submission
Upload your files at the webpage address of this homework on Moodle.
The uploaded files can include only the following:
The source files (.c and .h files),
An optional document file (.txt, .md, .docx) describing your work, like: what features of the
homework are achieved; what are the remaining problems; how did you solve the difficulties
that you met, some screen record of compiling and running the program …
About homework submission in a group:
at most 3 students can form a group to submit the homework. You can surely do the
homework alone.
One group only need to submit the homework by once by one student. The other members
do not need to submit anything, or just submit one .txt file saying who are the members of
the group and who submitted the homework.
In each file that you submit, record the names in Chinese (if you are not an international
student) and English letters, classes of each student, last 5 digits of student ID, as
comments. For example:
/* homework 1. Group members:
李⽩ Li, Bai CS110 D1
杜甫 Du, Fu EIE110 D2
李清照 Li, Qingzhao CS110 D3
*/
Deadline: Dec 18 2020

1. https://www.geeksforgeeks.org… ↩
2. C documentation can also be found at www.cplusplus.com, although the teacher prefers the
   cppreference.com. ↩
3. https://en.wikipedia.org/wiki… ↩