程序代写代做代考 c++ Tutorial7(Assignment4)

Tutorial7(Assignment4)

CSCI 1120
Introduction to Computing Using C++
Tutorial 7

WANG Fangzhou
Email : fzwang@cse.cuhk.edu.hk
QI Lu
Email : luqi@cse.cuhk.edu.hk

28th Oct, 2019

1

Table of contents

● Complementary Knowledge
○ C string
○ 2D array and char**
○ Case conversion

● Assignment 4
○ Introduction
○ Input & output requirements
○ Helper functions
○ Required Functions
○ Restrictions

● Indexes array for faster dictionary lookup(10% marks)

2

Complementary Knowledge

(1) C string

Examples:
● char str1[6] = {‘H’, ‘e’, ‘l’, ‘l’, ‘o’, ‘\0’};
● char str2[] = “Hello”;
● If you look into the memory, the

above str1 and str2 should look the
same. (As the right figure shows)

Strings are actually one-dimensional array of characters
terminated by a null character ‘\0’

3

Complementary Knowledge

(1) C string
How can we get the length of a cstring?

Ans : strlen ( const char * str ) returns the
length of the C string str.

The function is from library.

4

Example:

char str[10] = “WFZ”;

cout << strlen(str) << endl; // will print 3 char str[10] = “”; cout << strlen(str) << endl; // will print 0 Complementary Knowledge (2) 2D array and char** Static 2D array: int c[2][3] = {{1, 2, 3}, {4, 5, 6}}; char matrix1[3][3] = { {'a', 'b', 'c'}, {'d', 'e', 'f'}, {'c', 's', 'e'}}; char matrix2[3][3] = { {'a', 'b', 'c'}, {'d', 'e', '\0'}, {'c', ‘\0', 'e'}}; What will be the output if you cout matrix1[0] ? 1 2 3 4 5 6 c : matrix1: 'a' 'b' 'c' 'd' 'e' 'f' 'c' 's' 'e' matrix2: 'a' 'b' 'c' 'd' 'e' '\0' 'c' '\0' 'e' Ans: abcdefcse + some random sequence until we luckily hit a '\0' 5 Complementary Knowledge (2) 2D array and char** Static 2D array: int c[2][3] = {{1, 2, 3}, {4, 5, 6}}; char matrix1[3][3] = { {'a', 'b', 'c'}, {'d', 'e', 'f'}, {'c', 's', 'e'}}; char matrix2[3][3] = { {'a', 'b', 'c'}, {'d', 'e', '\0'}, {'c', ‘\0', 'e'}}; What about matrix2[0], matrix2[1], matrix2[2] ? 1 2 3 4 5 6 c : matrix1: 'a' 'b' 'c' 'd' 'e' 'f' 'c' 's' 'e' matrix2: 'a' 'b' 'c' 'd' 'e' '\0' 'c' '\0' 'e'Ans: abcde ; de ; c 6 Complementary Knowledge (2) 2D array and char**(con’t) Dynamic 2D array: char* : pointer to char char**�pointer to pointer to char How to visit a char via char** ? Assume p is a char**, p[0]: a char* pointing to certain address p[0][0]: the char in the address pointed by p[0] p[0][1]: the char in the address pointed by (p[0] + 1) Example of char** 7 Complementary Knowledge (3) Case conversion Example:(i) char upper = 'a' - 32; cout << upper; // prints A (ii) char lower = 'B' + 32; cout << lower; // prints b 8 … Difference = 32 Complementary Knowledge (3) Case conversion From library we have those functions.

Uppercase to lowercase: int tolower(int c)

Lowercase to uppercase: int toupper(int c)

Note: Since the return value of the above functions is
int, type conversion may be involved.

