C语言程序设计实用教程-第15章链表

《C语言程序设计实用教程》Powerpoint制作：耿祥义张跃平第15章链表2010-10主要内容及难点

2010-10概述当需要动态地减少或增加数据项时，可以使用链表这种数据结构。链表是由假设干个称作节点的数据项组成的一种数据结构，每个节点含有一个数据和下一个节点的地址〔单链表〕，或含有一个数据并含有上一个节点和下一个节点的地址〔双链表〕。对于本章例子中的的C程序，在用VC++6.0时，要建立相应的工程，并将源文件加到工程中。2010-1015.1初识链表用以下结构体类型变量在内存形成的结构来模拟情报人员的之间形成的关系，如图15.1所示。这种结构就是一个链表。structPeoson{intnumber;char*name;structPeoson*next;};1．链表的头指针：指向链表的第一个节点〔头节点〕的structPeoson类型的指针变量head称作链表的头指针。2．链表的名字：用头指针的名字来命名链表的名字。3．链表的索引与长度：链表中节点的个数称作链表的长度。4．节点的指针域与数据域：一个节点中含有一个指针〔变量〕，名字通常为next，next中存放着下一个节点的地址。next指针变量在当前节点中所占用的内存区域称作节点的指针域。节点中还含有存放数据的一些变量，这些变量在当前节点中所占有的内存称作节点的数据域。2010-1015.2链表与节点本节使用的结构体类型如下：typedefstructPeoson{ intnumber; char*name; structPeoson*next;}PERSON;当声明一个PERSON类型的指针变量，即给出链表的头指针，但头指针未指向PERSON类型的变量，比方头指针head：PERSON*head=NULL;那么称head是一个空链表。空链表中无任何节点。15.2.1空链表2010-1015.2.2链表的节点◆构造节点：void*malloc(unsignedintsize)函数为节点分配内存空间，并返回该内存空间的首地址。例如，为了构造出一个PERSON类型的节点，需进行如下的操作：PERSON*node;node=malloc(sizeof(PERSON));◆使用节点中的成员node->number=10016;node->name="张三";◆删除节点voidfree(void*p)函数用来释放〔自由〕malloc函数分配的内存空间，例如free(node);◆动态链表如果链表的节点是用malloc函数分配的内存，那么就可以使用free函数释放该节点的内存。这样的链表也被称作动态链表。2010-1015.2.3创立一个简单的链表创立有3个节点的链表，步骤如下：1．创立一个空链表head2．添加第1个节点nodeOne3．添加第2个节点nodeTwo4．添加最后一个节点nodeThree。例子1(example15_1.c)根据上述步骤的编写的代码。

2010-1015.3头插法创立链表_1本节使用的结构体类型如下：typedefstructnode{ charch; structnode*next;}NODE;头插法建立链表就是每次向链表添加的新节点将作为链表的头节点，链表的原节点的索引依次增1。假设有链表head。头插法的步骤如下：1创立一个新节点newNode,代码如下newNode=malloc(sizeof(NODE));2将新节点的指针域中的next指针〔变量〕的值设置为头指针的值，代码如下：newNode->next=head3让头指针指向新节点，代码如下：head=newNode;经过上述步骤后，newNode就是链表head的头节点。◆如果head是空链表,进过步骤2和3之后，链表head的结构如图15.6。◆如果head是非空链表,进过步骤2和3之后，链表head的结构如图15.7。2010-1015.3头插法创立链表_2例子2(example15_2.c)使用头插法建立了具有6个节点的链表，并输出了链表节点中的数据。2010-1015.4尾插法创立链表尾插法建立链表就是每次向链表添加的新节点将作为链表的尾节点。尾插法的步骤如下：1．创立一个新节点newNode，代码如下：newNode=malloc(sizeof(NODE));2．如果链表head是空链表，设置新节点是尾节点，将头节点指向新节点，代码如下：newNode->next=head;head=newNode;如果链表head是非空链表，找到当前链表的最后一个节点,将当前链表的最后一个节点的指针域中的next指针〔变量〕指向新节点，将新节点设置为尾节点。代码如下：NODE*foundEndNode=head;while((foundEndNode-next)!=NULL){foundEndNode=foundEndNode->next;}foundEndNode->next=newNode;newNode->next=NULL;经过上述步骤后，newNode就是链表head的尾节点例子3(example15_3.c)使用头插法建立了具有6个节点的链表,并输出了链表节点中的数据。2010-1015.5链表的插入操作在链表的第i个节点和第i+1个节点之间插入一个新节点的步骤如下：1在链表中寻找第i个节点：NODE*getNode(NODE*head,inti){ intm=1;NODE*node_i=head; while((node_i->next!=NULL)&&(m<i)){ node_i=node_i->next; m++; } if(m==i) returnnode_i; else returnNULL;}2创立一个新节点newNode：newNode=malloc(sizeof(NODE));3将新节点的next指针指向第i+1个节点，将第i个节点中的next指针指向新节点,代码如下：newNode->next=node_i->next;node_i->next=newNode;经过上述步骤后，newNode成为链表的第i+1个节点，而原来的第i+1个节点以及之后后的各个节点的索引依次增1。例子4(example15_4.c)使用尾插法建立了具有6个节点的链表，然后在第3和第4个节点之间插入一个新节点，新节点中的数据是字符'@'。插入新节点后，程序输出了链表节点中的数据。2010-1015.6链表的删除操作使用malloc函数为节点分配内存空间，例如：NODE*node;node=malloc(sizeof(NODE));当从链表中删除节点node后，必须使用free函数释放该节点所占用的内存，即执行代码：free(node);释放节点node占用的内存。1．删除链表head的头节点的代码如下：NODE*temp=head;//保存头节点的地址;head=head->next;//将头指针指向头节点的后继节点free(temp);//释放头节点的内存2．删除链表head的第i个节点〔i>1〕的步骤如下：〔1〕找到链表中的第i-1个节点，代码如下：foreNode=getNode(head,i-1);//见上一节中的getNode函数〔2〕删除foreNode的后继节点，代码如下：node_i=foreNode->next;//保存第i个节点的地址foreNode->next=node_i->next//将第i-1个节点的后继节点设置为链表的第i+1个节点〔3〕释放第i个节点的内存，代码如下：free(node_i);例子5(example15_5.c)首先使用头插法建立了具有6个节点的链表，然后删除第3个节点〔该节点中的数据是字符D〕。删除节点后，程序输出了链表节点中的数据。2010-1015.7综合举例假设链表head有N个节点。

◆向左旋转的操作是：如果1<m≤N，将第m个节点设置成链表的第m-1个节点，如果m=1，将第m个节点，即头节点，设置成链表的尾节点，即设置成第N个节点。◆向右旋转的操作是：如果1≤m<N，将第m个节点设置成链表的第m+1个节点，如果m=N，将第m个节点，即尾节点，设置成链表的头节点，即设置成第1个节点。例子6(example15_6.c,rotate.c,create.c,getNode.c,input.c)旋转有5个节点的链表，将链表向左旋转了5次。15.7.1旋转链表2010-1015.7.2围圈留一围圈留一”问题：“假设干个人围成一圈，从某个人开始顺时针数到第3个人，该人从圈中退出，然后继续顺时针数到第3个人，该人从圈中退出，依此类推，程序输出圈中最后剩下的人”。“围圈留一”问题可以简化为旋转链表，例如用链表的节点的数据存储区依次存放m个代表圈中人的号码的正整数1，2，…m。那么链表向左旋转2次后，此时链表的头节点应该是要退出圈中的人，这时只要删除链表的头节点即可。例子7(example15_7.c,rotate.c,create.c,getNo