程序员数据结构笔记(二)

1） 递推 6!=>5!=>4!=>3!=>2!=>1!=>0!
　　2） 回归 720<=120<=24<=6 <=2 <=1 <=0
　　递归工作栈实现递归的机制。
　　2、有关算法：
　　1） 顺序，链表结构下的出栈，入栈
　　2） 循環，队列的入队列，出队列。
　　3） 链队列的入队列，出队列。
　　4） 表达式计算：后缀表达式 35 6/4368/ *-
　　　　　　　　　　中缀表达式 （3 5）/6-4*（3 6/8）
　　由于中缀比较难处理，计算机内一般先将中缀转换为后缀。
　　运算：碰到操作数，不运算，碰到操符，运算其前两个操作数。
　　　中缀=>后缀
　　5) 迷宫问题
　　6) 线性链表的递归算法 一个链表=一个结点 一个链表
　　int fuction(NODE *p) {
　　　if(p==NULL) return 0;
　　　else return(function(p->next));
　　}
　　树与二叉树
　　一、 知识点:
　　1. 树的定义: data_struct(D,R);
　　其中:D中有一个根,把D和出度去掉,可以分成M个部分.
　　D1,D2,D3,D4,D5…DM
　　R1,R2,R3,R4,R5…RM
　　而子树Ri形成树.
　　1) 递归定义 高度
　　2) 结点个数=1
　　
O --0

O O --1

O O O O --2
此树的高度为2
　　2.二叉树定义:
　　结点个数>=0 .
　　3. 术语:左右孩子,双亲,子树,度,高度等概念.
　　4. 二叉树的性质
　　●层次为I的二叉树 I层结点 2I 个
　　●高度为H的二叉树结点 2H 1-1个
　　●H(点)=E(边) 1
　　●个数为N的完全二叉树高度为|_LOG2n_|
　　●完全二叉树结点编号:从上到下,从左到右.
i结点的双亲: |_i/2_| |_i-1/2_| 1
i结点的左孩子: 2i 2i 1 2 3
i结点的右孩子: 2i 1 2i 2 4 5 6 7
(根) 1为起点 0为起点
　　二叉树的存储结构:
　　　　1) 扩展成为完全二叉树,以一维数组存储。
A
B C
D E F
G H I
数组下标 0 1 2 3 4 5 6 7 8 9 10 11 12
元素 A B C D E F G H 　 　 　 　 I
　　　　2) 双亲表示法
数组下标 0 1 2 3 4 5 6 7 8
元素 A B C D E F G H I
双亲 -1 0 0 1 2 2 3 3 4
　　　　3) 双亲孩子表示法
数组下标 0 1 2 3 4 5 …
元素 A B C D E F …
双亲 -1 0 0 1 2 2 …
左子 1 3 4 　 　 　 …
右子 2 -1 5 　 　 　 …

结构:
　　　　typedef struct {
　　　　　datatype data;
　　　　　int parent;
　　　　　int lchild;
　　　　　int rchild;
　　　　}NODE;
　　　　NODE tree[N]; // 生成N个结点的树
　　　　4) 二叉链表
　　　　5) 三叉链表
　　　　6) 哈夫曼树
　　5.二叉树的遍历
　　　先根 \
　　　中根 栈 中根遍历(左子树)根(右子树),再用相同的方法处理左子树,右子树.
　　　后根 /
　　　先,中序已知求树:先序找根,中序找确定左右子树.
　　　层次遍历(队列实现)
　　6.线索二叉树(穿线树)
　　　中序线索二树树目的:利用空指针直接得到中序遍历的结果.
　　　手段(方法):左指针为空,指向前趋,右指针为空,指向后继.
　　结点结构:
ltag Lch Data rch rtag
　　Ltag=0,lch指向左孩子,ltag=1,指向前趋结点
　　Rtag=0,rch指向右孩子;rtag=1,指向后继结点
　　中序遍历: 1) 找最左结点(其左指针为空)
　　　　2) 当该结点的rtag=1,该结点的rch指向的就为后继
　　　　3) 当rtag=0,后继元素为右子树中最左边那个
　　N个结点的二树有空指针N 1个
　　排序查找是笔者觉得最头疼的算法了,常搞混去的啊.不知道各位学得如何,如果不错,还请告诉我一些经验!
查找
一、 知识点　　　　/静态查找->数组　　
　　1、 什么是查找
　　　　　　　　　　\动态查找->链树
　　●顺序查找，时 间复杂度 O(n)
　　●折半查找：条件：有序；时 间复杂度 O(nlog2n) (时 间复杂度实际上是查找树的高度)
　　●索引查找：条件：第I 1块的所有元素都大于第Ｉ块的所有元素。
　　　算法：根据index来确定X所在的块（i） 时 间复杂度：m/2　　　　
　　　　　　在第Ｉ块里顺序查找X　　　　 　时 间复杂度：n/2
　　　总的时 间复杂度：(m n)/2
　　●二叉排序树　1）定义：左子树键值大于根节点键值；右子树键值小于根的键值，其左右子树均为二叉排序树。　
　　　　　　　　　2）特点：中序遍历有序->（删除节点用到此性质）
　　　　　　　　　3）二叉排序树的查找：如果根大于要查找的树，则前左子树前进，如果根小于要查找的树，则向右子树前进。
　　　　　　　　　4）结点的插入->二叉排序树的构造方法
　　　　　　　　　5）结点删除（难点）　 1、右子树放在左子树的最右边
　　　　　　　　　　　　　　　　　　　　2、左子树放在右子树的最左边

