## 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)
print(a.get())

##### 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
def cdr(x):
return x
def numer(x):
return car(x)
def denom(x):
return cdr(x)
print(numer(cdr(z)))


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

x=[6,9]
def print_rat(x):
print(str(numer(x))+'/'+str(denom(x)))
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
else:
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()
print(str(int(numer(x)/g))+'/'+str(int(denom(x)/g)))
print_rat1(x) [ 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 .

##### Sequence

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:
print(p_node.val)
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)
myList.print_all_node()
# The second node of the list
print(' The list inserts the second node ')
myList.add_node(secondNode)
myList.print_all_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):
print(i)

##### 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
def cdr(z):
return z
if __name__ =='__main__':
a = [1,[2,[3,[4,[5,None]]]]]
node1 = car(a)
print(node1)
next_iter = cdr(a)
node2 = car(next_iter)
print(node2)


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)
else:
return cdr(a,n-1)
# return list The length of
def length_recursive(a):
if a==None:
return 0
else:
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
else:
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
else:
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
else:
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
else:
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
else:
if car(tree)%2==0:
return 0 + tree_iter(cdr(tree))
else:
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
else:
return fib(n-1) + fib(n-2)
def even_fibs(n):
def next_iter(k):
if k>n:
return None
else:
val = fib(k)
if val%2==0:
return [val, next_iter(k+1)]
else:
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

filter

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

https://javamana.com/2021/04/20210408094959511s.html