软考指南：程序员数据结构笔记2
添加时间: 2007-4-9 1:34:59 作者: 程序员认证参考 阅读次数:70 来源: http://www.d9soft.com
递归
定义：问题规模为N的解依赖于小规模问题的解。问题的求解通过小规模问题的解得到。
包括二个步骤：
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
上一篇文章: 软考指南：程序员数据结构笔记1 下一篇文章: 软考指南：程序员数据结构笔记3
相关软件: