c语言之链表.docx
《c语言之链表.docx》由会员分享，可在线阅读，更多相关《c语言之链表.docx（14页珍藏版）》请在冰点文库上搜索。
c语言之链表
−目录
∙第6讲动态数据结构（链表操作）
o学习目标
o授课内容
▪3.4动态数据结构
▪回顾1-4
▪5.链表的遍历
▪6.在链表中查找数据
▪7.在链表中插入数据
▪
（1）在表头插入数据
▪
（2）在表尾插入数据
▪（3）在有序表中插入数据
▪8.在链表中删除数据
▪9.链表的释放
第6讲动态数据结构（链表操作）
学习目标
【重点】
∙链表的遍历，插入和删除
【难点】
∙链表插入，链表删除
【学习要求】
∙1.掌握遍历链表的方法，并能够运用（如：
打印，查找等）。
∙2.了解在链表中插入数据的方法，能够通过插入元素建立链表。
∙3.了解在链表中删除数据的方法。
∙4.了解释放链表空间的方法。
【考核要求】
∙1.会编写遍历链表的程序，并能够实现打印、查找等功能。
∙2.熟悉动态分配链表结点的过程。
∙3.理解在链表中（包括开头、末尾和中间位置）插入数据的程序，会用链表结构示意图分析程序执行过程。
∙4.理解在链表中删除数据的程序，会用链表结构示意图分析程序执行过程。
∙5.理解释放链表空间的程序。
授课内容
3.4动态数据结构
回顾1-4
∙1.问题提出（数组与链表的对比）
∙2.链表概念（链表，结点，数据域，指针域，头指针）
∙3.结点结构的定义
structLink
{
intdata;//数据域（此处假设为整型）
structLink*next;//指针域
};
∙4.链表的特点
o优点：
插入、删除方便，不需要移动其他结点
o缺点：
只能顺序访问，一旦断链就会丢失其中的数据。
5.链表的遍历
遍历就是逐个访问每个数据元素的过程。
遍历是各种其他操作的基础。
以遍历并打印数据为例：
//遍历链表head，并依次打印每个结点中的数据
voidPrintList（structLink*head）
{
structLink*p;
p=head;//从头指针开始遍历
while（p!
=NULL）{
printf（"%d",p->data）;//访问（打印）结点中的数据
p=p->next;//指针移动到下一个结点
}
}
测试代码如下：
intmain（）
{
structLinka={1},b={2},c={3};
structLink*head;
//手工建立链表
a.next=&b;b.next=&c;c.next=NULL;
head=&a;
//打印链表
PrintList（head）;//123
return0;
}
遍历的关键是指针的在链表结点之间的移动。
遍历中“访问”结点数据的含义非常广泛，可以是打印，也可以是比较等其他操作。
6.在链表中查找数据
在链表中查找数据，可以通过在遍历的过程中跟要查找的内容比较来实现。
对于查找结果，在查找成功时，我们可以返回指向结点的指针，查找失败时，返回空指针。
//在链表head中查找x
//如果找到，返回指向结点的指针，否则，返回空指针
structLink*Find（structLink*head,intx）
{
structLink*p;
p=head;
while（p!
=NULL）{
if（p->data==x）returnp;//查找成功
p=p->next;
}
returnNULL;//查找失败
}
也可以改写为：
p=head;
while（p!
=NULL&&p->data!
=x）
p=p->next;
returnp;
测试代码如下：
intmain（）
{
structLinka={1},b={2},c={3};
structLink*head;
structLink*p;
intx;
//手工建立链表
a.next=&b;b.next=&c;c.next=NULL;
head=&a;
//查找x
x=2;
p=Find（head,x）;
if（p!
=NULL）
printf（"Found%d",p->data）;
else
printf（"Notfound%d",x）;
//打印链表
PrintList（head）;//123
return0;
}
还可以将x修改为其他值进行测试。
7.在链表中插入数据
按插入位置在表头、表尾和中间分三种情况讨论。
（1）在表头插入数据
首先要动态分配结点存放待插入的数据，然后再在链表中插入新的结点。
//在链表head开头插入数据x
//插入成功，返回新的表头
structLink*InsertFirst（structLink*head,intx）
{
structLink*s;
//新建节点s
s=（structLink*）malloc（sizeof（structLink））;
if（s==NULL）exit（0）;
s->data=x;
//将s插入表头
s->next=head;
head=s;
//返回新表头
returnhead;
}
注意将s插入表头时修改指针的顺序。
一般先修改新建结点的指针域。
注意返回值的处理：
因为插入操作可能使头指针改变，因此返回新的头指针方便使用。
测试代码：
intmain（）
{
structLink*head=NULL;//空表
head=InsertFirst（head,1）;//调用后注意保持新表头指针
head=InsertFirst（head,2）;
head=InsertFirst（head,3）;
head=InsertFirst（head,4）;
head=InsertFirst（head,5）;
PrintList（head）;//54321
return0;
}
（2）在表尾插入数据
一般情况下，首先要找到表尾结点p，然后在p之后插入新结点s。
如果链表是空表，则不存在表尾结点，此时只要插入表头即可。
实现代码如下：
//在链表head末尾插入数据x
//插入成功，返回新的表头
structLink*InsertLast（structLink*head,intx）
{
structLink*s,*p;
//新建节点s
s=（structLink*）malloc（sizeof（structLink））;
if（s==NULL）exit（0）;
s->data=x;
//查找表尾（插入位置）p
p=head;
while（p!
=NULL&&p->next!
=NULL）
p=p->next;
//插入数据
if（p==NULL）{//在空表中插入
s->next=head;
head=s;
}else{//在p之后插入s
s->next=p->next;//这里也可以s->next=NULL;
p->next=s;
}
//返回新的表头
returnhead;
}
测试代码：
intmain（）
{
structLink*head=NULL;//空表
head=InsertLast（head,1）;//调用后注意保持新表头指针
head=InsertLast（head,2）;
head=InsertLast（head,3）;
head=InsertLast（head,4）;
head=InsertLast（head,5）;
PrintList（head）;//12345
return0;
}
（3）在有序表中插入数据
所谓有序表，是指链表中的数据按有序排列，如从小到大或从大到小。
以下如无特殊说明，有序表中的数据从小到大有序。
在有序表中插入，也可分为在表头和表中（表尾）插入两种情况。
一般情况下，需要先查找小于等于x的最后一个结点p，然后在p之后插入。
在空表，或者第一数据元素大于待插入数据时，需要在表头插入，需要特殊处理。
实现代码：
//链表head中的数据从小到大有序排列
//在有序表head中插入数据x，仍然保持整个表有序
//插入成功，返回新的表头
structLink*OrderInsert（structLink*head,intx）
{
structLink*s,*p;
//新建节点s
s=（structLink*）malloc（sizeof（structLink））;
if（s==NULL）exit（0）;
s->data=x;
//插入数据
if（head==NULL||head->data>x）{
//需要在表头插入
s->next=head;
head=s;
}else{
//查找插入位置p
p=head;
while（p->next!
=NULL&&p->next->data<=x）
p=p->next;
//在p之后插入s
s->next=p->next;
p->next=s;
}
//返回新的表头
returnhead;
}
测试代码：
intmain（）
{
structLink*head=NULL;//空表
intx;
//输入若干整数（0作为结尾），插入有序表
scanf（"%d",&x）;
while（x!
=0）{
head=OrderInsert（head,x）;
scanf（"%d",&x）;
}
PrintList（head）;
return0;
}
8.在链表中删除数据
9.链表的释放
∙登录
∙文章
∙讨论
∙阅读
∙显示源文件
∙修订记录
搜索
窗体顶端
窗体底端
导航
教学资源
∙数据结构
∙算法分析与设计
∙软件测试
∙程序设计基础
∙C语言程序设计
∙计算机导论
∙JAVA语言程序设计
∙Web开发框架研究
∙计算机文化基础
∙Java2010
∙JSP
专业教学
∙计算机科学与技术专业
∙通信工程专业
∙计算机网络技术专业
∙软件技术专业
视频资源
∙教学视频
技术资料
∙Grails
∙Java
∙实用技巧
科研资源
∙科研园地
打印/导出
∙可打印版本
工具箱
∙反向链接
∙最近更改
∙上传文件
∙站点索引
∙永久链接
∙引用此文
升级会员 