【课程大纲】
1_0 课程简介 共7页.pptx
2_1绪论 共32页.pptx
2_2线性表-顺序表 共12页.pptx
2_3线性表-链表 共43页.pptx
3_1栈和队列 共29页.pptx
3_2递归和非递归 共22页.pptx
4_1串 共18页.pptx
5_1 数组 共19页.pptx
6_1二叉树 共19页.pptx
6_2森林和哈夫曼树 共15页.pptx
7_1 图（存储、遍历、连通） 共49页.pptx
7_2图（拓扑排序、关键路径、最短路径） 共52页.pptx
8_1集合与查找（静态查找、哈希、二叉排序树、平衡二叉树） 共28页.pptx
8_2集合与查找（B-树） 共12页.pptx
9内排序 共25页.pptx
### 数据结构与算法基础课程知识点概述
#### 一、课程概览
该课程是一门针对C语言和C++编程语言的数据结构与算法基础教程。课程共分为九个主要部分，涵盖了从基本的数据结构如线性表、栈、队列到更复杂的结构如二叉树、图，以及算法设计等内容。
#### 二、串的概念与运算
本节重点讲解串的基本概念、存储表示以及模式匹配算法，具体包括以下几个方面：
1. **串的定义**：串是由零个或多个字符组成的有限序列，通常表示为`s="a1a2...an"`(n≥0)，其中`s`是串名，括起来的字符序列是串的值。每个`ai`可以是字母、数字或其他字符。
2. **串的长度**：串中字符的个数称为串的长度。
3. **子串与主串**：
- 子串：串中任意个连续的字符所组成的子序列。
- 主串：包含子串的串称为主串。
4. **位置**：字符在序列中的序号。
5. **相等**：两个串的长度相等，并且对应位置的字符都相同。
6. **空串与空格串的区别**：空串是指长度为0的串，而空格串是指仅包含空格字符的串。
7. **串与线性表的区别**：
- 串的数据对象约束为字符集。
- 线性表的基本操作大多以“单个元素”为操作对象，而串的基本操作通常以“串的整体”作为操作对象。
8. **串的基本运算**：
- 置空串。
- 判断一个串是否为空串。
- 求一个串的长度。
- 将两个串拼接在一起构成一个新的串。
- 求从串的第i个字符开始连续j个字符所构成的子串。
- 求串S2在串S1中第一次出现的位置。
- 去掉首尾空格。
- 全部大写/全部小写。
- 分割串，得到串数组。
- 和另一个串是否相等。
#### 三、串的存储表示
串的存储表示包括以下几种方式：
1. **定长顺序表示**：适用于固定长度的串。
2. **变长顺序表示**：适用于长度可变的串。
3. **串的块链存储表示**：通过链表的形式存储串，适用于长度不确定的情况。
#### 四、模式匹配算法
模式匹配是串处理中的一个重要内容，主要包括：
1. **定义**：在串中寻找子串（第一个字符）在串中的位置。
2. **术语**：在模式匹配中，子串称为模式，串称为目标。
3. **朴素算法**（穷举法）：逐个字符比较，效率较低。
4. **KMP算法**：
- 由D.E.Knuth、V.R.Pratt和J.H.Morris共同发现。
- 特点：提高了匹配效率，i指针不回溯，利用已匹配的信息定位j指针。
- `next`数组：用于记录模式串的部分匹配信息，帮助优化匹配过程。
#### 五、总结
通过对上述知识点的学习，学生能够深入了解串这一数据结构的基础概念、存储方式以及常见的操作和算法。这些知识不仅有助于理解高级数据结构和算法的设计思想，还能为解决实际问题提供有效的工具。在后续的学习过程中，学生还将接触到更多复杂的数据结构和算法，逐步构建起完整的计算机科学知识体系。
