C程序设计第12章PPT学习教案

1、会计学1C程序设计第程序设计第12章章n使用数组带来的问题是：使用数组带来的问题是：n操作不方便；操作不方便；n数组尺寸不好确定。数组尺寸不好确定。 第二，数组第二，数组多大：为保存全部卡片，并且人多大：为保存全部卡片，并且人数不固定，就应该给一个足够大数不固定，就应该给一个足够大的数组。的数组。n最好把这些卡片存储成动态的，最好把这些卡片存储成动态的，n需要多大存储量（有多少张卡片）需要多大存储量（有多少张卡片）就用多大。就用多大。n中间加一张卡片时不要向后串别中间加一张卡片时不要向后串别的卡片，的卡片，n删除一张卡片时不要留下删除一张卡片时不要留下“洞洞”。第1页/共91页 如图的链式结构

2、可以满足要求:n当增加一张卡片时，只需要向计算机系统申请一块空间，联到链的适当位置上。例如，要增加一张卡片 50 插入到 2 、3 之间，则只需要如下修改指针：n若删除一节，只需要将其从链上摘下来即可。例删除2节得链上已经没有2节了，删掉的节所占的存储空间还可以还回计算机系统，以便作其它用途。123 n.50 第2页/共91页n这就是一种动态数据结构中的这就是一种动态数据结构中的链表。动态数据结构上的一项链表。动态数据结构上的一项是一个动态变量，指针是标识动是一个动态变量，指针是标识动态变量的有力手段。动态变量与态变量的有力手段。动态变量与静态变量的区别在于静态变量的区别在于:n静态变量是程序

3、中由程序员静态变量是程序中由程序员“显显式式”说明的变量。它有一个名字，说明的变量。它有一个名字，在编译时，编译程序已经给它分在编译时，编译程序已经给它分配存储空间。这块存储空间用变配存储空间。这块存储空间用变量的名字来标识。量的名字来标识。第3页/共91页n动态变量在程序中没有动态变量在程序中没有“显式显式”说明，它没有名字说明，它没有名字n在编译时编译程序不知道有该变量，不给（也不可在编译时编译程序不知道有该变量，不给（也不可能给）它分配空间。能给）它分配空间。n动态变量是在程序运行时动态变量是在程序运行时n随程序存储数据的需要，申请空间随程序存储数据的需要，申请空间函数（例如函数（例如m

4、alloc，当然也是由程，当然也是由程序员安排的）随机的动态的申请来序员安排的）随机的动态的申请来的空间。它没有名字，一般动态变的空间。它没有名字，一般动态变量都由指针标识。量都由指针标识。n当使用完毕后，由释放空间函数当使用完毕后，由释放空间函数（例如（例如free）释放，还回计算机存）释放，还回计算机存储管理系统，以备它用。储管理系统，以备它用。第4页/共91页n注意：这里所说的静态变量不是注意：这里所说的静态变量不是C语言中由静态存储类别语言中由静态存储类别static声声明的变量；动态变量也不是明的变量；动态变量也不是C语语言中由自动存储类别言中由自动存储类别auto声明的声明的变量。

5、而是一般程序设计概念中变量。而是一般程序设计概念中的静态变量、动态变量的静态变量、动态变量第5页/共91页第6页/共91页目标代码空间静态区空间库代码空间堆区空间栈区空间 内存 程序运行时，涉及用户程序的内存存储结构如右图所示，首先是目标代码区；然后是静态存储区，用于存放那些可用绝对地址标识的，主要是具有静态存储类别的数据和变量；接着是目标代码运行时用到的库程序代码区；最后剩余空间是栈区和堆区，栈区和堆区从剩余空间的两端，动态的向中间增长。栈区用来存储程序中声明的函数的局部变量等具有自动存储类别的数据和变量；堆区用来存储经过动态申请空间函数申请的变量。第7页/共91页nsizeof 运算符运算

