《[计算机软件及应用]链表 c++。ppt》由会员分享，可在线阅读，更多相关《[计算机软件及应用]链表 c++。ppt（88页珍藏版）》请在金锄头文库上搜索。
1、程序设计基础第11章 链表程序设计基础第11章 链表教学目标链表的概念建立链表中指针的运用插入删除结点的思路与双指针作用建立循环链表的思路程序设计基础第11章 链表链表属于动态数据结构，可以类比成一“环”接一“环”的链条，这里每一“环”视作一个结点，结点串在起形成链表。程序设计基础第11章 链表11.1 举例说明链表的概念程序设计基础第11章 链表【任务11.1】某电视台希望王小二同学为他们编一个程序。该程序可以将节目串在一起，形成一份有序的节目预告 。节目列表有如下三项1、节目名称 包括新闻联播（CCTV News） 祖国各地（Motherland） 体育之窗（Sports） 学校见闻（Co
2、llege） 电影展播（Movie） 2、节目主持人（Director） 3、播放时间长度（Time）程序设计基础第11章 链表我们可以将每一个节目单独放在一个结构里，用一个指针把两个结构连在一起，一天的节目形成一 条链表。用一个所谓的头指针 head 指向链表的第一个结点。如下图所示节目2节目nNULLhead头指针节目1下面的程序是建立链表的过程。程序设计基础第11章 链表11.2 建立链表的过程程序设计基础第11章 链表/* /* 程 序 名：11_1.cpp * /* 作 者：wuwh * /* 编制时间：2002年11月26日 * /* 主要功能：链表 * /* #include u
3、sing namespace std;struct ActList/ 定义一个名为 ActList 结构 char ActName20;/ 节目名为字符数组 char director20; / 主持人为字符数组 int Mtime;/ 节目长度为分钟 ActList *next;/ 指向 ActList 结构的指针 ;程序设计基础第11章 链表ActList *head; / 链头指针ActList *Create() / 定义一个指向 AcitList 结构 /的指针函数，名为 CreateActList *p=NULL; / 指针，指向个待插入的结点ActList *q=NULL; /
4、指针，用于在其后插入结点head = NULL; / 一开始链表为空int Time; / 节目时长，如为0则退出程序设计基础第11章 链表/ 以下是给新结点输入节目信息 cout Time; while(Time != 0) / 当该节目的时长不为0时，将其 / 纳入链表中p = new ActList;/ 分配内存空间给p结点p-Mtime = Time;/ 让Time赋给p结点的结 构成员Mtimecout p-ActName; / 输入节目名称cout p-director; / 输入主持人程序设计基础第11章 链表if (head = NULL) / head为空，要插入第一个hea
5、d = p; / 结点，让头指针指向结点pelse / 否则不是头结点，应将p结点q-next = p; / 插入到q结点的后面q = p; / q指向当前最后一个结点cout Time;/ 输入下一个节目时长/ 一旦跳出while循环，说明有一个节目时长为0if (head != NULL) q-next = NULL;/ 让q所指的最后一个结点的指针域为空说明这已是链尾了return(head);/ 返回头指针 程序设计基础第11章 链表void displayList(ActList *head) cout Mtime ActName director next; 程序设计基础第11章
6、链表int main( )/ 主函数开始 / 调用子函数displaList()/ 调用时的实参为Create()函数的返回值displayList( Create() );return 0; / 主函数结束程序设计基础第11章 链表说明 1、先从主函数说起主函数只有一条语句 displayList(Create( );这是调用子函数 displayList，该子函数的形参为 ActList *head 是一个指向 ActList 结构的名为 head 的指针变量。在主 函数调用 displayList 时所用的实际参数来自运行 Create( ) 函 数的返回值。从 Create( ) 的定
7、义 ActList *Create( ) 看出 Create( ) 函数的返回值应该是一个指向 ActList 的指针。主函数在调用子函数时，又遇到该函数的实参又是调用另一个函数之后的返回值。看起来的确显得复杂，但是我们耐心 分析之后，感到并不难。程序设计基础第11章 链表2、程序开头为结构定义。在这里我们称这样的一个结构为一个结点。这个结点包含两个域：数据域和指针域int MTime; char ActName20; 数据域 char director20 ActList *next; 指针域结 点数据域中装有节目的信息，而指针域装的是指向另一个结点的地址。显然这是为形成链表而专门设 置的。
8、程序设计基础第11章 链表3、在定义 Create 函数之前，先定义了一个指向结构的头指针 head，即ActList *head;4、定义 Create函数，该函数可返回指向 ActList 结构的指针，即ActList *Create( )分析这个函数的功能可分如下4块程序设计基础第11章 链表 定义 ActList *p = NULL; ActList *q = NULL; head = NULL; int Time;定义了两个指向结构 ActList 的指针 p 和 q，并初始化为空，即未指向任何地址。同时让头指针 head 也为空。再定义一个临时变量 Time，是一个整型数。程序设计
9、基础第11章 链表 提示“输入节目时长”，之后用键盘输入，用了下面两句：cout Time;这部分程序语句是为下面的 while 循环做准备的。如果 Time 不为 0，才做下面的内容。程序设计基础第11章 链表 while( Time != 0 ) 循环 在当循环的循环体内完成建立链表的过程。首先 给 p 结点分配内存空间。这个内存空间的大小要根 据 p 结点的定义（p 结点是 ActList 结构）来确定。接着下面就是几个赋值语句 p-MTime = Time;cout p-ActName;/ 用键盘输入节目名称cout p-director;/ 用键盘输入主持人程序设计基础第11章 链表
10、接着是一个分支语句 if (head=NULL)head=p; 这是说如果头指针为空，表示链表还是空的，这时 p 结点就是第一个结点。让 head 指向 p 结点。之 后让 q=p; 这是让 q 指向刚进入链表的结点，让 p 再去指向待加入的结点。如果 p 结点已不是第一个 结点了，head 必不为 NULL，因此要走 else 分支，即 elseq-next = p;程序设计基础第11章 链表将此时的 p 结点放到 q 所指向的结点后面。之后让 q=p; 即让 q 指向刚进入链表的结点，腾出 p 去指向下一个待加入的结点。接下来输入下一个节目时长，cout Time;至此，while 语句的
11、循环体结束。当 Time 值不为0，就会有结点加入链表，继续执行循环体。一旦 Time 为 0，则会跳出 while 循环。程序设计基础第11章 链表 执行两条语句 if (head != NULL)q-next = NULL; return (head); 第一条是说，如果 head 不空说明链表已 建成，这时 q 一定是最后一个结点，将该结 点的指针域置成空，以表明它是链尾。程序设计基础第11章 链表第二条 return (head); 将这条链表的头指针 head 返回。这件事意味着执行完 Create 函数后得到 head 指针所指向的地址，这 个地址就是链表中的第一个结点的地址 。这
12、时对主函数而言 displayList( Create( ) ) 就是 dispalyList( head ) 调用 dsplayList(head) 就会将整个链 表从头至尾输出。程序设计基础第11章 链表1、定义 ActList 结构，结构中包含数据域和指针域。将一个结构看作一个结点。 2、定义一个指向结构的指针 head，准备用来指向链表的第一个结点。 3、定义一个指向ActList 结构的指针函数，起名为 Create 函数 ，该函数返回的是创建好的链的头指针 head。下面是 Create 函数所要做的事情： 定义指向 ActList 结构的两个指针 p 和 q，定义后立即初 始化为
13、 NULL，即不指向任何地址。再让头指针 head 为 NULL，也是不指向任何地址，表示该链表尚未建立，一个 结点也没有。然后定义一个中间变量“节目时长 Time”，当 Time 为 0 时，建立链表的过程应该结束。建立链表的过程可归纳为如下三个步骤程序设计基础第11章 链表 下面程序的构思是，只要 Time 不为 0，就要构建链表。构建的思路是将一个一个的结点加至链表里来。 首先给 p 找一个能够指向的内存空间，我们说这是给 p 结点分配一片内存空间。如下图建立链表的过程可归纳为如下三个步骤p程序设计基础第11章 链表 然后，通过键盘往这个空间中装入与节目有关的信息。 装完之后判断一下 h
14、ead 为空否，如为空则 p 结点为第一个 结点，让 head 指向 p 结点就完成了有一个结点的链表。之 后让 q 赋值为 p，即使让 q 指针去指向刚加入链表的结点， 将 p 指针腾出来去做下一个结点的工作。head p q图 链表的第一个 结点建成程序设计基础第11章 链表当 Time 不为 0，p 又被分配了内存空间，形成了第二个 结点，装入节目信息后，判断 head 不再为空，说明前面已 有结点在链表中，这时要将第二个结点放到 q 所指向的结 点的后面。执行 q-next = p 之后就完成了。之后再将 q 指 针移到第二个结点上，将 p 指针腾出来去做下一个结点的工作。headpq
15、程序设计基础第11章 链表指针移到第二个结点上，将 p 指针腾出来去做下一个结点的工作。headq第三个结点加入链表的过程为headqp程序设计基础第11章 链表最末一个结点连至链表的尾部之后，要在 q 指针所指向 的最后一个机诶但的指针域加上一个 NULL，表示这里是链尾了，后面再也不连结点了。headqNULL程序设计基础第11章 链表练 习1、按下表顺序输入某班的一个学习小组的成员表：姓名赵达钱亮孙参李思周芜武陆郑琪出生年月 19831983198319821983198319821329546将学习小组形成一个链表，每人一个结点。结点中有将学习小组形成一个链表，每人一个结点。结点中有4 4个成员：姓名、出生年、出生月、指针。个成员：姓名、出生年、出生月、指针。建成链表后输出该链表。建成链表后输出该链表。程序设计基础第11章 链表链表结点的插入程序设计基础第11章 链表链表结点的插入原则： 插入操作不应破坏原链接关系 插入的结点应该在它该在的位置。应该 有一个插入位置的查找子过程程序设计基础第11章 链表5head61015null128先看下面一个简单的例子： 已有一个如图所示的链表。它是按结点中的整数 域从小到大排序的。现在要插入一个结点，
