关于数据结构的简单认识

一条晒干的咸鱼

发布于 2025-07-15 14:40:43

16500

代码可运行

文章被收录于专栏：learnlearn

运行总次数：0

代码可运行

数据结构概述

数据结构基本概念

数据结构指的是计算机存储数据和组织数据的方式，存储数据和组织数据的目的是为了后期对数据的再次利用，所以存储的数据一般是具有一个或者多个特定关系的集合，利用不同的数据结构可以提高数据的访问效率。

数据指的是可以被输入到计算机并且可以被计算机处理的符号的总称，数据的英文是Data。

数据是有单位的，数据的基本单位是数据元素（Data Element），在计算机中数据元素是作为整体来处理的，比如学生的信息。数据元素是由多个数据项组成的，所以数据项也被称为数据的最小单位，比如学生信息中的学号、姓名、年龄，数据项属于数据元素不可分割的一部分。

数据结构就是描述多个数据之间的逻辑结构和物理结构。逻辑结构指的是数据元素之间的逻辑关系，物理结构指的是计算机中存储数据的方式，所以物理结构也被称为存储结构。

注意：数据元素的逻辑关系和物理关系没有必然的联系，数据元素可能同时存储逻辑关系和物理关系，数据元素之间也可能只存在一种关系，或者数据元素之间一种关系都没有。

逻辑关系

对于数据结构的逻辑关系，可以分为：线性结构：数据元素一对一关系（如数组、链表、栈、队列）、非线性结构包括：树形结构（一对多，如二叉树、B树）和图形结构（多对多，如有向图、无向图）、集合结构：仅存在归属关系，无明确顺序（如哈希表）

物理关系

数据的物理关系可以分为：顺序存储（Sequential）：数据连续存放（如数组、动态数组）、链式存储（Linked）：通过指针/引用连接离散内存块（如链表、树、图的邻接表）、索引存储（Indexed）：额外建立索引表加速访问（如数据库索引）以及散列存储（Hashed）：通过哈希函数映射存储位置（如哈希表）。

什么是算法

广义上讲算法是研究数据之间的逻辑关系，然后选择某种方案来存储数据，并在此基础上对数据进行处理，其实更加直白的说：算法指的是计算或者解决问题的步骤。

思考一个问题：如果把下面的一个随机数列中的数值按照从小到大顺序进行排列?具体步骤是什么??

给定随机数列：[5, 2, 9, 1, 3]，将其按从小到大排序。

步骤1：选择排序算法

这里以冒泡排序（Bubble Sort）为例，因其直观易理解。核心思想：重复比较相邻元素，将较大的数逐步“冒泡”到右侧。

步骤2：具体排序过程

第1轮遍历（比较4次）

比较5和2 → 交换 → [2, 5, 9, 1, 3]
比较5和9 → 不交换
比较9和1 → 交换 → [2, 5, 1, 9, 3]
比较9和3 → 交换 → [2, 5, 1, 3, 9]

结果：最大值9已到最右。

第2轮遍历（比较3次）

比较2和5 → 不交换
比较5和1 → 交换 → [2, 1, 5, 3, 9]
比较5和3 → 交换 → [2, 1, 3, 5, 9]

结果：次大值5就位。

第3轮遍历（比较2次）

比较2和1 → 交换 → [1, 2, 3, 5, 9]
比较2和3 → 不交换

结果：序列已有序，提前结束。

算法特征

(1) 有穷性：指的是程序执行必须在有限次数内完成，而每一次必须在有限时间内执行完成。

(2) 确定性：执行的每一条语句都必须有准确的解释，不能出现二义性，意味着相同的输入就会相同的输出。

(3) 可行性：程序中每一条复杂语句都可以分解为基本指令，并且每条基本指令都必须在有限时间完成。

(4) 输入项：指的是算法可以有一个或者多个参数作为初始条件，然后对程序进行有效执行。

(5) 输出项：指的是算法经过运算之后可以有一个或者多个输出，所以一个有意义的算法是应该有输出结果的。

总结：一个程序的执行是需要用户选择合适的算法和数据结构的，程序 = 数据结构+算法。

思考一个问题：到底什么样的数据结构和算法是合适的?怎么去评定选择的数据结构和算法是否合适?

回答：对于数据结构的选择和算法的选择并不是唯一的，但是选择要是合适的，衡量数据结构和算法的选择是否合适，取决于算法实现的运行时间和内存空间。一般是通过两个专业性名称，分别是“时间复杂度”和“空间复杂度”。

时间复杂度

时间复杂度不是算法的运行时间来衡量，因为程序的运行时间取决于CPU的性能，不同性能的CPU执行指令的周期是不一样的，比如8bit单片机的主频是12MHZ，而32bit单片机的主机可以168MHZ，而计算机的CPU主频都是xxx.GHZ 。

时间复杂度指的是算法程序的语句的执行次数，也可以称为语句频度，一个程序的语句执行次数越多，则时间复杂度越大，则说明算法不合适。时间复杂度一般采用数学符号大O()表示，一般时间复杂度的计算中都会出现n，n表示规模，对于时间复杂度是表示算法的趋势。

一般会把算法程序的语句的执行次数用T()表示，但是对于函数T()可能是一个多项式，而时间复杂度就是找出函数T()影响最大的项，所以时间复杂度是执行语句的估算值，使用数学符号大O()表示。O其实是order的缩写。大O的括号中写的值就是影响程序执行语句最大的那个项。

计算技巧：只需要计算出算法的基本执行语句的最高次项，并且把最高次项的系数舍弃，就是算法的时间复杂度，需要使用数学符号O(xxx)，如果计算出的是常数项，则时间复杂度衡为O(1)。

问题：在数组中查找特定元素时间复杂度：O(n) - 最坏情况需要检查所有元素

#include <stdio.h>

int linear_search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  // 找到返回索引
        }
    }
    return -1;  // 未找到
}

int main() {
    int arr[] = {2, 5, 1, 7, 4};
    int target = 7;
    int result = linear_search(arr, 5, target);
    
    if (result != -1) {
        printf("元素 %d 在索引 %d\n", target, result);
    } else {
        printf("元素 %d 不存在\n", target);
    }
    return 0;
}

问题：对数组进行升序排序时间复杂度：O(n²) - 嵌套循环导致平方级复杂度

#include <stdio.h>

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换相邻元素
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {5, 2, 9, 1, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    bubble_sort(arr, n);
    
    printf("排序后数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

关键区别