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

C语言二级真题总结;; 线性表是n 个数据元素的有限序列。 通常记作（a1, a2, a3, …, an ）。;说明：设 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 线性链表;线性链表图示;结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点； 结点的数据域 ：结点中用于保存数据元素的部分; 结点的指针域 ：结点中用于保存数据元素直接后继存储地址的部分;;头指针：用于存放线性链表中第一个结点的存储地址;空指针：不指向任何结点，线性链表最后一个结点的指针通常是空指针，空指针一般用NULL表示;头结点：线性链表的第一元素结点前面的一个附加结点，称为头结点；带头结点的线性链表：第一元素结点前面增加一个附加结点的线性链表称为 带头结点的线性链表；;线性链表的每个结点中只有一个指针域 故也称为单链表;结点变量图示;常用的引用格式(一般格式)： 指针变量名-结构体成员名 如： h-x=10; h=h-next;; 设head是指向链表第一个结点的指针变量，head用来保存线性链表中第一个结点的地址。; 如何在线性链表head 上实现线性表的基本操作？ 如何建空表？如何插入？删除？ ;1 取元素操作 （从链表中找到与输入的值m相等的元素）·功能：1、将线性链表中第i 个元素赋值给 e 2、从链表中找到与输入的值m相等的元素，并将其指针返回 取元素操作主要步骤： 1）查找链表的第 i个元素结点；2) 将第i个元素结点中的数据元素赋值给e;（或将其指针返回;）;2 插入操作  功能：在线性链表head的第i个元素结点之前插入一个新元素结点； 插入操作图示：;插入操作主要步骤：1）查找链表L的第 i-1个元素结点；2）为新元素建立结点；3）修改第 i-1个元素结点的指针和新元素结点指针完成插入；;3 删除操作  功能：在线性链表L中删除第i个元素，并且用e 返回其值 删除操作图示：;删除操作主要步骤： 1）查找链表的第 i-1个元素结点；2）修改第 i-1个元素结点指针，删除第i个元素结点；3) 将第i个元素结点中的数据元素赋值给e;4）回收被删除结点空间；用free(指针变量)函数释放删除结点的空间;4 线性链表归并操作图示;以前考过的线性链表的题目;P10 13题（即2000年秋的填空题中的13题）;P10 13题（答案）;P21 14题（即2001年春的填空题中的14题）;P21 14题（答案）;P31 14题（即2001年秋的填空题中的14题）;P31 14题（答案）;P42 14题（即2002年春的填空题中的14题）;P42 14题（答案）;P51 14题（即2002年秋的填空题中的14题）;P51 14题（答案）;P60 14题（即2003年春的填空题中的14题）;P60 14题（即2003年春的填空题中的14题）;c;为了存储线性表，至少要保存两类信息：1）线性表中的数据元素；2）线性表中数据元素的顺序关系；; 线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。;说明： · 在顺序存储结构下，线性表元素之间的逻辑关系，可通过元素的存储顺序反映（表示）出来，所以只需存储数据元素的信息； · 假没线性表中每个数据元素占用 k 个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是： Loc(ai ) = Loc( a1 )+ ( i – 1)? k 这里 Loc(ai)是第 i 个元素的存储位置, Loc( a1 ) 是第1个元素的存储位置，也称为线性表的基址