From: 《计算机是怎样跑起来的》【日】矢泽久雄

读书笔记

变量与内存的关系

计算机所处里的数据都存储在了叫内存的 IC 中，内存分割为若干个数据存储单元，每个数据单元可以储存 8 bit（1 字节）的数据，并被分配一个编号，即“地址”。内存的大小为地址的个数。

变量是数据的容器，是程序中数据存储的最小单位，每个变量都对应着物理上的内存空间。
定义变量后，内存上就为该变量预留了一块空间，并以变量名字命名。

离散的变量有局限性，比如处理多个数据排序时，使用离散的变量很麻烦。

了解作为数据结构基础的数组

数组可以存储多个数据，定义数组后操作系统集中分配出一块内存空间，并将空间整体赋予数组名称。

数组可以通过索引访问。

数组反映了内存的物理结构本身，内存中存储数据的空间是连续分布的。

数组的应用

将数组的索引与循环计数器（Loop counter）对应使用，如线性搜索算法和冒泡排序算法。

典型数据结构的类型和概念

数据结构本质上是通过程序从逻辑上改变了内存的物理结构，即数据在内存上呈现出的连续分布状态。

栈（stack）：LIFO（Last in first out，后进先出）
干草堆，数据像干草一样堆起来，取出干草时是从上往下的顺序，即数据使用的顺序与堆积顺序是相反的，最后被存入的数据是最先被处理的。

队列（queue）：FIFO（fist in first out，先进先出）
可以想象购票窗口前买票的乘客，与栈相反，排在队头的乘客最先买到车票。即最先被存入的数据是最先被处理的。当无法一下子处理完数据的时候，就可以暂且先把数据排成队。

链表：
几人手拉手拍成一排，某个人只要松开拉住的那只手，再去拉住另一只手，这一排人的票唉咧顺序就改变了。先松开拉住的手，再让新人加入进来拉住他的手，就完成了数据的插入操作。

二杈树：
一棵树的每次都分为两杈，每个节点相当于一个数据，是链表的特殊形态。

实现栈和队列

  1. 实现栈：Python
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    stack = [] #建立空列表（数组）：元素个数为栈大小
    stackpointer = 0 #栈顶指针：指向栈中最顶端的数据

    def push(data): #入栈函数
        stack[stackpointer] = data #数据存储在栈顶指针所指的位置上
        stackpointer += 1 #更新栈顶指针的值

    def pop(): #出栈函数
        stackpointer -= 1 #更新栈顶指针的值
    return stack[stackpointer] #把数据从栈顶指针的位置中取出来
  2. 实现队列：Python 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    queue = []
    for i in range(100): 
        queue.append() = '' #建立含 100 个元素的空列表
    setindex = 0 #数据存储位置的索引
    getindex = 0 #数据读取位置的索引

    def set(data): #存储函数
        queue[setindex] = data #存入数据
        setindex += 1 #更新标识数据存储位置的索引
        if setindex >= 100: #如果已经达到数组的末尾则折回开头
            setinidex = 0

    def get(): #读取函数
        data = queue[getindex] #读取数据
        getindex += 1 #更新表示数据读取位置的索引
        if getindex >= 100: #如果已达末尾则折回开头
            getindex = 0
    return data
    可以发现，如果数据一直存放到了数组的末尾，下一个存储位置就折回到数组的开头，相当于数组末尾和开头连接上了，即虽然数组的物理结构是直线，但其逻辑结构已经变成圆环了。

了解结构体的组成

  • 定义：结构体是指把若干个数据项汇集到一处并赋予其名字后所形成的整体。
  • 一旦定义完结构体，就可以把结构体当工作室一种数据类型，来定义变量。
  • 被汇集到结构体中的每个数据项都可以被称作结构体的成员（Member）。
    例：一个存储考试成绩的结构体（C，Python 不知道咋写哈哈）
1
2
3
4
5
struct TestResult{
    char Chinese;
    char Math;
    char English;
};

了解链表和二叉树的实现方法

  1. 链表：类似数组，元素手拉手
    • 实现方法:在结构体中添加一个指针类型的变量成员，存储数组中另一个元素的地址，这种结构体称为自我引用的结构体，即引用了与自身相同的数据类型。
      例：将上述结构体改为链表 
      1
      2
      3
      4
      5
      6
      struct Testresult{
          char Chinese;
          char Math;
          char English;
          struct TestResult* Ptr; /*指向其他元素的指针*/
      };
    • 只要更换了 Ptr 值就可以实现不同于内存上的物理排列顺序。
    • 方便之处在于改变数据顺序不需要改变数据在内存上的位置，程序处理时间会缩短。这个特性也适用于对元素进行删除和插入。
  2. 二叉树：同样是自我引用的结构体，只不过改成带有两个连接信息的成员的自我引用结构体。 
    1
    2
    3
    4
    5
    6
    7
    struct Testresult{
            char Chinese;
            char Math;
            char English;
            struct TestResult* Ptr1; /*指向其他元素的指针1*/
            struct TestResult* Ptr2; /*指向其他元素的指针2*/
    };
    • 适用于搜索算法，如“二分查找法”