大学程序设计与算法语言《数组与字符串》复习课件

数组与字符串复习程序设计与算法语言2026课程导览01数组基础概念与存储模型02字符串基础表示与基本操作03遍历与查找核心操作与算法04排序算法经典排序与复杂度05多维数组矩阵与高维结构06字符串处理进阶常用函数与算法07动态内存与数组动态分配与指针数组08综合应用与复习知识点串联与题型01数组基础从连续存储开始理解数组数组的定义与存储模型连续存储是数组的根本特征：相同数据类型的元素有序排列，占据一段连续内存。收束：定长与越界是数组使用中必须时刻警惕的两条铁律。数组的四个核心特征随机访问首地址+下标

×

元素大小，一次计算直接定位任意元素。下标从0开始多数语言的约定；越界会读写数组之外的内存，轻则数据错乱，重则程序崩溃。定长约束声明时须确定元素类型与容量，容量一经确定不能随意改变。连续存储相同数据类型的有序排列，占据一段连续内存。一维数组的声明与引用声明三要素：类型名、数组名、长度。初初始化规则规则一花括号列表赋值，未赋值元素自动置零。规则二列表元素少于长度→剩余补零规则三多于长度→报错循引用与遍历下标须合法，可为变量，常与循环配合。for

循环变量充当下标，从首元素依次访问至末元素。统一模式求和求最值统计个数均可归结为

遍历加判断。数组的边界与易错点问题长度为10的数组合法下标是

0–9，写

10

或用负数寻址即越界。语言环境常不强制检查，越界可能暂不报错，却悄悄破坏相邻内存。表现为结果偶发异常、极难排查。对策编写循环时盯紧终止条件，避免“少遍历一个”或“多访问一个”。下标表示位置，元素值表示存储的数据，二者含义完全不同。02字符串基础字符序列的存储与操作字符与字符串的关系字符是单个存储单元，字符串是连续字符序列——本质是以特殊标记结尾的字符数组。记住字符串的结束标记，才能避免读过头字符串的存储与边界C风格字符串以空字符作结束标志，系统靠扫描它判断终点内存占用长度

n

的字符串实际占用

n+1

个存储单元漏留结束标记后续操作可能读过头，处理到字符串之外的内容字符串常量双引号包裹，在内存中同样自带结束标记C风格字符串的操作用格式说明符直接处理，系统自动维护结束标记。—C风格字符串核心手工实现虽繁琐，却让“字符串就是字符序列”这一本质真正落地。整体输入输出用格式说明符直接处理，系统自动维护结束标记。三个手工操作01求长度从头扫描到结束标记，统计步数02复制逐字符搬运，最后补上结束标记03比较逐字符比对，不能直接比数组名——数组名是地址，不是内容string类型的基本用法问题→对策对初学者而言，string屏蔽底层细节，把重点从“如何管理内存”转向“如何解决问题”。字符数组手工管理内存与边界：赋值、拼接、比较都要借助库函数易越界、易出错：赋值与拼接需谨慎处理比较大小：需手工调用函数读取内容：需手工控制数组边界访问字符：需管理下标并注意边界string类型封装成对象，自动管理内存与长度赋值与拼接：直接使用=与+，语义直观比较大小：直接使用比较运算符判断读取内容：可直接输入一行或一段访问字符：可通过下标完成，并提供获取长度的成员函数VS03遍历与查找从线性扫描到高效查找线性遍历的基本模式遍历中维护一个“当前结果”，每遇新元素按规则更新，循环结束即得答案。统一框架从首元素出发，按固定步长依次访问循环变量充当下标，批量处理皆可套用三类任务，同一内核求和每个元素累加进累积变量统计判断条件成立即计数求最值先取首元素为当前最大，再逐一比较更新查找算法的两种思路数据组织方式，决定算法选择。顺序查找线性扫描比较方式从头到尾逐个比对目标适用前提数据无需有序、支持顺序访问时间代价与元素个数成正比，最坏情况需比较全部典型场景无序小数据集、简单实现优先二分查找减半缩围比较方式每次取中间元素与目标比较，按大小缩小范围适用前提数据有序且支持随机访问时间代价每轮减半，效率大幅提升典型场景有序大数据集、查询频繁04排序算法比较与交换背后的算法思想冒泡排序与选择排序同为

O(n²)

的经典入门排序：冒泡排序与选择排序，用“相邻交换”与“挑最小前置”两种思路完成排序。两者均直观、易实现，适合入门理解排序过程；时间复杂度同为

