数据结构（严蔚敏版）——第一章《绪论》

时间：2023-02-26 18:01:48

第一章 绪论

1.1、基本概念

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

数据（Data）：是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。

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

数据元素（Data Element）：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据项（Data Item）：是组成数据元素的、有独立含义的、不可分割的最小单位。

数据对象（Data Object）：是性质相同的数据元素的集合，是数据的一个子集。

1.1.2、数据结构

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

**数据结构（Data Structure）：**是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构包括以下三个方面的内容：

  1. **逻辑结构：**数据元素之间的逻辑关系
  2. **物理结构（数据的存储结构）：**数据元素及其关系在计算机中的表示
  3. **运算和实现：**即对数据元素可以施加的操作以及这些操作在相应存储结构上的实现。

逻辑结构与存储结构的关系：

  • 存储结构是逻辑关系的映像与元素本身的映像
  • 逻辑结构是数据结构的抽象，存储结构是数据结构的实现
  • 两者综合起来建立了数据元素之间的结构关系

  • 逻辑结构的种类：

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

  • 存储结构

    • **顺序存储结构：**用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。
    • **链式存储结构：**用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。
    • 索引存储结构：在存储点信息的同时，还建立附加的索引表，索引表中的项称为索引项，索引项一般是：(关键字， 地址)
    • **散列存储结构：**根据结点的关键字直接计算出该结点的存储地址

1.1.3、数据类型和抽象数据类型

数据类型(Data Type)：是高级程序设计语言中的基本概念，是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称

C语言中的数据类型：

  • 基本数据类型：

    • int(4个字节)
    • short(2个字节)
    • long(4个字节)
    • float(单精度，4个字节,精确的字数和位数6~7)
    • double(双精度，8个字节，精确的数字和位数16-17位)
    • char(1个字节)

  • 数据存储大小：

char short int long long long float double
16位 1 2 2 4 8 4 8
32位 1 2 4 4 8 4 8
64位 1 2 4 8 8 4 8
  • 数组、结构、共用体、枚举等构造数据类型
  • 指针、空(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 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被销毁
  getReal(Z, &realPart)
    初始条件: 复数已存在。
    操作结果: 用realPart返回复数Z的实部值
  getImag(Z, &imagPart)
    初始条件: 复数已存在。
    操作结果: 用imagPart返回复数Z的虚部值
  Add(z1, z2, &sum)
    初始条件: z1, z2是复数
    操作结果: sum返回两个复数z1,z2的和
} ADT Complex

1.2、抽象数据类型的表示与实现

C语言实现复数：

#include<stdio.h>
#include<stdlib.h>
typedef struct {
  float r; 	// 实部
  float i; 	// 虚部
} Complex;

void Assign(Complex *A, float a, float b);    /* 赋值 */
void OutComplex(Complex A);
void Add(Complex *A, Complex B,Complex C);		            /* B+C */
void Sub(Complex *A, Complex B,Complex C);	                /* B-C */
void Mul(Complex *A, Complex B,Complex C);              	/* C*B */
void Div(Complex *A, Complex B,Complex C);	                /* B/C */

void Assign(Complex *A, float x, float y) {
  // 构造一个复数
  A -> x = r;
  A -> y = i;
}

void OutComplex(Complex A)
{
  // 输出复数
	if(A.v > 0)
	printf("%f+%fi",A.r, A.v);
	else printf("%f%fi",A.r, A.v);
}

void Add(Complex *A, Complex B,Complex C) {
  // 求两个复数c1 和 c2的和sum
  A -> r = B.r + C.r;
  A -> i = B.i + C.i;
}
Complex Sub(Complex *A, Complex B,Complex C) {
  // 求两个复数c1 和 c2 的差difference
  A -> r = B.r - C.r;
  A -> i = B.i - C.i;
}

void Mul(Complex *A, Complex B,Complex C)
{
	A -> r = B.r * C.r - B.i * C.i;
	A -> v = B.i * C.r + B.r * C.i;
}

