UPE Tutoring:

CS 31 Midterm 2 Review

Sign-in http://bit.ly/2QCmwRH

​

Slides link available upon sign-in

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Arrays

​

• Valid declarations:

​

int arr[10];

​

bool list[5];

​

const int MAX_SIZE = 10;

string words[MAX_SIZE];

​

int arr[] = {1, 2, 3};

2

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Arrays (cont.)

• Rules for specifying size:
• Must be included in the brackets
• Cannot involve a variable unless it is a constant known at compile time
• The only time size can be left out is when a list of its contents is included
• Not allowed in C++:
• int arr[]; // Size not included.
• /****** Use of non-const variable. ******/

int x;

cin >> x;

char buffer[x];

3

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Passing Arrays to Functions

• Parameter Syntax
• (..., type name[], ...)
• Arrays are default passed by reference
• Any changes made to the array will be retained outside of the function scope

4

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Passing Arrays to Functions (cont.)

• Size of array should be passed to the function
• Call to the function just passes in array name

​

// arr is the array itself, n is the size.

int firstOdd(int arr[], int n) {

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1)

return i;

}

return n; // If no odd number found.

}

​

5

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

6

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

7

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

8

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

9

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

10

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

11

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

12

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

13

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

14

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

15

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

16

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

17

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

18

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

19

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

20

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

21

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

22

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

23

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

24

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

25

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

26

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

27

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

28

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

29

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

30

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

31

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

32

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

What does this print?

​

// arr is the array itself, n is the size.

int changeOdd(int arr[], int n) {

int count = 0;

for (int i = 0; i < n; i++) {

if (arr[i] % 2 == 1) {

arr[i]--;

count++;

}

}

n++;

return count;

}

int main() {

int n = 5;

int arr[5] = {2, 6, 3, 5, 10};

cout << changeOdd(arr, n) << endl;

}

​

> 2

33

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Printing Arrays

• To print an array, we need to use a loop to print each element.
• Printing the name will just print the starting address of the array

​

string arr[] = {“Smallberg”, “CS31”, “Midterm”};

for (int i = 0; i < 3; ++i) {

cout << arr[i];

}

​

34

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Out of Bounds Errors

• Occur anytime you can access memory past the end (or beginning) of an array
• Only certain spaces in memory have useful data
• Anything outside is essentially garbage
• Hard to debug. C++ doesn’t do bounds checking on array access so out of bounds accesses can often go unnoticed.

​

string array[3] = {“CS31”, “Smallberg”, “Midterm”};

cout << array[3] << endl; // Out of bounds error!

​

35

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Out of Bounds Example

Do we have an out of bounds memory access here?

​

// Assume arr only contains n elements.

int countFives(int arr[], int n) {

int count = 0;

for (int i = 0; i <= n; ++i) {

if (arr[i] == 5) {

count++;

}

}

return count;

}

36

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Out of Bounds Example

Do we have an out of bounds memory access here?

​

// Assume arr only contains n elements

int countFives(int arr[], int n) {

int count = 0;

for (int i = 0; i <= n; ++i) {

if (arr[i] == 5) { Yes! The for loop will access the

count++; element at the nth index.

}

}

return count;

}

37

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Practice Question: Index of First Repeated

​

Given an array of integers and the size of the array, write a function firstRepeat that returns the index of the first repeat element. Return -1 if there are no duplicate elements.

​

Input: int arr[] = {1, 2, 3, 2, 4}; int size = 5;

Output: 3

​

Input: int arr[] = {1, 2, 3, 7, 0, 2, 7, 3, 1}; int size = 9;

Output: 5

​

(Contributed by Carter Wu)

38

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Solution: Index of First Repeated

We use nested for loops:

​

int firstRepeat(int a[], int n) {

for (int i = 1; i < n; i++)

for (int j = 0; j < i; j++)

if (a[i] == a[j])

return i;

return -1;

}

39

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Practice Question: What Makes CS Beautiful

int main() {

string oneD[] = {"Zayn", "Louis", "Harry", "Niall", "Liam"};

int size = 5;

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

}

