基本数据结构介绍了解

超、凢脫俗 2023-03-01 10:48 11阅读 0赞

数据结构:反应数据之间的关系,物理或逻辑上的关系。

有两个角度看数据结构:逻辑结构和存储结构。逻辑结构是指数据之间的逻辑关系,有没有联系。而存储结构才是重点,数据怎么存?存成什么样?有顺序、链式、散列存储等,不过主要研究顺序和链式存储等方式,并对他们的运算进行了解。什么是顺序和链式?其实不难理解,就是容易忘(滑稽)!两者都要从逻辑和存储上看。

顺序结构:逻辑上是连续的,即可以通过任意一节点元素找到该数据元素;存储上,就是物理地址是也是相邻的,连在一块。比如顺序表。

链式结构:逻辑上同理;但是物理存储地址却不是连在一块的。比如线性链表。

那不是还有线性和非线性结构吗?这个是什么角度呢?从数据的存储方式看,分为线性和非线性。线性结构或者叫线性表,指一个数据结构中的每个节点最多有一个前驱或后继(指向作用),则为线性表,可以看作连续线状结构。非空的线性表有以下特征:

  • 只有一个前节点,或头节点,无前件。
  • 只有一个尾节点,无后件
  • 其他节点只有一个前件和后件

那么常见的线性表有这么几个:数组、栈、队列、线性链表;而相应的非线性线性表有树、二叉树、图等等。

常见数据类型介绍:

数组:这个好理解,连续的嘛!一维数组,可以通过下标找到你,而且定义一个数组,在内存上是相邻的一块,非常符合线性表的概念。

栈:特殊一点,操作都在一端进行,这端或这头叫栈顶top,相反,另一端则为栈底bottom。如果为空的话叫空栈,特点就是:FILO(first in ,last out)

栈

  • 先进后出,后进先出
  • 插入删除操作都是在栈顶进行
  • 不像线性表,插入删除操作不需要移动栈内其他元素

插入栈内为入栈或压栈,退出为出栈或退栈,读取就是将栈顶元素读取。

队列:一端插入,另一端退出删除。遵循FIFO,先进先出。那么哪里是头?哪里是尾呢?想象一下一列火车穿过隧道,火车头先进入隧道,然后尾部(Front)后进入。所以原理类似,在队尾(Rear)进行插入,在队头进行删除。

队列

树:非线性的,是可以分支和划分层次的,由n(n>=0)个结点构成,树的结点应该满足以下条件:

  • 只有一个没前驱的节点为根
  • 其余结点可以构成子树
  • 没有子结点的为叶子结点,其余为分支点或内点

一个结点的前件为父结点,后件为孩子结点,有子节点个数多少为度。结点中最大的度为树的度,最大的层数为树的深度。

二叉树:通常由一个结点和左右子树构成,每一个结点最多有两个子结点。

满二叉树:除最后一层外,每一层上的结点都有两个子节点,从第一层开始数到n层,第k层有2的n减一次方个结点,共2的n次方减一个结点。(国内是这么定义的,国外则不是,国外定义为一棵二叉树的结点要么是叶子结点,要么它有两个子结点)

国内:
满二叉树
国外:
国际二叉树

完全二叉树:一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。 也就是说,满二叉树一定是完全二叉树!
完全二叉树

完全二叉树的判定:

