【笔记】数据结构_绪论

sphao

【概要】

• 数据结构相关的概念和术语

• 数据结构三要素

• 算法的时间复杂度和空间复杂度

数据结构的基本概念

基本概念和术语

1. 数据

   信息的载体，描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

2. 数据元素

   数据的基本单位，通常作为一个整体考虑处理。由若干数据项（构成数据元素的不可分割的最小单位）组成。

3. 数据对象

   具有相同性质的数据元素的集合，数据的一个子集。

4. 数据类型

   一个值的集合和定义在此集合上一组操作的总称。

5. 抽象数据类型

   ADT 抽象数据类型名{
      数据对象:<数据对象定义>
      数据关系:<数据关系定义>
      基本操作:<基本操作定义>
   }ADT 抽象数据类型名

6. 数据结构

   相互之间存在一种或多种特定关系的数据元素的集合。

   包括三个方面：逻辑结构、存储结构和数据的运算。

数据结构的三要素

1. 逻辑结构

   逻辑结构指数据元素之间的逻辑关系，即从逻辑关系上描述数据，与数据的存储无关。

2. 存储结构

   1）顺序存储

   2）连接存储

   3）索引存储

   4）散列存储

3. 运算

   运算的定义（逻辑结构）和实现（存储结构）。

算法和算法评价

算法的基本概念

算法是对特定问题求解步骤的描述，它是指令的有限序列。

算法的特性：

1. 有穷性

2. 确定性

3. 可行性

4. 输入

5. 输出

算法的目标：

1. 正确性
2. 可读性
3. 健壮性
4. 效率与低存储量需求

算法效率的度量

1. 时间复杂度

   O(1)<O(log n)<O(n)<O(nlog n)<O(n^2)<O(2^n)<O(n!)<O(n^n)

2. 空间复杂度

   原地工作指算法的空间复杂度为O(1)。

sphao

emmm 论坛的markdown怎么插代码啊，我按原来的插入在这显示有bug 啊

[C++] 纯文本查看 复制代码

   ```c++
   ADT 抽象数据类型名{
       数据对象:<数据对象定义>
       数据关系:<数据关系定义>
       基本操作:<基本操作定义>
   }ADT 抽象数据类型名
   ```

---------
把c++去了就好了。。我之后的markdown都得一个个改 有点蛋疼了

Try0oo

楼主这个 系列要写下去吗？

sphao

Try0oo 发表于 2017-10-18 16:51
楼主这个 系列要写下去吗？

写啊，第二篇已经发了

Try0oo

支持支持i