【示例一】学籍档案管理

【数据特点】

每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；
表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；

【操作】 对它的操作通常是： 在学生档案中

查找出某人的档案
读取某个学生的信息
插入某个学生的信息
删除某个学生的信息
更新某个学生的信息
……等

【示例二】制定教学计划

【注意】 在制定教学计划时，需要考虑：

各门课程的开设顺序，即有些课程需要先导课程，有些课程则不需要，而有些课程

又是其他课程的先导课程

（5）数据结构主要研究

（6）学习数据结构的目的

掌握常用的数据结构及其应用
学会合理地组织数据，有效地表示数据和处理数据
掌握算法设计技术和分析技术
掌握使用计算机解决问题的方法和技能，提高程序设计水平

二、基本概念和术语

（1）数据

数据（Data)：所有被计算机存储、处理的对象。

（2）数据元素

数据元素（Data Element）： 数据的基本单位，是运算的基本单位。常常又简称为元素。

（3）数据项

数据项（Data Item）： 数据元素常常还可分为若干个数据项，数据的不可分割的最小标识单位。

在数据库中数据项又称为字段或域，它是数据的不可分割的最小标识单位
实际问题中的数据称为原始数据

从宏观上看，数据、数据元素和数据项实际上反映了数据组织的三个层次，数据可由若干个数据元素组成，而数据元素又可由若干个数据项组成。

（4）数据结构

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

（5）数据的逻辑结构

逻辑结构（Logical Structure）：

指数据元素之间的结构关系。
与数据元素本身的形式、内容、相对位置、所含节点个数无关。

特别注意：

逻辑结构与数据元素本身形式、内容无关
逻辑结构与数据元素的相对位置无关
逻辑结构与所含结点个数无关

① 逻辑结构的种类

数据的逻辑结构	描述
集合	任意两个结点之间都没有邻接关系，组织形式松散
线性结构	结点按逻辑关系依次排列形成一条“链”,结点之间一个一个依次相邻接
树形结构	具有分支、层次特性，其形态像自然界中的树，上层的结点可以和下层多个结点相邻接，但下层结点只能和上层的一个结点相邻接
图结构	[最复杂] 其中任何两个结点都可以相邻接

② 四种基本逻辑结构的结构示意图

（6）数据的存储结构

存储结构 / 物理结构（Physical Structure）：指数据结构在机内的表示，数据的逻辑结构在计算机中的实现

数据结构的存储包含数据元素的存储及其逻辑关系的存储
存储结构可分为: 顺序存储结构、链式存储结构、索引存储方式和散列存储方式等。
顺序存储结构与链式存储结构最基本，应该重点掌握。如，如何操作，各有什么特点，什么时候选择顺序结构，什么时候选择链式结构等。

数据在计算机内的表示形式称为：

数据的存储结构

存储结构的主要部分：

存储结点（每个存储结点存放一个数据元素）
数据元素之间关联方式的表示

数据结构的存储包含：

数据元素的存储
数据元素逻辑关系的存储

存储结构的分类：

顺序存储方式
链式存储方式
索引存储方式
散列存储方式
…… 等

最基本的存储结构分类：

顺序存储方式
链式存储方式

① 顺序存储方式

顺序存储方式：

指所有存储结点存放在一个连续的存储区里
利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系

【说明】顺序的方法：

将元素存储到一片连续的存储区

【特点】

预先分配好长度，需要预估存储数据需要的存储量
插入和删除需要移动其他元素
存取快捷，是随机存取结构

【示意图】

② 链式存储方式

链式存储方式： 指每个存储结点除了含有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系。

【说明】这种结构是给结点附加一个指针字段，指出其后继节点的位置，即存放结点的存储单元分为两部分:

【特点】

动态分配，不需要预先确定内存分配
插入和删除不需要移动其他元素
非随机存取结构

【示意图】

③ 索引存储方式

索引存储方式：借助索引表中的索引指示各存储节点的存储位置

④ 散列存储方式

散列存储方式：用散列函数指示各节点的存储位置

（7）运算

运算：是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。

线性表、栈和队列中的元素具有相同的逻辑结构（即 线性结构），但有不同的运算集，它们是不同的数据结构。

三、算法及描述

算法规定了求解给定类型问题所需的所有 “处理步骤” 及执行顺序，使给定类型问题能在有限时间内被机械的求解。

