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 print(filter(f,a))

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

  1. 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 ...

  2. 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 --- ...

  3. 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 ...

  4. 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 ...

  5. [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 ...

  6. 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 ...

  7. 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 ...

  8. 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 ...

  9. [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 ...

  10. Cautionary tale Structure, structure json data

    Structure, structure json data Talk about the worst code you've ever run into in a project - V2EX

Random recommendation

  1. td All of the style ...

  2. 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 ...

  3. HDU 5067 ( State compression DP+TSP)

    Topic link : 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 ...

  4. 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 ...

  5. 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 ...

  6. 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 ...

  7. 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 ...

  8. 【 turn 】Python metaclass

    from : 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 ...

  9. stay Mac On the use of bootcamp install windows, Use Android studio Solution to the blue screen problem when starting the simulator

    Original link ...

  10. 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 ...