NCRE-C培训第十部分(补充链表-枚举部分).ppt

10.5 链表处理结构指针的应用 附:请参见教材讲解 10.5.1 概述 1链表结构 链表作为一种常用的、能够实现动态存储分配的数据 结构，在数据结构课程中有详细介绍。为方便没有学 过数据结构的读者，本书从应用角度，对链表作一简单介 绍。图10-1所示为单链表。 （1）头指针变量head指向链表的首结点。 （2）每个结点由2个域组成： 1）数据域存储结点本身的信息。 2）指针域指向后继结点的指针。 （3）尾结点的指针域置为“NULL（空）”，作为链表 结束的标志。 2对链表的基本操作 对链表的基本操作有：创建、检索（查找）、插入、 删除和修改等。 （1）创建链表是指，从无到有地建立起一个链表， 即往空链表中依次插入若干结点，并保持结点之间的前 驱和后继关系。 （2）检索操作是指，按给定的结点索引号或检索条 件，查找某个结点。如果找到指定的结点，则称为检索 成功；否则，称为检索失败。 （3）插入操作是指，在结点ki-1与ki之间插入一个新 的结点k，使线性表的长度增1，且ki-1与ki的逻辑关系发 生如下变化： 插入前，ki-1是ki的前驱，ki是ki-1的后继；插入后，新 插入的结点k成为ki-1的后继、ki的前驱，如图10-2所示。 （4）删除操作是指，删除结点ki，使线性表的长度 减1，且ki-1、ki和ki+1之间的逻辑关系发生如下变化： 删除前，ki是ki+1的前驱、ki-1的后继；删除后，ki-1成 为ki+1的前驱，ki+1成为ki-1的后继，如图10-3所示。 3语言对链表结点的结构描述 在语言中，用结构类型来描述结点结构。例如： struct grade char no7;/*学号*/ int score;/*成绩*/ struct grade *next;/*指针域*/ ; 10.5.2 创建一个新链表 案例10.7 编写一个create()函数，按照规定的结点结构，创建 一个单链表（链表中的结点个数不限）。 基本思路： 首先向系统申请一个结点的空间，然后输入结点数据 域的（2个）数据项，并将指针域置为空（链尾标志）， 最后将新结点插入到链表尾。对于链表的第一个结点， 还要设置头指针变量。 另外，案例代码中的3个指针变量head、new和tail的 说明如下： （1）head头指针变量，指向链表的第一个结点， 用作函数返回值。 （2）new指向新申请的结点。 （3）tail指向链表的尾结点，用tail-next=new， 实现将新申请的结点，插入到链表尾，使之成为新的尾 结点。 /*案例代码文件名：AL10_7.C*/ #define NULL 0 #define LEN sizeof(struct grade)/*定义结点长度*/ /*定义结点结构*/ struct grade char no7;/*学号*/ int score;/*成绩*/ struct grade *next;/*指针域*/ ; /*create()函数: 创建一个具有头结点的单链表*/ /*形参：无*/ /*返回值：返回单链表的头指针*/ struct grade *create( void ) struct grade *head=NULL, *new, *tail; int count=0; /*链表中的结点个数(初值 为0)*/ for( ; ; ) /*缺省3个表达式的for语句 */ new=(struct grade *)malloc(LEN);/*申请一个新结点 的空间*/ /*1、输入结点数据域的各数据项*/ printf(“Input the number of student No.%d(6 bytes): “, count+1); scanf(“%6s“, new-no); if(strcmp(new-no,“000000“)=0) /*如果学号为6个0，则退出*/ free(new); /*释放最后申请的结点空间 */ break; /*结束for语句*/ printf(“Input the score of the student No.%d: “, count+1); scanf(“%d“, count+; /*结点个数加1*/ /*2、置新结点的指针域为空*/ new-next=NULL; /*3、将新结点插入到链表尾，并设置新的尾指针*/ if(count=1) head=new; /*是第一个结点, 置头指针*/ else tail-next=new; /*非首结点, 将新结点插入到链表尾 */ tail=new; /*设置新的尾结点*/ return(head); 程序演示 思考题：在设计存储学号数据的字符数组时，其元素个数应为 学号长度+1。为什么？ 10.5.3 对链表的插入操作 案例10.8 编写一个insert()函数，完成在单链表的第i个结点后 插入1个新结点的操作。当i=0时，表示新结点插入到第一个结点之前 ，成为链表新的首结点。 基本思路： 通过单链表的头指针，首先找到链表的第一个结点； 然后顺着结点的指针域找到第i个结点，最后将新结点插 入到第i个结点之后。 /*案例代码文件名：AL10_8.C*/ /*函数功能：在单链表的第i个结点后插入1个新结点 */ /*函数参数：head为单链表的头指针，new指向要插 入的新结点，i为结点索引号*/ /*函数返回值：单链表的头指针*/ struct grade *insert(struct grade *head, struct grade *new, int i) struct grade *pointer; /*将新结点插入到链表中*/ if(head=NULL) head=new, new-next=NULL; /*将新结点插入 到1个空链表中*/ else/*非空链表*/ if(i=0) new-next=head, head=new; /*使新结点成为 链表 新的首结点*/ else /*其他位置*/ pointer=head; /*查找单链表的第i个结点(pointer指向它)*/ for(; pointer!=NULL pointer=pointer-next, i-) ; if(pointer=NULL) /*越界错*/ printf(“Out of the range, cant insert new node!n“); else /*一般情况：pointer指向第i个结点 */ new-next=pointer-next, pointer-next=new; return(head); 程序演示 Return 10.6枚举型 1枚举类型的定义 enum 枚举类型名 取值表； 例如，enum weekdays Sun,Mon,Tue,Wed,Thu,Fri,Sat； 枚举变量的定义与结构变量类似 （1）间接定义 例如，enum weekdays workday; （2）直接定义 例如，enum weekdays Sun,Mon,Tue,Wed,Thu,Fri,Sat workday; 说明 （1）枚举型仅适应于取值有限的数据。 例如，根据现行的历法规定，周天，年个月。 （2）取值表中的值称为枚举元素，其含义由程序解释。 例如，不是因为写成“Sun”就自动代表“星期天”。事实上， 枚举 元素用什么表示都可以。 （3）枚举元素作为常量是有值的定义时的顺序号 （从开始），所以枚举元素可以进行比较，比较规则 是：序号大