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

简单链表及其应用

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

每个元素(表项)由结点(Node)构成。线性结构

结点可以不连续存储表可扩充单链表(SinglyLinkedList)data

linka0a1a2a3a4head存储数据元素存储后继结点存储地址头结点空指针某单链表示意图如下：头指针head…………………110hat200………….……130cat135135eat170……….……160matNull165bat130170fat110………………200jat205205lat160………………165headbat

cat

eat

mat

^

…

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

floatscore;p=p->next;

student*next;}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;将结点设置为表头的过程如下图所示：pNewhead(b)

加入结点后head=pNew;pEnd=pNew;pEnd头结点加入结点前

head=0;

pEnd=pNew;pEndheadpNew将结点加到链表末尾的过程如下图所示：nextdatanextnext…datadata头结点结点n…新结点pNewpEndhead(a)加入前pNew=newnode;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.链表某个结点的访问node*access(node*head,intn)

{ if(head==0)

{cout<<"Listisempty!"<<endl;

return0;}

node*temp;

temp=head;

for(inti=1;i<n;i++)

{if(temp->next==0)

{cout<<“要访问的结点数大于链表的结点数.”<<‘\n’;

return0;}

temp=temp->next;

}

returntemp;

}.统计链表结点的个数intnode_count(node*head){node*temp=head;intcount=0;while(temp!=0){count++;temp=temp->next;}returncount;}.访问链表尾结点node*accessTail(node*head){ if(head==0) return0; node*temp=head;while(temp->next!=0)temp=temp->next;returntemp;}

第二种情况：在第一个结点前插入

newnode->next=head;head=newnode;（插入前）（插入后）

headnewnodenewnodehead

第三种情况：在链表中间插入

newnode->next=current->next; current->next=newnode；(插入前)(插入后)newnodecurrentnewnodecurrent

第四种情况：在链表末尾插入

tail->next=newnode；

newnode->next=0;

(插入前)(插入后)newnodenewnodetailtailp第二种情况:删除表中或表尾元素p->next=q->next;deleteq;ai-1ai-1aiaiai+1ai+1q删除前删除后.创建有序链表所谓有序链表，是指链表中的结点按结点的某个成员的大小进行排列。

将一个结点插入到有序链表中时，为了保持有序性，要判断插入的位置。函数insert_sort_node(node*&,node*&)。通过