​

40

What does the string array contain after this code is executed?

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

41

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

42

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

43

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

44

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

45

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

46

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

47

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

48

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

49

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

50

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

51

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

52

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

53

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

54

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

55

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

56

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

57

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

58

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

59

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

60

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

61

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

62

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

63

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

64

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

65

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

66

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

67

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

68

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Walkthrough

string oneD[] = {....};

int size = 5;

​

for (int i = 0; i < size; i++) {

int min = i;

for (int j = i + 1; j < size; j++)

if (oneD[j] < oneD[min])

min = j;

string temp = oneD[i];

oneD[i] = oneD[min];

oneD[min] = temp;

}

oneD[4] = "RIP" + oneD[4];

​

69

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Solution: What Makes CS Beautiful

After walking through two iterations of the outer for loop, we notice that the loops are sorting the array into alphabetical order!

(this is called Selection Sort, but don’t worry about it for now) https://en.wikipedia.org/wiki/Selection_sort

​

Initial: ["Zayn", "Louis", "Harry", "Niall", "Liam"]

i = 0: ["Harry", "Louis", "Zayn", "Niall", "Liam"]

i = 1: ["Harry", "Liam", "Zayn", "Niall", "Louis"]

i = 2: ["Harry", "Liam", "Louis", "Niall", "Zayn"]

i = 3: ["Harry", "Liam", "Louis", "Niall", "Zayn"]

i = 4: ["Harry", "Liam", "Louis", "Niall", "Zayn"]

Final Answer: ["Harry", "Liam", "Louis", "Niall", "RIPZayn"]

70

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Practice Question: Transpose

71

Implement a function that takes in a pointer to an nxn 2d array of ints and transposes it. That is, the rows should become the columns and vice versa.

​

void transpose(int** matrix, int n);��Example: 1 2 3 (n = 3) → 1 4 7� 4 5 6 2 5 8� 7 8 9 3 6 9

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Solution: Transpose

72

void transpose(int** matrix, int n) {� for (int i = 0; i < n; i++) {

for (int j = 0; j < i; j++) {

int temp = matrix[i][j];� matrix[i][j] = matrix[j][i];

matrix[j][i] = temp;

}

}�}

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Practice Question: Resolve Merge Issues

73

// Assume arr1 and arr2 are ordered from least to

// greatest and have size n1 and n2, respectively.�// Also assume arr3 has size n1 + n2.

void merge(int arr1[], int n1, int arr2[], int n2,

int arr3[]) {

int i1 = 0, i2 = 0, i3 = 0;

while (i3 < n1 + n2) {� if (arr1[i1] < arr2[i2]) {

arr3[i3] = arr1[i1];

i1++;

} else if (arr2[i2] < arr1[i1]) {

arr3[i3] = arr2[i2];

i2++;

}

i3++;

}

}

​

This function attempts to merge two arrays arr1 and arr2 that are ordered from least to greatest into a third array arr3, so that arr3 contains the contents of both arr1 and arr2 ordered from least to greatest.

�Example: arr1 = {1, 2, 5}, arr2 = {2, 4, 6}� → arr3 = {1, 2, 2, 4, 5, 6}��Can you find and fix the bugs in this function so that it performs correctly?

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Spring ‘19) https://tinyurl.com/y62uz9sc

Practice Question: Resolve Merge Issues

74

// Assume arr1 and arr2 are ordered from least to

// greatest and have size n1 and n2, respectively.�// Also assume arr3 has size n1 + n2.

void merge(int arr1[], int n1, int arr2[], int n2,

int arr3[]) {

int i1 = 0, i2 = 0, i3 = 0;

while (i3 < n1 + n2) {� if (arr1[i1] < arr2[i2]) { // what if i1>=n1

arr3[i3] = arr1[i1]; // or i2 >= n2??

i1++;

} else if (arr2[i2] < arr1[i1]) { // same!

arr3[i3] = arr2[i2];

i2++;

} // what do we do if arr1[i1] == arr2[i2]?

i3++;

}

}

