List of Figures
2.1 Pushing and popping data on a stack. (a) Originally, the top of the stack
stores the number 720. The number 653 is pushed onto the top of the stack.
(b) Data are retrieved (popped) from the stack. Pushes and pops can only
occur at the top of the stack. Although this figure illustrates the idea with
integers, a stack is a general concept and can manage any type of data. . 12
2.2 The flow of the program as indicated by the numbers 1, 2, and 3. . . . . . 12
2.3 The return location is the place where the program continues after the
function f1 returns. .............................. 13
2.4 The flow of the program with the three functions. . . . . . . . . . . . . . 14
2.5 The return locations (RLs) are marked at the lines after calling f2 (RL A)
and f1 (RLB). ................................. 14
2.6 Enter the commands at the bottom of DDD. . . . . . . . . . . . . . . . . . 29
2.7 Use the mouse to select a inside g1. Click the right mouse button and select
“Display a”. Do the same for b. ........................ 30
2.8 The values of a and b in function g1 areshown................ 30
2.9 Use the f commandtoseedifferentframes. ................. 31
8.1 A two-dimensional array has an array of pointers as the first dimension.
Eachelementpointstoanarray. ....................... 120
9.1 (a) Execution time for selection sort and quick sort. (b) The ratio of the
execution time. Please note that both axes use a logarithmic scale. . . . . 140
10.1 A file is a stream. This example uses the program source code as the input
file. (a) After calling fopen, the stream starts from the very first character of
the file and ends with EOF. EOF is a special character that does not actually
exist in the file, but signifies that there is no data left in the stream. (b),(c)
Each time fgetc is called, one character is taken out of the stream. (d)
After calling fgetc enough times, all the characters in the file are retrieved.
We have not yet attempted to read past the end of the file. (e) Finally, the
end of file character EOF is returned because there are no more characters
inthefile. .................................... 143
12.1 To decide f(n), consider the possibilities for the first ball. If the first ball
is B, the remaining n − 1 balls have f(n − 1) possibilities. If the first ball
is R, then the second ball must be B and the remaining n − 2 balls have
f(n − 2) possibilities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
12.2 To decide f (n), consider the possibilities for the first ball. If the first ball is
G or B
, the remaining n − 1 balls have f(n − 1) possibilities. If the first ball
is R, the second ball must be G or B and the remaining n − 2 balls have
f(n − 2) possibilities. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
xiii
xiv List of Figures
12.3 A city’s streets form a grid, and are either east–west bound or north–south
bound. A car can move only east or north. . . . . . . . . . . . . . . . . . 170
12.4 (a) A driver cannot turn anywhere when traversing from A to B. (b) Like-
wise, a driver cannot turn anywhere when traversing from C to D. (c) There
are some turning options when traversing from E to F. At E, the driver can
go northbound first or eastbound first, as indicated by the two arrows. . . 170
12.5 The Tower of Hanoi. (a) Some disks are on pole A and the goal is to move
all the disks to pole B, as shown in (b). A larger disk can never be placed
on top of a smaller disk. A third pole, C, can be used when necessary. . . 171
12.6 MovingonediskfromAtoBrequiresonlyonestep. ............ 172
12.7 MovingtwodisksfromAtoBrequiresthreesteps.............. 172
12.8 MovingthreedisksfromAtoBrequiressevensteps. ............ 173
12.9 Count the occurrences of “1” when partitioning n. ............. 176
13.1 Computing Fibonacci numbers bottom-up without using recursion. . . . . 195
13.2 Ratio of the execution times of the recursive and the non-recursive versions
for calculating Fibonacci numbers. The recursive function is much slower
andtheratioinexecutiontimekeepsrising. ................. 196
13.3 Computing f(5) requires calling f (4) and f (3). Computing f(4) requires
calling f(3) and f(2). ............................. 197
13.4 Redraw Fig. 13.3. This looks like a “tree”: computing each value requires
thesumoftwovalues. ............................. 198
14.1 Graphical illustration of f1 calls f2. ..................... 211
14.2 Graphical illustration of f1 calls f2 and f3. ................. 211
14.3 Graphical illustration of f1 calls f2 and f3; f2 also calls f3. ....... 211
14.4 Graphical illustration of f1 calls f2 in a loop and f3 outside a loop; f2 calls
f3. ........................................ 212
14.5 Graphical illustration of partition when the initial value of left is 3. . 212
14.6 Graphical illustration of partition when the value of left is2. ..... 213
14.7 Graphical illustration of partition when the value of left is1. ..... 213
15.1 In each step, the binary search reduces the number of elements to search
across by half. In the first step, key is compared with the element at the
center. If key is smaller, then it is impossible to find key in the upper half
of the array. If key is greater than the element at the center, then it is
impossible to find key inthelowerhalfofthearray.Thearraymusthave
beensortedbeforeperformingabinarysearch. ............... 224
15.2 Determine the values of fv and count using a graphical illustration of the
calling relations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
18.1 A linked list starts empty, i.e., without any Node. This figure shows three
views: (a) the source code view, (b) a diagram, and (c) the stack memory. 295
18.2 Creating a Node object whose value is 917. Please note that head is a pointer. 295
18.3 Replacing the three lines by using List
insert. .............. 296
18.4 Calling List
insert again to insert another list node. . . . . . . . . . . . 296
18.5 Insert the third object by calling List
insert again. . . . . . . . . . . . . 297
18.6 Delete the node whose value is −504. . . . . . . . . . . . . . . . . . . . . 299
18.7 To delete a list node, first create a pointer p that points to the same memory
address as head.................................. 299
18.8 The function creates another pointer q.Itsvalueisthesameasp->next. 300
List of Figures xv
18.9 Modify p->next to bypass the node that is about to be deleted. . . . . . 300
18.10 Release the memory pointed to by q. ..................... 301
19.1 (a) The original linked list. The list’s head points to A. (b) The reversed
linked list. The list’s head points to E. .................... 314
19.2 (a) Three pointers are used. (b) Change orighead -> next and make it
point to revhead.(c)Updaterevhead to the new head of the reversed list.
(d) Update orighead to the new head of the remaining list. (e) Update
origsec to the second node of the remaining list. . . . . . . . . . . . . . 315
20.1 Anexampleofabinarysearchtree....................... 318
20.2 An empty tree has one pointer called root and its value is NULL; root is a
pointeranditisnotatreenode. ....................... 320
20.3 A binary tree with only one tree node. Both left and right are NULL.
This node is called the root because it has no parent. It is also a leaf node
becauseithasnochildren............................ 320
20.4 A binary tree with two nodes. The node with value 917 remains the root. It
is no longer a leaf node because it has one child. The node with value −504
isaleafnodebecauseithasnochildren. ................... 320
20.5 Abinarytreewiththreenodes. ........................ 321
20.6 A binary tree with five tree nodes. A new view (d) simplifies the represen-
tationofthetree. ............................... 321
20.7 Insert values 8, 4, 11, 1, 9, 7, 10, 5, 12, 15. . . . . . . . . . . . . . . . . . . 322
20.8 Threedifferentlyshapedbinarysearchtrees.................. 326
20.9 Examplesofbinarysearchtrees......................... 327
20.10 (a) The original binary search tree. (b) Deleting the node “5”. The node is
a leaf node (has no children). This is the first case. The left child of node
“7” becomes NULL. (c) Deleting the node “14”. This node has one child.
This is the second case. The parent of “14” points to the only child of “14”,
i.e., “12”. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
20.11 (a) The node “8” has two children. This is the third case. Exchange the
values of this node and its successor. The tree temporarily loses its ordering
property. (b) Deleting the node “8” restores the property of the binary
searchtree. ................................... 329
20.12 (a) There are two uniquely shaped binary trees with 2 nodes. (b) There are
fiveuniquelyshapedbinarytreeswith3nodes. ............... 333
20.13 Five different shapes for the pre-order traversals of binary search trees stor-
ing1,2,and3.(a)< 1, 2, 3 >,(b)< 1, 3, 2 >,(c)< 2, 1, 3 >,(d)< 3, 2, 1 >,
(e)
< 3, 1, 2 >................................... 334
22.1 Coordinates (row, column). The upper left corner is (0, 0). Moving right
increasesthecolumn;movingdownincreasestherow............. 360
22.2 Strategy to get out of a maze. Suppose ↑ is north and → is east. A gray
square is a brick. (a) If moving east in step 1 does not reach a dead end,
then keep moving east in step 2. (b) If the corridor has a turn, then follow
the turn and keep moving forward. (c) After encountering a dead end, turn
around (i.e., backtrack) and move back along the corridor. . . . . . . . . . 370
xvi List of Figures
22.3 Strategy at an intersection. (a) About to enter an intersection. (b) At the
intersection (marked as “2”), try to go east first. (c) It is a dead end. Turn
around and return to the previous intersection. (d) The mark “2” now
becomes “4”, indicating that it is the fourth visited cell. Since cell “3” is a
deadend,itismarkedblack. ......................... 370
22.4 (a) Since east is a dead end, try to go south. (b) Enter another intersection,
marked as “6”. (c) Go east and find that it is another dead end. (d) Turn
around to the previous intersection, now marked as “8”. (This is the eighth
move in the sequence of moves.) The dead end is replaced by black. . . . 371
22.5 (a) It is not possible to go south at this intersection. Move west and mark
the cell as “9”. (b) This is another dead end. Turn around and mark the
intersection as “10”. (c) Since both options lead to dead ends, we return to
the previous intersection. The visited cells are marked black. (d) Back at
thefirstintersection. .............................. 371
22.6 (a) Going west is an option. (b) It is another dead end. Return to the
previous intersection. (c),(d) All options at this intersection lead to dead
ends,soitshouldreturnalongthecorridor. ................. 371
22.7 Two four-way intersections at A and B. At a four-way intersection, all four
if conditionsaretrue. ............................. 374
22.8 After reaching a dead end, we should turn around and move west. At loca-
tion 2, moving east is an option again. We will get stuck here in these two
cells and need a solution to prevent this from happening. . . . . . . . . . 375
23.1 Example of metadata: the exposure time, the focal length, the time and the
date,etc. .................................... 382
23.2 (a) The RGB color space, showing the primary colors and their mixtures.
White is produced by mixing all three primary colors together. Color filters.
(b) original images. (c) red only, (d) green only, (e) blue only. . . . . . . . 392
23.3 Color filters. (a)–(c) original images. (d) red only, (e) green only, (f) blue
only. ....................................... 392
23.4 Colorinversion.(a),(c):original.(b),(d):inverted............... 393
23.5 Detecting vertical edges. (a) The original image. (b) Gray-scale image. The
detected edges use different threshold values. (c) 120. (d) 100. (e) 80. (f)
is 60. Many vertical edges are not detected when the threshold is too high.
When the threshold is too low, there are many false-positive edges (like the
sky). ....................................... 393
23.6 Equalization. (a),(b): original images. (c),(d): processed images. . . . . . . 393
23.7 Equalization. (a),(b): original images. (c),(d): processed images. . . . . . . 393
24.1 Graphicalrepresentationofthecodebook................... 396
24.2 (a) The characters are sorted by the frequencies. (b) A linked list is created.
List nodes are expressed by rectangles. Tree nodes are expressed by ovals. 401
24.3 (a) Take the tree nodes, L and R, from the first two list nodes. (b) Create
atreenodeN whose left and right children are L and R. (c) Create a new
list node pointing to the newly created tree node. The list nodes are sorted
in the ascending order by the tree nodes’ frequencies. . . . . . . . . . . . 402
24.4 Continuetheprocedure. ............................ 403
24.5 At every step, two tree nodes are removed, combined into a single tree, and
thenthenewtreeisaddedintothelist. ................... 404
24.6 Continuetheprocedureshorteningthelinkedlist............... 405
List of Figures xvii
24.7 Now the linked list has only one node. The tree has been built, and it is in
theonlyremaininglistnode........................... 406
24.8 A list of tree nodes. This figure shows the list as it is being built. The tree
is the same as the one shown in Fig. 24.4 (c). . . . . . . . . . . . . . . . . 410
24.9 Display the tree in DDD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
24.10 If there are n leaf nodes on the left side, zeros should be filled in n rows.
Thecolumnisdeterminedbythedistancefromtheroot........... 412
24.11 The expressions for the code trees are (a) 1a1b00, (b) 1a1b1c000, (c)
1a1b01c1d000, (d) 1a1b01c1d1e0000. For each tree, the number of 1s is
the same as the number of leaf nodes. The number of 0s is one plus the
numberofnon-leafnodes. ........................... 416
24.12 (a) One tree node is added after reading the first command and the first
character. (b) After reading two bytes. (c) After reading six bytes. (d) The
first bit in the seventh byte is a command and it is 0. (e) The next command
bit(thesecondbitintheseventhbyte)is1. ................. 424
24.13 (a) The next command (the second bit in the eighth byte) is 0. This will
create a common parent for the first two tree nodes. (b) The next command
(the third bit in the eighth byte) is also 0. This will create a common parent
for the first two tree nodes. (c) The next command (the fourth bit in the
eighth byte) is 1. This will create a tree node to store the value g. . . . . 425
24.14 The remaining commands are 0. Continue building the tree. . . . . . . . . 426
24.15Finishbuildingthetree. ............................ 426
B.1 Create a new repository. In this example, I call it “demorepo”. As a teacher,
I can create a free private repository. Check the box of “Initialize this repos-
itory with a README”. Add .gitignore for C. This will ignore files that
are not supposed to be in the repository. Click “Create repository”. . . . . 448
C.1 Eclipse (www.eclipse.org) is one of the most popular IDEs. . . . . . . . 451
C.2 SelectC/C++DevelopmentTools. ...................... 452
C.3 Select Makefile Project and call the project “prog1”. Click Finish. . . . . . 453
C.4 Addaheaderfile. ............................... 453
C.5 Call the header file prog1.h. Eclipse automatically adds #ifndef, #define,
and #endif to the header file. Add two function declarations to the header
file......................................... 454
C.6 Addanewsourcefile. ............................. 454
C.7 You can customize the code formatting style by clicking Windows and select-
ing Preferences. Choose a style you like. You can experiment with different
styles and decide which suits your preferences. This example uses the GNU
style........................................ 455
C.8 Set the project’s property. Depending on your version of Eclipse and the
installed plug-ins, the build environment may already be set up correctly.
Click Project (on the menubar) and select Build Project. If Eclipse says “no
rule to make target all”, then you need to set the build environment. Select
“Generate Makefiles automatically” and click Apply. . . . . . . . . . . . . 455
C.9 When you click Project and select Build Project, Eclipse will say “undefined
reference to addtwo” and “undefined reference to subtwo”. This should be
expected because these functions have not been implemented. Eclipse’s error
message is displayed in the Console. Eclipse also highlights the two lines that
havetheerrors. ................................. 456
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.