●avl树（二叉平衡树）：左右子树高度只能差１层，即｜h｜<=1其子树也一样。
　　●B树：n阶B树满足以下条件　1）每个结点（除根外）包含有N～2N个关链字。　　　　　　　　　　　　　　　　2）所有叶子节点都在同一层。
　　　　　　　　　　　　　　　　3）B树的所有子树也是一棵B树。
　　　特点：降低层次数，减少比较次数。
排序
一、知识点
　　1、排序的定义
　　　　　　　　　/内排序：只在内存中进行
　　2、排序的分类
　　　　　　　　　\外排序：与内外存进行排序　
　　　内排序：　　　/直接插入排序
　　　　1）插入排序
　　　　　　　　　　\shell排序
　　　　　　　　　　/冒泡排序
　　　　2）交换排序　
　　　　　　　　　　\快速排序
　　　　　　　　　　　/简单选择排序
　　　　3）选择排序 堆
　　　　　　　　　　　\ 锦标赛排序
　　　　4）归并排序（二路）
　　　　5）基数排序（多关链字排序）
　　3、时 间复杂度（上午题目常考，不会求也得记住啊兄弟姐妹们！）
　　　　　　　　　* * * * * * 15 * * * 15 * * *
　　　　/稳定　　 * * * * * * * * 15 15 * * * *(前后不变)　
　　排序　　
　　　　\ 不稳定　* * * * * * * * 15 15 * * * *(前后改变)
　　经整理得:选择、希尔、堆、快速排序是不稳定的；直接插入、冒泡、合并排序是稳定的。


