《C语言程序设计(第二版) 教学课件 ppt 作者 刘加海 朱云其第十二章 第十二章》由会员分享，可在线阅读，更多相关《C语言程序设计(第二版) 教学课件 ppt 作者 刘加海 朱云其第十二章 第十二章（35页珍藏版）》请在金锄头文库上搜索。
1、第12章,链表及其应用,Company Logo,本章重点 链表的定义 栈的基本操作的实现 队列的基本操作的实现,Company Logo,本章难点 链表中栈的应用。 链表中队列的应用。 链表的插入、删除、查找和排序,Company Logo,12.1 链表的定义,链表中的每个结点，除了要有存放数据本身的数据域外，至少还需要有一个指针域，用它来存放下一个结点元素的地址，以便通过这些指针把各结点连接起来，从而形成如图12.1所示的链表。,图12.1 链表,每个链表都用一个“头指针”来指向链表的开始结点，链表最后一个结点的指针域不再指向其他结点，就置成0( NULL)值，标志着链表的结束。,Com
2、pany Logo,单向链表的结构体结点的类型定义如下： struct node int i; struct node *next; ; 单向链表的建立，需要用到下面两个内存管理函数。 1）void *malloc(unsigned size ) 在具体应用中为 p=(struct node *)malloc(sizeof(struct node) 2）void free(void *ptr),Company Logo,12.2 堆 栈,堆栈是一端固定，只允许在另一端进行插入和删除的特殊的线性表，如图12.2所示。允许插入和删除的一端称为栈顶，固定的一端称为栈底。当堆栈中没有任何元素时称为空栈
3、。向堆栈中插入元素称为入栈，删除元素称为出栈。,图12.2 堆栈,Company Logo,【例12.1】 从键盘输入一串字符，以堆栈的形式存放，当输入*时结束，然后逆序输出。,分析：堆栈是先进后出的存储结构，在堆栈建立过程中，头指针是不断在移动的。 堆栈的建立过程如下（见表12.3）。 1）链表未建立时，结点数为0，头指针为空，即n=0, head=NULL;如图12.3所示。 2）用p指针申请空间，产生第一个存储单元，读入数据，如图12.4所示。,图12.3 当头指针为空时 图12.4 动态分配一个结点,Company Logo,3）读入第一个数据，存入第一个存储单元，即p-i=x1;将第
4、一个存储单元链接在头指针后面，即p-next=head;head=p;如图12.5所示。,图12.5 头指针指向P所指的存储单元,Company Logo,4）申请第二个存储单元，读入数据，p-i=x2;将第二个结点链接到x1的前面，头指针head的后面，完成语句p-next=head;head=p;如图12.6所示。接下去重复步骤2）4）。,图12.6 第二个结点链入堆栈,Company Logo,编辑源程序代码12-1.c：,点击查看代码,堆栈一般具有如下基本操作： 1）置空栈。 清空栈的内容，准备存放数据。 2）入栈。 在栈顶插入一个元素，栈顶位置加1。 3）出栈。 删除原栈顶元素，栈顶
5、位置减1。 4）取栈顶元素。 返回栈顶元素，栈顶位置不变。 5）栈空判断。 判断栈是否为空，一般用于出栈或取栈顶元素。,Company Logo,12.3 队 列,队列是一种先进先出的存储结构，它是允许在队列的一端插入、在另一端删除的特殊线性表。允许插入的一端称为队尾，允许删除的一端称为队首，如图12.7所示。a1，a2，an-1，an依次插入队尾，先插入的元素先退出队列，因此又称为先进先出线性表。,图12.7 队列,Company Logo,【例12.2】 建立一个队例，用来存储输入的字符，当输入#符号时结束，然后输出队列中的数据。,分析：队列是先进先出的存储结构，在队列的建立过程中，头指针
6、不动，而尾指针不断指向新产生的结点。 队列的建立过程：在队列的建立过程中，所用到的有头指针head、尾指针rear和当前指针p，尾指针rear始终指向队列中最后的结点。 1）链表未建立时，结点数为0，头指针为空，即n=0, head=NULL; 如图12.8所示。 2）p指针申请第一个存储单元，读入数据，如图12.9所示。,图12.8 当头指针为空时 图12.9 动态分配一个结点,Company Logo,3）将第一个数据读入，并将数据存入第一个存储单元，即p-i=x1;将第一个存储单元链接到头指针的后面，即p-next=head;head=p;rear=p;如图12.10所示。,图12.10
7、 头指针指向p所指的存储单元,Company Logo,4）申请第二个存储单元，读入数据并赋值，p-i=x2;将第二个数据链接到结点x1后面，所用到语句为rear-next=p;把尾指针后移到当前指针rear=p;如图12.11所示。,图12.11 第二个结点链入队列,5）申请第三个存储单元的空间，读入第三个数据，然后给结点赋值，重复步骤2）4）。,Company Logo,注意：在队列的建立过程中有以下特征： 1）队列的尾结点的指针指向空NULL。 2）在队列建立过程中，除建立第1个结点外，头指针位 置始终不变。 3）在建立队列的过程中，队列的尾指针指向当前指针 所指的结点，把当前指针所指的
8、结点链入队列。,Company Logo,编辑源程序代码12-2.c：,点击查看代码,队列一般具有如下基本操作： 1）置空队列。建立一个空队列，准备存放数据。 2）入队。在队尾插入一个新元素。 3）出队。从队首删除一个元素。 4）取队首元素。取队首元素使用，不删除该元素。 5）队空判断。判断队列是否为空。,Company Logo,12.4链表的插入,结点插入链表中可能会有以下几种情况： 1）插入在链表的中间。 2）插入在链表的最后。 3）插入在一个空链表中。 4）插入在链表的最前面。 下面分析结点插入链表的各种情况。 1. 结点插入在链表的中间 把p0所指结点插在p1、p2之间，如图12.1
9、2所示。首先要把p0-next指向p1所指的结点，然后p2-next指向p0所指的结点，语句如下：,Company Logo,p0-next=p1; p2-next=p0;,图12.12 结点插入在链表的中间,Company Logo,2. 结点插入在链表的最后 结点插入在链表的最后，让p1指向尾结点，然后p1-next指向要插入的结点，插入结点的尾指针不再指向其他结点。语句如下： p1-next=p0; p0-next=NULL; 3. 结点插入在空链表中 结点插入在空链表中，表示此链表原先为空，如图12.13所示，此时可以把head（因head为NULL）赋给p0-next，然后再把头指针
10、指向要插入的结点。语句如下：,图12.13 结点插入在空链表中,Company Logo,p0-next=head; head=p0; 4. 结点插入在链表的最前面 结点插入在链表的最前面的情况如图12.14所示。首先p0-next指向头指针所指的链表，然后再把头指针指向p0。语句如下： p0-next=head; head=p0;,图12.14 结点插入在链表头,Company Logo,【例12.3】 结点插入链表的例子。把某结点插入一从小到大排列的链表中，要求插入后链表中数据仍然有序。其中head为指向链表的头指针，stud为指向插入结点的指针。,点击查看,Company Logo,12
11、.5 链表的删除,链表的删除也可以分为以下多种情况： 1）欲在空链表中删除结点。 2）删除链表头结点。 3）删除链表中间结点。 4）删除链表最后一个结点。 在链表中删除结点的具体过程为：首先定义两个结构体指针p1和p2，把p1、p2指向第一个结点，即头结点，接着查看是否满足删除条件（删除条件指num=p1-num）： 满足，删除头结点，语句如下： head=p1-next; free(p1);,Company Logo,2）如不满足，p1指针后移，如满足nump1-num，则： 先使p2后移，然后p2=p1； p1再后移，p1=p1-next； 判定是否是删除的结点，重复第2）步。 3）如果n
12、ump1-num不满足，即为删除的结点，那么删除结点p1，只需执行语句： p2-next=p1-next; free(p1); 从链表中删除某一结点，此时需三个指针p2、p1和head，头指针head是固定的，p2随p1在后依次后移，p1指在所删除的结点上。,Company Logo,【例12.4】 编写一函数，删除链表中的某一结点ch，链表的结构体如下：,struct node char ch; struct node next; ;,根据以上的分析，函数代码如下：,点击查看,Company Logo,12.6 链表的应用,【例12.5】 一个综合的链表程序，在此程序中首先定义一个结构体，它
13、有两个成员，一是描述一个人的姓名，二是指向结构体本身的指针，要求能实现以下功能：,1）创建新链表。 2）在链表中插入元素。 3）在链表中删除元素。 4）在链表中查找元素。 5）倒置链表。,分析：程序设计中首先显示有这些功能的菜单选择，根据选择调用函数，实现以上功能，具体步骤如下：,1）定义结构体结点。 struct elem/*定义结点*/ char name10; struct elem *next; create;,Company Logo,2）创建一个菜单。 void menu()/*创建菜单*/ printf(“ttt1.创建新链表-1n“); printf(“ttt2.插入新元素-2
14、n“); printf(“ttt3.删除旧元素-3n“); printf(“ttt4.查找旧元素-4n“); printf(“ttt5.倒置原链表-5n“); printf(“ttt6.显示所有元素-6n“); printf(“ttt7.退出-7nn“); printf(“请选择(17): “); ,Company Logo,3）创建新链表，如图12.15所示。语句如下：,图12.15 创建新链表,cur-next=NULL; van-next=cur;,Company Logo,具体模块如下： void news(int n)/*创建新链表,参数n为链表长度*/ int i; printf(
15、“n“); if(head=(create *)malloc(sizeof(create)=NULL)/*定义头结点*/ printf(“n不能创建链表“); exit(1); van=head;/*将前驱结点指针指向头结点*/ for(i=1;i=n;i+) if(cur=(create *)malloc(sizeof(create)=NULL)/*定义新结点*/ printf(“n不能创建链表“); exit(1); ,Company Logo,cur-next=NULL;/*将当前结点的后继指针置空*/ van-next=cur;/*连接结点*/ printf(“输入第%d个人的名字: “,i); scanf(“%s“, ,Company Logo,else van=temp; temp=temp-next; return(temp); 5）显示链表。关键语句如下： while(temp!=NULL) printf(“%s “,temp-name); temp=temp-next; 具体模块如下： void print()/*显示链表函数*/ temp=head-next; printf(“n“);,Company Logo,while(temp!=NULL) printf(“%s “,temp-name); temp=temp-next; 6）插入结点
