级语言考试真题重点题型分类总结PPT课件.ppt

C语言二级真题总结 真题汇总小结 省二级考试C语言真题重点题型分类一 线性表 建立 删除 插入 二 文件操作 文件打开 读 写 三 递归问题四 字符串操作问题五 变量作用域与静态变量问题六 数列或数字处理问题七 排序问题八 上机试题 线性表是n个数据元素的有限序列 通常记作 a1 a2 a3 an 一 线性表 例1 数学中的数列 11 13 15 17 19 21 例2 英文字母表 A B C D E Z 例3 某单位的电话号码簿 一线性表的逻辑结构 电话号码簿是数据元素的有限序列 每一数据元素包括两个数据项 一个是用户姓名 一个是对应的电话号码 说明 设A a1 a2 ai 1 ai ai 1 an 是一线性表1 均匀性 线性表的数据元素可以是各种各样的 但同一线性表中的元素必须是同一类型的 2 相邻性 每个元素至少有一个元素与之相邻 在表中ai 1领先于ai ai领先于ai 1 称ai 1是ai的直接前趋 ai 1是ai的直接后继 a1 无前驱 an无后继 3 有限性 线性表中元素的个数n称为线性表的长度 n 0时称为空表4 有序性 ai是线性表的第i个元素 称i为数据元素ai的序号 每一个元素在线性表中的位置 仅取决于它的序号 二线性表根据其存储结构不同可分为 链式存储结构的链表顺序存储结构的顺序表 一线性链表的概念1线性链表 1 线性链表 用一组任意的存储单元存储线性表中的数据元素 对每个数据元素除了保存自身信息外 还保存了直接后继元素的存储位置 用线性链表存储线性表时 数据元素之间的关系是通过保存直接后继元素的存储位置来表示的 线性链表图示 用线性链表存储线性表时 数据元素之间的关系是通过保存直接后继元素的存储位置来表示的 2线性链表图示一般来说 我们并不需要写出直接后继的实际地址 为直观起见 通常用如下所示的图表示链表 其中 箭头表示相应单元中保存的是它所指向结点的存储地址 head是头指针 head 结点 数据元素及直接后继的存储位置 地址 组成一个数据元素的存储结构 称为一个结点 结点的数据域 结点中用于保存数据元素的部分 结点的指针域 结点中用于保存数据元素直接后继存储地址的部分 3线性链表有关术语 存储数据元素 存储后继结点存储地址 头指针 用于存放线性链表中第一个结点的存储地址 空指针 不指向任何结点 线性链表最后一个结点的指针通常是空指针 空指针一般用NULL表示 头结点 线性链表的第一元素结点前面的一个附加结点 称为头结点 带头结点的线性链表 第一元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表 带头结点的线性链表图示 head是头指针 头结点 空指针 head 线性链表的每个结点中只有一个指针域故也称为单链表 head是头指针 head 注 从以往二级考试来看都是用没有附加头结点的链表 如图所示 结点变量图示 structnode intx structnode next node 结构体类型名 node类型结构变量有两个域 x 用于存放线性表的数据元素 next 用于存放元素直接后继结点的地址 该类型结构变量用于表示线性链表中的一个结点 h和head 指向结构体结点的指针变量 用于存放node类型结构变量的地址 xnext node类型结构变量 结构体结点指针变量h 4线性链表的结点类型定义及指向结点的指针类型定义 structnode h 或structnode head 结构体指针变量定义 结构体类型定义 常用的引用格式 一般格式 指针变量名 结构体成员名如 h x 10 h h next 注意 在引用过程中 数据类型还是成员的数据类型 如 h x为成员x的数据类型 即整形 5怎样利用结构体指针变量来引用结构体成员 structnode h 或structnode head 不常用引用格式 指针变量名 结构体成员名如 h x 10 h h next 设head是指向链表第一个结点的指针变量 head用来保存线性链表中第一个结点的地址 Head指向的链表 二线性链表基本操作的算法假设线性表用不带头结点的线性链表head的存储 下面讨论在这种存储方式下 线性表各种基本操作的算法 当线性表用线性链表存储时 对线性表各种基本操作实际上就是对存储在内存中的线性链表进行操作 如何在线性链表head上实现线性表的基本操作 如何建空表 如何插入 删除 1取元素操作 从链表中找到与输入的值m相等的元素 功能 1 将线性链表中第i个元素赋值给e2 从链表中找到与输入的值m相等的元素 并将其指针返回取元素操作主要步骤 1 查找链表的第i个元素结点 2 将第i个元素结点中的数据元素赋值给e 或将其指针返回 取元素操作图示 注 p p1为工作指针 2插入操作功能 在线性链表head的第i个元素结点之前插入一个新元素结点 插入操作图示 插入前 插入后 插入操作主要步骤 1 查找链表L的第i 1个元素结点 2 为新元素建立结点 3 修改第i 1个元素结点的指针域和新元素结点指针域 从而完成插入 3删除操作功能 在线性链表L中删除第i个元素 并且用e返回其值删除操作图示 删除前 删除后 删除操作主要步骤 1 查找链表的第i 1个元素结点 2 修改第i 1个元素结点指针域 使其指向第i 1个结点 从而删除第i个元素结点 3 将第i个元素结点中的数据元素赋值给e 4 回收被删除结点空间 用free 指针变量 函数释放删除结点的空间 4线性链表归并操作图示 1 3 1 n 5 4 2 n 6 3 1 5 以前考过的线性链表的题目 P1013题 即2000年秋的填空题中的13题 此题是链表归并问题 首先要搞清楚每个指针的用途 如pt指针变量就是用来指向建立的新结点 pc为新链表的头结点 pcr为工作结点 也是新链表的尾结点指针 即它始终指针新链表的最后一个结点 P6013题 即2000年秋的填空题中的13题 PNODE padd PNODE pa PNODE pb PNODE pcr pt pc pc NULL while 23 if pa y pb y pt 24 malloc sizeof PNODE pt x pa x pb x pt y pa y pt next NULL if pc NULL pc pcr pt else pcr next pt 25 pa pa next pb pb next elseif 26 pb pb next elsepa pa next Returnpc 本空显然是控制结束的 只有当pa pb两个链表中都没有元素时才会结束 分配的空间类型 判断pa pb中当前元素y成员的值谁大 将新增的结点连到工作指针pcr上 P1013题 答案 PNODE padd PNODE pa PNODE pb PNODE pcr pt pc pc NULL while 23 if pa y pb y pt 24 malloc sizeof PNODE pt x pa x pb x pt y pa y pt next NULL if pc NULL pc pcr pt else pcr next pt 25 pa pa next pb pb next elseif 26 pb pb next elsepa pa next Returnpc pa pb PNODE pa y pb y pcr pt P2114题 即2001年春的填空题中的14题 PNODE padd PNODE pa PNODE p1 p2 p p1 p2 pa while p1 if p1 x 2 0 链表结尾的指针 NULL 如果p1指向的结点就是第一个结点 则不用移 本行是从链表中删除结点 将p指向的结点插到链表的头部 没找着偶数值结点时 指针向后移 P2一直在P1的前一个结点 P2114题 答案 PNODE padd PNODE pa PNODE p1 p2 p p1 p2 pa while p1 if p1 x 2 0 NULL p1 pa p2 next p1 pa p P3114题 即2001年秋的填空题中的14题 Structnode deladd structnode h intvalue structnode p1 p2 intflage 0 p1 p2 h while p1 链表结束或找到结点不执行循环 Flage是一个标志变量用来标志是否找到结点 如果找到符合每件的结点 就删除结点 如果没找到适合每件的结点 则指针后移 如果没找到结点构造一个新结点 如果链表为空就直接将构造的结点作为链表的第一个结点 否则将其插入到链表最后 P3114题 答案 Structnode deladd structnode h intvalue structnode p1 p2 intflage 0 p1 p2 h while p1 p1 next p1 next p1 next p2 next p1 P4214题 即2002年春的填空题中的14题 27 create intn structnode p p1 p2 h NULL inti 0 if nx p next NULL if h NULL 29 else p1 p2 h while p2 函数返回值类型 如果找到的插入位置是第一个结点 创建结点个数的控制 如果链表为空 直接插入结点作为首结点 如果找到的插入位置不是第一个结点就在找到的位置插入 P4214题 答案 27 create intn structnode p p1 p2 h NULL inti 0 if nx p next NULL if h NULL 29 else p1 p2 h while p2 structnode p next p2 i n h p P5114题 即2002年秋的填空题中的14题 Structnode loop structnode head intdir structnode p1 p2 p1 head if p1 NULL p1 next NULL returnhead if dir 0 while p1 next p2 p1 p1 p1 next 23 NULL p1 next 24 head p1 else head 25 p2 head while p2 next p2 p2 next 26 p1 next NULL returnhead 右移一次 如果是空链表或只有一个结点的链表 左移一次 找到最后一个结点使得p1指向最后一个结点P2指向倒数第二个结点 将最后一个结点 p1指向的 移到链表头 找到最后一个结点P2指向最后一个结点 P5114题 答案 Structnode loop structnode head intdir structnode p1 p2 p1 head if p1 NULL p1 next NULL returnhead if dir 0 while p1 next p2 p1 p1 p1 next 23 NULL p1 next 24 head p1 else head 25 p2 head while p2 next p2 p2 next 26 p1 next NULL returnhead p1 next p2 next head p2 next p1 P6014题 即2003年春的填空题中的14题 Structnode find del structnode head int pm structnode p1 p2 pmax pre if head NULL returnNULL pmax 23 p2 p1 pmax while p1 if p1 x 24 pre p2 pmax p1 p2 p1 p1 p1 next if pmax head head pmax next else 25 pmax next 26 pmax Returnhead 如果是空链表就结束函数 并返回空指针 首先认为第一个结点是x值最大的结点 Pmax始终指向当前x值最大的结点 P1为工作指针 活动指针 如果首结点的x值最大就删除首结点 删除pmax指向的结点 将x值最大的结点地址保存到pm指向的指针变量中 P6014题 即2003年春的填空题中的14题 Structnode find del structnode head int pm structnode p1 p2 pmax pre if head NULL returnNULL pmax 23 p2 p1 pmax while p1 if p1 x 24 pre p2 pmax p1 p2 p1 p1 p1 next if pmax head head pmax next else 25 pmax next 26 pmax Returnhead head pmax x pre next pm c 2 2线性表的顺序表示和实现一线性表的顺序存储结构 顺序表1线性表的顺序存储结构2顺序表的类型定义二顺序表的基本操作算法三利用基本操作实现线性表的其他操作 2 顺序链表 2 顺序链表 为了存储线性表 至少要保存两类信息 1 线性表中的数据元素 2 线性表中数据元素的顺序关系 在计算机内部可以采用不同的方式来存储一个线性表 其中最简单的方式就是本节要讲的线性表的顺序存储结构 线性表的顺序存储结构 就是用一组连续的内存单元依次存放线性表的数据元素 用顺序表存储线性表时 数据元素之间的逻辑关系 是通过数据元素的存储顺序反映出来的 线性表 a1 a2 a3 an 的顺序存储结构 用顺序存储结构存储的线性表 称为顺序表 一线性表的顺序存储结构 顺序表 1线性表的顺序存储结构 说明 在顺序存储结构下 线性表元素之间的逻辑关系 可通过元素的存储顺序反映 表示 出来 所以只需存储数据元素的信息 假没线性表中每个数据元素占用k个存储单元 那么 在顺序存储结构中 线性表的第i个元素的存储位置与第1个元素的存储位置的关系是 Loc ai Loc a1 i 1 k这里Loc ai 是第i个元素的存储位置 Loc a1 是第1个元素的存储位置 也称为线性表的基址 2 顺序表的类型定义以上用自然语言描述了线性表的顺序存储结构 怎样将这种存储方式在计算机上实现 为此 我们用C语言对这种存储方式进行描述 我们知道C语言一维数组的机内表示也是顺序结构 因此 可借用C语言的一维数组实现线性表的顺序存储 顺序表的类型定义 defineLIST INIT SIZE100 线性表存储空间的初始分配量 defineLISTINCREMENT10 线性表存储空间的分配增量typedefstruct ElemType elem 线性表存储空间基址intlength 当前线性表长度intlistsize 当前分配的线性表存储空间大小 以sizeof ElemType 为单位 SqList SqList 类型名 SqList类型的变量是结构变量 它的三个域分别是 elem 存放线性表元素的一维数组基址 其存储空间在初始化操作 建空表 时动态分配 length 存放线性表的表长 listsize 用于存放当前分配 存放线性表元素 的存储空间的大小 顺序表图示 存放线性表元素的一维数组 设A a1 a2 a3 an 是一线性表 L是SqList类型的结构变量 用于存放线性表A 则L在内存中的状态如图所示 如何在顺序表上实现线性表的基本操作 如何建空表 如何求表长 如何插入 删除 设线性表用顺序表L存储 下面我们介绍用顺序表存储线性表时 各种基本操作的算法 当线性表用顺序表存储时 对线性表各种基本操作实际上就是对存储在内存中的顺序表进行操作 二 顺序表的基本操作算法 取元素操作图示 1取元素操作GetElem Sq SqListL inti ElemType GetElem Sq算法2 4由于C语言的一维数组下标从0开始 故线性表的第一个元素放在L elem 0 第i个素放L elem i 1 中 最后一个元素放在L elem L length 1 中 取元素操作 nLIST INIT SIZE 1 ai 再演示一次 2插入操作ListInsert Sq 插入操作示意图 插入操作图示 插入操作主要步骤 1 i是否合法 若合法转2 否则算法结束 并返回ERROR 2 L是否已满 若未满转3 否则算法结束 并返回ERROR 3 将顺序表ai及之后的所有元素后移一个位置 4 将新元素写入空出的位置 5 表长 1 用鼠标单击图中的绿字 插入元素操作 nLIST INIT SIZE 1 插入元素操作 n 1LIST INIT SIZE 1 StatusListInsert Sq SqList ListInsert Sq算法2 5a 插入操作算法 为初学者易于理解插入算法 这里通过下标引用L elem中的元素 3删除操作ListDelete sq SqList L inti ElemType e 功能 删除顺序表L的第i个元素 并用e返回 删除操作图示 删除操作主要步骤 1 i不合法或表空 算法结束 并返回ERROR 否则转2 2 将ai赋值给e 3 将顺序表中ai后面的元素依次向前移动一个位置 4 表长 1 删除操作图示 用鼠标单击图中的绿字 删除元素操作 nLIST INIT SIZE 1 删除元素操作 n 1LIST INIT SIZE 1 删除操作算法 StatusListDelete Sq SqList ListDelete Sq算法2 56a 为初学者易于理解插入算法 这里通过下标引用L elem中的元素 二级考试以往出现的顺序表试题 P612003春15题顺序表排序P492002秋12题顺序表插入元素P402002春11题顺序表处理P292001秋12题顺序表处理P202001春12题顺序表排序 二 文件操作 1 文件类型指针变量的定义格式 FILE 如 FILE fp 文件打开与关闭 打开文件 fopen 函数如 FILE fp if fp fopen c tc2 example1 txt w NULL printf Filecannoetbeopened n exit 0 文件打开方式 关闭文件 fclose 函数关闭文件的功能 是将写入到内容文件指针位置的内容存储到硬盘上的文件中 并关闭文件 释放文件指针 在程序终止前必须关闭文件 否则 向文件中存入的内容全部没有存入 使用格式 fclose 文件指针 文件的相关函数 文件所有的读 写 输入 输出函数在使用时 必须包含头文件 stdio h即 include1 feof 文件指针变量 本函数是判断文件是否结束 如果返回值为 真 则表示已到文件尾 如果返回值为 假 则表示未到文件尾 fgetc 文件指针变量 从文件中读出一个字符 并将文件当前位置移到下一位置 返回值 读出的值 EOF读出出错 fputc 字符 文件指针变量 将字符 常量或变量 写入文件指针指向的文件当前位置 返回值 写入的值 EOF写入出错 字符串输入 输出函数 fgets 字符串变量名 n 文件指针变量 从文件中读出一个长度为n 1的字符串 放到字符串变量 返回值 读出字符串的长度 EOF读出出错 fputs 字符串 文件指针变量 将字符串 常量或变量 写入文件指针指向的文件当前位置 返回值 写入的字符数 EOF写入出错 格式化输入 输出函数 6 fscanf fp 输入格式串 输入项 完成从文件中读入操作的函数 7 fprintf fp 输出格式串 输出项 向文件输出数据的函数 向fp指向的文件按 输出格式串 中规定 输出到文件中 块输入 输出函数 8 fread buffer size count fp 9 fwrite buffer size count fp 参数说明 buffer是一个指针 对于fread来说是读入数据块的存放地址 对fwrite来说 它是输出数据块的地址 这里的地址是指数据块的首地址 通常用数据名 或数组指针或结构体数组 来代表 size是要读 写数据块的字节数count的值是要读 写多少个size字节的数据块fp是一个文件指针 指示已经打开的文件 由fopen 函数打开的 文件定位函数 8 rewind fp 将文件读写位置重新设置在文件头部 9 fseek fp longoffset intorigin 参数说明 1 fp是指向要进行读写操作的文件结构指针 该文件已由fopen 函数打开 2 origin是计算文件指针位置的起始点 文件指针的起始点可以设置在三个不同的位置上 用三个符号常量或数字代表 SEEK SET或0代表文件头SEEK CUR或1代表文件当前位置SEEK END或2代表文件尾3 offset是距起始点的偏移位置 以字节为单位 二级考试以往出现的文件操作试题 P102000秋14题在文件中查找并替换P192001春10题从文件读入 向文件输出P29 302001秋11 13题从文件读入P402002春11题从文件读入在每次的上机题中 编写的程序输出内容必须输出到文件中 三 递归问题 P7 P82000秋5题 8题P202001春12题用递归实现排序 冒泡排序 P282001秋8题P492002秋11题P592003春11题 四 字符串操作问题 P92000秋12题从字符串中删除子串P202001春13题插入子串P302001秋13题读子串P392002春10题字符串加密P512002秋15题在字符串中查找子串P592003春12题字符串处理 五 变量作用域与静态变量问题 P62000秋3题变量作用域P272001秋7题静态变量P382002春8题变量作用域与静态变量P472002秋8题变量作用域P572003春8题变量作用域 六 数列或数字处理问题 P92000秋11题P202001春11题P282001秋10题P502002秋13题P602003春13题 七 排序问题 共出现三次排序问题 使用了1次冒泡排序 2次选择排序P412002春13题 上机考试 改