ACSL - 5: Data Structure & Recursive Functions

2019-10-13 Views ACSL 经验2091字9 min read

Data structure

可以先浏览一下这个视频:
Crashcourse Data structure

Data structure

为了避免重复造轮子,关于数据结构的内容可以到这篇文章了解,以下内容皆为对这篇文章的补充。

栈和队列

栈是一种先进后出的数据结构,它有两个指令—— PUSHPOP.
PUSH("A")即把A放在栈顶
POP("A")即把A移出栈顶,并把A赋值给另一个变量

队列和栈很相似,它与栈有相似的指令。唯一不同点是它的值是从底部拿出,而不是从TOP。这就意味着他是先进先出

PUSH("A")
PUSH("M")
PUSH("E")
X = POP()
PUSH("R")
X = POP()
PUSH("I")
X = POP()
X = POP()
X = POP()
X = POP()
PUSH("C")
PUSH("A")
PUSH("N")

考虑以上的代码,如果分别作用于栈和队列,POP的顺序是什么呢?

答案:
栈:E, R, I, M, A and NIL
队列:A, M, E, R, I and NIL

根(root)在树的顶端
子节点(children)父节点(parent node)之下
叶(leaves)树最底下的节点
兄弟节点(siblings)有相同父节点的节点

trees

根据上图我们可以知道,它的根是A。ACSL规定将重复的节点当作小于父节点,如图两个点A。
由于最深的节点位于根之下3个节点,所以树的深度(有时称为高度)为3。根节点的深度为0。
外部节点(external nodes):可以插入新节点的个数。在上面的树中,有9个外部节点;因为有5个位值可以继续加入节点,分别是A,C,I,N(各两个),R(1个)
内部路径长度(internal path length):该树的内部路径长度为15,这是所有节点的深度之和【记住根节点深度为0】。
外部路径长度(external path length):该树外部节点的深度的和,这棵树的外部路径长度为31(4 * 7 + 3)。

既然作为数据结构我们肯定要想方法遍历树的数据,所以就产生了以下的方法【我们以二叉树举例】:

二叉树的遍历方式

先序遍历:先根节点->遍历左子树->遍历右子树
中序遍历:遍历左子树->根节点->遍历右子树
后序遍历:遍历左子树->遍历右子树->根节点

search binary tree

二叉树删除元素

二叉树的构造最核心的提点就是左边元素小于等于右边元素,所以当我们删除其中任何一个节点的时候都要保证不破坏二叉树的这个特性。也正是因为这个特性,当搜索二叉树的时间复杂度是O(log2n)O(\log_2n)

我们可以结合这张图来看一下:
delete nodes in binary tree

删除没有子节点的节点:
delete no-leaf node in binary tree

删除只有一个子节点的节点:
delete node that has one leaf in binary tree

当要删除有左右子节点的树就比较复杂,我们可以看下面这个示例:
delete node that has two children - 1
当我们要删除58这个节点,我们要找到一个比58这个节点大但是小于60的节点,这样可以满足二叉树的条件,所以我们就是要从58节点的右子节点中找到一个最小的数来取代58这个节点:
delete node that has two children - 2

其它

当然,树不知有二叉树这一种。我们还有红黑树红黑树、AVL、替罪羊树、Treap、伸展树等。但是基本的搜索的思想基本是通用的,只不过实现的代码不同罢了。

平衡树(Balance tree):它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

Full and complete binary trees

完美二叉树(Perfect Binary Tree):一个完全且完满的二叉树被称为完美二叉树,即每一个子节点都有两个节点(除去叶节点)且除了最后一层之外的其他每一层都被完全填充。

完全二叉树(Complete Binary Tree):完全二叉树从根结点到倒数第二层满足完美二叉树,最后一层可以不完全填充,其叶子结点都靠左对齐

完满二叉树(Full Binary Tree):除了叶节点,每一个节点都有两个子节点。

优先队列

优先队列是基于这个数据结构建立的,堆的结构非常像二叉树的,它满足以下条件:

  1. 每一个父节点都小于等于它的两个子节点(两个子节点的排放位置不受他们的大小影响)
  2. 它的结构是完全二叉树——每一层都完全覆盖,除了叶节点,并且叶节点要从左到右填充

