数据结构

1.数据

• 数值型
  • 1 2 3
• 非数值型
  • 文字，图像， 图形

2.数据元素和数据项

• 数据元素

  • 组成数据的基本单位就是数据元素

    • 例如

      学号	姓名	性别	出生日期	政治面貌
      0001	张三	男	20020514	团员
      0002	李四	男	20030604	团员
      0003	王五	男	20040507	团员

      每一行就是一个数据元素，或者称为记录，节点或顶点

• 数据项

  • 组成数据元素的不可分割的最小单位
    • 例如上面的表中每一列就是一个数据项

• 数据 >数据元素>数据项

  • 学生表>个人纪录>学号，姓名·····

3.数据对象

• 是性质相同的数据元素的集合，是数据的一个子集
  • 例如整数的数据对象是集合N={1，2，3··}

4.数据对象与数据元素

• 数据元素 ------ 组成数据的基本单位
  • 与数据的关系： 是集合的个体
• 数据对象 ----- 性质相同的数据元素 的集合
  • 与数据的关系是：集合的子集

5.数据结构

1. 数据结构

   • 数据元素不是孤立存在的，他们之间存在着某种关系，数据元素相互之间的关系成为结构

   • 是指相互之间存在着一种或者多种特定关系的数据元素的集合

   • 是带有结构的数据元素的集合

2. 数据结构包括的内容

   • 数据元素之间的逻辑关系，称为逻辑结构
   • 数据元素及其关系在计算机内存中表示（又称为映像），称为数据机构的物理结构或者数据的存储结构
   • 数据的运算和实现，及对数据元素可以施加的操作在相应的存储结构上的实现

数据结构的两个层次

• 逻辑结构
  • 描述数据元素之间的逻辑关系
  • 与数据的存储无关，独立于计算机
  • 是从具体问题抽象出来的数学模型
• 物理结构（存储结构）
  • 数据元素及其关系在计算机存储器中的结构（存储方式）
  • 是数据结构在计算机中的表示
• 逻辑机构与存储结构的关系
  • 存储结构时逻辑结构关系的映像与元素本身的映像
  • 逻辑结构是数据结构的抽象，存储结构是数据结构的实现
  • 两者综合起来建立了数据元素之间的结构关系

逻辑机构的种类

划分方法一

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

2. 非线性结构

   • 一个节点可能有多个直接前趋，和直接后续

   • 例如：树， 图

划分方法二 — （四类基本逻辑结构）

1. 集合机构：数据中的数据元素之间除了同属与一个集合的关系外，无任何其他关系
2. 线性结构：结构中的数据元素之间存在着一对一的线性关系
3. 树形结构：结构中数据元素存在着一对多的层次关系
4. 图状结构或网状结构：机构中的数据元素之间存在这多对多的任意关系

存储结构

1.顺序结构

• 用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示
  • C语言中的数据就是这样存储的

2.链式结构

• 用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系使用指针来表示
  • c语言中指针来实现链式存储结构

3.索引存储结构

• 在存储节点信息的同时，还建立了附加的索引表，索引表中的每一项称为一个索引项
• 索引项的一般形式为：（关键字，地址）
• 关键字是能唯一标识一个节点的那些数据项
• 每一个节点在索引表中都有一个索引项，则该索引表称为稠密索引。若一组节点在索引表中只对应一个索引项，则该索引表称为稀疏索引

4.散列存储结构

• 根据节点的关键字直接计算出该节点的存储地址

数据类型和抽象数据类型

• 在使用高级程序语言设计语言编写程序时，必须对程序中出现的每个变量。常量，或表达式，明确说明他们所属的数据类型
  • 列入在c语言中
    • 提供int char float double等基本数据类型
    • 数组，结构体，共用体，枚举等构造数据类型
    • 还有指针，空（void）类型
    • 用户也可以使用typedef自己定义数据类型
  • 一些最基本数据结构可以用数据类型类实现，如数据，字符串等
  • 而另一些常用的数据结构，如栈，队列，树，图等。不能直接使用数据类型来表示
