C++课件简单链表及其应用

《C++课件简单链表及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、简单链表及其应用链表是指将一组同类型数据（通常为结构体类型）按其特有的方式连接在一起的一种数据结构。链表中的元素称为结点。每一个结点都包含两类数据：一类数据称为结点的值域，它是描述该结点所包含的实际数据，可以由多个不同类型的数据构成；另一类数据称为链域，它用来存储与本结点相邻的结点的地址，其作用是将各个结点连接在一起，它通常是与结点同类型的指针。任何一个链表都一个起始指针，称为该链表的头指针（head）。链表的最后一个结点称为尾结点，它的链域指针不指向任何结点，通常将它设置为空指针。特点每个元素(表项)由结点(

2、Node)构成。线性结构结点可以不连续存储表可扩充单链表(SinglyLinkedList)datalinka0a1a2a3a4head存储数据元素存储后继结点存储地址头结点空指针单链表的存储映像free(a)可利用存储空间a0a2a1a3freehead(b)经过一段运行后的单链表结构2000A2114B2056CNULL200021142056head某单链表示意图如下：头指针head…………………110hat200………….……130cat135135eat170……….……160matNull165

3、bat130170fat110………………200jat205205lat160………………165headbatcateatmat^…用C++语言描述的一个简单的单链表如下：structnode{intdata;//值域node*next;//链域};例.建立一个简单的链表，它由3个学生数据的结点组成，输出各结点中的数据。#defineNULL0p=head;structstudentdo{longnum;{cout<num<score;floatscore;p=p->next;student*n

4、ext;}while(p!=NULL);}};voidmain(){studenta,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;.创建无序链表一个链表是有若干个结点连接而成，创建链表实际上是创建链表中的各个结点，并

5、将它们连接起来。函数nosorted_create()实现创建链表，其算法为：如果链表为空(head==0)，则将该结点设置为表头；如果链表非空，则将该结点加入到链表的末尾。将结点设置为表头的过程如下图所示：pNewhead(b)加入结点后head=pNew;pEnd=pNew;pEnd头结点加入结点前head=0;pEnd=pNew;pEndheadpNew将结点加到链表末尾的过程如下图所示：nextdatanextnext…datadata头结点结点n…新结点pNewpEndhead(a)加入前pNew=n

6、ewnode;nextnext…datadata头结点结点n…nextdata结点n+1head(b)加入后pEnd->next=pNew;pEnd=pNew;pEndpNew链表创建结束next0nextnext…datadata头结点结点n…新结点pNewpEndhead(a)结束前pNew=newnode;(b)结束后pEnd->next=0；deletepNew;next0…datadata头结点结点n…pEndhead.链表的输出voidShowList(node*head){if(head==0){

7、cout<<"Listisempty!"<data<next;}}.链表某个结点的访问node*access(node*head,intn){if(head==0){cout<<"Listisempty!"<

8、1;inext==0){cout<<“要访问的结点数大于链表的结点数.”<<‘’;return0;}temp=temp->next;}returntemp;}.统计链表结点的个数intnode_count(node*head){node*temp=head;intcount=0;while(temp!=0){count++;temp=