资源描述
单链表单链表 (Singly Linked List)(Singly Linked List)data linka0a1a2a3a4 head存储存储(cn (cn ch)ch)数数据元素据元素存储后存储后继结点继结点(ji (ji din)din) 存存储地址储地址 头结点 空指针第1页/共23页第一页，共24页。free(a) 可利用存储空间可利用存储空间a0a2a1a3 freehead(b) 经过一段运行后的单链表结构经过一段运行后的单链表结构2000 A 2114 B2056 CNULL200021142056head第2页/共23页第二页，共24页。某单链表示意图(yt)如下：头指针(zhzhn) head110 200200130135135135170170160NullNull165130130170110110200205205205160160165headbat cat eat mat 第3页/共23页第三页，共24页。 用C+语言描述的一个(y )简单的单链表如下： struct node int data; /值域 node *next; /链域 ;第4页/共23页第四页，共24页。例. 建立一个(y )简单的链表，它由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的起始地址赋给a结点的next成员*/ b.next=&c; c.next=NULL;第5页/共23页第五页，共24页。. 创建创建(chungjin)无无序链表序链表 n 一个链表是有若干个结点连接而成，创建(chungjin)链表实际上是创建(chungjin)链表中的各个结点，并将它们连接起来。n 函数nosorted_create( )实现创建(chungjin)链表，其算法为：如果链表为空(head=0)，则将该结点设置为表头；如果链表非空，则将该结点加入到链表的末尾。 第6页/共23页第六页，共24页。n 将结点设置为表头的过程(guchng)如下图所示：pNewhead(b) 加入结点后 head=pNew; pEnd=pNew;pEnd头结点加入结点前加入结点前 head=0; pEnd=pNew;pEndheadpNew第7页/共23页第七页，共24页。n将结点加到链表末尾(mwi)的过程如下图所示：nextdatanextnextdatadata头结点结点n新结点pNewpEndhead(a) 加入前pNew=new node;nextnextdatadata头结点结点nnextdata结点n+1head(b) 加入后pEnd-next=pNew;pEnd=pNew;pEndpNew第8页/共23页第八页，共24页。n链表创建(chungjin)结束next0nextnextdatadata头结点结点n新结点pNewpEndhead(a) 结束前pNew=new node;(b) 结束后pEnd-next=0；delete pNew;next0datadata头结点结点npEndhead第9页/共23页第九页，共24页。. 链表的输出链表的输出(shch)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; 第10页/共23页第十页，共24页。. 链表某个链表某个(mu )结点结点的访问的访问node* access(node* head,int n) if(head=0) coutList is empty!endl; return 0;node *temp;temp=head;for(int i=1;inext=0) cout“要访问(fngwn)的结点数大于链表的结点数.”next;return temp;第11页/共23页第十一页，共24页。. 统计统计(tngj)链表结点的链表结点的个数个数int node_count(node* head) node* temp=head; int count=0; while(temp!=0) count+; temp=temp-next; return count; 第12页/共23页第十二页，共24页。. 访问访问(fngwn)链链表尾结点表尾结点node* accessTail(node* head)if(head=0) return 0;node* temp=head; while(temp-next!=0) temp=temp-next; return temp;第13页/共23页第十三页，共24页。.无序无序(w x)链表链表的插入的插入 headnewnode newnodehead第14页/共23页第十四页，共24页。 headnewnodenewnodehead第15页/共23页第十五页，共24页。newnodecurrentnewnodecurrent第16页/共23页第十六页，共24页。newnodenewnodetailtail 第17页/共23页第十七页，共24页。pcur=head;head=head-next; delete pcur;a1a1a2a2a3a3head删除删除(shnch)前前删除删除(shnch)后后.无序链表结点的删除无序链表结点的删除head第18页/共23页第十八页，共24页。pp-next=q-next; delete q;ai-1ai-1aiaiai+1ai+1q删除删除(shnch)前前删除删除(shnch)后后第19页/共23页第十九页，共24页。.创建创建(chungjin)有有序链表序链表n 所谓有序链表，是指链表中的结点按结点的某个成员的大小进行排列。 n 将一个结点插入到有序链表中时，为了保持有序性，要判断插入的位置。函数 insert_sort_node(node* & ,node* &) 。n 通过(tnggu)上述插入函数，可以创建一个有序链表。n 函数 sorted_create() 。第20页/共23页第二十页，共24页。.链表的删除链表的删除(shnch)void deletelist(node* &head)node* temp;while(head)temp=head;head=head-next;delete temp;第21页/共23页第二十一页，共24页。.无序无序(w x)链表链表的排序的排序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; 第22页/共23页第二十二页，共24页。感谢您的欣赏(xnshng)！第23页/共23页第二十三页，共24页。NoImage内容(nirng)总结特点。每个元素(表项)由结点(Node)构成。用C+语言(yyn)描述的一个简单的单链表如下：。p=p-next。如果链表非空，则将该结点加入到链表的末尾。 if(head=0)。endl。cout datanext。temp=temp-next。if(head=0)。将一个结点插入到有序链表中时，为了保持有序性，要判断插入的位置。第22页/共23页第二十四页，共24页。
展开阅读全文