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[0]

def cdr(x):

return x[1]
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 :

\]

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[0]

def cdr(z):

return z[1]
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))

## SCIP: Construct data abstraction -- Data structure in the queue and tree to explain more related articles

- Common tree in data structure （BST Binary search tree 、AVL Balanced binary trees 、RBT Red and black trees 、B- Trees 、B+ Trees 、B* Trees ）
Trees The binary search tree : 1. All non leaf nodes have at most two sons (Left and Right): 2. All nodes store a keyword : The left pointer of a non leaf node points to a subtree smaller than its keyword , The right pointer points to a subtree larger than its keyword : Such as : BST Trees ...

- All kinds of trees that are very common in data structures （BST Binary search tree 、AVL Balanced binary trees 、RBT Red and black trees 、B- Trees 、B+ Trees 、B* Trees ）
Common tree in data structure (BST Binary search tree .AVL Balanced binary trees .RBT Red and black trees .B- Trees .B+ Trees .B* Trees ) Binary sort tree . Balance tree . Red and black trees Red and black trees ---- Fourth articles : Step by step, figure one code , Make sure you really understand the red black tree --- ...

- Use JavaScript Array of data structure to achieve the queue and stack
Today we're going to use JavaScript Implement queues and stacks in data structures , Here is a summary . One . A brief introduction to queues and stacks 1.1. The basic concept of queues queue : It's a support for FIFO (FIFO) Set , That is, the data inserted first , Be first ...

- JavaScript Learning summary ( The 21st )—— Use JavaScript Array of data structure to achieve the queue and stack
Today we're going to use JavaScript Implement queues and stacks in data structures , Here is a summary . One . A brief introduction to queues and stacks 1.1. The basic concept of queues queue : It's a support for FIFO (FIFO) Set , That is, the data inserted first , Be first ...

- [Data Structure] All kinds of trees in data structure
There are many tree structures in the data structure , Including binary trees . Binary search tree .2-3 Trees . Red and black trees and so on . This paper summarizes the concepts and uses of several common trees in data structure , Don't be strict and precise , Simple and easy to understand . 1. Binary tree Binary tree is an important part of data structure ...

- Analysis of stack and... In data structure C Realization
I've been working on camera driving recently ,o()︿︶)o alas , Don't mention how annoying it is , A bunch of registers will be accepted -- This is not the development of MCU , This is kernel driver development -- Relax today , Let's look at the stack in the data structure , The knowledge points in this section can be said to be the easiest in data structure ...

- jvm The difference between stack in memory and stack in data structure
1. Common data structures : Stack . queue . Array . Chain list and red black tree ,java Memory division 2.JYM The stack in is FIFO , First in, first execution : 2. The stack in data structure is FIFO , A pistol like clip , The bullet that entered first was fired last : 3. In the data structure ...

- The stack in the data structure is C# In the implementation of
The stack in the data structure is C# In the implementation of One . Study in general Stack is a table oriented data structure , The data in the stack can only be added and deleted in a short time , It's a typical (LIFO) data structure . Understanding in real life : The plates in the cafeteria , People are always from the top ...

- [Oracle] A way to quickly construct large amounts of data
[Oracle] A way to quickly construct large amounts of data : create table tab001(id integer primary key, val varchar2(100)); insert into tab ...

- Cautionary tale Structure, structure json data
Structure, structure json data Talk about the worst code you've ever run into in a project - V2EX https://www.v2ex.com/t/214099

## Random recommendation

- td All of the style
td.style.clear= td.style.posRight=0 td.style.backgroundRepeat= td.style.borderTopStyle= td.style.mar ...

- We can talk ABC
I've been watching Mr. Jiang recently 13 piece < my WCF The journey >, It's over at last , It's very slow , I remember when I first came out to work, the technical director at that time suggested that I go to see , But I just started watching it a few months ago , It took months to see 13 I'm finished . Chapter one WCF My blog is me ...

- HDU 5067 ( State compression DP+TSP)
Topic link : http://acm.hdu.edu.cn/showproblem.php?pid=5067 The main idea of the topic : Lanxiang digs stones . Bring all the stones on the map back to the starting point , It's time consuming to ask . Their thinking : First of all YY Out ...

- HBase Distributed installation
install HBase It needs to be installed before Hadoop, because HBase Is running on the Hadoop On Cluster . install Hadoop You can refer to http://www.cnblogs.com/stGeekpower/p/3307289. ...

- Delphi Of Socket Programming steps
ClientSocket and ServerSocket Several important attributes : 1.client and server There are port attribute , It takes consistency to communicate with each other 2.client Yes Address attribute , Fill in the opposite party when using ...

- Java HashMap The source code parsing
Today we begin to analyze the code of specific collection class , First of all, with both familiar and unfamiliar HashMap Start . Signature (signature) public class HashMap<K,V> extends Abstract ...

- Wookmark-jQuery-master Waterfall flow plug-in
Wookmark-jQuery-master Waterfall flow plug-in use , Including personal tests DEMO requirement You're supposed to know This article requires a basic understanding of Html/CSS, JavaScript/JQuery. development environment Dream ...

- 【 turn 】Python metaclass
from : http://ju.outofmemory.cn/entry/32434 In reply yield Key words and decorator After the question , I understand better , I decided to answer this question in great detail . Warning before reading : This ...

- stay Mac On the use of bootcamp install windows, Use Android studio Solution to the blue screen problem when starting the simulator
Original link https://medium.com/@andrea.bresolin/windows-10-on-mac-with-boot-camp-making-intel-haxm-work-with ...

- new There are three forms of
C++ Language has always been regarded as one of the outstanding representatives of complex programming languages , It's not just the red tape of grammar , And because of its obscure terminology . Here's your old acquaintance —new: It's a memory management operator , Be able to divide an area from the heap , Automatic call construction ...