应试向的数据结构考试和实际写起代码来有很大区别。重复造轮子就不说了,更可怕的是,有时还需要应试者人脑模拟算法的执行过程。相对来说,对针对具体问题设计算法的考察较浅。
另外,有时王道书的代码风格奇特,我尽量改为了自己习惯的写法,这点需要特别注意。
本文中所有代码除非注明,均不保证能运行。
线性表 线性表:
顺序存储
链式存储
单链表(指针实现)
双链表(指针实现)
循环链表(指针实现)
静态链表(借助数组实现)
顺序表 线性表的顺序存储类型描述为:
1 2 3 4 5 const int MaxSize = 50 ;struct SqList { ElemType data[MaxSize]; int length; };
动态分配:
1 2 3 4 5 const int InitSize = 100 ;struct SeqList { ElemType* data; int MaxSize, length; };
C++ 的初始动态分配语句为:
1 L.data = new ElemType[InitSize];
注意:动态分配并不是链式存储,它同样属于顺序存储结构,物理结构没有变化,依然是随机存取方式,只是分配的空间大小可以在运行时动态决定。
例:17 页第 11 题。 顺序表的插入算法中,当 n 个空间已满时,可再申请增加分配 m 个空间,若申请失败,则说明系统没有(n + m 个连续 )可分配的存储空间。
顺序表的操作:插入、删除、按值查找。这部分的代码自己实现就行。
单链表 单链表的描述:
1 2 3 4 struct LNode { ElemType data; LNode* next; };
动态分配:
1 LNode* p = (LNode*) malloc (sizeof (LNode));
要表示一个单链表时,需要一个头指针L
:
带头节点的单链表:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 struct LNode { ElemType data; LNode* next; }; bool InitList (LNode*& L) { L = (LNode*) malloc (sizeof (LNode)); if (L==NULL ) return false ; L->next = NULL ; return true ; } bool isEmpty (LNode* L) { if (L->next==NULL ) return true ; else return false ; } void work () { LNode* L; InitList (L); }
按位序插入(带头节点):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 bool ListInsert (LNode*& L, int i, ElemType e) { if (i<1 ) return false ; LNode* p; int j = 0 ; p = L; while (p!=NULL && j<i-1 ){ p = p->next; j++; } if (p==NULL ) return false ; LNode* s = (LNode*) malloc (sizeof (LNode)); s->data = e; s->next = p->next; p->next = s; return true ; }
上面代码中,若i=1
,即是插在表头。
指定节点的后插操作:
1 2 3 4 5 6 7 8 9 bool InsertNextNode (LNode* p, ElemType e) { if (p==NULL ) return false ; LNode* s = (LNode*) malloc (sizeof (LNode)); s->data = e; s->next = p->next; p->next = s; return true ; }
此时,发现按位序插入(带头节点) 的代码可以通过复用指定节点的后插操作 的代码来简化:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 bool InsertNextNode (LNode* p, ElemType e) { if (p==NULL ) return false ; LNode* s = (LNode*) malloc (sizeof (LNode)); s->data = e; s->next = p->next; p->next = s; return true ; } bool ListInsert (LNode*& L, int i, ElemType e) { if (i<1 ) return false ; LNode* p; int j = 0 ; p = L; while (p!=NULL && j<i-1 ){ p = p->next; j++; } return InsertNextNode (p, e); }
指定节点的前插操作:
1 2 3 4 5 6 7 8 9 10 11 12 13 bool InsertPreNode (LNode* p, ElemType e) { if (p==NULL ) return false ; LNode* s = (LNode*) malloc (sizeof (LNode)); if (s==NULL ) return false ; s->next = p->next; p->next = s; s->data = p->data; p->data = e; return true ; }
按位序删除(带头节点):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 bool ListDelete (LNode*& L, int i, ElemType &e) { if (i<1 ) return false ; LNode* p; int j = 0 ; p = L; while (p!=NULL && j<i-1 ){ p = p->next; j++; } if (p==NULL ) return false ; if (p->next==NULL ) return false ; LNode* q = p->next; e = q->data; p->next = q->next; free (q); return true ; }
指定节点的删除:
1 2 3 4 5 6 7 8 9 10 bool DeleteNode (LNode* p) { if (p==NULL ) return false ; LNode* q = p->next; p->data = p->next->data; p->next = q->next; free (q); return true ; }
注意上图中的代码有一个 bug,在边界情况(p 节点刚好是最后一个节点)下会产生错误。但是只是应试的话无所谓了,扣也最多一两分,甚至不扣。
单链表按位查找:
1 2 3 4 5 6 7 8 9 10 11 12 13 LNode* GetElem (LNode*& L, int i) { if (i<0 ) return NULL ; LNode* p; int j = 0 ; p = L; while (p!=NULL && j<i){ p = p->next; j++; } return p; }
按值查找:
1 2 3 4 5 6 LNode* LocateElem (LNode*& L, ElemType e) { LNode* p = L->next; while (p!=NULL && p->data!=e) p = p->next; return p; }
注意:如果ElemType
是一个struct
,需要自己定义比较运算符。
1 2 3 4 5 6 7 8 struct ElemType { int a; int b; bool operator != (const ElemType& rhs); }; bool ElemType::operator != (const ElemType& rhs){ return (a!=rhs.a || b!=rhs.b); }
求表的长度:
1 2 3 4 5 6 7 8 9 int Length (LNode*& L) { int len = 0 ; LNode* p = L; while (p->next!=NULL ){ p = p->next; len++; } return len; }
尾插法建立单链表:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 LNode* List_TailInsert (LNode*& L) { int x; L = (LNode*) malloc (sizeof (LNode)); LNode *s, *r=L; scanf ("%d" ,&x); while (x!=9999 ){ s = (LNode*) malloc (sizeof (LNode)); s->data = x; r->next = s; r = s; scanf ("%d" ,&x); } r->next = NULL ; return L; }
头插法建立单链表:
1 2 3 4 5 6 7 8 9 10 11 void List_HeadInsert (LNode*& L) { InitList (L); int x; scanf ("%d" ,&x); while (x!=9999 ){ InsertNextNode (L, x); scanf ("%d" ,&x); } return ; }
总结:单链表的全部操作 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 struct LNode { ElemType data; LNode* next; }; bool InitList (LNode*& L) { L = (LNode*) malloc (sizeof (LNode)); if (L==NULL ) return false ; L->next = NULL ; return true ; } bool isEmpty (LNode* L) { if (L->next==NULL ) return true ; else return false ; } void work () { LNode* L; InitList (L); } bool InsertNextNode (LNode* p, ElemType e) { if (p==NULL ) return false ; LNode* s = (LNode*) malloc (sizeof (LNode)); s->data = e; s->next = p->next; p->next = s; return true ; } bool InsertPreNode (LNode* p, ElemType e) { if (p==NULL ) return false ; LNode* s = (LNode*) malloc (sizeof (LNode)); if (s==NULL ) return false ; s->next = p->next; p->next = s; s->data = p->data; p->data = e; return true ; } LNode* GetElem (LNode*& L, int i) { if (i<0 ) return NULL ; LNode* p; int j = 0 ; p = L; while (p!=NULL && j<i){ p = p->next; j++; } return p; } LNode* LocateElem (LNode*& L, ElemType e) { LNode* p = L->next; while (p!=NULL && p->data!=e) p = p->next; return p; } bool ListInsert (LNode*& L, int i, ElemType e) { if (i<1 ) return false ; LNode* p = GetElem (L, i-1 ); return InsertNextNode (p, e); } bool ListDelete (LNode*& L, int i, ElemType &e) { if (i<1 ) return false ; LNode* p = GetElem (L, i-1 ); if (p==NULL ) return false ; if (p->next==NULL ) return false ; LNode* q = p->next; e = q->data; p->next = q->next; free (q); return true ; } bool DeleteNode (LNode* p) { if (p==NULL ) return false ; LNode* q = p->next; p->data = p->next->data; p->next = q->next; free (q); return true ; } int Length (LNode*& L) { int len = 0 ; LNode* p = L; while (p->next!=NULL ){ p = p->next; len++; } return len; } LNode* List_TailInsert (LNode*& L) { int x; L = (LNode*) malloc (sizeof (LNode)); LNode *s, *r=L; scanf ("%d" ,&x); while (x!=9999 ){ s = (LNode*) malloc (sizeof (LNode)); s->data = x; r->next = s; r = s; scanf ("%d" ,&x); } r->next = NULL ; return L; } void List_HeadInsert (LNode*& L) { InitList (L); int x; scanf ("%d" ,&x); while (x!=9999 ){ InsertNextNode (L, x); scanf ("%d" ,&x); } return ; }
双链表 双链表的描述:
1 2 3 4 struct DNode { ElemType data; DNode *pre, *next; };
初始化:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 bool InitDList (DNode*& L) { L = (DNode*) malloc (sizeof (DNode)); if (L==NULL ) return false ; L->pre = NULL ; L->next = NULL ; return true ; } bool isEmpty (DNode* L) { if (L->next==NULL ) return true ; else return false ; } void work () { DNode* L; InitDList (L); }
双链表的插入:
1 2 3 4 5 6 7 8 9 10 11 bool InsertAfter (DNode* p, DNode* s) { if (p==NULL || s==NULL ) return false ; s->next = p->next; if (p->next != NULL ) p->next->pre = s; s->pre = p; p->next = s; return true ; }
双链表的删除和销毁:
1 2 3 4 5 6 7 8 9 10 11 12 13 bool DeleteAfter (DNode* p) { if (p==NULL ) return false ; DNode* q = p->next; if (q==NULL ) return false ; p->next = q->next; if (q->next!=NULL ) q->next->pre = p; free (q); return true ; }
1 2 3 4 5 6 7 void DestoryList (DNode*& L) { while (L->next!=NULL ) DeleteAfter (L); free (L); L = NULL ; }
双链表的遍历:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 while (p!=NULL ){ p = p->next; } while (p!=NULL ){ p = p->pre; } while (p->pre!=NULL ){ p = p->pre; }
循环链表 循环单链表:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 struct LNode { ElemType data; LNode* next; }; bool InitList (LNode*& L) { L = (LNode*) malloc (sizeof (LNode)); if (L==NULL ) return false ; L->next = L; return true ; } bool isEmpty (LNode* L) { if (L->next==L) return true ; else return false ; } bool isTail (LNode* L, LNode* p) { if (p->next==L) return true ; else return false ; }
具体代码可以自己实现,不再赘述。
循环双链表:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 struct DNode { ElemType data; DNode *pre, *next; }; bool InitDList (DNode*& L) { L = (DNode*) malloc (sizeof (DNode)); if (L==NULL ) return false ; L->pre = L; L->next = L; return true ; } void work () { DNode* L; InitDList (L); } bool isEmpty (DNode* L) { if (L->next==L) return true ; else return false ; } bool isTail (DNode* L, DNode* p) { if (p->next==L) return true ; else return false ; }
后插操作:
1 2 3 4 5 6 7 bool InsertAfter (DNode* p, DNode* s) { s->next = p->next; p->next->pre = s; s->pre = p; p->next = s; }
删除操作:
1 2 3 4 p->next = q->next; q->next->pre = p; free (q);
静态链表
1 2 3 4 5 6 7 8 9 10 const int Maxsize = 10 ;struct Node { ElemType data; int next; }; void work () { Node a[Maxsize]; }
栈、队列、数组 这 tm 还要学?
理论 顺序栈:代码自己实现。
共享栈:
链栈:通常采用不带头节点 的单链表实现,所有操作在表头进行。
队列:
循环队列:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 const int MaxSize = 50 ;struct myQueue { ElemType data[MaxSize]; int front, rear; }; void InitQueue (myQueue& qwq) { qwq.rear = qwq.front = 0 ; } bool isEmpty (myQueue qwq) { if (qwq.rear==qwq.front) return true ; else return false ; } bool EnQueue (myQueue& qwq, ElemType x) { if ((qwq.rear+1 )%MaxSize==qwq.front) return false ; qwq.data[qwq.rear] = x; qwq.rear = (qwq.rear+1 ) % MaxSize; return true ; } bool DeQueue (myQueue& qwq, ElemType& x) { if (qwq.rear==qwq.front) return false ; x = qwq.data[qwq.front]; qwq.front = (qwq.front+1 ) % MaxSize; return true ; }
队列的链式存储(左开右闭?):
通常采用带头节点 的单链表。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 struct LNode { ElemType data; LNode* next; }; struct LinkQueue { LNode* front; LNode* rear; }; void InitQueue (LinkQueue& qwq) { qwq.front = qwq.rear = (LNode*) malloc (sizeof (LNode)); qwq.front->next = NULL ; } void work () { LinkQueue qwq; InitQueue (qwq); } bool isEmpty (LinkQueue qwq) { if (qwq.front==qwq.rear) return true ; else return false ; } void EnQueue (LinkQueue& qwq, ElemType x) { LNode* s = (LNode*) malloc (sizeof (LNdoe)); s->data = x; s->next = NULL ; qwq.rear->next = s; qwq.rear = s; } bool DeQueue (LinkQueue& qwq, ElemType& x) { if (qwq.front==qwq.rear) return false ; LNode* p = qwq.front->next; x = p->data; qwq.front->next = p->next; if (qwq.rear==p) qwq.rear = qwq.front; free (p); return true ; }
应用 栈在括号匹配中的应用:
栈在表达式求值中的应用:
Reverse Polish notation(逆波兰表达式 = 后缀表达式)
Polish notation(波兰表达式 = 前缀表达式)
将中缀转后缀 和后缀表达式求值 两个算法结合起来:
树、二叉树 基本概念 有序树和无序树:
注意:此课程中度
的概念和离散数学中不同。 (万恶的图论名词差异)
树的一些性质:(注意这里的“度数”是歧义概念)
树中的节点数等于所有节点的度数之和加 1
度为 m 的树中第 i 层上至多有 $m^{i-1}$ 个节点($i\geqslant 1$)
高度为 h 的 m 叉树至多有 $\frac{m^h-1}{m-1}$ 个节点
具有 n 个节点的 m 叉树最小高度为 $\left \lceil \log_m(n(m-1)+1) \right \rceil$
结论 4 的推导:
假设高度为 $h$ , 由结论3 :
满二叉树、完全二叉树的性质:
二叉排序树:
平衡二叉树:
二叉树的性质 设非空二叉树中度
(歧义概念)为 0、1、2 的节点个数分别为 n0、n1、n2 , 则 $n_0=n_2+1$ (叶子节点比二分枝节点多一个)。推导如下:
假设树中节点总数为 n , 则:
$n = n_0 + n_1 + n_2$
$n = n_1 + 2n_2 + 1$
具有 n 个(n>0)节点的完全二叉树的高度 h 为 $\left \lceil \log_2(n+1) \right \rceil$ 或 $\left \lfloor \log_2n \right \rfloor +1$. (推导不难)
某个性质:
二叉树的存储 顺序存储(绝大多数情况下不会使用 ):
完全二叉树的此种存储结构的操作:
对于非完全二叉树:
链式存储:
代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 struct ElemType { int value; }; struct BinoTree { ElemType data; BinoTree* lchild; BinoTree* rchild; }; BinoTree* root = NULL ; root = (BinoTree*) malloc (sizeof (BinoTree)); root->data = {1 }; root->lchild = NULL ; root->rchild = NULL ; BinoTree* p = (BinoTree*) malloc (sizeof (BinoTree)); p->data = {2 }; p->lchild = NULL ; p->rchild = NULL ; root->lchild = p;
上面代码对应的图:
先、中、后序遍历
先 序遍历:根 、左、右(N LR)
中 序遍历:左、根 、右(LN R)
后 序遍历:左、右、根 (LRN )
例子:
和表达式的联系:
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 void preOrder (BinoTree* T) { if (T!=NULL ){ visit (T); preOrder (T->lchild); preOrder (T->rchild); } } void inOrder (BinoTree* T) { if (T!=NULL ){ inOrder (T->lchild); visit (T); inOrder (T->rchild); } } void postOrder (BinoTree* T) { if (T!=NULL ){ postOrder (T->lchild); postOrder (T->rchild); visit (T); } }
层次遍历 其实就是 BFS 。
执行算法:
初始化一个辅助队列
根节点入队
若队列非空,弹队首,访问弹出的节点,并将其孩子(若有)入队
重复 3 直至队列为空
伪代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 void bfs () { queue<node> qwq; node temp; qwq.push (temp); while (!qwq.empty ()){ node head = qwq.front (); qwq.pop (); qwq.push ((node){}); } }
一个 BFS 剪枝的实例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 #include <iostream> #include <queue> using namespace std;int n,m,sx,sy,ex,ey;char face; bool ok=true ;int a[53 ][53 ],ans;int fx[4 ][2 ]={{0 ,1 },{1 ,0 },{0 ,-1 },{-1 ,0 }};bool vis[53 ][53 ];struct node { int x,y; int dir,step; bool chan; }; inline int changedir (int dirt,int xia) { if (xia==0 )return (dirt+1 )%4 ; else if (xia==233 )return (dirt+2 )%4 ; else return (dirt-1 +4 )%4 ; } inline bool check (int x,int y) { if (x<1 ||x>=n||y<1 ||y>=m)return false ; if (a[x][y]||a[x+1 ][y])return false ; if (a[x][y+1 ]||a[x+1 ][y+1 ])return false ; return true ; } inline bool bfs () { queue<node> qwq; node temp; temp.x=sx;temp.y=sy; if (face=='E' )temp.dir=0 ; if (face=='S' )temp.dir=1 ; if (face=='W' )temp.dir=2 ; if (face=='N' )temp.dir=3 ; temp.step=0 ; temp.chan=false ; qwq.push (temp); vis[temp.x][temp.y]=true ; while (!qwq.empty ()) { node head=qwq.front (); qwq.pop (); for (int i=1 ;i<=3 ;i++) { int nx=head.x+fx[head.dir][0 ]*i; int ny=head.y+fx[head.dir][1 ]*i; if (!check (nx,ny))break ; if (vis[nx][ny])continue ; if (nx==ex&&ny==ey) { ans=head.step+1 ; return true ; } qwq.push ((node){nx,ny,head.dir,head.step+1 ,false }); vis[nx][ny]=true ; } if (head.chan)continue ; int dirti=changedir (head.dir,0 ); int dirti2=changedir (head.dir,1 ); qwq.push ((node){head.x,head.y,dirti,head.step+1 ,true }); qwq.push ((node){head.x,head.y,dirti2,head.step+1 ,true }); if (ok) { ok=false ; int dirti3=changedir (head.dir,233 ); qwq.push ((node){head.x,head.y,dirti3,head.step+2 ,true }); } } return false ; } int main () { cin>>n>>m; for (int i=1 ;i<=n;i++) for (int j=1 ;j<=m;j++) cin>>a[i][j]; cin>>sx>>sy>>ex>>ey>>face; if (sx==ex&&sy==ey)cout<<0 ; else if (bfs ())cout<<ans; else cout<<"-1" ; return 0 ; }
注意在树或者图中需要在具体的数据结构上实现 BFS ,例如链式前向星。
有必要给出应试代码,以下代码只适合二叉树:
由遍历序列构造二叉树 若只给出一棵二叉树的 前/中/后/层 序遍历序列中的一种,不能唯一确定一棵二叉树。
由二叉树的遍历序列构造二叉树,需已知以下三种信息中的任一种:
前序+中序 遍历序列
后序+中序 遍历序列
层序+中序 遍历序列
由前序+中序遍历序列确定二叉树:
由后序+中序遍历序列确定二叉树:
由层序+中序遍历序列确定二叉树:
补充说明:
线索二叉树 问题的引入:
线索二叉树的概念:
线索二叉树的存储结构:
1 2 3 4 5 6 7 8 struct ThreadNode { ElemType data; TreadNode* lchild; TreadNode* rchild; bool ltag, rtag; };
先序线索二叉树:
后序线索二叉树:
中序线索化代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 struct ThreadNode { ElemType data; TreadNode* lchild; TreadNode* rchild; bool ltag, rtag; }; ThreadNode* pre = NULL ; void visit (ThreadNode* q) { if (q->lchild==NULL ){ q->lchild = pre; q->ltag = 1 ; } if (pre!=NULL && pre->rchild==NULL ){ pre->rchild = q; pre->rtag = 1 ; } pre = q; } void inThread (ThreadNode* T) { if (T!=NULL ){ inThread (T->lchild); visit (T); inThread (T->rchild); } } void CreateInThread (ThreadNode* T) { pre = NULL ; if (T!=NULL ){ inThread (T); if (pre->rchild==NULL ){ pre->rtag = 1 ; } } }
先序线索化代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 struct ThreadNode { ElemType data; TreadNode* lchild; TreadNode* rchild; bool ltag, rtag; }; ThreadNode* pre = NULL ; void visit (ThreadNode* q) { if (q->lchild==NULL ){ q->lchild = pre; q->ltag = 1 ; } if (pre!=NULL && pre->rchild==NULL ){ pre->rchild = q; pre->rtag = 1 ; } pre = q; } void preThread (ThreadNode* T) { if (T!=NULL ){ visit (T); if (T->ltag==0 ) preThread (T->lchild); preThread (T->rchild); } } void CreatePreThread (ThreadNode* T) { pre = NULL ; if (T!=NULL ){ preThread (T); if (pre->rchild==NULL ) pre->rtag = 1 ; } }
后序线索化代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 struct ThreadNode { ElemType data; TreadNode* lchild; TreadNode* rchild; bool ltag, rtag; }; ThreadNode* pre = NULL ; void visit (ThreadNode* q) { if (q->lchild==NULL ){ q->lchild = pre; q->ltag = 1 ; } if (pre!=NULL && pre->rchild==NULL ){ pre->rchild = q; pre->rtag = 1 ; } pre = q; } void postThread (ThreadNode* T) { if (T!=NULL ){ postThread (T->lchild); postThread (T->rchild); visit (T); } } void CreatePostThread (ThreadNode* T) { pre = NULL ; if (T!=NULL ){ postThread (T); if (pre->rchild==NULL ){ pre->rtag = 1 ; } } }
中序线索二叉树找中序后继:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ThreadNode* firstNode (ThreadNode* p) { while (p->ltag==0 ) p = p->lchild; return p; } ThreadNode* nextNode (ThreadNode* p) { if (p->rtag==0 ) return firstNode (p->rchild); else return p->rchild; } void inOrderScan (ThreadNode* T) { for (ThreadNode* p=firstNode (T); p!=NULL ; p=nextNode (p)){ visit (p); } }
中序线索二叉树找中序前驱思路(上面找后继的思路类似,不回头补了):
中序线索二叉树找中序前驱代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ThreadNode* lastNode (ThreadNode* p) { while (p->rtag==0 ) p = p->rchild; return p; } ThreadNode* preNode (ThreadNode* p) { if (p->ltag==0 ) return lastNode (p->lchild); else return p->lchild; } void revInOrderScan (ThreadNode* T) { for (ThreadNode* p=lastNode (T); p!=NULL ; p=preNode (p)){ visit (p); } }
先序线索二叉树找先序后继:
先序线索二叉树找先序前驱:
可以发现,按照之前的思路无法实现。但是,如果每个节点增加指向其父节点的指针 ,则可以有如下思路:
后序线索二叉树找后序前驱:
后序线索二叉树找后序后继:
可以发现,按照之前的思路无法实现。但是,如果每个节点增加指向其父节点的指针 ,则可以有如下思路:
总结:
树、森林 孩子兄弟表示法(很怪,感觉不实用):
树和二叉树的转化:
森林和二叉树的转换:
树的遍历:先根遍历、后根遍历、层序遍历。
森林的遍历:先序遍历、中序遍历。
特别提醒: 以上只是一个应试的可选补充,熟悉 OI 代码直接在纸上写 OI 代码即可。例如树的遍历,采用链式前向星:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 struct Edge {int v,w,next;}edge[MAXM];int tot,head[MAXN];void addedge (int x,int y,int z) { edge[++tot].v=y; edge[tot].w=z; edge[tot].next=head[x]; head[x]=tot; } for (int i=head[x];i;i=edge[i].next){ int y=edge[i].v; }
树与二叉树的应用 Huffman树:https://dropsong.github.io/posts/9e22caea.html#Huffman%E6%A0%91
性质:n 个叶子节点最终构成的 Huffman 树节点总数为 2n-1 .
Huffman 编码:
并查集:https://dropsong.github.io/posts/9e22caea.html#%E5%B9%B6%E6%9F%A5%E9%9B%86
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <cstdio> #include <iostream> using namespace std;const int MAXN=10010 ;int uset[MAXN];void makeset (int size) { for (int i=0 ;i<size;i++)uset[i]=i; } int find (int x) { if (x!=uset[x])uset[x]=find (uset[x]); return uset[x]; } void unionset (int x,int y) { x=find (x); y=find (y); if (x==y)return ; uset[x]=y; } int main () { int n,m; cin>>n>>m; makeset (n+1 ); int z,x,y; while (m--) { scanf ("%d%d%d" ,&z,&x,&y); if (z==1 )unionset (x,y); else if (z==2 ){ if (find (x)==find (y)) printf ("Y\n" ); else printf ("N\n" ); } } return 0 ; }
图 基本概念 邻接矩阵的某个性质(建议配合离散数学食用):
类似地,有:
邻接表法:
十字链表存储有向图,空间复杂度 $O(|V|+|E|)$
只用于存储有向图
找到指定顶点的所有出边:顺着绿色线路找
找到指定顶点的所有入边:顺着橙色线路找
邻接多重表存储无向图,空间复杂度 $O(|V|+|E|)$
只能用于存储无向图
删除边、删除节点等操作“很方便”
我选择,链式前向星。希望阅卷老师能看懂。
图的基本操作 Adjacent(G, x, y)
:判断图 G 是否存在边<x,y>
或(x,y)
无向图
邻接矩阵时间复杂度 $O(1)$
邻接表时间复杂度 $O(1)\rightarrow O(|V|)$
有向图
邻接矩阵时间复杂度 $O(1)$
邻接表时间复杂度 $O(1)\rightarrow O(|V|)$
Neighbors(G, x)
:列出图 G 中与节点 x 邻接的边
无向图
邻接矩阵时间复杂度 $O(|V|)$
邻接表时间复杂度 $O(1) \rightarrow O(|V|)$
有向图
邻接矩阵时间复杂度 $O(|V|)$
邻接表时间复杂度
出边 $O(1) \rightarrow O(|V|)$
入边 $O(|E|)$
InsertVertex(G, x)
:在图 G 中插入顶点 x
无向图和有向图时间复杂度相同
邻接矩阵时间复杂度 $O(1)$
邻接表时间复杂度 $O(1)$
DeleteVertex(G, x)
:从图 G 中删除顶点 x
无向图
邻接矩阵时间复杂度 $O(|V|)$
邻接表时间复杂度 $O(1) \rightarrow O(|E|)$
有向图
邻接矩阵时间复杂度 $O(|V|)$
邻接表时间复杂度
删出边 $O(1) \rightarrow O(|V|)$
删入边 $O(|E|)$
AddEdge(G, x, y)
:加边
无向图和有向图类似
邻接矩阵 $O(1)$
邻接表 $O(1)$ (头插法)
FirstNeighbor(G, x)
:求图 G 中顶点 x 的第一个邻接点,若有返回顶点号;若没有或者根本不存在 x ,返回 -1
无向图
邻接矩阵 $O(1) \rightarrow O(|V|)$
邻接表 $O(1)$
有向图
邻接矩阵 $O(1) \rightarrow O(|V|)$
邻接表
找出边邻接点 $O(1)$
找入边邻接点 $O(1) \rightarrow O(|E|)$
NextNeighbor(G, x, y)
:假设图 G 中顶点 y 是顶点 x 的一个邻接点,返回除 y 外顶点 x 的下一个邻接点的顶点号,若 y 是 x 的最后一个邻接点,返回 -1
无向图
邻接矩阵 $O(1) \rightarrow O(|V|)$
邻接表 $O(1)$
有向图类似
Get_edge_value(G, x, y)
:获取图 G 中边对应的权值。 $\quad$ Set_edge_value(G, x, y, v)
:设置图 G 中边对应的权值为 v
与Adjacent(G, x, y)
(判断是否存在边)雷同,核心在于找到边。因此时间复杂度为:
邻接矩阵 $O(1)$
邻接表 $O(1) \rightarrow O(|V|)$
图的遍历 一、BFS
对教科书代码留个印象:
同一个图的邻接矩阵表示方式唯一,因此广度优先遍历序列唯一。同一个图的邻接表表示方式不唯一,因此广度优先遍历序列不唯一。
复杂度分析:
广度优先生成树:
广度优先生成森林:
二、DFS
对教科书代码留个印象:
复杂度分析:
同一个图的邻接矩阵表示方式唯一,因此深度优先遍历序列唯一。同一个图的邻接表表示方式不唯一,因此深度优先遍历序列不唯一。
深度优先生成树、深度优先生成森林,与之前提到的类似,不再赘述。
最小生成树 一睹芳容:
Prim 算法的实现思想:
下面给出 kruscal 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include <cstdio> #include <algorithm> using namespace std;const int MAXN = 5000 +10 ;const int MAXM = 200000 +10 ;struct Edge {int u,v,w;}edge[MAXM];int uset[MAXN],n,m,ans;int find (int x) { if (uset[x]!=x)uset[x]=find (uset[x]); return uset[x]; } void unionset (int x,int y) { x=find (x); y=find (y); if (x==y)return ; uset[x]=y; } bool cmp (Edge x,Edge y) {return x.w<y.w;}int main () { scanf ("%d%d" ,&n,&m); for (int i=1 ;i<=m;i++) { int x,y,z; scanf ("%d%d%d" ,&x,&y,&z); edge[i].u=x; edge[i].v=y; edge[i].w=z; } sort (edge+1 ,edge+1 +m,cmp); for (int i=0 ;i<=n;i++)uset[i]=i; int cnt=0 ; for (int i=1 ;i<=m;i++) { int x=find (edge[i].u); int y=find (edge[i].v); if (x==y)continue ; ans+=edge[i].w; unionset (x,y); if (++cnt==n-1 )break ; } if (cnt<n-1 )printf ("orz" ); else printf ("%d" ,ans); return 0 ; }
最短路径问题 SPFA 算法(用于求单源最短路径):
AKA, 队列优化的 Bellman-Ford 算法
允许图中存在负权边
不可求负环 ,可判断负环
在稀疏图上效率较高,时间复杂度 $O(km)$ , k 为较小的常数
在稠密图或特殊构造的 网格图上,算法可能退化为 $O(nm)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include <bits/stdc++.h> #define MAXM 500010 #define MAXN 10010 #define INF 2147483647 using namespace std;int n,m,s,dis[MAXN];bool inq[MAXN];struct Edge {int v,w,next;}edge[MAXM];int tot,head[MAXN];inline void addedge (int x,int y,int z) { edge[++tot].v=y; edge[tot].w=z; edge[tot].next=head[x]; head[x]=tot; } void spfa () { queue<int > qwq; for (int i=1 ;i<=n;i++)dis[i]=INF; qwq.push (s); dis[s]=0 ;inq[s]=true ; while (!qwq.empty ()) { int x=qwq.front (); qwq.pop (); inq[x]=false ; for (int i=head[x];i;i=edge[i].next){ int y=edge[i].v; if (dis[y]>dis[x]+edge[i].w){ dis[y]=dis[x]+edge[i].w; if (!inq[y]){qwq.push (y);inq[y]=true ;} } } } } int main () { scanf ("%d%d%d" ,&n,&m,&s); for (int i=1 ;i<=m;i++){ int x,y,z; scanf ("%d%d%d" ,&x,&y,&z); addedge (x,y,z); } spfa (); for (int i=1 ;i<=n;i++) if (s==i)printf ("0 " ); else printf ("%d " ,dis[i]); return 0 ; }
Dijkstra 算法(用于求单源最短路径):
要求图的边权为正
可以求环
时间复杂度:
考试中可认为(也就是未优化的算法版本)复杂度是 $O(n^2)$
若用二叉堆(C++ STL priority_queue
)维护 dist 数组,最终可以得到 $O((m+n)\log n)$ 的复杂度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 #include <cstdio> #include <queue> #define MAXM 200010 #define MAXN 100010 using namespace std;const int INF =2147483647 ;int n,m,s,dis[MAXN];bool done[MAXN];int tot,head[MAXN];struct Edge {int v,w,next;}edge[MAXM];inline void addedge (int x,int y,int z) { edge[++tot].v=y; edge[tot].w=z; edge[tot].next=head[x]; head[x]=tot; } struct node { int u,dist; bool operator <(const node& v)const { return dist>v.dist; } }; priority_queue<node> qwq; inline void dijkstra () { for (int i=1 ;i<=n;i++)dis[i]=INF; dis[s]=0 ; qwq.push ((node){s,0 }); while (!qwq.empty ()) { node front=qwq.top (); qwq.pop (); int u=front.u,dist=front.dist; if (done[u])continue ; done[u]=true ; for (int i=head[u];i;i=edge[i].next) { int y=edge[i].v,z=edge[i].w; if (dis[u]+z<dis[y]) { dis[y]=dis[u]+z; qwq.push ((node){y,dis[y]}); } } } } int main () { scanf ("%d%d%d" ,&n,&m,&s); int x,y,z; for (int i=1 ;i<=m;i++){ scanf ("%d%d%d" ,&x,&y,&z); addedge (x,y,z); } dijkstra (); for (int i=1 ;i<=n;i++)printf ("%d " ,dis[i]); return 0 ; }
Dijkstra 输出路径:
Floyd 算法:
喜闻乐见的人脑模拟算法执行:
找路径:
Floyd 代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <cstdio> #define MIN(a,b) ((a)<(b)?(a):(b)) const int MAXN = 103 ;const int MAXM = 4503 ;const int INF = (0x7fffffff >>1 )-10 ;int dis[MAXN][MAXN],n,m;int main () { scanf ("%d%d" , &n, &m); for (int i=1 ;i<=n;i++) for (int j=1 ;j<=n;j++) if (i!=j)dis[i][j] = INF; for (int i=1 ; i<=m; i++){ int x, y, z; scanf ("%d%d%d" ,&x, &y, &z); dis[x][y] = dis[y][x] = z; } for (int k=1 ; k<=n; k++) for (int i=1 ; i<=n; i++) for (int j=1 ; j<=n; j++) dis[i][j]=dis[j][i]=MIN (dis[i][j], dis[i][k]+dis[k][j]); for (int i=1 ; i<=n; i++){ for (int j=1 ; j<=n; j++){ printf ("%d " ,dis[i][j]); } putchar ('\n' ); } return 0 ; }
小结:
有向无环图描述表达式 知识里的你,再弱小也是真的:
看一眼真题:
此类题目的解题方法:
最后看一个特例:
从上面的特例(左)可以发现,允许重边;另外,可以画出的图不唯一。
拓扑排序 一个概念,AOV 网:
拓扑排序是对有向无环图的所有顶点,生成一个线性的序列,来表达这个图的顶点之间的先后关系:
通常使用 BFS 实现拓扑排序,流程如下:
首先建立空队列,把所有入度为 0 的节点加入队列
从队列中取出一个节点,将从其出发的所有边删除。在编程上,即将边所连到的点入度减一,判断该边通向的节点是否入度变为 0 ,若是,则加入队列
重复以上步骤,直至队列中不剩下任何节点为止
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 queue<int > qwq; void topoSort () { for (int i = 0 ; i < N; i++) if (inDegree[i] == 0 ) qwq.push (i); while (!qwq.empty ()) { int v = qwq.front (); qwq.pop (); cout << v << " " ; for (list<int >::iterator it = edge[v].begin (); it != edges[v].end (); it++) { inDegree[*it]--; if (!inDegree[*it]) qwq.push (*it); } } }
对于稍复杂的情况或使用链式前向星数据结构的代码,请参考:https://dropsong.github.io/posts/9e22caea.html#%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F
拓扑排序是对有向无环图而言的。如果需要判断图中是否存在环,则可以统计是否所有的顶点都入过队列,若存在未入过队的节点,代表图中存在环。
如果你愿意看王道的代码的话也不是不行:
以上代码的时间复杂度为 $O(|V|+|E|)$ ,若采用邻接矩阵,则为 $O(|V|^2)$ .
逆拓扑排序:
逆拓扑排序代码实现:
以上代码中,无论从哪一个顶点出发进行 DFS 都可以得到正确输出。
关键路径 概念,AOE 网:
AOE 网两个简单的性质:
仅有一个入度为 0 的顶点,称为“开始顶点(源点)”,它表示整个工程的开始
仅有一个出度为 0 的顶点,称为“结束顶点(汇点)”,它表示整个工程的结束
从源点到汇点的有向路径可能有多条,所有路径中,具有最大路径长度的路径称为关键路径 ,而把关键路径上的活动称为关键活动 。完成整个工程的最短时间就是关键路径的长度,若关键活动不能按时完成,则整个工程的完成时间就会延长。
算法思路:
大致实现思路:
若缩短关键活动的时间,可以缩短工期。但当缩短到一定程度时,关键活动可能会变成非关键活动。
可能有多条关键路径,只提高一条关键路径上的关键活动速度并不一定能缩短整个工程的工期。 只有加快那些包括在所有关键路径上的关键活动才能缩短工期。
最后,贴一个看起来像关键路径、但其实可以用拓扑排序的题目:P1113 杂务
查找 查找长度:在查找运算中,需要对比关键字的次数称为查找长度。
平均查找长度(ASL, Average Search Length):所有查找过程中,进行关键字的比较次数的平均值。
上式中,n 为数据元素个数;$P_i$ 为查找第 i 个元素的概率;$C_i$ 为查找第 i 个元素的查找长度。
一般来说,题目中若无特别说明,默认查找任何一个元素的概率都相同 。
顺序查找 某个小技巧:
查找判定树:
折半查找 二分查找的实现细节需要特别注意,在某些特殊的情况下,不正确的写法会导致死循环或是其他的错误。王道的代码就是错误的。
我们直接来看正确的做法:总是将查找区间设为左闭右开的。以题目P1824 进击的奶牛 为例,该题的做法是二分答案,给出代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <iostream> #include <algorithm> using namespace std;int a,b,p[1000010 ];inline bool check (int x) { int cnt=0 ,pre=-1500000000 ; for (int i=1 ;i<=a;i++) { if (p[i]-pre>=x){ cnt++; pre=p[i]; } } if (cnt>=b)return true ; else return false ; } int main () { cin>>a>>b; for (int i=1 ;i<=a;i++)cin>>p[i]; sort (p+1 ,p+1 +a); int left=0 ,right=0x7fffffff ; while (right!=left+1 ) { int mid=(left+right)>>1 ; if (check (mid))left=mid; else right=mid; } cout<<left; return 0 ; }
查找效率分析:
关于折半查找判定树:
判定树节点关键字:左<中<右,满足二叉排序树的定义
失败节点:n+1 个(等于成功节点的空链域数量)
分块查找 特点:块内无序,块间有序。
分块查找 ,又称索引顺序查找 ,算法过程如下:
在索引表中确定待查记录所属的分块(可顺序、可折半)
在块内顺序查找
折半查找索引表的例子:
以上是王道书的讲解,是丑陋并且有可能出错的。 但是为了应试,应当了解。如果采用我上面提到的折半查找的方式,查找索引表的方式会完全不同。
效率分析:
拓展思考:
二叉排序树(BST) 定义:
查找:
上面是非递归的实现,下面给出递归版本:
1 2 3 4 5 6 7 8 9 10 11 12 BSTNode* BSTsearch (BSTree T, int key) { if (T==NULL ) return NULL ; if (key==T->key) return T; else if (key < T->key) return BSTsearch (T->lchild, key); else return BSTsearch (T->rchild, key); }
插入新节点:
构造:
删除某一个节点:
先找到目标节点
若被删除节点是叶子节点,则直接删除。不会破坏二叉排序树的性质。
若被删除节点只有一棵左子树或右子树,则让其子树替代之。依然可以保证二叉排序树的性质。
若被删除节点既有左子树,又有右子树。有两种方法:
找到右子树中值最小的节点 p(即右子树中最左下的节点,该节点一定没有左子树),替代将被删除的节点。然后删除原来的节点 p(情况同第 3 步).
找到左子树中值最大的节点 p(即左子树中最右下的节点,该节点一定没有右子树),替代将被删除的节点。然后删除原来的节点 p(情况同第 3 步).
效率分析:
平衡二叉树(AVL) 一些概念:
二叉排序树中插入新节点时如何保持平衡:
调整最小不平衡子树:
续图:
总结:
一个小坑:
练习题:
查找效率分析:
平衡二叉树的删除 平衡二叉树的删除操作:
删除节点后,要保持二叉排序树的性质不变(左 < 中 < 右)
若删除节点导致不平衡,则需要调整平衡
平衡二叉树的删除操作的具体步骤:
删除节点(方法同“二叉排序树”)
一路向上找到最小不平衡子树,若找不到则结束算法
找最小不平衡子树下,“个头”最高的儿子、孙子
根据孙子的位置,调整平衡(LL / RR / LR / RL)
孙子在 LL: 儿子右单旋
孙子在 RR: 儿子左单旋
孙子在 LR: 孙子先左旋,再右旋
孙子再 RL: 孙子先右旋,再左旋
如果不平衡向上传导,转到 2
解释:对最小不平衡子树的旋转可能导致树变矮,从而导致上层祖先不平衡(不平衡向上传导)
在步骤 2 即结束算法的例子:
执行到第 4 步算法结束的例子:
不平衡向上传导一次的例子:
两种选择的例子,可以看到,无论挑选哪个作为“个头”最高的孙子,都可以达到目的:
平衡二叉树的删除操作的时间复杂度是 $O(log_2n)$ .
红 黑树的定义和性质
BST
AVL Tree
Red -Black Tree
生日
1960
1962
1972
查
O(n)
O(log_2^n)
O(log_2^n)
插
O(n)
O(log_2^n)
O(log_2^n)
删
O(n)
O(log_2^n)
O(log_2^n)
红 黑树的优势?
平衡二叉树(AVL)的劣势:插入/删除 操作很容易破坏“平衡”特性,需要频繁调整树的形态。如:插入操作导致不平衡,则需要先计算平衡因子,找到最小不平衡子树(时间开销大),再进行 LL/RR/LR/RL 调整。
相比之下,红 黑树的优势:插入/删除 操作很多时候不会破坏“红 黑”特性,无须频繁调整树的形态。即便需要调整,一般都可以在常数时间内完成。
平衡二叉树,适用于以查找为主,很少插入、删除的场景(实际也很少使用了)。
红 黑树,适用于频繁插入、删除的场景,实用性更强。
红 黑树的定义:
红 黑树是二叉排序树
每个节点或是红 色,或是黑色
根节点是黑色的
叶节点(外部节点、NULL节点、失败节点)都是黑色的
在红 黑树中,当我们提到叶子节点的时候,通常是指失败节点(又称“NULL节点”、“外部节点”)
不存在两个相邻的红 节点(即红节点的父节点和孩子节点都是黑色的)
对每个节点,从该节点到任一叶子节点的简单路径上,所含黑节点的数目相同
粗略地用一个结构体定义一下:
1 2 3 4 5 6 7 struct RBnode { int key; RBnode* parent; RBnode* lchild; RBnode* rchild; int color; };
补充概念,“黑高”:
红 黑树的性质:
从根节点到叶子节点的最长路径不大于最短路径的 2 倍
有 n 个内部节点(n 个关键字)的红 黑树高度 $h\leqslant 2 \log _2(n+1)$
由此得到红 黑树的查找操作的时间复杂度为 $O(\log _2n)$
红 黑树的查找:与 BST、AVL 相同,从根出发,左小右大,若查找到一个空叶子节点,则查找失败。
关于红 黑树的更多内容,由于考纲不考,时间有限,我就放过自己了,下面只给出一些链接:
B 树 一、引入
能否将二叉查找树(BST)拓展为 m 叉查找树?
如何保证查找效率:
二、定义
三、高度
B 树的插入、删除 一、插入
二、删除
续图:
B+ 树 定义:
查找:略。
注意点:在 B+ 树中,叶节点包含信息,所有非叶子节点仅起索引作用。
B+树 和 B树 的一点区别:
B+树的优点和应用场景:
总结:
散列查找 一睹芳容:
查找操作:略。
ASL 分析、装填因子:
设计散列函数的方法(模质数):
其他方法:
处理冲突的另一种方法,开放定址法:
线性探测法(实际没用,考试爱考):
平方探测法:
伪随机序列法:
处理冲突的另另一种方法,再散列法(再哈希法): 除了原始的散列函数 H(key) 之外,多准备几个散列函数。当散列函数冲突时,用下一个散列函数计算一个新地址,直到不冲突为止:
以上总结:
小优化:
排序
插入排序 算法思想:每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中,直到全部记录插入完成。
代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 void insertSort (int A[], int n) { int i, j, temp; for (i=1 ; i<n; i++){ if (A[i]<A[i-1 ]){ temp = A[i]; for (j=i-1 ; j>=0 && A[j]>temp; j--){ A[j+1 ] = A[j]; } A[j+1 ] = temp; } } }
代码实现(带哨兵):
最好时间复杂度:$O(n)$ 最坏时间复杂度:$O(n^2)$ 平均时间复杂度:$O(n^2)$算法稳定性(这里指,排序稳定性):稳定
一个小优化:
注意: 上图中王道的代码是有 bug 的,实际中不能这么写。
补充——对链表进行插入排序: 移动元素的次数变少了,但是关键字对比的次数依然是 $O(n^2)$ 数量级,整体来看时间复杂度依然是 $O(n^2)$ .
希尔排序(Shell Sort) 算法思想来源:
图示:
代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 void shellSort (int A[], int n) { int d, i, j; for (d=n/2 ; d>=1 ; d=d/2 ) for (i=d+1 ; i<=n; i++) if (A[i]<A[i-d]){ A[0 ] = A[i]; for (j=i-d; j>0 && A[0 ]<A[j]; j-=d) A[j+d] = A[j]; A[j+d] = A[0 ]; } }
注意上面代码中,每次让i++
,也就是轮流地切换着来处理不同的几个子表。下图选取几个关键时刻展示:
空间复杂度:$O(1)$ .
时间复杂度:
和增量序列 $d_1,d_2,d_3,\cdots $ 的选择有关
目前 无法用数学手段证明确切的时间复杂度
最坏时间复杂度为 $O(n^2)$ ,如该算法退化为插入排序时
当 n 在某个范围时,可达到 $O(n^{1.3})$ .
希尔排序仅适用于顺序表,不适用于链表。
稳定性:
冒泡排序 若某一趟排序没有发生“交换”,说明此时已经整体有序。
冒泡排序适用于链表。
快速排序 算法思想:
代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 void quickSort (int A[], int low, int high) { if (low<high){ int pivotPos = Partition (A, low, high); quickSort (A, low, pivotPos-1 ); quickSort (A, pivotPos+1 , high); } } int Partition (int A[], int low, int high) { int pivot = A[low]; while (low<high){ while (low<high && A[high]>=pivot) high--; A[low] = A[high]; while (low<high && A[low]<=pivot) low++; A[high] = A[low]; } A[low] = pivot; return low; }
性能分析:
快速排序不稳定。
一个应试的小疑惑:
简单选择排序
简单选择排序既可以用于顺序表,也可以用于链表。
堆排序 前置知识:
大根堆的建立:
建立大根堆的代码: (此处代码的动画演示参见王道视频_大根堆的建立 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 void build_maxHeap (int A[], int len) { for (int i=len/2 ; i>0 ; i--) headAdjust (A, i, len); } void headAdjust (int A[], int k, int len) { A[0 ] = A[k]; for (int i=2 *k; i<=len; i*=2 ){ if (i<len && A[i]<A[i+1 ]) i++; if (A[0 ]>=A[i]) break ; else { A[k] = A[i]; k = i; } } A[k] = A[0 ]; }
基于大根堆进行排序:
基于大根堆进行排序(代码):
1 2 3 4 5 6 7 8 9 10 11 void build_maxHeap (int A[], int len) ;void headAdjust (int A[], int k, int len) ;void heapSort (int A[], int len) { build_maxHeap (A, len); for (int i=len; i>1 ; i--){ swap (A[i], A[1 ]); headAdjust (A, 1 , i-1 ); } }
效率分析:
堆的插入、删除
归并排序
代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 int *B = (int *) malloc (n*sizeof (int )); void merge (int A[], int low, int mid, int high) { int i, j, k; for (k=low; k<=high; k++) B[k] = A[k]; for (i=low,j=mid+1 ,k=i; i<=mid&&j<=high; k++){ if (B[i]<=B[j]) A[k] = B[i++]; else A[k] = B[j++]; } while (i<=mid) A[k++] = B[i++]; while (j<=high) A[k++] = B[j++]; } void mergeSort (int A[], int low, int high) { if (low<high){ int mid = (low+high)/2 ; mergeSort (A, low, mid); mergeSort (A, mid+1 , high); merge (A, low, mid, high); } }
性能分析:
基数排序(Radix Sort)
效率分析:
应用:
完结撒花 外部排序考试不要求掌握,前面的区域,以后再来探索吧:
https://www.bilibili.com/video/BV1b7411N798/?p=96