数据结构是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。
通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
人们进行程序设计时通常关注两个重要问题
一是如何将待处理的数据存储到计算机内存中,即数据表示;
二是设计算法操作这些数据,即数据处理。
数据表示的本质是数据结构设计,数据处理的本质是算法设计。
PASCAL之父,瑞士著名计算机科学家沃思(Niklaus Wirth)教授曾提出:算法+数据结构=程序。可以看出数据结构和算法是程序的两个重要组成部分,数据结构是指数据的逻辑结构和存储方法,而算法是指对数据的操作方法。
数据结构 | 优点 | 缺点 |
---|---|---|
数组 | 插入块,如果知道下标,可以非常快的读取 | 查找慢,删除慢,大小固定,只能存储单一元素 |
有序数组 | 比无序数组查询快 | 插入慢,删除慢,大小固定,只能存储单一元素 |
栈 | 提供后进后出的存取方式 | 存取其他项很慢 |
队列 | 提供先进先出的存取方式 | 存取其他项很慢 |
链表 | 插入快,删除慢 | 查找慢 |
二叉树 | 如果树是平衡的,则查找、插入、删除都快 | 删除算法复杂 |
红黑树 | 查找、插入、删除都快。树总是平衡的 | 算法复杂 |
2-3-4 树 | 查找、插入、删除都快。树总是平衡的。类似的树对磁盘存储有效 | 算法复杂 |
哈希表 | 如果关键字已知则存取极快 | 删除慢,如果不知道关键字存取慢,对存储空间使用不充分 |
堆 | 插入、删除快,对最大数据项存取快 | 对其他数据存取慢 |
图 | 对现实世界建模 | 有些算法慢且复杂 |
以上数据结构中,除了数组之外,都可以认为是抽象数据结构(ADT)
正确性:首先,算法应当满足以特定的“规则说明”方式给出的需求。其次,对算法是否“正确”的理解可以 有以下四个层次:
PS:通常以第三层意义的正确性作为衡量一个算法是否合格的标准。
可读性:算法为了人的阅读与交流,其次才是计算机执行。因此算法应该易于人的理解;另一方面,晦涩 难懂的程序易于隐藏较多的错误而难以调试。
健壮性:当输入的数据非法时,算法应当恰当的做出反应或进行相应处理,而不是产生莫名其妙的输出结 果。并且,处理出错的方法不应是中断程序执行,而是应当返回一个表示错误或错误性质的值,以便在更高的抽象 层次上进行处理。
高效率与低存储量需求:通常算法效率值得是算法执行时间;存储量是指算法执行过程中所需要的最大存 储空间,两者都与问题的规模有关。