C程序设计第12章.pptx

n考虑上一章的职工卡片问题，用计算机管理考虑上一章的职工卡片问题，用计算机管理这些卡片这些卡片,要把卡片保存在计算机内。要把卡片保存在计算机内。n首先，用什么数据结构存储：一张卡片是一首先，用什么数据结构存储：一张卡片是一个结构体，所有卡片自然用结构体数组。个结构体，所有卡片自然用结构体数组。n第三，操作问题：第三，操作问题：若增加一个人，应该在数组中加一个元素，会若增加一个人，应该在数组中加一个元素，会产生数组不够大的可能。产生数组不够大的可能。若增加一张卡片在数组中间，应该把加入位置若增加一张卡片在数组中间，应该把加入位置以后的其它元素依次向后移动。以后的其它元素依次向后移动。若在中间删除一张卡片，会在数组中间留下一若在中间删除一张卡片，会在数组中间留下一个个“洞洞”，应该把，应该把“洞洞”以后的元素依次向前以后的元素依次向前移动移动n使用数组带来的问题是：使用数组带来的问题是：操作不方便；操作不方便；数组尺寸不好确定。数组尺寸不好确定。第二，数组多大：为保第二，数组多大：为保存全部卡片，并且人数不固定，就应该给一个存全部卡片，并且人数不固定，就应该给一个足够大的数组。足够大的数组。n最好把这些卡片存储成动态的，最好把这些卡片存储成动态的，需要多大存储量（有多少张卡片）就用多大。需要多大存储量（有多少张卡片）就用多大。中间加一张卡片时不要向后串别的卡片，中间加一张卡片时不要向后串别的卡片，删除一张卡片时不要留下删除一张卡片时不要留下“洞洞”。如图的链式结构可以满足要求如图的链式结构可以满足要求:n当增加一张卡片时，只需要向计算机系统申请一块空间，联当增加一张卡片时，只需要向计算机系统申请一块空间，联到链的适当位置上。例如，要增加一张卡片到链的适当位置上。例如，要增加一张卡片 50 插入到插入到 2、3 之间，则只需要如下修改指针：之间，则只需要如下修改指针：n若删除一节，只需要将其从链上摘下来即可。例删除若删除一节，只需要将其从链上摘下来即可。例删除2节得节得链上已经没有链上已经没有2节了，删掉的节所占的存储空间还可以还回节了，删掉的节所占的存储空间还可以还回计算机系统，以便作其它用途。计算机系统，以便作其它用途。123 n.50 n这就是一种动态数据结构中的这就是一种动态数据结构中的链表。动链表。动态数据结构上的一项是一个动态变量，指针态数据结构上的一项是一个动态变量，指针是标识动态变量的有力手段。动态变量与静是标识动态变量的有力手段。动态变量与静态变量的区别在于态变量的区别在于:n静态变量是程序中由程序员静态变量是程序中由程序员“显式显式”说明的说明的变量。它有一个名字，在编译时，编译程序变量。它有一个名字，在编译时，编译程序已经给它分配存储空间。这块存储空间用变已经给它分配存储空间。这块存储空间用变量的名字来标识。量的名字来标识。n动态变量在程序中没有动态变量在程序中没有“显式显式”说明，它没有名字说明，它没有名字n在编译时编译程序不知道有该变量，不给（也不可在编译时编译程序不知道有该变量，不给（也不可能给）它分配空间。能给）它分配空间。n动态变量是在程序运行时动态变量是在程序运行时随程序存储数据的需要，申请空间函数（例如随程序存储数据的需要，申请空间函数（例如malloc，当然也是由程序员安排的）随机的动态，当然也是由程序员安排的）随机的动态的申请来的空间。它没有名字，一般动态变量都的申请来的空间。它没有名字，一般动态变量都由指针标识。由指针标识。当使用完毕后，由释放空间函数（例如当使用完毕后，由释放空间函数（例如free）释）释放，还回计算机存储管理系统，以备它用。放，还回计算机存储管理系统，以备它用。n注意：这里所说的静态变量不是注意：这里所说的静态变量不是C语言中由语言中由静态存储类别静态存储类别static声明的变量；动态变量声明的变量；动态变量也不是也不是C语言中由自动存储类别语言中由自动存储类别auto声明的声明的变量。而是一般程序设计概念中的静态变量、变量。而是一般程序设计概念中的静态变量、动态变量动态变量管理动态变量管理动态变量n n动态变量在程序运行时，随程序存储数据动态变量在程序运行时，随程序存储数据的需要，向计算机系统申请；使用完后还的需要，向计算机系统申请；使用完后还回计算机系统。回计算机系统。n n本节介绍本节介绍申请计算机存储空间函数申请计算机存储空间函数申请计算机存储空间函数申请计算机存储空间函数mallocmalloc释放存储空间函数释放存储空间函数释放存储空间函数释放存储空间函数free free 目标代码空间目标代码空间静态区空间静态区空间库代码空间库代码空间堆区空间堆区空间栈区空间栈区空间 内存内存 程序运行时，涉及用户程序的内存存储程序运行时，涉及用户程序的内存存储结构如右图所示，首先是目标代码区；然后是结构如右图所示，首先是目标代码区；然后是静态存储区，用于存放那些可用绝对地址标识静态存储区，用于存放那些可用绝对地址标识的，主要是具有静态存储类别的数据和变量；的，主要是具有静态存储类别的数据和变量；接着是目标代码运行时用到的库程序代码区；接着是目标代码运行时用到的库程序代码区；最后剩余空间是栈区和堆区，栈区和堆区从剩最后剩余空间是栈区和堆区，栈区和堆区从剩余空间的两端，动态的向中间增长。栈区用来余空间的两端，动态的向中间增长。栈区用来存储程序中声明的函数的局部变量等具有自动存储程序中声明的函数的局部变量等具有自动存储类别的数据和变量；堆区用来存储经过动存储类别的数据和变量；堆区用来存储经过动态申请空间函数申请的变量。态申请空间函数申请的变量。nsizeof 运算符运算符单目运算符单目运算符 sizeof 的的操作数操作数是类型。是类型。运算结果运算结果是求得相应类型的尺寸，即存储相是求得相应类型的尺寸，即存储相应类型数据所需要的字节数。应类型数据所需要的字节数。sizeof(int)/*结果是结果是2*/sizeof(char)/*结果是结果是1*/sizeof(struct date)/*若若 struct date 是第十是第十一章定义的日期类型，结果是一章定义的日期类型，结果是6*/nmalloc 函数函数:原型原型 void*malloc(unsigned long size);功能功能 申请足够大内存区域用来存储长度为申请足够大内存区域用来存储长度为size的数据对象，返回该区域的首指针，并保证该的数据对象，返回该区域的首指针，并保证该区域符合任何数据类型对存储区域开始地址和区域符合任何数据类型对存储区域开始地址和对齐的要求。对齐的要求。返回指针是返回指针是void类型的，调用者必须使用类型的，调用者必须使用显示强制类型转换，把该指针转换成所需要类显示强制类型转换，把该指针转换成所需要类型的指针。型的指针。n例例:float*p;p=(float*)malloc(sizeof(float);struct date*pdate;pdate=(struct date*)malloc(sizeof(struct date);nfree函数函数动态申请的内存如果不再使用，应当适时释放动态申请的内存如果不再使用，应当适时释放这样可以提高程序运行效率。这样可以提高程序运行效率。free函数用来释函数用来释放经过放经过malloc申请的动态空间。申请的动态空间。free的函数的函数原型原型 void free(void*ptr);功能功能释放由释放由malloc申请的内存区域。申请的内存区域。free的参数的参数ptr是一个指针，指向以前由是一个指针，指向以前由malloc申请的一申请的一个内存区域。个内存区域。n例例申请申请float*p;p=(float*)malloc(sizeof(float);struct date*pdate;pdate=(struct date*)malloc(sizeof(struct date);释放释放free(p);free(pdate);free(ptr)/*释放释放ptr所指向由所指向由malloc申请的内存空间申请的内存空间*/一块存储区域一经释放，便不能再使用。使用一块存储区域一经释放，便不能再使用。使用free特特别注意，操作不当会产生不可预料的结果。如下情况别注意，操作不当会产生不可预料的结果。如下情况下使用下使用free都会造成灾难性后果。都会造成灾难性后果。ptr无值；无值；ptr的值为的值为NULL；ptr所指向的空间不是经过所指向的空间不是经过malloc申请来的；申请来的；对一次申请的存储区进行多次释放（实际可能是对一次申请的存储区进行多次释放（实际可能是ptr无值或值为无值或值为NULL）。）。n实用问题实用问题:若指针变量指向的用若指针变量指向的用malloc申请来的动态变量，是孤申请来的动态变量，是孤立的不能与其它变量相联系，显然作用不大。立的不能与其它变量相联系，显然作用不大。引进动态变量的目的是构造动态数据结构。引进动态变量的目的是构造动态数据结构。例如象本章开始介绍的那样，构造一个链表等。例如象本章开始介绍的那样，构造一个链表等。这就要求一个数据项上除基本的数据信息外，还应包这就要求一个数据项上除基本的数据信息外，还应包含与其它数据项相联系的信息，也就是包含指针。含与其它数据项相联系的信息，也就是包含指针。该结构必须用结构体类型描述，链表上一节的类型定该结构必须用结构体类型描述，链表上一节的类型定义形式。义形式。类型定义形式类型定义形式 struct t 基本数据部分；基本数据部分；struct t *next;基本数基本数据部分据部分指针部分指针部分一个数据项一个数据项 123 n.栈栈 stackn在第六章已经用数组实现过栈和队列，但是，数在第六章已经用数组实现过栈和队列，但是，数组有一定的局限性。如图可以用单向链表实现栈，组有一定的局限性。如图可以用单向链表实现栈，指针变量指针变量top指向栈顶。栈的操作有指向栈顶。栈的操作有:初始化：初始化：stackintial 压栈：压栈：stackpush 弹栈：弹栈：stackpop设有声明设有声明:typedef .items;typedef struct stackcell items data ;struct stackcell *predocessor;stackcelltype;typedef stackcelltype *pstacktype;pstacktype top;top:.栈栈如下实现栈的操作：如下实现栈的操作：void stackinitial(void)top=NULL;void stackpush(items x)pstacktype p;p=(pstacktype)malloc(sizeof(stackcelltype);p-data =x;p-prodocessor =top;top =p;void stackpop(items*x)pstacktype p;if(top!=NULL)*x =top-data;p =top;top =top-predecessor;free(p);else printf(“栈下溢栈下溢n”);看一下这三个操作看一下这三个操作:1.初始化后初始化后(调用调用stackinitail)得。得。2.调用一次调用一次 stackpush(1)得。得。3.再调用一次再调用一次stackpush(2)得得。4.调用一次调用一次stackpop(&b)得得。top:1.2b:2队列队列n如图可用单向链表实现队列，现在要用两个指针变量，一如图可用单向链表实现队列，现在要用两个指针变量，一个指向队头（个指向队头（front），一个指向队尾（），一个指向队尾（rear）。队列的操）。队列的操作有作有 初始化（初始化（queueinitial）进队进队排在队尾（排在队尾（inqueue）出队出队从队头删一项（从队头删一项（outqueue）rear:front:.设有如下说明设有如下说明:typedef .items;typedef struct queue items data struct queue *next;queuetype;typedef queuetype *pqueuetype;pqueuetype front,rear;操作：操作：void queueinital(void)front =NULL;rear =NULL;void inqueue(item x)pqueuetype p;p=(pqueuetype)malloc(sizeof(queuetype);p-data =x;p-next =NULL;if(rear=NULL)rear =p;front =p;else rear-next =p;rear =p;void outgueue(item*x)pqueuetype p;if(front=NULL)printf(“队空队空n”);else *x =front-data;p =front;front =front-next;if(front=NULL)rear =NULL;free(p);看一下这三个操作看一下这三个操作:1.调用初始化后（调用一次调用初始化后（调用一次 queueinitail）得；得；2.调用一次调用一次ingueue(1)得；得；再调用一次再调用一次ingueue(2)得；得；再调用一次再调用一次 ingueue(3)得得;3.调用一次调用一次 outgueue(&a)得；得；再调用一次再调用一次 outgueue(&b)得得;再调用一次再调用一次 outgueue(&a)得得。1a:rear:front:231 p:b:23NULLNULL链表链表linkage tablebase:1.2N-1N.双向链双向链base:12N-1N.单向链单向链base:12N-1N.环形链环形链base:12N-1N.双向双向环形链环形链 实际上前边讲的栈，队列都是单向链表，但是栈和实际上前边讲的栈，队列都是单向链表，但是栈和实际上前边讲的栈，队列都是单向链表，但是栈和实际上前边讲的栈，队列都是单向链表，但是栈和队列只是单向链表的两种特殊应用队列只是单向链表的两种特殊应用队列只是单向链表的两种特殊应用队列只是单向链表的两种特殊应用操作只在头操作只在头操作只在头操作只在头尾进行。下边介绍单向链表的一般操作尾进行。下边介绍单向链表的一般操作尾进行。下边介绍单向链表的一般操作尾进行。下边介绍单向链表的一般操作:n创建单向链表创建单向链表:创建单向链表，是指用一项一项的数据逐步建创建单向链表，是指用一项一项的数据逐步建创建单向链表，是指用一项一项的数据逐步建创建单向链表，是指用一项一项的数据逐步建立、形成一个链表。可以分成向链头加入数据和向立、形成一个链表。可以分成向链头加入数据和向立、形成一个链表。可以分成向链头加入数据和向立、形成一个链表。可以分成向链头加入数据和向链尾加入数据两种方式。链尾加入数据两种方式。链尾加入数据两种方式。链尾加入数据两种方式。创建单向链表可以分成向链头加入数据和向链创建单向链表可以分成向链头加入数据和向链创建单向链表可以分成向链头加入数据和向链创建单向链表可以分成向链头加入数据和向链尾加入数据两种方式。新项加入链头就是压栈的算尾加入数据两种方式。新项加入链头就是压栈的算尾加入数据两种方式。新项加入链头就是压栈的算尾加入数据两种方式。新项加入链头就是压栈的算法；新项加入链尾就是队列中入队的算法。只要反法；新项加入链尾就是队列中入队的算法。只要反法；新项加入链尾就是队列中入队的算法。只要反法；新项加入链尾就是队列中入队的算法。只要反复调用那里的函数或将函数体放在循环语句中即可，复调用那里的函数或将函数体放在循环语句中即可，复调用那里的函数或将函数体放在循环语句中即可，复调用那里的函数或将函数体放在循环语句中即可，这里不赘述。这里不赘述。这里不赘述。这里不赘述。n遍历单向链表遍历单向链表:遍历是指从头到尾将链表上数据全部加工一遍历是指从头到尾将链表上数据全部加工一遍历是指从头到尾将链表上数据全部加工一遍历是指从头到尾将链表上数据全部加工一遍。可用如下左端的算法。但实用中，经常用如遍。可用如下左端的算法。但实用中，经常用如遍。可用如下左端的算法。但实用中，经常用如遍。可用如下左端的算法。但实用中，经常用如下右端下右端下右端下右端 的算法来遍历单向链表。的算法来遍历单向链表。的算法来遍历单向链表。的算法来遍历单向链表。p =base;p0=NULL;while(p!=NULL)p =base;加工加工 p-while(p!=NULL)p =p-next;加工加工 p-p0 =p;p =p-next;n在单向链表上检索在单向链表上检索:检索是指在单向链表上查找关键字等于某给定检索是指在单向链表上查找关键字等于某给定值的节点值的节点,若找到则带回相应节点的指针；否则带若找到则带回相应节点的指针；否则带回回NULL。设关键字域域名为。设关键字域域名为key；欲检索的关键；欲检索的关键字值为字值为key0.如下算法实现检索：如下算法实现检索：p0=NULL;p =base;while(p!=NULL&p-key!=key0)p0=p;p =p-next;n向单向链表插入一项向单向链表插入一项:设有下图的链表，现在要把设有下图的链表，现在要把r所指示的数据项插所指示的数据项插入到入到 p0、p 所指两项之间。操作是所指两项之间。操作是:r-next =p;p0-next =r;p0 =r /*使使 p0 仍为仍为 p 的前一项的前一项*/r:5p0:p:1 2 3 4.n从单向链表上删除一项从单向链表上删除一项:设有下图的链表，现在要删除设有下图的链表，现在要删除p所指项。删除所指项。删除算法是：算法是：q=p;p =p-next;p0-next =p;free(q)p0:1234.p:q:n交换单向链表上两项交换单向链表上两项:设有如图所示链表。现在要把设有如图所示链表。现在要把 p 所指的项与所指的项与 q 所指所指的项交换的项交换 为了表示操作方便，我们把该链表分两段画出。为了表示操作方便，我们把该链表分两段画出。p0p123.q0 q456.p0:p:123.q0q:456.g:/*交换交换 p-next、q-next*/g =p-next;/*1*/p-next =q-next;/*2*/q-next =g;/*3*/*交换交换 p0-next、q0-next*/p0-next =q;/*4*/q0-next =p;/*5*/*交换交换 p、q*/p =p0-next;/*6*/q =q0-next;/*7*/树树treen两叉树，两叉树的每个数据项附带两个指针，分两叉树，两叉树的每个数据项附带两个指针，分别指向它的两个分支。两叉树的定义别指向它的两个分支。两叉树的定义:空是树；空是树；一个结点连接两个不相交的树一个结点连接两个不相交的树,仍为树；仍为树；所有结点具有相同的数据类型。所有结点具有相同的数据类型。*+-a/d*bcef(a+b/c)*(d e*f)root:设设 ti 为二叉树的一个结点，一般为二叉树的一个结点，一般 ti 由两部分组成：由两部分组成：l基本数据部分基本数据部分-保存本结点上的基本数据；保存本结点上的基本数据；l指针部分连指针部分连-接本结点以下的其它结点。接本结点以下的其它结点。结点结点 ti 的指针连接的结点称为的指针连接的结点称为 ti 的的子结点子结点，相应相应 ti 称为其子结点的称为其子结点的父结点父结点。ti的指针部分有两个指针：左指针、右指针。的指针部分有两个指针：左指针、右指针。称称 ti 的左指针连接的部分为的左指针连接的部分为 ti 的的左子树左子树，ti 的右指针连接的部分为的右指针连接的部分为 ti 的的右子树右子树。若左、右子树均空，则称若左、右子树均空，则称 ti 为为叶结点叶结点。ti78563124ti:n为了检索操作方便，一般把两叉树组织成两叉检索为了检索操作方便，一般把两叉树组织成两叉检索树。两叉检索树的定义是：树。两叉检索树的定义是：设树中每个结点的数据部分有一个数据项设树中每个结点的数据部分有一个数据项 key 是有序的是有序的,称该数据项为关键字。称该数据项为关键字。一个两叉树称为检索树，一个两叉树称为检索树，如果对每个结点如果对每个结点 ti，它的左子树中所有结点的，它的左子树中所有结点的 key 值都小于值都小于 ti 的的 key 值；值；ti 的右子树中所有结点的的右子树中所有结点的 key 值都大于值都大于 ti 的的 key 值。值。n二叉检索树的操作有二叉检索树的操作有:遍历遍历检索检索插入一个结点插入一个结点删除一个结点删除一个结点 由于树是递归定义的，所以树的操作用递归算由于树是递归定义的，所以树的操作用递归算法十分简洁。法十分简洁。设有说明部分设有说明部分:typedef .keytype；typedef .datatype；typedef struct tree keytype key；datatype data；struct tree *left；struct tree *right；treetype;typedef treetype *treepointer；treepointer root；n遍历遍历遍历二叉树是指按一定规律走遍树的每个结点，使每一遍历二叉树是指按一定规律走遍树的每个结点，使每一结点被访问一次，而且只被访问一次。在访问一个结点结点被访问一次，而且只被访问一次。在访问一个结点时，可以做任何信息加工工作。下例打印结点的时，可以做任何信息加工工作。下例打印结点的data域，域，并设该域为并设该域为char型的。型的。n遍历算法可分为前序，中序，后序遍历三种。遍历算法可分为前序，中序，后序遍历三种。前序遍历前序遍历：对任意一个结点：对任意一个结点 ti 来讲，先访问及处理该来讲，先访问及处理该结点的数据域；然后遍历左子树；最后遍历右子树。结点的数据域；然后遍历左子树；最后遍历右子树。中序遍历中序遍历：对任意一个结点：对任意一个结点 ti 来讲，先遍历左子树；来讲，先遍历左子树；然后访问及处理该结点的数据域；最后遍历右子树。然后访问及处理该结点的数据域；最后遍历右子树。后序遍历后序遍历：对任意一个结点：对任意一个结点 ti 来讲，先遍历左子树；来讲，先遍历左子树；然后遍历右子树；最后访问及处理该结点的数据域。然后遍历右子树；最后访问及处理该结点的数据域。【例例12-1】设有下图所示树设有下图所示树,这是由表达式这是由表达式(a+b/c)*(d-e*f)生成的生成的树，这棵树反映了表达式的结构，同时也反映了表达式的运算次树，这棵树反映了表达式的结构，同时也反映了表达式的运算次序。序。l 前序遍历过程是：得到表达式的波兰表示式（运算符在两个前序遍历过程是：得到表达式的波兰表示式（运算符在两个运算分量前）。运算分量前）。l前序遍历算法是：前序遍历算法是：void preorder(treepointer p)if(p!=NULL)printf(“%c”,p-data);preorder(p-left);preorder(p-right)*+-a/d*bcef a/b c-d*e fl中序遍历过程是：中序遍历过程是：得到表达式的原形式，只是没有括号。得到表达式的原形式，只是没有括号。中序遍历算法是：中序遍历算法是：void inorder(treepointer p)/*中序遍历中序遍历*/if(p!=NULL)inorder(p-left);printf(“%c”,p-data);inorder(p-right)*+-a/d*bcefa/bc-d*efl后序遍历过程是：后序遍历过程是：得到表达式的表达式的逆波兰表示式（运算符在两个运算分量得到表达式的表达式的逆波兰表示式（运算符在两个运算分量之后）。之后）。后序遍历算法是：后序遍历算法是：void postorder(treepointer p)/*后序遍历后序遍历*/if(p!=NULL)postorder(p-left);postorder(p-right)printf(“%c”,p-data);*+-a/d*bcefa/b c-d*e fn检索检索检索是按给定关键字值检索是按给定关键字值 c 在树上找一个结点在树上找一个结点 ti，且，且 ti 的关的关键字值键字值 key 恰好等于恰好等于 c。若检索到，函数将带回相应结点。若检索到，函数将带回相应结点指针；否则若没检索到，函数将带回指针；否则若没检索到，函数将带回 NULL。下述检索算。下述检索算法的前提条件是，法的前提条件是，p 是检索树。是检索树。treepointer search(typekey c,treepointer p)if(p-key=c)|(p=NULL)return p;else if(c key)return search(c,p-left);else return search(c,p-right);n插入一个结点插入一个结点插入是指将一个数据项插入到树中某一恰当位置，使树仍插入是指将一个数据项插入到树中某一恰当位置，使树仍保持检索树的性质。显然，首先要按保持检索树的性质。显然，首先要按key值查出应该插入值查出应该插入的位置，然后再插入。的位置，然后再插入。void insert(keytype c,datatype d,treepointer*p)if(*p=NULL)*p=(treepointer)malloc(sizeof(struct tree);(*p)-key =c;(*p)-data =d;(*p)-left =NULL;(*p)-right =NULL;else if(c key)insert(c,d,&(*p)-left);else insert(c,d,&(*p)-right);由于由于 insert 的参数的参数 p 是指向指针的指针类型，在是指向指针的指针类型，在 insert 内内 p 指向指向指针类型的实在参数指针类型的实在参数。所以在执行。所以在执行*p=(treepointer)malloc(sizeof(struct tree)时，将使实在参数指针变量指向新申请来的结点。时，将使实在参数指针变量指向新申请来的结点。1)若调用若调用 insert 时，如图时，如图 root 为空树。为空树。以以&root 作实在参数调用作实在参数调用 insert,即即 insert(c,d,&root)insert 的形式参数的形式参数 p 指向指向 root，而，而 root 值为值为 NULL。转插入功能，执行转插入功能，执行 *p=(treepointer)malloc(sizeof(struct tree)得得:再执行后边的几个赋值语句再执行后边的几个赋值语句,得得:root:c;d p:2)若调用若调用insert时，时，root非空，在中间某一个结点查到空指非空，在中间某一个结点查到空指 针，如图；设查到该结点后，应该继续向右查，以针，如图；设查到该结点后，应该继续向右查，以&(*p)-right)作实在参数递归调用作实在参数递归调用insert，即执行，即执行 insert(c,d,&(*p)-right)insert 的形式参数的形式参数 p 指向本步的指向本步的(*p)-right，而，而(*p)-right 值为值为 NULL。转插入功能，执行转插入功能，执行 *p=(treepointer)malloc(sizeof(struct tree)再执行后边的几个赋值语句再执行后边的几个赋值语句,得得:c;d .p:n删除一结点删除一结点设欲删除结点为设欲删除结点为 r，则可能有如下几种情况。针对不同，则可能有如下几种情况。针对不同情况删除算法不同情况删除算法不同.r 是叶结点是叶结点:简单删掉简单删掉 r 结点，并把结点，并把 r 的父结点连接处改的父结点连接处改成成NULL 即可即可。42513r:r 只有一个左子树只有一个左子树78563124r:78564231r:r 只有一个子树只有一个子树:把把 r 以下部分接入以下部分接入 r 的父结点连接的父结点连接 r 处。处。然后删掉然后删掉r结点结点。r 只有一个右子树只有一个右子树r 两个方向都有子树两个方向都有子树:在在 r 的左子树上找到关键字的左子树上找到关键字 key 值值最大的结点最大的结点 s，把，把 s 结点的数据结点的数据 data及关键字及关键字 key 复制复制到到 r 结点上，然后删除掉结点上，然后删除掉 s 结点。结点。9s:10r:4514151213312118679当然也可以在当然也可以在r的右子树上找到关键字的右子树上找到关键字key值最小的结点值最小的结点s，把，把s结点的数据结点的数据data及关键字及关键字key复制到复制到r结点上，然结点上，然后删除掉后删除掉s结点。结点。8s:5r:410131411123129766使用在左子树上找最大结点的方法，按如使用在左子树上找最大结点的方法，按如下步骤进行下步骤进行:沿沿 r 左子树的右方向，向下找一个没有左子树的右方向，向下找一个没有右子树的结点右子树的结点s，图中结点，图中结点(9)。把该结点把该结点 s 的值复制到结点的值复制到结点r（即欲删除（即欲删除的结点。的结点。把把 s 的左子树连在的左子树连在 s 的父结点（图中为的父结点（图中为结点结点(5)）的右链上，在图中即连到）的右链上，在图中即连到(5)结点的右链上。结点的右链上。删除删除s结点，即图中的结点，即图中的(9)结点。结点。图图3的情况的情况 r 两个方向都有子树两个方向都有子树:在在 r 的左子树上找到关键字的左子树上找到关键字 key 值值最大的结点最大的结点 s，把，把 s 结点的数据结点的数据 data及关键字及关键字 key 复制到复制到 r 结点结点 上，然后删除掉上，然后删除掉 s 结点。结点。9s:10r:4514151213312118679综合上述三种情况，下述函数综合上述三种情况，下述函数deletenode 完成删除完成删除一个结点。一个结点。deletenode的调用形式是：的调用形式是：deletenode(valueofkey,&root)其中其中lvalue_of_key是欲删除结点的关键字值；是欲删除结点的关键字值；lroot是指针类型（是指针类型（treepointer）变量，指向树）变量，指向树根。这里根。这里用指向指针的指针作参数。用指向指针的指针作参数。treepointer del(treepointer*,treepointer*)；/*处理第三种情处理第三种情况的函数的函数原型况的函数的函数原型*/void deletenode(keytype c,treepointer*p)/*删除关键字删除关键字值等于值等于 c 的结点的结点*/treepointer r;if(*p=NULL)printf(“not found:%dn”,c);else if(c key)/*c left);else if(c (*p)-key)/*c 当前结点的当前结点的 key 值，被删结点在右子树上值，被删结点在右子树上*/deletenode(c,&(*p)-right);else r =*p;if(r-right=NULL)*p =r-left /*右子树空，接左分支右子树空，接左分支*/else if(r-left=NULL)*p =r-right;/*左子树空，接右分支左子树空，接右分支*/else r=del(&(r-left),p);/*左右均非空左右均非空*/free(r);/*释放释放 r*/;45627138root:p:deletenode(4,&root)r:r 只有一个左子树只有一个左子树treepointer del(treepointer*s,treepointer*p)/*处理第三种情况，仅第三种情况调用处理第三种情况，仅第三种情况调用*/treepointer r;if(*s)-right!=NULL)/*右分支非空右分支非空?*/r=del(&(*s)-right),p)/右分支非空右分支非空,在右方向以下继续查找在右方向以下继续查找 else /*找到右分支为空的结点找到右分支为空的结点*s*/(*p)-key =(*s)-key;/*复制复制*s的关键字、数据到的关键字、数据到*p结点结点*/(*p)-data=(*s)-data;r=*s;/*r记载该记载该*s结点，为结点，为free做准备做准备*/*s=(*s)-left；/*删除删除*s所指结点。由于所指结点。由于s参数是指向指针的变量参数是指向指针的变量*/*本语句把本语句把*s 左分支接到左分支接到*s 的父结点上，的父结点上，*/*从而在树上摘下了从而在树上摘下了*s 所指向的结点。所指向的结点。*/return r;/把将释放的变量指针带回主程序把将释放的变量指针带回主程序123459768101112131415p:s:9r:root:图图G=(V，E)。其中。其中,lV=(v1,v2,vn)为图为图G的结点集合的结点集合 lvi为图为图G中结点中结点lE=(vi,vj)|vi,vj V 是图中边的集合是图中边的集合l(vi,vj)表示连接结点表示连接结点vi到结点到结点vj的边。的边。04316752图图graph(一一)邻接表方法邻接表方法 设设图图G有有k个结点，使用一个个结点，使用一个k*k的的int型矩阵型矩阵g表示表示图图G,矩阵矩阵g的第的第i行顺序列出与结点行顺序列出与结点i直接相连的结点编号直接相连的结点编号,最后以最后以“-1”结尾。则结尾。则图图G表示成右图的邻接表。表示成右图的邻接表。04316752012-11034-12045-1314-1412367-15267-1645-1745-1(二二)邻接矩阵方法邻接矩阵方法 设设图图G有有k个结点，使用一个个结点，使用一个k*k的的bool类型矩阵类型矩阵g表示表示图图G 矩阵元素矩阵元素 利用这种表示法，左图的网表示成右图利用这种表示法，左图的网表示成右图 8*8 的的 bool 矩阵。矩阵。g i j,=truetrue i j falsefalse i j 表示从结点表示从结点到结点到结点有直接路；有直接路；表示从结点表示从结点到结点到结点没有直接路；没有直接路；012345670tt1ttt2ttt3tt4ttttt5ttt6tt7tt04316752(三三)邻接链表方法邻接链表方法 设图设图G中有中有k个结点，使用一个有个结点，使用一个有k个元素的一维指针数组个元素的一维指针数组G,数组数组G的第的第i个元素对应网中第个元素对应网中第i个结点。以它为链首个结点。以它为链首,把与结点把与结点i直接相连的结点链成一个链。图直接相连的结点链成一个链。图G表示成右图的邻接链表表示成右图的邻接链表:04316752 4 5 .1 2 .1 4 0 3 4 .0 4 5 .2 6 7 .1 2 3 6 7 .4 5 .7 6 5 4 3 2 1 0已知一个网已知一个网g=(v,e)。其中。其中,l v=(v1,v2,vn)为网为网g的结点集合的结点集合,l vi为网中结点。为网中结点。l e=(vi,vj)是网中边的集合是网中边的集合,l(vi,vj)表示连接结点表示连接结点vi到结点到结点vj的边。的边。找路径是指求从结点找路径是指求从结点m到结点到结点n的所有路径。的所有路径。04316752例例12-5找路径找路径解解:这样想该问题这样想该问题,1.从从m点出发沿所有可能的路向前走一步点出发沿所有可能的路向前走一步;2.然后再站在新的点上，再向前走一步然后再站在新的点上，再向前走一步;.如此重复，直到走到结点如此重复，直到走到结点n为止。为止。在走的过程中，保证不走重