课程考核
对于课程考核,本课程按照下面划分
| 方式 | 分数 |
|---|---|
| 平时表现 | 20% |
| 作业 | 20% |
| 实验 | 10% |
| 期末考试 | 50% |
绪论
数据结构研究什么?
- 非数值计算问题的操作对象
- 对象之间的关系
- 在计算机中的表示和实现
数据结构的用法
- 通过预先分析问题来确定必须达到的 性能目标
- 挑选出恰当的数据结构
基本概念与术语
数据结构:
- 定义: 由某一数据结构的集合及该集合所有数据元素之间的关系构成
数据结构的逻辑结构:
- 数据的逻辑结构从逻辑关系上描述数据,只指向数据之间的逻辑关系
- 可以看作是从具体问题中抽象出来的数学模型
- 其可以分为: 线性结构,树状结构,图
数据的存储结构
从底层上而言,其储存结构可以分为顺序存储结构与链式存储结构
Note
对于顺序存储结构而言,所有元素存放在一片连续的存储单元(内存),在逻辑上相邻的元素在计算机内存上仍然连续
对于链式存储结构,元素可以存放在不连续的存储单元中,元素之间使用逻辑链接(指针),元素在内存上不一定是连续的
抽象数据模型
数据类型:
- 定义:一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称
- 例如:C语言中有如下数据类型
charintfloatdouble等
- 构造数据类型由 不同成员 构成
- 基本的数据类型可以看作是计算机中已实现的数据类型
抽象数据类型
- 是指一个数学模型以及定义在这个数学模型上的一组操作
- 特性
- 抽象: 通过外部接口访问其功能
- 封装: 将实现细节与外部特性分离
一个简单的实例 三元组
template <typename T1, typename T2, typename T3>
class ppair
{
private:
public:
T1 _first;
T2 _second;
T3 _third;
ppair(const T1 &a, const T2 &b, const T3 &c)
{
_first = a;
_second = b;
_third = c;
}
};算法与算法分析
算法是为了解决某类问题而规定的一个有限长的操作序列,为了度量算法的效率,我们通常使用复杂度来评估
时间复杂度
一个算法的时间复杂度只和其问题的规模有关系,在计算时间复杂度的时候我们通常只关心规模最大的子问题,即对于,是一个多项式,我们只关心幂次最高的项并且忽略常数
例如:
空间复杂度
与时间复杂度类似,空间复杂度也是只关心最大规模子问题所占用的空间规模