《VC程序设计链表与链表的基本操作》由会员分享，可在线阅读，更多相关《VC程序设计链表与链表的基本操作（36页珍藏版）》请在金锄头文库上搜索。
1、VC+VC+程序设计程序设计链表与链表的链表与链表的基本操作基本操作 链表是一种动态地进行存储分配的结构。最简单的链表称为单向链表，如图所示： 1249A1356B1475C1021DNULLHead 1249 1356 1475 1021特点：1。头指针变量head, 它存放一个地址，用于指向一个元素。链表中的一个元素称为结点。2。每个结点至少应包含两个部分：一为用户需要的实际数据，二为下一个结点的地址。 3。“表尾” 的地址部分放一个“Null”（表示“空地址”）。表示链表的最后一个元素，该元素不再指向其它元素。 简单链表简单链表 链表中各元素在内存中一般是不连续的。要找某一元素，必须先找
2、到上一个元素，根据它提供的下一个元素的地址才能找到下一个元素。可见，如果不提供头指针，则整个链表都无法访问。 由于链表的每个结点中都必须包含一个指向下一结点的指针变量和一个结点数据，因此可以用前面介绍的结构体类型的变量实现。 在定义一个结构体类型时，包含若干成员，而其中成员之一必须是一个指针变量，该指针变量用于指向下一个具有相同结构体类型的变量-“结点”。 struct studentint num;int score;student *next; 建立链表一般包括以下几个步骤：1、建立链表头 head2、使用动态内存分配技术，在内存中动态建立链表中的各个结点，并使链表头head指针next指
3、向第一结点，同时，每个结点的next指针逐一指向下一结点。3、使链尾结点的指针next指向空结点NULL。 例：写一函数建立一个有3名学生数据（学号、成绩）的单向链表(以输入num为0表示结束输入)。struct studentint num;int score;student *next;student *head, *p1, *p2;1104189.5next1104390next1104785NULLnumscorenext$7.1 $7.1 建立链表建立链表headp1p21104189nextn=1if(p1-num!=0)head=p1=p2=new student;headp1p
4、21104189nextn=2p1 = new studentif(p1-num!=0)P2-next=p1;1104390nextp1headp1p21104189next1104390nextp2=p1headp1p21104189next1104390next1104785nextn=3p1=new student;headp1p21104189next1104390next1104785nextn=3if(p1-num!=0)p2-next=p1p2=p1headp1p21104189.5next1104390next1104785NULLn=4p1=new student;if(p1
5、-num = 0)p2-next=NULL;return(head);00/建立链表的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-sc
6、ore; p2-next=NULL;/链表尾delete p1; return(head); 要输出链表，首先要知道链表头的地址，然后用一个指针指向第一个结点，输出该结点的数据成员p-num和p-score，再使p指向下一结点，再输出，直到链表的尾结点p-next=NULL。程序如下：void print(student *head) struct student *p=head; coutn Now,There are number records: n; if(head !=NULL) do coutnumtscorenext; while(p!=NULL);$7.7.2 $7.7.2 输
7、出链表输出链表 从一个链表中删去一个结点，并不一定是真正从内存中把它抹掉，而是把它从链表中分离开来，即改变链接关系。 headp11104189next1104390next1104785NULL初始 p1=head; $7.7.3 $7.7.3 对链表的删除操作对链表的删除操作headp1p21104189next1104390next1104785NULL如果不是要删除的结点if(p1-num!=num) p2=p1; p1=p1-next;如果找到某一结点是要删除的结点，还要区分两种情况：1.要删除的是第一个结点；2.要删除的不是第一个结点；此处还要考虑空表的情况。headp111041
8、8911043901104785NULL如果删除的是第一个结点if(p1=head)head=p1-next;headp1p21104189next1104390next1104785NULL如果删除的不是第一个结点else p2-next = p1-next;student *del(student *head, long num) student *p1,*p2; if(head = NULL) coutnum & p1-next!=NULL) p2=p1; p1=p1-next; if(num=p1-num) /找到要删除的结点找到要删除的结点 if(p1=head) /是第一个结点是第
9、一个结点 head = p1-next; delete p1; else p2-next = p1-next; delete p1; /不是第一个结点不是第一个结点 cout删除删除: numn; number=number-1;/结点记数器减一结点记数器减一 else /没有要删除的结点没有要删除的结点coutnumnext;delete p1;headp11104189next1104390next1104785NULL初始 p1=head;释放链表的结点空间headp1110418911043901104785NULL初始 p1=p2=head; p0=&stud;89102p2p0设已
10、有的链表中各结点的成员是按学号由小到大顺序排列的。 $7.7.4 $7.7.4 对链表的插入操作对链表的插入操作headp1110418911043901104785NULLif(p0-num p1-num) & ( p1-next!=NULL) p2=p1; p1=p1-next; /查找要插入结点的位置查找要插入结点的位置89102p2p0headp11104189next1104390next1104785NULL找到插入位置后，区分下列情况：1.插入的是头结点；2.插入的是链表尾；3.插入的是中间位置；11042nextp2p03. 插入的是中间位置；if(p0-num num) p2
11、-next=p0; p0-next=p1;headp11104189.511043901104785NULLif(p1=head) head=p0; p0-next=p1;11042p01.插入的是头结点；headp11104189.511043901104785&（p0-num p1-num）if(p1-next = NULL) p1-next=p0; p0-next =NULL;11042NULLp02.插入的是链表尾；student *insert(student *head, student *stud) student *p0,*p1,*p2; p1=head; p0=stud; i
12、f(head=Null)/原为空链表原为空链表 head=p0; p0-next=Null; else while(p0-num p1-num)&(p1-next != Null) /查找插入位置查找插入位置p2=p1; p1=p1-next; ;/插入结点的函数插入结点的函数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) /没有
13、找到插入位置并且已经到链尾没有找到插入位置并且已经到链尾 p1-next=p0; p0-next=Null; number=number+1; return(head);#include#define Null 0int num;struct studentint 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;cout输入要插入的节点：输入要插入的节点：
14、; coutstud.num;coutstud.score;head=insert(head,&stud);print(head);7.2.2 7.2.2 单链表类型模板单链表类型模板【例例7.4_h】单链表的结点采用类，凡与结点数据和指针操作有关单链表的结点采用类，凡与结点数据和指针操作有关函数作为成员函数。包括：清空链表、查找数据、计算表长、打印函数作为成员函数。包括：清空链表、查找数据、计算表长、打印数据、向前生成链表、向后生成链表、按升序生成链表等。数据、向前生成链表、向后生成链表、按升序生成链表等。templateclass List;templateclass Node T inf
15、o; /数据域数据域 Node *link; /指针域指针域public: Node(); /生成头结点的构造函数生成头结点的构造函数 Node(const T & data); /生成一般结点的构造函数生成一般结点的构造函数 void InsertAfter(Node* p); /在当前结点后插入一个结点在当前结点后插入一个结点 Node* RemoveAfter(); /删除当前结点的后继结点删除当前结点的后继结点 friend class List; /以以List为友元类，为友元类，List可直接访问可直接访问Node的私有函数的私有函数;template Node:Node()lin
16、k=NULL;template Node:Node(const T & data)info=data;link=NULL;templatevoid Node:InsertAfter(Node* p)p-link=link;link=p;结点类成员函数结点类成员函数:infolinkinfolinkinfolinkp(1)(2)当前结点待插入结点templateNode* Node:RemoveAfter()Node* tempP=link;if(link=NULL) tempP=NULL; /已在链尾已在链尾,后面无结点后面无结点else link=tempP-link;return temp
17、P;infolinkinfolinkinfolink当前结点tempPlink=tempP-linktemplateclass List Node *head,*tail; /链表头指针和尾指针链表头指针和尾指针public: List(); /构造函数，生成头结点构造函数，生成头结点(空链表空链表) List(); /析构函数析构函数 void MakeEmpty(); /清空一个链表，只余表头结点清空一个链表，只余表头结点 Node* Find(T data); /搜索数据域与搜索数据域与data相同的结点，返回该结点的地址相同的结点，返回该结点的地址 int Length(); /计算单
18、链表长度计算单链表长度 void PrintList(); /打印链表的数据域打印链表的数据域 void InsertFront(Node* p); /可用来向前生成链表可用来向前生成链表 void InsertRear(Node* p); /可用来向后生成链表可用来向后生成链表 void InsertOrder(Node *p); /按升序生成链表按升序生成链表 Node*CreatNode(T data); /创建一个结点创建一个结点(孤立结点孤立结点) Node*DeleteNode(Node* p); /删除指定结点删除指定结点;再定义链表类，操作包括建立有序链表、搜索遍历、再定义链表
19、类，操作包括建立有序链表、搜索遍历、插入、删除、取数据等插入、删除、取数据等:链表类成员函数：链表类成员函数：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; /删除(释放)脱离下来的结点
20、tail=head; /表头指针与表尾指针均指向表头结点，表示空链template Node* List:Find(T data) Node *tempP=head-link; while(tempP!=NULL&tempP-info!=data) tempP=tempP-link; return tempP; /搜索成功返回该结点地址，不成功返回NULLtemplateint List:Length( ) Node* tempP=head-link; int count=0; while(tempP!=NULL) tempP=tempP-link; count+; return count;
21、templatevoid List:PrintList( ) Node* tempP=head-link; while(tempP!=NULL) coutinfolink; coutendl;templatevoid 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)
22、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(tail=tempQ) tail=tem
23、pQ-link;templateNode* List:DeleteNode(Node* p) Node* tempP=head; while(tempP-link!=NULL&tempP-link!=p) tempP=tempP-link; if(tempP-link=tail) tail=tempP; return tempP-RemoveAfter( ); /本函数所用方法可省一个工作指针，与InsertOrder比较【例例7.47.4】由由键键盘盘输输入入1616个个整整数数，以以这这些些整整数数作作为为结结点点数数据据，生生成成两两个个链链表表，一一个个向向前前生生成成，一一个个向向后后生生成成，输输出出两两个个表表。然然后后给给出出一一个个整整数数在在一一个个链链表表中中查查找找，找找到到后后删删除除它它，再输出该表。清空该表，再按升序生成链表并输出。再输出该表。清空该表，再按升序生成链表并输出。在在VC+VC+平台上演示本例。平台上演示本例。在本例中程序只需调用类模板中的成员函数就可以完成所在本例中程序只需调用类模板中的成员函数就可以完成所有链表操作。有链表操作。