6、符n单目运算符单目运算符 sizeof 的的n操作数操作数是类型。是类型。n运算结果运算结果是求得相应类型的尺寸，即存储是求得相应类型的尺寸，即存储相应类型数据所需要的字节数。相应类型数据所需要的字节数。nsizeof(int) /* 结果是结果是2 */nsizeof(char) /* 结果是结果是1 */nsizeof(struct date) /* 若若 struct date 是第十一章定义的日期类型，是第十一章定义的日期类型，结果是结果是6 */第8页/共91页nmalloc 函数函数:n原型原型 void *malloc(unsigned long size);n功能功能 申请足够

7、大内存区域用来存申请足够大内存区域用来存储长度为储长度为size的数据对象，返回的数据对象，返回该区域的首指针，并保证该区域该区域的首指针，并保证该区域符合任何数据类型对存储区域开符合任何数据类型对存储区域开始地址和对齐的要求。始地址和对齐的要求。 返回指针是返回指针是void类型的，调类型的，调用者必须使用显示强制类型转换，用者必须使用显示强制类型转换，把该指针转换成所需要类型的指把该指针转换成所需要类型的指针。针。第9页/共91页n例例:float *p ;p = (float*)malloc( sizeof(float) );struct date *pdate;pdate=(struc

8、t date*)malloc(sizeof(struct date);第10页/共91页nfree函数函数n动态申请的内存如果不再使用，动态申请的内存如果不再使用，应当适时释放这样可以提高程序应当适时释放这样可以提高程序运行效率。运行效率。free函数用来释放经过函数用来释放经过malloc申请的动态空间。申请的动态空间。free的函的函数数n原型原型 void free ( void *ptr ) ;n功能功能释放由释放由malloc申请的内存区域。申请的内存区域。free的参数的参数ptr是一个指针，指向是一个指针，指向以前由以前由malloc申请的一个内存区申请的一个内存区域。域。第11

9、页/共91页n例例n申请申请float *p ;p = (float*)malloc( sizeof(float) );struct date *pdate;pdate=(struct date*)malloc(sizeof(struct date);n释放释放free(p);free(pdate);第12页/共91页nfree(ptr) /* 释放释放ptr所指向由所指向由malloc申请的内存空间申请的内存空间 */n一块存储区域一经释放，便不能再使用。使用一块存储区域一经释放，便不能再使用。使用free特别注意，操作不当会产生不可预料的结果。如下特别注意，操作不当会产生不可预料的结果。如

10、下情况下使用情况下使用free都会造成灾难性后果。都会造成灾难性后果。nptr无值；无值；nptr的值为的值为NULL；nptr所指向的空间不是经过所指向的空间不是经过malloc申申请来的；请来的；n对一次申请的存储区进行多次释放对一次申请的存储区进行多次释放（实际可能是（实际可能是ptr无值或值为无值或值为NULL）。）。第13页/共91页n实用问题实用问题:n若指针变量指向的用若指针变量指向的用malloc申请来的动态变量，是申请来的动态变量，是孤立的不能与其它变量相联系，显然作用不大。孤立的不能与其它变量相联系，显然作用不大。n引进动态变量的目的是构造动态数据结构。引进动态变量的目的是

11、构造动态数据结构。n例如象本章开始介绍的那样，构造一个链表等。例如象本章开始介绍的那样，构造一个链表等。n这就要求一个数据项上除基本的数据信息外，还应这就要求一个数据项上除基本的数据信息外，还应包含与其它数据项相联系的信息，也就是包含指针。包含与其它数据项相联系的信息，也就是包含指针。n该结构必须用结构体类型描述，链表上一节的类型该结构必须用结构体类型描述，链表上一节的类型定义形式。定义形式。第14页/共91页类型定义形式 struct t 基本数据部分； struct t *next ; 基本数据部分指针部分一个数据项 123 n.第15页/共91页栈栈 stackn在第六章已经用数组实现过

12、栈和队列，但是，数组有一定的局限在第六章已经用数组实现过栈和队列，但是，数组有一定的局限性。如图可以用单向链表实现栈，指针变量性。如图可以用单向链表实现栈，指针变量top指向栈顶。栈的操指向栈顶。栈的操作有作有: 初始化：初始化：stackintial 压栈：压栈：stackpush 弹栈：弹栈：stackpop第16页/共91页设有声明设有声明: typedef . items ; typedef struct stackcell items data ; struct stackcell *predocessor ; stackcelltype ; typedef stackcelltyp

13、e *pstacktype ; pstacktype top ;top:. .栈第17页/共91页如下实现栈的操作：如下实现栈的操作： 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 ) *

14、x = top-data ; p = top ; top = top-predecessor ; free(p); else printf( “栈下溢栈下溢n” ); 第18页/共91页看一下这三个操作看一下这三个操作:1.初始化后初始化后(调用调用stackinitail)得。得。2.调用一次调用一次 stackpush(1) 得。得。3.再调用一次再调用一次stackpush(2)得得 。4.调用一次调用一次stackpop(&b)得得 。top:1.2b:2第19页/共91页n如图可用单向链表实现队列，现在要用两个指针变量，一如图可用单向链表实现队列，现在要用两个指针变量，一个指向队头（

15、个指向队头（front），一个指向队尾（），一个指向队尾（rear）。队列的操）。队列的操作有作有 初始化（初始化（ queueinitial ） 进队进队排在队尾（排在队尾（inqueue） 出队出队从队头删一项（从队头删一项（outqueue）rear:front:. .第20页/共91页设有如下说明设有如下说明: typedef . items ; typedef struct queue items data struct queue *next ; queuetype ; typedef queuetype *pqueuetype ; pqueuetype front,rear ;操

16、作：操作： void queueinital(void) front = NULL ; rear = NULL ; 第21页/共91页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 ; 第22页/共91页void outgueue ( item *x ) pqueuetype p; if

17、 ( front=NULL ) printf( “队空队空n” ); else *x = front- data ; p = front ; front = front- next; if ( front=NULL ) rear = NULL ; free( p ) ; 第23页/共91页看一下这三个操作看一下这三个操作: 1. 调用初始化后（调用一次调用初始化后（调用一次 queueinitail） 得；得； 2. 调用一次调用一次ingueue(1)得；得； 再调用一次再调用一次ingueue(2)得；得； 再调用一次再调用一次 ingueue(3)得得 ;3. 调用一次调用一次 outg

18、ueue(&a) 得；得； 再调用一次再调用一次 outgueue(&b) 得得; 再调用一次再调用一次 outgueue(&a) 得得 。1a:rear:front:231 p:b:23NULLNULL第24页/共91页base:1.2N-1N.双向链base:12N-1N.单向链第25页/共91页base:12N-1N.环形链base:12N-1N.双向环形链第26页/共91页n创建单向链表创建单向链表: :第27页/共91页n遍历单向链表遍历单向链表:p = base ; p0 = NULL;while (p != NULL ) p = base ; 加工 p - while (p !=

19、 NULL ) p = p- next; 加工 p - p0 = p ; p = p- next; 第28页/共91页n在单向链表上检索在单向链表上检索: 检索是指在单向链表上查找关键字等于某给定检索是指在单向链表上查找关键字等于某给定值的节点值的节点, 若找到则带回相应节点的指针；否则若找到则带回相应节点的指针；否则带回带回NULL 。设关键字域域名为。设关键字域域名为key ；欲检索的；欲检索的关键字值为关键字值为key0 . 如下算法实现检索：如下算法实现检索： p0 = NULL; p = base ; while (p != NULL & p-key !=key0 ) p0 = p;

20、 p = p- next; 第29页/共91页n向单向链表插入一项向单向链表插入一项: 设有下图的链表，现在要把设有下图的链表，现在要把r所指示的数据项插所指示的数据项插入到入到 p0、p 所指两项之间。操作是所指两项之间。操作是: r- next = p ; p0- next = r ; p0 = r /* 使使 p0 仍为仍为 p 的前一项的前一项 */r:5p0: p: 1 2 3 4.第30页/共91页n从单向链表上删除一项从单向链表上删除一项: 设有下图的链表，现在要删除设有下图的链表，现在要删除p所指项。删除所指项。删除算法是：算法是： q = p ; p = p- next ;

21、p0- next = p ; free(q)p0:1234.p:q:第31页/共91页n交换单向链表上两项交换单向链表上两项: 设有如图所示链表。现在要把设有如图所示链表。现在要把 p 所指的项与所指的项与 q 所指所指的项交换的项交换 为了表示操作方便，我们把该链表分两段画出。为了表示操作方便，我们把该链表分两段画出。p0p123.q0 q456.第32页/共91页p0:p:123.q0q:456. g:/*交换 p- next 、q- next */ g = p- next; /* 1 */ p- next = q- next; /* 2 */ q- next = g; /* 3 */ /

22、*交换 p0- next 、q0- next */ p0- next = q; /* 4 */ q0- next = p; /* 5 */*交换 p 、q */ p = p0- next ; /* 6 */ q = q0- next ; /* 7 */第33页/共91页n两叉树，两叉树的每个数据项附带两个指针，分别指向它的两个两叉树，两叉树的每个数据项附带两个指针，分别指向它的两个分支。两叉树的定义分支。两叉树的定义:n空是树；空是树；n一个结点连接两个不相交的树一个结点连接两个不相交的树,仍为树；仍为树； n所有结点具有相同的数据类型。所有结点具有相同的数据类型。*+-a/d*bcef( a

23、 + b / c ) * ( d e * f )第34页/共91页root: 设 ti 为二叉树的一个结点，一般 ti 由两部分组成：l基本数据部分-保存本结点上的基本数据；l指针部分连-接本结点以下的其它结点。 结点 ti 的指针连接的结点称为 ti 的子结点， 相应 ti 称为其子结点的父结点。 ti的指针部分有两个指针：左指针、右指针。 称 ti 的左指针连接的部分为 ti 的左子树， ti 的右指针连接的部分为 ti 的右子树。 若左、右子树均空，则称 ti 为叶结点。ti第35页/共91页78563124ti:n为了检索操作方便，一般把两叉树组织成两叉检为了检索操作方便，一般把两叉树

24、组织成两叉检索树。两叉检索树的定义是：索树。两叉检索树的定义是：n设树中每个结点的数据部分有一个设树中每个结点的数据部分有一个数据项数据项 key 是有序的是有序的, 称该数据项称该数据项为关键字。为关键字。n一个两叉树称为检索树，一个两叉树称为检索树，n如果对每个结点如果对每个结点 ti ，它的左子树中，它的左子树中所有结点的所有结点的 key 值都小于值都小于 ti 的的 key 值；值；nti 的右子树中所有结点的的右子树中所有结点的 key 值都值都大于大于 ti 的的 key 值。值。第36页/共91页n二叉检索树的操作有二叉检索树的操作有:n遍历遍历n检索检索n插入一个结点插入一个

25、结点n删除一个结点删除一个结点 由于树是递归定义的，所以树的由于树是递归定义的，所以树的操作用递归算法十分简洁。操作用递归算法十分简洁。第37页/共91页 设有说明部分设有说明部分: typedef . keytype ； typedef . datatype ； typedef struct tree keytype key ； datatype data ； struct tree *left ； struct tree *right ； treetype; typedef treetype * treepointer ； treepointer root ；第38页/共91页n遍历遍历遍

26、历二叉树是指按一定规律走遍树的每个结点，使每遍历二叉树是指按一定规律走遍树的每个结点，使每一结点被访问一次，而且只被访问一次。在访问一个一结点被访问一次，而且只被访问一次。在访问一个结点时，可以做任何信息加工工作。下例打印结点的结点时，可以做任何信息加工工作。下例打印结点的data域，并设该域为域，并设该域为char型的。型的。n遍历算法可分为前序，中序，后序遍历三种。遍历算法可分为前序，中序，后序遍历三种。n前序遍历前序遍历：对任意一个结点：对任意一个结点 ti 来讲，先访问及处理来讲，先访问及处理该结点的数据域；然后遍历左子树；最后遍历右子该结点的数据域；然后遍历左子树；最后遍历右子树。树

27、。n中序遍历中序遍历：对任意一个结点：对任意一个结点 ti 来讲，先遍历左子树；来讲，先遍历左子树；然后访问及处理该结点的数据域；最后遍历右子树。然后访问及处理该结点的数据域；最后遍历右子树。n后序遍历后序遍历：对任意一个结点：对任意一个结点 ti 来讲，先遍历左子树；来讲，先遍历左子树；然后遍历右子树；最后访问及处理该结点的数据域。然后遍历右子树；最后访问及处理该结点的数据域。第39页/共91页 【例例12-1】设有下图所示树设有下图所示树,这是由表达式这是由表达式 (a+b/c)*(d-e*f) 生成生成的树，这棵树反映了表达式的结构，同时也反映了表达式的运的树，这棵树反映了表达式的结构，

28、同时也反映了表达式的运算次序。算次序。l 前序遍历过程是：得到表达式的波兰表示式（运算符在两前序遍历过程是：得到表达式的波兰表示式（运算符在两个运算分量前）。个运算分量前）。l前序遍历算法是：前序遍历算法是： void preorder (treepointer p) if ( p!=NULL ) printf(“%c” , p- data ) ; preorder( p- left ) ; preorder( p- right ) *+-a/d*bcefa/bc-d*ef第40页/共91页l中序遍历过程是：中序遍历过程是：得到表达式的原形式，只是没有括号。得到表达式的原形式，只是没有括号。中

29、序遍历算法是：中序遍历算法是： void inorder (treepointer p) /*中序遍历中序遍历*/ if ( p!=NULL ) inorder( p- left ) ; printf(“%c” , p- data ) ; inorder( p- right ) *+-a/d*bcefa/bc-d*ef第41页/共91页l后序遍历过程是：后序遍历过程是：得到表达式的表达式的逆波兰表示式（运算符在两个运算分量得到表达式的表达式的逆波兰表示式（运算符在两个运算分量之后）。之后）。后序遍历算法是：后序遍历算法是： void postorder (treepointer p) /*后序

30、遍历后序遍历*/ if ( p!=NULL ) postorder( p- left ) ; postorder( p- right ) printf(“%c” , p- data ) ; *+-a/d*bcefa/bc-d*ef第42页/共91页n检索检索检索是按给定关键字值检索是按给定关键字值 c 在树上找一个结点在树上找一个结点 ti ，且，且 ti 的的关键字值关键字值 key 恰好等于恰好等于 c 。若检索到，函数将带回相应。若检索到，函数将带回相应结点指针；否则若没检索到，函数将带回结点指针；否则若没检索到，函数将带回 NULL 。下述检。下述检索算法的前提条件是，索算法的前提条件

31、是，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 ) ; 第43页/共91页n插入一个结点插入一个结点插入是指将一个数据项插入到树中某一恰当位置，使树插入是指将一个数据项插入到树中某一恰当位置，使树仍保持检索树的性质。显然，首先要按仍保持检索树的性质。显然，首先要