This function attempts to merge two arrays arr1 and arr2 that are ordered from least to greatest into a third array arr3, so that arr3 contains the contents of both arr1 and arr2 ordered from least to greatest.

�Example: arr1 = {1, 2, 5}, arr2 = {2, 4, 6}� → arr3 = {1, 2, 2, 4, 5, 6}��Can you find and fix the bugs in this function so that it performs correctly?

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Spring ‘19) https://tinyurl.com/y62uz9sc

Solution: Resolve Merge Issues

75

void merge(int arr1[], int n1, int arr2[], int n2,

int arr3[]) {

int i1 = 0, i2 = 0, i3 = 0;

while (i1 < n1 && i2 < n2) {� if (arr1[i1] < arr2[i2]) {

arr3[i3] = arr1[i1];

i1++;

} else if (arr2[i2] <= arr1[i1]) {

arr3[i3] = arr2[i2];

i2++;

}

i3++;

}

// continued...

while (i1 < n1) { // only one of these will run

arr3[i3] = arr1[i1];

i1++;

i3++;

}

while (i2 < n2) {

arr3[i3] = arr2[i2];

i2++;

i3++;

}

}

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

C Strings

• C does not have the string class (or classes at all!)
• In C, we cannot declare strings or use class methods:
• string x = “hello”;
• x.size() // This is okay in C++, but not in C.
• Instead, we represent strings using char arrays:
• char y[] = “hello”;
• Cannot use C++ string functions with it
• y.size(), y.substr(...), etc. // Syntax errors.
• #include <cstring> provides functions like strlen
• strlen(x) returns 5

​

76

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Ascii: Characters are actually integers

77

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Ascii (cont.)

int x = ‘G’; // x is now 71.

x -= 1; // x is now 70.

char y = x; // y is now F.

int z = ‘5’; // z is now 53.

78

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

C Strings (cont.)

• The end of a C string is marked by a null byte (‘\0’)
• Null byte has ASCII value 0
• strlen simply looks for the null byte for you

​

char arr[] = “hello”;

for (int i = 0; arr[i] != ‘\0’; i++) // Standard for loop to iterate

// through c-strings.

​

Note: arr[i] != ‘\0’ and arr[i] != 0 are the same, as ascii value of ‘\0’ is 0.

​

79

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

C Strings (cont.)

​

// A null character is automatically

// put in index 5.

char x[50] = “hello”;

​

// Because we have more space in the array

// (50 total), we can add more characters.

x[5] = ‘s’;

x[6] = ‘\0’;

​

80

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

C Strings (cont.)

​

// A null character is automatically

// put in index 5.

char x[50] = “hello”;

​

// Because we have more space in the array

// (50 total), we can add more characters.

x[5] = ‘s’;

x[6] = ‘\0’;

​

81

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

C Strings (cont.)

​

// A null character is automatically

// put in index 5.

char x[50] = “hello”;

​

// Because we have more space in the array

// (50 total), we can add more characters.

x[5] = ‘s’;

x[6] = ‘\0’;

​

82

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Practice Question: C Strings - removeNonAlpha

​

Given a C String, write a function removeNonAlpha that removes all non-alphabet chars in the C String. When removing a non-alphabet char, you should shift all following chars one position to the left. Don’t forget to shift the null byte as well!

​

char cstr[] = "S5mal.lb-erg! Is+ C$s Senpai$$$";

removeNonAlpha(cstr);

for (int i = 0; cstr[i] != '\0'; i++)

cout << cstr[i];

​

// OUTPUT: SmallbergIsCsSenpai

​

(Contributed by Matt Wong)

83

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Solution: C Strings - removeNonAlpha

The outer for loop iterates through every character position in the C String. The inner while loop and for loop shifts the characters to the left to remove all non-alphabet characters.

​

#include <cctype>

​

void removeNonAlpha(char str[]) {

for(int i = 0; str[i] != '\0'; i++)

while ( !isalpha(str[i]) && str[i] != '\0' )

for(int j = i; str[j] != '\0'; j++)

str[j] = str[j+1];

}

84

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Pointers

• A pointer is the memory address of a variable.