算法必须使用某种语言描述：

程序
介于自然语言和程序设计语言的伪代码
非形式算法（自然语言）
框图 (N-S 图)

《数据结构导论》教材中使用了类 C 语言描述算法

四、算法分析

运算的实现是指该运算的算法。一个算法规定了求解给定问题所需的处理步骤及其执行顺序，使得给定问题能在有限时间内被求解。

（1）评价算法好坏的因素

（2）选出最优算法通常考虑的两个度量

解决同一问题的算法可以有多种
我们希望从中选出最优的算法，效率高或者存储空间小
为此，需要对算法进行评估、分析

（3）时间复杂度

① 如何确定算法的计算量

② 常见的时间复杂度按数量级递增排列

我们将时间复杂度记为输入数据规模 n 的函数，若求解问题需要执行 n2 次操作则，记作：O(n²)

③ 各种时间复杂度与时间的关系

④ 示例

【示例一】设变量 a、b、c、d 中各含一个整数

求 a、b、c 中的最大值与 d 的乘

【示例代码】
// 求 a/b 和 c/d 中的最大值，结果乘以 d，输出
void max1(int a, b, c, d)
{
    a *= d;            // 将 a 乘以 d
    b *= d;            // 将 b 乘以 d
    c *= d;            // 将 c 乘以 d
    if(a > b) x = a;   // 如果 a 大于 b，将 a 赋值给变量 x
    else x = b;        // 否则将 b 赋值给变量 x。
    if(c > x) x = c;   // 如果 c 大于 x，将 c 赋值给变量 x
    printf("%d\n", x); // 输出结果 x
}
 
// 求 a/b 和 c/d 中的最大值，然后将最大值乘以 d，输出
void max2(int a, b, c, d)
{
    if(a > b) x = a;    // 如果 a 大于 b，将 a 赋值给变量 x
    else x = b;         // 否则将 b 赋值给变量 x
    if(c > x) x = c;    // 如果 c 大于 x，将 c 赋值给变量 x
    x *= d;             // 将最大值乘以 d
    printf("%d\n", x);  // 输出结果 x
}
【代码详解】

以上两个函数的功能是求出 a/b 和 c/d 中的最大值并乘以 d，输出结果 x。这两个函数的实现方法不同，其中 max1 会先将输入的所有参数乘以 d，再进行比较；而 max2 先进行比较，再将最大值乘以 d 输出。
对于 max1 函数，该函数中的 x 是没有定义的变量，应在函数前面进行定义。另外，在 C 语言中需要指定变量的类型。
同时，建议加上 if(d == 0) 的判断来避免除以0的异常情况。

【说明】

算法 max1 和 max2 的最坏情况时间复杂度分别为 5 和 3

【示例二】编制函数求 1!＋2!＋…+n

【示例代码】对于这个问题，可以写出两个算法：
// 算法一：O（n²）
// 计算 n 的阶乘，并返回结果
int factl(int n)
{
    int i, j, temp, s;
    s = 0; // 初始化结果为 0
 
    // 从 1 到 n 循环，每次累乘
    for (i = 1; i <= n; i++)
    {
        temp = 1; // 每次循环，初始化 temp 的值为 1
        for (j = 1; j <= i; j++) // 按照 i 的大小进行循环，计算阶乘
        {
            temp = temp * j; // 计算 i 的阶乘
        }
        s = s + temp; // 将计算结果累加到 s 中
    }
 
    return s; // 返回结果
}
// 算法二：O（n）
// 计算 n 的阶乘，并返回结果
int fact2(int n)
{
    int i, j, temp, s;
    s = 0; // 初始化结果为 0
    temp = 1; // 初始化阶乘初始值为 1
 
    // 循环计算 n 的阶乘
    for (i = 1; i <= n; i++)
    {
        temp = temp * i; // 计算 i 的阶乘
        s = s + temp; // 将计算结果累加到 s 中
    }
 
    return s; // 返回结果
}
【代码详解】

1. 算法一

以上代码是一个计算 n 的阶乘的函数，将结果 s 初始化为 0，从 0 到 n 循环累乘，每次乘法计算的结果赋给变量 temp，再将 temp 加到结果 s 中，最终返回 s 的值。
不过，需要注意的是代码中，第7行的变量 i 并未初始化，应当改为 i=1；第 9、11 行的运算符应当是加号 +，而非十进制符号。