• 高级语言中的数据类型明显的或隐含的规定，在程序执行期间变量和表达的所有可能的取值范围，以及在这些数据范围山所允许进行的操作
  • 例如int型
    • 范围就是-32368 — 32762
    • 在这个整数集上可以进行 + - * / % 等操作
• 数据类型的作用
  • 约束变量或常量的取值范围
  • 约束变量或常量的操作

数据类型

• 定义： 数据类型是一组性质相同的值的集合，以及定义与这个值的集合上的一组操作的总称
  • 数据类型 = 值的集合 + 值集合上的一组操作

1.抽象数据类型（Abstract Data Type， ADT）

• 定义： 是指一个数学模型以及定义在此数学模型上的一组操作
  • 用用户定义，从问题抽象出数据模型（逻辑结构）
  • 还包括定义在数据模型上的一组抽象运算（相关操作）
  • 不考虑计算机内的具体存储结构与运算的具体实现算法

2.抽象数据类型的定义形式

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

  ADT 抽象数据类型名

  {

  数据对象：<数据对象的定义>

  数据关系：<数据关系的定义>

  基本操作：<基本操作的定义>

  } ADT 抽象数据类型名

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

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

  • 基本操作名（参数表）
    • 赋值参数， 只为了操作提供输入值
      • 例如 圆的面积： area（a）
    • 引用参数 以&打头，去可提供输入值外，还将返回操作结果
      • 例如 图形的缩放：picture（&G， n）；将缩放后的图形依旧保存在G中，类似c语言中以指针为参数传递的自定义函数，
  • 初始条件（初始条件描述）
    • 描述操作执行前数据和参数应满足的条件，如不满足，则操作失败，并且返回对应出错的信息，如初始条件为空，则省略之
  • 操作结果（操作结果描述）
    • 说明操作正常完成后，数据结构的变化状况和应返回的结果

• 例

  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 Complex

  {

  D = {r1, r2| r1,r2都是实数}

  S = {<r1, r2>| r1是实部， r2是虚部}

  assign（&C, v1, v2）

    初始条件：空的复数C已存在
  
    操作结果：构造复数C， r1，r2分别被赋予参数v1，v2的值
  

  destory（&C）

    初始条件：复数C已存在
  
    操作结果： 复数C被销毁
  

  GetReal(&C, &realPart)

    初始条件：复数已存在。
  
    操作结果：用realPart返回复数C的实部值
  

  GetImag(C,&ImagPart)

    初始条件：复数已存在
  
    操作结果：用ImagPart返回复数C的虚部值
  

  }ADT Complex

3.抽象数据的具体化

• c语言实现抽象数据类型

  • 使用已有的数据类型定义描述它的存储结构
  • 用函数定义描述它的操作

• 例：使用c语言来对抽象数据类型“复数”的实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

  /* 该程序是用来实现复数的运算 本函数用来求复数 ((8+6i)*(4+3i)) / ((8+6i) + (4+3i)) */ #include <stdio.h> typedef struct{ float realpart; float imagpart; }Complex; void creat(Complex *A, float realpart, float imagpart); void add(Complex A, Complex B, Complex *C); void subtract(Complex A, Complex B, Complex *C); void multiply(Complex A, Complex B, Complex *C); int except(Complex A, Complex B, Complex *C); int main() { int a; Complex z1, z2, z3, z4,z; creat(&z1, 8.0, 6.0); creat(&z2, 4.0, 3.0); add(z1, z2, &z3); multiply(z1, z2, &z4); a = except(z4, z3, &z1); if( a == 0) { printf("分母为零运算结束"); } else { printf("%.2f+%.2fi", z1.realpart, z1.imagpart); } } void creat(Complex *A, float realpart, float imagpart) { A->realpart = realpart; A->imagpart = imagpart; } void add(Complex A, Complex B, Complex *C) { C->realpart = A.realpart + B.realpart; C->imagpart = A.imagpart + B.imagpart; } void subtract(Complex A, Complex B, Complex *C) { C->realpart = A.realpart - B.realpart; C->imagpart = A.imagpart - B.imagpart; } void multiply(Complex A, Complex B, Complex *C) { C->realpart = (A.realpart * B.realpart)-(A.imagpart * B.imagpart); C->imagpart = (A.realpart * B.imagpart)+(A.imagpart * B.realpart); } int except(Complex A, Complex B, Complex *C) { if(B.imagpart != 0 || B.realpart!= 0) { C->realpart = (A.realpart * B.realpart+A.imagpart * B.imagpart)/(B.realpart*B.realpart+B.imagpart*B.imagpart); C->imagpart = (A.imagpart * B.realpart-A.realpart * B.imagpart)/(B.realpart*B.realpart+B.imagpart*B.imagpart); return 1; } return 0; }

