黔西南布依族苗族自治州网站建设_网站建设公司_关键词排名_seo优化

📚 目录（TOC）

• 第 1 节：数据结构三要素（逻辑结构 / 存储结构 / 运算）

• 第 2 节：线性表（定义、前驱后继、下标与边界）

• 第 3 节：顺序表（连续存储、随机访问与地址规律）

• 第 4 节：顺序表数据结构设计（data[] + last）

• 第 5 节：顺序表基本运算实现（增删查等）

• 第 6 节：典型综合算法（并集、去重）

• 今日学习总结

第 1 节：数据结构三要素（逻辑结构 / 存储结构 / 运算）

核心总结

数据结构可拆成三部分：逻辑结构、存储结构、运算。
逻辑结构描述“元素关系”，存储结构描述“内存落地方式”，运算描述“如何操作数据”。
后续学习任何结构都可按这三点逐项落地到代码。

讲解内容

• 逻辑结构：元素之间的关系是什么（线性、树形、图形等）。

• 存储结构：关系如何放进内存（顺序存储连续、链式存储通过指针连接等）。

• 运算：提供哪些操作（创建、插入、删除、查找、合并、去重等）。

• 关键区分：同一种逻辑结构可以有不同的存储实现；不要把“线性表”和“顺序表”混为一个概念。

示例代码

#include <stdio.h> int main(void) { // Data Structure = Logical Structure + Storage Structure + Operations puts("Data Structure = Logical Structure + Storage Structure + Operations"); puts("Example: Linear List (logical) can be implemented by array (sequential) or pointer links (linked)."); return 0; }

输出说明

程序输出三要素拆分方式与一句线性表实现方式的说明，用于建立概念框架。

错误示例

把“线性表”直接等同于“顺序表”。

错误原因分析

线性表是逻辑结构（关系是线性的）；顺序表是存储实现（连续内存）。概念层级不同。

正确写法

使用“线性表（逻辑）→ 顺序表/链表（存储实现）”的表述方式。

第 2 节：线性表（定义、前驱后继、下标与边界）

核心总结

线性表是有序序列，除首尾外每个元素都有且仅有一个直接前驱和一个直接后继。
实现中边界最重要：空表、首元素、尾元素、合法下标范围。

讲解内容

• 线性表可写为：L = (a0, a1, ..., a(n-1))，n为表长；n=0为空表。

• 前驱/后继：

  • a0无前驱

  • a(n-1)无后继

  • 中间元素前驱唯一、后继唯一

• 代码层面的“边界”通常表现为：下标是否合法、空表是否允许操作。

示例代码

#include <stdio.h> int main(void) { int a[] = {10, 20, 30, 40}; int n = (int)(sizeof(a) / sizeof(a[0])); // Access by index (logical order) printf("n=%d, head=%d, tail=%d\n", n, a[0], a[n-1]); for (int i = 0; i < n; i++) { printf("a[%d]=%d\n", i, a[i]); } return 0; }

输出说明

输出表长、表头元素、表尾元素，并按逻辑顺序遍历打印，体现“线性序列”的访问方式。

错误示例

下标越界访问：

int x = a[n]; // 错误：最大下标是 n-1

错误原因分析

C 数组下标范围固定为[0, n-1]，访问a[n]属于越界，结果不可靠。

正确写法

int x = a[n-1]; // 访问尾元素

第 3 节：顺序表（连续存储、随机访问与地址规律）

核心总结

顺序表把线性表元素存放在一段连续内存中。
连续存储带来 O(1) 随机访问，但插入/删除通常需要搬移元素。

讲解内容

• 连续存储：元素按逻辑顺序挨着放，地址满足固定步长增长。

• 随机访问：可通过下标直接定位第i个元素（本质是“基址 + 偏移”）。

• 代价：在中间插入/删除时，后续元素需要整体移动，成本随表长增长。

示例代码

#include <stdio.h> #include <stdint.h> int main(void) { int a[] = {1, 2, 3, 4}; for (int i = 0; i < 4; i++) { printf("&a[%d]=%p\n", i, (void*)&a[i]); } // Verify fixed stride (usually sizeof(int)) uintptr_t d1 = (uintptr_t)&a[1] - (uintptr_t)&a[0]; uintptr_t d2 = (uintptr_t)&a[2] - (uintptr_t)&a[1]; printf("stride1=%lu, stride2=%lu, sizeof(int)=%lu\n", (unsigned long)d1, (unsigned long)d2, (unsigned long)sizeof(int)); return 0; }

