1.x 绪论知识框架

dddd数据结构课本

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

本章框架

1.ADT、数据类型和数据结构的关系？

数据类型，除了包括数据对象外，还有定义在其上的运算（操作），数据结构也是如此，因此，可以认为，一种数据结构的实现一般都封装成了一个数据类型。
而ADT不关心具体实现和物理存储结构，因此可以说，一个ADT实现之后就是一个数据结构（数据类型）。

2.有些派别认为数据结构不应该包含数据的运算

那么，算法和数据结构就是完全独立的。

但实际上，每个数据结构都包含一些基本的操作，比如增删。C++里的容器几乎都至少有这两种操作。所以，不妨认为，数据结构的三要素：逻辑结构、物理结构和数据的基本操作。这里数据的基本操作就是增删这种简单的运算。如果需要更为复杂的运算，就求助于各种算法，比如排序、快速查找等。

3.关于时间复杂度

4.频度与时间复杂度计算

这是本章唯一的难点，多做题。

5.做题遇到的问题

1.一个数据结构需要考虑存储结构，而ADT不需要考虑存储结构。比如，线性表、栈都是一个ADT，但是链表、顺序表、循环队列、哈希表才算是数据结构。
2.有序表：有序的线性表，不是特指顺序表或者链表
3.循环队列：用顺序表表示的队列