数据结构 day06

6. 双向链表

6.3. 双向循环链表

   用双向循环链表实现约瑟夫环

1. #include <stdio.h>
2. #include <stdlib.h>
3. typedef int datatype;
4. // 定义结构体，一个节点的结构体，一个头尾指针的结构体
5. typedef struct node
6. {
7.         datatype data;
8.         struct node *prior;
9.         struct node *next;
10. }node;
11. typedef struct double_list
12. {
13.         struct node *head;
14.         struct node *tail;
15. }list;
16. // 主函数
17. int main()
18. {
19.         int i = 0;        // 计数
20.         int all = 0;        // 总人数
21.         int start = 0;        // 开始报数的人
22.         int kill = 0;        // 死亡数字
23.         node *pdel = NULL;        // 用于杀死死者
24.         node *h = NULL;        // 指向正在报数的人
25.         node *pnew = NULL:        // 指向新创建的人
26.         printf("输入总人数，死亡数字，开始报数的人的编号：");
27.         scanf("%d %d %d", &all, &kill, &start);
28.         // 创建头尾指针
29.         list *p = (list *)malloc(sizeof(list));
30.         if(p == NULL)
31.         {
32.                 printf("list malloc err\n");
33.                 return -1;
34.         }
35.         // 初始化头尾指针
36.         p->head = NULL;
37.         p->tail = NULL;
38.         // 创建节点
39.         p->head = (node*)malloc(sizeof(node));
40.         if(p->head == NULL)
41.         {
42.                 printf("node malloc err\n");
43.                 free(p);
44.                 return -1;
45.         }
46.         p->tail = p->head;
47.         // 初始化节点
48.         p->head->prior = NULL;
49.         p->head->next = NULL;
50.         p->head->data = 1;
51.         // 循环创建所有的人
52.         for(i = 2; i <= all; i++)
53.         {
54.                 pnew = (node*)malloc(sizeof(node));
55.                 if(pnew == NULL)
56.                 {
57.                         printf("pnewnode malloc err!!\n");
58.                         return -1;
59.                 }
60.                 // 初始化pnew
61.                 pnew->next = NULL;
62.                 pnew->prior = NULL;
63.                 pnew->data = i;
64.                 // 建立链接
65.                 pnew->prior = p->tail;
66.                 p->tail->next = pnew;
67.                 // 移动尾指针
68.                 p->tail = p->tail->next;
69.         }
70.         // 首尾相连
71.         p->tail->next = p->head;
72.         p->head->prior = p->tail;
73.         // h指向开始报数的人
74.         h = p->head;
75.         while(h->data != start)
76.                 h = h->next;
77.         // 开始报数，报到死亡数字之后杀人
78.         while(h != h->next)
79.         {
80.                 for(i = 1; i <= kill; i++)
81.                 {
82.                         h = h->next;
83.                 }
84.                 pdel = h;
85.                 h = h->next;
86.                 printf("kill %d\n", pdel->data);
87.                 // 杀死pdel
88.                 pdel->prior->next = pdel->next;
89.                 pdel->next->prior = pdel->prior;
90.                 free(pdel);
91.                 pdel = NULL;
92.         }
93.         printf("Survivor is %d", h->data);
94.         // 释放h
95.         free(h);
96.         h = NULL;
97. }

复制代码

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. 二叉树的遍历（画图）

前序：根左右，先找根，再找左孩子
中序：左根右，先找左孩子，再找根，再找右孩子
后序：左右根

每个节点左边画圈，沿着最左边划线，沿线顺序就是前序的遍历顺序

   练习：
已知遍历效果如下，试画出对应的二叉树。
前序： A B C E H F I J D G K
中序： A H E C I F J B D K G
提示：用前序确定根节点，然后用中序找到根节点然后再找左右子。

  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

1. #ifndef __TREE_H__
2. #define __TREE_H__
4. typedef struct tree_t
5. {
6.         int data;
7.         int id;
8.         tree_t* lchild;
9.         tree_t* rchild;
10. }tree;
12. // 1. 创建二叉树
13. tree* CreateBitTree(int n, int i);
14. // 2. 前序遍历
15. void PreOrder(tree* p);
16. // 3. 中序遍历
17. void InOrder(tree* p);
18. // 4. 后序遍历
19. void PostOrder(tree* p);
20. #endif

复制代码

   

• 创建二叉树，用递归函数创建。
  

1. tree* p CreateBitTree(int n, int i) //i根节点的编号，n：节点数
2. {
3.         // 申请空间存放根节点
4.         tree* p = (tree*)malloc(sizeof(tree));
5.         // 容错判断
6.         if(p == NULL)
7.         {
8.                 printf("BitTree malloc err!!\n");
9.                 return NULL;
10.         }
11.        
12.         // 初始化
13.         p->id = i;
14.         p->data = i;
15.         if(2*i <= n)
16.                 p->lchild = CreateBitTree(n, 2*i);
17.         else
18.                 p->lchild = NULL;
19.         if(2*i+1 <= n)
20.                 p->rchild = CreateBitTree(n, 2*i+1);
21.         else
22.                 p->rchild = NULL;
23.        
24.         return p;
25. }

复制代码

   

• 正序遍历二叉树，根左右
  

1. void PreOrder(tree* p)
2. {
3.         if(p == NULL)
4.                 return;
5.         // 根节点输出
6.         printf("%-4d", p->data);
7.        
8.         // 查看左孩子
9.         if(p->lchild != NULL)
10.                 PreOrder(p->lchild);
11.        
12.         // 查看右孩子
13.         if(p->rchild != NULL)
14.                 PreOrder(p->rchild);
15. }

复制代码

   

• 中序遍历，左根右
  

1. void InOrder(tree* p)
2. {
3.         if(p == NULL)
4.                 return;
5.         if(p->lchild != NULL)
6.                 InOrder(p->lchild);
7.         printf("%-4d", p->data);
8.         if(p->rchild != NULL)
9.                 InOrder(p->rchild);
10. }

复制代码

   

• 后序遍历，左右根
  

1. void PostOrder(tree* p)
2. {
3.         if(p->lchild !=  NULL)
4.                 PostOrder(p->lchild);
5.         if(p->rchild != NULL)
6.                 PostOrder(p->rchild);
7.         printf("%-4d", p->data);
8. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。