北京大学《计算概论》课件：ch14c语言编程应用

C语言编程应用北京大学《计算概论》第十四讲·信息科学技术学院Contents课程目录北京大学《计算概论》ch14—C语言编程应用课程纲要01C语言基础语法回顾02核心数据结构详解03编程实战：二维数组回形遍历04计算思维与课程总结CHAPTER01C语言基础语法回顾从数据类型到函数，夯实编程基本功Chapter14·CLanguage基本数据类型与存储C语言的数据类型决定了变量在内存中的存储方式和取值范围。合理选择数据类型不仅能优化内存使用，还能避免溢出错误，是编写健壮程序的基础。01整型家族char（1字节，-128~127）、short（2字节）、int（4字节，约±21亿）、longlong（8字节），选择时需考虑数值范围。int·4字节·±21亿02浮点类型float（4字节，7位有效数字）与double（8字节，15位有效数字），精度敏感场景必须用double避免舍入误差。double·15位精度03字符与字符串char存储单个ASCII字符，字符串本质是字符数组并以'\0'结尾，处理时需注意缓冲区边界。'\0'·缓冲区边界04类型转换陷阱隐式转换可能导致精度丢失或符号错误，如int转float会损失精度，负数转unsigned会得到意外大数。int→float·精度丢失CHAPTER14·编程应用控制结构与流程管理条件判断和循环是程序逻辑的核心载体。掌握各类控制结构的特点和适用场景，并养成检查边界条件的习惯，是避免逻辑错误的关键。条件判断if-else适合二分支逻辑，switch适合多分支等值判断；注意if后误加分号导致条件失效、switch漏写break造成穿透if·switch二分支/多分支等值for循环适合已知迭代次数的场景，初始化、条件、步进三个表达式清晰分离；注意循环变量边界，避免off-by-one错误for已知次数迭代while与do-whilewhile先判断后执行，do-while保证至少执行一次；处理用户输入或文件读取时，while循环更为自然while条件驱动迭代循环控制break立即跳出循环，continue跳过本次迭代；嵌套循环中使用标签可精确控制跳出层级，但应谨慎使用以保持可读性break·continue流程跳转控制CHAPTER14·CLANGUAGE函数定义与模块化编程函数是C语言实现代码复用和逻辑抽象的核心机制。理解参数传递方式、变量作用域和函数声明规则，是编写结构清晰、可维护程序的基础。01值传递机制C语言函数参数默认按值传递，形参是实参的副本；若需修改实参或传递大型结构体，应使用指针传递避免拷贝开销。指针传递直接操作内存地址，效率高且能实现双向数据交换。02返回值与void函数通过return返回单一值，void函数无返回值；需要返回多个结果时，可通过指针参数或结构体实现。合理设计返回值类型是函数接口设计的关键环节。03变量作用域局部变量在函数内有效，全局变量跨函数可见但增加耦合风险；static关键字可限制全局变量仅在本文件内可见。良好的作用域控制是模块化编程的重要原则。04函数声明与原型函数定义在调用点之后时，需提前声明函数原型（含参数类型和返回类型），帮助编译器进行类型检查。原型声明通常集中放在头文件中供多文件项目共享。CStandardI/O格式化输入与输出printf和scanf是C语言标准I/O的核心函数。掌握格式化占位符的正确用法，并警惕输入缓冲区残留等常见陷阱，是确保程序健壮性的基本要求。printf格式化%d（整数）、%f（浮点）、%s（字符串）、%c（字符）等占位符需与参数类型严格匹配；可通过宽度和精度控制输出格式，如%10.2f。%d%f%sscanf格式化读取double必须用%lf而非%f；scanf遇空格、制表符或换行符即停止读取，读含空格字符串需用fgets替代。%lf输入缓冲区陷阱scanf读取数值后换行符残留在缓冲区，可能导致后续字符读取异常；可用getchar()或scanf("%*c")清除残留字符。getchar()返回值检查scanf返回成功读取的项数，应检查返回值以判断输入是否合法，这是编写健壮输入处理代码的重要习惯。returnChapter14·CProgramming预编译指令与宏定义预编译指令在编译前由预处理器执行，负责宏替换、文件包含和条件编译。正确使用预处理功能可以提高代码的可维护性和跨平台兼容性。#define宏定义进行简单文本替换，无类型检查；带参数宏需给参数和整体加括号避免优先级错误。#defineSQUARE(x)((x)*(x))#include文件包含尖括号搜索系统头文件目录，双引号先搜索当前目录；头文件应包含防护宏以避免重复包含。#ifndef/#define/#endif条件编译根据条件决定代码是否参与编译，常用于平台适配（Windows/Linux差异处理）和调试模式开关。#if·#ifdef·#ifndef常用预定义宏编译器内置的调试信息宏，在调试和日志记录中非常实用，可自动获取当前代码位置信息。__FILE__·__LINE__·__func__CHAPTER02核心数据结构详解数组、指针与结构体——C语言的三大利器C·ARRAYFUNDAMENTALS一维数组：连续内存的数据管理一维数组在内存中占据连续空间，通过下标实现O(1)时间的随机访问。理解数组的内存布局和下标边界，是避免内存错误的前提。内存布局01数组元素在内存中连续存储，intarr[10]占用40字节连续空间；数组名arr等价于首元素地址&arr[0]。40bytes下标访问02下标从0开始，arr[i]等价于*(arr+i)；C语言不做边界检查，越界访问可能导致崩溃或静默数据损坏。*(arr+i)初始化方式03intarr[5]={1,2,3}部分初始化时剩余元素自动为0；intarr[]={1,2,3}编译器自动推断大小为3。自动推断数组与函数04数组作为函数参数时退化为指针，函数内无法用sizeof获取数组大小，必须额外传递长度参数。退化为指针CHAPTER14·CLANGUAGE二维数组：矩阵数据的组织方式二维数组在逻辑上呈现行列结构，在物理上采用行优先的连续存储。理解这一特性对于高效遍历和内存操作至关重要。定义与内存intmatrix[3][4]定义3行4列数组，行优先存储意味着matrix[0][3]紧邻matrix[1][0]，物理上是一维连续空间。这种存储方式使得按行遍历时内存访问具有局部性优势，能够充分利用CPU缓存机制提升访问效率。行优先存储初始化方法嵌套大括号intm[2][3]={{1,2,3},{4,5,6}}最清晰直观，便于阅读和维护；也可省略第一维大小由编译器自动推断元素个数。部分初始化时未指定元素自动置零，这是C语言保证数组安全性的重要特性。嵌套大括号遍历模式双层for循环外层i控制行、内层j控制列；按行遍历访问连续内存效率高，按列遍历则缓存不友好。在大规模数据处理场景下，遍历顺序的选择直接影响程序性能，行优先遍历通常比列优先快数倍。双层for循环作为函数参数传参时第一维大小可省略，但第二维必须指定如voidfunc(intm[][4],introws)，因为寻址需要列数计算偏移量。编译器通过列数确定元素在内存中的实际位置，缺失列数将无法正确解析数组结构。第二维必须指定C·MemoryModel指针：直接操作内存的钥匙指针存储内存地址，通过解引用操作间接访问数据。掌握指针的本质——地址与值的区分，是理解C语言内存模型的关键一步。基本概念指针变量存储内存地址，int*p声明指向int的指针；&x取地址，*p解引用获取指向的值，两者互为逆操作指针大小32位系统指针占4字节，64位系统占8字节，与所指类型无关；void*是通用指针，可指向任意类型但需强制转换后使用野指针与悬空指针未初始化的指针指向随机地址（野指针），指向已释放内存的指针（悬空指针），两者均会导致不可预测的崩溃指针运算p+1不是地址值加1，而是跳过sizeof(*p)个字节；两个同类型指针相减得到元素个数差，这是数组遍历的基础Chapter14·Pointer&Array指针与数组的深层关系数组名在表达式中退化为指向首元素的指针，arr[i]等价于*(arr+i)。理解这一等价关系，是掌握C语言底层内存操作的基础。退化规则数组名在表达式中退化为指向首元素的指针，arr等价于&arr[0]；但sizeof(arr)和&arr是例外，前者返回数组总大小。sizeof(arr)等价访问arr[i]编译器内部转换为*(arr+i)，因此也可写成i[arr]；指针遍历*p++比arr[i]在某些场景更高效。*(arr+i)指针算术p+n跳过n×sizeof(*p)字节，int*加1跳4字节，char*加1跳1字节；两指针相减得元素个数，前提是指向同一数组。p+nconst指针constint*p指向的值不可改（指向常量），int*constp指针本身不可改（常量指针），两者组合则值和地址均不可改。constCH14·CLANGUAGE字符串处理：字符数组与标准库C语言字符串是以'\0'结尾的字符数组，标准库提供了丰富的字符串操作函数。正确处理字符串长度和缓冲区边界，是避免安全漏洞的关键。字符串本质字符数组以'\0'（空字符）标记结束，"hello"实际占6字节；strlen返回不含\0的长度，sizeof返回含\0的数组大小'\0'Terminator常用函数strlen计算长度、strcpy复制、strcat拼接、strcmp比较（返回0表示相等）；使用前必须#include<string.h>string.h缓冲区安全strcpy和strcat不检查目标空间，易导致溢出；安全替代方案是strncpy和strncat，可指定最大操作长度strncpy字符串字面量"hello"存储在只读区，char*s="hello"后修改s[0]会崩溃；如需可修改字符串，应声明为chars[]="hello"chars[]CLanguage·Chapter14结构体：自定义复合数据类型结构体将不同类型的数据封装为一个整体，是实现复杂数据模型的基础工具。理解成员访问方式和内存对齐机制，对编写高效代码至关重要。01定义与初始化structStudent{charname[20];intage;floatscore;};使用struct关键字声明结构体类型，成员可以是任意数据类型。初始化可采用花括号字面量按顺序赋值，或对指定成员逐一生成初始值，灵活适应不同场景需求。02成员访问p→name(*p).name直接访问使用点运算符，指针访问使用箭头运算符，两者完全等价。结构体支持嵌套定义，访问时需逐级展开，形成清晰的数据层级关系。03内存对齐char+int→8bytes(not5)#pragmapack(n)编译器按最大成员类型自动对齐，可能产生内存填充。理解对齐规则有助于优化结构体布局，减少内存占用。可通过编译指令调整默认对齐方式。04typedef简化typedefstruct{intx;inty;}Point;为结构体类型创建别名，省略冗余的struct关键字，使代码更加简洁优雅。别名通常采用首字母大写的命名风格，增强代码可读性和可维护性。CHAPTER14·CLANGUAGE动态内存分配：运行时的内存管理动态内存分配允许程序在运行时按需申请和释放内存，是处理不确定大小数据的核心手段。正确使用malloc/free并避免内存泄漏，是C程序员的基本素养。malloc与callocmalloc(size)申请size字节未初始化内存，calloc(n,size)申请n×size字节并初始化为0；返回NULL表示分配失败，必须检查。malloc/callocrealloc调整大小realloc(ptr,new_size)可扩大或缩小已有内存块，可能移动数据到新位置；返回新地址，原指针可能失效。reallocfree释放内存使用完毕必须free释放，否则造成内存泄漏；free后应将指针置NULL，避免悬空指针导致难以调试的崩溃。free常见错误重复free同一内存、free非动态分配的内存、访问已free的内存、忘记检查malloc返回值，均会导致未定义行为。UndefinedBehaviorChapter14·CProgramming文件操作：数据持久化与外部交互文件操作是程序与外部世界交互的重要通道。掌握文件的打开、读写和关闭流程，并正确处理文件操作的错误情况，是编写实用程序的基本要求。文件打开FILE*fp=fopen("data.txt","r")，模式包括r(读)、w(写/清空)、a(追加)、rb/wb(二进制)；返回NULL表示打开失败，必须检查fopen·NULLcheck文本读写fprintf/fscanf格式化读写类似printf/scanf；fgets按行读取更安全（可限制长度），fputs写入字符串；feof判断文件末尾fgets·feof二进制读写fread(buffer,size,count,fp)和fwrite用于读写二进制数据，适合结构体数组等批量数据的高效存取fread·fwrite关闭与定位fclose(fp)关闭文件并释放资源；fseek移动指针到任意位置，ftell获取当前位置，rewind回到文件开头fseek·fcloseCHAPTER03编程实战：二维数组回形遍历从问题分析到代码实现，体验完整的编程思维过程ProblemDefinition问题定义：回形遍历的规则与输入输出回形遍历要求从二维数组左上角出发，按顺时针螺旋顺序访问所有元素。理解遍历规则和边界条件，是设计算法的第一步。遍历规则从array[0][0]开始，按右→下→左→上的顺序螺旋前进，每走完一圈向内收缩一层，直到所有元素被访问。螺旋收缩输入格式第一行两个整数row和col（0<row<100,0<col<100），随后row行每行col个整数构成二维数组。row×col输出要求按回形遍历顺序输出每个整数，每个整数占一行，输出个数应恰好等于row×col。逐行输出关键挑战每圈的边界不同，且最后一圈可能退化为单行或单列，需要精确控制四个方向的循环条件。四方向控制AlgorithmAnalysis思路分析：边界收缩与四向遍历回形遍历的核心思想是用四个边界变量控制遍历范围，每完成一圈四个边界向内收缩一层。当行边界或列边界交叉时，遍历结束。01四边界模型用xx_row（行上限）、sx_row（行下限）、xx_col（列上限）、sx_col（列下限）四个变量动态追踪当前圈的范围02四向移动规律向右（行=xx_row，列从xx_col到sx_col）→向下（列=sx_col）→向左→向上，每步后收缩对应边界03边界收缩向右走完xx_row++，向下走完sx_col--，向左走完sx_row--，向上走完xx_col++，四个边界逐圈向中心逼近04终止条件当xx_row>sx_row或xx_col>sx_col时遍历完毕；注意最后一圈可能只需走部分方向（如单行或单列）CodeImplementation代码实现：基础框架与输入处理程序首先读取数组维度和元素，然后通过四个边界变量控制回形遍历。清晰的变量命名和结构化的循环设计是代码可读性的保障。宏定义与数组声明#defineROW100和#defineCOL100定义最大维度，intmatrix[ROW][COL]在栈上分配足够大的空间。100×100输入处理scanf读取行列维度，双层for循环按行优先顺序逐个读取matrix[i][j]元素完成数据填充。scanf边界变量初始化xx_row=0,sx_row=row-1,xx_col=0,sx_col=col-1，分别表示当前遍历圈的四条边界。4Boundaries主循环结构while外层判断边界合法性，内部四个for循环分别处理右、下、左、上四个方向的遍历。→↓←↑SPIRALMATRIXTRAVERSAL核心逻辑：四向遍历的代码详解四个方向的for循环依次执行，每个循环结束后收缩对应边界。向左和向上遍历前需额外检查边界条件，防止最后一圈重复输出。向右与向下RIGHT→for(j=xx_col;j<=sx_col;j++)for(j=xx_col;j<=sx_col;j++)matrix[xx_row][j]xx_row++输出matrix[xx_row][j]，完成后xx_row++，上边界下移一行。此步骤从左到右遍历当前最外层的顶部行。DOWN↓for(i=xx_row;i<=sx_row;i++)for(i=xx_row;i<=sx_row;i++)matrix[i][sx_col]sx_col--输出matrix[i][sx_col]，完成后sx_col--，右边界左移一列。此步骤从上到下遍历当前最外层的右侧列。向左与向上LEFT←sx_row>=xx_row先检查sx_row>=xx_row避免单行重复for(j=sx_col;j>=xx_col;j--)matrix[sx_row][j]sx_row--for(j=sx_col;j>=xx_col;j--)输出matrix[sx_row][j]，完成后sx_row--。此步骤从右到左遍历当前最外层的底部行。UP↑xx_col<=sx_col先检查xx_col<=sx_col避免单列重复for(i=sx_row;i>=xx_row;i--)matrix[i][xx_col]xx_col++for(i=sx_row;i>=xx_row;i--)输出matrix[i][xx_col]，完成后xx_col++。此步骤从下到上遍历当前最外层的左侧列。SPIRALTRAVERSAL·EDGECASES边界情况：退化圈的正确处理当数组非正方形或最后一圈退化时，四个方向可能只需部分执行。在向左和向上遍历前增加边界检查，是确保算法正确性的关键。单行退化row=1时只需向右遍历一次，xx_row++后超出边界，后续方向自动跳过；关键是向左前检查sx_row≥xx_row。ROW=1单列退化col=1时只需向下遍历一次，sx_col--后超出边界，后续方向自动跳过；关键是向上前检查xx_col≤sx_col。COL=1奇数方阵中心如5×5数组最内圈仅1个元素，向右遍历后即完成，后续三个方向因边界交叉而跳过。5×5矩形数组如3×7数组，圈数由min(row,col)决定，长边方向每圈遍历更多元素，短边方向较早到达边界。3×7CLANGUAGE·CHAPTER14完整代码：回形遍历程序完整的回形遍历程序约30行代码，结构清晰、逻辑完整。通过宏定义控制数组大小，四边界模型控制遍历过程，是C语言基础知识的综合应用。程序结构宏定义→变量声明→输入处理→回形遍历→返回，五个部分层次分明，符合C程序的标准组织方式。五层架构输入模块先读row和col，再双层循环读矩阵元素，scanf格式字符串与变量类型严格对应。SCANF遍历核心while循环控制圈数，四个for循环分别处理四个方向，每个方向完成后收缩对应边界。四方向边界保护向左遍历前检查行边界条件，向上遍历前检查列边界条件，防止退化圈重复输出。防退化CHAPTER14·CLANGUAGE优化思考与问题扩展编程不仅是写出能运行的代码，更要思考优化空间和扩展可能。从不同角度审视同一个问题，是培养计算思维的有效途径。01方向数组优化用dx[]={0,1,0,-1}和dy[]={1,0,-1,0}表示四个方向的坐标增量，配合方向变量d，可统一四个循环为单一while循环while循环02逆时针遍历只需调整方向顺序为下→右→上→左，或修改方向数组为dx[]={1,0,-1,0}和dy[]={0,1,0,-1}方向数组03复杂度分析时间复杂度O(row×col)每个元素访问一次，空间复杂度O(row×col)存储数组，已达理论最优O(row×col)04扩展挑战从中心向外螺旋、三维数组螺旋遍历、原地旋转矩阵90度等相关问题，可作为课后进阶练习进阶练习DEBUGGINGSKILLS调试技巧：定位与修复程序错误调试能力是程序员的核心竞争力。通过构造测试用例、打印中间变量和单步调试，可以系统地定位问题，而非盲目修改代码。最小测试用例先用2×2、3×3等小数组手动验证输出，确认基本逻辑正确后再测试大数组和边界情况（如1×n、n×1）2×2打印中间状态在每圈开始处打印四个边界变量的值，在每次输出后打印当前坐标(i,j)，帮助追踪程序执行路径(i,j)单步调试使用GDB或IDE的断点功能逐行执行，观察变量变化是否符合预期，特别关注循环边界和条件判断GDB常见错误排查off-by-one错误（循环边界多1或少1）、退化圈重复输出、边界更新遗漏，是回形遍历最常见的三类bugOff-by-oneChapter04计算思维与课程总结从C语言到计算思维，培养AI时代的核心能力APPLICATIONSCENARIOSC语言的现代价值与应用场景C语言作为系统级编程的基石，在操作系统、嵌入式、高性能计算等领域不可替代。学习C语言的核心价值在于理解计算机底层运行机制。01系统编程基石Linux内核、Windows驱动、macOS底层框架均以C语言为主，操作系统级别的开发离不开C的直接内存操作能力。掌握C语言是深入理解系统底层运行机制的关键路径。Linux·Windows·macOS02嵌入式与物联网单片机、ARM芯片、传感器驱动等资源受限环境，C语言因其高效和可控性成为首选甚至唯一选择。在微控制器编程领域，C语言仍是不可替代的核心工具。ARM·MCU·IoT03高性能计算科学计算、图形渲染、数据库引擎（如MySQL/Redis）对性能极致追求的场景，C语言的零开销抽象无可替代。这些关键基础设施依赖C语言实现毫秒级