数据结构(DS)

什么是数据结构

数据结构指的是数据在计算机中的组织与存储形式
是表示数据组织, 管理, 储存的形式
可分为两部分:

  • 逻辑形式(ADT)
  • 具体实现

为什么需要数据结构?

  1. 特殊的问题需要特殊的数据结构
  2. 方便对数据进行修改和查找
  3. 在数据量很大时支持快速的访问
  4. 执行特殊的方法

常见的数据结构

  • 数组(Array)
  • 链表(LinkList)
  • 栈(Stack)
  • 队列(Quene)
  • 树(Tree)
  • 图(Graphics)
  • 等等……

抽象数据类型(ADT)

什么是数据抽象数据类型

简单的说就是数据结构的逻辑形式, 不管它的实现
比如数组在Python中长这样:

1
a = [1, 2, 4]

C/C++长这样:
1
int a[3] = {1, 2, 4};

而ADT, 只需要说明a是个数组就可以了, 不需要在乎它是怎么做出来的

为什么需要ADT

-每种程序设计语言都有不同的数据结构实现方法, 使用ADT可以更方便数学计算和描述工作流程-
不用ADT(以C++为例)的栈:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Stack {
    private:
        int top;
        int arr[5];
    public:
        Stack() {
            top = -1;
            for (int i=0; i < 5; i++) {
                arr[i] = 0;
            }
        }
        bool isEmpty() {
            return top == -1 ? true : false;
        }
        bool isFull() {
            return top == 5 ? true : false;
        }
        void push(int val) {
            if (isFull())
                cout << "OVERFLOW" << endl;
            else {
                top++;
                arr[top] = val;
            }
        }
        int pop() {
            if (isEmpty()) {
                cout << "UNDERFLOW" << endl;
                return 0;
            } else {
                int popVal = arr[top];
                arr[top] = 0;
                top--;
                return popVal;
            }
        }
        int count() {
            return top+1;
        }
        int peek(int pos) {
            if(isEmpty()) {
                cout << "UNDERFLOW" << endl;
                return 0;
            } else {
                return arr[pos];
            }
        }
        void change(int pos, int val) {
            arr[pos] = val;
        }
        void display() {
            for (int i=4;i >= 0;i--) {
                cout << arr[i] << endl;
            }
        }
};

TM谁想用这么个东西描述工作流程啊? 我又不一定看得懂C++, 格式若乱一点就不用看了, 根本看不懂
而用了ADT就简单多了, 直接用自然语言告诉你栈的各个属性和功能就好了, So Easy!