数据结构七 中测

一、数据结构基础概念

1. 数据结构三要素

• 逻辑结构：数据元素之间的逻辑关系（与计算机无关）。
• 存储结构（物理结构）：数据在计算机中的实际存储方式。
• 运算：对数据施加的操作。

数据结构研究的是数据的逻辑结构和物理结构及它们之间的相互关系。

2. 逻辑结构 vs 存储结构

• 逻辑结构：指数据元素之间的逻辑关系，是数据元素之间的相互关系（不是数据项之间的关系）。
• 存储结构：是逻辑结构在计算机中的存储实现，主要有顺序存储、链式存储、索引存储、散列存储。

易错辨析（判断题45、46）：

• “数据的逻辑结构是指数据元素和数据元素之间的逻辑关系” —— 对。
• “数据的逻辑结构是指数据的各数据项之间的逻辑关系” —— 错。逻辑结构是数据元素间的关系，不是元素内部数据项的关系。

3. 数据元素与数据项

• 数据元素是数据的基本单位。
• 数据项是数据的最小不可分割单位。
• 判断题51：“数据元素是数据的最小单位” —— 错，最小单位是数据项。

4. 算法的特性与算法分析

• 算法五大特性：有穷性、确定性、可行性、输入、输出。
• 算法分析的两个主要方面：时间复杂性和空间复杂性。
• 时间复杂度不仅取决于问题的规模，还与待处理数据的初态有关（第1题）。
  • 例如：顺序表插入操作，在最好情况（末尾插入）为O(1)，最坏情况（表头插入）为O(n)。
• 健壮的算法：不会因非法的输入数据而出现莫名其妙的状态。

5. 时间复杂度分析（通用方法）

基本方法：

1. 找出执行次数最多的基本语句（通常是循环体内语句）。
2. 写出基本语句执行次数关于问题规模n的函数。
3. 取最高阶项（忽略系数和低阶项），得到大O复杂度。

常见复杂度举例：

(1) 对数阶 O(logₖn) 循环变量按几何级数增长。

• 例：for(i=1; i<=n; i=i*3) → 执行约 log₃n 次，复杂度 O(log₃n)。

(2) 平方阶/立方阶 多层嵌套循环，每层与n相关。

• 例：

for (i=1; i<n; i++) {        // 外层 n-1 次
    y = y+1;
    for (j=0; j<=(2*n); j++)  // 中层 2n+1 次
        for (k=1; k<=3*n; k++) // 内层 3n 次
            x++;
}

执行次数 ≈ n × 2n × 3n = 6n³，复杂度 O(n³)。

(3) 线性阶 O(n) 单层循环与n成正比。

(4) 常数阶 O(1) 执行次数与n无关，如顺序表随机访问。

---

二、线性表

1. 顺序表（顺序存储）

• 物理地址连续，可随机存取。
• 插入操作：在第i个位置插入，需后移 n-i+1 个元素，平均移动 n/2 个，时间 O(n)。
• 删除操作：删除第i个元素，需前移 n-i 个元素，平均移动 (n-1)/2 个。
  • 例（第5题）：30个元素顺序表，删除一个元素平均移动 (30-1)/2 = 14.5 个。
• 顺序栈满的条件（top从0或-1开始有区别）：
  • 若top从0开始，满时 top == m0-1（最多m0个元素，下标0~m0-1）。
  • 若top从-1开始，满时 top == m0-1。

2. 链表（链式存储）

• 每个结点包含数据域和指针域，用指针链接，物理地址可以不连续。
• 链式存储不能随机存取，只能顺序存取（第52题判断为错）。
• 单链表删除已知结点*p：需找到其前驱结点，时间 O(n)。
• 链栈：用链表存储栈元素，插入删除在表头（栈顶）进行。

3. 链栈操作

出栈操作（top为栈顶指针，s指向被删结点）：

s = top;               // s保存栈顶结点
top = top->next;       // top后移

注意：顺序栈出栈则是先取元素再移动指针。

4. 顺序栈出栈操作

若栈顶指针top指向栈顶元素位置：

x = S->data[S->top];   // 先取出栈顶元素
S->top--;              // 栈顶指针下移

