数据结构 day06
6. 双向链表6.3. 双向循环链表
用双向循环链表实现约瑟夫环
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
// 定义结构体，一个节点的结构体，一个头尾指针的结构体
typedef struct node
{
datatype data;
struct node *prior;
struct node *next;
}node;
typedef struct double_list
{
struct node *head;
struct node *tail;
}list;
// 主函数
int main()
{
int i = 0; // 计数
int all = 0; // 总人数
int start = 0; // 开始报数的人
int kill = 0; // 死亡数字
node *pdel = NULL; // 用于杀死死者
node *h = NULL; // 指向正在报数的人
node *pnew = NULL: // 指向新创建的人
printf("输入总人数，死亡数字，开始报数的人的编号：");
scanf("%d %d %d", &all, &kill, &start);
// 创建头尾指针
list *p = (list *)malloc(sizeof(list));
if(p == NULL)
{
printf("list malloc err\n");
return -1;
}
// 初始化头尾指针
p->head = NULL;
p->tail = NULL;
// 创建节点
p->head = (node*)malloc(sizeof(node));
if(p->head == NULL)
{
printf("node malloc err\n");
free(p);
return -1;
}
p->tail = p->head;
// 初始化节点
p->head->prior = NULL;
p->head->next = NULL;
p->head->data = 1;
// 循环创建所有的人
for(i = 2; i <= all; i++)
{
pnew = (node*)malloc(sizeof(node));
if(pnew == NULL)
{
printf("pnewnode malloc err!!\n");
return -1;
}
// 初始化pnew
pnew->next = NULL;
pnew->prior = NULL;
pnew->data = i;
// 建立链接
pnew->prior = p->tail;
p->tail->next = pnew;
// 移动尾指针
p->tail = p->tail->next;
}
// 首尾相连
p->tail->next = p->head;
p->head->prior = p->tail;
// h指向开始报数的人
h = p->head;
while(h->data != start)
h = h->next;
// 开始报数，报到死亡数字之后杀人
while(h != h->next)
{
for(i = 1; i <= kill; i++)
{
h = h->next;
}
pdel = h;
h = h->next;
printf("kill %d\n", pdel->data);
// 杀死pdel
pdel->prior->next = pdel->next;
pdel->next->prior = pdel->prior;
free(pdel);
pdel = NULL;
}
printf("Survivor is %d", h->data);
// 释放h
free(h);
h = NULL;
}
7. 树 tree
7.1. 特点
7.1.1. 什么是树
[*]存在一个根节点（root）
[*]其余节点可以分为多少子树
7.1.2. 树的特性
[*]层次关系，一对多，
[*]每个节点最多只有一个前驱，根节点无前驱
[*]每个节点可以有多个后继，叶节点无后继
7.1.3. 关于树的一些术语
[*]度数：节点的子树个数，节点有几个孩子
[*]树度数：整个树中节点最大的度数
[*]叶节点或终端节点，度数为0的节点，最末端的节点
[*]分支节点：度数不为0，有孩子的节点
[*]内部节点：除根节点以外的分支节点
[*]节点层次：根节点到叶节点之间的个数，称为层数，根节点的层数是1
[*]树的深度又叫树的高度：最大的节点层次
7.2. 二叉树
7.2.1. 什么是二叉树
每个节点最多只有两个孩子，分为左孩子和右孩子。由一个根节点和两个互不相交的左子树和右子树组成。二叉树严格区分左右孩子，哪怕只有一个孩子也要分左右。
7.2.2. 二叉树的性质
[*]二叉树第k层上的节点最多有2k-1个
[*]深度为k的二叉树最多有2k-1个节点
[*]叶节点的数量比度数为2的节点的数量多1
盘算
度数为0：n0
总节点数为各类节点之和：n = n0 + n1 + n2
总节点数为所有子节点数加一：n = 1n1 + 2n2 + 1
0 = n2 + 1 - n0
n0 = n2 + 1
7.2.3. 满二叉树和完全二叉树的区别
满二叉树：深度为k时节点为2k-1
完全二叉树：只有最下面两层有度数小于2的节点，最下面一层的叶节点都是左孩子，那么就是完全二叉树
非完全二叉树：两种环境：
[*]除最下面两层外还有别的地方有度数不为2的二叉树
[*]只有最下面两层有度数不为2的二叉树，最下面一层存在右孩子
7.2.4. 二叉树的遍历（画图）
前序：根左右，先找根，再找左孩子
中序：左根右，先找左孩子，再找根，再找右孩子
后序：左右根
https://i-blog.csdnimg.cn/direct/700d3f4b770e44caa0347cdc47e024dd.png#pic_center
每个节点左边画圈，沿着最左边划线，沿线顺序就是前序的遍历顺序
https://i-blog.csdnimg.cn/direct/d7f89ba592a249b6a5d6c66715bbf181.png#pic_center
https://i-blog.csdnimg.cn/direct/0bb2bd0266f34a31af5b04dbc2bb4405.png#pic_center
练习：
已知遍历效果如下，试画出对应的二叉树。
前序： A B C E H F I J D G K
中序： A H E C I F J B D K G
提示：用前序确定根节点，然后用中序找到根节点然后再找左右子。
https://i-blog.csdnimg.cn/direct/484ba5dee56445ce9c7e5cde0795925c.png
7.2.5. 二叉树的顺序存储结构
完全二叉树的节点编号方法为从上到下，从左到右，根节点为1号节点
公式：完全二叉树的节点数为n，某节点编号为i
[*]当 i > 1 （不为根节点）时，有父节点。父节点编号为i/2;
[*]当2i <= n时，有左孩子，其编号为2i， 否则没有左孩子，是叶节点
[*]当 2i <= n 时，有右孩子，其编号为 2i + 1，否则没有右孩子
n个节点可以用n+1个元素的数组顺序存储，节点号和数组下标一一对应，下标为0的位置不用，非完全二叉树虚构节点组成完全二叉树之后存储，会造成空间的浪费
7.2.6. 二叉树的链式存储结构
用链表实现，基于完全二叉树规律创建二叉树，按照完全二叉树的编号方法，从上到下，从左到右
1. 头文件 tree.h
#ifndef __TREE_H__
#define __TREE_H__
typedef struct tree_t
{
int data;
int id;
tree_t* lchild;
tree_t* rchild;
}tree;
// 1. 创建二叉树
tree* CreateBitTree(int n, int i);
// 2. 前序遍历
void PreOrder(tree* p);
// 3. 中序遍历
void InOrder(tree* p);
// 4. 后序遍历
void PostOrder(tree* p);
#endif
[*]创建二叉树，用递归函数创建。
tree* p CreateBitTree(int n, int i) //i根节点的编号，n：节点数
{
// 申请空间存放根节点
tree* p = (tree*)malloc(sizeof(tree));
// 容错判断
if(p == NULL)
{
printf("BitTree malloc err!!\n");
return NULL;
}
// 初始化
p->id = i;
p->data = i;
if(2*i <= n)
p->lchild = CreateBitTree(n, 2*i);
else
p->lchild = NULL;
if(2*i+1 <= n)
p->rchild = CreateBitTree(n, 2*i+1);
else
p->rchild = NULL;
return p;
}
[*]正序遍历二叉树，根左右
void PreOrder(tree* p)
{
if(p == NULL)
return;
// 根节点输出
printf("%-4d", p->data);
// 查看左孩子
if(p->lchild != NULL)
PreOrder(p->lchild);
// 查看右孩子
if(p->rchild != NULL)
PreOrder(p->rchild);
}
[*]中序遍历，左根右
void InOrder(tree* p)
{
if(p == NULL)
return;
if(p->lchild != NULL)
InOrder(p->lchild);
printf("%-4d", p->data);
if(p->rchild != NULL)
InOrder(p->rchild);
}
[*]后序遍历，左右根
void PostOrder(tree* p)
{
if(p->lchild !=NULL)
PostOrder(p->lchild);
if(p->rchild != NULL)
PostOrder(p->rchild);
printf("%-4d", p->data);
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]