当要删除根节点时,因为它是最小的数,我们只需要选出一个最大的数,然后遍历堆,找出最小的数把它放在节点即可:

b = bottom-most and right-most element
p = root of tree
p’s key = b’s key
delete b
while (p is larger than either child)
  exchange p with smaller child
  p = smaller child
end while

当最小的数在根节点时,这种堆被称为最小堆

Questions

  1. Consider an initially empty stack. After the following operations are performed, what is the value of Z?
PUSH(3)
PUSH(6)
PUSH(8)
Y = POP()
X = POP()
PUSH(X-Y)
Z = POP()
  1. Create a min-heap with the letters in the word PROGRAMMING. What are the letters in the bottom-most row, from left to right?

  2. Create a binary search tree from the letters in the word PROGRAM. What is the internal path length?

Solutions

  1. The first POP stores 8 in Y. The second POP stores 6 in X. Then, 6-8=-2 is pushed onto the stack. Finally, the last POP removes the -2 and stores it in Z.
  2. The bottom row contains the letters RORN, from left-to-right. Here is the entire heap:
    solution - 2
  3. When drawing the tree, P has a depth of 0, O and R have a depth of 1, G and R have a depth of 2, and A and M have a depth of 3. Therefore, the internal path length is 21 + 22 + 2*3 = 12. Here is the tree:
    solution - 3

Recursive functions

编程语言中,函数Func(Type a,……)直接或间接调用函数本身,则该函数称为递归函数。
比如有这样一个函数:

def Fibonacci(x):
  if x == 1 :
      return 1
  elif x == 2:
      return 1
  else:
      return Fibonacci(x-1) + Fibonacci(x-2)

这个函数会输出斐波那契数列。我们可以看到这个函数在他的内部调用了自己。因为斐波那契数列就是F(n) = F(n-1) + F(n-2),我们利用这个特性就可以利用程序输出任意位置的斐波那契数列的值。

def Factorial(x):
  if x == 0:
      return 1
  return x * Factorial(x-1)

这个是输出阶乘的函数,我们可以看到当 x = 0 or x = 1 的时候结果都为1,然后当 x = 2 输出结果为 2!……

我们可以看到这两个函数都有一个共同特点——他们都有判断语句。这个判断的条件就是递归语句的终止条件,如果没有判断条件,那么递归就会一直运行下去,直到内存溢出。

根据ACSL的官方教程,递归函数不会考察难度太高,如想了解更深层测的递归以及递归在排序算法的运用可以参考这两篇文章
递归与栈
递归排序算法

Question

  1. Find g(11) given the following

g(x)={g(x3)+1if x>03xotherwiseg(x)=\left\{\begin{matrix} g(x-3) + 1 \hspace{1em} if \ x > 0 \\ 3x \hspace{1em} otherwise \end{matrix}\right.

Solution

g(11)= g(8)+1
g(8) = g(5)+1
g(5) = g(2)+1
g(2) = g(-1)+1
g(-1)= -3

We now use what we know about g(−1) to learn more values, working our way back "up" the recursion:
We now know the value of g(2):g(2)=−3+1=−2
We now know the value of g(5):g(5)=−2+1=−1
We now know the value of g(8):g(8)=−1+1=0
And finally, we now have the value of g(11):g(11)=0+1=1

For more questions, look at this website.


注:如果文中有什么问题,欢迎在评论区指出;有不懂的也可以在评论区提问哦!


References:

  1. http://www.categories.acsl.org/wiki/index.php?title=Data_Structures
  2. http://www.categories.acsl.org/wiki/index.php?title=Recursive_Functions
  3. https://blog.csdn.net/yeyazhishang/article/details/82353846
  4. https://blog.csdn.net/wannuoge4766/article/details/83998377
  5. https://www.cnblogs.com/wfaceboss/p/10694736.html
  6. https://blog.csdn.net/mudooo/article/details/100100338

logo   WRITTEN BY:Serence

一个程序员和文艺青年的博客!

本文章采用CC BY-NC-SA 4.0进行许可。转载请注明出处!

上一篇

ACSL - 6: What Does This Program Do? & FSAs and Regular Expressions


下一篇

Crashcourse 计算机科学