数据结构一 数据结构基础概念

一、数据结构基础概念

1. 数据结构的定义与三要素

数据结构是研究非数值计算问题中计算机的操作对象、它们之间的关系和运算的学科。它包含三个层面：

• 逻辑结构：数据元素之间抽象的逻辑关系，与计算机无关。
• 存储结构（物理结构）：数据在计算机中的实际存储方式。
• 运算（算法）：对数据进行的操作，如插入、删除、修改、查找、排序。

2. 逻辑结构的分类

• 线性结构：元素间是一对一关系。
• 非线性结构：包含树形结构（一对多）和图形结构（多对多）。

3. 逻辑结构的特点总结

结构类型	前驱/后续关系	第一个结点	最后一个结点	内部结点
线性结构	一对一	无前驱	无后续	1个前驱，1个后续
树形结构	一对多	根结点无前驱	叶子结点无后续	1个前驱，多个后续
图形结构	多对多	任意多个前驱和后续	任意多个前驱和后续	任意多个前驱和后续

4. 存储结构的四种基本方式

• 顺序存储：逻辑相邻的元素物理位置也相邻（如数组）。
• 链式存储：通过指针链接元素，物理位置可以不相邻。
• 索引存储：建立索引表存储结点地址。
• 散列存储：通过哈希函数直接计算存储地址。

---

二、算法与算法分析

1. 算法的五大特性

• 有穷性：执行有限步后结束。
• 确定性：每条指令含义明确，无二义性。
• 可行性：操作均可通过已实现的基本运算执行。
• 输入：有零个或多个输入。
• 输出：至少有一个输出。

2. 算法分析的目的与维度

• 目的：分析算法的效率以求改进。
• 两个主要方面：
  • 时间复杂度：算法运行所需时间，通常用基本语句的执行次数来衡量。
  • 空间复杂度：算法运行所需的额外存储空间。

---

三、时间复杂度通用解法（重点，结合你的错题）

时间复杂度通常用大O记号表示，只关心随问题规模n增长的最高阶项，忽略常数和系数。

通用解题三步法：

1. 找基本语句：执行次数最多的语句，通常是循环体最内层的语句。
2. 列次数表达式：写出该语句执行次数关于输入规模n的函数。
3. 取最高阶项：去掉系数和低阶项，得到大O阶。

常见题型与举例分析（包含你做错的题目）：

题型1：单层循环（对数阶） 这是你错题20的原型，易错点在于把指数增长误判为线性。

• 题目：i=1; while(i<=n) i=i*3;
• 分析：设循环执行次数为t。i的值依次为：1, 3, 9, 27, ... , 3^t。 循环终止时需满足 3^t > n，即 t > log₃n。所以执行次数约为log₃n。
• 复杂度：O(log₃n) ，通常简写为O(log n)。
• 常见变式：若循环变量为 i=2 且 i=i*2，复杂度为O(log₂n)。

题型2：双层循环（乘积阶）

• 题目：for(i=0;i<n;i++) for(j=0;j<m;j++) A[i][j]=0;
• 分析：外层执行n次，内层执行m次，基本语句A[i][j]=0共执行 n*m 次。
• 复杂度：O(n×m) 。若m=n，则为O(n²)。

题型3：嵌套循环含依赖关系（平方阶）

• 题目：

  for (i=1;i<n;i++) { 
      y=y+1;  
      for (j=0; j<=(2*n); j++) x++;
  }
  

• 分析：外层循环次数 n-1（≈n），内层循环次数 2*n+1（≈2n）。两者无变量依赖，直接相乘：(n-1)*(2n+1) ≈ 2n²。
• 复杂度：O(n²)。

题型4：循环次数依赖于累计和（你错题19的原型，重点理解）

• 题目：

  i=s=0;
  while(s<n) { 
      i++;  
      s+=i; 
  }
  

• 分析：这是最易错的类型，循环次数不与n成简单的线性或对数关系。设循环执行了t次。
  • i的值序列：第1次后i=1，第2次后i=2，第3次后i=3 ... 第t次后i=t。
  • s的值序列：s是i的累加和。第1次后s=1，第2次后s=1+2=3，第3次后s=1+2+3=6... 第t次后 s = 1+2+...+t = t(t+1)/2。
  • 循环终止条件：s >= n，即 t(t+1)/2 >= n。
  • 求解t与n的数量级关系：近似认为 t²/2 ≈ n，即 t ≈ √(2n)。所以t与√n同阶。
• 复杂度：O(√n)。
• 解题关键：遇到累计和 s+=i 或类似递增循环，用数列求和公式推导执行次数t与n的关系，再取阶。