C语言程序设计实用教程-第15章链表.ppt

《C语言程序设计实用教程》 主要内容及难点 概述 15.1 初识链表 15.2 链表与节点 15.2.1 空链表 15.2.2 链表的节点 15.2.3 创建一个简单的链表 15.3 头插法创建链表 _1 15.3 头插法创建链表 _2 15.4 尾插法创建链表 15.5 链表的插入操作 15.6 链表的删除操作 15.7 综合举例 15.7.1 旋转链表 15.7.2 围圈留一 15.8 小节 * Power point 制作：耿祥义 张跃平 第15章 链表 当需要动态地减少或增加数据项时，可以使用链表这种数据结构。 链表是由若干个称作节点的数据项组成的一种数据结构，每个节点含有一个数据和下一个节点的地址（单链表），或含有一个数据并含有上一个节点和下一个节点的地址（双链表）。 对于本章例子中的的C程序，在用VC++6.0时，要建立相应的工程，并将源文件加到工程中 。 用下列结构体类型变量在内存形成的结构来模拟情报人员的之间形成的关系，如图15.1所示。这种结构就是一个链表 。 struct Peoson { int number; char * name; struct Peoson * next; }; 1．链表的头指针：指向链表的第一个节点（头节点）的struct Peoson类型的指针变量head称作链表的头指针。 2．链表的名字： 用头指针的名字来命名链表的名字。 3．链表的索引与长度：链表中节点的个数称作链表的长度。 4．节点的指针域与数据域： 一个节点中含有一个指针（变量），名字通常为next，next中存放着下一个节点的地址。next指针变量在当前节点中所占用的内存区域称作节点的指针域。节点中还含有存放数据的一些变量，这些变量在当前节点中所占有的内存称作节点的数据域。 本节使用的结构体类型如下： typedef struct Peoson { int number; char * name; struct Peoson * next; } PERSON; 当声明一个PERSON类型的指针变量，即给出链表的头指针，但头指针未指向PERSON类型的变量，比如头指针head： PERSON * head = NULL; 那么称head是一个空链表。 空链表中无任何节点。 ◆构造节点： void * malloc(unsigned int size)函数为节点分配内存空间，并返回该内存空间的首地址。例如，为了构造出一个PERSON类型的节点，需进行如下的操作： PERSON * node; node = malloc(sizeof(PERSON)); ◆使用节点中的成员 node-number =10016; node-name = 张三; ◆删除节点 void free(void *p)函数用来释放（自由）malloc函数分配的内存空间 ，例如 free(node); ◆动态链表 如果链表的节点是用malloc函数分配的内存，那么就可以使用free函数释放该节点的内存。这样的链表也被称作动态链表。 创建有3个节点的链表，步骤如下： 1．创建一个空链表head 2．添加第1个节点nodeOne 3．添加第2个节点nodeTwo 4．添加最后一个节点nodeThree。 例子1(example15_1.c)根据上述步骤的编写的代码 。 本节使用的结构体类型如下： typedef struct node { char ch; struct node * next; } NODE; 头插法建立链表就是每次向链表添加的新节点将作为链表的头节点，链表的原节点的索引依次增1。 假设有链表head。头插法的步骤如下： 1 创建一个新节点newNode,代码如下 newNode = malloc(sizeof(NODE)); 2 将新节点的指针域中的next指针（变量）的值设置为头指针的值，代码如下： newNode-next = head 3 让头指针指向新节点，代码如下：head = newNode; 经过上述步骤后，newNode就是链表head的头节点。 ◆如果head是空链表,进过步骤2和3之后，链表head的结构如图15.6。 ◆如果head是非空链表,进过步骤2和3之后，链表head的结构如图15.7。 例子2(example15_2.c)使用头插法建立了具有6个节点的链表，并输出了链表节点中的数据 。 尾插法建立链表就是每次向链表添加的新节点将作为链表的尾节点。 尾插法的步骤如下： 1．创建一个新