C语言链表探析.ppt

第十一章 链表;例：跳马。依下图将每一步跳马之后的位置(x,y)放到一个“结点”里，再用“链子穿起来”，形成一条链，相邻两结点间用一个指针将两者连到一起。;依上图有7个结点;11.7 用指针处理链表;1249;链表中结点的定义;链表的基本操作; （4）删除操作是指，删除结点ki，使线性表的长度减1，且ki-1、ki和ki+1之间的逻辑关系发生如下变化： 删除前，ki是ki+1的前驱、ki-1的后继；删除后，ki-1成为ki+1的前驱，ki+1成为ki-1的后继. (5)打印输出;一个指针类型的成员既可指向其它类型的结构体数据，也可以指向自己所在的结构体类型的数据;11.7.2 简单链表; 11.7.3 处理动态链表所需的函数;函数原形:void *calloc(unsigned n,unsigned size); 作用：在内存动态区中分配 n个 长度为size的连续空间。 函数返回值：指向分配域起始地址的指针 执行失败：返回null 主要用途：为一维数组开辟动态存储空间。n 为数组元素个数，每个元素长度为size ;3. free 函数;结点的动态分配;11.7.4 建立动态链表;11.7.4 建立动态链表;图11.14;图11.14;图11.15; 图11.16 ;例11.8 建立一个有3名学生数据的单向动态链表;续;11.7.5 输出链表;图 11.18;例题 9;11.7.6 对链表的删除操作;链表中结点删除;图11.19;图11.20;图11.20;例 题 10;11.7.7 对链表的插入操作; 操 作 分 析;图11.22;图11.22;例 题 11;5;分析：按三种情况 1、第一种情况，链表还未建成（空链表），待插入结点p实际上是第一个结点。这时必然有head==null。只要让头指针指向 p 就可以了。语句为;6;3、第三种情况，链表已建成，待插入结点 p 的数据比头结点的数据大，需要找到正确的插入位置。这时，可以借助两个结构指针r 和 g，利用循环比较来找到正确位置。然后将结点 p 插入到链表中正确的位置。 参见下面的图示;6;6;6;// 结构7.c #include stdio.h // 预编译命令 #include malloc.h // 内存空间分配 #define null 0 // 定义空指针常量 #define LEN sizeof(struct numST) // 定义常量，表示结构长度 struct numST // 结构声明 { int num; // 整型数 struct numST *next; // numST结构指针 }; ;// 被调用函数insert()，两个形参分别表示链表和待插入的结点 void insert (struct numST **phead, struct numST *p) { // 函数体开始 struct numST *q,*r; // 定义结构指针q,r if ((*phead)==null) // 第一种情况，链表为空 { *phead = p; // 链表头指向p return; // 完成插入操作，返回 } else // 链表不为空 { // 第二种情况，p结点num值小于链表头结点的num值 if ( (*phead)-num p-num) { // 将p结点插到链表头部 p-next = *phead;// 将p的next指针指向链表头(*phead) *phead = p; // 将链表头赋值为p return; // 返回 }; // 第三种情况，循环查找正确位置 r = *phead; // r赋值为链表头 q = (*phead)-next; // q赋值为链表的下一个结点 while (q!=null) // 利用循环查找正确位置 { // 判断当前结点num是否小于p结点的num if (q-num p-num) { r = q; // r赋值为q，即指向q所指的结点 q = q-next;// q指向链表中相邻的下一个结点 } else // 找到了正确的位置 break; // 退出循环 } // 将p结点插入正确的位置 r-next = p; p-next = q; } };// 被调用函数，形参为ST结构指针，用于输出链表内容 void print(struct numST *head) { int k=0; // 整型变量，用