江苏省二级(c语言)考试真题重点题型分类总结

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,注：从以往二级考试来看都是用没有附加头结点的链表，如图所示,结点变量图示,struct node int x； struct node *next； ;, node：结构体类型名； node类型结构变量有两个域： x：用于存放线性表的数据元素， next：用于存放元素直接后继结点的地址； 该类型结构变量用于表示线性链表中的一个结点； h和head：指向结构体结点的指针变量，用于存放node类型结构变量的地址；,x next,node类型 结构变量,结构体结点 指针变量h,4 线性链表的结点类型定义及指向结点的指针类型定义,struct node *h；或struct node *head；,结构体指针变量定义,结构体类型定义,常用的引用格式(一般格式)： 指针变量名-结构体成员名如： h-x=10; h=h-next;,注意：在引用过程中，数据类型还是成员的数据类型。 如：h-x为成员x的数据类型（即整形）,5 怎样利用结构体指针变量来引用结构体成员,struct node *h；或struct node *head；,不常用引用格式： （*指针变量名）. 结构体成员名如： (*h). x=10; *h=(*h).next;,设head是指向链表第一个结点的指针变量，head用来保存线性链表中第一个结点的地址。,Head指向的链表,二 线性链表基本操作的算法 假设线性表用不带头结点的线性链表head的存储。下面讨论在这种存储方式下，线性表各种基本操作的算法。当线性表用线性链表存储时，对线性表各种基本操作实际上就是对存储在内存中的线性链表进行操作。,如何在线性链表head上实现线性表的基本操作？如何建空表？如何插入？删除？,？,1 取元素操作 （从链表中找到与输入的值m相等的元素）功能：1、将线性链表中第i 个元素赋值给 e 2、从链表中找到与输入的值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个元素结点；3) 将第i个元素结点中的数据元素赋值给e;4）回收被删除结点空间；用free(指针变量)函数释放删除结点的空间,4 线性链表归并操作图示,1,3,1,n,5,4,2,n,6,3,1,5,以前考过的线性链表的题目,P10 13题（即2000年秋的填空题中的13题）,此题是链表归并问题： 首先要搞清楚每个指针的用途。如pt指针变量就是用来指向建立的新结点。,P10 13题（即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; else if( (26) ) pb=pb-next; else pa=pa-next; Return pc;,本空显然是控制结束的，只有当pa、pb两个链表中都没有元素时才会结束,分配的空间类型,判断papb中当前元素y成员的值谁大,将新增的结点连到工作指针pcr上,P10 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; else if( (26) ) pb=pb-next; else pa=pa-next; Return pc;,pa&pb,PNODE *,pa-ypb-y,pcr=pt,P21 14题（即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的前一个结点,P21 14题（答案）,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,P31 14题（即2001年秋的填空题中的14题）,Struct node *deladd（struct node *h, int value)struct node *p1 , *p2; int flage=0; p1=p2=h; while(p1 ,链表结束或找到结点不执行循环,Flage是一个标志变量用来标志是否找到结点,如果找到符合每件的结点，就删除结点,如果没找到适合每件的结点，则指针后移,如果没找到结点构造一个新结点,如果链表为空就直接将构造的结点作为链表的第一个结点，否则将其插入到链表最后,P31 14题（答案）,Struct node *deladd（struct node *h, int value)struct node *p1 , *p2; int flage=0; p1=p2=h; while(p1 ,p1-next,p1-next,p1-next,p2-next=p1,P42 14题（即2002年春的填空题中的14题）,(27) create（int n)struct node *p, *p1 , *p2, *h=NULL; int i=0; if(nx); p-next=NULL; if(h=NULL) (29) ; else p1=p2=h; while(p2,函数返回值类型,如果找到的插入位置是第一个结点,创建结点个数的控制,如果链表为空，直接插入结点作为首结点,如果找到的插入位置不是第一个结点就在找到的位置插入,P42 14题（答案）,(27) create（int n)struct node *p, *p1 , *p2, *h=NULL; int i=0; if(nx); p-next=NULL; if(h=NULL) (29) ; else p1=p2=h; while(p2,struct node *,p-next=p2,inext=NULL) return head; 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; return head;,右移一次,如果是空链表或只有一个结点的链表,左移一次,找到最后一个结点使得p1指向最后一个结点P2指向倒数第二个结点,将最后一个结点（p1指向的）移到链表头,找到最后一个结点P2指向最后一个结点,P51 14题（答案）,Struct node *loop（struct node *head, int dir)struct node *p1 , *p2; p1=head; if(p1=NULL|p1-next=NULL) return head; 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; return head;,p1-next,p2-next,head,p2-next=p1,P60 14题（即2003年春的填空题中的14题）,Struct node *find_del（struct node *head, int *pm)struct node *p1 , *p2 , *pmax , *pre; if(head=NULL) return NULL; 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;Return head;,如果是空链表就结束函数，并返回空指针,首先认为第一个结点是x值最大的结点,Pmax始终指向当前x值最大的结点,P1为工作指针（活动指针）,如果首结点的x值最大就删除首结点,删除pmax指向的结点,将x值最大的结点地址保存到pm指向的指针变量中,P60 14题（即2003年春的填空题中的14题）,Struct node *find_del（struct node *head, int *pm)struct node *p1 , *p2 , *pmax , *pre; if(head=NULL) return NULL; 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;Return head;,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语言的一维数组实现线性表的顺序存储。,顺序表的类型定义#define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量typedef structElemType * elem; /线性表存储空间基址int length; /当前线性表长度int listsize; /当前分配的线性表存储空间大小 /（以sizeof(ElemType)为单位）SqList;,SqList ：类型名，SqList类型的变量是结构变量，它的三个域分别是： *elem：存放线性表元素的一维数组基址；其存储空间在初始化操作（建空表）时动态分配； length：存放线性表的表长； listsize：用于存放当前分配（存放线性表元素）的存储空间的大小。,顺序表图示,存放线性表元素 的一维数组,设 A = （a1,a2 , a3 , . an ）是一线性表，L是SqList 类型的结构变量，用于存放线性表A，则L在内存中的状态如图所示：,如何在顺序表上实现线性表的基本操作？如何建空表？如何求表长？如何插入？删除？,？,设线性表用顺序表L存储，下面我们介绍用顺序表存储线性表时，各种基本操作的算法。当线性表用顺序表存储时，对线性表各种基本操作实际上就是对存储在内存中的顺序表进行操作。,二、顺序表的基本操作算法,取元素操作图示,1 取元素操作 GetElem_Sq ( SqList L, int i, ElemType / GetElem_Sq 算法2.4 由于C语言的一维数组下标从0开始, 故线性表的第一个元素放在L.elem0，第i个素放L.elemi-1中，最后一个元素放在 L.elemL.length-1中。,取元素操作,n LIST_INIT_SIZE-1,ai,再演示一次,2 插入操作 ListInsert_Sq ( 插入操作示意图：,插入操作图示,插入操作主要步骤：1）i 是否合法，若合法转2），否则算法结束，并返回ERROR；2）L是否已满， 若未满转3），否则算法结束，并返回ERROR；3）将顺序表ai 及之后的所有元素后移一个位置；4) 将新元素写入空出的位置；5）表长+1 ；,用鼠标单击图中的绿字,插入元素操作,n LIST_INIT_SIZE-1,插入元素操作,n+1 LIST_INIT_SIZE-1,Status ListInsert_Sq(SqList /ListInsert_Sq 算法2.5a,插入操作算法,为初学者易于理解插入算法，这里通过下标引用L.elem中的元素。,3 删除操作 ListDelete_sq ( SqList &L, int i, ElemType &e ) 功能：删除顺序表L的第i个元素，并用e返回删除操作图示,删除操作主要步骤 ：1）i 不合法或表空，算法结束，并返回ERROR；否则转2）2）将ai赋值给e; 3）将顺序表中ai后面的元素依次向前移动一个位置;4）表长-1,删除操作图示,用鼠标单击图中的绿字,删除元素操作,n LIST_INIT_SIZE-1,删除元素操作,n-1 LIST_INIT_SIZE-1,删除操作算法,Status ListDelete_Sq(SqList /ListDelete_Sq 算法2.56a,为初学者易于理解插入算法，这里通过下标引用L.elem中的元素。,二级考试以往出现的顺序表试题,P61 2003春15题 顺序表排序P49 2002秋12题 顺序表插入元素P40 2002春11题 顺序表处理P29 2001秋12题 顺序表处理P20 2001春12题 顺序表排序,二、文件操作,1、文件类型指针变量的定义格式： FILE 如：FILE *fp；、文件打开与关闭）打开文件-fopen()函数如：FILE *fp; if(fp=fopen(“c:tc2example1.txt”,”w”)= =NULL) printf(“File can noet be opened!n”); exit(0); ,文件打开方式：,）关闭文件-fclose()函数关闭文件的功能：是将写入到内容文件指针位置的内容存储到硬盘上的文件中，并关闭文件，释放文件指针。在程序终止前必须关闭文件。否则，向文件中存入的内容全部没有存入。使用格式：fclose(文件指针)；,文件的相关函数,文件所有的读写，输入输出函数在使用时，必须包含头文件：stdio.h 即：#include 1、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，long offset ，int origin) 参数说明： 1）fp 是指向要进行读写操作的文件结构指针，该文件已由fopen()函数打开； 2）origin是计算文件指针位置的起始点； 文件指针的起始点可以设置在三个不同的位置上，用三个符号常量或数字代表： SEEK_SET 或 0 代表文件头 SEEK_CUR 或 1 代表文件当前位置 SEEK_END 或 2 代表文件尾 3）offset是距起始点的偏移位置，以字节为单位。,二级考试以往出现的文件操作试题,P10 2000秋14题 在文件中查找并替换P19 2001春10题 从文件读入/向文件输出P29、30 2001秋11、13题 从文件读入P40 2002春11题 从文件读入在每次的上机题中，编写的程序输出内容必须输出到文件中,三、递归问题,P7、 P8 2000秋5题、8题 P20 2001春4、12题 用递归实现排序（冒泡排序）P28 2001秋8题P49 2002秋11题P59 2003 春11题,四、字符串操作问题,P9 2000秋12题 从字符串中删除子串P20 2001春13题 插入子串P30 2001秋13题 读子串P39 2002春10题 字符串加密P51 2002秋15题 在字符串中查找子串P59 2003 春12题 字符串处理,五、变量作用域与静态变量问题,P6 2000秋3题 变量作用域P27 2001秋7题 静态变量P38 2002春8题 变量作用域与静态变量P47 2002秋8题 变量作用域P57 2003春8题 变量作用域,六、数列或数字处理问题,P9 2000秋11题 P20 2001春11题 P28 2001秋10题P50 2002秋13题P60 2003 春13题,七、排序问题,共出现三次排序问题：使用了1次冒泡排序，2次选择排序P41 2002春 13题,上 机 考 试-改错题,第一：看函数返回值类型是否正确,03