VC程序设计链表与链表的基本操作.ppt

VC+程序设计链表与链表的基本操作,链表是一种动态地进行存储分配的结构。最简单的链表称为单向链表，如图所示：,1249,A,1356,B,1475,C,1021,D,NULL,Head1249135614751021,特点：1。头指针变量head,它存放一个地址，用于指向一个元素。链表中的一个元素称为结点。2。每个结点至少应包含两个部分：一为用户需要的实际数据，二为下一个结点的地址。3。“表尾”的地址部分放一个“Null”（表示“空地址”）。表示链表的最后一个元素，该元素不再指向其它元素。,简单链表,链表中各元素在内存中一般是不连续的。要找某一元素，必须先找到上一个元素，根据它提供的下一个元素的地址才能找到下一个元素。可见，如果不提供头指针，则整个链表都无法访问。由于链表的每个结点中都必须包含一个指向下一结点的指针变量和一个结点数据，因此可以用前面介绍的结构体类型的变量实现。,在定义一个结构体类型时，包含若干成员，而其中成员之一必须是一个指针变量，该指针变量用于指向下一个具有相同结构体类型的变量-“结点”。structstudentintnum;intscore;student*next;,建立链表一般包括以下几个步骤：1、建立链表头head2、使用动态内存分配技术，在内存中动态建立链表中的各个结点，并使链表头head指针next指向第一结点，同时，每个结点的next指针逐一指向下一结点。3、使链尾结点的指针next指向空结点NULL。,例：写一函数建立一个有3名学生数据（学号、成绩）的单向链表(以输入num为0表示结束输入)。,structstudentintnum;intscore;student*next;student*head,*p1,*p2;,11041,89.5,next,11043,90,next,11047,85,NULL,num,score,next,$7.1建立链表,head,p1,p2,11041,89,next,n=1if(p1-num!=0)head=p1=p2=newstudent;,head,p1,p2,11041,89,next,n=2p1=newstudentif(p1-num!=0)P2-next=p1;,11043,90,next,p1,head,p1,p2,11041,89,next,11043,90,next,p2=p1,head,p1,p2,11041,89,next,11043,90,next,11047,85,next,n=3p1=newstudent;,head,p1,p2,11041,89,next,11043,90,next,11047,85,next,n=3if(p1-num!=0)p2-next=p1p2=p1,head,p1,p2,11041,89.5,next,11043,90,next,11047,85,NULL,n=4p1=newstudent;if(p1-num=0)p2-next=NULL;return(head);,0,0,/建立链表的C+语言函数如下：student*creat(void)student*head,*p1,*p2;number=0;/结点记数器,全局变量head=NULLp1=p2=newstudent;/产生第一个结点coutp1-num;coutp1-score;while(p1-num!=0)number+;/结点记数器if(number=1)head=p1;elsep2-next=p1;p2=p1;p1=newstudent;/产生下一个结点coutp1-num;coutp1-score;p2-next=NULL;/链表尾deletep1;return(head);,要输出链表，首先要知道链表头的地址，然后用一个指针指向第一个结点，输出该结点的数据成员p-num和p-score，再使p指向下一结点，再输出，直到链表的尾结点p-next=NULL。程序如下：voidprint(student*head)structstudent*p=head;coutnumscorenext;while(p!=NULL);,$7.7.2输出链表,从一个链表中删去一个结点，并不一定是真正从内存中把它抹掉，而是把它从链表中分离开来，即改变链接关系。,head,p1,11041,89,next,11043,90,next,11047,85,NULL,初始p1=head;,$7.7.3对链表的删除操作,head,p1,p2,11041,89,next,11043,90,next,11047,85,NULL,如果不是要删除的结点if(p1-num!=num)p2=p1;p1=p1-next;,如果找到某一结点是要删除的结点，还要区分两种情况：要删除的是第一个结点；要删除的不是第一个结点；此处还要考虑空表的情况。,head,p1,11041,89,11043,90,11047,85,NULL,如果删除的是第一个结点if(p1=head)head=p1-next;,head,p1,p2,11041,89,next,11043,90,next,11047,85,NULL,如果删除的不是第一个结点elsep2-next=p1-next;,student*del(student*head,longnum)student*p1,*p2;if(head=NULL)coutnum,删除结点的函数del如下：,voiddeletechain(student*head)student*p1;while(head)p1=head;head=head-next;deletep1;,head,p1,11041,89,next,11043,90,next,11047,85,NULL,初始p1=head;,释放链表的结点空间,head,p1,11041,89,11043,90,11047,85,NULL,初始p1=p2=head;p0=,89102,p2,p0,设已有的链表中各结点的成员是按学号由小到大顺序排列的。,$7.7.4对链表的插入操作,head,p1,11041,89,11043,90,11047,85,NULL,if(p0-nump1-num)/查找要插入结点的位置,89102,p2,p0,head,p1,11041,89,next,11043,90,next,11047,85,NULL,找到插入位置后，区分下列情况：1.插入的是头结点；2.插入的是链表尾；3.插入的是中间位置；,11042,next,p2,p0,3.插入的是中间位置；if(p0-numnum)p2-next=p0;p0-next=p1;,head,p1,11041,89.5,11043,90,11047,85,NULL,if(p1=head)head=p0;p0-next=p1;,11042,p0,1.插入的是头结点；,head,p1,11041,89.5,11043,90,11047,85,11042,NULL,p0,2.插入的是链表尾；,student*insert(student*head,student*stud)student*p0,*p1,*p2;p1=head;p0=stud;if(head=Null)/原为空链表head=p0;p0-next=Null;elsewhile(p0-nump1-num),/插入结点的函数insert如下：,if(p0-numnum)/找到插入位置if(p1=head)/插入的是头结点head=p0;p0-next=p1;elsep2-next=p0;p0-next=p1;/插入的是中间位置elseif(p1-next=Null)/没有找到插入位置并且已经到链尾p1-next=p0;p0-next=Null;number=number+1;return(head);,#include#defineNull0intnum;structstudentintnum;intscore;student*next;,voidmain(void)student*head;intnum;head=creat();print(head);coutnum;head=del(head,num);print(head);studentstud;coutstud.num;coutstud.score;head=insert(head,7.2.2单链表类型模板,【例7.4_h】单链表的结点采用类，凡与结点数据和指针操作有关函数作为成员函数。包括：清空链表、查找数据、计算表长、打印数据、向前生成链表、向后生成链表、按升序生成链表等。templateclassList;templateclassNodeTinfo;/数据域Node*link;/指针域public:Node();/生成头结点的构造函数Node(constT,templateNode:Node()link=NULL;templateNode:Node(constT,结点类成员函数:,p,(1),(2),当前结点,待插入结点,templateNode*Node:RemoveAfter()Node*tempP=link;if(link=NULL)tempP=NULL;/已在链尾,后面无结点elselink=tempP-link;returntempP;,当前结点,tempP,link=tempP-link,templateclassListNode*head,*tail;/链表头指针和尾指针public:List();/构造函数，生成头结点(空链表)List();/析构函数voidMakeEmpty();/清空一个链表，只余表头结点Node*Find(Tdata);/搜索数据域与data相同的结点，返回该结点的地址intLength();/计算单链表长度voidPrintList();/打印链表的数据域voidInsertFront(Node*p);/可用来向前生成链表voidInsertRear(Node*p);/可用来向后生成链表voidInsertOrder(Node*p);/按升序生成链表Node*CreatNode(Tdata);/创建一个结点(孤立结点)Node*DeleteNode(Node*p);/删除指定结点;,再定义链表类，操作包括建立有序链表、搜索遍历、插入、删除、取数据等:,链表类成员函数：,templateList:List()head=tail=newNode();templateList:List()MakeEmpty();deletehead;templatevoidList:MakeEmpty()Node*tempP;while(head-link!=NULL)tempP=head-link;head-link=tempP-link;/把头结点后的第一个结点从链中脱离deletetempP;/删除(释放)脱离下来的结点tail=head;/表头指针与表尾指针均指向表头结点，表示空链,templateNode*List:Find(Tdata)Node*tempP=head-link;while(tempP!=NULL,templatevoidList:PrintList()Node*tempP=head-link;while(tempP!=NULL)coutinfolink;coutvoidList:InsertFront(Node*p)p-link=head-link;head-link=p;if(tail=head)tail=p;,templatevoidList:InsertRear(Node*p)p-link=tail-link;tail-link=p;tail=p;templateNode*List:CreatNode(Tdata)Node*tempP=newNode(data);returntempP;,templatevoidList:InsertOrder(Node*p)Node*tempP=head-link,*tempQ=head;/tempQ指向tempP前面的一个结点while(tempP!=NULL)if(p-infoinfo)break;/找第一个比插入结点大的结点，由tempP指向tempQ=tempP;tempP=tempP-link;tempQ-InsertAfter(p);/插在tempP指向结点之前，tempQ之后if(tail=tem