程序=数据结构+算法

数据结构基本概念

数据、数据元素、数据项、数据对象

数据（Date）

• 是能输入计算机且能被计算机处理的各种符号的集合

• 包括：

• 数值型的数据：整数、实数等

• 非数值型的数据：文字、图像、图形、声音等

数据元素（Date Element）和数据项（Date item）

• 数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理

• 数据项是构成数据元素的不可分割的最小单位

• 三者关系：数据>数据元素>数据项

数据对象（Date Object）

• 是性质相同的数据元素的集合，是数据的一个子集

数据结构

• 数据元素之间的相互关系称为结构

• 数据元素之间的逻辑关系称为逻辑结构

• 数据元素及其关系在计算机内存中的表示（又称为映像），称为数据的物理结构或数据的存储结构

• 数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现

逻辑结构

• 数据元素之间的逻辑关系

• 独立于计算机

物理结构（存储结构）

• 数据元素及其关系在计算机内存中的结构（存储方式）

• 是数据结构在计算机中的表示

逻辑结构的划分

1. 线性结构：有且仅有一个开始和一个终端节点，并且所有节点都最多只有一个直接前趋和一个直接后继。例如（线性表、栈、队列、串）

2. 非线性结构：一个节点可能有多个直接前趋和直接后继（例如：树（一对多）、图（多对多））

划分二

1. 集合结构：结构中的数据元素同属于一个集合

2. 线性结构：结构中的数据元素存在一对一的线性关系

3. 树形结构：结构中的数据元素存在一对多的层次关系

4. 图状结构：结构中的数据元素存在多对多的任意关系

四种基本存储结构

• 顺序存储结构：数组

• 链式存储结构：指针

• 索引存储结构

• 散列存储结构

数据类型和抽象数据类型(Abstract Data Type,ADT)

• 程序中的没每个变量、常量或按和表达式，都有所属的数据类型

• 例如

• 提供int, char, float, double等基本数据类型

• 数组、结构、共用体、枚举等构造数据类型

• 还有指针、空(void)类型

• 用户也可用typedef自己定义数据类型

• 数据类型的作用：约束变量或常量的取值范围，约束变量或常量的操作。

抽象数据类型的形式定义

• 抽象数据类型可用(D,S,P)三元组表示。

• 其中:D是数据对象，S是D上的关系集，P是对D的基本操作集。

• 一个抽象数据类型的定义格式如下:

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

• 数据对象、数据关系的定义用伪代码描述

• 基本操作的定义格式为:

• 基本操作名:参数表

  赋值参数 只为操作提供输入值。

  引用参数 以&打头，除可提供输入值外，还将返回操作结果。

• 初始条件:初始条件描述

  描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之。

• 操作结果:操作结果描述

  说明操作正常完成之后，数据结构的变化状况和应返回的结果。

• 抽象数据类型(ADT)定义举例: Circle的定义

ADT Circle{
   数据对象:D={r,x,y| r,x,y均为实数}
   数据关系:R={<r,x,y>|r是半径,<x,y>是圆心坐标}
   基本操作:
   Circle(&C,r,x,y)
          操作结果:构造一个圆。
   double Area(C)
          初始条件:圆已存在。
          操作结果:计算面积。
   double Circumference(C)
          初始条件:圆已存在。
          操作结果:计算周长。
}ADT Circle

• 抽象数据类型(ADT)定义举例:复数的定义

ADT Complex{
    D = { r1,r2 | r1,r2都是实数}
    S = {<r1,r2>| r1是实部，r2是虚部}
    assign(&C,v1,v2)
          初始条件:空的复数C已存在
          操作结果:构造复数C,r1,r2分别被赋以参数v1,v2的值。
    destroy(&C)
          初始条件:复数C已存在
          操作结果:复数C被销毁。
    Assign(&Z, v1, v2)
          操作结果:构造复数Z，其实部和虚部，分别被赋以参数v1、v2值。
    Destroy(&Z)
          操作结果:复数Z被销毁。
    GetReal(Z,&ealPart)
          初始条件:复数已存在。  
          操作结果:用realPart返回复数Z的实部值。
    Getlmag(Z,&ImagPart )
          初始条件:复数已存在。 
          操作结果:用lmagPart返回复数Z的虚部值。
    Add(z1,z2,&sum )
          初始条件: z1,z2是复数。
          操作结果: sum返回两个复数z1,z2的和。

}ADT Complex

算法

算法的定义

• 对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作。

算法的描述

• 自然语言:英语、中文

• 流程图:传统流程图、NS流程图

• 伪代码：类语言:类C语言

• 程序代码:C语言程序、JAVA语言程序.....

算法特性

• 一个算法必须具备以下五个重要特性

• 有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

• 确定性 算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出

• 可行性 算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

• 输入 一个算法有零个或多个输入。

• 输出 一个算法有一个或多个输出。

算法设计的要求

• 正确性(Correctness)

• 可读性(Readability)

• 健壮性(Robustness)

• 高效性(Efficiency)：要求花费尽量少的时间和尽量低的存储需求

算法和算法分析

• 一个好的算法首先要具备正确性，然后是健壮性，可读性，仕儿个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。

• 算法效率以下两个方面来考虑:

  1．时间效率:指的是算法所耗费的时间;

  2．空间效率:指的是算法执行过程中所耗费的存储空间。

• 时间效率和空间效率有时候是矛盾的。

事前分析方法:

• 一个算法的运行时间是指一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作(如赋值、比较、移动等）所需的时间与算法中进行的简单操作次数乘积。

• 算法运行时间=一个简单操作所需的时间×简单操作次数

• 即算法中每条语句的执行时间之和

• 算法运行时间=求和（每条语句的执行次数×该语句执行一次所需的时间）

基本的数据结构

线性表

基本的数据处理技术

猜猜这是什么：<span class="pwd">Dream主题</span>.html

猜猜这是什么：<span class="pwd">Dream主题</span>

<span style="background:#000; color:#000;" onmouseover="this.style.color='#fff'" onmouseout="this.style.color='#000'">Dream主题</span>

猜猜这是什么：<span class="pwd">Dream主题</span>//////

bash|自定义标题:select
/**
 * 运行程序
 */
|+ java -jar dream.jar

bash|自定义标题:select
/**
 * 运行程序
 */
|+ java -jar dream.jar

\\\bash|自定义标题:select
/**
 * 运行程序
 */
|+ java -jar dream.jar
\\\

\\\bash|自定义标题:select
/**
 * 运行程序
 */
|+ java -jar dream.jar
\\\

\\\bash<suhcaojicshu
/**
 * 运行程序
 */
java -jar dream.jar
\\\

\\\bash<suhcaojicshu
/**
 * 运行程序
 */
java -jar dream.jar
\\\