赫斌老师数据结构视频查缺补漏笔记

赫斌老师数据结构视频查缺补漏笔记

观看学习赫斌老师数据结构的视频，记录下自己之前学习这块内容时似懂非懂的知识，仅针对自己查缺补漏使用
视频链接：《郝斌老师数据结构自学视频》
1.指针的大小
指针类型占用的内存大小是固定的（无论该指针指向哪种数据类型），在 32 位系统中为 4 字节；在 64 位系统中为 8 字节
指针的大小实际上是由CPU的寻址位数决定
2.结构体和类
结构体中只能包含成员的属性，不可以包含行为，所以结构体中不能直接写一个函数进去
3.字符串重新赋值
字符串指针初始化之后不可以改变值，但是字符串数组可以
字符串数组 和 字符串指针 的区别
4.向函数中传递结构体变量
推荐传递变量的地址，快而且不耗内存
5.关于stdio.h
多数与C语言输入输出相关的函数在中定义
6.结构体不可以加减乘除，但是可以互相赋值
7.如果想要跨函数使用内存（跨函数赋值），必须传入变量地址，否则函数运行完之后，函数会被释放，函数中定义的局部变量也会被释放
8.typedef

typedef Struct Student
{
}*PST; // PST等价于 Struct Student * 

typedef Struct Student
{
}*PST, ST; // PST等价于 Struct Student * , ST等价于 Struct Student

9.栈的应用
函数调用，表达式求值，中断，内存分配，缓存，迷宫
10.队列
1）静态队列（数组）一般都是循环队列
如果不是循环队列，已经出队的位置将无法储存数据，对长度有限的数组而言队列长度将越来越小直至为零，无法再储存数据。
2）rear指针指向最后一个有效元素的后一个位置
11.队列的应用
所有和时间有关的 *** 作
12.当一个函数运行期间调用另一个函数时，在运行被调函数之前，系统需要完成三件事：
1）将所有的实际参数，返回地址等信息传递给被调函数保存
2）为被调函数的局部变量（也包括形参）分配存储空间
3）将控制转移到被调函数的入口
13.从被调函数返回主调函数之前，系统也要完成三件事：
1）保存被调函数的返回结果
2）释放被调函数所占的存储空间
3）依照被调函数保存的返回地址将控制转移到调用函数
14.递归和迭代的比较
递归：易于理解，速度慢，存储空间大
迭代：不易于理解，速度快，存储空间小
迭代是逐渐逼近，用新值覆盖旧值，直到满足条件后结束，不保存中间值，空间利用率高。
递归是将一个问题分解为若干相对小一点的问题，遇到递归出口再原路返回，因此必须保存相关的中间值，这些中间值压入栈保存，问题规模较大时会占用大量内存。
15.树的定义
满二叉树：在不增加树的层数的前提下，无法再多添加一个节点的二叉树
完全二叉树：只是删除了满二叉树最底层最右端的连续若干个节点形成的二叉树
16.二叉树的连续存储（完全二叉树）
优点：查找某个节点的父节点和子节点（也包括判断有没有子节点）速度很快
缺点：耗用内存空间过大
17.二叉树表示法
把普通树转化成二叉树储存，转换方法：
左指针域指向它的第一个孩子，右指针域指向他的下一个兄弟
18.森林的存储
把不同的根节点当作兄弟，再用二叉树表示法储存
19.已知两种遍历求二叉树
只有通过先序和中序，或通过中序和后序，才可以唯一确定一个二叉树
1）已知先序和中序
中序判断左右节点（根节点左边是左子树，右边是右子树），先序判断根（先出现的为根）
2）已知后序和中序
中序判断左右节点（根节点左边是左子树，右边是右子树），后序判断根（最后出现的为根）
20.树的应用
1）树是数据库中数据组织的一种重要形式
2） *** 作系统子父进程的关系本身就是一棵树
3）面向对象语言中类的继承关系