void Dev(Complex *A, Complex B,Complex C)
{
	A -> r = B.r*C.r-B.v*C.v;
	A -> v = (B.i * C.r - B.r * C.i) / (C.r * C.r + C.i * C.i);
}

void main() {
  int i;
  Complex z, z1, z2;
  float a1, a2, b1, b2;
  while(i != 0) {
    printf("请分别输入复数z1的实部和虚部：");
    scanf("%f%f", &a1, &b1);
    printf("请分别输入复数z2的实部和虚部：");
    sacnf("%f%f", &a2, &b2);
    Assign(&z1, a1, b1);
    Assign(&z2, a2, b2);
    printf("复数在z1 = ");
    OutComplex(z1);
    printf("\n复数z2 = ");
    OutComplex(z2);
    	Add(&Z, z1, z2);
    	printf("\n复数z1 + z2 = ");
    	OutComplex(z);
    	Sub(&Z, z1, z2);
    	printf("\n复数z1 - z2 = ");
    	OutComplex(z);
    	Mul(&Z, z1, z2);
    	printf("\n复数z1 * z2 = ");
    	OutComplex(z);
    	Dev(&Z, z1, z2);
    	printf("\n复数z1 / z2 = ");
    	OutComplex(z);
    printf("按任意按键结束\n");
    System("cls");
  }
}

java实现复数类：

package struct;

import java.math.BigDecimal;
import java.util.Objects;

/**
 * @author java小豪
 * @version 1.0.0
 * @description 复数类
 */
public class Complex {

    /**实部*/
    private double real;
    /**虚部*/
    private double imag;
    /**get/set方法*/
    public double getReal() {
        return real;
    }
    public double getImag() {
        return imag;
    }
    public void setReal(double real) {
        this.real = real;
    }
    public void setImag(double imag) {
        this.imag = imag;
    }
    public Complex() {}

    public Complex(double real, double imag) {
        this.real = real;
        this.imag = imag;
    }
    /**
     *
     * 两个复数相加
     * @param other
     * @return 复数相加
     */
    public Complex add(Complex other) {
        return add(this, other);
    }
    public static Complex add(Complex complex, Complex other) {
        double r = complex.getReal() + other.getReal();
        double i = complex.getImag() + other.getImag();
        return new Complex(r, i);
    }
    /**
     * 两个复数相减
     * @param other
     * @return 复数相减
     */
    public Complex sub(Complex other) {
        return sub(this, other);
    }
    public static Complex sub(Complex complex, Complex other) {
        double r = complex.getReal() - other.getReal();
        double i = complex.getImag() - other.getImag();
        return new Complex(r, i);
    }
    /**
     * 两复数相乘
     * @param other
     * @return 复数相乘
     */
    public Complex mul(Complex other) {
        return mul(this, other);
    }
    public static Complex mul(Complex complex, Complex other) {
        double r = complex.getReal() * other.getReal() - complex.getImag() * other.getImag();
        double i = complex.getImag() * other.getReal() + complex.getReal() * other.getImag();
        return new Complex(r, i);
    }
    public Complex div(Complex other) {
        return div(this, other);
    }
    public static Complex div(Complex complex, Complex other) {
        //如果为0,表示除以0, 产生除0异常。
        if(other.getReal() == 0 && other.getImag() == 0){
            throw new ArithmeticException("除 0 异常");
        }
        double r = complex.getReal() * other.getReal() - complex.getImag() * other.getImag();
        double i = (complex.getImag() * other.getReal() - complex.getReal() * other.getImag())
        / (complex.getReal() * complex.getReal() + complex.getImag() * complex.getImag());
        return new Complex(r, i);
    }

