买网站做seo,河南中国建设厅官方网站,在线设计平台的缺点,网站建设工作室北京小俊哥文章目录 一、树#xff08;一#xff09;概念1. 前序遍历#xff1a;根左右2. 中序遍历#xff1a;左根右3. 后序遍历#xff1a;左右根4. 层序遍历#xff1a;需要借助队列实现 #xff08;二#xff09;代码实现#xff1a;二叉树1. 结构体定义2. 创建二叉树1. 注意… 文章目录 一、树一概念1. 前序遍历根左右2. 中序遍历左根右3. 后序遍历左右根4. 层序遍历需要借助队列实现 二代码实现二叉树1. 结构体定义2. 创建二叉树1. 注意点2. 代码实现 3. 遍历二叉树1. 注意点2. 代码实现 4. 销毁树1. 注意点2. 代码实现 二、哈希Hash一构造函数保留除数法质数除余法二处理冲突的方法1. 开放地址法2. 链地址法 三使用实例1. 功能需求2. 需求分析3. 代码实现1结构体定义2 一、树
一概念
1. 前序遍历根左右
先遍历根节点 然后遍历左子树 最后遍历右子树 一般用于创建一棵树时因为得先有根节点才能给根节点左右指针分配空间
2. 中序遍历左根右
先遍历左子树 然后遍历根节点 最后遍历右子树 对于一颗有序的二叉树使用中序遍历可以得到一个有序的数列
3. 后序遍历左右根
先遍历左子树 然后遍历右子树 最后遍历根节点 一般用于销毁一棵树时因为需要先释放左右子树才能释放根节点
4. 层序遍历需要借助队列实现
根节点入队列然后出队列前先把要出的节点的左右子树
二代码实现二叉树
1. 结构体定义
typedef struct _Node{char data; //数据域struct _Node *lchild; //左子树struct _Node *rchild; //右子树
}node_t;2. 创建二叉树
1. 注意点
创建二叉树是按照前序的顺序来创建的判断递归是否结束的语句需要放在申请空间之前否则如果申请空间后再执行递归结束会造成内存泄漏
2. 代码实现
int create_tree(node_t **root){if(NULLroot) return -1;char data;printf(请输入节点数据);scanf(%c,data);getchar();//吃垃圾字符if(#data) return 0; //递归的出口*root(node_t *)malloc(sizeof(node_t));if(NULL*root) return -1;(*root)-lchildNULL;(*root)-rchildNULL;(*root)-datadata;//左子树create_tree(((*root)-lchild));//右子树create_tree(((*root)-rchild));return 0;
}3. 遍历二叉树
1. 注意点
遍历二叉树前序、中序、后序的区别仅在于调用函数的顺序前序即先打印根节点再打印左节点最后打印右节点中序则先打印左节点再打印根节点最后打印右节点后序就是先打印左节点再打印右节点最后打印根节点
2. 代码实现
//前序遍历
int preorder(node_t *root){if(NULL root) return -1;printf(%c ,root-data);preorder(root-lchild);preorder(root-rchild);return 0;
}//中序遍历
int inorder(node_t *root){if(NULL root) return -1;inorder(root-lchild);printf(%c ,root-data);inorder(root-rchild);return 0;
}//后序遍历
int postorder(node_t *root){if(NULL root) return -1;postorder(root-lchild);postorder(root-rchild);printf(%c ,root-data);return 0;
}4. 销毁树
1. 注意点
销毁树要按照后续顺序销毁即先销毁左右节点最后再释放根节点
2. 代码实现
int destory_tree(node_t **root){if(NULL root|| NULL*root) return -1;//先销毁左右子树destory_tree(((*root)-lchild));destory_tree(((*root)-lchild));//销毁根节点free(*root);*rootNULL;return 0;
}二、哈希Hash
理想的哈希查找方法对于给定的key值不需任何比较就可以获取记录。 在建立记录表时确定记录的key与其存储地址的关系这个关系就是Hash函数H(key) 下述仅介绍一种常用的方法
一构造函数保留除数法质数除余法
基本思想设一个Hash表空间长度为m取一个不大于m的最大的质数p 公式表达H(key)key%p
二处理冲突的方法
冲突表中某地址中已存放数据但是另一个数据经过Hash函数后得到的地址与该地址相同 选取随机度好的Hash函数可以使冲突减少但是很难完全避免
在处理冲突的过程中可能发生一连串的冲突现象即可能得到一个地址序列H1、H2……HnHi∈[0m-l]。 H1是冲突时选取的下一地址而H1中可能己有记录又设法得到下一地址H2……直到某个Hn不发生冲突为止。这种现象称为“聚积”它严重影响了Hash表的查找效率
1. 开放地址法 如下图46%13707%137但是地址8已有数据使用线性探查法将07存到了地址9 但是这种方法可能会因为处理冲突占用空间而导致冲突产生例如如果此时再存入数据0909%13909本应该存在地址9但是为了解决46和07的冲突占用了地址9的位置而导致冲突产生。还有可能发生聚积。
此外在遍历数据查找有无某元素时无法确定需要遍历多少地址增量才能确定没有该元素.
2. 链地址法
发生冲突时将各冲突记录链在一起 这种方法不会发生聚积现象且容易判断某元素是否存在
三使用实例
1. 功能需求
运用哈希思想实现学生信息录入和查找 存储学生信息以名字首字母为关键字设计哈希函数用链地址法解决哈希冲突
2. 需求分析
需要定义一个学生节点的结构体
3. 代码实现
1结构体定义 2
