【文档说明】C++课件简单链表及其应用.ppt，共(25)页，670.000 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-44712.html

以下为本文档部分文字说明：

特点每个元素(表项)由结点(Node)构成。线性结构结点可以不连续存储表可扩充单链表(SinglyLinkedList)datalinka0a1a2a3a4head存储数据元素存储后继结点存储地址头结点空指针单链表的存储映像free(a)可利用存储空间a0a2a1

a3freehead(b)经过一段运行后的单链表结构2000A2114B2056CNULL200021142056head某单链表示意图如下：头指针head…………………110hat200………….……130cat135135eat170……….……160

matNull165bat130170fat110………………200jat205205lat160………………165headbatcateatmat^…用C++语言描述的一个简单的单链表如下：structnode{intdata;//值域node*next;//链域};

例.建立一个简单的链表，它由3个学生数据的结点组成，输出各结点中的数据。#defineNULL0p=head;structstudentdo{longnum;{cout<<p->num<<p->scor

e;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=9910

7;c.score=85;head=&a;/*将结点a的起始地址赋给头指针head*/a.next=&b;/*将结点b的起始地址赋给a结点的next成员*/b.next=&c;c.next=NULL;.创建无序链表一个链表是有若干个结点连接而成，创建

链表实际上是创建链表中的各个结点，并将它们连接起来。函数nosorted_create()实现创建链表，其算法为：如果链表为空(head==0)，则将该结点设置为表头；如果链表非空，则将该结点加入到链表的末尾。将

结点设置为表头的过程如下图所示：pNewhead(b)加入结点后head=pNew;pEnd=pNew;pEnd头结点(a)加入结点前(b)head=0;(c)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=new

node;(b)结束后pEnd->next=0；deletepNew;next0…datadata头结点结点n…pEndhead.链表的输出voidShowList(node*head){if(head==0

){cout<<"Listisempty!"<<endl;return;}node*temp=head;cout<<"nowtheitemsoflistare:\n";while(temp!=0){cout<<temp->data<<endl;temp=temp->next;}}.链表某个

结点的访问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)r

eturn0;node*temp=head;while(temp->next!=0)temp=temp->next;returntemp;}.无序链表的插入第一种情况：插入一个空表head=newnode;head->next=0;（插入前）（插

入后）headnewnode^newnodehead第二种情况：在第一个结点前插入newnode->next=head;head=newnode;（插入前）（插入后）headnewnodenewnodehead第三种情况：在链表中间插入newnode->next=current->

next;current->next=newnode；(插入前)(插入后)newnodecurrentnewnodecurrent第四种情况：在链表末尾插入tail->next=newnode；newnode->ne

xt=0;(插入前)(插入后)newnodenewnodetailtail第一种情况:删除表中第一个元素pcur=head;head=head->next;deletepcur;a1a1a2a2a3a3hea

d删除前删除后.无序链表结点的删除headp第二种情况:删除表中或表尾元素p->next=q->next;deleteq;ai-1ai-1aiaiai+1ai+1q删除前删除后.创建有序链表所谓

有序链表，是指链表中的结点按结点的某个成员的大小进行排列。将一个结点插入到有序链表中时，为了保持有序性，要判断插入的位置。函数insert_sort_node(node*&,node*&)。通过上述插入函数，可以创建一个有序链表。函数sorted_crea

te()。.链表的删除voiddeletelist(node*&head){node*temp;while(head){temp=head;head=head->next;deletetemp;}}.无序链表的排序voidconvert(){inttemp,i,j;node*pcur=head

;for(i=1;i<node_count(head);i++){for(j=1;j<=node_count(head)-i;j++){if(pcur->data>pcur->next->data){temp=pcur->data;pcur->data=pcur->next-

>data;pcur->next->data=temp;}pcur=pcur->next;}pcur=head;}}谢谢大家！