CS110留学生编程代写、代做C++程序代写、program程序语言调试

日期：2021-01-09 11:10

Homework 3 -- String Functions

CS110/EIE110/LP101 2020 Fall

Macau Univ. of Sci. and Tech.

Instructor: Zhiyao Liang

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/c/string/byte/strcpy */

int my_strcmp(const char * str1, const char * str2);

/* my version of the strcmp() function.

https://en.cppreference.com/w/c/string/byte/strcmp */

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/caesar-cipher-in-cryptography/ ?

2. C documentation can also be found at www.cplusplus.com, although the teacher prefers the

cppreference.com. ?

3. https://en.wikipedia.org/wiki/Selection_sort ?