数据结构的基本概念以及算法的基本内容

1. 数据结构的重要性

• 数据结构与算法的关系：数据结构是算法的基础，算法是数据结构的操作逻辑。

2. 基本概念与术语

• 数据：描述客观事物的符号，是计算机操作的基本单位（如数值、字符、图像等）。

• 数据元素：组成数据的基本单位（如学生信息表中的一条记录）。

• 数据项：数据元素的组成部分（如学生信息中的学号、姓名）。

• 数据对象：性质相同的数据元素集合（如所有学生的学号集合）。

3. 逻辑结构与物理结构

• 逻辑结构：

  • 集合结构：元素间无明确关系。

• 线性结构：元素间是一对一关系（如数组、链表）。

• 树形结构：元素间是一对多关系（如家谱树）。

• 图形结构：元素间是多对多关系（如社交网络）。

• 注意两点
  • 将每一个数据元素看做一个结点，用圆圈表示
  • 元素之间的逻辑关系用结点之间的连线表示，如果这个关系是有方向的，那么用带箭头的连线表示

• 物理结构：

  • 顺序存储：元素在内存中连续存放（如数组），支持随机访问。

• 链式存储：元素通过指针链接（如链表），支持动态扩展。

4. 抽象数据类型（ADT）

• 定义：数学模型及其操作的集合，与具体实现无关。

• 描述方式：

  ADT 抽象数据类型名
  Data数据元素及其逻辑关系定义
  Operation操作1：初始条件与结果描述操作2：...
  endADT

• 意义：封装数据与操作，简化复杂问题的建模。

5. 算法定义与特性

• 定义：解决特定问题的有限步骤描述，体现为指令的有序序列。

• 五大特性：

  • 输入：零或多个输入。

  • 输出：至少一个输出。

  • 有穷性：执行步骤有限。

  • 确定性：每步含义明确，无二义性。

  • 可行性：操作可通过基本运算实现。

6. 算法设计要求

• 正确性：对合法输入产生正确结果。

• 可读性：代码清晰易理解。

• 健壮性：对非法输入有处理能力。

• 高效性：时间与空间复杂度低。

7. 算法效率分析

• 时间复杂度：衡量算法执行时间随输入规模增长的趋势。

  • 大O表示法：

    1. 用常数1取代运行时间中的所有加法常数。

    2. 只保留最高阶项。

    3. 去除最高阶项的系数。

  • 常见复杂度：

    • O(1)：常数阶（如数组访问）。

    • #include <stdio.h>// 直接访问数组的第三个元素（时间复杂度固定为 O(1)）
      int access_third_element(int arr[], int size) {if (size < 3) return -1; // 边界检查return arr[2]; // 直接访问索引为2的元素
      }int main() {int arr[] = {10, 20, 30, 40, 50};int size = sizeof(arr) / sizeof(arr[0]);printf("第三个元素: %d\n", access_third_element(arr, size)); // 输出 30return 0;
      }

    • O(n)：线性阶（如遍历数组）。

    • #include <stdio.h>// 遍历数组并打印所有元素（时间复杂度为 O(n)）
      void print_all_elements(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
      }int main() {int arr[] = {1, 2, 3, 4, 5};int size = sizeof(arr) / sizeof(arr[0]);print_all_elements(arr, size); // 输出 1 2 3 4 5return 0;
      }

    • O(n²)：平方阶（如双重循环）。

    • #include <stdio.h>// 双重循环遍历二维数组（时间复杂度为 O(n²)）
      void print_all_pairs(int arr[], int size) {for (int i = 0; i < size; i++) {for (int j = 0; j < size; j++) {printf("(%d, %d) ", arr[i], arr[j]);}printf("\n");}
      }int main() {int arr[] = {1, 2, 3};int size = sizeof(arr) / sizeof(arr[0]);print_all_pairs(arr, size); // 输出所有元素对return 0;
      }

    • O(log n)：对数阶（如二分查找）。

    • #include <stdio.h>// 二分查找（时间复杂度为 O(log n)，数组必须有序）
      int binary_search(int arr[], int size, int target) {int left = 0, right = size - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) return mid;    // 找到目标if (arr[mid] < target) left = mid + 1; // 右半部分else right = mid - 1;                  // 左半部分}return -1; // 未找到
      }int main() {int arr[] = {2, 5, 8, 12, 16, 23, 38, 45};int size = sizeof(arr) / sizeof(arr[0]);int target = 16;int index = binary_search(arr, size, target);if (index != -1) {printf("元素 %d 的索引是 %d\n", target, index); // 输出 4} else {printf("元素不存在\n");}return 0;
      }

• 空间复杂度：算法所需存储空间的量度（如递归调用栈的深度）。

8. 实例对比

• 高斯求和：

  • 暴力累加（O(n)） vs. 公式计算（O(1)）。

  • #include <stdio.h>// 暴力循环累加
    int gauss_sum_loop(int n) {int sum = 0;for (int i = 1; i <= n; i++) {sum += i;}return sum;
    }// 数学公式直接计算（时间复杂度 O(1)）
    int gauss_sum_formula(int n) {return n * (n + 1) / 2;
    }int main() {int n = 100;printf("暴力累加结果: %d\n", gauss_sum_loop(n));   // 输出 5050printf("公式计算结果: %d\n", gauss_sum_formula(n)); // 输出 5050return 0;
    }

• 递归与迭代：

  • 斐波那契数列的递归实现（O(2ⁿ)） vs. 迭代实现（O(n)）。

  • #include <stdio.h>// 递归实现（效率低）
    int fibonacci_recursive(int n) {if (n <= 1) {return n; // 终止条件：F(0)=0, F(1)=1}return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
    }// 迭代实现（时间复杂度 O(n)，空间复杂度 O(1)）
    int fibonacci_iterative(int n) {if (n <= 1) return n;int a = 0, b = 1, temp;for (int i = 2; i <= n; i++) {temp = a + b;a = b;b = temp;}return b;
    }int main() {int n = 10;printf("递归结果(F(10)): %d\n", fibonacci_recursive(n)); // 输出 55printf("迭代结果(F(10)): %d\n", fibonacci_iterative(n)); // 输出 55return 0;
    }