基于C语言
- 数据 data
- 数据 是对客观事物的符号表示，是一个广义宽泛的概念。
- 数据元素 data element
- 数据元素 在一个程序中被当作一个整体来对待。但数据元素也可能包括一些 数据项（数据的最小单位，不可分割，同 原子数据atom data ）。)
- 数据对象 data object
- 数据对象 是性质相同的数据元素的集合。
- 数据结构 data structure
- 数据结构 是相互之间存在一种或多种特定关系的数据元素的集合。注意，一个数据结构不仅包括了这些元素的相关关系，还包括了这些数据元素本身，所以它的定义形式是一个如下的二元组
data_structure = (D,S) - 通常我们会接触到以下四种 数据结构
- 集合：其中的元素关系松散（除了同属一个集合外）；
- 线性结构：其中的元素存在 一对一 的链接关系；
- 树形结构：其中的元素存在 一对多 的链接关系；
- 图状结构：其中的元素存在 多对多 的链接关系。
- 数据结构 是相互之间存在一种或多种特定关系的数据元素的集合。注意，一个数据结构不仅包括了这些元素的相关关系，还包括了这些数据元素本身，所以它的定义形式是一个如下的二元组
- 数据类型 data type
- 数据类型 是在程序语言当中用来刻画数据 特性 的概念。例如，python语言当中的 int 和 double 等就是数据类型，因为对它们操作要考虑它们特有的一些性质。
- 抽象数据类型 Abstract Data Type
- 抽象数据类型 的是和数据类型相当类似的概念，不过我们应该将它们理解成 数学模型（所以才配的上 抽象 ）。所以说它是一个更加广义的数据类型的 概念。例如，整型 的概念放到数学模型上来说，就是抽象数据类型， 而如果放到 C++ 当中就是 数据类型 了。
- 多形数据类型 Polymorphic Data Type
- 多形数据类型 指一种成分不确定的数据类型，它们可能是 整型 、字符串 或者其他更加复杂的成分，但却被视为同一种 抽象数据类型 ，所以这种特殊的数据类型被称作多形数据类型。通常这样的实现需要借助类似于 C++ 的面向 对象程序设计语言。
- 算法效率的度量
- 事后统计的方法 : 不好。因为通过计算程序运算时长的影响因素太多了。没意义。
- 事前分析估算的方法 : 一个高级语言所编写的程序在计算机上需要运行的时间主要取决于以下因素
- 算法所采用的策略
- 问题的规模（通常以循环次数表现）
- 程序所采用的语言级别（通常越高级的语言越慢）
- 编译程序的优良（其实和上一点原理上查不太多）
- 机器执行指令的速度
- 渐进时间复杂度 Asymptotic time complexity
- 算法的时间度量通常等于
T(n) = O(f(n))它表明随着规模n的增大，增长率f(n)会导致算法的执行时间增长。则O(f(n))表明算法的 渐进时间复杂度，简称 时间复杂度 。通常我们用 频度 （一个语句在程序中的执行次数）来表示一个程序的时间复杂度，通常我们会遇到类似O(n)常量阶；O(n)线性阶；O(n^k)多项式阶；O(log(n))对数阶；O(2^n)指数阶
- 通常，我们应尽可能选用
O(n^k)多项式阶，而避免采用指数阶的算法。
- 算法的时间度量通常等于
- 空间复杂度 space complexity
- 空间复杂度 S(n) 指执行一个程序所需要的存储空间的量度。不用太在意这个毕竟时间和内存，大家还是能买得起内存的。
-
一些概念
- 线性表 linear_list 是 最常用且最简单的 一种数据结构。简单来说，它是一个由多个 数据元素 构成的 有限 序列。然而对于其中的数据元素，还可以由多个 数据项 item 组成，如果是多个数据项构成的数据元素，我们就称之为 记录 record，对于多个记录的集合，我们称之为 文件 file。所以它们的关系是下面这样
数据项--->记录(数据元素)--->文件(线性表)
- 如果将线性表记为如下的序列形式
(a_1, a_2, ... , a_i-1, a_i, a_i+1, ... , a_n);
- 那么我们称
a_i-1是a_i的 直接前驱元素，a_i+1是a_i的 直接后驱元素； - 当线性表的长度
n == 0时，这个线性表是一个 空表； - 下标
i被称为数据元素a_i在一个线性表当中的 位序；
- 线性表 linear_list 是 最常用且最简单的 一种数据结构。简单来说，它是一个由多个 数据元素 构成的 有限 序列。然而对于其中的数据元素，还可以由多个 数据项 item 组成，如果是多个数据项构成的数据元素，我们就称之为 记录 record，对于多个记录的集合，我们称之为 文件 file。所以它们的关系是下面这样
-
算法2.1(Page20) 实现：将
线性表A根据线性表B按照A = A & B的规则扩展。void union(List &La, List Lb){ //insert all the diff elements(in La but not in Lb)into La. La_len = ListLength(La); Lb_len = ListLength(Lb); for(i = 1; i <= Lb_len; i++){ GetElem(Lb, i, e); if(!LocateElem(La, e, equal)) ListInsert(La, ++La_len, e); } }//union -
算法2.2(Page20) 实现：将
线性表A和线性表B合并，且均按照非递减排列void mergeList(List La, List Lb, List &Lc){ InitList(Lc); i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb); while((i <= La_len) && (j <= Lb_len)){ GetElem(La, i, ai); GetElem(Lb, j, bj); if(ai <= bj){ LPaistInsert(Lc, ++k, ai); ++i; } } }//MergeList
-
注：下文的线性表如无特殊说明均指顺序线性表
-
如果线性表当中的每个记录/元素（看是一个数据项还是多个数据项）需要
l个储存单元，那么第i个数据元素的存储位置LOC(a_i)满足以下等式LOC(a_i) = LOC(a_i-1) + l;LOC(a_i) = LOC(a_1) + (i-1)*l;
-
随机存取 是线性表存储结构的特性。因为线性表当中的数据元素是以在内存当中物理位置的相邻来表示数据元素的逻辑关系，所以我们可以任意地读取和修改任意 一个元素。同样，由于线性表的长度可变，所以需要创建的存储空间也应该是可变的，所以我们做如下初始操作
-
算法2.3(Page 23)
#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{ ElemType *elem; //elem is the base address of this list int length; //length is the current length of this list int listsize; //listsize is the current size of this list }SqList Status InitList_Sq(SqList &L){ //to create a empty list L L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); //if the base address 'elem' does not exist, then exit; L.length = 0; L.listsize = LIST_INIT_SIZE; return OK; }//InitList_Sq -
算法2.4(Page 24) 实现：在顺序
线性表L中第i个位置之前插入新的元素eStatus ListInsert_Sq(SqList &L, int i, ElemTYpe e){ if(i < 1 || i > L.length + 1) return ERROR; if(L.length >= L.listsize){ //if the room is full, increase it. newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType)); if(!newbase) exit(OVERFLOW); L.elem = newbase; L.listsize += LISTINCREMENT; } q = &(L.elem[i-1]); for (p = &(L.elem[L.length - 1]);p >= q; --p) *(p+1) = *p *q = e; ++L.length; return OK; }//ListInsert_Sq -
算法2.5 (Page 25) 实现：在顺序
线性表L中删除第i个元素，并用e返回其值；Status ListDelete_Sq(SqList &L, int i,ElemType &e){ if((i < 1) || (i > L.length)) return ERROR; p = &(L.elem[i-1]); e = *p; q = L.elem + L.length - 1; for(++p; p<=q; ++p) *(p-1) = *p; --L.length; return OK; }//ListDelete_Sq -
以上两个算法（算法2.4 和算法2.5）中主要的循环是移动后面的元素往前或往后，时间也主要耗费在这上面，所以我们需要对这两个循环细致研究。
-
假设
p_i是在第i个元素之前插入一个元素的概率（实际上只有前i-1个元素是保持不动的），那么在长度是n的线性表当中插入一个元素时所要移动元素次数的期望如下E_insert = sum(p_i*(n-i+1),i=1,i=n+1)
-
同理，假设
q_i是删除第i个元素的概率（虽然也是前i-1个元素没动，但是被删除的元素也相当于没动），那么我们有移动元素次数的期望如下E_delete = sum(q_i*(n-i),i=1,i=n)
-
多数情况下，我们可以假定任一元素前被插入一个元素和删除任一元素的概率是相同的，所以我们有
p_i = 1/(n+1)（因为可能会在列表最末尾加入元素，所以看起来一个表就有了n+1长）和q_i = 1/n，那么上述两个式子可以简化为E_insert = n/2E_delete = (n-1)/2
-
这也很符合我们的直觉。由此它们的时间复杂度是线性的，为
O(n)。 -
算法2.6 实现：在
线性表L中使用compare()函数查找于值e相等的元素，返回其位序。int LocateElem_Sq(SqList L, ElemType e, Status(*compare)(ElemType, ElemType)){ i = 1; p = L.elem; while (i <= L.length && !(*compare)(*p++, e)) ++i; if(i <= L.length) return i; else return 0; }//LocateElem_Sq
算法2.6的时间复杂度是O(L.length)，因为比较次数是介于(1,L.length)之间的某个值。类似的，对于合并两个顺序表的算法2.1（union算法），它的之间复杂度则是O(La.length*Lb.length).
-
算法2.7 实现：合并两个顺序线性表
La和Lb，并且按照非递减进行排列。void MergeList_Sq(SqList La, SqList Lb, SqList &Lc){ pa = La.elem; pb = Lb.elem; Lc.listsize = Lc.length = La.length + Lb.length; pc = Lc.elem = (ElemType*)malloc(Lc.listsize*sizeof(ElemType)); if(!Lc.elem) exit(OVERFLOW); pa_last = La.elem + La.length - 1; pb_last = Lb.elem + Lb.length - 1; while(pa <= pa_last && pb <= pb_last){ if(*pa <= *pb) *pc++ = *pa++; else *pc++ = *pb++; } while(pa <= pa_last) *pc++ = *pa++; while(pb <= pb_last) *pc++ = *pb++; //this two whiles are aim to insert the left elements after comparation. }//MergeList_Sq
线性链表 和顺序线性表的最大区别就是它不需要在物理地址上相邻存储，它的存储空间是任意的。因此，我们需要添加一个参数来将线性链表中的每一个元素链接起来，这样，每个数据元素就应该具有三个成分
* 自身的存储地址
* 自身的数据（数据域）
* 指向下一个元素的指针/链（指针域）
当然，一个完整的链表除了每个元素都应具有上述三个成分之外，还应该有一个指向第一个数据元素的头指针H，另外值得注意的是，由于最后一个元素后面没有其他元素，所以它的指针域为空NULL。由于这样的链表每个结点（即数据元素）当中只存储了一个指针，所以这样的表就叫做线性链表或者单向链表/单链表（区别于后文将提到的双向链表）。单向链表的存储结构如下
typedef struct LNode{
ElemType data;
struct LNode *Next;
}LNode, *LinkList;
有时，为了让 头指针H 不太孤独，我们也常常把它组合成为 头结点。头结点的数据域可以不存储任何信息，也可以存一些表的信息，例如 表的长度 等。头结点的数据域指向表中第一个真正的结点。由于链表的特殊存储方式，所以我们不能简单地按照物理地址相邻来取各个数据元素。
-
算法2.8 (Page 29) 实现：获取单链表当中的第
i个元素。Status GetElem_L(LinkList L, int i, ElemType &e){ p = L->next; j = 1; while(p && j<i){ p = p->next; ++j; } if(!p || j>i) return ERROR; e = p->data; return OK; }//GetElem_L
其中L->next代表的是头结点所指的第一个元素的指针；类似地，p->next表示的是p所指元素的指针域（即下一个元素的地址）；p->data表示p所指元素的数据。
由于单向链表的元素在存储时非常分散，所以在 插入/删除 元素的时候，应该注意对指针域的保护。我们通过 头结点/头指针 来找到一个单链表，同理，对于每一个元素和它们后面的一长串元素，也可以想象称 头结点 和单链表的关系。所以如果一个元素和它后面元素的链接断裂（指针域被破坏），那么我们就找不到它后面的所有元素了。就像一条悬挂的铁链，如果中间的一个环被破坏，那它下面的所有环也就都掉下去了，尽管下面的那些环仍然是链接着的。如何对指针域进行保护呢？通俗点来说就是，永远都在一切安排妥当之后再删除/修改原有的指针域。
例如插入，流程应该是下面这样
- 准备好需要插入的元素
- 将这个元素的指向插入后的下一个元素(
new->next = prev->next) - 最后将上一个元素指向这个新元素(
prev->next = new)
其实，第二步应该是new->next = subs，但在链表当中，我们不能直接获取到后驱元素subs的地址，所以需要借助前驱元素prev的指针域来获取subs的地址；第三步当中则在一切安排妥当之后，再修改原有的指针域。
删除 与之类似，但可以简化
- 将准备删除的元素的前一个元素的指针域指向准备删除的元素的后面的那个元素（看等式好了…）
prev->next = prev->next->next
虽然删除只有这么一个流程，但要理解这么做是因为被删除的元素我们就不用费心取处理它了，既然都分手了为什么还要做朋友呢？不过从长远发展来看，这是不负责的。因为如果“潜逃的”这个被删除元素被捕了，那么警察就可以根据它的指针域找到之前它所在的链表的所有后驱元素。例如，如果被删除的这个元素被我用在了别的链表，而我又恰巧没有对它的指针域进行更新，那我的这个新的链表就会多很多我不需要的元素。所以，在实际处理当中，视情况还是处理好被删除元素比较妥当。
-
算法2.9 (Page 29) 实现：在带头结点的
单链表L中第i个位置插入元素e。Status ListInsert_L(LinkList &L, int i, ElemType e){ p = L; j = 0; while(p && j < i-1){ p = p->next; ++j; } if(!p || j > i-1) return ERROR; s = (LinkList)malloc(sizeof(LNode)); //to create some room for LinkList with size of LNode and return the address to s s->data = e; //step 1 s->next = p->next; //step 2 p->next = s; //step 3 return OK; }//ListInsert_L -
算法2.10(Page 30) 实现：在带头结点的
单链表L删除第i个元素的值，并且由e返回其值。Status ListDelete(LinkList &L, int i, ElemType &e){ p = L; j = 0; while(p->next && j<i-1){ p = p->next; ++j; } if(!(p->next) || j > i-1) return ERROR; q = p->next; p->next = q->next; //to finish p->next->next e = q->next; free(q); //to avoid something wrong caused by this deleted element. return OK; }//ListDelete_L -
算法2.11(Page 30) 实现：逆位序输入
n个元素的值，建立带头结点的单链表L。void CreateList_L(LinkList &L, int n,){ L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; for(i = n; i > 0; --i){ p = (LinkList)malloc(sizeof(LNode)); scanf(&p->data); p->next = L->next; L->next = p; } }//CreateList_L -
算法2.12(Page31) 实现：按照非递减序列归并已经按照非递减规律排列好的
单链表La与单链表Lb。void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc){ pa = La->next; pb = Lb->next; Lc = pc = La; while(pa && pb){ if(pa->data <= pb->data){ pc->next = pa; pc = pa; pa = pa->next; } else{ pc->next = pb; pc = pb; pb = pb->next; } } pc->next = pa ? pa : pb; // expression ? case1 : case2 means if expression is true then execute case1, if false then case2. free(Lb); }//MergeList_L
和合并线性表、顺序线性表不同的是，对于链表的合并操作我们只需要不断的刷新单链表Lc的指针域就可以了。可以理解为所有的元素都已经为我们准备好，而我们需要做的就是将它们按照非递减的顺序用线连起来即可。
-
有时，利用数组的下标和
struct我们可以构建一个类似于链表的数据类型。#define MAXSIZE 1000 typedef struct{ ElemType data; int cur; }component, SLinkList[MAXSIZE]
在这里，我们用数组的下标来当作它们的地址（可以理解为 相对寻址模式），而上面的代码所建立的数组元素的结构中，data和链表的数据域具有等同的意义；cur则代表了指针域，它用来指示下一个结点在数组中的位置（下标）。我们称这类用数组表示的链表为 静态链表。下面仅一查找元素为例，注意静态链表在表达上的区别。
-
算法2.13(Page 32) 实现：在
静态单链表L中查找第一个值为e的元素，并返回其位序。int LocateElem_SL(SLinkList S, ElemType e){ i = S[0].cur; while(i && S[i].data != e) i = S[i].cur; return i; }//LocateElem_SL
其他算法请参阅教材page 33.
循环链表 的特点是表中最后一个元素的指针域指向 第一个元素或头结点，所以在普通单链表当中判断循环完成的条件（判断元素的指针域是否为空NULL）失效，此时正确的做饭应该是判断元素的指针域是否等于头结点的指针域。需要注意，教材中提到有些情况下循环链表不会设立头指针，而是采用尾指针来简化某些操作。例如，在合并两个设立了尾指针的循环链表只需要按照如下的操作即可完成
循环链表CLa的尾指针所指向的尾结点的指针域指向循环链表CLb的尾指针所指向的尾结点的指针域所指向的头结点；循环链表CLb的尾指针所指向的尾结点的指针域指向循环链表CLa的尾指针所指向的尾结点的指针域所指向的头结点。
简言之就是，尾 --指向-> 头。
顾名思义，双向链表 的每一个元素当中有两个指针域，一个指向 直接后继元素， 另一个指向直接前驱元素。
typedef struct DuLNode{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode, *DuLinkList
双向链表当中，有些只需要一个方向的指针就能够完成的操作例如ListLength、GetElem
、LocateElem等，这类操作和普通线性单链表的操作一致。但在插入、删除上有很大的不同,
因为双向链表需要修改两个方向的指针，例如
-
算法2.18(Page 36) 实现：在带有头结点的
循环链表L中的第i个位置插入元素e。Status ListInsert_DuL(DuLinkList &L, int i, ElemType e){ if(!(p = GetElemP_DuL(L, i))) // GetElemP_Dul will return the status of operation successful or not. return ERROR; if(!(s = (DuLinkList)malloc(sizeof(DuLNode)))) exit(OVERFLOW); s->data = e; s->prior = p->prior; p->prior->next = s; s->next = p; p->prior = s; return OK; }//ListInsert_DuL -
算法2.19(Page 37) 实现：删除带有头结点的
循环链表L的第i个元素，并且返回其值e。Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e){ if(!(p = GetElemP_DuL(L,i))) return ERROR; e = p->data; p->prior->next = p->next; p->next->prior = p->prior; free(p); return OK; }//ListDelete_DuL -
由于链表中的数据元素和普通的线性表当中的 位序 关系已经发生了很大的变化，所以在普通的线性表当中规定的一些基本操作在链表中就会显得笨拙和不适。所以我们从实际角度出发重新定义线性链表的基本操作。见教材Page 37
（略）
栈 是一个和我们直觉相悖的一类特殊的表，因为 栈 这个表的 表尾 被称为 栈顶 top，而 表头 反而被称为 栈底 bottom。根据修改栈时候的对数据元素操作的先后顺序，栈 还可以被称为 后进先出 Last in first out LIFO 型的线性表。
-
顺序栈 和顺序线性表类似，这种栈利用一组地址连续的相邻空间来存储栈中的各个元素，同时设 指针p 来指示栈顶元素所在的位置（地址）。
typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack;其中
stacksize表示 当前设定 的栈的容量空间，但应注意，由于多数情况下栈的大小是不定的，所以我们也会设定STACKINCREMENT作为当栈的容量不够时的增量。base表示 栈底 指针，在顺序栈中它始终指向栈底（表头），当判定base为NULL时，则可以断定这个栈时不存在的。top表示 栈顶 指针， 最开始和base是重合的，所以top = base也可以作为栈空的标记（栈空不表示栈不存在），不过最值得一说的是，无论什么时候，top都指向 下一个入栈的元素所存储的地址 。按照教材上的说法，我们认为栈的地址规律是 增序 的，也就是说，每当增加一个入栈的元素，top就会自动加1指向下一个入栈的元素应该存储的位置。
-
算法3.1(Page 48) 实现：将非负十进制数转化为八进制数。
void conversion(){ InitStack(S); scanf("%d",N); while(N){ Push(S, N % 8); N = N/8; } while(!StackEmpty(S)){ Pop(S,e); printf("%d",e); } }//conversion -
算法3.a(Written by Matt) 实现：括号匹配检验
void checkbrackect(){ InitStack(S); scanf(N); while(N){ if((N == '(') || (N == '[')) Push(S,N); if((N == ')') || (N == ']')){ Pop(S,e); if((N == ')') && (e == '(')) continue; elseif((N == ']') && (e == '')) continue; else return ERROR; } } return OK; } -
算法3.2(Page 50) 实现：创建一个行输入缓冲区
void LineEdit(){ InitStack(S); ch = getchar(); while(ch != EOF){ while(ch != EOF && ch!='\n'){ //EOF means the whole input behavior ends. switch(ch){ case '#' Pop(S,c); case '@' ClearStack(S); default Push(S,ch); } ch = getchar(); } ClearStack(S); if(ch != EOF) ch = getchar(); } }//LineEdit -
算法3.4(Page 53) 实现： 表达式求值
在通过堆栈进行表达式求值时，我们通常创建两个栈来实现运算，分别是OPTR栈和OPND栈。当进行求值时，对输入的表达式进行逐一字符读取。当获取的字符是运算符时，将其压入OPTR栈；当获取的字符是数字时，将其压入OPND栈。不过在每次对运算符进行操作是，应该与OPTR栈顶的运算符进行优先级比较，如果栈顶的优先级更高的话，就应该暂停对栈的修改，而是取这个优先级高的元素来进行运算。例如3*7-2的运算，OPTR栈应先压入*，在对-进行操作时，由于-的优先级低于*，所以我们就不能将-压入，而是让*出栈，进行乘法运算。简单来说，我们永远都应该压入优先级更高的运算符进入OPTR栈。
程序在调用函数时候的顺序和栈很类似。最后调用的函数要返回值给上一个被调用的函数，然后这个被调用的函数还要返回值给它更外层的那个函数。所以多个函数构成嵌套调用是，有一个 后调用先返回 的原则，这和栈的 后入先出很类似。当嵌套中调用的函数和外层函数相同时，就是 递归。在实际工作当中，我们需要在系统中建立一个 递归工作栈 来实现这样的调用。
和 栈 相反，队列是一种 先进先出 First in first out FIFO 的线性表。它只允许在表的一端插入元素，被称为 队尾 rare;在另一端进行删除元素，被称为 队头 front。
和链表类似。不同点是链队列有两个指向队头和队尾的指针称为 头指针 和 尾指针 。同样，为了操作方便，我们仿照链表也设立一个 头结点。初始化之后， 头指针 和 尾指针 都指向 头结点。这时如果我们需要在队列中插入新的元素，只需要让尾指针指向这个元素，并且让之前的最后一个元素也指向这个新元素就可以了；删除元素时需要修改 头结点 向后指向一个元素（ 头指针 其实是一直指向 头结点 的）。
由于队列的两端都可以进行操作，在修改了很多次头或者尾之后会导致整个队列的存储空间发生位移，所以我们没有办法灵活的利用空间。为此我们选择把顺序队列的储存空间臆造为一个环状的结构。
- 和循环链表的不同点：循环链表是 元素 头尾相接；循环队列是 存储空间 首尾相接。
- 使用时的注意：
- 如果不做任何处理，循环队列的 头指针
Q.front和 尾指针Q.rear相等时既可能时 队列空 也可能时 队列满。所以，可以设立一个 标志位 来区分这两种情况，或者少利用一个存储空间，这样 队列空 的时候是Q.front = Q.rear, 而 队列满 的时候就是Q.front = Q.rear + 1(指Q.front指向Q.rear在环状结构的下一个位置上)。 - 如果我们不知道队列的最大长度，就没有办法确定这个环的大小。所以，只有 能确定最大长度 的队列我们才可以采用 循环队列， 而对于 不知道最大长度 的队列我们应该选取 链队列。
- 如果不做任何处理，循环队列的 头指针
我们可以把二维数组视为一个线性表，线性表中的每一个数据元素又是一个线性表。所以一个数组看起来就是这个样子
Array a_ij =
a_00 -> a_01 -> a_02 -> a_03 -> ... -> a_0n
|
a_10 -> a_11 -> a_12 -> a_13 -> ... -> a_1n
|
a_20 -> a_21 -> a_22 -> a_23 -> ... -> a_2n
|
...
|
a_m0 -> a_m1 -> a_m2 -> a_m3 -> ... -> a_mn
上面的这个表示是把二维数组看作一个 列向量 线性表，这个线性表中的每一个数据元素代表了原二维数组的 对应行。类似地，也可以把这个二位数组看作一个 行向量 线性表，这时其中的数据元素就是原数组的 对应列。大概是这个样子
Array a_ij =
a_00 -> a_01 -> a_02 -> a_03 -> ... -> a_0n
| | | | |
a_10 a_11 a_12 a_13 a_1n
| | | | |
a_20 a_21 a_22 a_23 a_2n
| | | | |
... ... ... ... ...
| | | | |
a_m0 a_m1 a_m2 a_m3 a_mn
- 数组一旦被定义，它的 维数 和 维界 就不再改变。所以除了初始化和销毁之外，对一个数组只能进行 读写元素 的操作。
由于数组的固定性，所以我们可以用顺序表来很好地表示数组。但在存储空间当中我们很难用二维进行表示，所以我们通常用 首尾相接 的方式来把二维数组转化为一个一维数组（但是是分段的）。如果我们把 每一行 链接起来，那么称为主序是 行序。 如果我们把 每一列 链接起来，主序就是 列序 了。
对于这样的存储方式来说，只要我们知道了数据元素在数组中的下标，就可以查找到这个元素的存储位置了。
LOC(i,j) = LOC(0,0) + (b2 * i + j) * L;
// b2 is the length of demention 2 (equals the length of row)
// L is the size of each element
// LOC(0,0) is the location of element 00
for demention n
LOC(j_1,j_2,...,j_n) = LOC(0,0,...,0) + sum(c_i * j_i);
// c_n = L;
// c_i-1 = b_i * c_i;
// 1 < i <= n;
通常，用高级语言编写成叙事，都是用二维数组来存储矩阵。有时为了节省存储空间，我们对这类矩阵进行 压缩存储。
-
压缩存储：为多个 值相同 的元只分配一个存储空间；对 零元 不分配空间。
-
假若值相同的元素或者零元在矩阵中的分布 具有一定规律，则称其为 特殊矩阵，反之则是 稀疏矩阵。
- 对称矩阵：
n阶矩阵中的元满足性质a_ij = a_ji。对于对称矩阵，我们只需要存储一个对称元当中的一个元素即可，但由于 主对角线 上的并不存在对称元，所以我们还应该对它们进行存储。所以我们存储矩阵的 下三角（包括对角线）区域，总共需要存储的数据元素个数应该是n*(n+1)/2个。通常，我们以 行序 来存储这个区域，生成一个 一维数组sa[]。所以矩阵中的每一个元素的值和这个一维数组的关系如下
a_ij =
if(i >= j)
a_ij = i*(i-1)/2 + j - 1;
else
a_ij = j*(j-1)/2 + i - 1;
其实上面的关系一点也不复杂。从上面的关系可以得出，当i > j的时候，这个元素位于我们所存储的 下三角区域，所以直接计算它在这个 一维数组 当中是第几个就可以了。计算方法是，在下三角区域中对这个元素上面 所有行 的元素个数进行求和，为i*(i-1)/2；然后再加上它所在这一行的位置j；最后还有-1这项纯粹是因为 一维数组 是以0为下标起始的。当i < j的时候和上面的计算是完全一样的，只要我们把不在 下三角区域 里面的元素通过关系a_ij = a_ji转换到 下三角区域 就可以完全按照上面的计算方法计算。
- 三角矩阵：顾名思义，只有 一个包含对角线的三角区域 含有丰富的值，而除此之外的那个 不含有对角线的三角区域 是 常数c或零元0。则和对称矩阵的存储特点一样，只不过再增加一个存储那个 常数c或零元0 的存储空间即可。
- 对角矩阵：这类矩阵所有非零元都集中在以主对角线为中心的带状区域中。所以除了主对角线上和直接在对角线上、下放若干调对角线上的元之外，所有其他的元都是零。对于这样的矩阵，我们可以采取某种规则来对它进行压缩存储，例如 行序 或者 按照对角线的顺序。
假设在m*n的矩阵当中，有t个元素不为零，我们令delta = t / (m * n)为矩阵的 稀疏因子。通常认为当delta <= 0.05时称其为 稀疏矩阵。对稀疏矩阵的压缩存储的思路有以下几种：
- 三元组顺序表：利用三元组对非零元进行存储；三元组的内容是 非零元的行下标 、 非零元的列下标 和 非零元的值。通过一个数组来存储这样的三元组，就成了 非零元三元组表，通常我们还随同存储 矩阵的行数、 矩阵的列数 和 非零元的个数 这三个矩阵基本信息。
- 行逻辑链接的顺序表：为了方便地读写任意一个非零元（利用 三元组顺序表 读写元素是要从表头开始查找），我们可以将矩阵的 行信息数组
rpos固定在稀疏矩阵的结构当中。这种带行信息的三元组表就是 行逻辑链接的顺序表。其中 行信息数组rpos所存储的是 每行第一个非零元的位置。 - 十字链表：某些情况下非零元的变化比较大，利用紧凑的顺序表来存储非零元就不是很妥当了。所以我们采用链式存储结构。它应该含有以下成分：
- 非零元的行下标
i - 非零元的列下标
j - 非零元的值
e - 非零元的向下域
down - 非零元的向右域
right这里面的向右域right指向同行下一个非零元，向下域down指向同列下一个非零元。每个非零元结点既是某个行链表中的一个结点，又是某个列链表的一个结点。这样整个矩阵就构成了一个十字交叉的链表。
- 非零元的行下标
广义表和很多语言当中的 cell structure （例如 Matlab）很类似。简单来说就是一个表中数据元素类型不确定的表。所以这时一种 可变聚合类型 的表。这类表通常采用 链式存储结构 。这样数据元素不确定的情况下，我们通常把元素分为 表结点 和 原子结点 两类。所以在存储时，我们用如下的形式创建广义表
typedef enum {ATOM, LIST}ElemTag;
typedef struct GLNode {
ElemTag tag;
union{
AtomType atom;
struct{
struct GLNode *hp, *tp;
}ptr;
}
}*GList
上面的结构表明，每个 表结点 含有三个域，分别是 tag， hp 和 tp，其中 hp 用来指示结点， tp 用来指示下一个结点，表尾最后一个元素为空。每个 原子结点 含有两个域，分别是 tag 和 atom。其中 tag 和表结点中的 tag 用来区分是哪种结点，例如tag = 1则是表结点，tag = 0则是原子结点。如果按照上面的结构存储，必有 每个表（包括子表）中，必须由表结点来表示每一个数据元素。，这句话的意思是，如果这个元素是一个子表的话，那么这个表结点的 hp 就应该指向一个子表；如果这个元素是一个原子结点，那么对应的这个表结点 hp 就应该指向一个原子结点。广义表的深度定义为广义表中括弧的重数，是广义表的一种量度。
树 Tree 是n个结点的有限集。在任意一棵非空树当中，由且只有一个 根结点。其余结点可以被划分为m个互不相交的有限集，每个集合 本身还是一棵树，被称为 子树。每个树的 结点 包含 一个数据元素 和若干指向其子树的 分支。度为0的结点被称为 叶子结点 或 终端结点 , 其余的结点被称为 非终端结点 或 分支结点。 树的度 是树内个结点的度的 最大值。
结点的子树的根（也就是所指向的数据元素点）被称为该结点的 孩子 Child，那么这个结点被称为孩子的 双亲 Parent。同一个 双亲 下的孩子互称为 兄弟。一个结点下面所有子树中的结点都称为该结点的 子孙。
结点的 层次 是从根结点开始定义的，根在 第一层。 在同一层的结点互为堂兄弟。树中的最大层次被称为树的 深度 Depth。
如果一棵树中的各个结点是从左到右有次序的，则称该树是 有序树，否则就是 无序树。
森林 是多棵互不相交的树的集合。
二叉树 的每个结点最多有两棵子树，而且其子树有左右之分，所以 二叉树是有序树。 满二叉树 就是结点数最大（为2^k - 1）的二叉树。 完全二叉树 就是前面的编号结点都和 满二叉树 一一对应，只可能最后的几个连续的叶子结点缺失的二叉树。
- 二叉树的第
i层最多有2^(i-1)个结点。 - 深度为
k的二叉树最多有2^k - 1个结点。 - 对任何一棵二叉树，如果有
n个终端结点，那么树中度为2的结点数为n-1。 重点记忆 - 具有
n个结点的完全二叉树的深度为log_2_n + 1（取小于它的最大整数）。 - 如果对一棵有
n个结点的完全二叉树中的结点进行标号的话，则对第i个结点，有- 如果
i = 1，则结点i是二叉树的根，无双亲； - 如果
i > 1，则结点i的双亲PARENT(i) = i/2; - 如果
2i > n，则结点i是 叶子结点；否则其左孩子LCHILD(i) = 2i; - 如果
2i + 1 > n,则结点i没有右孩子；否则其右孩子RCHILD(i) = 2i+1。
- 如果
- 顺序存储结构：仅适用于 完全二叉树，如果一般的二叉树中相比满二叉树缺失结点较多就浪费了不少空间。 可能考
- 链式存储结构
- 单向链存储：一个结点由一个三个域的结构存储，分别为
lchild、rchild和data； - 双向链存储：不仅有单向链存储的三个域，还要添加一个指向其双亲的
parent域。
- 单向链存储：一个结点由一个三个域的结构存储，分别为
我们可以认定二叉树的每个结点都可以分为三个基本成分 根结点、 左孩子 LChild 和 右孩子 RChild。如果能逐渐遍历这三个基本成分，便可以遍历整个二叉树。根据对它们三个的访问顺序，我们可以有三种遍历方案（规定了无论何种方案都先遍历左孩子再遍历右孩子），分别称为 先序遍历、 中序遍历 和 后序遍历。具体方法如下
- 先序遍历
- 访问根结点
- 先序遍历 左子树
- 先序遍历 右子树
- 中序遍历
- 中序遍历 左子树
- 访问根结点
- 中序遍历 右子树
- 后序遍历
- 后序遍历 左子树
- 后序遍历 右子树
- 访问根结点
可以看出以上的方法都是一个 递归 的方法。例如先序遍历中的 先序遍历 左子树 相当于对左子树又调用了一次先序遍历程序。对于数学表达式的二叉树表示，还可以对应称这三种遍历方式为 前缀表示（波兰式）、 中缀表示 和 后缀表示（逆波兰式）。
上一节的遍历二叉树相当于对二叉树的每一个结点按照一定的规则进行了线性化操作。但是再存储空间当中，却找不到线性化之后的信息。所以我们引入 线索二叉树 来记录遍历序列中 前驱 与 后继 的信息。作如下结点结构| lchild | ltag | data | rtag | rchild |并规定当ltag或者rtag为0的时候分别指示它们的 左孩子 或者 右孩子，为1时，ltag指向该结点的直接前驱，rtag指向该结点的直接后继。
以上的存储结构存储的二叉树叫做 线索链表，其中指向前后的指针被称为 线索。带有 线索 的二叉树就是 线索二叉树 了。对二叉树进行遍历从而使其变为线索二叉树的过程被称为 线索化。
- 双亲表示法 以一组 连续空间 存储树的结点，同时再每个结点中附设一个 指示器 指示器双亲结点在表中的位置。
- 孩子表示法
在每个树的结点当中设置 指示器 指示该结点的孩子所在的位置，由于每个结点可能有多棵子树，所以我们才用 多重链表 的形式来表示。 多重链表 是指每个结点有多个指针域，在树的孩子表示法当中，我们通常使用如下的两种结构
`struct 1 | data | child1 | child2 | child3 | ... | childd |
struct 2
| data | degree | child1 | child2 | ... | childd |
```
第一种结构的每一个结点都是 同构 的，也就是所有结点的结构都完全相同，那么我们对于 结点的度d 就应该取所有结点当中最大的那个度d_max,但是由于树当中的很多结点的度小于d所以这样的结构会造成很多空间上的浪费。
第二种结构当中我们用域 degree 来指示每一个结点自有的度，虽然降低了空间复杂度，但是再操作上有所不便。
另一种方式就是把每个结点的孩子结点排列起来，看成一个 单向线性链表 。例如，一棵树有n个结点，那么图这棵树就有n个孩子链表， 而n个头指针又组成一个 线性顺序表。
3. 孩子兄弟表示法
又称 二叉树表示法 或 二叉链表表示法 。其实指示因为长得像二叉树而已。也是建立一个表，每个结点在表中有两个链域，分别指向该结点的第一个孩子结点 firstchild 和下一个兄弟结点 nextsibiling。
森林和二叉树的相互转换和前面的二叉树遍历一样都是利用了递归的**进行构建。下面进行简要说明
- 树转化为二叉树 对于树的 孩子兄弟表示法 来说，我们可以将其结构等价为一个二叉树的结构，因为它们实在是太像了，例如每个结点都有三个域，其中两个域是指针域。那么我们就可以将这样的结构视为一个二叉树，这样就完成了转化。那么不难得出，这个二叉树中结点的左孩子代表这个结点在原树中的 第一个孩子，而右孩子则代表了这个结点在原来的树中的 下一个兄弟。这与 孩子兄弟表示法 是相同的。
- 森林转化为二叉树
- 将森林中的每一棵树都转化为二叉树；
- 建立一棵新的二叉树，以森林中的第一棵树作为基本（可以发现现在这棵新的二叉树只有左子树）；
- 再将森林中的下一棵树接到这棵新二叉树的右子树上（可以发现现在这棵新树的右子树上也只有左子树）；
- 再将下一棵树接到之前接上的右子树的右子树上；
- 就这么接下去…… 其实可以理解为这棵森林的上面还有一个没有被表示的根结点，这个隐形的根结点链接着森林中每棵树的根，这样我们新转化出来的二叉树当中一次对右子树审视下去就会发现其实是森林中每一棵树的根。
- 二叉树转化为森林
- 首先将二叉树根结点的右子树砍下去，把根和左子树当作森林的第一棵树；
- 然后对上一步砍下来的右子树做同样的事情；
- 就这么砍下去…… 其实就是 森林转化为二叉树 的逆操作。
由于二叉树的孩子只有左孩子和右孩子两个，所以我们可以拓展出 先根遍历、 中根遍历 和 后根遍历。但是对于一般的树来说，如果用 中根遍历 我们并不知道把根安排再哪些子树的中间比较好，尴尬。所以我们就不要 中根遍历 了。对于一般的树，只有 先序遍历 和 后序遍历 两种。 不过，对于森林，我们推出了 先序遍历 和 中序遍历 两种方法。这里面的 中序遍历 实际上是对森林中的每一棵树都依次采用 后序遍历，所以步骤看起来是这个样子
- 中序遍历 森林中第一棵树的根结点的所有子树形成的森林；
- 访问第一棵子树的根结点；
- 中序遍历 除去第一棵树之后剩余的树所构成的森林；
是不是看起来很像 中序遍历 ，不过在理解的时候要明白其实只看前两步的话，是对森林中的每棵树采用了 后序遍历。
（略略略）
所谓 最优二叉树 就是指其 带权 路径长度最小。其中 带权路径长度 指 WPL = sum(w_k*l_k)。由此可见，Huffman树的构造和结点的权值息息相关，所以我们通过以下步骤来构造Huffman树。
- 在要构成Huffman树的结点集合当中选取两个权最小的结点构成一个小二叉树的左右子树，这棵小二叉树的根结点是这两个权值的和；
- 把这个小二叉树放回之前的结点集合当中，但我们只参考这个根结点的权值（也就是那两个子树的和），所以也可以视为一个结点；
- 重复
步骤1直到这个集合当中只含有一个树（Huffman树就是它！）；
注意：按照教材上的习惯，以及下文中Huffman编码的方便处理，我们通常将步骤1生成的树放在后面步骤中继续生成的树的 右子树 上。
所谓Huffman编码，是指一种前缀编码，利用这种编码进行通信的时候，能够尽可能少的减少通信成本。具体构造方法如下
- 用所要编码的结点构造称一个Huffman树，权值越大的证明越可能会用到这个结点；
- 令每个左分支为
0，每个右分支为1； - 从根到每个结点，按照分支上的数值构成编码；
- 图中的数据元素通常称作 顶点。
<v,w>表示从v到w的一条 弧，且称v为 弧尾 或 初始点，称w为 弧尾 或 终端点，具有这样特性的图被称为 有向图。如果说v和w之间的顺序是对称的，那么用(v,w)来表示一条 边，具有这样特性的图被称为 无向图。
有0.5*n(n-1)条边的无向图被称为 完全图，具有n(n-1)条弧的有向图被称为 有向完全图。如果边或者弧少于n*log_10_n的图被称为 稀疏图，反之我称其为 稠密图。 - 带权的一个图我们还可以叫它 网。
- 如果一个图在其边或者弧的集合当中删掉一些（甚至全部）的元素，再构成的图被称为原图的 子图。如果顶点和顶点之间有直接的边或者弧，则说这两个顶点 向关联 或者 相互 依附。 和一个顶点相关的边或者弧的数目被称为顶点的 度。 入度 表示以这个结点为终端点的边或者弧的个数； 出度 表是以这个结点为初始点的边或者弧的个数。
- 路径 是只存在与无向图中的一个概念，它表示了一系列线性向关联的顶点的集合，这样相关联的结点也称为 相通，如果图中任意两个结点都是相通的，那这样的图就是 连通图，无向图当中的极大（就是不对边进行拆分）连通子图被称为 连通分量。如果一个路径的第一个结点和最后一个结点是同一个结点，则称这样的路径为 回路 或 环。路径的序列当中顶点不会重复出现的路径是 简单路径。
- 类似的，在有向图当中，如果任意两个结点的 正反 路径都存在的话，那么这个有向图是一个 强连通图。
- 生成树 是指一个含有一个连通图的所有结点的一棵树，它只有刚好足以构成一棵树的
n-1条边，正因为边的这个性质，如果我们在生成树上任意添加一条边，必然会出现环。根据这个性质，如果一个图有n个结点，那么如果边的数量小于n-1，则这个图一定是非连通图；如果边的数量大于n-1，则这个图一定包含环。但是恰有n-1条边却不能证明这个图一定是生成树（可能既不连通又有环）。 - 有向树 只有一个顶点的入度为
0，其余点的入度皆为1。一个有向图的 生成森林 由若干棵有向树构成。
图很随意的，因为没有一个收敛的规则能让它安安稳稳排成一个线性表，所以通常顶点、邻接点的位置也是人为划分的。随缘。也正是因为这点，所以我们也没办法用顺序结构来存储一个图。
邻接表 邻接矩阵 深度优先搜索 广度优先搜索
构建 邻接矩阵 的方法非常简单，我们根据图中的所有结点 同时 作为行标和列标建立一个二维数组。如果从行标对应结点到列标对应结点是连通的，则对应元素置1，否则对应元素置0。对于带有权值的 网 来说，连通的对应元素置为其边或弧的权值，否则置为无穷。
- 无向图的邻接矩阵具有对称性，可以用压缩存储的方式只存储矩阵的上三角或下三角；
- 无向图：顶点的度就是邻接矩阵当中对应行（或对应列）的元素之和；
- 有向图：顶点的入度是对应行的元素之和，而顶点的入度则是对应列的元素之和；
邻接表 是图的一种链式存储结构，在邻接表当中，对途中每一个结点建立一个 单向链表。链表中的元素表示和其相邻的结点的位置（如果有多个结点都和这个链表所代表的结点相邻，顺序无所谓），在有向图当中则结点对应的链表中的元素表示以该结点为 起始点 的弧所对应的 终端点。他们的结构如下
表结点
| adjvex | nextarc | info |
-
头结点
| data | firstarc |
- 注意：通常图中的结点标号是从
1开始的，而表结点当中表示结点位置的域adjvex通常是从0开始的，注意不要出错！ - info域通常用来存储权值之类的信息；
- 一个结点的链表当中的元素代表了这个结点的 度，但对于有向图来说，只代表了 出度。
为了在某些情况下求结点的 入度 或者以该结点为头的弧，我们还会反过来建立 逆邻接表，即链表中的元素代表了所有指向这个表头所代表结点的结点。
十字链表里面的信息真的是太全了，全到有点复杂。比如先来看看它的结构
弧结点
| tailvex | headvex | hlink | tlink | info |
-
顶点结点
| data | firstin | firstout |
- 首先要明白一件事情：十字链表里面，除了头结点之外，其他的结点都是表示 弧 的。
tailvex表示这个弧的弧尾结点的位置；（数据域）headvex表示这个弧的弧头结点的位置；（数据域）hlink指向和这个弧的弧头相同的下一个弧；（指针域）tlink指向和这个弧的弧尾相同的下一个弧；（指针域）firstout指向第一个以这个结点为弧尾的弧；（指针域）firstin指向第一个以这个结点为弧头的弧；（指针域）
和十字链表类似，只不过针对无向图，而且域更多了一点。
边结点
| mark | ivex | ilink | jvex | jlink | info |
-
顶点结点
| data | firstedge |
mark标志域，在搜索或者遍历的时候可以用来标记是否对这条边操作过；ivex表示这条边所依附的其中一个结点；ilink表示和ivex相通依附的下一个边；jvex和jlink的意义同上，只不过是边所依附的另一个结点；firstedge表示头结点的第一条边。
对于一个图的遍历，可以分为 深度优先搜索 和 广度优先搜索 两种方法。例如教材中Page 168的图，我们可以写出如下的 邻接矩阵。具体方法是，如果两个结点相邻，对应元素就为1，如果不相邻那对应元素就为0。不过无论哪种操作，必须记下每一个访问过的结点，否则会出现重复访问的错误。
- 1 2 3 4 5 6 7 8
1 0 1 1 0 0 0 0 0
2 1 0 0 1 1 0 0 0
3 1 0 0 0 0 1 1 0
4 0 1 0 0 0 0 0 1
5 0 1 0 0 0 0 0 1
6 0 0 1 0 0 0 1 0
7 0 0 1 0 0 1 0 0
8 0 0 0 1 1 0 0 0
接下来对其采用 深度优先搜索，从结点1开始，行1的第一个非零元是对应的列是结点2，记录下结点2之后跳转到行2，继续搜索非零元，第一个非零元对应列结点1，但结点1已经记录过了，所以继续查找下一个非零元对应列结点4，记录下结点4，之后跳转到行4，以此类推。可以得到以下顺序
v1 -> v2 -> v4 -> v8 -> v5 -> v3 -> v6 -> v7
接下来尝试一下 广度优先搜索， 广度 和 深度 的区别在于，其在查找完当前行的 所有非零元 之后再跳转到这一行当中所记录的第一个非零元所对应结点的行。
当我们对行1进行搜索的时候，我们可以记录下结点2和结点3，之后跳转到行2再进行相同的工作。以此类推，可以得到以下顺序
v1 -> v2 -> v3 -> v4 -> v8 -> v5 -> v6 -> v7
我们在通过 深度优先搜索 和 广度优先搜索 对无向图进行遍历的时候，实际上只访问了一个无向图的部分边，这部分边和它们所依附的结点必然会构成一棵树（因为我们遍历的时候不会重复访问同一个结点），这样的树就是连通图的一棵生成树，并且分为 深度优先生成树 和 广度优先生成树 两种。如果是非连通图，显然生成的就是每个连通分量的生成树所构成的森林。嘻嘻嘻。
（略略略）
最小生成树 代表构造里爱你通往的最小代价（树上各边的权值之和最小）生成树。
- Prim 算法
Prim 算法的精髓就是建立一个表格，列标是除去第一个结点之后的结点，当然还会有一些辅助列；而行是随着流程动态变化的。具体步骤如下
- 从第一个结点开始进行逐列权值记录；
- 选取当前行当中权值最小的结点作为 下一行的参考结点 并且这个当前最小权值所在的边作为 最小生成树的边；
- 利用上一步记录的那个参考结点再逐列对权值进行刷新（如果有某列的权值可以更小，则记录下来，否则保留上一行的值）；
- 重复步骤2，直到构造出了完整的最小生成树。
- Kruskal 算法 这个算法比较简单，首先观察网中权值最小的一个边，如果它的顶点落在 不同的连通分量 当中，则选取这个边作为最小生成树的一个边；否则舍弃，继续观察下一条权值最小的边。
如果去掉某个结点会让连通图分割称两个或两个以上的连通分量，那么这个结点就是 关节点。没有关节点的连通图被称为 重连通图。
- 偏序 指集合当中只有部分元素之间可以相互比较；
- 全序 指集合当中的全部元素之间都可以相互比较；
- 拓扑排序 有偏序找到全序的过程就叫拓扑排序；
- 一个偏序的有向图通常用来表示一个流程图;
- AOV网 指顶点表示活动的网；
- 通过 AOV网 进行拓扑有序排列：
- 记录并删除网中没有前驱的结点
- 以此类推，完成拓扑有序排列
- 通过 AOV网 进行拓扑有序排列：
- AOE网 指边表示活动，权值表示活动的持续时间，顶点表示事件的网；
在 AOE网 当中，我们常用到以下概念：
- 事件的最早发生时间
ve：表示这个事件之前的活动已经 全部完成，所以在计算的ve的时候，我们要找从起始事件开始，到所求事件的最长路径（因为要保证有足够的事件让所有活动都能完成，如果选最短路径，就会有不少活动无法完成，这样事件也就没法达成了，需要注意）； - 事件的最晚发生时间
vl：表示 在不推迟整个工程的情况下，所求事件最晚可以什么时候发生（也最晚可以什么时候开始后面的活动）。由于涉及到了 整个工程 的完成时间，所以我们首先应该了解完成整个工程所需要的最短时间，也就是 结束事件 的最早发生时间（找从头到尾的最长路径）。然后还要获取这个事件之后的活动最快需要多久完成，也就是找这个结点到 结束事件 的最长路径。它们的差值vl所具有的意义就是，对于这个事件，我们可以给他vl的事件，无论你怎么拖延，只要在vl时间之内完成，都不会推迟整个工程。 - 关键路径 就是一个 AOE网 中最长的路径，因为它决定了整个工程的完成事件，所以我们称其为关键路径；
- 活动的最早开始时间
e：因为在 AOE网 当中，活动是在边上的，所以开始一个活动可以看作表示这个活动的弧的弧尾，所以e也就等同于弧尾结点的最早发生事件ve； - 活动的最晚开始时间
l：由于我们需要在vl事件内完成包括这个活动在内的之前所有活动，所以开始这个活动的最晚开始时间应该是l = vl - dut，式中dut表示活动的持续时间；
虽然关键路径的定义很简单，但对于复杂的 AOE网 来说，单纯的观察是不能可靠地求出关键路径的。所以我们通常用如下表格来求 关键路径：
| vertex | ve | vl | | activity | e | l | l-e |
|--------|----|----| |----------|---|---|-----|
| v1 | 0 | 0 | | a1 | 0 | 1 | 1 |
| ... | ...| ...| | ... |...|...| ... |
表格中记录每一个事件和结点的数据，通过l-e = 0来判断是否为 关键活动， 所有的 关键活动 构成 关键路径。
- 查找表 是有同一类型的数据元素或者记录构成的集合。
- 静态查找表 只能对其中的元素或者记录进行查找工作；
- 动态查找表 不仅能够进行查找工作，还可以在其中插入或者删除元素或记录；
- 主关键字 可以唯一地表示一个记录； 次关键字 可以用来识别若干个关键字；
顺序查找 Sequential Search 从表中的最后一个记录开始，逐个关键字比对，如果比对成功，则查找完成，如果直到第一个记录都没有比对成功，则说明表中没有所要查找的记录，则查找失败。
- 平均查找长度
ASL_ss = (n+1)/2
折半查找 Binary Search 首先将整个表划分两个部分，确定所查元素的范围之后；在将这个范围划分为两个部分，继续确定所查元素的范围，直到找到/找不到记录为止。
- 折半查找 当中我们通常设立三个指针，分别是
low、mid和high。其中mid = (low + high)/2（取下界）。所以在初始化之后，显然low指向表中的第一个元素，而high指向表中的最后一个元素，而且整个表通过mid分为了两个部分。
Hash 表 就是根据元素的特征，按照一定的规律（Hash 函数）进行编排的表。使用这样的表我们可以很轻易地根据元素的特征在表中查找到它，所以在最理想的情况下我们可以直接通过计算来得到元素的位置。
通过上面的说明，显然我们需要得到一个 Hash 函数。其中 除留余数法 是一种和能够最简单也最长用的构造 Hash 函数 的方法。
H(key) = key MOD p, p<=m;
公式中的约束条件p<=m是保证计算出来的地址不会超出表长m。
常用的方法有 线性探测再散列、 二次探测再散列 和 伪随机探测再散列。例如 线性探测再散列 常常表示为：
d_i+1 = (d1 + i) mod m;
其实上式是一种不规范的表述，因为我们在这里用符号d来表示增量，那么d_i+1应该是下一个增量，而d_1则表示第一个增量。但这里所表示的意思是，在表长范围内，我们对所求得的地址进行线性加1，所以公式中的d1应该是所求得的有冲突的原始地址，这点需要注意。
直接插入排序 是一种最 智障的 排序方法，它的基本操作将下一个记录插入到一个已经排好序的表当中，从而得到一个新的有序表。
- 折半插入排序 由于 智障的 直接插入排序 需要对每一个新的记录进行查找，所以我们可以再查找的过程当中显得不那么 智障。例如，使用 折半查找 来确定新的记录应该插入的位置。
- 2-路插入排序 略
- 表插入排序 略
希尔排序 又称 缩小增量排序，简单来说就是，先粗略排序，再细致排序。我们用增量序列来描述 粗略 和 细致 的区别。假设增量序列是(5, 3, 1)，意味着我们应该首先 每五个元素 对比一次，进行粗略排序；然后再 缩小增量， 每三个元素 对比一次，进行第二次排序；最后再 逐个元素 对比，完成最后一步排序。
尽管增量缩小，但是整个排序过程仍然是不收敛的，就是说，它和 归并排序 宏观上来看是不同的。例如在最后一步 增量1排序 的时候，仍然有很大的可能会出现需要移动很长距离的元素。这点需要注意。
快速排序 更形象的叫法应该是 分区块排序，它的精髓在于，每次都设定一个参考值（常被称为 枢轴 或 支点，通常选取无序表中的第一个元素），然后根据这个参考值把整个无序表分为两个部分：比参考值小 的元素都集中在它的左侧， 比参考值大 的元素都集中在它的右侧。再对这两个部分采用这样的方法进行进一步细分，最后完成排序。 所以如何准确地划分区块就是这个算法的核心问题。因为我们需要把整个无序表划分为 较小 和 较大 两个部分，而且分别集中在参考值的左右两边，前人帮我们总结出了如下的方法。
- 默认选取无序表第一个元素作为枢轴（参考值）；
- 设立一个尾指针，从无序表的最右边向前查找第一个比枢轴小的元素，并且把它与枢轴交换；（看是不是 较小 的元素就跑到左边了！）
- 设立一个头指针，再从无序表的最左边向后查找第一个比枢轴大的元素，并且把它与枢轴交换；（看是不是 较大 的元素就跑到右边了！）
- 不断地这样 左右交换，直到最后头尾指针重合，完成了 第一次划分。
智障的是，上面这么繁琐的做法只完成了第一次划分，也就是我们得到的表只不过分为了 较小 和 较大 的两个部分。接下来还需要继续对这两个部分分别采取这样的方法，直到最后整个表变得有序。
堆排序 也是一个 比较智障 的排序方法。它看起来很像输出 二叉排序树，不过对于 二叉排序树，我们只需要中根遍历它就好了，可是对于 堆排序，我们需要不断输出 堆顶元素（因为堆顶元素是表中最大/最小的那个元素），然后还需要对整个堆进行调整！
堆排序 所需要的 堆——假设它是一个 最小堆 ——是一个根结点最小，而且其他结点必小于其左右孩子的树。这样，宏观来看，只要我不断输出 具有这样性质的堆 的 堆顶元素，我就可以得到一个增序排列的表。但是重点在于 如何才能调整输出了一个结点之后的堆。
前人还总结了如下的方法给我们（以最小堆为例）：
- 输出堆顶元素后，用表中的最后一个元素补充到堆顶（虽然这显然是不对的，但是这么做能减少对内存的修改次数）；
- 然后从上之下开始逐个基本树调整，首先从根结点和它的两个孩子开始，选取其中最小的元素与根结点进行交换；
- 交换的这个元素之前所在的树必然受到了这个新来的原根结点的扰乱，则对这个基本树采取同样的调整方式；
- 直到最后产生了一个新的满足这样顺序的堆；
太烦了竟然打了这么多字，看不懂去看 Page281 的图。
看起来很像 快速排序 反了过来，实际上更有一点 希尔排序 的内涵在里面。 归并排序 指先每两个元素进行排序，然后把这两个元素看成一个整体；接下来对相邻的两个整体再进行归并，再看成一个整体（现在这个整体里就有4个元素了），不断这样归并，最后合成一个完整的有序表。
这里的归并所有的算法和前面的 顺序表 或 链表 的 Merge 算法，是一样的。