《VC程序设计链表与链表的基本操作》由会员分享，可在线阅读，更多相关《VC程序设计链表与链表的基本操作（36页珍藏版）》请在金锄头文库上搜索。
1、VC+程序设计 链表与链表的 基本操作链表是一种动态地进行存储分配的结构。最简单的链表称 为单向链表，如图所示： 1249A1356B1475C1021DNULLHead 1249 1356 1475 1021特点： 1。头指针变量head, 它存放一个地址，用于指向一个元素。 链表中的一个元素称为结点。 2。每个结点至少应包含两个部分：一为用户需要的实际数据， 二为下一个结点的地址。 3。“表尾” 的地址部分放一个“Null”（表示“空地址”）。 表示链表的最后一个元素，该元素不再指向其它元素。 简单链表链表中各元素在内存中一般是不连续的。要找某一元素 ，必须先找到上一个元素，根据它提供的下
2、一个元素的地址 才能找到下一个元素。可见，如果不提供头指针，则整个链 表都无法访问。由于链表的每个结点中都必须包含一个指向下一结点的 指针变量和一个结点数据，因此可以用前面介绍的结构体类 型的变量实现。 在定义一个结构体类型时，包含若干成员，而其中成员 之一必须是一个指针变量，该指针变量用于指向下一个具有 相同结构体类型的变量-“结点”。 struct student int num; int score; student *next; ;建立链表一般包括以下几个步骤： 1、建立链表头 head 2、使用动态内存分配技术，在内存中动态建立链表中的各 个结点，并使链表头head指针next指向第
3、一结点，同时，每 个结点的next指针逐一指向下一结点。 3、使链尾结点的指针next指向空结点NULL。 例：写一函数建立一个有3名学生数据（学号、成绩）的单 向链表(以输入num为0表示结束输入)。struct student int num; int score; student *next; ; student *head, *p1, *p2;11041 89.5 next11043 90 next11047 85 NULLnumscorenext$7.1 建立链表headp1p211041 89 nextn=1if(p1-num!=0) head=p1=p2=new student;
4、headp1p211041 89 nextn=2p1 = new student if(p1-num!=0) P2-next=p1;11043 90 nextp1headp1p211041 89 next11043 90 nextp2=p1headp1p211041 89 next11043 90 next11047 85 nextn=3p1=new student;headp1p211041 89 next11043 90 next11047 85 nextn=3if(p1-num!=0) p2-next=p1 p2=p1headp1p211041 89.5 next11043 90 nex
5、t11047 85 NULLn=4p1=new student; if(p1-num = 0) p2-next=NULL; return(head);0 0/建立链表的C+语言函数如下： student *creat( void ) student *head,*p1,*p2;number=0; /结点记数器,全局变量 head=NULLp1=p2=new student;/产生第一个结点coutp1-num; coutp1-score;while(p1-num!=0)number+; /结点记数器 if(number=1) head=p1; else p2-next=p1; p2=p1; p
6、1=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 输出链表从一个链表中删去一个结点，并不一
7、定是真正从内存中 把它抹掉，而是把它从链表中分离开来，即改变链接关系。 headp111041 89 next11043 90 next11047 85 NULL初始 p1=head;$7.7.3 对链表的删除操作headp1p211041 89 next11043 90 next11047 85 NULL如果不是要删除的结点 if(p1-num!=num) p2=p1;p1=p1-next; 如果找到某一结点是要删除的 结点，还要区分两种情况： 1. 要删除的是第一个结点； 2. 要删除的不是第一个结点；此处还要考虑空表的情况。headp111041 8911043 9011047 85 N
8、ULL如果删除的是第一个结点 if(p1=head) head=p1-next;headp1p211041 89 next11043 90 next11047 85 NULL如果删除的不是第一个结点 else p2-next = p1-next; student *del(student *head, long num) student *p1,*p2;if(head = NULL) coutnum p1=p1-next; if(num=p1-num) /找到要删除的结点 if(p1=head) /是第一个结点head = p1-next; delete p1;else p2-next = p
9、1-next; delete p1; /不是第一个结点coutnext; delete p1; headp111041 89 next11043 90 next11047 85 NULL初始 p1=head;释放链表的结点空间headp111041 8911043 9011047 85 NULL初始 p1=p2=head;p0=89102p2 p0设已有的链表中各结点的成员是按学号由小到大顺序排列的。 $7.7.4 对链表的插入操作headp111041 8911043 9011047 85 NULLif(p0-num p1-num) p1=p1-next; /查找要插入结点的位置89102p
10、2p0headp111041 89 next11043 90 next11047 85 NULL找到插入位置后，区分下列情况： 1.插入的是头结点； 2.插入的是链表尾； 3.插入的是中间位置；11042nextp2 p0 3. 插入的是中间位置； if(p0-num num) p2-next=p0;p0-next=p1; headp111041 89.511043 9011047 85 NULLif(p1=head) head=p0;p0-next=p1; 11042p01.插入的是头结点；headp111041 89.511043 9011047 85p0-next =NULL; 1104
11、2NULLp02.插入的是链表尾；student *insert(student *head, student *stud) student *p0,*p1,*p2;p1=head; p0=stud;if(head=Null)/原为空链表head=p0; p0-next=Null; elsewhile(p0-num p1-num) p1=p1-next; ;/插入结点的函数insert如下：if(p0-num num)/找到插入位置 if(p1=head)/插入的是头结点 head=p0; p0-next=p1; else p2-next=p0; p0-next=p1;/插入的是中间位置els
12、e 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
13、; coutstud.num; coutstud.score; head=insert(head, print(head); 7.2.2 单链表类型模板【例7.4_h】单链表的结点采用类，凡与结点数据和指针操作有关 函数作为成员函数。包括：清空链表、查找数据、计算表长、打印 数据、向前生成链表、向后生成链表、按升序生成链表等。 templateclass List; templateclass NodeT info; /数据域Node *link; /指针域 public:Node(); /生成头结点的构造函数Node(const T /生成一般结点的构造函数void InsertAfter(
14、Node* p); /在当前结点后插入一个结点Node* RemoveAfter(); /删除当前结点的后继结点friend class List;/以List为友元类，List可直接访问Node的私有函数 ;template Node:Node()link=NULL; template Node:Node(const T link=NULL; templatevoid Node:InsertAfter(Node* p) p-link=link; link=p; 结点类成员函数:infolinkinfolinkinfolinkp(1)(2)当前结点待插入结点templateNode* Node
15、:RemoveAfter() Node* tempP=link; if(link=NULL) tempP=NULL; /已在链尾,后面无结点 else link=tempP-link; return tempP; infolinkinfolinkinfolink 当前结点tempPlink=tempP-linktemplateclass ListNode *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 Ins