O(n²)，数据规模较大时效率明显不足；适用场景：小规模数据或教学演示。冒泡排序相邻元素反复比较与交换，每轮把当前未排序区间的最大元素“浮”到末尾；逐轮缩小未排序区间，直至整体有序。选择排序每轮从未排序区间挑出最小元素，与区间首位交换，逐步划出已排序前缀。插入排序与快速排序思想理解快排的分治框架，是打开高效算法之门的关键一步。插入排序：模拟整理扑克牌数组分为已排序前缀与未排序后缀每次取后缀首元素，插入前缀正确位置数据接近有序时表现很好快速排序：分治思想选取基准元素，一趟划分成小于/大于两部分递归排序两部分大范围交换避免逐对比较，平均效率远高于基础算法排序算法的比较与选择两个维度：时间复杂度与稳定性。复杂度分档冒泡、选择、插入：均为元素个数的平方级别冒泡与插入在数据基本有序时可提前结束，表现更优快速排序：平均为元素个数与对数之积量级，适合大规模数据稳定性指排序后相等元素的相对顺序是否保持不变在多关键字排序中很重要快速排序稳定性不如前三者选择依据小规模数据：直接调用简单算法即可大规模数据：优先考虑快速排序或语言内置的高效排序实现05多维数组从一维到二维的思维跃迁二维数组的结构与存储逻辑结构数组的数组由行与列构成表格元素需行下标与列下标共同定位物理存储一段连续空间按行优先存放第一行元素依次排完，紧跟第二行，依此类推地址可计算给定行数、列数、元素大小任意元素的内存地址可直接算出随机访问特性保留遍历对应外层循环控制行内层循环控制列正是行优先存储的直接体现二维数组的初始化与遍历双重循环是解决矩阵类程序问题的基本功。初始化嵌套花括号列表嵌套花括号列表，外层对应行、内层对应列；未列出元素自动补零。遍历模板双重循环外层循环控行、内层循环控列，依次访问每个元素。求矩阵元素总和定位最大值所在行列坐标按列优先处理：交换内外层循环职责，访问顺序与按行存储的内存布局不完全一致矩阵运算与高维扩展无论维度多高，核心都是下标顺序与内存布局的对应关系。无论维度多高，核心都是下标顺序与内存布局的对应关系。矩阵相加行列数相同，对应位置元素相加，结果仍为同型矩阵。矩阵转置行与列互换，原矩阵第i行第j列元素，转到新矩阵第j行第i列。下标控制两者实现都归结为行列下标的精确控制。三维数组可看作“数组的二维数组”，用三个下标定位。存储顺序存储按层、行、列顺序连续排列。06字符串处理进阶库函数与模式匹配常用字符串处理函数在字符串处理中，基础操作与安全边界是两条并行的主线。理解函数的行为边界，比单纯记住函数名更重要。四类基础操作求长度获取字符串中字符的个数复制把源串内容逐个搬运到目标位置连接在目标串末尾追加源串内容比较按字符编码逐一对位，返回大小关系查找定位子串、提取子串等实用功能安全边界安全边界目标空间容量是否足够、长度参数是否准确，决定是否越界。字符串的模式匹配核心思想：利用已匹配的信息，不做无谓回退两串长度之积朴素匹配·最坏比较次数线性量级KMP改进·比较次数朴素匹配2项原理主串每个位置逐一比对，失配就整体后移一位重来代价最坏比较次数接近两串长度之积KMP改进2项原理预处理子串，记录失配后可回退的位置优势主串指针不再反复回退，比较次数降至线性量级07动态内存与数组让数组大小随需而变动态分配数组动态数组的指针与长度需分开管理，比定长数组多一分责任，也换来宝贵的灵活性。问题→对策

定长数组容量编译期确定，无法按运行时数据规模调整。

动态分配运行时按需申请连续内存，返回首地址，数据量多大申请多大。动态分配C++用

new

配合指针完成动态数组创建。动态分配3项创建C++用

new

配合指针完成动态数组创建释放使用完毕必须

delete，把内存归还系统风险忘记释放→内存泄漏；重复释放或释放后继续使用→未定义行为指针数组与内存管理构造方式：先建指针数组存放各行首地址，再为每行单独申请内存，形成锯齿形二维结构。动态内存带来自由，也要求对每块内存的生命周期心中有数。构造方式原理先建指针数组存放各行首地址结构再为每行单独申请内存，形成锯齿形二维结构优势节省空间释放顺序第1步先逐行释放每块行内存第2步最后释放指针数组本身注意顺序不可颠倒：先释放指针数组后，行指针便无从访问；漏放某行则造成内存泄漏12308综合应用与复习融会贯通，从容应考知识串联与典型题型

解题入口先明确数据如何存储，再选遍历方式与算法，主线就不会散。一条主线连续存储加下标定位——数