输出说明

打印每个元素地址，并输出相邻地址差值（通常等于sizeof(int)），用于直观看到“连续 + 固定步长”。

错误示例

把“线性表必须连续存储”当作结论。

错误原因分析

连续存储是“顺序表”的要求，不是“线性表”的通用要求；线性表也可以用非连续存储（例如指针链接）实现。

正确写法

结论应为：线性表是逻辑结构；顺序表是线性表的一种连续存储实现。

第 4 节：顺序表数据结构设计（data[] + last）

核心总结

顺序表常用结构：数组data[]保存元素，last保存“最后有效下标”。
约定last=-1表示空表，表长为last+1。

讲解内容

• data[]：连续存储空间（容量固定或可扩容）。

• last：最后一个有效元素的位置：

  • 空表：last = -1

  • 非空：有效区间为[0, last]

• 好处：边界检查直观、求长 O(1)，适合实现插入/删除/定位等运算。

示例代码

#include <stdio.h> #define N 8 typedef int data_t; typedef struct { data_t data[N]; int last; // -1 means empty } sqlist; int main(void) { sqlist L = {.last = -1}; printf("empty=%s, length=%d\n", (L.last == -1) ? "YES" : "NO", L.last + 1); // tail insert (manual) L.data[++L.last] = 42; printf("empty=%s, length=%d, head=%d\n", (L.last == -1) ? "YES" : "NO", L.last + 1, L.data[0]); return 0; }

输出说明

先输出空表状态与长度，再模拟一次尾插，验证last与长度/访问方式的一致性。

错误示例

把空表写成last=0：

sqlist L = {.last = 0}; // 错误：这会被当成有 1 个元素

错误原因分析

last表示“最后有效下标”。若last=0，代码会认为[0..0]有一个元素，空表判断会失效。

正确写法

sqlist L = {.last = -1}; // 空表

第 5 节：顺序表基本运算实现（增删查等）

核心总结

顺序表的基本运算包括：创建/清空/判空/求长/取元素/定位/插入/删除。
实现重点是：下标范围校验、插入搬移方向、删除后的覆盖与更新last。

讲解内容

• 判空：last == -1

• 求长：last + 1

• 取元素：下标必须在[0, last]

• 定位：顺序扫描找到首次出现的位置

• 插入：将[i..last]整体后移一位（必须从后往前搬移）

• 删除：将[i+1..last]整体前移覆盖，再last--

示例代码

#include <stdio.h> #define N 10 typedef int data_t; typedef struct { data_t data[N]; int last; } sqlist; void list_create(sqlist *L) { L->last = -1; } int list_empty(const sqlist *L) { return (L->last == -1); } int length(const sqlist *L) { return L->last + 1; } int locate(const sqlist *L, data_t x) { for (int i = 0; i <= L->last; i++) if (L->data[i] == x) return i; return -1; } int insert(sqlist *L, data_t x, int i) { if (L->last >= N - 1) return 0; // full if (i < 0 || i > L->last + 1) return 0; // 0..last+1 for (int k = L->last; k >= i; k--) { // move backward L->data[k + 1] = L->data[k]; } L->data[i] = x; L->last++; return 1; } int delete_at(sqlist *L, int i, data_t *deleted) { if (i < 0 || i > L->last) return 0; if (deleted) *deleted = L->data[i]; for (int k = i; k < L->last; k++) { L->data[k] = L->data[k + 1]; } L->last--; return 1; } static void dump(const sqlist *L, const char *tag) { printf("%s(len=%d): ", tag, length(L)); for (int i = 0; i <= L->last; i++) printf("%d ", L->data[i]); puts(""); } int main(void) { sqlist L; list_create(&L); insert(&L, 10, 0); insert(&L, 20, 1); insert(&L, 15, 1); // insert in middle dump(&L, "after inserts"); data_t del = 0; delete_at(&L, 1, &del); printf("deleted=%d\n", del); dump(&L, "after delete"); printf("empty=%d, locate(20)=%d\n", list_empty(&L), locate(&L, 20)); return 0; }

输出说明

• 插入后顺序应体现“中间插入导致后续右移”。

