Data Structure教学课件（华南理工）Tutorial02 ans.pdfVIP

Data Structure (Semester 1, 2014-2015) Tutorial 02 - Answer Prepared by Dr. Patrick Chan Date: September-2014 1. Write a series of C++ statements that uses that List ADT of Figure 4.1 to create a list capable of holding twenty elements and which actually stores the list with the following configuration: 2, 23 | 15, 5, 9 Answer: list L1(20); L1.append(2); L1.append(23); L1.append(15); L1.append(5); L1.append(9); L1.next(); L1.next(); Data Structure – Tutorial 2 1 2. A common problem for compliers is to determine if the brackets in a string are balanced and properly nested. For example, the string “()(()(()()))” contains properly nested pairs of brackets, but the string “)())” does not. Write an algorithm that returns true if a string contains properly nested and balanced brackets, and false otherwise. Hints: You may want to use charAt(pos) in string data type. It will return the character of at pos position. e.g. if a = ‘abc’, a.charAt(2) is equal to ‘b’. Answer: bool balance(String str) { Stack S; int pos = 0; while (str.charAt(pos) != NULL) { if (str.charAt(pos) == ’(’) S.push(’(’); else if (str.charAt(pos) == ’)’) if (S.isEmpty()) return FALSE; else S.pop(); pos++; } if (S.isEmpty()) return TRUE; else return FALSE; } 3. Let Q be a non-empty queue, and let S be an empty stack. Using only the stack and queue ADT functions and a single element variable X, write an algorithm to reverse the order of the elements