    /**
     * 比较两个复数是否相等
     * @param o
     * @return true 或 false
     */
    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Complex complex = (Complex) o;
        return Double.compare(complex.real, real) == 0 && Double.compare(complex.imag, imag) == 0;
    }
    @Override
    public int hashCode() {
        return Objects.hash(real, imag);
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        //保留四位小数，并且去0.
        String tempR = new BigDecimal(this.real).
                setScale(4, BigDecimal.ROUND_HALF_UP).stripTrailingZeros().toString();
        sb.append(tempR);
        //如果虚部为正，需要添加一个+号。 为-时，不需要添加
        if(this.imag>0){
            sb.append("+");
        }
        //如果为0,返回实部
        if(this.imag==0){
            return sb.toString();
        }
        //添加虚部， 复数后面的 i是固定的
        String tempI=new BigDecimal(this.imag).
                setScale(4, BigDecimal.ROUND_HALF_UP).stripTrailingZeros().toString();
        sb.append(tempI);
        sb.append("i");
        return sb.toString();
    }
}

/**
 * @author java小豪
 * @version 1.0.0
 * @description 复数运算测试类
 */
public class ComplexTest {
    public static void main(String[] args) {

        //1. 第一个复数, 实部为3,虚部为8
        Complex c1 = new Complex(3, 8);
        //2. 第二个复数， 实部为3,虚部为-6
        Complex c2 = new Complex(4, -9);
        //3. 第三个复数，实部为2，虚部为-7.
        Complex c3 = new Complex(5, -9);
        //4. 第四个复数，看是否相同
        Complex c4 = new Complex(23, 8);

        System.out.println("c1打印输出:" + c1.toString());
        System.out.println(c1.toString() + "+" + c2.toString() + "=" + Complex.add(c1, c2));
        System.out.println(c1.toString() + "-" + c2.toString() + "=" + Complex.sub(c1, c2));
        System.out.println(c1.toString() + "*" + c2.toString() + "=" + Complex.mul(c1, c2));
        System.out.println(c1.toString() + "/" + c2.toString() + "=" + Complex.div(c1, c2));
        System.out.println(c1.toString()+"与"+c4.toString()+"是否相同:"+c1.equals(c4));
    }
}

1.3、算法和算法分析内容

1.3.1、算法

:black_circle:算法的定义：对特定问题求解方法和步骤的一种描述，他的指令的有限序列。

:black_circle:算法的描述：

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

:black_circle:算法的特性：一个算法必须具备以下五个重要的特性

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

​ :black_medium_small_square:确定性：对于每种情况下所应执行的操作，在算法中有确切的规定，不会产生二义性

​ :black_medium_small_square:可行性：算法中所有的操作都可以通过以实现的基本操作运算执行有限次来实现

​ :black_medium_small_square:输入：一个算法有零个或多个输入

​ :black_medium_small_square:输出：一个算法有一个或多个输出

:black_circle:算法设计的要求：

​ :black_medium_small_square:正确性

​ 算法转化为程序后要注意：

​ 1、程序中不含语法错误

​ 2、程序对于机组输入数据能够得出满足要求的结果

​ 3、程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果

​ 4、程序对于一切合法的输入数据都能得出满足要求的结果

​ :black_medium_small_square:可读性

​ :black_medium_small_square:健壮性

​ :black_medium_small_square:高效性

:black_circle:算法的效率：

  • 时间效率：算法所耗费的时间。
    • 该算法编制的程序在计算机上执行所消耗的时间来度量
    • 度量方法：事后统计法、事前分析估算法
  • 空间效率：算法执行过程中所耗费的存储空间。

**算法运行的时间 = **$$\sum 每条语句频度 * 该语句执行一次所需的时间$$

**n $$\times$$ n矩阵相乘的算法可描述为： **

for (int i = 1; i <= n; i++) 												// 频度n + 1次
  for (int j = 1; j<= n; j++) {											// 频度n * (n + 1)次
    c[i][j] = 0;																		// 频度n * n次
    for (int k = 0; k < n; k++) {										// 频度n * n * (n + 1)次
      c[i][j] = c[i][j] + a[i][k] * b[k][j];				// 频度n * n * n次
    }
  }