算法和算法分析

算法的定义

• 对特定问题求解方法和步骤的一种描述， 它是指令的有限**序列每一个指令表示一个或者多个操作
  • 简而言之，算法就是解决问题的方法和步骤
  • steps1·······
  • steps2·······

算法的描述

• 自然语言：英文， 中文
• 流程图：传统流程图，NS流程图
• 伪代码：类语言：类c语言
• 程序代码：c语言程序，JAVA语言程序

算法与程序

• 算法是解决问题的一种方法或者一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法

• 程序使用魔种程序设计语言对算法的具体实现。

  程序 = 数据结构 + 算法

  数据结构通过算法实现操作

  算法根据数据结构设计程序

算法特性（有五种）

• 有穷性：一个算法必须总是在执行又穷步后结束，且，每一步都在有穷区间内完成
• 确定性：算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
• 可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来完成
• 输入：一个算法有零个或多个输入
• 输出：一个算法有一个或多个输出

算法设计的要求

• 正确性（Correctness）
  • 正确性：算法满足问题要求。能正确解决问题，算法转化为程序后需要注意
    1. 程序中不含有语法错误
    2. 程序对于几组输入数据能够得出满足要求的结果
    3. 程序对于精心选择的，典型的，苛刻且带有刁难性的几组输入数据能够得出满足要求的结果
    4. 程序对于一切合法的输入数据都能满足要求的结果
       • 通常以第三层意义上的正确性作为衡量一个算法是否合格的标准
• 可取性（Readability）
  1. 算法主要是为了人的阅读和交流，其次才是为了计算机执行，因此算法应该易与人的理解
  2. 另一方面，晦涩难懂的算法易于隐藏较多的错误而难以调试
• 健壮性（Robustness）
  1. 指当输入非法数据时算法恰当的做出反应或进行相应的处理，而不是产生莫名其妙的输出结果
  2. 处理错误的方法，不应是中断程序，而是返回一个表示错误或错误性质的值，以便在更高抽象层次上进行处理
• 高效性（Efficiency）
  1. 要求花费尽量少的时间，和尽量低的存储需求

评价算法

• 一个好的算法首先要具备正确性，然后是健壮性，可读性，在这几个方面都满足的情况下，组要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度
• 算法效率以下两个方面来考虑：
  1. 时间效率：指的是算法所耗费的时间
  2. 空间效率： 指的是算法执行过程中所耗费的存储空间

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

• 算法时间效率的度量
  • 算法时间效率可以用依据该算法在计算机上执行所耗的时间来度量
  • 两种度量方法
    • 事后统计
      • 将算法实现，测算其时间和空间开销
      • 缺点：编写程序实现算法将花费较多的时间和精力；所得实验结果依赖于计算机的软硬件等环境因素，掩盖算法本身的优劣
    • 事前分析
      • 对算法所耗资源的一种估算方法

