数据抽象

第八章、数据抽象

数据结构，潜在主题是抽象的工具的构建

1. 基本数据结构

• 数组和聚合
• 列表、栈和队列
• 树

2. 相关概念

2.1 抽象

• 计算机的主存储器是由一组壳寻址的存储单元顺序组成的，其他的数据结构都必须进行模拟，使用户不必关心实际数据存储的节点

2.2 静态结构与动态结构

考虑数据结构是否会发生改变

2.3 指针

用于记录数据项的存储位置

• 比如在更新移动一个数据的位置，通常通过更新指针的地址
• CPU指令执行的指令指针

3. 数据结构的实现

• 数组（连续的地址）
• 聚合存储（指针）
• 存储列表（链接表、链表）
• 存储栈和队列（Top指针、两个指针）
• 二叉树（数据单元、左指针、右指针）（不用指针的存储的树）

3.1 操控数据结构

• 二分搜索算法（可以通过二叉树来实现）

方法

约定，当列表的一部分为偶数项时，区中间两项例最大的为中间项

1. 将列表的中间项成为根节点
2. 然后把余下的左半部分的中间节点作为左子节点
3. 右半部分的中间节点作为右子节点

二分搜索用于作为炼石二叉树实现的列表

def Search(Tree, TargetValue):
    if (Tree is None):
        return None
    elif (TargetValue == Tree.Value):
        return Tree
    elif (TargetValue < Tree.Value):
        return Search(Tree.Left, TargetValue)
    elif (TargetValue > Tree.Value):
        return Search(Tree.Right, TargetValue)

垃圾回收

• 由于动态数据结构的增大和缩小，存储空间也不断地占用或释放，所以需要回收不用的存储空间
• 否则的话，会导致内存泄露（memory leak）

用于打印二叉树中数据的函数

def PrintTree(Tree):
	if (Tree != None):
        printTree(Tree.Left)
        print(Tree.Value)
        printTree(Tree.Right)

一个用于向二叉树存储的列表中插入新的项的函数

def Inster(Tree, NewValue):
    if (Tree is None):
        Tree = TreeNode()
        Tree.Value = NewValue
    elif (NewValue > Tree.Value):
        Insert(Tree.Right, NewValue)
    elif (NewValue < Tree.Value):
        Insert(Tree.Left, NewValue)
    else:
        print("find Next")
    return Tree

5. 定制的数据类型

为了更好地满足某个具体应用的需求，自定义一些数据类型

• 比如结构体

定义了一个新的聚合

struct {
    char name[25];
    int age;
    float skillRating;
} Employee;

Employee employee1;

没有定义新的聚合

struct EmployeeType {
    char name[25];
    int age;
    float skillRating;
};

struct EmployeeType employee1;

抽象数据类型（ADT）

• 以实现一个堆栈来说明

struct StackType {
    int StackEntries[20];
    int StackPointer = 0;
} Stack;

Stack StackOne, StackTwo, StackThree;

// 我们向隐藏堆栈的使用细节,比如插入push()
// 所以我们需要实现这个方法，缺点在与这个类型并不具有方法的功能
push(int value, Stack stack) {
    if (stack.StackPointer >= 19) {
        printf("stack is full");
        return 
    }
    stack.StackPointer ++;
    StackEntries[stack.StackPointer] = value;
}

在JAVA中

• 我们可以通过接口来实现，或者通过类（面向对象的思维来实现）

interface StackType {
    public int pop();
    public int push();
    public int isempty();
    public int isFull();
}

6. 类和对象

类和对象的概念体现了成勋中数据抽象的表示技术又前进了一大步

7. 机器语言中的指针

• 立即寻址
• 直接寻址
• 间接寻址

最后更新： 2018年07月11日 14:12

原始链接： https://ilifexiao.github.io/2018/06/11/计算机科学概论/第八章、数据抽象/

xiao