北京大学《计算概论》课件：第10讲复合数据结构数组与结构

第10讲：复合数据结构数组与结构——北京大学《计算概论》课程Contents课程目录北京大学《计算概论》第10讲：复合数据结构之数组与结构体核心知识脉络。01数组基础：声明、初始化与内存模型02数组进阶：多维数组与字符串处理03结构体基础：定义、初始化与成员访问04结构体进阶：结构体数组、指针与嵌套05对比总结与实战案例CHAPTER01数组基础从基本类型到复合类型的思维跨越COMPOSITEDATASTRUCTURES为什么需要复合数据结构？基本数据类型每次只能存储单个值，无法高效管理批量同类型数据。复合数据结构使程序能够以简洁的方式操作大规模数据集合，是从"单一变量思维"到"批量数据思维"的关键跨越。基本类型局限每个变量只能存储一个值，管理100个学生成绩需定义100个独立变量100个变量核心价值用统一名称管理一组相关数据，配合循环实现批量操作，提升简洁性批量操作C语言两类结构数组存储同类型有序集合，结构体组合不同类型为逻辑整体Array+Struct计算思维体现"抽象"与"模式化"思维——将重复的数据管理模式抽象为统一语法抽象·模式化CHAPTER10·DATASTRUCTURES数组的定义与核心特征数组是C语言中最基础的复合数据结构，它将一组相同类型的元素存储在连续的内存空间中，通过统一名称和下标索引实现快速定位与访问，是批量数据处理的基础工具。01定义数组是一组具有相同数据类型的变量的有序集合，每个元素通过数组名加下标（索引）来唯一标识和访问02同质性数组中所有元素必须是同一数据类型（如全为int或全为float），编译器据此计算每个元素的内存偏移量03连续性数组元素在内存中占据连续的存储空间，首元素地址最低，后续元素依次排列，这是数组高效随机访问的物理基础04固定性数组一旦声明，其大小在程序运行期间不可改变（C99变长数组VLA除外），需在编译期或声明时确定长度SYNTAXFUNDAMENTALS一维数组的声明语法C语言中数组声明遵循"类型数组名[常量表达式]"的固定语法，编译器根据类型和大小分配连续内存空间。理解声明语法的每个组成部分，是正确使用数组的第一步。STANDARD标准声明语法类型说明符数组名[常量表达式]，如intscore[100];编译器根据类型和元素个数计算所需内存总字节数，在栈区或静态存储区分配连续空间。100×4=400bytesCONSTRAINT常量表达式要求方括号内须为正整数常量或常量表达式，C89标准严格禁止变量作为数组大小。使用宏定义或枚举可提高代码可维护性与可读性。#defineN50C99变长数组VLAC99标准引入变长数组特性，允许使用变量指定数组大小，如inta[n];但VLA不可在声明时初始化，且部分嵌入式编译器可能不支持此特性。VariableLengthArrayPOINTER数组名的本质数组名在大多数表达式中会被转换为指向首元素的指针常量&a[0]，其值在编译期确定，不可重新赋值，但可通过下标或指针运算访问元素。a=b;←非法CHAPTER10·ARRAYS数组的初始化方式C语言提供三种数组初始化方式：完全初始化、部分初始化和自动推断大小。未显式初始化的数组元素值未定义（全局数组除外），掌握正确的初始化方法是避免程序Bug的关键。完全初始化inta[5]={1,2,3,4,5};花括号内元素个数与数组大小一致，元素按顺序赋值给a[0]到a[4]5/5部分初始化inta[5]={1,2};仅前2个元素赋值，剩余a[2]~a[4]自动初始化为0（仅限初始化列表场景）2/5→0自动推断大小inta[]={1,2,3,4};省略方括号内大小，编译器根据列表元素个数自动确定数组长度为4[]→4全局与静态数组全局数组和static局部数组，未初始化也自动为0；普通局部数组未初始化时元素值不确定staticMemoryModel数组的内存模型与地址计算数组元素在内存中连续存储，每个元素的地址可通过"首地址+下标×元素大小"精确计算。这种连续布局使数组具备O(1)的随机访问能力，是理解指针运算和数组高效性的物理基础。连续存储布局声明inta[5];后，编译器分配5×4=20字节的连续内存，a[0]~a[4]依次排列，相邻元素地址差恰好等于sizeof(int)地址计算公式a[i]的地址=(char*)a+i×sizeof(元素类型)，例如首地址为0x1000时，a[3]地址为0x1000+3×4=0x100C随机访问的O(1)复杂度由于地址可通过公式直接计算，访问任意下标元素的时间完全相同，不随数组大小增长，这是数组最核心的性能优势越界访问的风险C语言不检查数组下标越界，a[5]或a[-1]不会报错但会读写相邻内存，可能导致数据被覆盖或程序崩溃，是常见的安全隐患ArrayTraversal数组元素的访问与遍历数组通过下标运算符[]实现元素访问，下标从0开始。结合for循环可高效遍历整个数组，配合sizeof运算可自动获取数组长度，形成C语言中最经典的批量数据处理模式。01下标访问：通过a[i]访问第i+1个元素，下标范围为0到n-1（n为数组长度），a[0]是首元素，a[n-1]是末元素a[i]02for循环遍历模式：for(i=0;i<n;i++){处理a[i];}是C语言中最经典的数组遍历范式，适用于求和、查找、排序等所有批量操作for(;;)03数组长度的自动计算：使用sizeof(a)/sizeof(a[0])可在编译期获取数组元素个数，避免硬编码数组长度，提升代码的可维护性sizeof04常见错误：下标越界（如访问a[n]）、忘记初始化、混淆数组大小与最大下标（大小n对应的最大下标是n-1）是初学者最常犯的三类错误a[n]✗Chapter02数组进阶多维数组、字符数组与字符串处理ARRAY·MEMORYLAYOUT二维数组的声明与内存布局二维数组是数组的数组，声明时用两组方括号指定行数和列数。虽然逻辑上呈表格形态，但物理上仍按行优先顺序线性存储在连续内存中，这一特性是理解二维数组地址计算的关键。01声明语法：intmatrix[3][4];声明3行4列共12个int元素的二维数组，第一组方括号指定行数，第二组指定列数，编译器分配3×4×4=48字节48B02逻辑视图：可理解为3个一维数组的数组，matrix[i]代表第i行（本身是一个含4个int的一维数组），matrix[i][j]代表第i行第j列元素[i][j]03行优先存储：内存中按matrix[0][0]、matrix[0][1]…matrix[0][3]、matrix[1][0]…顺序线性排列，地址公式&a[i][j]=base+(i×cols+j)×size行优先04初始化方式：inta[2][3]={{1,2,3},{4,5,6}};按行分组初始化最清晰；也可inta[2][3]={1,2,3,4,5,6};按内存顺序依次赋值，两种方式结果相同等价ClassicApplication二维数组的经典应用：矩阵运算二维数组是矩阵运算的天然载体，矩阵转置和矩阵乘法是两个最经典的应用场景。它们展示了嵌套循环与二维下标的配合模式，是训练算法思维和循环控制能力的重要练习。矩阵转置将n×n矩阵的行列互换，核心操作为swap(a[i][j],a[j][i])，仅需遍历上三角区域（j>i），避免重复交换导致恢复原值swap(a[i][j],a[j][i])矩阵乘法C=A×B中c[i][j]=Σ(a[i][k]×b[k][j])，需要三重嵌套循环实现，时间复杂度为O(n³)，是理解算法复杂度的经典案例O(n³)嵌套循环范式外层循环控制行（i从0到m-1），内层循环控制列（j从0到n-1），这是遍历二维数组的标准模式，几乎所有矩阵操作都基于此i→rows,j→cols实际应用延伸二维数组还广泛用于图像处理（像素矩阵）、游戏开发（地图网格）、动态规划（状态表）等领域，是计算机科学的基础数据结构图像·游戏·DPCHAPTER10·ARRAY&STRUCTURE字符数组与C风格字符串C语言没有内置字符串类型，字符串通过以'\0'结尾的字符数组实现。这个设计虽然简洁，但要求程序员手动管理字符串的终止符和缓冲区大小，是C语言灵活性与风险并存的典型体现。声明charstr[20];可存储最长19个字符的字符串，需预留1个位置给终止符'\0'，每个元素占1字节内存空间19+1bytes终止符'\0'ASCII=0strlen等字符串函数通过扫描'\0'确定字符串长度，缺少终止符将导致越界读取未定义内存nullterminator初始化"Hello"→6B(含\0){'H','e',…}→5B(无\0)双引号字符串自动包含终止符；逐字符赋值不含'\0'，仅为普通字符数组而非有效字符串6vs5bytes输入风险fgets(str,size,stdin)scanf和gets不检查缓冲区边界，超长输入导致栈溢出漏洞，推荐fgets替代以指定最大读取长度bufferoverflowString.h·CStandardLibrary常用字符串处理函数（string.h）C标准库string.h提供了strlen、strcpy、strcat、strcmp等核心字符串操作函数，它们均以'\0'作为字符串边界判断依据。掌握这些函数的用法和安全性注意事项，是C语言字符串编程的基本功。长度与复制strlen(s)返回字符串s的实际长度（不含'\0'），时间复杂度O(n)，通过从首字符扫描至'\0'实现计数O(n)长度与复制strcpy(dest,src)将src字符串（含'\0'）复制到dest，dest必须有足够空间，否则导致缓冲区溢出，安全替代为strncpystrncpy拼接与比较strcat(dest,src)将src追加到dest末尾，覆盖dest原来的'\0'并在新末尾添加'\0'，需确保dest有足够剩余空间APPEND拼接与比较strcmp(s1,s2)按ASCII值逐字符比较两字符串，返回0表示相等、负值表示s1<s2、正值表示s1>s2，不可用==运算符比较字符串ASCIICHAPTER03结构体基础将不同类型的数据组织为逻辑整体STRUCT为什么需要结构体？数组只能存储同类型数据，而现实世界的实体往往由多种类型属性组成。结构体通过将不同类型的数据成员封装为一个逻辑单元，实现了对复杂现实对象的自然建模。01数组的局限性管理学生信息需维护多个平行数组（name[]、id[]、score[]），下标是唯一关联纽带，排序或插入时极易出现数据错位。02结构体的解决方案将姓名、学号、成绩等不同类型属性封装为Student结构体，每个学生的所有信息作为一个整体存储和操作。03从「集合」到「对象」数组关注「一组同类数据」，结构体关注「一个完整实体」，后者更接近人类认知世界的方式，是面向对象编程的思想萌芽。04用户自定义类型结构体是C语言中用户自定义数据类型（UDT）的核心机制，程序员可根据需求灵活设计数据结构，突破内置类型的限制。CHAPTER10·COMPOSITEDATASTRUCTURES结构体的定义语法结构体使用struct关键字定义，花括号内列出所有成员及其类型。定义结构体仅创建类型模板，不分配内存；声明结构体变量时才按成员总大小分配连续存储空间。这一"先定义类型、后声明变量"的模式是C语言类型系统的核心设计。基本语法struct结构体名{类型1成员1;类型2成员2;...};以Student为例，包含name、id、score三类成员。structStudent{...};类型定义≠变量声明structStudent{...};仅定义类型模板，编译器不分配内存；需声明变量structStudents1;才分配空间。Type≠Variable成员类型多样性成员可为int、float、char等基本类型，也可为数组、指针、甚至其他已定义的结构体类型。int/char[]/structtypedef简化typedefstruct{...}Student;为结构体起别名，之后直接Students1;声明变量，无需每次写struct。typedef→别名STRUCTOPERATIONS结构体的初始化与成员访问结构体变量可通过花括号初始化列表或逐成员赋值来设置初始值，使用点运算符访问成员；C99指定初始化器提升了可读性。01顺序初始化按成员定义顺序依次赋值，未指定的尾部成员自动初始化为零值structStudents1={"张三",1001,92.5};按序赋值02C99指定初始化器按成员名赋值，顺序不限且可读性更强，推荐优先使用此方式structStudents2={.name="李四",.score=88.0};推荐方式03点运算符访问通过.运算符访问各成员，成员可像普通变量一样参与表达式运算printf("%s:%.1f",,s1.score);s.member04整体赋值与比较同类型结构体可整体赋值，编译器逐成员复制；比较须逐成员手动进行s2=s1;/*禁止s1==s2*/逐成员MemoryLayout结构体的内存布局与对齐结构体的实际大小通常大于各成员大小之和，因为编译器会插入填充字节以满足内存对齐要求。对齐的目的是让CPU能高效访问数据，但会导致内存浪费。通过合理安排成员顺序，可以减少填充，优化内存使用。01内存对齐规则每个成员的起始地址必须是其自身大小（或编译器设定的对齐值）的整数倍，如int需从4的倍数地址开始，double需从8的倍数地址开始4×Nbytes02填充字节示例struct{chara;intb;charc;}看似1+4+1=6字节，实际因对齐填充为12字节——a后填充3字节，c后填充3字节使总大小为4的倍数6→12bytes03sizeof运算sizeof(structStudent)返回结构体的实际占用大小（含填充），这个值总是最大对齐成员大小的整数倍max(align)×N04优化策略将成员按大小降序排列（double→int→char）可减少填充浪费，如struct{doubled;inti;charc;}比乱序排列节省内存↓PaddingCHAPTER04结构体进阶结构体数组、指针与嵌套设计STRUCTARRAY结构体数组：批量管理复合对象结构体数组将结构体的"异构组合"能力与数组的"批量管理"能力结合，是C语言中管理同类实体集合的标准方式。声明与初始化每个元素是完整的结构体变量，支持逐字段初始化：structStudentclass[3]={{"张三",1001,92.5},{"李四",1002,88.0},{"王五",1003,95.5}};struct[N]成员访问class[0].score通过下标与点运算符精确定位到特定元素的成员，如class[0].score获取第一个学生的成绩，可参与任意运算和比较。class[i].member[i].member排序操作交换整个结构体变量，所有成员同步移动，数据关联不会被破坏：structStudenttemp=class[i];class[i]=class[j];class[j]=temp;整体交换与平行数组对比结构体数组用一个数组管理所有属性，数据天然内聚；平行数组需多个独立数组靠下标隐式关联，容易因索引错位导致数据混乱。结构体数组单一数组存储，成员绑定紧密，代码可读性强平行数组多数组并行，依赖下标同步，维护易出错操作安全Pointer&ArrowOperator结构体指针与箭头运算符结构体指针存储结构体变量的地址，通过箭头运算符->可高效访问成员。在函数传参时使用指针避免了结构体的整体复制开销，是C语言实现高效数据操作和构建动态数据结构（如链表）的基础。指针声明与赋值structStudent*p=&s1;structStudent*p=&s1;指针p指向结构体变量s1，仅占4或8字节（取决于系统），远小于复制整个结构体的开销。4~8Bytes箭头运算符p->name(*p).namep->name等价于(*p).name，通过指针访问成员时使用->更简洁直观。箭头运算符是C语言为结构体指针专门设计的语法糖，简化了解引用和成员访问的组合操作。p->member函数传参优化函数接收指针而非值，避免复制整个结构体，对含大数组成员的大型结构体性能提升显著。指针传参使函数能够直接修改原结构体内容，实现高效的数据交换与状态更新。零拷贝传参动态分配mallocp->member使用malloc在堆上动态创建结构体，配合p->member访问，是链表等动态数据结构的基础。链表基础STRUCTNESTING嵌套结构体：构建层次化数据模型结构体的成员可以是其他结构体类型，形成嵌套组合关系。这种机制允许程序员按照现实世界的层次结构来组织数据，是构建复杂数据模型的基础能力。01嵌套定义先定义structDate{intyear,month,day;}，再在structStudent中声明structDatebirthday成员，形成层次化的数据结构。层次化结构02逐层访问使用连续点运算符访问嵌套成员，如s1.birthday.year=2005；每层用'.'分隔，从左到右逐级深入。逐级深入03嵌套初始化内层花括号对应嵌套结构体成员的初始化值，按定义顺序匹配：{"张三",1001,92.5,{2005,6,15}}。花括号匹配04实际应用场景广泛用于复杂系统建模：员工信息（含地址结构体）、图形系统（点→线段→多边形）、文件系统（目录→文件→属性）。复杂建模ParameterPassing结构体与函数：参数传递策略结构体作为函数参数时，按值传递安全但有复制开销，按指针传递高效但可能修改原数据。选择传递策略需在安全性与效率之间权衡，const指针是兼顾两者的最佳实践。按值传递voidfunc(structStudents)复制整个结构体到栈上，函数内修改不影响原变量，但大型结构体的复制开销不可忽视voidfunc(structStudents)按指针传递voidfunc(structStudent*p)仅传递地址（4或8字节），效率极高，但函数内可通过p->member修改原始数据voidfunc(structStudent*p)const保护voidfunc(conststructStudent*p)既享受指针传递的高效，又通过const禁止函数内修改，是只读访问的推荐方式conststructStudent*p返回结构体structStudentcreateStudent()可直接返回结构体，编译器通常优化为隐式指针传递（RVO），但超大型结构体仍建议用指针参数输出RVO/隐式指针CHAPTER05对比总结与实战案例融会贯通，从对比中深化理解COMPARISON数组vs结构体：核心差异全面对比数组以同类型连续存储适合批量数据管理，结构体以混合类型逻辑封装适合实体建模，两者可组合构建更丰富的数据结构。数组与结构体核心特性对比对比维度数组(Array)结构体(Structure)数据类型所有元素必须是相同类型成员可以是不同类型内存布局元素严格连续存储，无间隙成员大致连续，可能有对齐填充访问方式下标运算符a[i]，O(1)随机访问点运算符s.member，按名称访问大小计算元素个数×单个元素大小各成员大小之和+对齐填充字节声明关键字无需特殊关键字必须使用struct关键字用户自定义不是用户自定义数据类型是用户自定义数据类型（UDT）设计意图管理同类数据的有序集合封装一个完整实体的多个属性性能特点遍历和搜索更快（同质+连续）灵活性强但访问开销略高数组与结构体在数据类型、内存布局、访问方式等8个维度存在本质差异，两者互补而非替代STRUCTURE×ARRAY组合使用：数组与结构体的协同数组与结构体并非对立关系，而是可以灵活组合使用。结构体数组用于批量管理复合对象，结构体内嵌数组用于描述对象的多值属性，两者结合构成了C语言处理复杂数据的核心范式。结构体数组structStudentclass[50]structStudentclass[50]用数组管理50个学生，每个元素包含姓名、学号、成绩，配合循环实现批量操作排序、查找、统计等算法可直接应用，交换时整个结构体同步移动，数据完整性得到保证50个学生结构体内嵌数组成员中包含字符数组（姓名）和整数数组（5门课成绩），实现单个实体的多值属性建模s1.scores[2]strcpys1.scores[2]获取第3门课成绩，strcpy设置姓名，双重定位访问双重定位高级组合模式*ptrs[50]*ptrs[50]指针数组指向动态结构体，适合数量不确定或需频繁插入删除的场景DepartmentStudent[100]嵌套结构体数组：Department内含Student[100]，层次化数据模型层次化CASESTUDY实战案例：学生成绩管理系统学生成绩管理系统是数组与结构体综合应用的经典案例。通过定义Student结构体、使用结构体数组存储数据、结合循环和条件判断实现增删查改，完整展示了复合数据结构在实际程序设计中的应用模式。数据结构设计定义structStudent，包含name[20]、id、scores[5]、avg成员，结构体中同时涵盖基本类型和数组，完整描述学生信息。STRUCT批量录入与存储声明class[100]结构体数组，配合for循环与scanf逐个录入，用count变量记录实际人数，避免遍历无效元素。100人上限平均分计算遍历scores数组求和后除以课程数，结果存入avg成员，体现结构体内嵌数组的典型访问模式s.scores[i]。5COURSES排序与查找按avg降序冒泡排序交换结构体变量，按学号线性搜索比较id，排序后可升级为二分搜索提升效率。冒泡→二分CASESTUDY实战案例：通讯录管理系统通讯录系统是字符数组（字符串）与结构体深度结合的应用场景。姓名、电话等文本信息依赖字符数组存储，string.h函数库实现排序和查找，结构体将多个字符串属性封装为完整的联系人实体。DATASTRUCTURE数据结构structContact封装三个字符数组成员，分别存储姓名、电话和邮箱，长度按实际需求设定。charname[30];charphone[15];charemail[50];STRINGOPS字符串操作录入用fgets替代scanf防止溢出，排序与查找均基于strcmp实现精确匹配或模糊搜索。fgets()·strcmp()//安全读取字符串DYNAMICMGMT动态管理指针数组配合malloc动态分配内存，新增联系人时分配新空间，删除时free释放并移动指针。malloc()·free()//动态内存管理PERSISTENCE数据持久化通讯录以文本格式写入文件，程序启动时从文件读取恢复，实现数据的跨会话保存。fprintf()·fscanf()//文件读写操作PITFALLS&BESTPRACTICES常见错误与避坑指南数组越界、字符串终止符遗漏、指针与数组混淆、结构体非法比较和内存对齐误解，是C语言复合数据结构编程中最高频的五类错误。理解其根因并养成防御性编程习惯，是从"能写代码"到"写好代码"的关键进阶。数组相关陷阱01越界访问：a[n]访问大小为n的数组会读写相邻内存，C语言不做边界检查，需用循环条件严格控制下标范围，避免缓冲区溢出漏洞。02字符串遗漏'\0'：手动构造字符数组时忘记添加终止符，导致strlen、printf("%s")等函数越界读取直到碰到偶然的零字节，引发不可预期行为。边界检查结构体相关陷阱01非法比较：两个结构体不能用==比较（编译器报错或比较地址），需逐成员手动比较；赋值虽合法但是浅拷贝，含指针成员时需特别注意深拷贝问题。02大小误解：sizeof(struct)通常大于成员大小之和，因内存对齐会插入填充字节；网络传输时需考虑字节序和对齐问题，使用#pragmapack需谨慎。内存对齐通用建议01防御性编程：始终用常量或宏定义数组大小，输入字符串用fgets限定长度，访问成员前检查指针是否为NULL，避免硬编码魔术数字。02调试技巧：使用sizeof验证数据结构大小是否符合预期，用Valgrind等工具检测内存越界和泄漏问题，结合GDB断点调试定位崩溃现场。ValgrindSummary本讲知识框架总结第10讲围绕'复合数据结构'这一核心，系统讲授了数组（同类型连续集合）和结构体（异类型逻辑封装）两大工具及其进阶应用。两者既可独立使用，也可灵活组合，共同构成C语言数据组织的完整能力体系。数组知识体系声明语法、初始化方式（完全/部分/自动推断）、下标访问、for循环遍历、连续内存模型与O(1)