链表及其基本操作ppt课件.ppt

VC++++课程07级copyright:柏毅版本号:-。最简单的链表称为单向链表,如图所示:1249A1356B1475C1021DNULLHead1249135614751021特点:1。头指针变量head,它存放一个地址,用于指向一个元素。链表中的一个元素称为结点。2。每个结点至少应包含两个部分:一为用户需要的实际数据,二为下一个结点的地址。3。“表尾”的地址部分放一个“Null”(表示“空地址”)。表示链表的最后一个元素,该元素不再指向其它元素。简单链表链表中各元素在内存中一般是不连续的。要找某一元素,必须先找到上一个元素,根据它提供的下一个元素的地址才能找到下一个元素。可见,如果不提供头指针,则整个链表都无法访问。由于链表的每个结点中都必须包含一个指向下一结点的指针变量和一个结点数据,因此可以用前面介绍的结构体类型的变量实现。在定义一个结构体类型时,包含若干成员,而其中成员之一必须是一个指针变量,该指针变量用于指向下一个具有相同结构体类型的变量---“结点”。structstudent{ intnum; intscore; student*next;};建立链表一般包括以下几个步骤:1、建立链表头head2、使用动态内存分配技术,在内存中动态建立链表中的各个结点,并使链表头head指针next指向第一结点,同时,每个结点的next指针逐一指向下一结点。3、使链尾结点的指针next指向空结点NULL。例:写一函数建立一个有3名学生数据(学号、成绩)的单向链表(以输入num为0表示结束输入)。structstudent{ intnum; intscore; student*next;};student*head,*p1,*p2;$=1if(p1->num!=0)head=p1=p2=newstudent;headp1p21104189nextn=2p1=newstudentif(p1->num!=0)P2->next=p1;1104390nextp1headp1p21104189next1104390nextp2=p1headp1p21104189next1104390next1104785nextn=3p1=newstudent;headp1p21104189next1104390next1104785nextn=3if(p1->num!=0)p2->next=p1p2==4p1=newstudent;if(p1->num==0)p2->next=NULL;return(head);00//建立链表的C++语言函数如下:student*creat(void){ student*head,*p1,*p2; number=0; //结点记数器,全局变量 head=NULL p1=p2=newstudent; //产生第一个结点 cout<<"num:"; cin>>p1->num; cout<<"score:"; cin>>p1->score; while(p1->num!=0) { number++; //结点记数器 if(number==1)head=p1; elsep2->next=p1; p2=p1; p1=newstudent; //产生下一个结点 cout<<"num:";cin>>p1->num; cout<<"score:"; cin>>p1->score; } p2->next=NULL; //链表尾 deletep1; return(head);}