CMPS 12B Final 复习提纲
第六讲 指针和动态分配（Pointers & Dynamic Allocation）
第八讲 算法复杂度（Big O Notation & Algorithm Efficiency）
第九讲 基础排序算法分析（Sorting Algorithms）
*第十二讲 优先队列和堆（Priority Queue & Heap）
递归是一种迭代的算法，核心是自己调用自己，把一个大的问题分解成若干个相同的小的问题。
递归要求有一个基态(Base Case)，一个递归完成的标志，就如同迷宫有个出口一般。
最基础的例子参见http://jcarlson.is-programmer.com/posts/209486.html 最下面的Recursion部分。这一块其实不需要细讲。
http://jcarlson.is-programmer.com/posts/211435.html 也是一个不错的例题，虽然是python写的，主要是掌握核心思想。
一般的递归函数的格式是：
<static> <return type> name (<parameters>) {
if (base case) {
//statements
return;
}
//statements & call recursion function
}
在模拟的时候，可以使用栈来模拟递归的操作。每一次递归相当于把一个新的状态压入栈。
第二讲 抽象数据类型（ADT，Abstract Data Types）
抽象数据类型是一种概念，并非一种特殊的数据结构。数据结构是实现抽象数据类型的。
一般来说，抽象数据类型包括一个模型（A collection of data）和对在模型上的若干种操作（A set of operations on the data）。
我个人的理解就是一个架构，跟头文件比较类似，用户只能知道这些操作，并且可以调用这些操作，至于这些操作到底是怎么实现的，用户并不需要关心。且，用户不能直接访问架构里的数据，只能通过操作访问。
这里引申出一个Java的封装性（Encapsulation）问题。封装性也是面向对象程序设计（OOP）的一大特性。
封装性可以简单理解为“黑盒子”：一组数据，一些按钮，用户知道按钮的功能，可以通过按钮操作数据，但不知道这些按钮是如何实现的。对于用户而言，只需要知道前置条件和结果就行了，并不需要在意它的过程，这就是封装。
Java里封装性的体现是作用域，主要是class内的各个属性和各个方法的可使用范围，通常分为public, protected, private三种，少数情况或者是程序员相当的懒，会不写作用域，也就是default。
public即为最公开的一种，从任何地方都能够访问的了。一般class的各个方法的属性都会设置为public，因为需要从外部调用。当然这也只是一般情况。
protected相对于public较为严格，访问的条件是class内部以及其子类，以及和该class属于同一个包的其他class。
(default)相对于protected更为严格一点，访问条件仅限于class和同包的class，即其子类是不能够使用的。
private最为严格，仅能从本class中使用。
除此以外，OOP的另两大特性分别是继承性（Inheritance）和多态性（Polymorphism）。可以在那个AP复习里面找到。
ADT的一些例子：GUI Button，班级座位表，图形，复数等。
虽然被翻译为顺序表，和表（Table）是两回事。
顺序表是一个一维的线性表，但跟数组是不同的两样东西。具体而言，顺序表是一个抽象数据类型，而数组是用于保存一系列数据的具体数据结构。我们可以通过数组来实现顺序表。
顺序表有序存储一系列数据，每一个数据都有前驱（predecessor）和后继（successor），位于顺序表头的数据没有前驱，尾的数据没有后继。
顺序表的操作通常有：
create()，isEmpty()，size()，add(item, pos)，remove(pos)，removeAll()，get(pos)，displayList()，replace(item, pos)等
构造新顺序表时的语句 alist = new List;
在有了普通的List以后，我们可以在List的基础上构造一个新的ADT，比如SortedList，它继承List的所有特性，同时有自己的新特性（Sorted）。这是OOP继承性的一个体现。
在构造并实现一个ADT，形成这样一个数据结构后，我们可以使用一些操作去验证这些方法是否正确的实现了。
举例，(aList.add(item, i)).remove(i) = aList，aList.create().size()=0等。这些叫做公理（Axioms）。
我怎么觉得讲链表之前应该先上第六章的指针和动态分配内容来着……
算了。
链表也是一个线性表，但是不是顺序存储数据。链表由表头和若干个节点组成，每一个节点里有一个指针存储下一个节点的地址（就是个指针）。相较数组最大的不同点在于链表是动态分配地址，可以灵活利用内存。简单的理解的话可以认为是没有规定长度。
节点（Node）通常包括两部分，一个是Object item，一个是Node next指向下一个节点。双向链表还具有Node prev。
表头（Head）最开始为null，之后指向第一个节点。如果head为null表示空链表。
插入操作：
（假设newNode要插入在prev和curr之间）prev.next = newNode; newNode.next = curr;
（插入在表头）newNode.next = head; head = newNode;
遍历操作：
for (curr = head; curr != null; curr = curr.next); //没有循环体
删除操作：
（删除中间节点curr） prev.next = curr.next;
（删除表头） head = head.next;
废弃表：head = null;
查找需要的点（prev&&curr）循环：
for ( prev=null, curr=head; (curr != null) && (<CONDITION>); prev = curr, curr = curr.next); //同样的没有循环体
ADT链表相关：
默认构造函数：初始化numItems（存储链表量），head（存储表头）
操作：isEmpty()，size()，add(<index>,item)，remove(index)，get(index)，removeAll()，private find(index)
Node find(index) { Node curr = head; for (int skip = 0; skip<index; skip++) curr = curr.getNext(); return curr; }
Object get(index) { if (index>=0 && index< numItems) Node curr = find(index); return curr.getItem(); }
链表变种：
Sorted Linked List：按顺序进行插入，保持链表为顺序状态。
Tail References：含有尾指针，便于在末尾插入。
Circular Linked List：循环链表，“末尾”节点指向头节点（head所指向的节点）
Dummy Head Nodes：伪表头节点，让Head指向，以防止prev值为null的情况，解决head的特判问题
Double Linked List：双向链表，每一个节点都有前驱和后继，一个节点两个指针
栈是一个后进先出（LIFO）的数据结构。递归的时候也讲过对于每一层递归我们是把当前的状态压入栈进行模拟的。
举个例子吧，我们把10个棋子叠起来，首先放的是最下面的1号棋子，然后再叠到10号。不考虑弹射出去之类的情况，我们要取走8号棋子，必须要先把10号棋子拿下来，然后是9号棋子，之后才能取走8号。
新元素压入栈时位于栈顶。弹出操作总是弹出栈顶的那个元素。
ADT栈的相关操作：
createStack()，isEmpty()，push(item) *入栈，pop() *出栈，popAll()，peek()
例题：括号匹配
好像……没了？真的没什么要讲的.jpg
第六讲 指针和动态分配（Pointers & Dynamic Allocation）
（鸽了 考完回头再补 毕竟不算重点）
队列是一个先进先出（FIFO）的数据结构。
新元素入队列位于队尾。出队列操作总是出队头的元素。
实际应用的话就和排队差不多吧，新来的人都排在队尾，先处理的人就从队头出去。
ADT队列的相关操作：
createQueue()，isEmpty()，enqueue(item) *入队，dequeue() *出队，dequeueAll()，peek()
例题给的是判断回文串（这破东西要队列做？）
ADT队列的链表实现：
为了增加到队尾一般会使用双指针链表，但是也可以节省使用单尾指针循环链表。
ADT队列的数组实现：
一般会使用循环数组。但是队列大小是个问题，时刻注意队列内的元素数量。
第八讲 算法复杂度（Big O Notation & Algorithm Efficiency）
算法复杂度包括两部分，一个是时间复杂度，一个是空间复杂度，体现一个算法的效率。12B内容里只考虑时间复杂度。
一个算法的执行时间是跟它所做的操作数量，或者叫时间频度T(n)相关的。
把时间频度T(n)去掉常数项，换句话讲是增长率分离出来，称为f(n)。用O(f(n))描述一个算法的时间复杂度。
常见的复杂度包括O(1)，O(logN)【此处log以2为底，下同】，O(N)，O(NlogN)，O(N^2)，O(N^K)，O(2^N)，O(K^N)等等
以搜索举例，顺序搜索的平均效率是O(N)，对排序后的数组进行二分查找的平均效率是O(logN)。
（懒了 后面再补具体内容）
第九讲 基础排序算法分析（Sorting Algorithms）
其中三个在AP那篇文章里讲过了就不多讲了。
选择排序，冒泡排序和插入排序的平均复杂度是O(N^2)。
归并排序使用分治的方法，首先对各个元素进行拆分操作，拆成独立元素后再进行合并，在合并过程中排好序。
算法的平均复杂度是O(NlogN)。
快速排序同样是一个以分治为核心思想的排序算法，首先确定一个“中点”（Pivot），将比中点大的元素全部移到中点右侧，小的元素移到中点左侧。然后对这两块分别再次进行快速排序。
算法的平均复杂度是O(NlogN)。
基数排序俗称桶排序，将所有元素当作字符串进行处理。每一次处理最末位的字符，按照顺序将元素分配到若干个桶中，之后再一起拿出来处理前一位的字符。
算法的平均复杂度是O(Nw)，w表示字长。
表（Table）是一个“Key-Value”的数据结构，一个键对应一个值，根据键去访问值。相当于键取代了数组“下标”的地位，成了值的标识物。
哈希表（Hash Table）是一个查询期望为O(1)的表。通过哈希函数计算出一个查询的哈希值（键），根据哈希值去找对应的值。
如果哈希函数不好造成了冲突（Collision），可以使用两个不同的哈希函数去计算哈希值。
（哇哇哇没时间了等会再写）
树是一种数据结构，可以视作一个N个节点的集合，有如下特征：
1、有一个根节点（Root）
2、除了根节点以外剩余的节点形成若干个新的集合，每一个集合也是一棵树，叫做根节点的子树。
二叉树是树的特殊情况，对于一棵二叉树，每一个节点最多有2个子树。
（内容好多啊再看一遍笔记就去考试了啊啊啊啊啊啊啊）
*第十二讲 优先队列和堆（Priority Queue & Heap）
（鸽了 反正不考 之后再补不迟）
THE END
评论 (0)
