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

1、10.5 链表处理结构指针的应用附:请参见教材讲解,10.5.1 概述 1链表结构 链表作为一种常用的、能够实现动态存储分配的数据结构，在数据结构课程中有详细介绍。为方便没有学过数据结构的读者，本书从应用角度，对链表作一简单介绍。图10-1所示为单链表。 （1）头指针变量head指向链表的首结点。 （2）每个结点由2个域组成： 1）数据域存储结点本身的信息。 2）指针域指向后继结点的指针。 （3）尾结点的指针域置为“NULL（空）”，作为链表结束的标志。,2对链表的基本操作 对链表的基本操作有：创建、检索（查找）、插入、删除和修改等。 （1）创建链表是指，从无到有地建立起一个链表，即往空链表中

2、依次插入若干结点，并保持结点之间的前驱和后继关系。 （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成

3、为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个）数据项，并将指针域置为空（链尾标志），最后将新结点插入到链表尾。对于链表的第一个结点，还要设置头指针变量。

4、 另外，案例代码中的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;/

5、*指针域*/ ; /*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、(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, /*3、将新结点插入到链表尾，并设置新的尾指针*/,if(count=1) head=new; /*是第一个结点, 置头指针*/ else tail-next=new; /*非首结点, 将新结点插入

7、到链表尾*/ tail=new; /*设置新的尾结点*/ return(head); 程序演示 思考题：在设计存储学号数据的字符数组时，其元素个数应为学号长度+1。为什么？ 10.5.3 对链表的插入操作 案例10.8 编写一个insert()函数，完成在单链表的第i个结点后插入1个新结点的操作。当i=0时，表示新结点插入到第一个结点之前，成为链表新的首结点。,基本思路： 通过单链表的头指针，首先找到链表的第一个结点；然后顺着结点的指针域找到第i个结点，最后将新结点插入到第i个结点之后。 /*案例代码文件名：AL10_8.C*/ /*函数功能：在单链表的第i个结点后插入1个新结点*/ /*函数

8、参数：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 /*其他位置*/

9、pointer=head; /*查找单链表的第i个结点(pointer指向它)*/ for(; pointer!=NULL 程序演示 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）枚举元素作为常量是有值的定义时的顺序号（从开始），所以枚举元素可以进行比较，比较规则是：序号大者为大！ 例如，上例中的S