《【教学课件】第十二章动态数据结构.ppt》由会员分享,可在线阅读,更多相关《【教学课件】第十二章动态数据结构.ppt(92页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第十二章第十二章 动态数据结构动态数据结构n n管理动态变量管理动态变量n n动态数据结构动态数据结构栈栈栈栈 stack stack队列队列队列队列 queue queue 链表链表链表链表linkage tablelinkage table树树树树treetree图图图图 graph graphn n程序设计实例程序设计实例n n本章小结本章小结n n作业作业n n考虑上一章的职工卡片问题,用计算机管理考虑上一章的职工卡片问题,用计算机管理这些卡片这些卡片,要把卡片保存在计算机内。要把卡片保存在计算机内。n n首先,用什么数据结构存储:一张卡片是一首先,用什么数据结构存储:一张卡片是一个结
2、构体,所有卡片自然用结构体数组。个结构体,所有卡片自然用结构体数组。n n第三,操作问题:第三,操作问题:若增加一个人,应该在数组中加一个元素,会若增加一个人,应该在数组中加一个元素,会若增加一个人,应该在数组中加一个元素,会若增加一个人,应该在数组中加一个元素,会产生数组不够大的可能。产生数组不够大的可能。产生数组不够大的可能。产生数组不够大的可能。若增加一张卡片在数组中间,应该把加入位置若增加一张卡片在数组中间,应该把加入位置若增加一张卡片在数组中间,应该把加入位置若增加一张卡片在数组中间,应该把加入位置以后的其它元素依次向后移动。以后的其它元素依次向后移动。以后的其它元素依次向后移动。以
3、后的其它元素依次向后移动。若在中间删除一张卡片,会在数组中间留下一若在中间删除一张卡片,会在数组中间留下一若在中间删除一张卡片,会在数组中间留下一若在中间删除一张卡片,会在数组中间留下一个个个个“洞洞洞洞”,应该把,应该把,应该把,应该把“洞洞洞洞”以后的元素依次向前以后的元素依次向前以后的元素依次向前以后的元素依次向前移动移动移动移动n n使用数组带来的问题是:使用数组带来的问题是:操作不方便;操作不方便;操作不方便;操作不方便;数组尺寸不好确定。数组尺寸不好确定。数组尺寸不好确定。数组尺寸不好确定。第二,数组多大:为保第二,数组多大:为保第二,数组多大:为保第二,数组多大:为保存全部卡片,
4、并且人数不固定,就应该给一个存全部卡片,并且人数不固定,就应该给一个存全部卡片,并且人数不固定,就应该给一个存全部卡片,并且人数不固定,就应该给一个足够大的数组。足够大的数组。足够大的数组。足够大的数组。n n最好把这些卡片存储成动态的,最好把这些卡片存储成动态的,需要多大存储量(有多少张卡片)就用多大。需要多大存储量(有多少张卡片)就用多大。需要多大存储量(有多少张卡片)就用多大。需要多大存储量(有多少张卡片)就用多大。中间加一张卡片时不要向后串别的卡片,中间加一张卡片时不要向后串别的卡片,中间加一张卡片时不要向后串别的卡片,中间加一张卡片时不要向后串别的卡片,删除一张卡片时不要留下删除一张
5、卡片时不要留下删除一张卡片时不要留下删除一张卡片时不要留下“洞洞洞洞”。如图的链式结构可以满足要求如图的链式结构可以满足要求如图的链式结构可以满足要求如图的链式结构可以满足要求:n n当增加一张卡片时,只需要向计算机系统申请一块空间,联当增加一张卡片时,只需要向计算机系统申请一块空间,联当增加一张卡片时,只需要向计算机系统申请一块空间,联当增加一张卡片时,只需要向计算机系统申请一块空间,联到链的适当位置上。例如,要增加一张卡片到链的适当位置上。例如,要增加一张卡片到链的适当位置上。例如,要增加一张卡片到链的适当位置上。例如,要增加一张卡片 50 50 插入到插入到插入到插入到 2 2、3 3
6、之间,则只需要如下修改指针:之间,则只需要如下修改指针:之间,则只需要如下修改指针:之间,则只需要如下修改指针:n n若删除一节,只需要将其从链上摘下来即可。例删除若删除一节,只需要将其从链上摘下来即可。例删除若删除一节,只需要将其从链上摘下来即可。例删除若删除一节,只需要将其从链上摘下来即可。例删除2 2节得节得节得节得链上已经没有链上已经没有链上已经没有链上已经没有2 2节了,删掉的节所占的存储空间还可以还回节了,删掉的节所占的存储空间还可以还回节了,删掉的节所占的存储空间还可以还回节了,删掉的节所占的存储空间还可以还回计算机系统,以便作其它用途。计算机系统,以便作其它用途。计算机系统,以
7、便作其它用途。计算机系统,以便作其它用途。1 12 23 3 n n.50 n n这就是一种动态数据结构中的这就是一种动态数据结构中的链表。动链表。动态数据结构上的一项是一个动态变量,指针态数据结构上的一项是一个动态变量,指针是标识动态变量的有力手段。动态变量与静是标识动态变量的有力手段。动态变量与静态变量的区别在于态变量的区别在于:n n静态变量是程序中由程序员静态变量是程序中由程序员“显式显式”说明的说明的变量。它有一个名字,在编译时,编译程序变量。它有一个名字,在编译时,编译程序已经给它分配存储空间。这块存储空间用变已经给它分配存储空间。这块存储空间用变量的名字来标识。量的名字来标识。n
8、 n动态变量在程序中没有动态变量在程序中没有动态变量在程序中没有动态变量在程序中没有“显式显式显式显式”说明,它没有名字说明,它没有名字说明,它没有名字说明,它没有名字n n在编译时编译程序不知道有该变量,不给(也不可在编译时编译程序不知道有该变量,不给(也不可在编译时编译程序不知道有该变量,不给(也不可在编译时编译程序不知道有该变量,不给(也不可能给)它分配空间。能给)它分配空间。能给)它分配空间。能给)它分配空间。n n动态变量是在程序运行时动态变量是在程序运行时动态变量是在程序运行时动态变量是在程序运行时随程序存储数据的需要,申请空间函数(例如随程序存储数据的需要,申请空间函数(例如随程
9、序存储数据的需要,申请空间函数(例如随程序存储数据的需要,申请空间函数(例如mallocmalloc,当然也是由程序员安排的)随机的动态,当然也是由程序员安排的)随机的动态,当然也是由程序员安排的)随机的动态,当然也是由程序员安排的)随机的动态的申请来的空间。它没有名字,一般动态变量都的申请来的空间。它没有名字,一般动态变量都的申请来的空间。它没有名字,一般动态变量都的申请来的空间。它没有名字,一般动态变量都由指针标识。由指针标识。由指针标识。由指针标识。当使用完毕后,由释放空间函数(例如当使用完毕后,由释放空间函数(例如当使用完毕后,由释放空间函数(例如当使用完毕后,由释放空间函数(例如fr
10、eefree)释)释)释)释放,还回计算机存储管理系统,以备它用。放,还回计算机存储管理系统,以备它用。放,还回计算机存储管理系统,以备它用。放,还回计算机存储管理系统,以备它用。n n注意:这里所说的静态变量不是注意:这里所说的静态变量不是C语言中由语言中由静态存储类别静态存储类别static声明的变量;动态变量声明的变量;动态变量也不是也不是C语言中由自动存储类别语言中由自动存储类别auto声明的声明的变量。而是一般程序设计概念中的静态变量、变量。而是一般程序设计概念中的静态变量、动态变量动态变量管理动态变量管理动态变量n n动态变量在程序运行时,随程序存储数据动态变量在程序运行时,随程序
11、存储数据的需要,向计算机系统申请;使用完后还的需要,向计算机系统申请;使用完后还回计算机系统。回计算机系统。n n本节介绍本节介绍申请计算机存储空间函数申请计算机存储空间函数申请计算机存储空间函数申请计算机存储空间函数mallocmalloc释放存储空间函数释放存储空间函数释放存储空间函数释放存储空间函数free free 目标代码空间目标代码空间静态区空间静态区空间库代码空间库代码空间堆区空间堆区空间栈区空间栈区空间 内存内存内存内存 程序运行时,涉及用户程序的内存存储程序运行时,涉及用户程序的内存存储程序运行时,涉及用户程序的内存存储程序运行时,涉及用户程序的内存存储结构如右图所示,首先是
12、目标代码区;然后是结构如右图所示,首先是目标代码区;然后是结构如右图所示,首先是目标代码区;然后是结构如右图所示,首先是目标代码区;然后是静态存储区,用于存放那些可用绝对地址标识静态存储区,用于存放那些可用绝对地址标识静态存储区,用于存放那些可用绝对地址标识静态存储区,用于存放那些可用绝对地址标识的,主要是具有静态存储类别的数据和变量;的,主要是具有静态存储类别的数据和变量;的,主要是具有静态存储类别的数据和变量;的,主要是具有静态存储类别的数据和变量;接着是目标代码运行时用到的库程序代码区;接着是目标代码运行时用到的库程序代码区;接着是目标代码运行时用到的库程序代码区;接着是目标代码运行时用
13、到的库程序代码区;最后剩余空间是栈区和堆区,栈区和堆区从剩最后剩余空间是栈区和堆区,栈区和堆区从剩最后剩余空间是栈区和堆区,栈区和堆区从剩最后剩余空间是栈区和堆区,栈区和堆区从剩余空间的两端,动态的向中间增长。栈区用来余空间的两端,动态的向中间增长。栈区用来余空间的两端,动态的向中间增长。栈区用来余空间的两端,动态的向中间增长。栈区用来存储程序中声明的函数的局部变量等具有自动存储程序中声明的函数的局部变量等具有自动存储程序中声明的函数的局部变量等具有自动存储程序中声明的函数的局部变量等具有自动存储类别的数据和变量;堆区用来存储经过动存储类别的数据和变量;堆区用来存储经过动存储类别的数据和变量;
14、堆区用来存储经过动存储类别的数据和变量;堆区用来存储经过动态申请空间函数申请的变量。态申请空间函数申请的变量。态申请空间函数申请的变量。态申请空间函数申请的变量。n nsizeof sizeof 运算符运算符运算符运算符单目运算符单目运算符单目运算符单目运算符 sizeof sizeof 的的的的操作数操作数操作数操作数是类型。是类型。是类型。是类型。运算结果运算结果运算结果运算结果是求得相应类型的尺寸,即存储相是求得相应类型的尺寸,即存储相是求得相应类型的尺寸,即存储相是求得相应类型的尺寸,即存储相应类型数据所需要的字节数。应类型数据所需要的字节数。应类型数据所需要的字节数。应类型数据所需要
15、的字节数。sizeof(int)/*sizeof(int)/*结果是结果是结果是结果是2*/2*/sizeof(char)/*sizeof(char)/*结果是结果是结果是结果是1*/1*/sizeof(struct date)/*sizeof(struct date)/*若若若若 struct date struct date 是第十是第十是第十是第十一章定义的日期类型,结果是一章定义的日期类型,结果是一章定义的日期类型,结果是一章定义的日期类型,结果是6*/6*/n nmalloc malloc 函数函数函数函数:原型原型原型原型 void*malloc(unsigned long siz
16、e);void*malloc(unsigned long size);功能功能功能功能 申请足够大内存区域用来存储长度为申请足够大内存区域用来存储长度为申请足够大内存区域用来存储长度为申请足够大内存区域用来存储长度为sizesize的数据对象,返回该区域的首指针,并保证该的数据对象,返回该区域的首指针,并保证该的数据对象,返回该区域的首指针,并保证该的数据对象,返回该区域的首指针,并保证该区域符合任何数据类型对存储区域开始地址和区域符合任何数据类型对存储区域开始地址和区域符合任何数据类型对存储区域开始地址和区域符合任何数据类型对存储区域开始地址和对齐的要求。对齐的要求。对齐的要求。对齐的要求。
17、返回指针是返回指针是返回指针是返回指针是voidvoid类型的,调用者必须使用类型的,调用者必须使用类型的,调用者必须使用类型的,调用者必须使用显示强制类型转换,把该指针转换成所需要类显示强制类型转换,把该指针转换成所需要类显示强制类型转换,把该指针转换成所需要类显示强制类型转换,把该指针转换成所需要类型的指针。型的指针。型的指针。型的指针。n n例例例例:float*p;float*p;p=(float*)malloc(sizeof(float);p=(float*)malloc(sizeof(float);struct date*pdate;struct date*pdate;pdate=
18、(struct date*)malloc(sizeof(struct pdate=(struct date*)malloc(sizeof(struct date);date);n nfree函数函数动态申请的内存如果不再使用,应当适时释放动态申请的内存如果不再使用,应当适时释放动态申请的内存如果不再使用,应当适时释放动态申请的内存如果不再使用,应当适时释放这样可以提高程序运行效率。这样可以提高程序运行效率。这样可以提高程序运行效率。这样可以提高程序运行效率。freefree函数用来释函数用来释函数用来释函数用来释放经过放经过放经过放经过mallocmalloc申请的动态空间。申请的动态空间。申
19、请的动态空间。申请的动态空间。freefree的函数的函数的函数的函数原型原型原型原型 void free(void*ptr);void free(void*ptr);功能功能功能功能释放由释放由释放由释放由mallocmalloc申请的内存区域。申请的内存区域。申请的内存区域。申请的内存区域。freefree的参数的参数的参数的参数ptrptr是一个指针,指向以前由是一个指针,指向以前由是一个指针,指向以前由是一个指针,指向以前由mallocmalloc申请的一申请的一申请的一申请的一个内存区域。个内存区域。个内存区域。个内存区域。n n例例申请申请申请申请float*p;float*p;p
20、=(float*)malloc(sizeof(float);p=(float*)malloc(sizeof(float);struct date*pdate;struct date*pdate;pdate=(struct date*)malloc(sizeof(struct date);pdate=(struct date*)malloc(sizeof(struct date);释放释放释放释放free(p);free(p);free(pdate);free(pdate);free(ptr)free(ptr)/*/*释放释放释放释放ptrptr所指向由所指向由所指向由所指向由mallocmal
21、loc申请的内存空间申请的内存空间申请的内存空间申请的内存空间*/*/一块存储区域一经释放,便不能再使用。使用一块存储区域一经释放,便不能再使用。使用一块存储区域一经释放,便不能再使用。使用一块存储区域一经释放,便不能再使用。使用freefree特特特特别注意,操作不当会产生不可预料的结果。如下情况别注意,操作不当会产生不可预料的结果。如下情况别注意,操作不当会产生不可预料的结果。如下情况别注意,操作不当会产生不可预料的结果。如下情况下使用下使用下使用下使用freefree都会造成灾难性后果。都会造成灾难性后果。都会造成灾难性后果。都会造成灾难性后果。ptrptr无值;无值;无值;无值;ptr
22、ptr的值为的值为的值为的值为NULLNULL;ptrptr所指向的空间不是经过所指向的空间不是经过所指向的空间不是经过所指向的空间不是经过mallocmalloc申请来的;申请来的;申请来的;申请来的;对一次申请的存储区进行多次释放(实际可能是对一次申请的存储区进行多次释放(实际可能是对一次申请的存储区进行多次释放(实际可能是对一次申请的存储区进行多次释放(实际可能是ptrptr无值或值为无值或值为无值或值为无值或值为NULLNULL)。)。)。)。n n实用问题实用问题实用问题实用问题:若指针变量指向的用若指针变量指向的用若指针变量指向的用若指针变量指向的用mallocmalloc申请来的
23、动态变量,是孤申请来的动态变量,是孤申请来的动态变量,是孤申请来的动态变量,是孤立的不能与其它变量相联系,显然作用不大。立的不能与其它变量相联系,显然作用不大。立的不能与其它变量相联系,显然作用不大。立的不能与其它变量相联系,显然作用不大。引进动态变量的目的是构造动态数据结构。引进动态变量的目的是构造动态数据结构。引进动态变量的目的是构造动态数据结构。引进动态变量的目的是构造动态数据结构。例如象本章开始介绍的那样,构造一个链表等。例如象本章开始介绍的那样,构造一个链表等。例如象本章开始介绍的那样,构造一个链表等。例如象本章开始介绍的那样,构造一个链表等。这就要求一个数据项上除基本的数据信息外,
24、还应包这就要求一个数据项上除基本的数据信息外,还应包这就要求一个数据项上除基本的数据信息外,还应包这就要求一个数据项上除基本的数据信息外,还应包含与其它数据项相联系的信息,也就是包含指针。含与其它数据项相联系的信息,也就是包含指针。含与其它数据项相联系的信息,也就是包含指针。含与其它数据项相联系的信息,也就是包含指针。该结构必须用结构体类型描述,链表上一节的类型定该结构必须用结构体类型描述,链表上一节的类型定该结构必须用结构体类型描述,链表上一节的类型定该结构必须用结构体类型描述,链表上一节的类型定义形式。义形式。义形式。义形式。类型定义形式类型定义形式 struct t 基本数据部分;基本数
25、据部分;struct t *next;基本数基本数据部分据部分指针部分指针部分一个数据项一个数据项 1 12 23 3 n n.栈栈 stackn n在第六章已经用数组实现过栈和队列,但是,数在第六章已经用数组实现过栈和队列,但是,数在第六章已经用数组实现过栈和队列,但是,数在第六章已经用数组实现过栈和队列,但是,数组有一定的局限性。如图可以用单向链表实现栈,组有一定的局限性。如图可以用单向链表实现栈,组有一定的局限性。如图可以用单向链表实现栈,组有一定的局限性。如图可以用单向链表实现栈,指针变量指针变量指针变量指针变量toptop指向栈顶。栈的操作有指向栈顶。栈的操作有指向栈顶。栈的操作有指
26、向栈顶。栈的操作有:初始化:初始化:初始化:初始化:stackintialstackintial 压栈:压栈:压栈:压栈:stackpushstackpush 弹栈:弹栈:弹栈:弹栈:stackpopstackpop设有声明设有声明设有声明设有声明:typedef .items;typedef .items;typedef struct stackcell typedef struct stackcell items data ;items data ;struct stackcell *predocessorstruct stackcell *predocessor;stackcelltyp
27、e;stackcelltype;typedef stackcelltype *pstacktype;typedef stackcelltype *pstacktype;pstacktype top;pstacktype top;top:.栈栈如下实现栈的操作:如下实现栈的操作:如下实现栈的操作:如下实现栈的操作:void stackinitial(void)void stackinitial(void)top=NULL;top=NULL;void stackpush(items x)void stackpush(items x)pstacktype p;pstacktype p;p=(psta
28、cktype)malloc(sizeof(stackcelltype);p=(pstacktype)malloc(sizeof(stackcelltype);p-data =x;p-data =x;p-prodocessor =top;p-prodocessor =top;top =p;top =p;void stackpop(items*x)void stackpop(items*x)pstacktype p;pstacktype p;if(top if(top!=!=NULL)NULL)*x =top-data;*x =top-data;p =top;p =top;top =top-pre
29、decessor;top =top-predecessor;free(p);free(p);else printf(“else printf(“栈下溢栈下溢栈下溢栈下溢n”);n”);看一下这三个操作看一下这三个操作看一下这三个操作看一下这三个操作:1.1.初始化后初始化后初始化后初始化后(调用调用调用调用stackinitailstackinitail)得。得。得。得。2.2.调用一次调用一次调用一次调用一次 stackpush(1)stackpush(1)得。得。得。得。3.3.再调用一次再调用一次再调用一次再调用一次stackpush(2)stackpush(2)得得得得 。4.4.调用
30、一次调用一次调用一次调用一次stackpop(&bstackpop(&b)得得得得 。top:1.2b:2队列队列n n如图可用单向链表实现队列,现在要用两个指针变量,一如图可用单向链表实现队列,现在要用两个指针变量,一如图可用单向链表实现队列,现在要用两个指针变量,一如图可用单向链表实现队列,现在要用两个指针变量,一个指向队头(个指向队头(个指向队头(个指向队头(frontfront),一个指向队尾(),一个指向队尾(),一个指向队尾(),一个指向队尾(rearrear)。队列的操)。队列的操)。队列的操)。队列的操作有作有作有作有 初始化(初始化(初始化(初始化(queueinitial
31、queueinitial)进队进队进队进队排在队尾(排在队尾(排在队尾(排在队尾(inqueueinqueue)出队出队出队出队从队头删一项(从队头删一项(从队头删一项(从队头删一项(outqueueoutqueue)rear:front:.设有如下说明设有如下说明设有如下说明设有如下说明:typedef .items;typedef .items;typedef struct queue typedef struct queue items data items data struct queue *next;struct queue *next;queuetype;queuetype;ty
32、pedef queuetype *pqueuetype;typedef queuetype *pqueuetype;pqueuetype front,rear;pqueuetype front,rear;操作:操作:操作:操作:void queueinital(void)void queueinital(void)front =NULL;front =NULL;rear =NULL;rear =NULL;void inqueue(item x)void inqueue(item x)pqueuetype p;pqueuetype p;p=(pqueuetype)malloc(sizeof(qu
33、euetype);p=(pqueuetype)malloc(sizeof(queuetype);p-data =x;p-data =x;p-next =NULL;p-next =NULL;if(rear=NULL)if(rear=NULL)rear =p;rear =p;front =p;front =p;else else rear-next =p;rear-next =p;rear =p;rear =p;void outgueue(item*x)void outgueue(item*x)pqueuetype p;pqueuetype p;if(front=NULL)if(front=NUL
34、L)printf(“printf(“队空队空队空队空n”);n”);else else *x =front-data;*x =front-data;p =front;p =front;front =front-next;front =front-next;if(front=NULL)if(front=NULL)rear =NULL;rear =NULL;free(p);free(p);看一下这三个操作看一下这三个操作看一下这三个操作看一下这三个操作:1.1.调用初始化后(调用一次调用初始化后(调用一次调用初始化后(调用一次调用初始化后(调用一次 queueinitail queueinitai
35、l)得;得;得;得;2.2.调用一次调用一次调用一次调用一次ingueue(1)ingueue(1)得;得;得;得;再调用一次再调用一次再调用一次再调用一次ingueue(2)ingueue(2)得;得;得;得;再调用一次再调用一次再调用一次再调用一次 ingueue(3)ingueue(3)得得得得;3.3.调用一次调用一次调用一次调用一次 outgueue(&a)outgueue(&a)得;得;得;得;再调用一次再调用一次再调用一次再调用一次 outgueue(&b)outgueue(&b)得得得得;再调用一次再调用一次再调用一次再调用一次 outgueue(&a)outgueue(&a)
36、得得得得 。1a:rear:front:231 p:b:23NULLNULL链表链表linkage tablebase:1.2N-1N.双向链双向链base:12N-1N.单向链单向链base:12N-1N.环形链环形链base:12N-1N.双向双向环形链环形链 实际上前边讲的栈,队列都是单向链表,但是栈和实际上前边讲的栈,队列都是单向链表,但是栈和实际上前边讲的栈,队列都是单向链表,但是栈和实际上前边讲的栈,队列都是单向链表,但是栈和队列只是单向链表的两种特殊应用队列只是单向链表的两种特殊应用队列只是单向链表的两种特殊应用队列只是单向链表的两种特殊应用操作只在头操作只在头操作只在头操作只在
37、头尾进行。下边介绍单向链表的一般操作尾进行。下边介绍单向链表的一般操作尾进行。下边介绍单向链表的一般操作尾进行。下边介绍单向链表的一般操作:n n创建单向链表创建单向链表创建单向链表创建单向链表:创建单向链表,是指用一项一项的数据逐步建创建单向链表,是指用一项一项的数据逐步建创建单向链表,是指用一项一项的数据逐步建创建单向链表,是指用一项一项的数据逐步建立、形成一个链表。可以分成向链头加入数据和向立、形成一个链表。可以分成向链头加入数据和向立、形成一个链表。可以分成向链头加入数据和向立、形成一个链表。可以分成向链头加入数据和向链尾加入数据两种方式。链尾加入数据两种方式。链尾加入数据两种方式。链
38、尾加入数据两种方式。创建单向链表可以分成向链头加入数据和向链创建单向链表可以分成向链头加入数据和向链创建单向链表可以分成向链头加入数据和向链创建单向链表可以分成向链头加入数据和向链尾加入数据两种方式。新项加入链头就是压栈的算尾加入数据两种方式。新项加入链头就是压栈的算尾加入数据两种方式。新项加入链头就是压栈的算尾加入数据两种方式。新项加入链头就是压栈的算法;新项加入链尾就是队列中入队的算法。只要反法;新项加入链尾就是队列中入队的算法。只要反法;新项加入链尾就是队列中入队的算法。只要反法;新项加入链尾就是队列中入队的算法。只要反复调用那里的函数或将函数体放在循环语句中即可,复调用那里的函数或将函
39、数体放在循环语句中即可,复调用那里的函数或将函数体放在循环语句中即可,复调用那里的函数或将函数体放在循环语句中即可,这里不赘述。这里不赘述。这里不赘述。这里不赘述。n n遍历单向链表遍历单向链表遍历单向链表遍历单向链表:遍历是指从头到尾将链表上数据全部加工一遍历是指从头到尾将链表上数据全部加工一遍历是指从头到尾将链表上数据全部加工一遍历是指从头到尾将链表上数据全部加工一遍。可用如下左端的算法。但实用中,经常用如遍。可用如下左端的算法。但实用中,经常用如遍。可用如下左端的算法。但实用中,经常用如遍。可用如下左端的算法。但实用中,经常用如下右端下右端下右端下右端 的算法来遍历单向链表。的算法来遍历
40、单向链表。的算法来遍历单向链表。的算法来遍历单向链表。p =base;p0=NULL;while(p!=NULL)p =base;加工加工 p-while(p!=NULL)p =p-next;加工加工 p-p0 =p;p =p-next;n n在单向链表上检索在单向链表上检索在单向链表上检索在单向链表上检索:检索是指在单向链表上查找关键字等于某给定检索是指在单向链表上查找关键字等于某给定检索是指在单向链表上查找关键字等于某给定检索是指在单向链表上查找关键字等于某给定值的节点值的节点值的节点值的节点,若找到则带回相应节点的指针;否则带若找到则带回相应节点的指针;否则带若找到则带回相应节点的指针;
41、否则带若找到则带回相应节点的指针;否则带回回回回NULL NULL。设关键字域域名为。设关键字域域名为。设关键字域域名为。设关键字域域名为key key;欲检索的关键;欲检索的关键;欲检索的关键;欲检索的关键字值为字值为字值为字值为key0.key0.如下算法实现检索:如下算法实现检索:如下算法实现检索:如下算法实现检索:p0=NULL;p0=NULL;p =base;p =base;while(p!=NULL&p-key!=key0)while(p!=NULL&p-key!=key0)p0=p;p0=p;p =p-next;p =p-next;n n向单向链表插入一项向单向链表插入一项向单向
42、链表插入一项向单向链表插入一项:设有下图的链表,现在要把设有下图的链表,现在要把设有下图的链表,现在要把设有下图的链表,现在要把r r所指示的数据项插所指示的数据项插所指示的数据项插所指示的数据项插入到入到入到入到 p0 p0、p p 所指两项之间。操作是所指两项之间。操作是所指两项之间。操作是所指两项之间。操作是:r-next =p;r-next =p;p0-next =r;p0-next =r;p0 =r /*p0 =r /*使使使使 p0 p0 仍为仍为仍为仍为 p p 的前一项的前一项的前一项的前一项*/*/r:5p0:p:1 2 3 4.n n从单向链表上删除一项从单向链表上删除一项
43、从单向链表上删除一项从单向链表上删除一项:设有下图的链表,现在要删除设有下图的链表,现在要删除设有下图的链表,现在要删除设有下图的链表,现在要删除p p所指项。删除所指项。删除所指项。删除所指项。删除算法是:算法是:算法是:算法是:q=p;q=p;p =p-next;p =p-next;p0-next =p;p0-next =p;free(q)free(q)p0:1234.p:q:n n交换单向链表上两项交换单向链表上两项:设有如图所示链表。现在要把设有如图所示链表。现在要把设有如图所示链表。现在要把设有如图所示链表。现在要把 p p 所指的项与所指的项与所指的项与所指的项与 q q 所指所指
44、所指所指的项交换的项交换的项交换的项交换 为了表示操作方便,我们把该链表分两段画出。为了表示操作方便,我们把该链表分两段画出。为了表示操作方便,我们把该链表分两段画出。为了表示操作方便,我们把该链表分两段画出。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-n
45、ext;/*7*/树树treen n两叉树,两叉树的每个数据项附带两个指针,分两叉树,两叉树的每个数据项附带两个指针,分两叉树,两叉树的每个数据项附带两个指针,分两叉树,两叉树的每个数据项附带两个指针,分别指向它的两个分支。两叉树的定义别指向它的两个分支。两叉树的定义别指向它的两个分支。两叉树的定义别指向它的两个分支。两叉树的定义:空是树;空是树;空是树;空是树;一个结点连接两个不相交的树一个结点连接两个不相交的树一个结点连接两个不相交的树一个结点连接两个不相交的树,仍为树;仍为树;仍为树;仍为树;所有结点具有相同的数据类型。所有结点具有相同的数据类型。所有结点具有相同的数据类型。所有结点具有
46、相同的数据类型。*+-a/d*bcef(a+b/c)*(d e*f)root:设设 ti 为二叉树的一个结点,一般为二叉树的一个结点,一般 ti 由两部分组成:由两部分组成:l基本数据部分基本数据部分-保存本结点上的基本数据;保存本结点上的基本数据;l指针部分连指针部分连-接本结点以下的其它结点。接本结点以下的其它结点。结点结点 ti 的指针连接的结点称为的指针连接的结点称为 ti 的的子结点子结点,相应相应 ti 称为其子结点的称为其子结点的父结点父结点。ti的指针部分有两个指针:左指针、右指针。的指针部分有两个指针:左指针、右指针。称称 ti 的左指针连接的部分为的左指针连接的部分为 ti
47、 的的左子树左子树,ti 的右指针连接的部分为的右指针连接的部分为 ti 的的右子树右子树。若左、右子树均空,则称若左、右子树均空,则称 ti 为为叶结点叶结点。ti78563124ti:n n为了检索操作方便,一般把两叉树组织成两叉检索为了检索操作方便,一般把两叉树组织成两叉检索为了检索操作方便,一般把两叉树组织成两叉检索为了检索操作方便,一般把两叉树组织成两叉检索树。两叉检索树的定义是:树。两叉检索树的定义是:树。两叉检索树的定义是:树。两叉检索树的定义是:设树中每个结点的数据部分有一个数据项设树中每个结点的数据部分有一个数据项设树中每个结点的数据部分有一个数据项设树中每个结点的数据部分有
48、一个数据项 key key 是有序的是有序的是有序的是有序的,称该数据项为关键字。称该数据项为关键字。称该数据项为关键字。称该数据项为关键字。一个两叉树称为检索树,一个两叉树称为检索树,一个两叉树称为检索树,一个两叉树称为检索树,如果对每个结点如果对每个结点如果对每个结点如果对每个结点 ti ti,它的左子树中所有结点的,它的左子树中所有结点的,它的左子树中所有结点的,它的左子树中所有结点的 key key 值都小于值都小于值都小于值都小于 ti ti 的的的的 key key 值;值;值;值;ti ti 的右子树中所有结点的的右子树中所有结点的的右子树中所有结点的的右子树中所有结点的 key
49、 key 值都大于值都大于值都大于值都大于 ti ti 的的的的 key key 值。值。值。值。n n二叉检索树的操作有二叉检索树的操作有二叉检索树的操作有二叉检索树的操作有:遍历遍历遍历遍历检索检索检索检索插入一个结点插入一个结点插入一个结点插入一个结点删除一个结点删除一个结点删除一个结点删除一个结点 由于树是递归定义的,所以树的操作用递归算由于树是递归定义的,所以树的操作用递归算由于树是递归定义的,所以树的操作用递归算由于树是递归定义的,所以树的操作用递归算法十分简洁。法十分简洁。法十分简洁。法十分简洁。设有说明部分设有说明部分设有说明部分设有说明部分:typedef .keytype
50、typedef .keytype;typedef .datatype typedef .datatype;typedef struct tree typedef struct tree keytype key keytype key;datatype data datatype data;struct tree *left struct tree *left;struct tree *right struct tree *right;treetype;treetype;typedef treetype *treepointer typedef treetype *treepointer;tre