算法的渐进时间复杂度：$$T(n) = O(n^3)$$

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

  1. 找出==语句频度最大==的那条语句作为==基本语句==
  2. 计算==基本语句==的频度得到问题规模n的某个函数
  3. 取其数量级用符号"O"表示

举例分析：

例一：

x = 0; y = 0;
for (int i = 1; i <= n; i++)
  x++;
for (int j = 1; j <= n; j++)
  for (int k = 1; k <= n; k++) 
    y++;

时间复杂度为：y++的频度为f(n) = $$n^2$$,所以时间复杂度为：$$T(n) = O(n^2)$$

例二：

void exam(float x[][], int m, int n) {
  float sum[];
  for (int i = 0; i < m; i++) {
    sum[i] = 0.0;
    for (int j = 0; j < n; j++) {
      sum[i] += x[i][j];
    }
  }
  for (int i = 0; i < m; i++)
    System.out.println("%d", sum[i]);
}

时间复杂度：sum[i] += x[i][j]的频度为$$f(n) = m * n$$，时间复杂度为：$$T(n) = O(m * n)$$

例三：

for (int i = 1; i <= n; i++) 												
  for (int j = 1; j<= n; j++) {											
    c[i][j] = 0;																		
    for (int k = 0; k < n; k++) {										
      c[i][j] = c[i][j] + a[i][k] * b[k][j];				
    }
  }

时间复杂度：c[i][j] = c[i][j] + a[i][k] * b[k][j]的频度为$$f(n) = n^3$$，时间复杂度为：$$T(n) = O(n^3)$$

例四：

int i = 1, j = 1, k = 1;
for (i = 1; i <= n; i++) 
  for (j = 1; j<= i; j++)
    for (k = 0; k <= j; k++)
      x = x + 1;

时间复杂度为：x = x + 1 的频度为$f(n) = \sum i * (i + 1) / 2$，时间复杂度为： $T(n) = O(n * (n + 1) * (n + 2) / 6) = O(n^3)$

例五：

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

时间复杂度为：i = i * 2 的频度为：$f(n) = log_2 n$，时间复杂度为：$T(n) = log_2 n$

1.3.3、算法时间复杂度的计算

  1. **最好时间复杂度：**指在最好情况下，算法的时间复杂度
  2. **最坏时间复杂度：**指在最坏情况下，算法的时间复杂度
  3. **平均时间复杂度：**指在所有的输入实例在等概率出现的情况下，算法的期望运行时间

注意：对于复杂的算法，可以分成几个容易估算的部分，然后利用大O加法法则和乘法法则计算

  • 加法法则：$T(n) = T_1(n) + T_2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))$
  • 乘法法则：$T(n) = T_1(n) * T_2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n))$

复杂度$T(n)$按数量级递增顺序为：

越向右算法的复杂度越高

常数阶 对数阶 线性阶 线性对数阶 平方阶 立方阶 K次方阶 指数阶
O(1) O(logn) O(n) O(n * log n) O(n^2^) O(n^3^) O(n^k^) O(2^n^)

1.3.4、算法的空间复杂度

:black_medium_square:**空间复杂度：**算法所需存储空间的度量，记作：$S(n) = O(f(n))$其中n为问题的规模(或大小)

:black_medium_square:算法要占据的空间:

  1. 算法本身要占据的空间，输入/输出，指令，常数，变量等
  2. 算法要使用的辅助空间

分析例题：

例一：将一维数组a中的n个数逆序存放到原数组中

for (int i = 0; i < n; i++) {
  t = a[i];
  a[i] = a[n - i -1];
  a[n - i - 1] = t;
}

**空间复杂度：**仅借用临时变量t，与问题规模n大小无关，所以空间复杂度为$O(1)$

for (int i = 0; i < n; i++)
  b[i] = a[n - i - 1];
for (int i = 0; i < n; i++) 
  a[i] = b[i];

**空间复杂度为：**借用大小为n的辅助数组b，所以空间复杂度为$O(n)$

标签：

相关文章