《二级(C语言)考试真题重点题型分类总结PPT课件.ppt》由会员分享，可在线阅读，更多相关《二级(C语言)考试真题重点题型分类总结PPT课件.ppt（72页珍藏版）》请在金锄头文库上搜索。
1、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
2、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 线性链表 用一组任意的存储单元存储线性表中的
3、数据元素 对每个数据元素除了保存自身信息外 还保存了直接后继元素的存储位置 用线性链表存储线性表时 数据元素之间的关系是通过保存直接后继元素的存储位置来表示的 线性链表图示 用线性链表存储线性表时 数据元素之间的关系是通过保存直接后继元素的存储位置来表示的 2线性链表图示一般来说 我们并不需要写出直接后继的实际地址 为直观起见 通常用如下所示的图表示链表 其中 箭头表示相应单元中保存的是它所指向结点的存储地址 head是头指针 head 结点 数据元素及直接后继的存储位置 地址 组成一个数据元素的存储结构 称为一个结点 结点的数据域 结点中用于保存数据元素的部分 结点的指针域 结点中用于保存数
4、据元素直接后继存储地址的部分 3线性链表有关术语 存储数据元素 存储后继结点存储地址 头指针 用于存放线性链表中第一个结点的存储地址 空指针 不指向任何结点 线性链表最后一个结点的指针通常是空指针 空指针一般用NULL表示 头结点 线性链表的第一元素结点前面的一个附加结点 称为头结点 带头结点的线性链表 第一元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表 带头结点的线性链表图示 head是头指针 头结点 空指针 head 线性链表的每个结点中只有一个指针域故也称为单链表 head是头指针 head 注 从以往二级考试来看都是用没有附加头结点的链表 如图所示 结点变量图示 stru
5、ctnode intx structnode next node 结构体类型名 node类型结构变量有两个域 x 用于存放线性表的数据元素 next 用于存放元素直接后继结点的地址 该类型结构变量用于表示线性链表中的一个结点 h和head 指向结构体结点的指针变量 用于存放node类型结构变量的地址 xnext node类型结构变量 结构体结点指针变量h 4线性链表的结点类型定义及指向结点的指针类型定义 structnode h 或structnode head 结构体指针变量定义 结构体类型定义 常用的引用格式 一般格式 指针变量名 结构体成员名如 h x 10 h h next 注意 在引
6、用过程中 数据类型还是成员的数据类型 如 h x为成员x的数据类型 即整形 5怎样利用结构体指针变量来引用结构体成员 structnode h 或structnode head 不常用引用格式 指针变量名 结构体成员名如 h x 10 h h next 设head是指向链表第一个结点的指针变量 head用来保存线性链表中第一个结点的地址 Head指向的链表 二线性链表基本操作的算法假设线性表用不带头结点的线性链表head的存储 下面讨论在这种存储方式下 线性表各种基本操作的算法 当线性表用线性链表存储时 对线性表各种基本操作实际上就是对存储在内存中的线性链表进行操作 如何在线性链表head上实
7、现线性表的基本操作 如何建空表 如何插入 删除 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删除操作功能 在
8、线性链表L中删除第i个元素 并且用e返回其值删除操作图示 删除前 删除后 删除操作主要步骤 1 查找链表的第i 1个元素结点 2 修改第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指针变量就是用来指向建立的新结点 P1013题 即2000年秋的填空题中的13题 PNODE padd PNO
9、DE 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成员的值谁大 将新增的
10、结点连到工作指针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 P
11、2114题 即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年秋的填空题中的
12、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
13、 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 NUL
14、L 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 hea
15、d 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
16、 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指向
