SCIP: constructing data abstraction -- Explanation of queue and tree in data structure

adminmttt 2021-04-08 09:58:20
scip constructing data abstraction explanation

Now it's the most critical step in mathematical abstraction : Let's forget what these symbols mean . It's not supposed to stop here , There are many operations that can be applied to these symbols , And there's no need to think about what they stand for .
--Hermann Weyi 《 The mathematical way of thinking 》

Construct data abstraction

Now consider a system that does rational arithmetic , Imagine an operation add-rat, Take two rational numbers as parameters , The sum that produces them . Starting from the basic data , A rational number can be regarded as a combination of two integers -- Molecules and denominators , The process can be used add-rat Realization , A molecule that produces sum numbers , Another one produces the denominator of sum numbers , When using this data , There are many rational numbers , The corresponding numerator and denominator appear in pairs , If there are no rules , It's going to make the code harder to read , So I want to consider a method of composite data , Put the data “ Adhesion ” get up .

A key idea in dealing with composite data is the concept of closure -- in other words , The glue used to combine object data can not only be used to combine basic data objects , It can also be used for composite data objects ; Another key idea is that composite objects can be combined program modules in a mixed and matched way .

Data abstraction Guide

1) The basic idea of abstract data , It's trying to build programs that use composite data objects , Make them feel like they're “ Abstract data ” Same as above .

2) A kind of “ Specifically ” The definition of data representation has nothing to do with the way data is used in a program .

[ notes ]   The same idea as object-oriented ,“ Class ”, At the time when the author wrote the book , The concept of object-oriented programming is not mainstream yet , The idea of that era was the method of mathematical logic , Define symbolic variables , And deduce . The idea mentioned above is the properties and methods of classes in object-oriented programming , It's just functional programming .

Rational number

Today we might build a Point class , From the perspective of data and operation , Process oriented is the same as object-oriented .

class RationalNumber(object):
def __init__(self, x, y):
# Ordered pair (x,y) They represent the numerator and denominator respectively
self.x = x
self.y = y
def numer(self):
return self.x
def denom(self):
return self.y
def get(self):
return self.x/self.y
if __name__ =='__main__':
a = RationalNumber(4,5)
The operation of rational numbers

If you design the program from the top to the bottom , Consider three functions
def make_rat(n,d):  Returns a rational number :
def numer(x) Returns a rational number x The molecules of ,def denom(x) Returns a rational number x Denominator of .
The addition, subtraction, multiplication and division of two rational numbers can be written as :

def add_rat(x,y):
   return make_rat(x,y)
def make_rat(x,y):
   return (numer(x)*denom(y) +numer(y)*denom(x))/(denom(x) *denom(y) )

However numer and denom Undefined , If you define an ordered pair ,numer Returns the first position of an ordered pair ( molecular ),denom Returns the second position of the ordered pair ( The denominator ), And then again :

x = [1,2]
y = [3,4]
z = [x,y]
def car(x):
   return x[0]
def cdr(x):
   return x[1]
def numer(x):
   return car(x)
def denom(x):
   return cdr(x)

In the above example def car(x): amount to numer(x),def cdr(x): amount to denom(x).

def print_rat(x):
The output is :6/9, There is no reduction to the simplest form , In order to simplify , Consider the greatest common divisor
def gcd(a,b):
   if b==0:
       return a
       return gcd(b,a%b)
def print_rat1(x):
   g = gcd(denom(x),numer(x))
   # It must be divisible , however python The language automatically casts types , Keep decimal places , In order to look good ->int()

[ notes ]: car and cdr It's the concept of registers Contents of Address part of Register” and “Contents of Decrement part of Register“.

All the rational operations given above , It's all based on constructors make_rat And selection functions numer(x) and denom(x) Defined , The idea of data abstraction is to identify a set of operations for each type of data object , So that all operations on such data objects can be expressed by these operations , And when you add, delete, modify and query these data, you can only use these operations .

( In terms of function ,make_rat A number is disassembled and written as a combination of other functions ,numer(x) and denom(x) These two functions choose the position of the data in the ordered alignment , In computational theory , As long as the functions are the same , It can be regarded as equivalent )

What data means

Rational number x A division that can be written as two integers :

\[\frac{number(x)}{denom(x)}= \frac{n}{d} \]

I mentioned the idea of selecting functions and constructors , Rational number x It is also represented by an ordered pair in the program , stay python And we used that List To achieve :

x = [a,b]

What is implemented by a given constructor and selection function , It is very difficult to formalize this idea strictly . There are two ways to accomplish this formalization .

1) Methods of abstract models , It formalizes as outlined in the rational number example above “ Process plus conditions ” Specification description of , The abstract model method is always based on some defined data object types , Define a new class of data objects .

2) Algebraic norms . This approach will “ The process ” As elements of an abstract algebraic system , The behavior of the system consists of some corresponding to us “ Conditions ” The axiomatic characterization of , And through the abstract algebra technology to check the data object assertion .