32、按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

33、, d , &(*p)-right) ) ; 第44页/共91页由于 insert 的参数 p 是指向指针的指针类型，在 insert 内 p 指向指针类型的实在参数。所以在执行 *p=(treepointer)malloc(sizeof(struct tree)时，将使实在参数指针变量指向新申请来的结点。第45页/共91页 1) 若调用 insert 时，如图 root 为空树。 以 &root 作实在参数调用 insert , 即 insert(c,d,&root) insert 的形式参数 p 指向 root ，而 root 值为 NULL。 转插入功能，执行 *p=(treepoint

34、er)malloc(sizeof(struct tree) 得: 再执行后边的几个赋值语句, 得: root: c ; d p:第46页/共91页 2) 若调用insert时，root非空，在中间某一个结点查到空指 针，如图；设查到该结点后，应该继续向右查，以 &(*p)-right)作实在参数递归调用insert，即执行 insert(c,d, &(*p)-right) )insert 的形式参数 p 指向本步的 (*p)- right ，而 (*p)- right 值为 NULL。转插入功能，执行 *p=(treepointer)malloc(sizeof(struct tree)再执行后

35、边的几个赋值语句, 得: c ; d . p:第47页/共91页n删除一结点设欲删除结点为 r，则可能有如下几种情况。针对不同情况删除算法不同.r 是叶结点:简单删掉 r 结点，并把 r 的父结点连接处改成NULL 即可 。 42513r:第48页/共91页r 只有一个左子树78563124r:78564231r:r 只有一个子树: 把 r 以下部分接入 r 的父结点连接 r 处。然后删掉r结点 。r 只有一个右子树第49页/共91页r 两个方向都有子树: 在 r 的左子树上找到关键字 key 值最大的结点 s，把 s 结点的数据 data及关键字 key 复制到 r 结点上，然后删除掉 s

36、结点。 9s:10r:4514151213312118679第50页/共91页当然也可以在r的右子树上找到关键字key值最小的结点s，把s结点的数据data及关键字key复制到r结点上，然后删除掉s结点。8s:5r:410131411123129766第51页/共91页使用在左子树上找最大结点的方法，按如下步骤进行:沿 r 左子树的右方向，向下找一个没有右子树的结点s ，图中结点 (9) 。把该结点 s 的值复制到结点r（即欲删除的结点。把 s 的左子树连在 s 的父结点（图中为结点(5) ）的右链上，在图中即连到(5) 结点的右链上。删除s结点，即图中的(9)结点。 图3的情况 r 两个方向

37、都有子树: 在 r 的左子树上找到关键字 key 值最大的结点 s，把 s 结点的数据 data及关键字 key 复制到 r 结点 上，然后删除掉 s 结点。 9s:10r:4514151213312118679第52页/共91页综合上述三种情况，下述函数deletenode 完成删除一个结点。deletenode的调用形式是： deletenode( valueofkey , &root )其中lvalue_of_key是欲删除结点的关键字值；lroot是指针类型（treepointer）变量，指向树根。这里用指向指针的指针作参数。第53页/共91页treepointer del( tree

38、pointer * , 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 值，被删结点在右子树上值，被删结点

39、在右子树上 */ deletenode( c , &(*p) - right ) ) ; 第54页/共91页 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 */ ;第55页/共91页45627138root:p:deletenod

40、e( 4 , &root )r:r 只有一个左子树第56页/共91页treepointer del( treepointer *s, treepointer *p ) /* 处理第三种情况，仅第三种情况调用处理第三种情况，仅第三种情况调用 */ treepointer r;if (*s)-right != NULL ) /* 右分支非空右分支非空? */ r=del( &(*s)-right),p ) /右分支非空右分支非空, 在右方向以下继续查找在右方向以下继续查找 else /* 找到右分支为空的结点找到右分支为空的结点 *s */ (*p)-key =(*s)- key ; /* 复制复

41、制 *s的关键字、数据到的关键字、数据到 *p结点结点 */ (*p)-data =(*s)- data ; r = *s ; /* r记载该记载该 *s结点，为结点，为free做准备做准备 */ *s =(*s)- left ；/* 删除删除 *s所指结点。由于所指结点。由于s参数是指向指针的变量参数是指向指针的变量 */ /* 本语句把本语句把 *s 左分支接到左分支接到 *s 的父结点上，的父结点上，*/ /* 从而在树上摘下了从而在树上摘下了 *s 所指向的结点。所指向的结点。*/ return r; / 把将释放的变量指针带回主程序把将释放的变量指针带回主程序第57页/共91页123

