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

《NCRE-C培训第十部分(补充链表-枚举部分)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、：创建、检索（查找）、插入、删除和修改等。（1）创建链表是指，从无到有地建立起一个链表，即往空链表中依次插入若干结点，并保持结点之间的前驱和后继关系。（2）检索操作是指，按给定的结点索引号或检索条件，查找某个结点。如果找到指定的结点，则称为检索成功；否则，称为检索失败。（3）插入操作是指，在结点ki-1与ki之间插入一个新的结点k’，使线性表的长度增1，且ki-1与ki的逻辑关系发生如下变化：插入前，ki-1是ki的前驱，ki是ki-1的后继；插入后，新插入的结点k’成为ki-1的后继、ki的前驱，如图10-2所示。（

3、4）删除操作是指，删除结点ki，使线性表的长度减1，且ki-1、ki和ki+1之间的逻辑关系发生如下变化：删除前，ki是ki+1的前驱、ki-1的后继；删除后，ki-1成为ki+1的前驱，ki+1成为ki-1的后继，如图10-3所示。3．Ｃ语言对链表结点的结构描述在Ｃ语言中，用结构类型来描述结点结构。例如：structgrade{charno[7];/*学号*/intscore;/*成绩*/structgrade*next;/*指针域*/};10.5.2创建一个新链表[案例10.7]编写一个create()函数，按照规

4、定的结点结构，创建一个单链表（链表中的结点个数不限）。基本思路：首先向系统申请一个结点的空间，然后输入结点数据域的（2个）数据项，并将指针域置为空（链尾标志），最后将新结点插入到链表尾。对于链表的第一个结点，还要设置头指针变量。另外，案例代码中的3个指针变量head、new和tail的说明如下：（1）head──头指针变量，指向链表的第一个结点，用作函数返回值。（2）new──指向新申请的结点。（3）tail──指向链表的尾结点，用tail->next=new，实现将新申请的结点，插入到链表尾，使之成为新的尾结点。/*

5、案例代码文件名：AL10_7.C*/#defineNULL0#defineLENsizeof(structgrade)/*定义结点长度*//*定义结点结构*/structgrade{charno[7];/*学号*/intscore;/*成绩*/structgrade*next;/*指针域*/};/*create()函数:创建一个具有头结点的单链表*//*形参：无*//*返回值：返回单链表的头指针*/structgrade*create(void){structgrade*head=NULL,*new,*tail;int

6、count=0;/*链表中的结点个数(初值为0)*/for(;;)/*缺省3个表达式的for语句*/{new=(structgrade*)malloc(LEN);/*申请一个新结点的空间*//*1、输入结点数据域的各数据项*/printf("InputthenumberofstudentNo.%d(6bytes):",count+1);scanf("%6s",new->no);if(strcmp(new->no,"000000")==0)/*如果学号为6个0，则退出*/{free(new);/*释放最后申请的结点空间*

7、/break;/*结束for语句*/}printf("InputthescoreofthestudentNo.%d:",count+1);scanf("%d",&new->score);count++;/*结点个数加1*//*2、置新结点的指针域为空*/new->next=NULL;/*3、将新结点插入到链表尾，并设置新的尾指针*/if(count==1)head=new;/*是第一个结点,置头指针*/elsetail->next=new;/*非首结点,将新结点插入到链表尾*/tail=new;/*设置新的尾结点*/}

8、return(head);}[程序演示]思考题：在设计存储学号数据的字符数组时，其元素个数应为学号长度+1。为什么？10.5.3对链表的插入操作[案例10.8]编写一个insert()函数，完成在单链表的第i个结点后插入1个新结点的操作。当i=0时，表示新结点插入到第一个结点之前，成为链表新的首结点。基本思路：通过单链表的头指针，