　●锦标赛排序方法：　13　　16　　11　　18　　21　　3　　17　　6
　　　　　　　　　　　　 \　　/　　　\　　/　　　\　 /　　　 \　/
　　　　　　　　　　　　　 13　　　　　11　　　　　3　　　　　 6
　　　　　　　　　　　　　　\　　　　　/　　　　　　\　　　　 /
　　　　　　　　　　　　　　　　　11　　　　　　　　　　　3
　　　　　　　　　　　　　　　　　 \　　　　　　　　　　 /
　　　　　　　　　　　 　　　　　　　　　　　　3（胜出，将其拿出，并令其为正无穷&Go On）
　　●归并排序方法：　　13　　16　　11　　18　　21　　3　　17　　6
　　　　　　　　　　　　 \　　/　　　\　　/　　　\　 /　　　\　 /
　　　　　　　　　　　　　13,16　　　 11,18　　　 3,21　　　 6,17
　　　　　　　　　　　　　　\　　　　　/　　　　　　\　　　　 /
　　　　　　　　　　　　　　11,13,16,18　　　　　　　3,6,17,21
　　　　　　　　　　　　　　　　　\　　　　　　　　　　 /
　　　　　　　　　　　　　　　　　 3,6,11,13,16,17,18,21
　　●shell排序算法：1）定义一个步长（或者说增量）数组D[m]；其中：D[m-1]=1(最后一个增量必须为1，否则可能不完全)
　　　　　　　　　2）共排m趟，其中第i趟增量为D[i],把整个序列分成D[i]个子序列，分别对这D[i]个子序列进行直接插入排序。
　　　　　　 　　程序如下： for(i=0;i<m;i )
　　　　　　　　　　　　　　{for(j=0;j<d[i];j )
　　　　　　　　　　　　　　　{对第i个子序列进行直接插入排序；　
　　　　　　　　　　　　　　　　　　注意：下标之差为D[i];
　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　}
　　●快速排序　( smaller )data ( bigger )
　　　d[]　i->　13　16　11　18　21　3　17　6　24　8　<-j
　　　先从后往前找，再从前往后找。　
　　　思想：空一个插入一个，i空j挪，j空i挪（这里的i,j是指i,j两指针所指的下标）。
　　　一次执行算法：1）令temp=d[0](枢纽)，i=0,j=n-1;
　　 　　　　　　　 2）奇数次时从j位置出发向前找第一个比temp小的元素，找到后放到i的位置(d[i]=d[j];i ;) i往后挪。
　　　　　　　　　　3）偶数次时从i开始往后找第一个比temp大的数，（d[j]=d[i];j--;)
　　　　　　　　　　4）当i=j时，结束循环。d[i]=temp；
　　再用递归对左右进行快速排序，因为快速排序是一个典型的递归算法。
　　●堆排序　
　　　　定义：d[n]满足条件：d[i]<d[2i 1]&&d[i]<d[2i 2] 大堆（上大下小）
　　　　　　　　　　　　　　d[i]>d[2i 1]&&d[i]>d[2i 2] 小堆（上小下大）
　　　　判断是否为堆应该将其转换成树的形式。总共排序n-1次
　　调整(重点)
　　　程序: flag=0;
　　　　　　while(i<=n-1) {
　　　　　　　if(d[i]<d[2*i 1])||(d[i]<d[2*i 2]))
　　　　　　　{ if(d[2*i 1]>d[2*i 2]) 8 24 {d[i]<->d[2*i 1]; 24 21 -> 8 21
　　　　　　　　i=2*i 1;
　　　　　　　　else {
　　　　　　　　　d[i]<->d[2*i 2];
　　　　　　　　　i=2*i 2;
　　　　　　　　}
　　　　　　　}
　　　　　　　else
　　　　　　　　flag=1; //是堆

}
　　堆排序过程：
　　●基数排序(多关键字排序)
　　扑克: 1) 大小->分配
　　　　　2) 花色->分配,收集
　　思想:分配再收集.
　　构建链表:链表个数根据关键字取值个数有关.
　　例:将下面九个三位数排序:
　　　　321 214 665 102 874 699 210 333 600
　　　定义一个有十个元素的数组:
　　　　　　　　　　a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
　　　第一趟(个位): 210　321　102　333　214　665　　　　　　　　 699
　　　　　　　　　　600　　　　　　　　 874
　　　　　　　结果: 210　600　321　102　333　214　874　665　699
　　　第二趟(十位): 600　210　321　　　 333　　　 665　874　　　 699
　　　　　　　　　　102　214
　　　　　　　结果: 600　102　210　214　321　333　665　874　699
　　　第三趟(百位): 102　210　321　　　　　　600　　　 874
　　　　　　　　　　　　 214　333　　　　　　665
　　　　　　　　　　　　　　　　　　　　　　 699
　　　　　　　结果: 102　210　214　321　333　600　665　699　874(排序成功)
八大类算法
　　程序员考试下午试题最后一道一般是八大类算法里头的.大家尤其要注意的是递归，因为近几年都考了，而且有的还考两题。可以说如果我们不掌握递归就没有掌握C，况且递归是C里的难点。为了控制合格率，程序员考试不会让我们轻松过关的，为了中国软件业，我想也应该这样啊。
　　　　/数据结构(离散)
　　迭代
　　　　\数值计算(连续)
　　枚举 策略好坏很重要
递推
　　递归
　　回溯
　　分治
　　贪婪
　　动态规划
　　其中：递推、递归、分治、动态规划四种算法思想基本相似。都是把大问题变成小问题，但技术上有差别。
枚举:
　　背包问题:
　　枚举策略：1)可能的方案：2N
　　　　　　　2)对每一方案进行判断.
　　枚举法一般流程：
　　　　while(还有其他可能方案)
　　　　{ 按某种顺序可难方案;
　　　　　检验方案;
　　　　　if(方案为解)
　　　　　　保存方案;
　　　　　}
　　　　}
　　枚举策略:
　　例：把所有排列枚举出来 P6=6!.
　　　Min:123456
　　　Max:654321
　　　a1a2a3a4a5a6=>?(下一排列)=>?
　　　比如:312654的下和种情况=>314256
递归
　　递归算法通常具有这样的特征：为求解规模为N的问题，设法将它分解成一些规模较小的问题，然后从这些较小问题的解能方便地构造出题目所需的解。而这些规模较小的问题也采用同样的方法分解成规模更小的问题，通过规模更小的问题构造出规模校小的问题的解，如此不断的反复分解和综合，总能分解到最简单的能直接得到解的情况。
　　因此,在解递归算法的题目时,要注意以下几点:
　　1) 找到递归调用的结束条件或继续递归调用条件.
　　2) 想方设法将处理对象的规模缩小或元素减少.
　　3) 由于递归调用可理解为并列同名函数的多次调用,而函数调用的原则是一层一层调用,一层一层返回.因此,还要注意理解调用返回后的下一个语句的作用.在一些简单的递归算法中,往往不需要考虑递调用返回后的语句处理.而在一些复杂的递归算法中,则需要考虑递归调用返回后的语句处理和进一步的递归调用.
　　4) 在读递归程序或编写递归程序时,必须要牢记递归函数的作用,这样便于理解整个函数的功能和知道哪儿需要写上递归调用语句.当然,在解递归算法的题目时,也需要分清递归函数中的内部变量和外部变量.
　　表现形式:
　　●定义是递归的(二叉树,二叉排序树)
　　●存储结构是递归的(二叉树,链表,数组)
　　●由前两种形式得出的算法是递归的
　　一般流程: function(variable list(规模为N))
　　　{ if(规模小,解已知) return 解;
　　　　else {
　　　　　把问题分成若干个部分;
　　　　　某些部分可直接得到解;
　　　　　而另一部分(规模为N-1)的解递归得到;
　　　　}
　　}
　　例1：求一个链表里的最大元素.
　　大家有没想过这个问题用递归来做呢?
　　非递归方法大家应该都会哦?
　　　　Max(nodetype *h) {
　　　　　nodetype *p;
　　　　　nodetype *q; //存放含最大值的结点
　　　　　Int max=0;
　　　　　P=h;
　　　　　While(p!=NULL){
　　　　　　if (max<p->data) {
　　　　　　　max=p->data;
　　　　　　　q=p;
　　　　　　}
　　　　　　p=p->next;
　　　　　}
　　　　　return q;
　　　　}
　　下面真经来了,嘻嘻嘻~~~
　　　　*max(nodetype *h) {
　　　　　nodetype *temp;
　　　　　temp=max(h->next);
　　　　　if(h->data>temp->data)
　　　　　　return h;
　　　　　else
　　　　　　return temp;
　　　　}

