《C++课件简单链表及其应用.ppt》由会员分享，可在线阅读，更多相关《C++课件简单链表及其应用.ppt（24页珍藏版）》请在三一办公上搜索。
1、简单链表及其应用,链表是指将一组同类型数据（通常为结构体类型）按其特有的方式连接在一起的一种数据结构。链表中的元素称为结点。每一个结点都包含两类数据：一类数据称为结点的值域，它是描述该结点所包含的实际数据，可以由多个不同类型的数据构成；另一类数据称为链域，它用来存储与本结点相邻的结点的地址，其作用是将各个结点连接在一起，它通常是与结点同类型的指针。任何一个链表都一个起始指针，称为该链表的头指针（head）。链表的最后一个结点称为尾结点，它的链域指针不指向任何结点，通常将它设置为空指针。,特点 每个元素(表项)由结点(Node)构成。线性结构 结点可以不连续存储 表可扩充,单链表(Singly
2、Linked List),存储数据元素,存储后继结点 存储地址,头结点,空指针,单链表的存储映像,某单链表示意图如下：,头指针 head,用C+语言描述的一个简单的单链表如下：struct node int data;/值域 node*next;/链域;,例.建立一个简单的链表，它由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,
3、*head,*p;a.num=99101;a.score=89.5;b.num=99103;b.score=90;c.num=99107;c.score=85;head=,.创建无序链表,一个链表是有若干个结点连接而成，创建链表实际上是创建链表中的各个结点，并将它们连接起来。函数nosorted_create()实现创建链表，其算法为：如果链表为空(head=0)，则将该结点设置为表头；如果链表非空，则将该结点加入到链表的末尾。,将结点设置为表头的过程如下图所示：,将结点加到链表末尾的过程如下图所示：,链表创建结束,.链表的输出,void ShowList(node*head)if(head=
4、0)coutdatanext;,.链表某个结点的访问,node*access(node*head,int n)if(head=0)coutnext=0)coutnext;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)t
5、emp=temp-next;return temp;,.无序链表的插入,第一种情况：插入一个空表 head=newnode;head-next=0;,第二种情况：在第一个结点前插入 newnode-next=head;head=newnode;,第三种情况：在链表中间插入 newnode-next=current-next;current-next=newnode；,第四种情况：在链表末尾插入 tail-next=newnode；newnode-next=0;,第一种情况:删除表中第一个元素,pcur=head;head=head-next;delete pcur;,a1,a1,a2,a2,a
6、3,a3,head,删除前,删除后,.无序链表结点的删除,head,p,第二种情况:删除表中或表尾元素,p-next=q-next;delete q;,ai-1,ai-1,ai,ai,ai+1,ai+1,q,删除前,删除后,.创建有序链表,所谓有序链表，是指链表中的结点按结点的某个成员的大小进行排列。将一个结点插入到有序链表中时，为了保持有序性，要判断插入的位置。函数 insert_sort_node(node*&,node*&)。通过上述插入函数，可以创建一个有序链表。函数 sorted_create()。,.链表的删除,void deletelist(node*,.无序链表的排序,void convert()int temp,i,j;node*pcur=head;for(i=1;idatapcur-next-data)temp=pcur-data;pcur-data=pcur-next-data;pcur-next-data=temp;pcur=pcur-next;pcur=head;,