​

• The & operator can be used to determine the address of a variable to be stored in the pointer.
• The * operator can be used to dereference a pointer and get the value stored in the variable that is being pointed to.

double d = 10.0;

double *dp; // pointer that holds the address of a double

dp = &d; // stores the address of d into dp

*dp = 20.0; // changes the value of d from 10.0 to 20.0

​

​

85

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Pointers

int var = 20; // actual variable declaration�int *ip; // pointer variable declaration

// store address of var in ip�ip = &var;��cout << "Value of var variable: ";�cout << var << endl;��// print the address stored in ip pointer�cout << "Address stored in ip variable: ";�cout << ip << endl;��// access the value at address stored in pointer�cout << "Value of *ip variable: ";�cout << *ip << endl;�

​

​

​

> Value of var variable: 20

> Address stored in ip variable: 0xBFC601AC

> Value of *ip variable: 20

86

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Pointer Arithmetic

int arr[] = {10, 20, 30, 40};

​

int *ptr = arr; // arr == &arr[0]

cout << *ptr << endl;

​

ptr++;

cout << *ptr << endl;

​

ptr = ptr + 1;

cout << *ptr << endl;

​

ptr--;

cout << *(ptr + 2) << endl;

​

> 10

> 20

> 30

> 40

87

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Pointers – new and delete

• The new operator can be used to create dynamic variables. These variables can be accessed using pointers.

string *p;

p = new string;

p = new string(“hello”);

• The delete operator eliminates dynamic variables.

delete p;

• Note: Pointer p is now a dangling pointer! Dereferencing it is dangerous and leads to undefined behavior. One way to avoid this is to set p to NULL after using delete.

88

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Pointers – Dynamic Arrays

• A pointer can also be used when creating a dynamic array. Dynamic arrays are useful because their size can be determined while the program is running!

int *ptr;

int arraySize;

cin >> arraySize;

ptr = new int[arraySize];

• To destroy the dynamically allocated array, use the delete[] operator.

delete[] ptr;

89

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Pointers – the Heap and the Stack

• As it turns out, there are two places where your variables live.
• The first is the stack, which is the place you're most familiar with. With local variables, the compiler is like a city planner who decides where each variable should live.

90

int a[4]

int k

string s

100

116

120

void foo() {

int a[4]; // Stored at 100

int k; // Stored at 116

string s; // Stored at 120

}

Variables in the calling function.

0-100

If the size isn't specified at compile time, how would the compiler know where to put k or s?

When foo called

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Pointers – the Heap and the Stack (cont.)

• As it turns out, there are two places where your variables live.
• The first is the stack, which is the place you're most familiar with. With local variables, the compiler is like a city planner who decides where each variable should live.

91

Vacant

Vacant

Vacant

100

116

120

void foo() {

int a[4]; // Stored at 100

int k; // Stored at 116

string s; // Stored at 120

}

Variables in the calling function.

0-100

When the function returns, the variables are evicted from their addresses.

When foo returns

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Pointers – the Heap and the Stack (cont.)

• As it turns out, there are two places where your variables live.
• The second is the heap, which is the place where dynamic variables live. Dynamic variables essentially lease some part of the heap to live in.

92

int[5]

2000

void bar() {

int *p = new int[5];

string *q = new string("Cat");

}

"cat"

2248

HEAP

string *q

int *p

136

140

When bar called

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Pointers – the Heap and the Stack (cont.)

• As it turns out, there are two places where your variables live.
• The second is the heap, which is the place where dynamic variables live. Dynamic variables essentially lease some part of the heap to live in.

93

int[5]

2000

"cat"

2248

HEAP

Contains a memory leak!

void bar() {

int *p = new int[5];

string *q = new string("Cat");

}

When bar returns

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Pointers – the Heap and the Stack (cont.)

• As it turns out, there are two places where your variables live.
• The second is the heap, which is the place where dynamic variables live. Dynamic variables essentially lease some part of the heap to live in.

94

void bar() {

int *p = new int[5];

string *q = new string("Cat");

delete[] p;

delete q;

}

