data structure and algorithm analysis in C - weiss

【实例简介】
data structure and algorithm analysis in C - weiss
Structures, Algorithm Analysis: PREFACE 页码,2/4 only a few keystrokes and no increased speed. i believe that this book demonstrates that unreadable code can be avoided by exercising reasonable care Overview Chapter 1 contains review material on discrete math and recursion. i believe the only way to be comfortable with recursion is to see good uses over and over. Therefore, recursion is prevalent in this text, with examples in every chapter except Chapter 5 Chapter 2 deals with algorithim analysis. This chapter explains asymptotic analysis and its major weaknesses. Many examples are provided, including an in- depth explanation of logarithmic running time. Simple recursive programs are analyzed by intuitively converting them into iterative programs. More complicated divide-and-conquer programs are introduced, but some of the analysis (solvin recurrence relations) is implicitly delayed until Chapter 7, where it is performed in detail Chapter 3 covers lists, stacks, and queues. The emphas is here is on coding these data structures using fast implementation of these data structures, and an exposition of some of their uses. There are almost no programs (just routines), but the exercises contain plenty of ideas for programming assignments Chapter 4 covers trees, with an emphasis on search trees, including e Vernal search trees (B-trees). The file system and expression trees are used as examples. trees and splay trees are introduced but not analyzed. Seventy five percent of the code is written, leaving similar cases to be completed by the student. Additional coverage of trees, such as file compression and game trees is deferred until Chapter 10. Data structures for an external medium are considered as the final topic in several chapters Chapter 5 is a relatively short chapter concerning hash tables. Some analysis is performed and extendible hashing is covered at the end of the chapter Chapter 6 is about priority queues. Binary heaps are covered, and there is additional material on some of the theoretically interesting implementations of priority queues. Chapter 7 covers sorting. It is very specific with respect to coding details and analysis. All the important general-purpose sorting algorithms are covered and compared. Three algorithms are analyzed in detail insertion sort, Shellsort, and quicksort. External sorting is covered at the end of the chapter. Chapter 8 discusses the disjoint set algorithm with proof of the running time This is a short and specific chapter that can be skipped if Kruskal' s algorithm is not discussed Chapter 9 covers graph algorithms. Algorithms on graphs are interesting not only because they frequently occur in practice but also because their running time is so heavily dependent on the proper use of data structures. Virtually all of the standard algorithms are presented along with appropriale dala structures, pseudocode, and analysis of running time To place these problems in a proper mk: @MSITStore: K: \Data Structures and Algorithm Analysis. in C. chm:: /. 2006-1-27 Structures, Algorithm Analysis: PREFACE 页码,3/4 context, a short discussion on complexity theory (including Np-completeness and undecidability) is provided. Chapter 10 covers algori thm design by examining common problem-solving techniques. This chapter is heavily fortified with examples. Pseudocode is used in these later chapters so that the student s appreciation of an example algorithm is not obscured by implementalion details. apter ll deals with amortized analysis. Three data structures from Chapters 4 and 6 and the Fibonacci heap, introduced in this chapter are analyzed Chaplers 1-9 provide enough material for most one-semester dald structures courses. If time permits, then Chapter 10 can be covered. a graduate course on algorithm analysis could cover Chapters 7-11. The advanced data structures analyzed in Chapter 11 can easily be referred to in the earlier chapters. The course. Garey and Johnson,s book on NP-completeness can be used to augment thi. a discussion of NP-completeness in Chapter 9 is far too brief to be used in such text Exercises Exercises, provided at the end of each chapter, match the order in which material is presented. The last exercises may address the chapter as a whole rather than a specific section Difficult exercises are marked with an asterisk, and more challenging exercises have two asterisks a solutions manual containing solutions to almost all the exercises is available separalely [rol The Benjamin/ Cummings Publishing Compan References References are placed at the end of each chapter. Generally the references either are historical, represent ing the original source of the material, or they represent extensions and improvements to the results given in the text. Some references represent solutions to exercises Acknowledgments I would like to thank the many people who he lped me in the preparation of this and previous versions of the book. The professionals at Benjamin/ Cummings made ly book a considerably less harrowing experience than i had been led to expect. i' d like to thank my previous editors, Alan Apt and John Thompson, as well as carter Shanklin, who has edited this version, and Carter s assistant, Vivian McDougal for answering all my questions and putting up with my delays. Gail Carrigan at Benjamin/ Cummings and Melissa g. Madsen and Laura Snyder at publication Services did a wonderful job with production. The C version was handled by Joe Heathward ind his outstanding staff, who were able to meet the production schedule despite the delays caused by hurricane Andrew. I would like to thank the reviewers, who provided valuable comments, many of mk: @MSITStore: K: \Data Structures and Algorithm Analysis. in C. chm:: /. 2006-1-27 Structures, Algorithm Analysis: PREFACE 页码,4/4 which have been incorporated into the text. Alphabetically, they are vicki allan (Utah State University), Henry Bauer (University of Wyoming), Alex Biliris (Boston University), Jan Carroll (University of North Texas), Dan Hirschberg (University of California, Irvine), Julia Hodges (Mississippi State University) Bill kraynek (florida International University), Rayno d. Niemi (rochester Institule of Technology), Robert 0. Pettus (University of SouTh Carolina),Robert Probasco(University of Idaho), Charles Williams (Georgia State University),and Chris Wilson(University of Oregon). I would particularly like to thank Vicki Allan, who carefully read every draft and provided very detailed suggestions for improvement At Fiu, many people helped with this project. Xinwei Cui and John Tso provided me with their class notes. I' d like to thank bill kraynek, Wes mackey, Jai Navlakha and Wei Sun for using drafts in their courses, and the many students who suffered through the sketchy early drafts. Maria fiorenza, Eduardo gonzalez, Ancin Peter Tim Riley, Jefre riser, and Magaly sotolongo reported several errors, and Mike Hall checked through an early draft for programming errors. A special thanks goes lo Yuzheng Ding, who cOmpiled and tested every program in the original book, including the conversion of pseudocode to Pascal. I' d be remiss to forget Carlos Ibarra and Steve luis, who kept the printers and the computer system working and sent out tapes on a minute s notice This book is a product of a love for data structures and algori thms that can be obtained only from top educators. I d like to take the time to thank bob Hopkins E. C. Horvath, and Rich Mendez, who taught me at Cooper Union, and Bob Sedgewick Ken Steiglitz, and Bob Tarjan from Princeton. Finally, i d like to thank all my friends who provided encouragement during the project. In particular, I' d like to thank Michele dorchak, Arvin Park, and Tim Snyder for listening to my stories; Bill Kraynek, Alex Pelin, and Norman Pestaina for being civil next-door (office) neighbors, even when I wasn't: Lynn and Toby Berk for shelter during andrew, and the htMc for work relief Any mistakes in this book are, of course, my own. I would appreciate reports of any errors you find: my e-mail address is weissofiu edu M.A." Miami. florida September 1992 Go to Chapter 1 Return to Table of Contents mk: @MSITStore: K: \Data Structures and Algorithm Analysis. in C. chm:: /. 2006-1-27 Structures, Algorithm Analysis: CHAPTER 1: INTRODUCTIO 页码,1/14 CHAPTER 1: E Previous Chapter E Return to Table of Contents E Next chapter INTRODUCTION In this chapter, we discuss the aims and goals of this text and briefly review programming concepts and discrete mathematics. We wil See that how a program performs for reasonably large input is just as important as its performance on moderate amounts of input Review good programming style Summarize the basic mathematical background needed for the rest of the book Briefly review recursion 1.1. What s the book about? Suppose you have a group of n numbers and would like to determine the kth largest. This is known as the selection problem. Most students who have had a programming course or two would have no difficulty writing a program to solve this problem. There are quite a few obvious" solutions One way to solve this problem would be to read the n numbers into an array, sort the array in decreasing order by some simple algorithm such as bubblesort, and then return the element in position k. A somewhat better algorithm might be to read the first k elements into an array and sort them (in decreasing order). Next, each remaining element is read one by one. As a new element arrives, it is ignored if it is smaller than the hth clement in the array. Otherwise, it is placed in its correct spot in the array bumping one element out of the array. When the algorithm ends, the elenment in the kth position is returned as the answer Both algorithms are simple to code, and you are encouraged to do so. The natural questions, then, are which algorithm is better and, more importantly, is either algorithm good enough? A simulation using a random file of l million elements and time--each re quires several days of computer processing to terminate (alber of k= 500, 000 will show that neither algorithm finishes in a reasonable amount eventually with a correct answer). An alternative method, discussed in Chapter 7, gives a solution in about a second. Thus, although our proposed algorithms work, they cannot be considered good algorithms, because they are entirely impractical for input sizes that a third algorithm can handle in a reasonable amount of time A second problem is to solve a popular word puzzle. The input consists of a two- dimensional array of letters and a list of words. The object is to find the words in the puzzle. These words may be horizontal, vertical, or diagonal in any mk: @MSITStore: K: \Data Structures and Algorithm Analysis. in C. chm:: /. 2006-1-27 tructures, algorithm Analysis: ChaPter 1: INTRODUCTION 页码,2/14 direction. As an example, the puzzle shown in Figure 1. 1 contains the words this, two, fat, and that. The word this begins at row 1, column 1(1, 1) and extends to (1, 4); two goes from (1, 1)to(3, 1); fat goes from (4, 1) to (2, 3); and that goes from (4, 4) to (1, 1) Again, there are at least two straightforward algorithms that solve the problem For each word in the word list, we check each ordered triple (row, column orientation) for the presence of the word. This amounts to lots of nested for loops but i s basically straightforward AlternaTively, for each ordered quadruple (row, column, orientalion, number ol characters) that doesnt run off an end of the puzzle, we can test whether the word indicated is in the word list. Again, this amounts to lots of nested for loops. It is possible to save some time if the maximum number of characters in any word is known It is relatively easy to code up either solution and solve many of the real-life puzzles commonly published in magazines. These typically have 16 rows, 16 columns, and 40 or so words. Suppose, however, we consider the variation where only the puzzle board is given and the word list is essentially an english dictionary. Both of the solutions proposed require considerable time to solve this problem and therefore are not acceptable. However, it is possible, even with a large word list, to solve the problen in a maller of seconds. An important concept is that, in many problems, writing a working program is not good enough. If the program is to he run on a large data set, then the running time becomes an issue. Throughout this book we will see how to estimate the running time of a program for large inputs and, more importantly, how to compare the running times of two programs without actually coding them. We will see techniques for drastically improving the speed of a program and for determining programm bottlenecks. These techniques will enable us to find the section of the code on which to concentrate our optimization efforts. 1234 a t h 4 f g d t Figure 1. 1 Sample word puzzle 1.2. Mathematics review This section lists some of the basic formulas you need to memorize or be able to derive and reviews basic proof techniques mk: @MSITStore: K: \Data Structures and Algorithm Analysis. in C. chm:: /. 2006-1-27 Structures, Algorithm Analysis: CHAPTER 1: INTRODUCTIO 页码,3/14 1. 1. Exponents b 2n+2n=2hn+1 1.2.2. Logari thms In computer science, all logarithms are to base 2 unless specified otherwise DEFINITION: x-b if and only if log. b-d Several convenient equalities follow from this definition. THEOREM 1.1 log, b= loge a PROOF Let x=log b nd b. Then, by the definition of logarithms, c= b, C a, and a'=b. Combining theso thrcc qualities yiclds (c-c=b. Thcrcforc, x-yz, which implies 2= x/y, proving the theorem. THEOREM 1.2 log ab=10g PROOF Let. x= log a, y=log b, 2= log ab. Then, assuming the default base of 2, a,2=b,22 ab. Combining thc last thrcc cqualitics yiclds 2 2J=22=ab. Thcrcforc, x-y=z, which proves the theorem Some other useful formulas, which can ali be derived in a similar manner follow Icg 8/ b= log a- log b mk: @MSITStore: K: \Data Structures and Algorithm Analysis. in C. chm:: /. 2006-1-27 Structures, Algorithm Analysis: CHAPTER 1: INTRODUCTIO 页码,4/14 lcg(a=b log a lcg x< x for all x>0 1,1ogl,024=10, 1.2.3. Series The easiest formulas to remember are =0 and the companion M+1 In the latter formula. it0< a< 1. then and as n tends to the sum approaches 1/(1-a). These are the geometric series"formulas We can derive the last formula for i=04/0<a<1) n the following manner. Let s be the Then Then 2S=a++ If we subtract these two equations (which is permissible only for a convergent series), virtually II the terms on the right side cancel, leaving thich implies that 1 Ve can use this same technique to compute 2j= i, 21 a sum that occurs frequently. We write 2345 mk: @MSITStore: K: \Data Structures and Algorithm Analysis. in C. chm:: /. 2006-1-27 Structures, Algorithm Analysis: CHAPTER 1: INTRODUCTIO 页码,5/14 and multiply by 2, obtaining 2s=1+ 十 Subtracting these two equations yields 11111 2 Another type of common series in analysis is the arithmetic series. Any such series can be evaluated from the basic formula N(N+1 For instance, to find the sum 2+5+8+ +(3k- 1), rewrite it as 3(1+2+3+ k (1+1+1+.+1), which is clearly 3k(k+ 1)/2-k. Another way to remember this is to add the first and last terms (total 3k+1), the second and next to last terms (total 3k+1), and so on. Since there are k/2 of these pairs, the total sum is k(3k+ 1)/2, which is the same answer as before The next two formulas pop up now and then but are fairly infrequent 2N(N+1(2N+1)N M k+1 k≠=1 + When k=-1, the latter formula is not valid. We then need the following formula, which is used far more in computer science than in other mathematical disciplines. The numbers 从 are known as the harmonic numbers, and the sum is known as a harmonic sum. The crror in the following appr ation tends to y 0.57721566. which is known as Euler' s constant log N These two formulas are just general algebraic manipulations mk: @MSITStore: K: \Data Structures and Algorithm Analysis. in C. chm:: /. 2006-1-27 【实例截图】
【核心代码】