若top指向栈顶下一空位，则先top--再取元素。需注意题目的top指向约定。

---

三、栈与队列

1. 栈的基本概念

• 操作原则：先进后出（FILO）/ 后进先出（LIFO）。
• 插入和删除都在栈顶进行。
• 栈顶（允许插入端）即栈的操作端。
• 链栈的容量不需要预先固定（动态分配），顺序栈容量需预先设定。

2. 出栈序列判断（通用方法）

对于入栈顺序固定的情况，判断某个出栈序列是否合法：

• 核心原则：在出栈序列中，若后面出栈的元素比前面出栈的某个元素小，则这些较小元素必须按入栈的逆序出栈。
• 验证法：模拟入栈过程，依次将入栈元素压栈，每当栈顶与期望出栈元素匹配时出栈。

例1（第14题）：出栈序列为 A,B,C,D（由栈顶到栈底），即实际出栈顺序为 D,C,B,A。

• 不可能的进栈顺序是 DCAB。若进栈为D,C,A,B，D和C出栈后，A入栈，此时栈中还有A，但B还没入栈，无法下一个出B。

例2（第15题）：入栈1,2,3,4,5，非法出栈序列是 45312。

• 验证：1,2,3,4依次入栈，4出栈，5入栈后出栈，此时栈中为1,2,3（栈顶为3），下一个只能出3，无法出3之前的1。

例3（第17题）：输入序列1,2,...,n，输出第一个是n，则输出序列是 n, n-1, n-2, ..., 1。

• 第i个输出元素 = n-i+1。

3. 栈的最小容量

若已知入栈和出栈序列，可模拟出栈过程，统计栈中最大元素个数即为最小容量。

例（第30题）：进栈a,b,c,d,e，出栈c,e,d,b,a。

• a入(1)，b入(2)，c入(3)，c出(2)
• d入(3)，e入(4)，e出(3)，d出(2)，b出(1)，a出(0)
• 最大栈深度=4？需重新核实：a入(栈:[a])，b入([a,b])，c入([a,b,c])，c出([a,b])，d入([a,b,d])，e入([a,b,d,e])，e出([a,b,d])，d出([a,b])，b出([a])，a出([])。最大为4，原答案3有误，但以试卷答案为准，可能是栈顶指针含义不同。若设初始top=0，入栈后top指下一空位，则实际占用数=top值。模拟：a入top=1，b入top=2，c入top=3，c出top=2，d入top=3，e入top=4，e出top=3，d出top=2，b出top=1，a出top=0。最大top=4，实际占用最大=4。如答案为3，则可能是另一种计数约定，需根据教材确认。

4. 循环队列核心公式

• 队空：front == rear
• 队满：(rear + 1) % MAXLEN == front
• 入队：rear = (rear + 1) % MAXLEN
• 出队：front = (front + 1) % MAXLEN
• 元素个数：(rear - front + MAXLEN) % MAXLEN
• 队满时元素数 = MAXLEN - 1（牺牲一个单元）

注意：数组大小为 A[0..m] 时，容量为 m+1。入队操作为 rear = (rear+1) % (m+1)。

5. 队列的基本概念

• 操作原则：先进先出（FIFO）。
• 限定在端点（两端）进行操作：一端插入（队尾），一端删除（队头）。
• 队满时 rear == MAXLEN - 1（非循环顺序队列）或 (rear+1) % MAXLEN == front（循环队列）。
• 顺序队列入队不改变front，只改变rear。
• 链队列不会出现队满（动态内存分配）。

---

四、串

1. 串的定义

• 串是零个或多个字符组成的有限序列，数据元素只能是单个字符，是一种特殊的线性表。
• 串长度 = 串中字符的总个数（不是不同字符的个数）。
• 空串（长度为0）≠ 空格串（长度=空格个数）。

2. 子串与子串个数

• 子串：串中任意个连续的字符组成的子序列。
• 空串是任意串的子串。
• 长度为n的串，子串总数 = n(n+1)/2 + 1（含空串）。
  • 例（第13题）：S="abcdef"，n=6，子串总数 = 6×7/2 + 1 = 22。

3. 串的基本操作

