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

VC+程序设计链表与链表的基本操作,链表是一种动态地进行存储分配的结构。最简单的链表称为单向链表，如图所示：,1249,A,1356,B,1475,C,1021,D,NULL,Head 1249 1356 1475 1021,特点： 1。头指针变量head, 它存放一个地址，用于指向一个元素。 链表中的一个元素称为结点。 2。每个结点至少应包含两个部分：一为用户需要的实际数据， 二为下一个结点的地址。 3。“表尾” 的地址部分放一个“Null”（表示“空地址”）。 表示链表的最后一个元素，该元素不再指向其它元素。,简单链表,链表中各元素在内存中一般是不连续的。要找某一元素，必须先找到上一个元素，根据它提供的下一个元素的地址才能找到下一个元素。可见，如果不提供头指针，则整个链表都无法访问。 由于链表的每个结点中都必须包含一个指向下一结点的指针变量和一个结点数据，因此可以用前面介绍的结构体类型的变量实现。,在定义一个结构体类型时，包含若干成员，而其中成员之一必须是一个指针变量，该指针变量用于指向下一个具有相同结构体类型的变量-“结点”。 struct student int num; int score; student *next; ;,建立链表一般包括以下几个步骤： 1、建立链表头 head 2、使用动态内存分配技术，在内存中动态建立链表中的各个结点，并使链表头head指针next指向第一结点，同时，每个结点的next指针逐一指向下一结点。 3、使链尾结点的指针next指向空结点NULL。,例：写一函数建立一个有3名学生数据（学号、成绩）的单向链表(以输入num为0表示结束输入)。,struct student int num; int score; 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=1 if(p1-num!=0) head=p1=p2=new student;,head,p1,p2,11041,89,next,n=2 p1 = new student if(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=3 p1=new student;,head,p1,p2,11041,89,next,11043,90,next,11047,85,next,n=3 if(p1-num!=0) p2-next=p1 p2=p1,head,p1,p2,11041,89.5,next,11043,90,next,11047,85,NULL,n=4 p1=new student; if(p1-num = 0) p2-next=NULL; return(head);,0,0,/建立链表的C+语言函数如下： student *creat( void ) student *head,*p1,*p2; number=0; /结点记数器,全局变量 head=NULL p1=p2=new student; /产生第一个结点 coutp1-num; coutp1-score; while(p1-num!=0) number+; /结点记数器 if(number=1) head=p1; else p2-next=p1; p2=p1; p1=new student; /产生下一个结点 coutp1-num; coutp1-score; p2-next=NULL; /链表尾 delete p1; return(head); ,要输出链表，首先要知道链表头的地址，然后用一个指针指向第一个结点，输出该结点的数据成员p-num和p-score，再使p指向下一结点，再输出，直到链表的尾结点p-next=NULL。 程序如下： void print(student *head) struct student *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,如果删除的不是第一个结点 else p2-next = p1-next; ,student *del(student *head, long num) student *p1,*p2; if(head = NULL) coutnum ,删除结点的函数del如下：,void deletechain(student *head) student *p1; while(head) p1=head; head=head-next; delete p1; ,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-num p1-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-num num) 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; else while(p0-num p1-num),/插入结点的函数insert如下：,if(p0-num num) /找到插入位置 if(p1=head) /插入的是头结点 head=p0; p0-next=p1; else p2-next=p0; p0-next=p1; /插入的是中间位置 else if(p1-next = Null) /没有找到插入位置并且已经到链尾 p1-next=p0; p0-next=Null; number=number+1; return(head); ,#include #define Null 0 int num; struct student int num; int score; student *next; ;,void main( void ) student *head; int num; head=creat( ); print(head); coutnum; head=del(head,num); print(head); student stud; coutstud.num; coutstud.score; head=insert(head, ,7.2.2 单链表类型模板,【例7.4_h】单链表的结点采用类，凡与结点数据和指针操作有关函数作为成员函数。包括：清空链表、查找数据、计算表长、打印数据、向前生成链表、向后生成链表、按升序生成链表等。 templateclass List; templateclass Node T info; /数据域 Node *link; /指针域 public: Node(); /生成头结点的构造函数 Node(const T ,template Node:Node()link=NULL; template Node:Node(const T ,结点类成员函数:,p,(1),(2),当前结点,待插入结点,templateNode* Node:RemoveAfter() Node* tempP=link; if(link=NULL) tempP=NULL; /已在链尾,后面无结点 else link=tempP-link; return tempP; ,当前结点,tempP,link=tempP-link,templateclass List Node *head,*tail; /链表头指针和尾指针 public: List(); /构造函数，生成头结点(空链表) List(); /析构函数 void MakeEmpty(); /清空一个链表，只余表头结点 Node* Find(T data); /搜索数据域与data相同的结点，返回该结点的地址 int Length(); /计算单链表长度 void PrintList(); /打印链表的数据域 void InsertFront(Node* p); /可用来向前生成链表 void InsertRear(Node* p); /可用来向后生成链表 void InsertOrder(Node *p); /按升序生成链表 Node*CreatNode(T data); /创建一个结点(孤立结点) Node*DeleteNode(Node* p); /删除指定结点 ;,再定义链表类，操作包括建立有序链表、搜索遍历、插入、删除、取数据等:,链表类成员函数：,templateList:List( ) head=tail=new Node( ); templateList:List( ) MakeEmpty( ); delete head; templatevoid List:MakeEmpty( ) Node *tempP; while(head-link!=NULL) tempP=head-link; head-link=tempP-link; /把头结点后的第一个结点从链中脱离 delete tempP; /删除(释放)脱离下来的结点 tail=head; /表头指针与表尾指针均指向表头结点，表示空链,template Node* List:Find(T data) Node *tempP=head-link; while(tempP!=NULL ,templatevoid List:PrintList( ) Node* tempP=head-link; while(tempP!=NULL) coutinfolink; coutvoid List:InsertFront(Node *p) p-link=head-link; head-link=p; if(tail=head) tail=p; ,templatevoid List:InsertRear(Node *p) p-link=tail-link; tail-link=p; tail=p; templateNode* List:CreatNode(T data) Node*tempP=new Node(data); return tempP; ,templatevoid List: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