数据结构与算法基础课程 C语言C++程序语言设计教程 4_1串 共18页.pptx

【课程大纲】 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`数组：用于记录模式串的部分匹配信息，帮助优化匹配过程。 #### 五、总结 通过对上述知识点的学习，学生能够深入了解串这一数据结构的基础概念、存储方式以及常见的操作和算法。这些知识不仅有助于理解高级数据结构和算法的设计思想，还能为解决实际问题提供有效的工具。在后续的学习过程中，学生还将接触到更多复杂的数据结构和算法，逐步构建起完整的计算机科学知识体系。