2. 算法二

以上代码是一个计算 n 的阶乘的函数，将结果 s 初始化为 0，将 temp 初始化为 1。在循环计算阶乘时，每次计算 i 的阶乘后将其累加到 s 中，最终返回 s 的值。
需要注意的是，在第4行中，变量 termp 是打错了，应该是 temp。另外，循环体中 men个变量 s 必须初始化为 0 才能累加。

【示例三】矩阵运算 —— 矩阵乘法

【示例代码】
// 矩阵相乘函数
void matrixmlt(int** A, int** B, int** C, int n) {
    // 遍历矩阵 A 的行
    for (int i = 0; i < n; i++) {
        // 遍历矩阵 B 的列
        for (int j = 0; j < n; j++) {
            C[i][j] = 0; // 初始化结果矩阵 C 的元素为 0
            // 计算矩阵相乘
            for (int k = 0; k < n; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}
【代码详解】

函数 void matrixmlt(int** A, int** B, int** C, int n) 实现了矩阵相乘的操作。
A 是输入矩阵 A 的二维数组指针，B 是输入矩阵 B 的二维数组指针，C 是输出矩阵 C 的二维数组指针，n 是矩阵的维度。
外层循环 for (int i = 0; i < n; i++) 用于遍历矩阵 A 的行。
内层循环 for (int j = 0; j < n; j++) 用于遍历矩阵 B 的列。
初始化结果矩阵 C 对应元素为 0，C[i][j] = 0;。
再次嵌套循环 for (int k = 0; k < n; k++) 用于计算矩阵相乘，将结果累加到 C[i][j]上，C[i][j] += A[i][k] * B[k][j];。
最终得到的矩阵相乘结果存储在矩阵 C 中。

【时间复杂度】此算法的最坏时间复杂度和平均时间复杂度均为 n 的函数：
T(n)= n2 + n3
T(n) 与 n3 的数量级相同
称此算法的时间复杂度量级为 O(n3)，记作 T(n)= O(n3) 一般我们将 O(n3) 称作时间复杂度

【示例四】程序段的时间复杂度

一个算法的时间复杂度是算法输入规模的函数

【示例代码】
// 初始化乘积为1
product = 1;
 
// 外层循环，从 n 递减到 1
for (i = n; i > 0; i--) {
    // 内层循环，从当前 i 递增到 n
    for (j = i; j <= n; j++) {
        product *= j; // 计算乘积
    }
}
【代码详解】

首先，我们初始化一个变量 product 为 1，用于存储乘积的结果。
外层循环 for (i = n; i > 0; i--) 用于从 n 递减到 1，控制循环的执行次数。
内层循环 for (j = 1; j <= n; j++) 用于从 1 递增到 n，控制乘法操作的执行次数。
在每次循环中，乘积运算 product *= j;将当前的 j 乘以 product 的值，并将结果保存回 product 中。
最终，当外层循环执行完毕，内层循环也执行完毕时，变量 product 存储着从 1 到 n 的连续整数的乘积。

【注意】

这段代码实际上计算的是 n 的阶乘（n!），因为它将从 1 到 n 的所有整数相乘在一起
其中， n 是一个正整数
代码利用嵌套循环结构，逐个将整数相乘并更新乘积的值

【操作执行次数】
基本操作执行次数：
T(n) = 1 + 2 + … + n = (n+1)n/2
【时间复杂度】
时间复杂度量级：O(n²)
t(n) = O(n²)

【示例五】统计内层循环的执行次数，将其累加到变量 t 中

【示例代码】变量 t 的值将表示内层循环的总执行次数：
// 初始化变量 t 为 0
int t = 0;
 
// 外层循环，从 1 递增到 n-1
for (i = 1; i < n; i++) {
    // 内层循环，从 1 递增到 i-1
    for (j = 1; j < i; j++) {
        t = t + 1; // 更新变量 t 的值
    }
}
【代码详解】

首先，我们初始化一个变量 t 为 0，用于记录循环执行的次数。
外层循环 for (i = 1; i < n; i++) 从 1 递增到 n-1，控制外层循环的执行次数。
内层循环 for (j = 1; j < i; j++) 从 1 递增到 i-1，控制内层循环的执行次数。
在每次内层循环中，语句 t = t + 1; 将变量 t 的值加 1，并将结果保存回变量 t 中。
内层循环的起始值 j = 1，确保内层循环只执行 i-1 次，避免执行多余的计算。

【操作执行次数】
基本操作执行次数：
T(n) = 0 + 1 + 2 + … + (n-2) = (n-1)(n-2)/2
【时间复杂度】
时间复杂度量级：O(n²)
t(n) = O(n²)

（4）空间复杂度

空间复杂度：是对一个算法在运行过程中临时占用存储空间大小的量度。

一个算法在执行期间所需要的存储空间量包括以下部分：

程序代码所占用的空间
输入数据所占用的空间
辅助变量所占用的空间

估算算法空间复杂度时，一般只分析辅助变量所占用的空间

【示例一】读入 n=100 个整数到一个数组中，写出实现将该组数进行逆置的算法，并分析算法的空间复杂度

【示例代码】
// 算法一：O（1）
// 数组元素交换函数
void f1(int a[], int n) {
    int i, temp;
    
    // 遍历数组前半部分的元素
    for (i = 0; i <= n / 2 - 1; i++) {
        // 交换数组中对称位置的元素
        temp = a[i];
        a[i] = a[n - 1 - i];
        a[n - 1 - i] = temp;
    }
}
 
 
// 算法二：O（n）
// 数组元素翻转函数
void f2(int a[], int n) {
    int i, b[100]; // 定义临时数组 b
    
    // 将数组 a 中的元素按照相反的顺序存入数组 b
    for (i = 0; i <= n - 1; i++) {
        b[i] = a[n - 1 - i];
    }
    
    // 将数组 b 的元素复制回数组 a
    for (i = 0; i <= n - 1; i++) {
        a[i] = b[i];
    }
}
【代码详解】

1. 算法一

这段代码的作用是将数组中的元素按对称位置进行交换，实现数组的翻转或对称处理。
函数 void f1(int a[], int n) 实现了数组元素的交换操作。
a[] 是输入的整数数组，n 是数组的长度。
初始化变量 i 和 temp。
外层循环 for (i = 0; i <= n / 2 - 1; i++) 用于遍历数组前半部分的元素。
内部的交换操作将数组中的对称位置元素进行交换，使其从数组两端向中间靠拢。
temp = a[i]; 将当前位置的元素暂存到变量 temp 中。
a[i] = a[n - 1 - i]; 将对称位置的元素赋值给当前位置。
a[n - 1 - i] = temp; 将暂存的元素赋值给对称位置。

2. 算法二

这段代码的作用是将数组 a 中的元素翻转，即将原先靠前的元素放到靠后的位置，实现数组的倒序排列。
函数 void f2(int a[], int n) 实现了数组元素的翻转操作。
a[] 是输入的整数数组，n 是数组的长度。
声明了临时数组 b[100]，用于暂存翻转后的元素。
第一个循环遍历数组 a，将元素按相反的顺序存入数组 b。
b[i] = a[n-1-i]; 将数组 a 中的第 i 个元素存入数组 b 中，位置为 n-1-i。
第二个循环将数组 b 的元素复制回数组 a。
a[i] = b[i]; 将数组 b 中的第 i 个元素复制给数组 a 中的位置 i。

【代码功能】

这段代码包含两个函数，分别是 f1 和 f2，它们的功能分别是：

函数 f1：

作用：交换数组元素
输入参数：
a[]：整数数组
n：数组的长度
执行过程：
通过遍历数组的前半部分元素，将数组中对称位置的元素进行交换
输出结果：
修改了输入的数组 a[]，将元素进行了交换操作

函数 f2：

作用：翻转数组元素
输入参数：
a[]：整数数组
n：数组的长度
执行过程：
创建一个临时数组 b[100]，用于暂存翻转后的元素
将数组 a[] 中的元素按相反的顺序存入数组 b[]
将数组 b[] 的元素复制回数组 a[]
输出结果：
修改了输入的数组 a[]，将元素进行了翻转操作

这两个函数都需要一个整数数组作为输入，并根据指定的功能对数组元素进行处理。

f1 函数通过元素交换来改变数组的顺序，而 f2 函数则通过创建临时数组来实现翻转数组的效果。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/516232