数据结构--概述

数据结构--概述

什么数据结构

研究非数值计算的程序设计问题中的操作对象, 以及他们之间的关系和操作等相关问题的学科

程序设计 = 数据结构 + 算法

数据结构就是关系, 数据元素相互之间存在的一种或多种特定关系的集合

逻辑结构和物理结构

1. 逻辑结构: 数据对象中数据元素之间的相互关系

2. 物理结构: 数据的逻辑结构在计算机中的存储形式

四大逻辑结构

1. 集合结构: 集结构总的数据元素除了同属于同一个集合外, 他们之间没有其他的关系

2. 线性结构: 线性结构中的数据元素之间是一对一的关系

3. 树形结构: 数据元素之间存在一种一对多的层侧关系

4. 图形结构: 数据元素是多对多的关系

物理结构

研究的就是如何把数据元素存储到计算机的存储器中

分为两种形式: 顺序存储和链式存储

1. 顺序存储结构: 把数据元素存放在地址连续的存储单元里, 其数据建的逻辑关系和物理关系时一致的, 例如数组

2. 链式存储结构: 把元素存放在任意的存储单元里, 这组存储单元可以是连续的, 也可以是不连续的. 这种结构的数据元素存储关系并不鞥呢反应器逻辑关系, 因此需要用一个指针存放数据元素的地址, 这样通脱地址就可以找到相关联数据元素的位置

什么是算法

解决特定问求解步骤的描述, 在计算机中表现为指令的悠闲序列, 并且每条指令标识一个或多个操作

一个问题可以由多个算法解决, 一个算法不可能具有同届所有问题的能力

特性

输入, 输出, 有穷性, 确定性, 可行性

• 输入: 具有零个或多个输入

• 输出至少一个或多个输出

• 有穷性: 算法在执行有限的步骤之后, 自动结束而不会出现无限循环, 并且每一个步骤在可接受的时间内完成

• 确定性: 每一个步骤都具有确定的含义, 不会出现二义性, 在一定调价下, 只有一条执行路径, 相同的输入智能有唯一的输出结果

• 可行性: 每一个步骤都必须是可行的, 也就是说, 每一个步骤都能通过执行有限次数完成

设计的要求

• 正确性:

  • 算法的正确性是指算法至少应该具有输入, 输出和加工处理无歧义性, 能正确反映问题的需求, 能够得到问题的正确答案

  • 大体分为以下四个层次：

    • 算法程序没有语法错误

    • 算法程序对于合法输入能够产生满足要求的输出

    • 算法程序对于非法输入能够产生满足规格的说明

    • 算法程序对于故意刁难的测试输入都有满足要求的 输出结果

• 可读性:

  • 算法设计另一目的是为了便于阅读, 理解和交流

  • 我么写代码的目的, 一方面是为了让计算机执行, 但还有一个重要的目的是为了便于他人阅读和自己日后阅读修改

• 健壮性:

  • 当输入数据不合法时, 算法也能做出相关处理, 而不是产生异常, 崩溃或莫名其妙的结果

• 时间效率高和存储量低

  • 应该具备时间效率高和存储量低的特点. 所以在设计算法的时候我们应该尽量思考这两方面的问题

时间复杂度: 估算程序指令执行的次数(执行时间)

空间复杂度: 估算所需占用的存储空间

大O表示法(Big O)

忽略常数, 系数, 低阶

仅仅是一种粗略的分析模型, 是一种估算, 能帮助我们短时间内了解一个算法的执行效率

常见复杂度

常见复杂度

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)