Advanced Topics in C_ Core Concepts in Data Structures [Kalicharan 2013-10-29].pdf

(4759 KB) Pobierz
For your convenience Apress has placed some of the front
matter material after the index. Please use the Bookmarks
and Contents at a Glance links to access them.
Contents at a Glance
About the Author �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½xiii
About the Technical Reviewer �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½
xv
Preface �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½
xvii
Chapter 1: Sorting, Searching, and Merging �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½1
Chapter 2: Structures �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½27
Chapter 3: Pointers �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½51
Chapter 4: Linked Lists �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½69
Chapter 5: Stacks and Queues�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½103
Chapter 6: Recursion �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½133
Chapter 7: Random Numbers, Games, and Simulation �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½159
Chapter 8: Working with Files �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½183
Chapter 9: Introduction to Binary Trees �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½213
Chapter 10: Advanced Sorting �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½241
Chapter 11: Hashing �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½265
Index �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½287
v
Chapter 1
Sorting, Searching, and Merging
In this chapter, we will explain the following:
How to sort a list of items using selection and insertion sort
How to add a new item to a sorted list so that the list remains sorted
How to sort an array of strings
How to sort related (parallel) arrays
How to search a sorted list using
binary search
How to search an array of strings
How to write a program to do a frequency count of words in a passage
How to merge two sorted lists to create one sorted list
1.1 Sorting an Array: Selection Sort
Sorting is the process by which a set of values are arranged in ascending or descending order. There are many reasons
to sort. Sometimes we sort in order to produce more readable output (for example, to produce an alphabetical listing).
A teacher may need to sort her students in order by name or by average score. If we have a large set of values and we
want to identify duplicates, we can do so by sorting; the repeated values will come together in the sorted list.
Another advantage of sorting is that some operations can be performed faster and more efficiently with sorted
data. For example, if data is sorted, it is possible to search it using binary search—this is much faster than using a
sequential search. Also, merging two separate lists of items can be done much faster than if the lists were unsorted.
There are many ways to sort. In this chapter, we will discuss two of the “simple” methods:
selection
and
insertion
sort. In Chapter 10, we will look at more sophisticated ways to sort. We start with selection sort.
Consider the following list of numbers stored in a C array,
num:
1
Chapter 1
Sorting, SearChing, and Merging
Sorting
num
in ascending order using
selection sort
proceeds as follows:
1
st
pass
Find the smallest number in the entire list, from positions
0
to
6;
the smallest is
15,
found
in position
4.
Interchange the numbers in positions
0
and
4.
This gives us the following:
2
nd
pass
Find the smallest number in positions
1
to
6;
the smallest is
33,
found in position
5.
Interchange the numbers in positions
1
and
5.
This gives us the following:
3
rd
pass
Find the smallest number in positions
2
to
6;
the smallest is
48,
found in position
5.
Interchange the numbers in positions
2
and
5.
This gives us the following:
4
th
pass
Find the smallest number in positions
3
to
6;
the smallest is
52,
found in position
6.
Interchange the numbers in positions
3
and
6.
This gives us the following:
5
th
pass
Find the smallest number in positions
4
to
6;
the smallest is
57,
found in position
4.
Interchange the numbers in positions
4
and
4.
This gives us the following:
2
Zgłoś jeśli naruszono regulamin