版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、C+课件简单链表及其应用C+课件简单链表及其应用特点 每个元素(表项)由结点(Node)构成。 线性结构 结点可以不连续存储 表可扩充单链表 (Singly Linked List)data linka0a1a2a3a4head存储数据元素存储后继结点 存储地址 头结点 空指针特点单链表 (Singly Linked List)data单链表的存储映像free(a) 可利用存储空间a0a2a1a3freehead(b) 经过一段运行后的单链表结构2000 A 2114 B2056 CNULL200021142056head单链表的存储映像free(a) 可利用存储空间a0a2a1a某单链表示意
2、图如下:头指针 head110 hat200.130cat135135eat170.160matNull165bat130170fat110200jat205205lat160165headbat cat eat mat 某单链表示意图如下:头指针 head110 h 用C+语言描述的一个简单的单链表如下: struct node int data; /值域 node *next; /链域 ; 用C+语言描述的一个简单的单链表如下:例. 建立一个简单的链表,它由3个学生数据的结点组成, 输出各结点中的数据。#define NULL 0 p=head;struct student do long
3、 num; coutnumscore; float score; p=p-next; student *next; while(p!=NULL); ;void main()student a,b,c,*head,*p; a.num=99101; a.score=89.5; b.num=99103; b.score=90; c.num=99107; c.score=85; head=&a; /*将结点a的起始地址赋给头指针head*/ a.next=&b; /*将结点b的起始地址赋给a结点的next成员*/ b.next=&c; c.next=NULL;例. 建立一个简单的链表,它由3个学生数据
4、的结点组成,. 创建无序链表 一个链表是有若干个结点连接而成,创建链表实际上是创建链表中的各个结点,并将它们连接起来。 函数nosorted_create( )实现创建链表,其算法为:如果链表为空(head=0),则将该结点设置为表头;如果链表非空,则将该结点加入到链表的末尾。 . 创建无序链表 一个链表是有若干个结点连接而成,创建链 将结点设置为表头的过程如下图所示:pNewhead(b) 加入结点后 head=pNew; pEnd=pNew;pEnd头结点加入结点前 head=0; pEnd=pNew;pEndheadpNew 将结点设置为表头的过程如下图所示:pNewhead(将结点加到
5、链表末尾的过程如下图所示:nextdatanextnextdatadata头结点结点n新结点pNewpEndhead(a) 加入前pNew=new node;nextnextdatadata头结点结点nnextdata结点n+1head(b) 加入后pEnd-next=pNew;pEnd=pNew;pEndpNew将结点加到链表末尾的过程如下图所示:nextdatanext链表创建结束next0nextnextdatadata头结点结点n新结点pNewpEndhead(a) 结束前pNew=new node;(b) 结束后pEnd-next=0;delete pNew;next0datadat
6、a头结点结点npEndhead链表创建结束next0nextnextdatadata头结. 链表的输出void ShowList(node* head) if(head=0) coutList is empty!endl; return; node *temp=head; cout now the items of list are: n; while(temp!=0) cout datanext; . 链表的输出void ShowList(node* hea. 链表某个结点的访问node* access(node* head,int n) if(head=0) coutList is emp
7、ty!endl; return 0;node *temp;temp=head;for(int i=1;inext=0) cout“要访问的结点数大于链表的结点数.”next;return temp;. 链表某个结点的访问node* access(node* . 统计链表结点的个数int node_count(node* head) node* temp=head; int count=0; while(temp!=0) count+; temp=temp-next; return count; . 统计链表结点的个数int node_count(node. 访问链表尾结点node* acces
8、sTail(node* head)if(head=0) return 0;node* temp=head; while(temp-next!=0) temp=temp-next; return temp;. 访问链表尾结点node* accessTail(node.无序链表的插入 第一种情况:插入一个空表 head = newnode; head-next=0;(插入前) (插入后) headnewnode newnodehead.无序链表的插入 第一种情况:插入一个空表(插入前) 第二种情况:在第一个结点前插入 newnode-next = head ; head = newnode;(插入
9、前) (插入后) headnewnodenewnodehead 第二种情况:在第一个结点前插入(插入前) 第三种情况:在链表中间插入 newnode-next = current-next; current-next = newnode;(插入前) (插入后)newnodecurrentnewnodecurrent 第三种情况:在链表中间插入(插入前) 第四种情况:在链表末尾插入 tail-next = newnode; newnode-next = 0; (插入前) (插入后)newnodenewnodetailtail 第四种情况:在链表末尾插入(插入前) 第一种情况: 删除表中第一个元素
10、pcur=head;head=head-next; delete pcur;a1a1a2a2a3a3head删除前删除后.无序链表结点的删除head第一种情况: 删除表中第一个元素pcur=head;headp第二种情况: 删除表中或表尾元素p-next=q-next; delete q;ai-1ai-1aiaiai+1ai+1q删除前删除后p第二种情况: 删除表中或表尾元素p-next=q-ne.创建有序链表 所谓有序链表,是指链表中的结点按结点的某个成员的大小进行排列。 将一个结点插入到有序链表中时,为了保持有序性,要判断插入的位置。函数 insert_sort_node(node* & ,node* &) 。 通过上述插入函数,可以创建一个有序链表。 函数 sorted_create() 。.创建有序链表 所谓有序链表,是指链表中的结点按结点的某个.链表的删除void deletelist(node* &head)node* temp;while(head)temp=head;head=head-next;delete temp;.链表的删除void deletelist(node* &h.无序链表的排序void convert() int temp,i,j; node* pcur=head; for(i=1;inode_
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 涂层加工合同范例
- 防尘工安全生产岗位责任制模版(2篇)
- 大连市2024年度个人租房合同
- 植保冬季防寒合同模板
- 纹绣培训合同范例
- 关于材料购买合同
- 二零二四年度产品研发与技术支持服务合同
- 电器礼品采购合同模板
- 环境综合整治工作方案(3篇)
- 2024房屋租赁合同标准版范本
- 【人教版】《劳动教育》五上 劳动项目三《制作扇子》 课件
- 《公共科目》军队文职考试试题及解答参考(2024年)
- 2024年秋季新人教版七年级上册英语全册教案设计
- 《零售变革新零售时代》演讲课件
- 法律服务投标方案(技术方案)
- 2024年人教版七年级上册历史第三单元综合检测试卷及答案
- 2024年江苏省高中学业水平合格性考试数学试卷试题(答案详解1)
- DZ∕T 0148-2014 水文水井地质钻探规程(正式版)
- 初中八年级英语课件周琦8A Unit7 Seasons Welcome课件
- 高级政工师职称面试题
- 完整解读中华人民共和国政府信息公开条例课件
评论
0/150
提交评论