数据结构学习
数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。balabala 这都是概念啦，可能大家都忘了，没关系，反正这次分享跟这个概念也每个鸟关系。
不过能虽然有些概念还是比较坑爹的没用，有些大家还是要关注一下
逻辑结构
集合结构
线性结构
树形结构
图形结构
物理结构
顺序存储结构
链式存储结构
Q1 ：ok 那么大家认为逻辑结构中每个元素的对应关系是什么呢？
Q2：思考一下，顺序存储结构和链式存储结构的区别
数据结构最最最最最基本的东西就这点
那么说数据结构肯定会涉及到算法这个东西
算法的概念我就不跟大家说了，就跟大家说说算法的时间复杂度和空间复杂度吧
默认的我们把算法的时间复杂度 叫做复杂度
时间复杂度，我们用大O阶来表示
现在举一个例子
假如我现在要求设计一个 从0加到n的算法
有两种方法
int sumSilly(int n) {
int sum = 0; //1
for(int i =0; i <= n; ++ i) { //n +1
sum += i //n
}
return sum /1
}
int sumSmart(int n) {
int sum = n * (n + 1) / 2; //1
return sum // 1
}
void main() {
int result1 = sumSilly(100)
int result2 = sumSmart(100)
}
现在我们来计算一下两种方法分辨计算了几次
silly： 1+（n+1）+n +1 = 2n + 3
smart: 1+1 = 2
显而易见的大家都觉得第二种方法比较好，大O阶推到出来的话，一个是O（n） 一个是 O（1），我们一推到大O的时候会把常数的舍去，因为当n无穷大的时候常数对结果的影响就会非常的小。
大家能写一些如：线性阶O(1)，对数阶O(log n),指数阶O(n^m)的算法么
时间复杂度的大小关系，就跟o里面那个大小关系有关(前提n很大)
以下的n为变量，m为常量（n很大）
1 < logn < n < nlogn < n^m < m^n < n! < n^n
扯淡扯完了，下一个
线性表，有两种，顺序表和链表，对应的就是顺序存储和链式存储
可能有些小伙伴表示好奇，静态链表去哪了，静态链表是一个特殊的东西但是也算是链表吧我觉得，长度固定的链表么。我说的长度是最大长度。
链表里面又有循环链表，单链表，双向链表。
那么单链表的定义
typedef struct Node {
ElemType data;
struct Node* next；
} Node，*DuLinkList；
插入p到s之后：
p.next = s.next;
s.next = p;
删除p后面的一个节点s
p.next = s.next
free(s)
Q3：双向链表怎么删除节点p，插入节点p到s后面呢？
双向链表的定义如下
typedef struct DulNode {
ElemType data;
struct DulNode* prior;
struct DulNode* next；
}DulNode，*DuLinkList；
栈和队列
栈
栈这个东西是先入后出的谁都知道吧，那考考大家
如果我入栈1，2，3
那么下面不可能被输出的是哪些
123，213，321，132，231，312
只能在表尾插入和删除，结构定义如下
typedef struct {
SelemType data[MAXSIZE];
int top;
}SqStack;
插入操作
status Push(SqStack *s,SelemType e) {
if (s->top == MAXSIZE -1) {
return error;
}
s->top ++;
s->data[s->top] = e;
return ok;
}
删除操作
status Pop(SqStack *s,SelemType e) {
if (s->top == -1) {
return error;
}
*e = s->data[s->top];
s->top--;
return ok;
}
栈的空间是事先确定好的，如果小了就需要扩充，而且事先申明打了么，又浪费。
大家还记不记得 小时候的三八线。
这个三八线，我们用计算机的思维，就是两栈共享空间，那么我们来看一下定义
typedef struct {
SelemType data[MAXSIZE];
int top1;
int top2;
}SqStack;
插入操作
status Push(SqStack *s,SelemType e,int stacNumber) {
if (s->top1 + 1 == s->top2) {
return error;
}
if (stackNumber == 1){
s->data[++s->top1] = e
} else if (stackNumber == 2) {
s->data[--s->top2] = e
}
return ok;
}
删除操作
status Pop(SqStack *s,SelemType e,int stacNumber) {
if (stackNumber == 1) {
if (s->top1 == -1) {
return error;
}
*e = s->data[s->top1 --];
}
if (stackNumber == 2) {
if (s->top2 == MAXSIZE) {
return error;
}
*e = s->data[s->top2 ++];
}
return ok;
}
栈的应用-----递归，递归就要说
斐波那契数列
如果兔子出生两个月之后可以生育，兔子成熟后每个月可以生一对兔子，假设兔子不会死，求n个月能有几对兔子
第一个月 1
第二个月 1
第三个月 2
第四个月 3
第五个月 5
第六个月 8
这个数列的规律是什么？ 前两项之和等于第三项
int fbi(int i) {
if (i < 2) {
return i ==0 ? 0 : 1;
}
return fbi(i -1) + fbi (i - 2);
}
Q4.汉诺塔最优算法的实现？
var hanoi = function (disc, src, aux, dst) {
if (disc > 0) {
hanoi(disc - 1, src, dst, aux);
document.writeln('Move disc ' + disc + ' from ' + src + ' to ' + dst);
hanoi(disc - 1, aux, src, dst);
}
}
栈的应用----后缀表达式
9 + （3 - 1） * 3 + 10 / 2
答案是多少
·
·
·
·
·
·
·
·
然而我并不想知道算出来的结果，我只是用这个来告诉大家这个后缀表达式咋整
9 3 1 - 3 * 10 2 / +
然后现在来看计算机怎么算的
队列
先入先出嘛。
说说循环队列
typedef struct {
QelemType data[MAXSIZE];
int front;
int rear;
}SqQueue;
队列为空的时候我们定义为
q->front = q->rear;
那么满的时候呢？
(q->rear + 1)%MAXSIZE = q->front
那么入队和出队操作就好搞了
status en(SqQueue *q.QelemType e) {
if ((q->rear + 1)%MAXSIZE == q->front) {
return error;
}
q->data[q->rear] = e;
q->rear = (q->rear + 1) % MAXSIZE;
return ok;
}
status de(SqQueue *q.QelemType e) {
if (q->front == q->rear) {
return error;
}
*e = q->data[q->front];
q->front = (q->front+1)%MAXSIZE
return ok
}
树
二叉树
二叉树有几个性质，不管是考试还是面试都会考到
在二叉树的第i层最多有几个节点
深度为k的二叉树最多有几个节点
具有n个节点的二叉树深度为？【log2n】 + 1
如果一个n个节点的完全二叉树，那么
i=1 这个是跟节点
i>1 那么他的双亲节点是 i/2
2i> n 无左子节点 否则就是左节点
2i+1 >n 无右子节点 否则就是右节点
对于任意一个二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n = n2 +1
二叉树的遍历方法
前序遍历
先访问根节点，后访问左子树，然后右子树
void PreOrderTraverse(BiTree t) {
if (t == null) {
return;
}
printf("%c",t->data);
PreOrderTraverse(t->lchild)
PreOrderTraverse(t->rchild)
}
中序遍历
先访问左子树，然后跟，然后右子树
void InOrderTraverse(BiTree t) {
if (t == null) {
return;
}
InOrderTraverse(t->lchild);
printf("%c",t->data);
InOrderTraverse(t->rchild);
}
后序遍历
先左后右在跟
void PostOrderTraverse(BiTree t) {
if (t == null) {
return;
}
PostOrderTraverse(t->lchild);
PostOrderTraverse(t->rchild);
printf("%c",t->data);
}
层序遍历
跟开始 从左到右
Q5.推导一下，前序遍历是ABCDEF，中序遍历CBAEDF，二叉树是啥
树转换成二叉树
1、加线。兄弟之间加线
2、去线。去掉和除了第一个孩子的线
3、层次调整。自己的孩子就是左孩子，兄弟就是右孩子
森林转二叉树
1、先变成二叉树
2、第一个不变，后面的每个变成前一个的右子树
二叉树转树
倒一下
二叉树转森林
倒过来
霍夫曼树
加权路径最小的二叉树就是霍夫曼树
0-59 5%
60-69 15%
70-79 40%
80-89 30%
90-100 10%
算一下霍夫曼树
霍夫曼编码
BADCADFEED
A27
B8
C15
D15
E30
F5
