转眼又过了一周了，前面一周里面我编了一些程序:链表，长整型数相加，三元组表转置以及一些简单的函数.其实有些算法想想是很简单，不过写起来还是需要一定耐心和C基础的，如果你自己觉得各算法都很懂了，不妨开机编编试试.或许会有一些新的发现与体会.
栈和队列
1、知识点:
栈的定义:操作受限的线性表
特点:后进先出
栈的存储结构:顺序，链接
/push
栈的基本操作:
“pop
栈定义：
struct;
队列定义
特点:先进先出
/入队列in_queue
队列的操作:
“出队列del_queue
队列存储结构:
链队列:
TypedefstructnodeNODE;
TypedefstructQueue;
顺序队列:
struct;
问题:
队列ó线性表
假溢出<=循环队列
队列满，队列空条件一样<=浪费一个存储空间
递归
定义：问题规模为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)线性链表的递归算法一个链表=一个结点+一个链表
intfuction
树与二叉树
一、知识点:
1.树的定义:data_struct;
其中:D中有一个根，把D和出度去掉，可以分成M个部分.
D1，D2，D3，D4，D5…DM
R1，R2，R3，R4，R5…RM
而子树Ri形成树.
1)递归定义高度
2)结点个数=1
O
--0
OO
--1
OOOO
--2
此树的高度为2
2.二叉树定义:
结点个数>=0.
3.术语:左右孩子，双亲，子树，度，高度等概念.
4.二叉树的性质
层次为I的二叉树I层结点2I个
高度为H的二叉树结点2H+1-1个
H=E+1
个数为N的完全二叉树高度为_LOG2n_
完全二叉树结点编号:从上到下，从左到右.
i结点的双亲:_i/2__i-1/2_1i结点的左孩子:2i2i+123i结点的右孩子:2i+12i+245671为起点0为起点
二叉树的存储结构:
1)扩展成为完全二叉树，以一维数组存储。
ABCDEFGHI
数组下标0123456789101112元素ABCDEFGHI
2)双亲表示法
数组下标012345678元素ABCDEFGHI双亲-100122334
3)双亲孩子表示法
数组下标012345…元素ABCDEF…双亲-100122…左子134…右子2-15…
结构:
typedefstructNODE;
NODEtree[N];//生成N个结点的树
4)二叉链表
5)三叉链表
6)哈夫曼树
5.二叉树的遍历
先根“
中根栈中根遍历根，再用相同的方法处理左子树，右子树.
后根/
先，中序已知求树:先序找根，中序找确定左右子树.
层次遍历
6.线索二叉树
中序线索二树树目的:利用空指针直接得到中序遍历的结果.
手段:左指针为空，指向前趋，右指针为空，指向后继.
结点结构:
ltagLchDatarchrtag
Ltag=0，lch指向左孩子，ltag=1，指向前趋结点
Rtag=0，rch指向右孩子;rtag=1，指向后继结点
中序遍历:1)找最左结点
2)当该结点的rtag=1，该结点的rch指向的就为后继
3)当rtag=0，后继元素为右子树中最左边那个
N个结点的二树有空指针N+1个
周六我去了周SIR的办公室，他很热情，我问的是中序线索化二叉树的问题，关于这个问题我会在以后的笔记中作重点补充。我在这学校从来没有碰到过像他这样热情的老师，真的，大一的时候我们学校就开了C，当时我就连#include这句话的意思都不晓得，别说是让我写程序了（到这份上也不怕把丑事都抖出来了:《数据结构》的课程设计也是哈科大的littlebob兄帮我做的，很遗憾，他高程就差几分，希望他早日成功，我们都要向他学习）等于说我的C知识九成都是在大二下学期的时候学的。而且全是自学的。拿这个周末来说吧。我三天时间就看完了一本C语言大全。当然，并不是从头到尾，只是根据自己的实际情况，重点是指针和数据结构那块。C最要的便是指针。程序员考试下午试题最重要的便是递归问题（1～2道，没有掌握就没希望了哦）。我说这些并不是为了表明自己多么用功，只是希望每位"学者"都有所侧重。 |