C++代码实现(不是本人亲写):

  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. template <class T>
  5. struct TreeNode
  6. {
  7. T data;
  8. TreeNode<T> *left;
  9. TreeNode<T> *right;
  10. TreeNode(const T &x) : data(x),
  11. left(NULL),
  12. right(NULL) {}
  13. };
  14. template <class T>
  15. bool IsComplete(TreeNode<T> *root)
  16. {
  17. //1.树为空,返回错误
  18. if (root == NULL) {
  19. return false;
  20. }
  21. //2.树不为空
  22. queue<TreeNode<T> *> q;
  23. q.push(root);
  24. while (!q.empty()){
  25. TreeNode<T> *top = q.front();
  26. //2.1如果该节点两个孩子都有,则直接pop
  27. if (top->left && top->right) {
  28. q.pop();
  29. q.push(top->left);
  30. q.push(top->right);
  31. }
  32. //2.2如果该节点左孩子为空,右孩子不为空,则一定不是完全二叉树
  33. if (top->left == NULL && top->right {
  34. return false;
  35. }
  36. //2.3如果该节点左孩子不为空,右孩子为空或者该节点为叶子节点,则该节点之后的所有结点都是叶子节点
  37. if ((top->left && top->right == NULL) || (top->left == NULL && top->right == NULL)) {
  38. if (NULL != top->left && NULL == top->right) {
  39. q.push(top->left);
  40. }
  41. q.pop(); //则该节点之后的所有结点都是叶子节点
  42. while (!q.empty()) {
  43. top = q.front();
  44. if (top->left == NULL && top->right == NULL) {
  45. q.pop();
  46. }
  47. else {
  48. return false;
  49. }
  50. }
  51. return true;
  52. }
  53. }
  54. return true;
  55. }
  56. //满二叉树
  57. // 1
  58. // 2 3
  59. // 4 5 6 7
  60. void test1(){
  61. TreeNode<int> *node1 = new TreeNode<int>(1);
  62. TreeNode<int> *node2 = new TreeNode<int>(2);
  63. TreeNode<int> *node3 = new TreeNode<int>(3);
  64. TreeNode<int> *node4 = new TreeNode<int>(4);
  65. TreeNode<int> *node5 = new TreeNode<int>(5);
  66. TreeNode<int> *node6 = new TreeNode<int>(6);
  67. TreeNode<int> *node7 = new TreeNode<int>(7);
  68. node1->left = node2;
  69. node1->right = node3;
  70. node2->left = node4;
  71. node2->right = node5;
  72. node3->left = node6;
  73. node3->right = node7;
  74. cout << IsComplete<int>(node1) << endl;
  75. }
  76. //二叉树为空
  77. void test2(){
  78. cout << IsComplete<int>(NULL) << endl;
  79. }
  80. //3.二叉树不为空,也不是满二叉树,遇到一个结点左孩子为空,右孩子不为空
  81. void test3(){
  82. // 1
  83. // 2 3
  84. // 4 5 7
  85. TreeNode<int> *node1 = new TreeNode<int>(1);
  86. TreeNode<int> *node2 = new TreeNode<int>(2);
  87. TreeNode<int> *node3 = new TreeNode<int>(3);
  88. TreeNode<int> *node4 = new TreeNode<int>(4);
  89. TreeNode<int> *node5 = new TreeNode<int>(5);
  90. TreeNode<int> *node7 = new TreeNode<int>(7);
  91. node1->left = node2;
  92. node1->right = node3;
  93. node2->left = node4;
  94. node2->right = node5;
  95. node3->right = node7;
  96. cout << IsComplete<int>(node1) << endl;
  97. }
  98. //4.二叉树不为空,也不是满二叉树,遇到叶子节点,则该叶子节点之后的所有结点都为叶子节点
  99. void test4(){
  100. // 1
  101. // 2 3
  102. // 4 5
  103. TreeNode<int> *node1 = new TreeNode<int>(1);
  104. TreeNode<int> *node2 = new TreeNode<int>(2);
  105. TreeNode<int> *node3 = new TreeNode<int>(3);
  106. TreeNode<int> *node4 = new TreeNode<int>(4);
  107. TreeNode<int> *node5 = new TreeNode<int>(5);
  108. node1->left = node2;
  109. node1->right = node3;
  110. node2->left = node4;
  111. node2->right = node5;
  112. cout << IsComplete<int>(node1) << endl;
  113. }
  114. //4.二叉树不为空,也不是满二叉树,遇到左孩子不为空,右孩子为空的结点,则该节点之后的所有结点都为叶子节点
  115. void test5(){
  116. // 1
  117. // 2 3
  118. // 4 5 6
  119. TreeNode<int> *node1 = new TreeNode<int>(1);
  120. TreeNode<int> *node2 = new TreeNode<int>(2);
  121. TreeNode<int> *node3 = new TreeNode<int>(3);
  122. TreeNode<int> *node4 = new TreeNode<int>(4);
  123. TreeNode<int> *node5 = new TreeNode<int>(5);
  124. TreeNode<int> *node6 = new TreeNode<int>(6);
  125. node1->left = node2;
  126. node1->right = node3;
  127. node2->left = node4;
  128. node2->right = node5;
  129. node3->left = node6;
  130. cout << IsComplete<int>(node1) << endl;
  131. }
  132. int main(){
  133. test1();
  134. /*test2();*/
  135. /*test3();*/
  136. /*test4();*/
  137. /*test5();*/
  138. return 0;
  139. }

源码连接:https://blog.csdn.net/gogogo\_sky/article/details/76223384

二叉树通常用链式存储,每一个元素则可以有两个后件,分别可以指向左右子结点,其链式结构又叫二叉链表。

二叉树遍历:

二叉树遍历要求不能重复访问结点,常用的有前序遍历、中序遍历、后序遍历。

  • 前序遍历Data Left Right(DLR):先访问根节点,然后遍历左子树,最后遍历右子树
  • 中序遍历Left Data Right(LDR):先遍历左子树,访问根节点,最后遍历右子树
  • 后序遍历Left Right Data(LRD):先遍历左子树,后遍历右子树,最后访问根节点

相应的文章请到博客园二叉树

后序遍历。

  • 前序遍历Data Left Right(DLR):先访问根节点,然后遍历左子树,最后遍历右子树
  • 中序遍历Left Data Right(LDR):先遍历左子树,访问根节点,最后遍历右子树
  • 后序遍历Left Right Data(LRD):先遍历左子树,后遍历右子树,最后访问根节点

相应的文章请到博客园二叉树


个人网站 https://maliaoblog.cn/

发表评论

表情:
评论列表 (有 0 条评论,11人围观)

还没有评论,来说两句吧...

相关阅读