HEAP

Don't forget to clean up after yourself!

When bar returns

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Practice Question: Array Traversal w/ Pointers

Write a function that sums the items of an array of n integers using only pointers to traverse the array.

95

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Solution: Array Traversal w/ Pointers

Simple array traversal, but with pointers. To get to item i, add i to your head pointer then dereference. This works because the compiler knows the size of an item in your array in C++. Sum values as you go by adding them to a total value created outside of the for loop.

int sum(int *head, int n) {

int total = 0;

for (int i = 0; i < n; i++) {

total += *(head + i);

}

return total;

}

​

​

​

​

sum(arr, 5);

​

​

96

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Practice Question: C String Reversal with Pointers

97

Implement the function reverse, which takes a C String as an argument and prints out the characters in reverse order. You are not allowed to use the strlen function, and you must use pointers in any traversal of the C String.

​

void reverse(const char s[]);

​

int main() {

char str[] = “stressed”

reverse(str);

// OUTPUT: desserts

}

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Solution: C String Reversal with Pointers

98

void reverse(const char s[]) {

const char *p = s; // create a new pointer for our traversal

while (*p != '\0') { // move the pointer to the end of the C String

p++;

}

p--; // set p to point at the last char in the C String

while (p >= s) { // print out chars as we traverse back to the beginning

cout << *p;

p--;

}

cout << endl;

}

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Practice Question: strcat

99

Implement the C string concatenation function. The function takes two C strings and copies the chars from the source C string to the end of the destination C string. The original null byte of the destination is overwritten when copying the source. Return the destination pointer at the end of the function. You do not know the size of the destination and source C strings (so you can’t create a temporary C string to store all of the characters!)

​

char* strcat(char* destination, const char* source);

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Solution: strcat

100

char* strcat(char* destination, const char* source) {

char* d = destination;

while (*d) // this loop sets d to point at the null byte of destination

d++;

const char* s = source;

while (*s) { // this loop copies the source C string to where d is pointing

*d = *s;

d++;

s++;

}

*d = '\0'

return destination; }

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Structs

• A struct is a collection of data that is treated as its own special data type. We use them to organize data that belongs together.

struct Person {

int age;

string name;

}; // Must end with semicolon!

• Structs can store any number of any other data type, accessed using . (the dot operator). These stored values are called member variables.

101

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Structs

You can declare a struct outside of any functions and treat it as a normal variable, for the most part. A struct can even contain another struct!

struct Date {

int day, month, year;

};

​

struct Person {

Date birthday;

string name;

double money;

};

void doubleMoney(Person& guy) {

guy.money *= 2;

}

​

int main() {

Person p1;

p1.name = “Smelborp”;

p1.money = 3.50;

p1.birthday.day = p1.birthday.month = 1;

Person p2 = p1; // Perfectly legal

doubleMoney(p2);

cout << p2.money; // 7

cout << p1.money; // 3.5

Person p3 = { p1.birthday, “Jimbo”, 3.5 };

p2 += p1; // ERROR! How do you add people?!

}

102

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Structs – Tips

• Structs are a good way to keep code looking organized and readable
• When declaring a struct, member variables with primitive types will be left uninitialized. Classes will be constructed with their default constructor.
• Long story short: you must assign them yourself!
• Always remember the semicolon! It’s there so that you can declare struct variables at the same time that you define the struct.

struct Circle {

int radius;

} ring, hoop; // This creates two Circle structs named ring and hoop

103

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH

Good luck!

Sign-in http://bit.ly/2QCmwRH

Slides http://bit.ly/2NXAYls

Practice https://github.com/uclaupe-tutoring/practice-problems/wiki

​

Questions? Need more help?

• Come up and ask us! We'll try our best.
• UPE offers daily computer science tutoring:
• Location: ACM/UPE Clubhouse (Boelter 2763)
• Schedule: https://upe.seas.ucla.edu/tutoring/
• You can also post on the Facebook event page.

104

UPSILON PI EPSILON

CS 31 Midterm 2 Review (Fall ‘19) http://bit.ly/2QCmwRH