指针与链表,链表是一种最常见的数据结构，分为动态链表和静态链表。程序员经常使用的是动态链表，它能进行动态内存分配，可以适应数据动态增减的情况，并且可以方便地进行数据元素的插入、删除等操作。 链表有单向链表、双向链表、循环链表等形式。下图是一个单向链表的结构示意图。,用指针处理链表,链表是一种最常见的数据结构，分为动态链表和静态链表。程序员经常使用的是动态链表，它能进行动态内存分配，可以适应数据动态增减的情况，并且可以方便地进行数据元素的插入、删除等操作。 链表有单向链表、双向链表、循环链表等形式。下图是一个单向链表的结构示意图。,8.6 用指针处理链表,头指针:每个链表都有一个“头指针”变量，图中以head表示，它存放一个地址，指向链表的第一个元素。结点:链表中每一个元素被称为一个“结点”(node)。每个结点都应包含两部分，第一部分是链表中存放的用户需要用的实际数据，在图中以、表示；第二部分是一个地址，指向下一个结点。表尾:链表中最后一个结点称为“表尾”，表尾结点存放一个NULL(表示空地址)，因此该结点不再指向其它结点 。,链表是一种最常见的数据结构，分为动态链表和静态链表。程序员经常使用的是动态链表，它能进行动态内存分配，可以适应数据动态增减的情况，并且可以方便地进行数据元素的插入、删除等操作。 链表有单向链表、双向链表、循环链表等形式。下图是一个单向链表的结构示意图。,8.6 用指针处理链表,链表中各结点在内存中可以不是连续存放的，要找到某一结点,必须先找到上一个结点,根据它提供的下一个结点的地址才能找到下一个结点。结点中的地址用指针变量来实现。即一个结点中应包含一个指针变量,用它存放下一个结点的地址。 用结构变量作链表中的结点是最合适的，一个结构体变量包含若干成员，它们可以是数值类型、字符类型、数组类型，也可以是指针类型。我们用这个指针类型成员来存放下一个结点的地址。,链表是一种最常见的数据结构，分为动态链表和静态链表。程序员经常使用的是动态链表，它能进行动态内存分配，可以适应数据动态增减的情况，并且可以方便地进行数据元素的插入、删除等操作。 链表有单向链表、双向链表、循环链表等形式。下图是一个单向链表的结构示意图。,用指针处理链表,struct student int num; float score; student *next; ；,每个结点数据都属于student结构类型，因而next也应为一个student类型的结构指针，它指向下一结点的地址。用这种方法可以建立链表。,链表是一种最常见的数据结构，分为动态链表和静态链表。程序员经常使用的是动态链表，它能进行动态内存分配，可以适应数据动态增减的情况，并且可以方便地进行数据元素的插入、删除等操作。 链表有单向链表、双向链表、循环链表等形式。下图是一个单向链表的结构示意图。,用指针处理链表,struct student int num; float score; student *next; ；,每个结点数据都属于student结构类型，因而next也应为一个student类型的结构指针，它指向下一结点的地址。用这种方法可以建立链表。,链表的特点在于动态地进行内存分配，即在需要时才会开辟一个结点的存储空间，当某个存储空间不再需要时可以释放。在+语言中，可使用new和delete两个运算符进行动态内存的分配和释放。,算法分析: 假设输入的学号为0时，表示建立链表的过程结束，该结点不应链接到链表中。根据题目要求，链表中结点数据应采用结构体类型来描述。 同时定义三个指针变量head，p1，p2，它们都是结构类型的指针变量。结构指针变量head的初值为NULL(即等于0),此时是空链表(head不指向任何结点,链表中无结点)，当链表建成后，应使head指向第一个结点。, 例1 写一个函数，建立一个有5名学生数据(包含学号和成绩)的单向动态链表。,struct student long num; float score; student *next; ; student *head, *p1, *p2; int n=0; /n为结点个数，初值为0,p1,数据域,指针域,建立链表的过程:首先利用new运算符，在内存中开辟一个存储空间,用来存放新结点。使p1,p2都指向该存储空间,然后从键盘上输入一个学生的数据进行判断,如果输入的p1-num不等于0，而且是第一个结点数据（n1）,则把p1的值赋给head(head=p1),这样，结构指针head就指向了链表中的第一个结点。,p2,p1,head,(n=1),建立表头结点,0001,89.5,p2,p1,head,0001,89.5,然后利用new再开辟一个新的存储空间，用来存放另一个结点，并使p1指向新开辟的存储空间，然后输入该结点的数据。如果输入的p1-num不等于0，而且不是第一个结点（n1）时，则应将新建结点与前一个结点连接在一起,即:执行p2 - next=p1，使第一个结点的next 成员指向第二个结点。 接着使p2p1，即:使p2指向刚刚建立的结点(即建立链表进程中的最后一个结点) 。,建立中间结点,(n=2),p2,p1,head,0001,89.5,然后利用new再开辟一个新的存储空间，用来存放另一个结点，并使p1指向新开辟的存储空间，然后输入该结点的数据。如果输入的p1-num不等于0，而且不是第一个结点（n1）时，则应将新建结点与前一个结点连接在一起,即:执行p2 - next=p1，使第一个结点的next 成员指向第二个结点。 接着使p2p1，即:使p2指向刚刚建立的结点(即建立链表进程中的最后一个结点) 。,建立中间结点,(n=2),0002,76,p2,p1,head,0001,89.5,然后利用new再开辟一个新的存储空间，用来存放另一个结点，并使p1指向新开辟的存储空间，然后输入该结点的数据。如果输入的p1-num不等于0，而且不是第一个结点（n1）时，则应将新建结点与前一个结点连接在一起,即:执行p2 - next=p1，使第一个结点的next 成员指向第二个结点。 接着使p2p1，即:使p2指向刚刚建立的结点(即建立链表进程中的最后一个结点) 。,建立中间结点,(n=2),0002,76,p2,p1,head,0001,89.5,然后利用new再开辟一个新的存储空间，用来存放另一个结点，并使p1指向新开辟的存储空间，然后输入该结点的数据。如果输入的p1-num不等于0，而且不是第一个结点（n1）时，则应将新建结点与前一个结点连接在一起,即:执行p2 - next=p1，使第一个结点的next 成员指向第二个结点。 接着使p2p1，即:使p2指向刚刚建立的结点(即建立链表进程中的最后一个结点) 。,(n=2),0002,76,p2,head,0001,89.5,0002,76,重复步骤 ,依次建立若干个新结点。每次都让p1指向新建立的结点，p2指向链表中最后一个结点,然后用“p2-next=p1”，把p1所指的结点连接到p2所指结点的后面。当输入某个结点数据后,如果p1-num等于0,则不再执行上述循环,此新结点不应该被连接到链表中,用语句“p2-next=NULL”,将NULL值赋给前一个结点的next成员。 至此，建立链表的过程结束。,p1,(n=2),p2,head,0001,89.5,0002,76,重复步骤 ,依次建立若干个新结点。每次都让p1指向新建立的结点，p2指向链表中最后一个结点,然后用“p2-next=p1”，把p1所指的结点连接到p2所指结点的后面。当输入某个结点数据后,如果p1-num等于0,则不再执行上述循环,此新结点不应该被连接到链表中,用语句“p2-next=NULL”,将NULL值赋给前一个结点的next成员。 至此，建立链表的过程结束。,p1,0003,88,p2,head,0001,89.5,0002,76,重复步骤 ,依次建立若干个新结点。每次都让p1指向新建立的结点，p2指向链表中最后一个结点,然后用“p2-next=p1”，把p1所指的结点连接到p2所指结点的后面。当输入某个结点数据后,如果p1-num等于0,则不再执行上述循环,此新结点不应该被连接到链表中,用语句“p2-next=NULL”,将NULL值赋给前一个结点的next成员。 至此，建立链表的过程结束。,0003,88,p2,head,0001,89.5,0002,76,重复步骤 ,依次建立若干个新结点。每次都让p1指向新建立的结点，p2指向链表中最后一个结点,然后用“p2-next=p1”，把p1所指的结点连接到p2所指结点的后面。当输入某个结点数据后,如果p1-num等于0,则不再执行上述循环,此新结点不应该被连接到链表中,用语句“p2-next=NULL”,将NULL值赋给前一个结点的next成员。 至此，建立链表的过程结束。,0003,88,0,0,p1,NULL,建立表尾结点,struct student * creat( ) student *head,*p1,*p2; head = NULL; /在没有创建任何结点时，表头指向空 p1 = new student; /创建一个新结点 -（1） p2 = p1; cinp1-nump1-score; /*输入第一个结点的 学生数据*/,p2,p1,head,0001,89.5,(n=1),建立表头结点,while(p1-num != 0) / -（2） n +; if (n = 1) head = p1; / 将链表中第一个新建结点作为表头 else p2-next = p1; p2 = p1; p1 = new(student); / 新建一个结点 cinp1-nump1-score; delete p1; p2-next =NULL; return head; /返回表头指针 /end creat,while(p1-num != 0) / -（2） n +; if (n = 1) head = p1; / 将链表中第一个新建结点作为表头 else p2-next = p1; p2 = p1; p1 = new(student); / 新建一个结点 cinp1-nump1-score; delete p1; p2-next =NULL; return head; /返回表头指针 /end creat,