42、459768101112131415p:s:9r:root:第58页/共91页图图G=(V，E)。其中。其中,lV=(v1 ,v2 , ,vn) 为图为图G的结点集的结点集合合 lvi为图为图G中结点中结点lE= (vi , vj ) |vi, vjV 是图中边的是图中边的集合集合l(vi ,vj)表示连接结点表示连接结点vi到结点到结点vj的边。的边。04316752第59页/共91页(一一) 邻接表方法邻接表方法 设设图图G有有k个结点，使用一个个结点，使用一个k*k的的int型矩阵型矩阵g表示表示图图G, 矩阵矩阵g的第的第i行顺序列出与结点行顺序列出与结点i直接相连的结点编号直接相连的

43、结点编号, 最后以最后以“-1”结尾。则结尾。则图图G表示成右图的邻接表。表示成右图的邻接表。04316752012-11034-12045-1314-1412367-15267-1645-1745-1第60页/共91页(二二) 邻接矩阵方法邻接矩阵方法 设设图图G有有k个结点，使用一个个结点，使用一个k*k的的bool类型矩阵类型矩阵g表示表示图图G 矩阵元素矩阵元素 利用这种表示法，左图的网表示成右图利用这种表示法，左图的网表示成右图 8*8 的的 bool 矩阵。矩阵。gij,=true i j false i j 表示从结点到结点有直接路；表示从结点到结点没有直接路；012345670