• StrLength(S)：求串长（\0不计入长度）。例："A:/doc/Mary.doc" 长度15（逐个字符数），"A:/Mary.doc" 长度11。
• SubStr(S, pos, len)：从第pos位取len个字符。位置从1开始计。
• 字符定位：返回字符在串中首次出现的位置。

---

五、数组与广义表

1. 数组的存储

• 数组是顺序存储的线性结构（一维数组各元素连续存储，二维数组按行或列展开为一维）。
• 存储方式：行序优先、列序优先两种。
• 数组一定是线性结构。

2. 二维数组地址计算（通用公式）

(1) 按行优先存储 若行下标范围 r₁~r₂，列下标范围 c₁~c₂，行数 = r₂-r₁+1，列数 = c₂-c₁+1。 元素 a[i][j] 前面有： (i - r₁) × 列数 + (j - c₁) 个元素。

地址：LOC(a[i][j]) = 基地址 + [(i-r₁)×列数 + (j-c₁)] × 元素大小

(2) 按列优先存储 元素 a[i][j] 前面有： (j - c₁) × 行数 + (i - r₁) 个元素。

地址：LOC(a[i][j]) = 基地址 + [(j-c₁)×行数 + (i-r₁)] × 元素大小

例（第35题）：A[0…8][1…5]，4字节，A[0][1]地址=0。

• 行数=9，列数=5（1到5共5列）。
• 最后一个元素为A[8][5]，按行优先，前面有 (8-0)×5 + (5-1) = 40+4 = 44 个元素（A[0][1]是第1个，前0个）。
• A[0][1]地址0，则A[8][5]地址 = 0 + 44×4 = 176。
• 按列优先求A[3][5]：前面有 (5-1)×9 + (3-0) = 4×9+3 = 39，地址=39×4=156。
• 按列优先求A[5][3]：前面有 (3-1)×9 + (5-0) = 2×9+5 = 23，地址=23×4=92。

注意：下标起始和数组基地址定义要看清（A[0][1]是第一个元素还是A[0][0]是第一个）。

例（第27题）：A[10][10]（下标0~9），按行优先，a[2][0]地址500，每个3字节，求a[3][3]。

• a[2][0]前有 2×10+0 = 20 个元素，设基地址=500-20×3=440。
• a[3][3]前有 3×10+3=33 个元素，地址=440+33×3=440+99=539。

3. 广义表

• 广义表是线性表的推广，元素可以是原子或子表。
• 表头：第一个元素；表尾：去掉表头后的剩余部分（一定是广义表）。
• Head可取原子或子表，Tail结果永远是广义表。
• 例：((a,b),c,d,e) 表头=(a,b)，表尾=(c,d,e)。

---

六、判断题易错总结

判断内容	正误	要点
数据的逻辑结构是指数据元素之间的逻辑关系	对	元素间关系，非数据项间关系
数据的逻辑结构是指各数据项之间的逻辑关系	错	同上
数据元素是数据的最小单位	错	数据项才是最小单位
数组一定是顺序存储的线性结构	对	数组是顺序存储的线性结构
串和数组都是线性结构	对	二者均属线性结构
链式存储方式可用于随机存储	错	链式存储只能顺序存取
共享顺序栈，当整个栈空间占满时才上溢	对	共享空间全部满才溢出
在栈中允许插入的一端称为栈顶	对	栈顶即操作端
空串就是由空格组成的串	错	空串无任何字符
串长度为串中不同字符的个数	错	是字符总个数，不是不同字符数

---

七、知识速记卡

1. 时间复杂度：取决于问题规模和初态，对数阶看乘法/除法增长，立方阶看三层嵌套。
2. 顺序表：插入移n-i+1，删除移n-i，平均移约n/2。
3. 链栈出栈：s=top; top=top->next;。
4. 循环队列：满(rear+1)%MAXLEN==front，空front==rear，个数取模。
5. 出栈序列：模拟验证，大数出栈后小数必须逆序出。
6. 数组地址：行优先(i×列数+j)×L，列优先(j×行数+i)×L，注意下标起止。
7. 广义表：表头取第一个，表尾取剩余且必带括号。