《C++课件简单链表及其应用.ppt》由会员分享，可在线阅读，更多相关《C++课件简单链表及其应用.ppt（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、简单链表及其应用简单链表及其应用n 链表链表是指将一组同类型数据（通常为结构体类型）按其特有的方式连接在一起的一种数据结构。n 链表中的元素称为结点结点。每一个结点都包含两类数据：一类数据称为结点的值域值域，它是描述该结点所包含的实际数据，可以由多个不同类型的数据构成；另一类数据称为链域链域，它用来存储与本结点相邻的结点的地址，其作用是将各个结点连接在一起，它通常是与结点同类型的指针。n 任何一个链表都一个起始指针，称为该链表的头指针头指针（head）。n 链表的最后一个结点称为尾结点尾结点，它的链域指针不指向任何结点，通常将它设置为空指针空指针。n n特点特点uu 每个元素每个元素(表项表项
2、)由结点由结点(Node)构成。构成。uu 线性结构线性结构uu 结点可以不连续存储结点可以不连续存储uu 表可扩充表可扩充单链表单链表(Singly Linked List)(Singly Linked List)data linka0a1a2a3a4 head存储数据元素存储数据元素存储后继结点存储后继结点 存储地址存储地址 头结点头结点 空指针空指针单链表的存储映像单链表的存储映像freefree(a)(a)可利用存储空间可利用存储空间可利用存储空间可利用存储空间a0a2a1a3 freehead(b)经过一段运行后的单链表结构经过一段运行后的单链表结构2000 A 2114 B2056
3、 CNULL200021142056head某单链表示意图如下：头指针 head110 hathathathat200200.130catcatcatcat135135135eateateateat170170.160matmatmatmatNullNull165batbatbatbat130130170fatfatfatfat110110200jatjatjatjat205205205latlatlatlat160160165headbat cat eat mat 用C+语言描述的一个简单的单链表如下：struct node int data;/值域值域 node *next;/链域链域 ;
4、例.建立一个简单的链表，它由3个学生数据的结点组成，输出各结点中的数据。#define NULL 0 p=head;struct student do long 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的
5、起始地址赋给a结点的next成员*/b.next=&c;c.next=NULL;.创建无序链创建无序链表表 n 一个链表是有若干个结点连接而成，创建链表实际上是创建链表中的各个结点，并将它们连接起来。n 函数nosorted_create()实现创建链表，其算法为：如果链表为空(head=0)，则将该结点设置为表头；如果链表非空，则将该结点加入到链表的末尾。n 将结点设置为表头的过程如下图所示：pNewhead(b)加入结点后加入结点后 head=pNew;pEnd=pNew;pEnd头结点头结点(a)加入结点前加入结点前(b)head=0;(c)pEnd=pNew;pEndheadpNewn
6、将结点加到链表末尾的过程如下图所示：nextdatanextnextdatadata头结点头结点结点结点n新结点新结点pNewpEndhead(a)加入前加入前pNew=new node;nextnextdatadata头结点头结点结点结点nnextdata结点结点n+1head(b)加入后加入后pEnd-next=pNew;pEnd=pNew;pEndpNewn链表创建结束next0nextnextdatadata头结点头结点结点结点n新结点新结点pNewpEndhead(a)结束前结束前pNew=new node;(b)结束后结束后pEnd-next=0；delete pNew;next0
7、datadata头结点头结点结点结点npEndhead.链链表的输出表的输出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;.链链表某个结点的访问表某个结点的访问node*access(node*head,int n)if(head=0)coutList is empty!endl;return 0;node*temp;temp=head;for(int i=1;i
8、next=0)cout“要访问的结点数大于链表的结点数要访问的结点数大于链表的结点数.”next;return temp;.统计统计链链表结点的个数表结点的个数int node_count(node*head)node*temp=head;int count=0;while(temp!=0)count+;temp=temp-next;return count;.访问访问链链表尾结点表尾结点node*accessTail(node*head)if(head=0)return 0;node*temp=head;while(temp-next!=0)temp=temp-next;return tem
9、p;.无序链表的插入无序链表的插入n n 第一种情况：插入一个空表第一种情况：插入一个空表 head=newnode;head-next=0;（插入前）（插入前）（插入后）（插入后）headnewnode newnodeheadn n 第二种情况：在第一个结点前插入第二种情况：在第一个结点前插入 newnode-next=head;head=newnode;（插入前）（插入前）（插入后）（插入后）headnewnodenewnodeheaduu 第三种情况：在链表中间插入第三种情况：在链表中间插入 newnode-next=current-next;current-next=newnode；(
10、插入前插入前)()(插入后插入后)newnodecurrentnewnodecurrentuu 第四种情况：在链表末尾插入第四种情况：在链表末尾插入 tail-next=newnode；newnode-next=0;(插入前插入前)()(插入后插入后)newnodenewnodetailtail n n第一种情况第一种情况:删除表中第一个元素删除表中第一个元素pcur=head;head=head-next;delete pcur;a1a1a2a2a3a3head删除前删除前删除后删除后.无序链表结点的删除无序链表结点的删除headpuu第二种情况第二种情况:删除表中或表尾元删除表中或表尾元素
11、素p-next=q-next;delete q;ai-1ai-1aiaiai+1ai+1q删除前删除前删除后删除后.创建有序链表创建有序链表n 所谓有序链表有序链表，是指链表中的结点按结点的某个成员的大小进行排列。n 将一个结点插入到有序链表中时，为了保持有序性，要判断插入的位置。函数 insert_sort_node(node*&,node*&)。n 通过上述插入函数，可以创建一个有序链表。n 函数 sorted_create()。.链表的删除链表的删除void deletelist(node*&head)node*temp;while(head)temp=head;head=head-next;delete temp;.无序链表的排序无序链表的排序void convert()int temp,i,j;node*pcur=head;for(i=1;inode_count(head);i+)for(j=1;jdatapcur-next-data)temp=pcur-data;pcur-data=pcur-next-data;pcur-next-data=temp;pcur=pcur-next;pcur=head;