44、tt1ttt2ttt3tt4ttttt5ttt6tt7tt04316752第61页/共91页 (三三) 邻接链表方法邻接链表方法 设图设图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

45、3 2 1 0第62页/共91页已知一个网已知一个网g=(v,e)。其中。其中,l v=(v1 ,v2 , ,vn) 为网为网g的结点集合的结点集合, l vi为网中结点。为网中结点。l e= (vi , vj) 是网中边的集合是网中边的集合,l (vi ,vj)表示连接结点表示连接结点vi到结点到结点vj的边。的边。找路径是指求从结点找路径是指求从结点m到结点到结点n的所有路径。的所有路径。04316752第63页/共91页解解:这样想该问题这样想该问题, 1.从从m点出发沿所有可能的路向前走一步点出发沿所有可能的路向前走一步; 2.然后再站在新的点上，再向前走一步然后再站在新的点上，再向前

46、走一步; . 如此重复，直到走到结点如此重复，直到走到结点n为止。为止。 在走的过程中，保证不走重复点，可以得到下图的算法在走的过程中，保证不走重复点，可以得到下图的算法:m=n输出p0rm点的所有后继结点 iip0rpr = mroute(i,n,r+1)route m:开始点；n:终结点； r:路迹数组p尾标结束第64页/共91页在该算法中，关键在于找出在该算法中，关键在于找出m点的所有后继点。点的所有后继点。 (一一) 邻接链表方法邻接链表方法 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第65页

