C语言链表ppt课件.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(unsignedn,unsignedsize);
作用：在内存动态区中分配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例题911.7.6对链表的删除操作链表中结点删除图11.19图11.20图11.20例题1011.7.7对链表的插入操作操作分析图11.22图11.22例题115分析：按三种情况
1、第一种情况，链表还未建成（空链表），待插入结点p实际上是第一个结点。这时必然有head==null。只要让头指针指向p就可以了。语句为63、第三种情况，链表已建成，待插入结点p的数据比头结点的数据大，需要找到正确的插入位置。这时，可以借助两个结构指针r和g，利用循环比较来找到正确位置。然后将结点p插入到链表中正确的位置。

参见下面的图示666//结构7.c

#include<stdio.h> //预编译命令
#include<malloc.h> //内存空间分配
#definenull0 //定义空指针常量
#defineLENsizeof(structnumST) //定义常量，表示结构长度

structnumST //结构声明
{
intnum; //整型数
structnumST*next; //numST结构指针
};
//被调用函数insert()，两个形参分别表示链表和待插入的结点
voidinsert(structnumST**phead,structnumST*p)
{ //函数体开始
structnumST*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结构指针，用于输出链表内容
voidprint(structnumST*head)
{
intk=0; //整型变量，用于计数
structnumST*r; //声明r为ST结构指针
r=head; //r赋值为head，即指向链表头

while(r!=null) //当型循环，链表指针不为空则继续
{ //循环体开始
k=k+1; //计数加1
printf("%d%d\n",k,r->num);
r=r->next; //取链表中相邻的