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) 扩展成为完全二叉树,以一维数组存储。
| 数组下标 |
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) 哈夫曼树
上一页 [1] [2] [3] 下一页
上一篇文章： 考试辅导：程序员数据结构笔记（一）下一篇文章： 考试辅导：程序员数据结构笔记（三） 【
发表评论】【
加入收藏】【
告诉好友】【
打印此文】【
关闭窗口】
