数据结构小知识点

待我称王封你为后i 2022-06-08 04:20 210阅读 0赞

![1345165188_5989.jpg][]

![1345165205_1659.jpg][]

1，链表专业术语：

首节点：第一个有效节点

尾节点：最后一个有效节点

头结点：第一个有效节点之前的那个节点，头结点并不存放有效数据，加头结点的目的主要是为了方便对链表的操作

头指针：指向头结点的指针变量

尾指针：指向尾节点的指针变量

2，栈的分类

静态栈：用数组实现

动态栈：用链表实现

3，循环队列（静态队列，数组）的讲解：

1，静态队列为什么是循环队列？

因为循环队列不会浪费内存，如果不是循环的话，因为是静态队列，内存是操作系统分配的，当出栈的时候该出栈的元素不能

及时释放回收，而不能利用，从而造成了浪费

2，循环队列需要几个参数来确定？及其含义讲解

需要两个参数来确定：front队首指针和rear队尾指针

两个参数不同场合的不同含义：

1),  队列初始化：front和rear的值都是0

2),  队列为空：front代表的是队列的第一个元素，rear代表的是队列的最后一个有效元素的下一个元素，一般为NULL

3),  队列空：front和rear的值相等，但不一定是0

3， 循环队列入队伪算法的讲解：

1),将值存入r所代表的位置

2),错误的写法，rear = rear+1

正确的写法，rear = (rear+1)%数组的长度,因为是循环，不能无限增大，会回到原点

4，循环队列出队伪算法讲解：

front = (front +1)%数组的长度

5，如何判断循环队列是否为空

如果front 与 rear 的值相等，则该队列一定为空

6，如何判断循环队列是否为满. 两种方式：

1),多增加一个标识参数，如计算当前队列元素的个数，但是每次增删的时候都需要修改该参数，麻烦

2),少用最后一个元素，如果rear 和 front 紧挨着(不是相等)，则表明队列已满,

( r+1 )%数组长度 == f ? “已满” ： "不满"

递归和循环  
递归：易于理解，速度慢，存储空间大  
循环：不易理解，速度快，存储空间小

树的基本概念：

深度：从根节点到最底层节点的层数称之为深度，根节点是第一层  
叶子节点：没有子节点的节点  
非终端节点：实际就是非叶子节点  
度：子节点的个数称为度  
树的分类  
       一般树：任意一个节点的子节点的个数都不受限制  
       二叉树： 任意一个节点的子节点的个数最多两个，且字节点的个数不可更换  
               分类：  
                    一般二叉树 ：  
                    满二叉树：在不增加树的层数的前提下，无法再多添加一个节点的二叉树就是满二叉树  
                    完全二叉树：如果只是删除了满二叉树最底层最右边的连续若干个节点，这样形成的二          叉树就是完全二叉树。用数组来存储的话，其内部就一定要用完全二叉树，满二叉树是完全二叉树的一个特例  
  
树的存储：  
        二叉树的存储  
                 连续存储\[完全二叉树\]  
                           优点：查找某个节点的父节点和子节点（也包括判断有没有子节点）速度很快，有公式  
                           缺点：耗用内存空间过大，因为非完全二叉树要先转换为完全二叉树先                                    
  
                 链式存储：

一般树的存储：

双亲表示法：求父节点比较方便。

孩子表示法：求子节点比较方便。

双亲孩子表示法：求父节点和子节点都不很方便，但是结构复杂

孩子兄弟表示法，又称二叉树表示法或二叉链表表示法：把一个普通树转化成二叉树来存储。

具体转换方法：设法保证任意一个节点的左指针域指向他的第一个孩子，右指针域指向他的下一个兄弟，只要能满足此条件，就可以把一个普通树转换为一个二叉树，一个普通树转换为二叉树一定没有右子树。

森林的存储：先把森林转换为二叉树，再对二叉树进行存储

[1345165188_5989.jpg]: https://img-my.csdn.net/uploads/201208/17/1345165188_5989.jpg
[1345165205_1659.jpg]: https://img-my.csdn.net/uploads/201208/17/1345165205_1659.jpg