47、/共91页设有如下声明：#define h 10struct node int no; struct node *link; ;int ph ; /* 路迹数组 */struct node *gh ; /* 网的邻接链表 */void printp( int,int )； / 函数原型：输出bool iinp( int,int,int ) ; / 函数原型：判断 /点i是否已经走过（在P中）第66页/共91页void route ( int m, int n, int r ) / 开始结点、终结结点、路迹数组开始结点、终结结点、路迹数组p的尾的尾 struct node *hh; int i;

48、 pr=m; if ( m=n ) printp(0,r); else hh = gm; while ( hh!=NULL ) i = hh-no; if ( !iinp(i,0,r) ) route(i,n,r+1); hh = hh-link; 第67页/共91页bool iinp( int ii,int u,int v ) int j; for ( j=u; j=v; j+ ) if ( ii=pj ) return true; return false ;void printp( int e,int f ) int j; for (j=e; jnext结束return base使bas

49、ep递增寻找p应该插入的位置r0,rp插入到r0、r之间结束第72页/共91页p插入到r0、r之间结束defrp把p独立出来=q ;p指向p0插入到r0,r之间:q-next = r ; r0-next = q插入到链头:q-next = base ; base = qr = base寻找位置r = base r-keykey r!=pr0 = r;r = r-next 结束def第73页/共91页考查程序运行中各个参数、变量、链表的变化状态。如图所示：考查程序运行中各个参数、变量、链表的变化状态。如图所示：设从设从base到到p0之间的子链表已经递增，现在加入之间的子链表已经递增，现在加入p

50、所指示的节；所指示的节；在在basep0之间查找合适位置，设应该把之间查找合适位置，设应该把p所指的节插入到所指的节插入到r0,r所之间；所之间；把把p独立出来独立出来=q ， p指向指向p0： q = p ; p0-next = p-next ; p = p0 ;把把p（现在由（现在由q指示）插入到指示）插入到r0,r之间：之间： q-next = r ; r0-next = q；现在链表结构是：现在链表结构是：datakeydatakey.datakeydatakeybase:datakeydatakeydatakeydatakeyr0:r:p:p0:q:第74页/共91页pt sort(

51、 pt base ) /* 链表排序，链表排序，base 为链首为链首 */ pt p , p0 , r , r0 , q ; p0 = NULL ; p = base ; while ( p!=NULL ) /* 逐项处理，把逐项处理，把p加入到子序列中，并保持加入到子序列中，并保持“base-p”递增递增 */ r = base ; /* 寻找位置寻找位置 */ while ( ( r-key key ) & ( r!=p ) ) r0 = r ; r = r- next ; if (r!=p) /* p插入到插入到r0、r之间之间 */ /* 若若 r=p ，在链尾，则不用插入，在链尾，

52、则不用插入 */ q = p ; /* 把把 p 独立出来，令独立出来，令 q 指向它指向它 */ p0-next = p-next ; p = p0 ; if ( r = base ) /* 插入插入 */ /* 插在链首插在链首 */ q-next = base ; base = q ; else /* 插在链中插在链中r0 、r之间之间 */ q-next = r ; r0 - next = q ; p0 = p ; /* 前进一项前进一项 */ p = p-next ; return base ; /* sort */ 第75页/共91页 对任意给定的自然数对任意给定的自然数 n ，把

53、所有如下形式的不可约分数，把所有如下形式的不可约分数 按递增顺序排列起来，称该序列为按递增顺序排列起来，称该序列为 n 级法雷序列级法雷序列 Fn 。 例如例如F8 为为: 编函数，对任意给定的正整数编函数，对任意给定的正整数n ，求，求n级法雷序列，并带回级法雷序列，并带回n级法雷序列链指针。级法雷序列链指针。 ( 0in ; 0ji )ji=0 1 1 1 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 5 6 7 1,1 8 7 6 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 6 7 8 1例例12-3 法雷序列法雷序列第76页/共91页分析：分析： 法雷序列

54、的每项是个分数，不能用实数精确的表示，而且这法雷序列的每项是个分数，不能用实数精确的表示，而且这些数的排列顺序是不规则的。用下图形式的链表来表示它。些数的排列顺序是不规则的。用下图形式的链表来表示它。 分子分母分子分母分子分母分子分母.第77页/共91页显然法雷序列的各项均在区间0/1,1/1之内。生成法雷序列算法l先把一阶法雷序列：0/1,1/1放入链表中；l然后顺序分别以i=2,3, . ,n 作分母，对任意i以j=1,2, . , i-1作 分子，作成分数j/i；l若j/i是不可约分数，则该j/i必然是法雷序列的一项；把该j/i插入到链表的合适位置上，并使链表仍保持按递增排序。0/1 ,

55、 1/1 放入序列读入 n生成 n 阶法雷序列链表结束 for(i=2; i=n; i+) for(j=1; ji; j+)把 j/i 放入序列j/i 不可约分把 j/i 插入到 r0,r 之间查 j/i 应插入的位置 r0,r第78页/共91页 struct farlei_item int numerator , denominator ; struct farlei_item *next ;typedef struct farlei_item * farleipointer ;int gcd( int x , int y ) /* 求最大公约数求最大公约数 */ if ( y=0 ) return x ; else return gcd( y , x % y ) ;第79页/共91页/*构造法雷序列,并返回序列头指针*/farleipointer farlei(int n) int i,j ; farleipointer fn , r , r0 , p ; if( n1 ) /如果nnumerator = 0 ; fn-denominator = 1 ; fn-next = (farleipointer) m