• 删除后顺序应体现“后续左移覆盖”。

• deleted输出用于验证删除目标正确。

错误示例

插入时从前往后搬移（会覆盖数据）：

for (int k = i; k <= L->last; k++) { // 错误方向 L->data[k + 1] = L->data[k]; }

错误原因分析

插入需要整体右移，如果从前往后搬，会先覆盖尚未搬走的源元素，造成数据丢失。

正确写法

for (int k = L->last; k >= i; k--) { // 从后往前搬 L->data[k + 1] = L->data[k]; }

第 6 节：典型综合算法（并集、去重）

核心总结

综合算法通常由“定位 + 插入/删除”组合而成。
并集：把Lb中不在La的元素追加进La。
去重：对每个元素，删除后续重复项；删除后索引推进策略必须正确。

讲解内容

• 并集（La ∪ Lb ⇒ La）：遍历Lb，对每个x做locate(La,x)，不存在则尾插。

• 去重：双层扫描；当删除发生时，当前位置会被新元素覆盖，所以“删除后不能直接 j++”。

• 两者性能直觉：都包含线性扫描与搬移，表长增大会更慢。

示例代码

#include <stdio.h> #define N 20 typedef int data_t; typedef struct { data_t data[N]; int last; } sqlist; void list_create(sqlist *L) { L->last = -1; } int length(const sqlist *L) { return L->last + 1; } int locate(const sqlist *L, data_t x) { for (int i = 0; i <= L->last; i++) if (L->data[i] == x) return i; return -1; } int insert(sqlist *L, data_t x, int i) { if (L->last >= N - 1) return 0; if (i < 0 || i > L->last + 1) return 0; for (int k = L->last; k >= i; k--) L->data[k + 1] = L->data[k]; L->data[i] = x; L->last++; return 1; } int delete_at(sqlist *L, int i) { if (i < 0 || i > L->last) return 0; for (int k = i; k < L->last; k++) L->data[k] = L->data[k + 1]; L->last--; return 1; } int list_union(sqlist *La, const sqlist *Lb) { int inserted = 0; for (int i = 0; i <= Lb->last; i++) { data_t x = Lb->data[i]; if (locate(La, x) == -1) { if (!insert(La, x, La->last + 1)) break; // tail insert inserted++; } } return inserted; } int remove_duplicates(sqlist *L) { int removed = 0; for (int i = 0; i <= L->last - 1; i++) { int j = i + 1; while (j <= L->last) { if (L->data[j] == L->data[i]) { delete_at(L, j); // do NOT j++ removed++; } else { j++; } } } return removed; } static void dump(const sqlist *L, const char *tag) { printf("%s(len=%d): ", tag, length(L)); for (int i = 0; i <= L->last; i++) printf("%d ", L->data[i]); puts(""); } int main(void) { sqlist La, Lb; list_create(&La); list_create(&Lb); // La = 1 2 3 3 4 insert(&La, 1, 0); insert(&La, 2, 1); insert(&La, 3, 2); insert(&La, 3, 3); insert(&La, 4, 4); // Lb = 3 4 5 insert(&Lb, 3, 0); insert(&Lb, 4, 1); insert(&Lb, 5, 2); dump(&La, "La"); dump(&Lb, "Lb"); remove_duplicates(&La); dump(&La, "La after dedup"); list_union(&La, &Lb); dump(&La, "La after union"); return 0; }

输出说明

典型现象应为：

• La after dedup中重复的3被删除，仅保留一个。

• La after union会包含5（因为5不在原La中）。

错误示例

去重时删除后仍j++，导致漏删：

if (L->data[j] == L->data[i]) { delete_at(L, j); j++; // 错误：会跳过新搬到 j 的元素 }

错误原因分析

顺序表删除会导致后续元素左移覆盖。删除后j位置已经是“新元素”，若立刻j++会漏检。

正确写法

if (L->data[j] == L->data[i]) { delete_at(L, j); // 删除后不递增 j } else { j++; }

今日学习总结

• 数据结构可按“逻辑结构、存储结构、运算”三要素拆解，避免概念混淆。

• 线性表描述线性关系；顺序表是线性表的连续存储实现，支持随机访问但插入/删除通常需要搬移。

• 顺序表实现的关键在边界控制：合法下标、空表/满表、插入搬移方向、删除后的索引推进策略。