Example:
(i)
char str[] = “Test”;
for(int i = 0; i <= 3; i++) { cout << (char)tolower( str[i] ); } Output: test (ii) char str[] = “Test”; for(int i = 0; i <= 3; i++) { cout << (char)toupper( str[i] ); } Output: TEST 9 Assignment 4: Word Search Puzzles (1) Introduction Given: I. A matrix consisting of lowercase alphabets II. A dictionary containing some words (we call it “legal words” for convenience) Matrix example 3964 10 act add ... able acid ... zippy absorb ... xenophobia xylography Dictionary example 10 Assignment 4: Word Search Puzzles (1) Introduction Matrix example 3964 10 act add ... able acid ... zippy absorb ... xenophobia xylography Dictionary example Want to: I. Find all legal words in the matrix (Scan for each row and column) One hit: bee 11 Assignment 4: Word Search Puzzles (1) Introduction Matrix example 3964 10 act add ... able acid ... zippy absorb ... xenophobia xylography Dictionary example Want to: I. Find all legal words in the matrix (Scan for each row and column) Another hit: beer 12 Assignment 4: Word Search Puzzles (1) Introduction Matrix example 3964 10 act add ... able acid ... zippy absorb ... xenophobia xylography Dictionary example Want to: I. Find all legal words in the matrix (Scan for each row and column) 13 Assignment 4: Word Search Puzzles (1) Introduction Matrix example 3964 10 act add ... able acid ... zippy absorb ... xenophobia xylography Dictionary example Want to: I. Find all legal words in the matrix (Scan for each row and column) 14 Assignment 4: Word Search Puzzles (1) Introduction Matrix example 3964 10 act add ... able acid ... zippy absorb ... xenophobia xylography Dictionary example Want to: I. Find all legal words in the matrix (Scan for each row and column) 15 Assignment 4: Word Search Puzzles (1) Introduction Matrix example 3964 10 act add ... able acid ... zippy absorb ... xenophobia xylography Dictionary example Want to: I. Find all legal words in the matrix (Scan for each row and column) 16 Assignment 4: Word Search Puzzles (1) Introduction Matrix example 3964 10 act add ... able acid ... zippy absorb ... xenophobia xylography Dictionary example Want to: I. Find all legal words in the matrix (Scan for each row and column) 17 Assignment 4: Word Search Puzzles (1) Introduction Matrix example 3964 10 act add ... able acid ... zippy absorb ... xenophobia xylography Dictionary example Want to: I. Find all legal words in the matrix (Scan for each row and column) 18 Assignment 4: Word Search Puzzles (1) Introduction Matrix example 3964 10 act add ... able acid ... zippy absorb ... xenophobia xylography Dictionary example Want to: I. Find all legal words in the matrix (Scan for each row and column) 19 Assignment 4: Word Search Puzzles (1) Introduction Want to: I. Find all legal words in the matrix (Scan for each row and column) II. Capitalize those words in the matrix 20 Assignment 4: Word Search Puzzles (2) Input & Output requirement Input: The matrix to be solved and dictionary will be stored in two text files(eg: data1.txt, dict.txt). Output: (1) Print words with their row/col number (2) Print the solved matrix(with words capitalized) Notes: For interaction part, please refer to the assignment specification for detail (Sample Run section) 21 Assignment 4: Word Search Puzzles (2) Input & Output requirement File structure(where to put data files?) For visual studio user: The data files should be put in the project folder, at the same directory level with the source files. 22 Assignment 4: Word Search Puzzles (2) Input & Output requirement File structure(where to put data files?) For Xcode user: Pay attention to where the executable files are generated. And put the data files at the same directory level with the executable file. For reference(Xcode): https://www.youtube.com/watch?v=JM1D0yxAYHk Notes: You can also choose to place the data files in another folder, and use absolute path to locate those data files, e.g. typing C:\Users\xxxx\Desktop\datafiles\dict.txt 23 https://www.youtube.com/watch?v=JM1D0yxAYHk Assignment 4: Word Search Puzzles (3) Helper Functions helper.h and helper.cpp will be provided to help you with the assignment. 24 Example of using helper functions: Assignment 4: Word Search Puzzles (3) Helper Functions 25 Notes: Do remember to call delete2DArray when you will no longer use it. (To avoid memory leaks ) More: https://www.geeksforgeeks.org/memory-leak-in-c-and-how-to-avoid-it/ https://www.geeksforgeeks.org/memory-leak-in-c-and-how-to-avoid-it/ Note: If you run on XCode, uncomment the line //#define XCODE in the helper.h header file. Assignment 4: Word Search Puzzles (3) Helper Functions 26 Assignment 4: Word Search Puzzles (4) Required Functions void search( char** puzzle, int rows, int cols, char** dict, int words, int wlen, int indexes[][26], char** solved_puzzle, bool vertical = false); • This function will search the puzzle according to the given dictionary dict in one direction(either horizontally or vertically). • And indexes (we will talk about it later) can help to increase the matching speed. Result will be stored in solved_puzzle and you can specify the searching direction via vertical. Notes: The vertical flag may be used to control whether you output “row” or “col” when you found a match. (But you are free to use it in other ways) 27 Assignment 4: Word Search Puzzles (4) Required Functions void transpose (char** a, char** b, int rows, int cols); Transpose is an operation that flips a matrix by switching its rows with its columns. Intuition: Searching a matrix A vertically equals searching the transpose of A horizontally. So that we will not need to write another function to search matrix vertically. 28 Assignment 4: Word Search Puzzles (4) Required Functions void print2DArray(char** arr, int rows, int cols); This function prints a puzzle array arr to the screen. Refer to the Sample Runs section for the expected format of the output. Notes: You must not modify the prototypes of the aforementioned functions. 29 Assignment 4: Word Search Puzzles (5) Restrictions • No global variables (except global constants) • Don’t use std::string class in your code. Use char arrays or char pointers instead. • No Non-standard C++ or third-party library functions. But standard library functions for processing C-strings are allowed, like strlen(), tolower(), toupper(), etc. • The use of the helper source is not optional but mandatory. That means, you should not reinvent your own functions for doing file reading. • Don’t modify or add any code to the helper.h and helper.cpp files because they won’t be included in your submission. You must implement your program all inside the wordsearch.cpp file which is the only file to be submitted. 30 31 Indexes array for faster dictionary lookup(10% marks) Indexes array: indexes[i][x-'a']: stores the index for the first words in dictionary whose length is i and start with character x. Q: How can indexes speed up the dictionary lookup? (note that large dictionary has over 370k words!) A: The dictionary is sorted in (1) ascending word length, and (2) then in alphabetic order. For example, a word with length 6 will never appear in the section where word lengths are less than 6. Then we can skip plenty of meaningless comparison. Notes: If you decide to give up using this index mechanism, you may just pass a null pointer (NULL or nullptr) as the indexes parameter for the search() function. (But 10% marks will be lost) 'a' 0 'b' 1 'c' 2 'z' 25 0 -1 -1 -1 … -1 -1 -1 1 -1 -1 -1 … -1 -1 -1 2 -1 -1 -1 -1 -1 -1 3 0 15 35 … 217 4 219 231 283 … 852 … … … … … … … … 10 3688 3723 3728 … 3962 -1 -1 … -1 -1 -1 … -1 -1 -1 50 -1 -1 -1 … -1 -1 -1 Index Word 0 act 1 add ... ... 15 bad ... ... 35 cab ... ... 217 zap ... ... 219 able ... ... 852 zany ... ... 3688 absolutely ... ... 3962 xenophobia ... ... Dictionary array Indexes array word length first letter of word Indexes array 32 What to do when we hit a -1 at a particular indexes element like indexes[10][25] ? Ans: This implies that words of length 10 starting with letter ‘z’ do not exist in the dictionary. Simply bypass this checking. Assignment 4: Word Search Puzzles Better way to check your answer: Copy and paste your program output and our sample program output to a diff checker like https://www.diffchecker.com and see if there are any differences. 33 https://www.diffchecker.com/ Assignment 4: Word Search Puzzles Due: 8:00 PM , Saturday, November 9, 2019 Submission: wordsearch.cpp file only 34 Reference: http://www.annigeri.in/2011/11/dynamic-two-dimensioned- arrays-in-c.html 35 http://www.annigeri.in/2011/11/dynamic-two-dimensioned-arrays-in-c.html