Tài liệu, ebook Cơ Sở Dữ Liệu

Summary In this talk, we introduced binary trees – Each node has two distinct and identifiable sub-trees – Either sub-tree may optionally be empty – The sub-trees are ordered relative to the other We looked at: – Properties – Applications

32 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 974 | Lượt tải: 2

Summary This topic covered two types of traversals: – Breadth-first traversals – Depth-first traversals – Applications – Determination of how to structure a depth-first traversal

25 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 976 | Lượt tải: 1

Summary In this topic, we have looked at one implementation of a general tree: – store the value of each node – store all the children in a linked list – not an easy (Q(1)) way to access children – if we use an array, different problems.

21 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1003 | Lượt tải: 1

Summary In this topic, we have: – Introduced the terminology used for the tree data structure – Discussed various terms which may be used to describe the properties of a tree, including: • root node, leaf node • parent node, children, and siblings • ordered trees • paths, depth, and height • ancestors, descendants, and subtrees – We looke...

42 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1118 | Lượt tải: 1

Summary We have considered the implementation of linked lists in C++ – Aspects of the Node class – Accessors and mutators – The implementation of various member functions – Stepping through a linked list – Defining the copy and assignment operator – Defining move constructors and move assignment operators – Discussed efficiencies

147 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1069 | Lượt tải: 3

Summary In this topic, we have introduced the more general deque abstract data structure – Allows insertions and deletions from both ends of the deque – Internally may be represented by either a doubly-linked list or a twoended array More important, we looked at the STL and the design pattern of an iterator

34 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1120 | Lượt tải: 1

Summary The queue is one of the most common abstract data structures Understanding how a queue works is trivial The implementation is only slightly more difficult than that of a stack Applications include: – Queuing clients in a client-server model – Breadth-first traversals of trees

49 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 978 | Lượt tải: 3

Stacks The stack is the simplest of all ADTs – Understanding how a stack works is trivial The application of a stack, however, is not in the implementation, but rather: – where possible, create a design which allows the use of a stack We looked at: – parsing, function calls, and reverse Polish

104 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1074 | Lượt tải: 2

Summary In this topic, we have introduced Abstract Lists – Explicit linear orderings – Implementable with arrays or linked lists • Each has their limitations • Introduced modifications to reduce run times down to Q(1) – Discussed memory usage and the sizeof operator – Looked at the String ADT – Looked at the vector class in the STL

28 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1150 | Lượt tải: 1

Summary In these slides we have looked at: – The run times of • Operators • Control statements • Functions • Recursive functions – We have also defined best-, worst-, and average-case scenarios We will be considering all of these each time we inspect any algorithm used in this class

98 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1053 | Lượt tải: 1