1） 递推 6!=>5!=>4!=>3!=>2!=>1!=>0!
　　2） 回归 720<=120<=24<=6 <=2 <=1 <=0
　　递归工作栈实现递归的机制。
　　2、有关算法：
　　1） 顺序，链表结构下的出栈，入栈
　　2） 循環，队列的入队列，出队列。
　　3） 链队列的入队列，出队列。
　　4） 表达式计算：后缀表达式 35 6/4368/ *-
　　　　　　　　　　中缀表达式 （3 5）/6-4*（3 6/8）
　　由于中缀比较难处理，计算机内一般先将中缀转换为后缀。
　　运算：碰到操作数，不运算，碰到操符，运算其前两个操作数。
　　　中缀=>后缀
　　5) 迷宫问题
　　6) 线性链表的递归算法 一个链表=一个结点 一个链表
　　int fuction(NODE *p) {
　　　if(p==NULL) return 0;
　　　else return(function(p->next));
　　}
　　树与二叉树
　　一、 知识点:
　　1. 树的定义: data_struct(D,R);
　　其中:D中有一个根,把D和出度去掉,可以分成M个部分.
　　D1,D2,D3,D4,D5…DM
　　R1,R2,R3,R4,R5…RM
　　而子树Ri形成树.
　　1) 递归定义 高度
　　2) 结点个数=1
　　
O --0

O O --1

O O O O --2
此树的高度为2
　　2.二叉树定义:
　　结点个数>=0 .
　　3. 术语:左右孩子,双亲,子树,度,高度等概念.
　　4. 二叉树的性质
　　●层次为I的二叉树 I层结点 2I 个
　　●高度为H的二叉树结点 2H 1-1个
　　●H(点)=E(边) 1
　　●个数为N的完全二叉树高度为|_LOG2n_|
　　●完全二叉树结点编号:从上到下,从左到右.
i结点的双亲: |_i/2_| |_i-1/2_| 1
i结点的左孩子: 2i 2i 1 2 3
i结点的右孩子: 2i 1 2i 2 4 5 6 7
(根) 1为起点 0为起点
　　二叉树的存储结构:
　　　　1) 扩展成为完全二叉树,以一维数组存储。
A
B C
D E F
G H I
数组下标 0 1 2 3 4 5 6 7 8 9 10 11 12
元素 A B C D E F G H 　 　 　 　 I
　　　　2) 双亲表示法
数组下标 0 1 2 3 4 5 6 7 8
元素 A B C D E F G H I
双亲 -1 0 0 1 2 2 3 3 4
　　　　3) 双亲孩子表示法
数组下标 0 1 2 3 4 5 …
元素 A B C D E F …
双亲 -1 0 0 1 2 2 …
左子 1 3 4 　 　 　 …
右子 2 -1 5 　 　 　 …