实例介绍
【实例简介】Algorithms and Data Structures for Games Programming.pdf
【实例截图】
【核心代码】
Contents 1 Introduction and Overview 1 1.1 Aims and Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Syllabus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.1 Continuous Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 Reading List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Array Containers 1 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2.2 An Array class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2.2.1 Major points to note in Array.h . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.2 Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 A Simple Client Program for Array . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 The Big-Three . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4.1 Defence against naive defaults . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Overloading the Stream Output Operator . . . . . . . . . . . . . . . . . . . . . . 17 2.6 std::vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.6.1 Points to note in vectort1.cpp . . . . . . . . . . . . . . . . . . . . . . . . 20 3 Analysis of Algorithms 1 3.1 O Notation (Big-oh) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3.2 Estimating the Growth Rate of an Algorithm . . . . . . . . . . . . . . . . . . . . 3 3.2.1 Simple Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.2.2 Decision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.2.3 Counting Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 Sorting and Searching 1 4.1 Bubble-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 4.1.1 Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 4.2 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4.2.1 Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4.3 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4.3.1 Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 4.4 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.4.1 Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.5 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.5.1 Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.5.2 Standard Library Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.6 Comparison: Bubble, Selection, Insertion and Merge and Quick Sorts . . . . . . . 9 0–1 4.7 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.7.1 Sequential Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.7.2 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.7.3 Logarithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.7.4 Is Binary Search Really Faster than Linear? . . . . . . . . . . . . . . . . . 12 5 Linked Lists 1 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 5.2 A Singly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 5.2.1 Class Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 5.2.2 Dissection of List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5.2.3 Class Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5.3 A simple List client program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.4 Doubly Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.4.1 Brief Discussion of the Doubly Linked List . . . . . . . . . . . . . . . . . 19 5.4.2 Simple Test Program, ListT1.cpp . . . . . . . . . . . . . . . . . . . . . . 20 5.4.3 Doubly Linked List Implementation . . . . . . . . . . . . . . . . . . . . . 24 5.5 Arrays versus Linked List, Memory Usage . . . . . . . . . . . . . . . . . . . . . . 31 5.6 Arrays versus Linked List, Cache issues . . . . . . . . . . . . . . . . . . . . . . . . 31 6 Stacks and Queues 1 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 6.2 Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 6.2.1 Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 6.2.2 A simple client program . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6.3 Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6.3.1 Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6.3.2 A simple client program . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 6.4 Stack Application — RPN Calculator . . . . . . . . . . . . . . . . . . . . . . . . 10 6.4.1 RPN Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 6.4.2 Conversion from Infix to Postfix . . . . . . . . . . . . . . . . . . . . . . . 14 6.5 Stack Application — Balancing Brackets . . . . . . . . . . . . . . . . . . . . . . 16 6.6 Appendix. Illustration of Dijkstra’s Shunting Algorithm . . . . . . . . . . . . . . . 18 7 Trees 1 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 7.2 Binary Search Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 7.2.1 Binary Search Tree Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 7.2.2 Notes on BST.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 7.2.3 Traversal of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 7.2.4 Exercising Program, BSTT1.cpp . . . . . . . . . . . . . . . . . . . . . . . 9 7.3 n-ary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 8 Recursion 1 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 8.2 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 8.2.1 Deduction versus Induction . . . . . . . . . . . . . . . . . . . . . . . . . . 3 8.3 Recursive Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 8.4 Recursion in Compilers and Calculators . . . . . . . . . . . . . . . . . . . . . . . 8 8.4.1 Prefix, infix, postfix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 0–2 8.5 Proving Termination of Recursive and Other Non-deterministic Algorithms . . . . 9 8.6 Divide-and-Conquer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 8.6.1 Maximum of an Array using Divide and Conquer . . . . . . . . . . . . . . 10 8.6.2 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 8.6.3 Towers of Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 8.6.4 Drawing a Ruler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 8.7 Trees and Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 8.7.1 Recursive drawing of a ruler . . . . . . . . . . . . . . . . . . . . . . . . . 21 8.7.2 Recursive maximum of an array . . . . . . . . . . . . . . . . . . . . . . . 21 8.7.3 Recursive evaluation of a prefix expression . . . . . . . . . . . . . . . . . . 23 8.8 Elimination of Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 9 Trees Miscellany 1 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 9.2 n-ary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 9.3 Game Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 9.3.1 Nim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 9.3.2 Minimax Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 9.3.3 Recursive Minimax Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 7 9.3.4 Minimax Applied to Tic-tac-toe . . . . . . . . . . . . . . . . . . . . . . . 8 10 Simple Pathfinding 1 10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 10.2 Deque Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 10.2.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 10.2.2 Discussion of sDeque.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 10.3 Path-finding in a Maze — Depth-first and Breadth-first Searching . . . . . . . . . 4 10.3.1 Maze implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 10.3.2 Depth-first pathfinding solution . . . . . . . . . . . . . . . . . . . . . . . 8 10.3.3 Backtracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 10.3.4 Absolute dead end . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 10.3.5 Breadth-first pathfinding solution . . . . . . . . . . . . . . . . . . . . . . 13 10.4 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 11 Graphs 1 11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 11.2 Examples of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 11.2.1 General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 11.2.2 Games and Path-finding . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 11.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 11.4 Graph Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 11.4.1 Depth-first Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 11.4.2 Breadth-first Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 11.5 Software Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 11.5.1 Basics of Graph.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 11.5.2 Depth-first Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 11.5.3 Use of Stack for Depth-first? . . . . . . . . . . . . . . . . . . . . . . . . 11 11.5.4 Animated Display of the Traversal . . . . . . . . . . . . . . . . . . . . . . 12 11.5.5 Breadth-first Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 0–3 11.5.6 Depth-first and Breadth-first, a Summary . . . . . . . . . . . . . . . . . . 14 12 Pathfinding 1 12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 12.2 Pathfinding as a graph search problem . . . . . . . . . . . . . . . . . . . . . . . . 1 12.3 Graph search — informed or uninformed? . . . . . . . . . . . . . . . . . . . . . . 4 12.4 Graph search pathfinding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 12.4.1 Uninformed graph search . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 12.4.2 Breadth-first pathfinding — basic algorithm . . . . . . . . . . . . . . . . . 4 12.4.3 Informed graph search — add a heuristic . . . . . . . . . . . . . . . . . . 6 12.4.4 Depth-first pathfinding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 12.5 Practical examples of graph-search algorithms . . . . . . . . . . . . . . . . . . . . 8 12.5.1 Silly Breadth-first . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 12.5.2 Breadth-first . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 12.5.3 Distance-first . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 12.5.4 ’Simple’ Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 12.5.5 Distance Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 12.5.6 AStar Heuristic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 12.6 Algorithms Applied to a Maze problem . . . . . . . . . . . . . . . . . . . . . . . . 17 12.7 Performance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 12.7.1 Performance Measures for Breadth first . . . . . . . . . . . . . . . . . . . 19 12.7.2 Performance Measures for Depth first . . . . . . . . . . . . . . . . . . . . 21 12.8 Pathfinding in non-tile-based environments . . . . . . . . . . . . . . . . . . . . . . 21 12.9 Software Implementations of the Algorithms . . . . . . . . . . . . . . . . . . . . . 22 13 Sets and Maps 1 13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 13.2 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 13.3 Bitvector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 13.4 Hashing and Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 13.5 Example Use of set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 13.6 Sets need to be able to order elements . . . . . . . . . . . . . . . . . . . . . . . . 5 13.7 Example Use of multiset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 13.8 A Name class whose objects we want to insert in set . . . . . . . . . . . . . . . . 8 13.9 Set of Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 13.10A Telephone Directory using a map . . . . . . . . . . . . . . . . . . . . . . . . . 13 13.11A Telephone Directory using a multimap . . . . . . . . . . . . . . . . . . . . . . . 16
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论