事前分析法(时间效率)

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

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

    	每条语句执行的次数又称为**语句频度**
  
    	一个简单操作所需要的时间有机器而异，所以可以**假设执行每条语句所需要的时间**均为**单位时间**，所以算法运行的时间就可以转换为**算法运行次数**的比较
  

  1 2 3 4 5 6 7 8 9 10 11

  for( i = 0; i < n; i++) // 执行n+1次 最后一次还要判断是否退出 { for( j = 0; j < n; j++) // 执行n*(n+1)次 { printf("我爱数据结构~~~"); // 执行n*n次 for(k = 0; k < n; k++) // 执行n*n*(n+1)次 { printf("有点腻害"); // 执行n*n*n次 } } }

  上述代码一共执行了2n^3 + 3n^2 + 2*n + 1次

  1 2 3 4 5 6 7

  for( i = 0; i < n; i++) { for( j = i; j < n; j++) { printf("我爱数据结构~~~"); } }

  上述代码一共执行了n+(n-1)+(n-2)+(n-3) ··· + 2 + 1 = (1+n)*n/2 = n/2 + n^2/2 次

  我们把算法所耗费的时间定义为该算法中每条语句的频度之和，则上述代码时间消耗为T(n^2)

  但是以上方法太过于繁琐， 所以我们只要比较他们的数量级即可

• 若有某个辅助函数fn(n)，使得当n趋近于无穷大的时候，T(n)/f(n)的极限值为不等于零的常数，同阶无穷小，记作T(n) = O(f(n)) ,称O(f(n))为算法的渐进时间复杂度（O是数量级的符号），简称时间复杂度

  例如上面第一个例子

    T(n) = 2*n^3 + 3*n^2 + 2*n + 1; 当n->∞的时候 T(n)/n^3   -> 2 这表示n充分大时，T（n）与n^3是同阶或者同数量级，引入大“O”记号，则T（n）可记作
  
    											T(n) = O(n^3)
  

• 分析算法时间复杂度的基本方法

  1. 找出语句频度最大的那一条语句作为基本语句
  2. 计算基本语句的频度得到问题规模n的某个函数f(n) 然后去掉低次项， 和高次项的系数
  3. 取其数量级用符号“O”表示、

  1 2 3 4 5

  i = 1; while( i < n) { i = i*2; }

  执行次数分析 ：

  • 若循环一次 i = 2；
  • 若循环两次 i = 2*2;
  • 若循环三次 i = 2^3;
  • 若循环x次 i = 2^x；
  • 因为 i < n; 所以 2^x <= n ----> x <= log(2)n;

• 注意 有的情况下，算法中基本操作重复执行的次数随问题的输入数据集不同而不同

  • 例 顺序查找，在数组a[i]中查找值等于e的元素，返回其所在的位置

    1 2 3 4 5 6 7 8

    for(i = 0; i < n; i++) { if( a[i] == e) { return i+1; //找到，则返回是第几个元素 } } return 0;

    最好的情况： 1次

    • 指在最好的情况下，算法的时间复杂度

    最坏的情况：n

    • 指在最坏的情况下，算法的时间复杂度

    平均时间复杂度为：O（n）

    • 指在所有可能输入实例在等概率出现的情况下，算法的期望运行时间

  • 一般总是考虑在最坏情况的时间复杂度，以保证算法运行时间不会比它更长

• 对于复杂的算法，可以将它分成几个容易估算的部分，然后利用大O加法和乘法法则，计算算法的时间复杂度

  • 加法规则

    T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

  • 乘法法则

    T(n) = T1(n)*T2(n) = O(f(n)) * O(g(n)) = O(g(n)*f(n))

空间效率

• 空间复杂度：算法所需存储空间的度量
  • 记作 S(n) = O(f(n))
  • 其中n为问题的规模（或大小）
• 算法要占据的空间
  • 算法本身要占据的空间，输入/输出，指令，常数，变量
  • 算法要使用的辅助空间
• 例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// 将一维数组a中的n个逆序存放到原数组中
// 算法一
for(i = 0;i < n/2; i++)
{
    t = a[i];
    a[i] = a[n-i-1];
    a[n-i-1] = t;   //其中t为辅助空间
}
//算法二
for(i = 0;i < n; i++)
{
    b[i] = a[i];  //其中b[i]为辅助空间
}
for( i = 0; i < n; i++)
{
    a[i] = b[n-1-i];
}

第一个的空间复杂度为S(n) = O(1);因为辅助空间不随着n的增长而增长

第二个空间复杂度为S(n) = O(n); n越大b[n]所占的空间越大

所以第一个算法比较好