没有合适的资源?快使用搜索试试~ 我知道了~
首页《A Practical Introduction to Data Structures and Algorithm Analysis》
《A Practical Introduction to Data Structures and Algorithm Analy...
需积分: 10 14 下载量 81 浏览量
更新于2023-03-16
评论
收藏 2.46MB PDF 举报
《A Practical Introduction to Data Structures and Algorithm Analysis》
资源详情
资源评论
资源推荐
A Practical Introduction to
Data Structures and Algorithm
Analysis
Edition 3.2 (C++ Version)
Clifford A. Shaffer
Department of Computer Science
Virginia Tech
Blacksburg, VA 24061
May 20, 2011
Copyright © 2009-2011 by Clifford A. Shaffer.
This document is made freely available for educational and other
non-commercial use.
You may make copies of this file and redistribute it without charge.
You may extract portions of this document provided that the front page,
including the title, author, and this notice are included.
Any commercial use of this document requires the written consent of the
author.
The author can be reached at shaffer@cs.vt.edu.
Further information about this text is available at
http://people.cs.vt.edu/
˜
shaffer/Book/
Contents
Preface xiii
I Preliminaries 1
1 Data Structures and Algorithms 3
1.1 A Philosophy of Data Structures 4
1.1.1 The Need for Data Structures 4
1.1.2 Costs and Benefits 6
1.2 Abstract Data Types and Data Structures 8
1.3 Design Patterns 12
1.3.1 Flyweight 13
1.3.2 Visitor 13
1.3.3 Composite 14
1.3.4 Strategy 15
1.4 Problems, Algorithms, and Programs 16
1.5 Further Reading 18
1.6 Exercises 20
2 Mathematical Preliminaries 25
2.1 Sets and Relations 25
2.2 Miscellaneous Notation 29
2.3 Logarithms 31
2.4 Summations and Recurrences 32
2.5 Recursion 36
2.6 Mathematical Proof Techniques 38
iii
iv Contents
2.6.1 Direct Proof 39
2.6.2 Proof by Contradiction 39
2.6.3 Proof by Mathematical Induction 40
2.7 Estimation 46
2.8 Further Reading 47
2.9 Exercises 48
3 Algorithm Analysis 55
3.1 Introduction 55
3.2 Best, Worst, and Average Cases 61
3.3 A Faster Computer, or a Faster Algorithm? 62
3.4 Asymptotic Analysis 65
3.4.1 Upper Bounds 65
3.4.2 Lower Bounds 67
3.4.3 Θ Notation 68
3.4.4 Simplifying Rules 69
3.4.5 Classifying Functions 70
3.5 Calculating the Running Time for a Program 71
3.6 Analyzing Problems 76
3.7 Common Misunderstandings 77
3.8 Multiple Parameters 79
3.9 Space Bounds 80
3.10 Speeding Up Your Programs 82
3.11 Empirical Analysis 85
3.12 Further Reading 86
3.13 Exercises 86
3.14 Projects 90
II Fundamental Data Structures 93
4 Lists, Stacks, and Queues 95
4.1 Lists 96
4.1.1 Array-Based List Implementation 100
4.1.2 Linked Lists 103
4.1.3 Comparison of List Implementations 112
Contents v
4.1.4 Element Implementations 114
4.1.5 Doubly Linked Lists 115
4.2 Stacks 120
4.2.1 Array-Based Stacks 121
4.2.2 Linked Stacks 124
4.2.3 Comparison of Array-Based and Linked Stacks 125
4.2.4 Implementing Recursion 125
4.3 Queues 129
4.3.1 Array-Based Queues 129
4.3.2 Linked Queues 134
4.3.3 Comparison of Array-Based and Linked Queues 134
4.4 Dictionaries 134
4.5 Further Reading 145
4.6 Exercises 145
4.7 Projects 149
5 Binary Trees 151
5.1 Definitions and Properties 151
5.1.1 The Full Binary Tree Theorem 153
5.1.2 A Binary Tree Node ADT 155
5.2 Binary Tree Traversals 155
5.3 Binary Tree Node Implementations 160
5.3.1 Pointer-Based Node Implementations 160
5.3.2 Space Requirements 166
5.3.3 Array Implementation for Complete Binary Trees 168
5.4 Binary Search Trees 168
5.5 Heaps and Priority Queues 178
5.6 Huffman Coding Trees 185
5.6.1 Building Huffman Coding Trees 186
5.6.2 Assigning and Using Huffman Codes 192
5.6.3 Search in Huffman Trees 195
5.7 Further Reading 196
5.8 Exercises 196
5.9 Projects 200
6 Non-Binary Trees 203
vi Contents
6.1 General Tree Definitions and Terminology 203
6.1.1 An ADT for General Tree Nodes 204
6.1.2 General Tree Traversals 205
6.2 The Parent Pointer Implementation 207
6.3 General Tree Implementations 213
6.3.1 List of Children 214
6.3.2 The Left-Child/Right-Sibling Implementation 215
6.3.3 Dynamic Node Implementations 215
6.3.4 Dynamic “Left-Child/Right-Sibling” Implementation 218
6.4 K-ary Trees 218
6.5 Sequential Tree Implementations 219
6.6 Further Reading 223
6.7 Exercises 223
6.8 Projects 226
III Sorting and Searching 229
7 Internal Sorting 231
7.1 Sorting Terminology and Notation 232
7.2 Three Θ(n
2
) Sorting Algorithms 233
7.2.1 Insertion Sort 233
7.2.2 Bubble Sort 235
7.2.3 Selection Sort 237
7.2.4 The Cost of Exchange Sorting 238
7.3 Shellsort 239
7.4 Mergesort 241
7.5 Quicksort 244
7.6 Heapsort 251
7.7 Binsort and Radix Sort 252
7.8 An Empirical Comparison of Sorting Algorithms 259
7.9 Lower Bounds for Sorting 261
7.10 Further Reading 265
7.11 Exercises 265
7.12 Projects 269
剩余612页未读,继续阅读
rtoax
- 粉丝: 2611
- 资源: 217
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 数据结构1800题含完整答案详解.doc
- 医疗企业薪酬系统设计与管理方案.pptx
- 界面与表面技术界面理论与表面技术要点PPT学习教案.pptx
- Java集合排序及java集合类详解(Collection、List、Map、Set)讲解.pdf
- 网页浏览器的开发 (2).pdf
- 路由器原理与设计讲稿6-交换网络.pptx
- 火电厂锅炉过热汽温控制系统设计.doc
- 企业识别CIS系统手册[收集].pdf
- 物业管理基础知识.pptx
- 第4章财务预测.pptx
- 《集成电路工艺设计及器件特性分析》——实验教学计算机仿真系.pptx
- 局域网内共享文件提示没有访问权限的问题借鉴.pdf
- 第5章网络营销策略.pptx
- 固井质量测井原理PPT教案.pptx
- 毕业实习总结6篇.doc
- UGNX建模基础篇草图模块PPT学习教案.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0