CMPT225 Final Review 1 Simon Fraser University CMPT 225

CMPT225 Final Review - MT 前

ppt2 ADT
ppt3-7 List ADT class, Stack vs Heap memory allocation
ppt9 Stack ADT class
ppt10 Queue ADT class
ppt11-12, 21, 26, 34 Searching, Sorting
ppt14-18 BST ADT class
ppt19-20 AVL ADT class
ppt21 Tree sort (见 Sorting)



ADT List Stack/ Queue BST

CDT Array, LL Array LL, List ADT class Array, LL

,ppt2
1. ADT
(1) 定义:
 Abstract Data Type/ data collection
 墙前能看: class interface in .h file - public
墙后不能看: data members in .h file - private 和 implementation of methods in .cpp file
 Linux 指令/ .h 和.cpp 文件格式/ Test driver
o description: single responsibility
o precondition: what is true before method is called
o postcondition: what is true after method is called -- ppt4
o exception:




(2) 优缺点:
优:
1. Preserve/control the integrity of a class’ data
2. Ease s/w development team work
3. Ease modification
4. Reduce complexity (from a client code’s perspective)
5. Ease reusability

缺:
1. More code to write: must have getters/setters methods
2. Limited access: user of the class (as writer of client code that makes use of the class),
may feel limited by the class’ public methods


(3) Class invariant:
 是描述 class 特征的 statement
 对于该 class 所有实例化的 objects, 这些特征不变 (True)

, ppt3-7
1. ADT vs CDT:
 ADT: data collection eg: List
 CDT: data structure eg: Array, LL


2. Data organization 分类:
 Linear: 一个 predecessor 一个 successor
 Non-linear: 没有 predecessor 和 successor
 Hierarchical: 一个 predecessor 很多 successor
 Graph: 很多 predecessor 很多 successor


3. List ADT class:
(1) List 分类:
 position-oriented: operations based on position of data
 value-oriented: operations based on value of data


(2) Operation:
1. Position-oriented:
o insert(elemt, position)
o remove(position)
o removeAll()
o elemt get(position)
o int getElemtCount
o append(elemt) 尾加
o swap(position1, position2)

2. Value-oriented:
o insert(elemt)
o remove(elemt)
o removeAll()
o elemt get(elemt)
o int getElemtCount