第1章 概论

数据结构

结构的分类

线性结构中的关系r称为线性关系，也称前驱关系。结点集合K中的每个结点在关系r上最多只有一个前驱结点和一个后继结点。线性结构包括数组、链表、栈、队列等。
树形结构，简称树结构或层次结构，其关系r一般称为层次关系。有且仅有一个结点在关系r中没有前驱，称为树根。树形结构包括二叉树、有序树等等。
图结构，也称为网络结构，对结点的前驱和后继数目不做限制。

存储结构

主存特点：空间相邻、随机访问。
常用的存储映射方法：顺序方法、链接方法、索引方法和散列方法。

顺序方法：将一组结点存放在一片地址相邻的存储单元中，也称为紧凑存储结构。
链接方法：指针
索引方法：顺序方法的推广，将索引值映射到结点的存储地址，存储表的每一个元素就是指向相应数据结点的指针，即结点存储单元的开始地址。
散列方法：索引法的延伸和扩展，利用散列函数进行索引值的计算，然后通过索引表求出结点的指针地址。

抽象数据类型ADT

可以用(D, R, P)三元组表示，分别代表对象、关系、基本操作。

算法

性质：通用性、有效性、确定性、有穷性
常见方法：穷举、回溯、分治和递归、贪心和动态规划

算法分析

大O表示法：如果存在正数c和N，使得对任意的 \(n\geq N\)，都有\(f(n)\leq cg(n)\)，则称f(n)在集合O(g(n))中，或简称f(n)是O(g(n))的。
\(c < logn < n < nlogn < n^2 < a^n\)
omega表示法：下限
西塔表示法：上下限相同时

数据结构与算法复习-第一章

原文：https://www.cnblogs.com/winterwinds/p/14992905.html