一、数据结构的三要素学数据结构先记住一个总纲**数据结构 逻辑结构 存储结构 数据的运算**这就是数据结构三要素。搞懂它你就知道顺序表、链表在整张地图上站在什么位置。1.1 逻辑结构数据之间是什么关系逻辑结构logical structure说的是数据元素之间的逻辑关系——只关心谁和谁有关、是什么关系不管数据在内存里怎么放属于抽象层面。常见的有四类- **线性结构**一对一。每个元素最多一个直接前驱、一个直接后继像排队买票一个人后面最多跟一个人。**线性表就属于线性结构**。- **树形结构**一对多。一个父亲可以带多个孩子像家族谱、文件夹目录。- **图形结构**多对多。任意两点之间都可能相连像地铁线路图。- **集合**元素之间没有关系像一袋散装水果。 一句话小结逻辑结构回答数据之间是什么关系线性表是线性结构一对一排队。1.2 存储结构数据“实际怎么放”存储结构storage structure也叫物理结构指数据在计算机内存里实际怎么存放属于实现层面。常见四种顺序存储一块连续的内存格子挨着放像电影院连排座位。**顺序表用的就是它**。链式存储数据不要求挨着每个元素带一个指向下一个的指针串起来。**链表用的就是它**。索引存储额外建一张索引表来找数据像书的目录。散列存储按哈希函数直接算出存放位置像按门牌号找房间。 一句话小结存储结构回答数据在内存里怎么存顺序表用顺序存储链表用链式存储。1.3 数据的运算能对数据干什么数据的运算指对数据能做的操作比如**插入、删除、查找、修改还有求长度、判空等。运算分两个层面看- **定义**由逻辑结构决定只要是线性表逻辑上都支持插入、删除——这是做什么。- **实现**由存储结构决定顺序表靠**挪数据**完成插入链表靠**改指针**完成插入——这是怎么做。 一句话小结数据的运算回答能干什么做什么由逻辑结构定怎么做由存储结构定。1.4 线性表Linear List线性表Linear List是 nn≥0个**同类型**数据元素的**有限序列**。白话解释一串排好队的数据有先后顺序——第一个元素没有前驱最后一个元素没有后继其余每个元素都有且仅有一个直接前驱和一个直接后继。补充n1 时唯一元素既是第一个又是最后一个既无前驱也无后继n0 时是空表一个元素都没有。两个关键点- **线性表是逻辑结构**是抽象概念本身不关心数据在内存里怎么放。- 线性表的基本运算插入、删除、查找、求长度、判空等是逻辑层面的约定。 一句话小结线性表是抽象的一串排队数据只管逻辑关系不管怎么存。1.5 三者关系线性表、顺序表、链表线性表逻辑结构一对一排队│├──用顺序存储实现→顺序表连续格子└──用链式存储实现→链表指针串联用表格对照更清楚| 概念 | 属于三要素中的哪个 | 一句话解释 ||------|------------------|-----------|| 线性表 | 逻辑结构 | 抽象的一串数据不管怎么存 || 顺序表 | 存储结构顺序存储 | 线性表用连续内存实现 || 链表 | 存储结构链式存储 | 线性表用指针串联实现 || 插入/删除/查找 | 数据的运算 | 逻辑上都要支持实现方式不同 |再记两个关键点a. **同一个逻辑结构可以用不同存储结构实现**线性表既能用顺序存储做成顺序表也能用链式存储做成链表——就像排队这个抽象概念可以排成电影院的连续座位顺序也可以排成寻宝线索链式。b. **运算的做什么和怎么做是分开的**同样是插入一个元素顺序表要挪数据O(n)链表只改指针O(1)——目标一样手段不同。 一句话小结线性表是抽象概念顺序表、链表是它的两种具体实现。二、顺序表2.1 顺序表是什么顺序表Sequential List就是用数组array一块连续的内存区域来存数据。数组里的每一个格子是一块内存空间格子与格子之间紧紧挨着就像电影院连成一排的座位2.2 内存长什么样内存格子示意一格存一个数据┌────┬────┬────┬────┬────┬────┐│ 10 │ 20 │ 30 │ 40 │ 50 │ │└────┴────┴────┴────┴────┴────┘下标 0 1 2 3 4 5下标index就是第几个格子的编号从 0 开始数。想取第 3 个数据直接写 data[2] 就行一步到位。2.3 结构体定义3.3 结构体定义 c #define MAX 100 // 定义常量 MAX 100表示最多存 100 个数据 typedef struct { // typedef 是给结构体类型起个简短的名字 int data[MAX]; // data真正存数据的数组相当于一排座位 int length; // length当前已经存了多少个有效数据相当于已经坐了几个人 } SeqList; // 这个结构体的名字叫 SeqList - data存数据的地方容量固定是 MAX 个格子。 - length记录现在有几个有效数据插入删除后都要修改它。2.4 三个核心操作2.4.1: (a) 插入 insert为什么中间插入要挪数据因为格子是连续的新数据要挤进去后面的数据必须整体往后让位置。为什么必须**从后往前**挪如果从前往后挪第一个数据先把第二个覆盖了第二个原样就丢了后面全部乱套。从最后一个开始往前挪每挪一个覆盖掉的都是已经挪走、没用了的位置数据才不会丢。// 在顺序表的第 pos 个位置插入值 xpos 从 1 开始数 void insert(SeqList *L, int pos, int x) { int i; // i 是循环用的计数器 if (L-length MAX) return; // 表满了插不进去直接返回 if (pos 1 || pos L-length 1) return; // 位置不合法注意最后可以插在末尾 for (i L-length - 1; i pos - 1; i--) { L-data[i 1] L-data[i]; // 从最后一个开始逐个往后挪一格 } L-data[pos - 1] x; // 空出来的位置放入新值 x L-length; // 有效数据多了一个length 加 1 }2.4.2:(b) 删除 delete删除就是往前覆盖被删位置后面的数据一个个往前挪一格把被删的数据盖掉length 再减一。// 删除顺序表第 pos 个位置的数据函数名用 deleteElem 而不是 delete void deleteElem(SeqList *L, int pos) { int i; if (pos 1 || pos L-length) return; // 位置不合法空表或超出范围返回 for (i pos - 1; i L-length - 1; i) { L-data[i] L-data[i 1]; // 后面的数据往前覆盖一格 } L-length--; // 有效数据少了一个length 减 1 }说明标准 C 语言里 delete 不是关键字写成 void delete(...) 用 C 编译器编译是能通过的。但它同时是 C 的关键字——初学者如果把文件存成 .cpp 或用 C 编译器编译就会报错所以教程里改名 deleteElem 更稳妥。2.4.3:(c) 查找 search按下标访问是 O(1)一步到位但**按值查找**没有捷径只能从第 0 个开始一个一个比。// 查找值为 x 的数据找到了返回下标找不到返回 -1 int search(SeqList *L, int x) { int i; for (i 0; i L-length; i) { // 从下标 0 到最后一个逐个遍历 if (L-data[i] x) return i; // 找到相等的值返回它的下标 } return -1; // 全部找完都没有返回 -1 表示没找到 }2.5 优点和缺点- **优点**读得快。按下标直接访问一步到位时间复杂度 O(1)。- **缺点**写插入、删除得慢因为要挪一大片数据时间复杂度 O(n)而且空间大小固定一开始就要定好 MAX——存少了浪费存多了装不下。 一句话小结顺序表读快写慢、空间固定适合存数量固定、以查询为主的数据。三、单链表3.1 单链表是什么链表Linked List链表里的每个数据叫**结点Node)**。一个结点有两部分**数据域**存数据和**指针域**存下一个结点在哪里的地址。结点之间用指针pointer存内存地址的变量串起来像珠子穿在一条线上。3.2 结点结构体typedef struct Node { // 结构体里要用到自身所以这里必须写 struct Node int data; // 数据域存一个整数 struct Node *next; // 指针域存下一个结点的地址 } Node; // 别名 Node 在这一行才生效为什么 next 必须写 struct Node *因为结构体还在定义中自己的名字 Node这个别名要到右花括号之后才生效所以内部引用自己时只能用完整的 struct Node 来声明指针。3.3 链表长什么样head头结点不存数据只当起点│▼┌────┬─────┐ ┌────┬─────┐ ┌────┬─────┐│ 10 │ ───────►│ 20 │ ───────►│ 30 │ NULL │└────┴─────┘ └────┴─────┘ └────┴─────┘数据 指针 数据 指针 数据 指针最后一个结点的 next 指向 NULLC 语言里表示空地址意思是后面没有了。链表一般带一个**头结点**上图的 head它不存数据只用来标记起点——这样在第一个位置做插入删除时就不用单独写一套特殊逻辑了。带头结点的空链表是这样创建的Node *head (Node *)malloc(sizeof(Node)); // 申请头结点 head-next NULL; // 头结点后面暂时没有结点这就是空链表——头结点存在但后面一个数据结点都没有练习 3 的答案就基于这个。3.4 核心操作3.4.1(a) 头插法建表**头插法**新结点永远插在头结点后面也就是每次插到最前面。关键就是两条赋值语句顺序不能反// 在链表头部插入一个新结点数据为 x Node *headInsert(Node *head, int x) { Node *p (Node *)malloc(sizeof(Node)); // malloc 申请一块新结点的内存实际代码应检查 p NULL这里省略以突出重点 p-data x; // 新结点的数据域放 x p-next head-next; // 第一步先连后面新结点指向原来的第一个结点 head-next p; // 第二步再连前面头结点指向新结点 return head; // 返回头结点 }为什么顺序不能反如果先执行 head-next p头结点就先指向新结点了而原来第一个结点的地址没有存下来链表就断了后面的结点全找不到了。所以必须**先连后面再连前面**先让新结点抓住原来的第一个再让头结点放开、指向新结点。就像换绳子要先挂好新的一头再解旧的一头。3.4.2(b) 尾插法建表头插法每次都插在最前面所以建好的链表顺序是反的。想保持原顺序就用**尾插法**用一个**尾指针 tail**始终跟在最后一个结点后面。// 在链表尾部插入一个新结点数据为 x Node *tailInsert(Node *head, int x) { Node *p (Node *)malloc(sizeof(Node)); // 申请新结点实际代码应检查 p NULL这里省略以突出重点 p-data x; // 数据域放 x p-next NULL; // 新结点将是最后一个next 指向 NULL Node *tail head; // tail 从头开始负责找尾巴 while (tail-next ! NULL) // 只要 next 不是 NULL 就继续走 tail tail-next; // 一步一步往后走 tail-next p; // 找到最后一个了让它指向新结点 return head; // 返回头结点 }3.4.3(c) 在指定结点后插入在结点 p 后面插入新结点 s同样是先连后面、再连前面s-next p-next; // 第一步s 先指向 p 原来的下一个结点 p-next s; // 第二步p 再指向 s3.4.4 (d) 删除结点删除 p 的下一个结点就是跳过它让 p 直接连到下下个再把被删结点 free释放内存还给操作系统Node *q p-next; // q 指向要被删的那个结点 p-next p-next-next; // p 跳过 q直接连到 q 的下一个 free(q); // 把 q 占用的内存释放掉3.4.5(e) 遍历遍历traverse: 就是把链表从头到尾走一遍。用一个指针 p从第一个结点出发每走一步 p p-next直到 p NULL 说明走完了// 打印链表里所有结点的数据 void printList(Node *head) { Node *p head-next; // p 从第一个真正存数据的结点开始 while (p ! NULL) { // 只要 p 不是空地址就继续 printf(%d , p-data); // 打印当前结点的数据 p p-next; // p 走到下一个结点 } printf(\n); // 全部打完换一行 }3.5 优点和缺点- **优点**写插入、删除快只要改指针时间复杂度 O(1)前提是已持有插入/删除位置的指针空间**按需分配**用到多少就 malloc 多少不会浪费也不会装不下。- **缺点**读查找慢没有下标只能从头一个结点一个结点走时间复杂度 O(n)每个结点还要额外存一个指针多占内存。 一句话小结链表写快读慢、空间灵活适合频繁插入删除、数据量不固定的场景。四、顺序表 vs 单链表对比总结| 维度 | 顺序表 | 单链表 ||--------------|-----------------------------------------|-------------------------------------------|| 访问速度 | 按下标直接访问快O(1) | 必须从头一个个走慢O(n) || 插入删除 | 要挪一大片数据慢O(n) | 只改指针快O(1)前提是已持有位置指针 || 空间 | 固定大小一次性分配 | 按需分配用多少申请多少 || 适用场景 | 查得多、改得少、数据量固定 | 改得多、查得少、数据量不定 |五、练习题1. **逆序输出**单链表的所有结点值。提示可以写一个递归函数先处理后面的结点再打印当前的也可以先遍历一遍存进数组再倒着打印。2. 在顺序表的第 k 个位置插入值 x。想一想k 的合法范围是什么插入前需要做哪两个判断3. 编写一个函数判断单链表是否为空。提示空链表就是头结点后面没有结点。 最后再记一句顺序表和链表是数据结构的两个基本盘——顺序表用连续换速度链表用线索换灵活。两种都要会做题面试都常用。