c语言之链表.docx
- 文档编号:9216777
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:14
- 大小:20.78KB
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
∙实用技巧
科研资源
∙科研园地
打印/导出
∙可打印版本
工具箱
∙反向链接
∙最近更改
∙上传文件
∙站点索引
∙永久链接
∙引用此文
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言