Hierarchical data and closure properties

When we construct rational numbers , Order pairs provide a way to construct a basic data structure “ adhesive ”, And when we use it , The first position is defined as the molecule , The second position is the denominator , call numer(x) and denom(x) when , The function is just to extract the data from the corresponding location .( Pay attention to the idea of the pointer )

For example, rational numbers 1/2,car and cdr Take out the elements in the first and second positions respectively

In addition, the further abstraction of ordered pairs mentioned above can also be expressed as :

From today's point of view, it is the concept of pointer , Mark the address , Point to data elements , And the linear table mentioned in the data structure . According to rules , The elements created by a combined order pair are still order pairs , So that's the closure property of the rule -- The results obtained by combining data objects can also be combined by the same operation , Through this nature, we can establish a hierarchical structure .


according to SICP The idea of , When abstracting, consider two important factors :

1) Basic expressions --> Basic representation of data

2) Composition and abstraction of methods --> How to manipulate the data

If you recall the data structure you learned in second grade , The code for writing a linear table is ( Take the addition and traversal in the addition, deletion and modification query as an example ):

class Node(object):
def __init__(self, val):
# Define the current node value
self.val = val
self.next_node = None
class MyList(object):
def __init__(self, node):
# Define the current node value
self.node = node
def add_node(self,node):
self.node.next_node = node
def print_all_node(self):
p_node = self.node
while p_node!=None:
p_node = p_node.next_node
if __name__ =='__main__':
firstNode = Node(1)
secondNode = Node(2)
# The first node of the list
print(' Create a new node and insert the first list ')
myList = MyList(firstNode)
# The second node of the list
print(' The list inserts the second node ')

And if you learn Python Maybe write like this , also python Of List Built in append and pop Methods are used to insert and delete elements

if __name__ =='__main__':
lst = [1, 2, 3]
for i in iter(lst):
SICP Sequences and operations in

stay SICP in , The idea of data combination abstraction , Due to the limitation of language ,python Although it can achieve and Lisp Same function , But this is not recommended :

def car(z):
return z[0]
def cdr(z):
return z[1]
if __name__ =='__main__':
a = [1,[2,[3,[4,[5,None]]]]]
node1 = car(a)
next_iter = cdr(a)
node2 = car(next_iter)

Sequence operation

If it's the second part of the traversal sequence n A place , Suppose the data of the sequence is expressed as a=[1,2,3,4,5], Then return the subscript directly . And if the data of the sequence is expressed as a = [1,[2,[3,[4,[5,None]]]]], You can use the constructed car() and cdr() Ergodic function :

# Back to page n Elements of position ( from 0 Start )
def list_ref(a,n):
if n==0:
return car(n)
return cdr(a,n-1)
# return list The length of
def length_recursive(a):
if a==None:
return 0
return 1 + length(cdr(a))
# return list The length of
def length_iterative(a):
count = 0
def length_iter(a,count):
if a == None:
return count
return length_iter(cdr(a),count+1)
return length_iter(a,count)
#list The joining together of
# a=[1,2,3],b=[4,5]==>c=[1,2,3,4,5]
def list_append(list1,list2):
if list1==None:
return list2
return [car(list1),list_append(cdr(list1),list2)]
#list Of mapping
# a = [1,2,3] ==>f(a)=[2,4,6]
def scale_list(items, factors):
if items==None:
return None
return [car(items)*factors, scale_list(cdr(items),factors)]
#mapping High level abstraction of operations
def map_higher_order(f,items):
if items==None:
return None
return [f(car(items)),map_higher_order(f,cdr(items))]
if __name__ =='__main__':
a = [1,[2,[3,[4,[5,None]]]]]

If we use the idea of data structure to examine :a=[1,2,3,4,5] and a = [1,[2,[3,[4,[5,None]]]]] difference , The former can be understood as a linear table , The latter is the tree :

The general interface definition of a sequence

With the idea of data abstraction to compound data ( Basic expression ), The details of program implementation are masked . With abstract data , We should consider the abstraction of data operation , Now in object-oriented software design , Often mentioned some interface design , Consider the following two procedures :

example: Take a tree as a parameter , Calculate the sum of squares of odd leaf nodes

#f For the higher-order abstraction of functions
def sum_odd_square(f,tree):
    def tree_iter(tree):
        if tree== None:
            return 0
            if car(tree)%2==0:
                return 0 + tree_iter(cdr(tree))
                return f(car(tree)) + tree_iter(cdr(tree))
    return tree_iter(tree)
if __name__ == '__main__':
    tree = [1, [2, [3, [4, [5, [6,None]]]]]]
    print(sum_odd_square(lambda x:x*x,tree))

example: Construct all even Fibonacci Fib(k) A table of , Among them k Less than a given integer n:

def fib(n):
if n==1:
return 1
elif n==0:
return 0
return fib(n-1) + fib(n-2)
def even_fibs(n):
def next_iter(k):
if k>n:
return None
val = fib(k)
if val%2==0:
return [val, next_iter(k+1)]
return next_iter(k+1)
return next_iter(0)

Compare the functions of the two functions

def sum_odd_square(f,tree):

1) Enumerate all the leaves of the tree
2) Filter leaf nodes , Choose the odd number
3) Find the square
4) Sum up

def even_fibs(n):
1) Enumerating integers 0 To n
2) Calculate Fibonacci number
3) Filter results , Take out even numbers
4) Combine the results


def filter(predicate, sequence):
if sequence ==None:
return None
if predicate(car(sequence)):
return [car(sequence), filter(predicate,cdr(sequence))]
return filter(predicate, cdr(sequence))
def f(z):
if z%2==0:
return True
return False

  1. How to realize encryption and decryption of spring boot interface parameters gracefully?
  2. A new way to play in spring 5! This kind of URL request makes me see better!
  3. Can parameters in spring MVC be passed like this? It's up!
  4. Hand in hand to teach you how to develop mybatis plug-ins
  5. Fine spring boot + thymeleaf, there are so many fun details!
  6. Spring boot logs all kinds of posture, it's time to clear!
  7. Web 3.0踏浪而来,分布式存储举足轻重|时空云邀请您参加Web3.0中国峰会暨分布式存储行业大会
  8. spring-aop 进不了切面方法的解决办法
  9. Web 3.0 is coming, distributed storage is very important | spatiotemporal cloud invites you to attend Web3.0 China Summit and distributed storage industry conference
  10. The solution of spring AOP can't enter the section method
  11. Linux中如何启用root用户
  12. How to enable root in Linux
  13. 踩坑 MySQL 索引,看看你真的会用吗?
  14. Hive优化之配置参数的优化(一)
  15. Step on the MySQL index to see if you really know how to use it?
  16. Optimization of configuration parameters for hive optimization (1)
  17. Linux入门教程资料分享
  18. Introduction to Linux
  19. 外部连接mysql docker容器异常
  20. Exception of external connection MySQL docker container
  21. Zookeeper分布式锁?
  22. Zookeeper distributed lock?
  23. 嵌入式Linux_Framebuffer_03点阵显示ASCII字符串
  24. 嵌入式Linux_Framebuffer_02字符编码
  25. Embedded Linux_ Framebuffer_ 03 dot matrix display ascii string
  26. Embedded Linux_ Framebuffer_ 02 character encoding
  27. Looking forward to new product launch of Xiaomi in spring CNMO takes you to see 11 new products in advance
  28. An inventory of the commonly used garbage collectors in Java
  29. Why is it so easy to get started with HBase?
  30. Implementation of PRC framework based on netty
  31. 2021 Java back end engineer must know knowledge - (Dubbo, distributed RPC framework)
  32. 关于spring advisor和元数据 同时来管理事务的问题
  33. How to manage transactions with spring advisor and metadata at the same time
  34. 使用Playwright对Java API实现自动视觉测试 - applitools
  35. Using playwright to implement automatic visual testing for Java API - applitools
  36. Dubbo和Spring cloud、Istio对比图
  37. Comparison of Dubbo with spring cloud and istio
  38. HttpServletRequest、通过request获得请求头、请求体等、解决中文乱码等问题
  39. Mybatis学习笔记-一对一,一对多,多对多关联查询
  40. Mybatis学习笔记-基本概念与操作
  41. HttpServletRequest, obtaining request header and request body through request, solving Chinese garbled code and other problems
  42. Mybatis learning notes - one to one, one to many, many to many association query
  43. Mybatis learning notes - basic concepts and operation
  44. Spring Cloud 升级之路 - 2020.0.x - 3. Undertow 的 accesslog 配置
  45. Spring cloud upgrade road - 2020.0. X - 3. Accesslog configuration of undertow
  46. 被Java培训机构坑骗后,我在这里找回了自信
  47. After being cheated by java training institutions, I found my confidence here
  48. Linux下安装Mysql出现的常见问题以及解决办法
  49. Common problems and solutions of installing MySQL under Linux
  50. java并发编程JUC第十二篇:AtomicInteger原子整型
  51. Java Concurrent Programming JUC Chapter 12: atomicinteger atomic integer
  52. 面经手册 · 第29篇《Spring IOC 特性有哪些,不会读不懂源码!》
  53. Chapter 29 "what are the features of spring IOC? I can't understand the source code! 》
  54. 浅析linux容器--Docker
  55. Analysis of Linux container -- docker
  56. 换种方法学操作系统,轻松入门Linux内核
  57. 浅析linux容器--Docker
  58. Another way to learn operating system, easy access to Linux kernel
  59. Analysis of Linux container -- docker
  60. 手摸手教你阅读和调试大型开源项目 ZooKeeper