2021年08月01日 课堂笔记

• 树
• 基数排序
• 快速排序和归并排序的非递归实现

哈希

顺序
链式
哈希（散列）
索引（）

前三种用在内存中，索引可以用来内存也可以用在外存中。

HashTable就是使用链接地法解决冲突。

自己写一个HashMap,使用拉链法进行存储。

add(int key,T value);
T get(int key);

代码示例

链地址法实现哈希存储
快速排序非递归实现。

讲解
2G内存，如何对8G大的内容排序

讲解2
从N个有序大的数组中，从这批数组中，找到m个最小的数字。

定义一个长度为m的数组，第0个元素，存放第1个数组的第1个值，第1个元素存放地2个数组的值。

讲解2
判断链表尾环
使用两个指针X,Y，一个X每次走一步，一个Y每次走两步，当两个指针相遇的时候就表示有尾环
求出环的入口：
相遇的时候走一步的指针X不变，每次X走一步，再使用一个指针Z从链表的头开始，每次Z走一步
当
当两者相遇的时候，就是入口点。

web应用赶紧做。
下次讲二叉树的遍历
前序遍历
中序遍历
后续遍历

二叉树的遍历

面试要问

递归方式
非递归方式

概念详解

练习题

非递归遍历实现

前序非递归实现

编程题，实现：八个方法

前序，中序，后序，递归和非递归实现，6
层次遍历，1
判断是否是完全二叉树。1

递归的，使用非递归实现，
使用栈来解决

stack.push(t)
while(栈非空){
t=pop();
打印t.data
if(t.rChirld!=null)
入栈
if(t.lChirld!=null)
入栈
}

方式2 前序：
while(t!=null)
{
打印t.data
pusu(t)
t=t.lchirld
}
while(栈非空){
t=pop()
if(t.rchild!=null){
t=t.rchild;
while(t!=null)
{
打印t.data
pusu(t)
t=t.lchirld
}
}
}

中序：

while(t!=null)
{
//打印t.data
pusu(t)
t=t.lchirld
}
while(栈非空){
t=pop()
打印t.data
if(t.rchild!=null){
t=t.rchild;
while(t!=null)
{
打印t.data
pusu(t)
t=t.lchirld
}
}
}

层次遍历：
（队列实现）

入队(t)
while(队列非空){
t=出队
打印
if(左非空)
入队
if(右非空)
入队
}

判断完全二叉树
（队列实现）