还剩45页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《数据结构与算法》实验指导书大连民族学院信息与通信工程学院2013年10月10日基本要求
1.学生必须按时到实验室做实验,不得迟到早退,未经老师批准不得中途离开凡迟到者,应给予批评并作适当扣分实验课迟到20分钟以上及无故缺席者视为旷课,旷课者不予补做实验,本次实验以零分计学生因病或特殊情况不能按时到实验室做实验时,应__正常请假手续请病假必须有医生签字的病假条,请事假必须有班主任签字的事假条不符合请假手续的,以旷课论处请假的学生由指导教师安排补做实验对于未做实验数达三分之一以上(含三分之一)的学生,实验课程按0分计
2.学生在每次实验课之前,应仔细阅读实验教材,查阅相关的资料,写出预习报告预习报告的具体内容包括实验内容、实验目的、实验原理图、实验步骤、实验数据记录表格等实验课前由任课教师检查预习报告,未写预习报告者不予做实验
3.做实验前,了解设备的原理和正确使用方法在没有弄懂仪器设备的使用方法前,不得贸然使用,否则因使用不当造成仪器设备损坏的,根据大连民族学院《仪器设备损坏丢失处理暂行办法》规定进行处理实验室内设备在实验过程中不准任意搬动和调换,非本次实验所用仪器设备,未经指导教师允许不得动用
4.要求每位学生在实验过程中,要具有严谨的学习态度、认真、踏实、一丝不苟的科学作风实验过程中学生按照预习的内容进行实验,且重视实验的调试过程,学会如何根据实验现象判断问题所在坚持每次实验都要亲自动手,不可“坐车”,每个实验每个学生都要__完成,不允许抄袭,无特殊原因,中途不得退出实验,否则本次实验无效
5.实验中若接线、改接、拆线都必须在切断电源的情况下进行,线路连接完毕再送电实验中,特别是设备刚投入运行时,要随时注意仪器设备的运行情况,如发现有过热、异味、冒烟、火花等,应立即断电,并请指导老师检查、处理
6.实验过程中,如出现事故,就马上拉开电源开关,然后找指导教师和实验技术人员,如实反映事故情况,并分析原因和处理事故如有损坏仪表和设备时,应马上提出,按有关规定处理
7.每次实验结束,指导教师要对实验数据和结果进行检查,并签字,在教师确认正确无误后,学生方可拆线整理好实验台和周围卫生,填写实验登记簿后方可离开
8.每次实验后学生必须写出符合要求的实验报告,缺交者本次实验以零分计实验报告要求字迹工整、原始数据齐全、图表清晰、程序正确实验报告必须附有指导教师签字的原始数据表或预习报告,否则该实验报告无效为满足上述要求的按其程度扣除一定分值
(1)pubuse.h是几乎所有实验中都涉及到的,包含了一些常量定义,系统函数原型声明和类型(Status)重定义结果状态代码等在本文中的内容对某一个实验可能没有完全用到,但对本课程的其他实验可能有用;
(2)数据结构定义以____Def.h为文件名;
(3)基本操作和算法以____Algo.h为文件名;
(4)调用基本操作的主程序以_____Use.cpp为文件名实验一线性表的结构定义及基本操作(必做,2学时)
一、实验目的.掌握线性表的逻辑特征.掌握线性表顺序存储结构的特点,熟练掌握顺序表的基本运算.熟练掌握线性表的链式存储结构定义及基本操作.加深对顺序存储数据结构的理解和链式存储数据结构的理解,逐步培养解决实际问题的编程能力
二、实验内容
(一)基本实验内容(顺序表)建立顺序表,完成顺序表的基本操作初始化、插入、删除、销毁、置空表、求表长、查找元素、判线性表是否为空;1.问题描述利用顺序表设计一组输入数据(假定为一组整数),能够对顺序表进行如下操作.创建一个新的顺序表,实现动态空间分配的初始化;.根据顺序表结点的位置插入一个新结点位置插入,也可以根据给定的值进行插入值插入,形成有序顺序表;.根据顺序表结点的位置删除一个结点位置删除;.彻底销毁顺序线性表,回收所分配的空间;.对顺序线性表的所有元素删除,置为空表;.返回顺序线性表数据元素个数;.按序号查找,根据顺序表的特点,可以随机存取,直接可以定位于第i个结点,查找该元素的值,对查找结果进行返回;.按值查找,根据给定数据元素的值,只能顺序比较,查找该元素的位置,对查找结果进行返回;.判断顺序表中是否为空表,对判断结果进行返回;.编写主程序,实现对各不同的算法调用2.实现要求对顺序表的各项操作一定要编写成为C(C++)语言函数,组合成模块化的形式,每个算法的实现要从时间复杂度和空间复杂度上进行评价;.“初始化算法”的操作结果构造一个空的顺序线性表对顺序表的空间进行动态管理,实现动态分配、回收和增加存储空间;.“位置插入算法”的初始条件顺序线性表L已存在,给定的元素位置为i,且1≤i≤ListLengthL+1;操作结果在L中第i个位置之前插入新的数据元素e,L的长度加1;.“位置删除算法”的初始条件顺序线性表L已存在,1≤i≤ListLengthL;操作结果删除L的第i个数据元素,并用e返回其值,L的长度减1;.“销毁算法”初始条件顺序线性表L已存在;操作结果销毁顺序线性表L;.“置空表算法”初始条件顺序线性表L已存在;操作结果将L重置为空表;.“求表长算法”初始条件顺序线性表L已存在;操作结果返回L中数据元素个数;.“按序号查找算法”初始条件顺序线性表L已存在,元素位置为i,且1≤i≤ListLengthL操作结果返回L中第i个数据元素的值;.“按值查找算法”初始条件顺序线性表L已存在,元素值为e;操作结果返回L中数据元素值为e的元素位置;.“判表空算法”初始条件顺序线性表L已存在;操作结果若L为空表,则返回TRUE,否则返回FALSE;分析:修改输入数据,预期输出并验证输出的结果,加深对有关算法的理解二)基本实验内容(链表)建立单链表,完成链表(带表头结点)的基本操作建立链表、插入、删除和输出操作1.问题描述利用线性表的链式存储结构设计一组输入数据(假定为一组整数),能够对单链表进行如下操作.初始化一个带表头结点的空链表;.创建一个单链表是从无到有地建立起一个链表,即一个一个地输入各结点数据,并建立起前后相互链接的关系.插入结点根据给定位置进行插入(位置插入).删除结点根据给定位置进行删除(位置删除).输出单链表的内容是将链表中各结点的数据依次显示,直到链表尾结点.编写主程序,实现对各不同的算法调用其它的操作算法描述略2.实现要求对链表的各项操作一定要编写成为C(C++)语言函数,组合成模块化的形式,还要针对每个算法的实现从时间复杂度和空间复杂度上进行评价.“初始化算法”的操作结果构造一个空的线性表L,产生头结点并使L指向此头结点;.“建立链表算法”初始条件空链存在;操作结果选择逆位序或正位序的方法,建立一个单链表,并且返回完成的结果;.“链表(位置)插入算法”初始条件已知单链表L存在;操作结果在带头结点的单链线性表L中第i个位置之前插入元素e;.“链表(位置)删除算法”初始条件已知单链表L存在;操作结果在带头结点的单链线性表L中,删除第i个元素并由e返回其值;.“输出算法”初始条件链表L已存在;操作结果依次输出链表的各个结点的值;
三、实验指导一个简单程序通常主要由三部分构成
1、常量定义(#define),类型重定义typedef及函数原型#include声明;还有针对每一种数据结构的类型定义,由于本实验是要求实现对线性表的顺序存储和链式存储两种存储结构的定义,因此不同的物理存储结构的定义和其基本操作最好是以__的文件存在,因此本实验将顺序表和链表可分解为两个不同的实验部分
2、算法函数,对于顺序表,每一个函数具有__的功能,组合成为模块的形式,如ListInit_Sq、ListInsert_Sq、ListDelete_Sq、ListReverse_Sq、ListPrint_Sq等;对于链表,每一个函数具有__的功能,组合成为模块的形式,如ListInit_Link、ListInsert_Link、ListDelete_Link等
3、主函数(__in)【说明1】――顺序表的定义与操作1.可以将这三部分组合在一个文件中,也可以按照项目的方式(多个不同的文件组合在一起,共同完成一个功能)进行组织(本课程的实验强烈推荐这种形式),如将本课程后续所有算法几乎都要使用的常量定义(#define)和系统函数原型定义#include声明组合成一个文件,存储为一个头文件(取名为pubuse.h),只需建立一次,以后凡涉及到相关的内容,只需在你的文件的前面加上一条#include“pubuse.h”即可,无需重复输入2.对于类型定义,由于每一种数据结构的定义都不一样,因此要进行专门的类型定义,也可以将数据结构的定义组合成为一个文件,存储为一个头文件(如线性表的顺序存储结构定义取名为seqlistDef.h),只需建立一次,以后凡涉及到关于顺序表操作的相关内容,一定要在你的文件的前面加上一条#include“seqlistDef.h”即可,无需重复进行顺序存储结构的定义3.关于实验内容要完成的操作,一般都以__的算法出现,关于某类数据结构的各种不同算法函数组合在一个文件之中,存储为一个头文件(如取名为seqlistAlgo.h),以后凡涉及到要使用本文件中的顺序表算法,一定要在你的文件的前面加上一条#include“seqlistAlgo.h”即可,无需重复定义类似的算法,就象使用系统函数一样,只需进行函数原型的声明即可4.还应包含一个__in函数,作为整个程序的执行入口处,定义测试的数据,完成各种算法的调用执行,对算法的执行过程和结果进行判断和输出控制,存储为一个源文件(如取名为seqlistUse.cpp)5.为了对实际问题更加通用和适应,在算法中使用的数据类型为ElemType,为了与实际数据类型一致,一般要将ElemType用typedef重定义如实际问题中顺序表的每个元素是整型,则使用typedefintElemType;定义语句;如实际问题中顺序表的每个元素是单精度实数的话,使用typedeffloatElemType;定义语句【说明2】――链表的定义与操作1.根据一个完整的C语言组成,将实验内容组合成如上所述的三个组成部分,功能清晰明了,其常量定义和常用系统函数原型声明的文件“pubuse.h”代码复用,不需另行建立2.建立一个单链表类型定义的头文件,如取名为linklistDef.h,以后凡使用该文件定义的类型,就只需使用包含语句#include“linklistDef.h”即可3.关于实验内容要完成的操作,一般都以__的算法出现,建立一个单链表的基本算法文件将各种不同算法组合在一个文件之中,存储为一个头文件如取名为linklistAlgo.h,后凡涉及到要使用本文件中的单链表算法,一定要在你的文件的前面加上一条#include“linklistAlgo.h”即可,实现的算法函数,如ListInit_Link、ListInsert_Link、ListDelete_Link、等;4.还应包含一个__in函数,作为整个程序的执行入口处,定义测试的数据,完成各种算法的调用执行,对算法的执行过程和结果进行判断和输出控制,存储为一个源文件(如取名为linklistUse.cpp)
四、基本实验的参考程序
(一)线性表的顺序存储结构的定义及其基本操作的参考程序(顺序表)1文件1pubuse.h是公共使用的常量定义和系统函数调用声明,以后每个实验中几乎都涉及到此文件#includestring.h#includectype.h#include__lloc.h/*__lloc等*/#includelimits.h/*INT___X等*/#includestdio.h/*EOF=^Z或F6NULL*/#includestdlib.h/*atoi*/#includeio.h/*eof*/#include__th.h/*floor__ilabs*/#includepro__ss.h/*exit*//*函数结果状态代码*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/*#defineOVERFLOW-2因为在__th.h中已定义OVERFLOW的值为3故去掉此行*/typedefintStatus;/*Status是函数的类型其值是函数结果状态代码,如OK等*/typedefintBoolean;/*Boolean是布尔类型其值是TRUE或FALSE*/2文件2seqlistDef.h进行线性表的动态分配顺序存储结构的表示#defineLIST_INIT_SIZE10/*线性表存储空间的初始分配量*/#defineLISTINCREMENT2/*线性表存储空间的分配增量*/typedefstruct{ElemType*elem;/*存储空间基址*/intlength;/*当前长度*/intlistsize;/*当前分配的存储容量以sizeofElemType为单位*/}SqList;3文件3seqlistAlgo.h进行线性表顺序存储结构的基本实验算法定义StatusListInit_SqSqListL/*算法
2.3*/{/*操作结果构造一个空的顺序线性表*/L.elem=ElemType*__llocLIST_INIT_SIZE*sizeofElemType;if!L.elemexitOVERFLOW;/*存储分配失败*/L.length=0;/*空表长度为0*/L.listsize=LIST_INIT_SIZE;/*初始存储容量*/returnOK;}StatusListInsert_SqSqListLintiElemTypee/*算法
2.4*/{/*初始条件顺序线性表L已存在,1≤i≤ListLengthL+1*//*操作结果在L中第i个位置之前插入新的数据元素e,L的长度加1*/ElemType*newbase*q*p;ifi1||iL.length+1/*i值不合法*/returnERROR;ifL.length=L.listsize/*当前存储空间已满增加分配*/{newbase=ElemType*reallocL.elemL.listsize+LISTINCREMENT*sizeofElemType;if!newbaseexitOVERFLOW;/*存储分配失败*/L.elem=newbase;/*新基址*/L.listsize+=LISTINCREMENT;/*增加存储容量*/}q=L.elem+i-1;/*q为插入位置*/forp=L.elem+L.length-1;p=q;--p/*插入位置及之后的元素右移*/*p+1=*p;*q=e;/*插入e*/++L.length;/*表长增1*/returnOK;}StatusListDelete_SqSqListLintiElemType*e/*算法
2.5*/{/*初始条件顺序线性表L已存在,1≤i≤ListLengthL*//*操作结果删除L的第i个数据元素,并用e返回其值,L的长度减1*/ElemType*p*q;ifi1||iL.length/*i值不合法*/returnERROR;p=L.elem+i-1;/*p为被删除元素的位置*/*e=*p;/*被删除元素的值赋给e*/q=L.elem+L.length-1;/*表尾元素的位置*/for++p;p=q;++p/*被删除元素之后的元素左移*/*p-1=*p;L.length--;/*表长减1*/returnOK;}StatusListPrint_SqSqListL{/*初始条件顺序线性表L已存在*//*操作结果依次对L的数据元素输出*/inti;printf\n;fori=0;iL.length;i++printf%dL.elem[i];returnOK;}/*StatusListDestroy_SqSqListL{/*初始条件顺序线性表L已存在*//*操作结果销毁顺序线性表L*//*FreeL.elem;L.elem=NULL;L.length=0;L.listsize=0;returnOK;}*/StatusListClear_SqSqListL{/*初始条件顺序线性表L已存在*//*操作结果将顺序线性表L重置为空表*/L.length=0;returnOK;}StatusListEmpty_SqSqListL{/*初始条件顺序线性表L已存在*//*操作结果若顺序线性表L为空表,则返回TRUE否则返回FALSE*/ifL.length==0returnTRUE;//else//returnFALSE;}StatusListGetElem_SqSqListLintiElemTypee{/*初始条件顺序线性表L已存在1≤i≤ListLengthL*//*操作结果用e返回L中第i个数据元素的值*/ifi1||iL.length/*i值不合法*/exitERROR;e=*L.elem+i-1;returnOK;}/*还有一些算法,请同学们自己补充完整*/4文件4seqlistUse.cpp进行线性表顺序存储结构的基本算法验证#includepubuse.h/*实现通用常量的定义,常用系统函数的声明*/typedefintElemType;/*实现一组整数的操作将int型特定义为通用的ElemType类型名*/#includeseqlistDef.h/*采用线性表的动态分配顺序存储结构定义*/#includeseqlistAlgo.h/*采用顺序表的基本算法定义*/void__in{SqListL;Statusi;intj;intnum;ElemTypet;/*首先一定要初始化顺序表*/i=ListInit_SqL;ifiprintf成功地构造了一个空顺序表!\n;printf请输入顺序表的长度j=;scanf%dj;printf请输入顺序表的元素以空格为间隔;intm=j;forj=1;j=m;j++{scanf%dnum;i=ListInsert_SqLjnum;}ListPrint_SqL;/*输出表L的内容*/intpos;intval;printf\n请输入插入的位置和元素值以为间隔:;scanf%d%dposval;ListInsert_SqLposval;/*随机指定插入点位置,假设在第二个元素前插入新的元素,其值为20*/printf\n插入新的元素后,顺序表的内容为;ListPrint_SqL;/*检验一下插入的结果,输出表L的内容*/printf\n请输入删除元素的位置:;scanf%dpos;ListDelete_SqLpost;/*随机指定删除点位置,假设对第四个元素进行删除*/printf\n删除元素后,顺序表的内容为;ListPrint_SqL;/*检验一下删除的结果,输出表L的内容*/printf\nTheDeletedvalueis%dt;/*检验一下删除点元素的值*/systempause;}
(二)线性表的链式存储结构的定义及其基本操作的参考程序(链表)1.文件linklistDef.h是线性表的单链表存储结构的定义structLNode{ElemTypedata;structLNode*next;};typedefstructLNode*LinkList;/*另一种定义LinkList的方法*/2.文件linklistAlgo.h是单链表的基本算法描述/*以下的算法均是针对带表头结点的单链表*/StatusListInit_LinkLinkListL{/*操作结果构造一个空的线性表L*/L=LinkList__llocsizeofstructLNode;/*产生头结点并使L指向此头结点*/if!L/*存储分配失败*/exitOVERFLOW;L-next=NULL;/*指针域为空*/returnOK;}StatusListDestroy_LinkLinkListL{/*初始条件线性表L已存在*//*操作结果销毁线性表L*/LinkListq;whileL{q=L-next;freeL;L=q;}returnOK;}StatusListClear_LinkLinkListL/*不改变L*/{/*初始条件线性表L已存在*//*操作结果将L重置为空表*/LinkListpq;p=L-next;/*p指向第一个结点*/whilep/*没到表尾*/{q=p-next;freep;p=q;}L-next=NULL;/*头结点指针域为空*/returnOK;}StatusListEmpty_LinkLinkListL{/*初始条件线性表L已存在*//*操作结果若L为空表,则返回TRUE,否则返回FALSE*/ifL-next/*非空*/returnFALSE;elsereturnTRUE;}intListLength_LinkLinkListL{/*初始条件线性表L已存在*//*操作结果返回L中数据元素个数*/inti=0;LinkListp=L-next;/*p指向第一个结点*/whilep/*没到表尾*/{i++;p=p-next;}returni;}StatusGetElem_LinkLinkListLintiElemTypee/*算法
2.8*/{/*初始条件:L为带头结点的单链表的头指针*//*操作结果当第i个元素存在时其值赋给e并返回OK否则返回ERROR*/intj=1;/*j为计数器*/LinkListp=L-next;/*p指向第一个结点*/whilepji/*顺指针向后查找直到p指向第i个元素或p为空*/{p=p-next;j++;}if!p||ji/*第i个元素不存在*/returnERROR;e=p-data;/*取第i个元素*/returnOK;}intLocateElem_LinkLinkListLElemTypeeStatus*compareElemTypeElemType{/*初始条件:线性表L已存在compare是数据元素判定函数满足为1否则为0*//*操作结果:返回L中第1个与e满足关系compare的数据元素的位序*//*若这样的数据元素不存在则返回值为0*/inti=0;LinkListp=L-next;whilep{i++;ifcomparep-datae/*找到这样的数据元素*/returni;p=p-next;}return0;}StatusListInsert_LinkLinkListLintiElemTypee/*算法
2.9不改变L*/{/*在带头结点的单链线性表L中第i个位置之前插入元素e*/intj=0;LinkListp=Ls;whilepji-1/*寻找第i-1个结点*/{p=p-next;j++;}if!p||ji-1/*i小于1或者大于表长*/returnERROR;s=LinkList__llocsizeofstructLNode;/*生成新结点*/s-data=e;/*插入L中*/s-next=p-next;p-next=s;returnOK;}StatusListDelete_LinkLinkListLintiElemTypee/*算法
2.10不改变L*/{/*在带头结点的单链线性表L中,删除第i个元素并由e返回其值*/intj=0;LinkListp=Lq;whilep-nextji-1/*寻找第i个结点并令p指向其前趋*/{p=p-next;j++;}if!p-next||ji-1/*删除位置不合理*/returnERROR;q=p-next;/*删除并释放结点*/p-next=q-next;e=q-data;freeq;returnOK;}StatusListTr__erse_LinkLinkListL{/*初始条件线性表L已存在*//*操作结果:依次对L的每个数据元素的值进行输出*/LinkListp=L-next;whilep{printf%dp-data;p=p-next;}printf\n;returnOK;}voidCreateList_LinkLinkListLintn/*算法
2.11*/{/*逆位序插在表头输入n个元素的值,建立带表头结构的单链线性表L*/inti;LinkListp;L=LinkList__llocsizeofstructLNode;L-next=NULL;/*先建立一个带头结点的单链表*/printf请输入%d个数据\nn;fori=n;i0;--i{p=LinkList__llocsizeofstructLNode;/*生成新结点*/scanf%dp-data;/*输入元素值*/p-next=L-next;/*插入到表头*/L-next=p;}}3.将测试数据和主函数新定义一个文件如取名为:linlistUse.cpp./*linlistUse.cpp主要实现算法
2.
9、
2.
10、
2.
11、
2.12的程序*/#includepubuse.htypedefintElemType;#includelinklistDef.h#includelinklistAlgo.hvoid__in{intn=5;LinkListLb;inti;ElemTypee;printf按非递增顺序;CreateList_LinkLbn;/*逆位序输入n个元素的值*/printfLb=;/*输出链表Lb的内容*/ListTr__erse_LinkLb;/*算法
2.9的测试*/printf\nenterinsertlocationandvalue:;scanf%d%die;ListInsert_LinkLbie;/*在Lb链表中第i个结点处插入一个新的结点,其值为e;*/printfLb=;/*输出链表Lb的内容*/ListTr__erse_LinkLb;/*算法
2.10的测试*/printf\nenterdeletedlocation:;scanf%di;ListDelete_LinkLbie;/*在Lb链表中删除第i个结点,其值为返回给e变量*/printfTheDeletede=%d\ne;/*输出被删结点的内容*/printfLb=;/*输出链表Lb的内容*/ListTr__erse_LinkLb;}
五、实验环境和实验步骤实验环境利用VisualC++集成__环境进行本实验的操作实验步骤――顺序表的定义与操作1.启动VC++;
2.新建工程/Win32ConsoleApplication,选择输入位置如“d:\”,输入工程的名称如“SeqlistDemo”;按“确定”按钮,选择“AnEmptyProject”,再按“完成”按钮,3.新建文件/C/C++HeaderFile,选中“添加到工程的复选按钮”,输入文件名“pubuse.h”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;
4.新建文件/C/C++HeaderFile,选中“添加到工程的复选按钮”,输入文件名“seqlistDef.h”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;
5.新建文件/C/C++HeaderFile,选中“添加到工程的复选按钮”,输入文件名“seqlistAlgo.h”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;
6.新建文件/C++Sour__File,选中“添加到工程的复选按钮”,输入文件名“seqlistUse.cpp”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;7.按F7键,或工具图标进行工程的建立,如有错误,根据错误显示区中的提示,改正错误,重新建立应用程序;8.按Ctrl+F5键,或工具图标进行工程的执行实验步骤――链表的定义与操作1.启动VC++;
2.新建工程/Win32ConsoleApplication,选择输入位置如“d:\”,输入工程的名称如“linklistDemo”;按“确定”按钮,选择“AnEmptyProject”,再按“完成”按钮,3.加载实验一中的pubuse.h选中菜单的“project”-“addtoproject”---“files”选择已存在文件,确定,然后一定将文件pubuse.h拷贝到所建的工程目录下;
4.新建文件/C/C++HeaderFile,选中“添加到工程的复选按钮”,输入文件名“linklistDef.h”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;
5.新建文件/C/C++HeaderFile,选中“添加到工程的复选按钮”,输入文件名“linklistAlgo.h”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;
6.新建文件/C++Sour__File,选中“添加到工程的复选按钮”,输入文件名“linklistUse.cpp”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;7.构建、调试、运行与实验一相同,在此不再复述;
六、思考题1.对于同样的一组整数,比较线性表的两种不同存储结构的特点和使用场合
2.将两个递增的有序链表合并为一个递增的有序链表要求结果链表仍使用原来两个链表的存储空间不另外占用其它的存储空间表中不允许有重复的数据
3.设计一个算法,通过一趟遍历在带头结点的单链表中确定值最大的结点实验二栈和队列的结构定义及基本操作(必做2学时)
一、实验目的.熟练掌握栈和队列的特点.掌握栈的定义和基本操作,熟练掌握顺序栈的操作及应用.掌握对列的定义和基本操作,熟练掌握链式队列的操作及应用掌握环形队列的入队和出队等基本操作.加深对栈结构和队列结构的理解,逐步培养解决实际问题的编程能力
二、实验内容:定义顺序栈,完成栈的基本操作空栈、入栈、出栈、取栈顶元素;实现十进制数与八进制数的转换;定义链式队列,完成队列的基本操作入队和出队;1.问题描述
(1)利用栈的顺序存储结构设计一组输入数据(假定为一组整数),能够对顺序栈进行如下操作.初始化一个空栈,分配一段连续的存储空间,且设定好栈顶和栈底;.完成一个元素的入栈操作,修改栈顶指针;.完成一个元素的出栈操作,修改栈顶指针;.读取栈顶指针所指向的元素的值;.将十进制数N和其它d进制数的转换是计算机实现计算的基本问题,其解决方案很多,其中最简单方法基于下列原理即除d取余法例如
(1348)10=
(2504)8NNdiv8Nmod8134816841682102125202从中我们可以看出,最先产生的余数4是转换结果的最低位,这正好符合栈的特性即后进先出的特性所以可以用顺序栈来模拟这个过程以此来实现十进制数与八进制数的转换;.编写主程序,实现对各不同的算法调用
(2)利用队列的链式存储结构设计一组输入数据(假定为一组整数),能够对链式队列进行如下操作.初始化一个空队列,形成一个带表头结点的空队;.完成一个元素的入队操作,修改队尾指针;.完成一个元素的出队操作,修改队头指针;.修改主程序,实现对各不同的算法调用其他算法的描述省略,参见实现要求说明2.实现要求对顺序栈的各项操作一定要编写成为C(C++)语言函数,组合成模块化的形式,每个算法的实现要从时间复杂度和空间复杂度上进行评价.“初始化栈算法”操作结果构造一个空栈S;.“销毁栈算法”操作结果销毁栈S,S不再存在;.“置空栈算法”操作结果把S置为空栈;.“判是否空栈算法”操作结果若栈S为空栈,则返回TRUE,否则返回FALSE;.“求栈的长度算法”操作结果返回S的元素个数,即栈的长度;.“取栈顶元素算法”操作结果若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR;.“入栈算法”操作结果插入元素e为新的栈顶元素.“出栈算法”操作结果若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR;.“实现十进制数与八进制数的转换算法”操作结果输入任意一个非负的十进制数,输出对应的八进制数;对链式队列的各项操作一定要编写成为C(C++)语言函数,组合成模块化的形式,每个算法的实现要从时间复杂度和空间复杂度上进行评价.“初始化空队算法”操作结果构造一个空队列Q;.“销毁队列算法”操作结果销毁队列Q无论空否均可;.“空队列算法”操作结果将Q清为空队列;.“判队列是否为空算法”操作结果若Q为空队列则返回TRUE否则返回FALSE;.“求队列的长度算法”操作结果求队列的长度,返回队列中结点的个数;.“取队头元素算法”操作结果若队列不空则用e返回Q的队头元素并返回OK否则返回ERROR;.“入队算法”操作结果插入元素e为Q的新的队尾元素;.“出队算法”操作结果若队列不空删除Q的队头元素用e返回其值并返回OK否则返回ERROR;
三、实验指导
(一)顺序栈的实验指导1.首先将顺序栈存储结构定义放在一个头文件如取名为SqStackDef.h2.将顺序栈的基本操作算法也集中放在一个文件之中,如取名为SqStackAlgo.h如InitStack、DestroyStack、ClearStack、StackEmpty、StackLength、GetTop、Push、Pop、conversion10_8等3.将函数的测试和主函数组合成一个文件,如取名为SqStackUse.cpp
(二)链式队列的实验指导1.首先将链式队列的存储结构定义放在一个头文件如取名为LinkQueueDef.h2.将链式队列的基本操作算法也集中放在一个文件之中,如取名为LinkQueueAlgo.h如InitQueue、DestroyQueue、ClearQueue、QueueEmpty、QueueLength、GetHead_Q、EnQueue、DeQueue、QueueTr__erse等3.将函数的测试和主函数组合成一个文件,如取名为LinkQueueUse.cpp
四、参考程序
(一)顺序栈1.文件SqStackDef.h中实现了栈的顺序存储表示#defineSTACK_INIT_SIZE10/*存储空间初始分配量*/#defineSTACKINCREMENT2/*存储空间分配增量*/typedefstructSqStack{SElemType*base;/*在栈构造之前和销毁之后,base的值为NULL*/SElemType*top;/*栈顶指针*/intstacksize;/*当前已分配的存储空间,以元素为单位*/}SqStack;/*顺序栈*/2.文件SqStackAlgo.h中实现顺序栈的基本操作(存储结构由SqStackDef.h定义)StatusInitStackSqStackS{/*构造一个空栈S*/S.base=SElemType*__llocSTACK_INIT_SIZE*sizeofSElemType;if!S.baseexitOVERFLOW;/*存储分配失败*/S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusDestroyStackSqStackS{/*销毁栈S,S不再存在*/freeS.base;S.base=NULL;S.top=NULL;S.stacksize=0;returnOK;}StatusClearStackSqStackS{/*把S置为空栈*/S.top=S.base;returnOK;}StatusStackEmptySqStackS{/*若栈S为空栈,则返回TRUE,否则返回FALSE*/ifS.top==S.basereturnTRUE;elsereturnFALSE;}intStackLengthSqStackS{/*返回S的元素个数,即栈的长度*/returnS.top-S.base;}StatusGetTopSqStackSSElemTypee{/*若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR*/ifS.topS.base{e=*S.top-1;returnOK;}elsereturnERROR;}StatusPushSqStackSSElemTypee{/*插入元素e为新的栈顶元素*/ifS.top-S.base=S.stacksize/*栈满,追加存储空间*/{S.base=SElemType*reallocS.baseS.stacksize+STACKINCREMENT*sizeofSElemType;if!S.baseexitOVERFLOW;/*存储分配失败*/S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}StatusPopSqStackSSElemTypee{/*若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR*/ifS.top==S.basereturnERROR;e=*--S.top;returnOK;}StatusStackTr__erseSqStackSStatus*visitSElemType{/*从栈底到栈顶依次对栈中每个元素调用函数visit*//*一旦visit失败,则操作失败*/whileS.topS.basevisit*S.base++;printf\n;returnOK;}voidconversion10_8/*算法
3.1*/{/*对于输入的任意一个非负十进制整数,打印输出与其等值的八进制数*/SqStacks;unsignedn;/*非负整数*/SElemTypee;InitStacks;/*初始化栈*/printfEnterannumber=0:;scanf%un;/*输入非负十进制整数n*/whilen/*当n不等于0*/{Pushsn%8;/*入栈n除以8的余数8进制的低位*/n=n/8;}while!StackEmptys/*当栈不空*/{Popse;/*弹出栈顶元素且赋值给e*/printf%de;/*输出e*/}printf\n;}3.在SqStackUse.cpp文件中,测试算法
3.1的调用,其中间接调用了顺序栈的其他基本算法typedefintSElemType;/*定义栈元素类型为整型*/#includepubuse.h/*常量定义与系统函数原型声明,与实验一中的相同*/#includeSqStackDef.h/*采用顺序栈的类型定义*/#includeSqStackAlgo.h/*利用顺序栈的基本操作*/void__in{conversion10_8;/*十进制数到八进制转换的验证*/}
(二)链式队列1.文件LinkQueueDef.h中实现单链队列--队列的链式存储结构的表示typedefstructQNode{QElemTypedata;structQNode*next;}QNode*QueuePtr;typedefstruct{QueuePtrfrontrear;/*队头、队尾指针*/}LinkQueue;2.文件LinkQueueAlgo.h中实现的链队列的基本算法,其存储结构由LinkQueueDef.h定义StatusInitQueueLinkQueueQ{/*构造一个空队列Q*/Q.front=Q.rear=QueuePtr__llocsizeofQNode;if!Q.frontexitOVERFLOW;Q.front-next=NULL;returnOK;}StatusDestroyQueueLinkQueueQ{/*销毁队列Q无论空否均可*/whileQ.front{Q.rear=Q.front-next;freeQ.front;Q.front=Q.rear;}returnOK;}StatusClearQueueLinkQueueQ{/*将Q清为空队列*/QueuePtrpq;Q.rear=Q.front;p=Q.front-next;Q.front-next=NULL;whilep{q=p;p=p-next;freeq;}returnOK;}StatusQueueEmptyLinkQueueQ{/*若Q为空队列则返回TRUE否则返回FALSE*/ifQ.front==Q.rearreturnTRUE;elsereturnFALSE;}intQueueLengthLinkQueueQ{/*求队列的长度*/inti=0;QueuePtrp;p=Q.front;whileQ.rear!=p{i++;p=p-next;}returni;}StatusGetHead_QLinkQueueQQElemTypee{/*若队列不空则用e返回Q的队头元素并返回OK否则返回ERROR*/QueuePtrp;ifQ.front==Q.rearreturnERROR;p=Q.front-next;e=p-data;returnOK;}StatusEnQueueLinkQueueQQElemTypee{/*插入元素e为Q的新的队尾元素*/QueuePtrp=QueuePtr__llocsizeofQNode;if!p/*存储分配失败*/exitOVERFLOW;p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;}StatusDeQueueLinkQueueQQElemTypee{/*若队列不空删除Q的队头元素用e返回其值并返回OK否则返回ERROR*/QueuePtrp;ifQ.front==Q.rearreturnERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;ifQ.rear==pQ.rear=Q.front;freep;returnOK;}StatusQueueTr__erseLinkQueueQvoid*viQElemType{/*从队头到队尾依次对队列Q中每个元素调用函数vi一旦vi失败则操作失败*/QueuePtrp;p=Q.front-next;whilep{vip-data;p=p-next;}printf\n;returnOK;}3.文件LinkQueueUse.cpp中包含检验LinkQueueAlgo.h中关于链式队列基本操作的声明、测试数据和主函数#includepubuse.h/*与实验一的意义相同*/typedefintQElemType;/*假设链式队列中的结点是一组整数*/#includeLinkQueueDef.h#includeLinkQueueAlgo.hvoidvisitQElemTypei{printf%di;}void__in{inti;intL;intm;QElemTyped;LinkQueueq;i=InitQueueq;ifiprintf成功地构造了一个空队列!\n;printf是否空队列?%d1:空0:否QueueEmptyq;printf队列的长度为%d\nQueueLengthq;printf请输入新队列的长度L=;scanf%dL;m=L;printf请输入新队列的元素;forL;L0;--L{scanf%dd;EnQueueqd;}printf插入%d个元素后队列的长度为%d\nmQueueLengthq;printf是否空队列?%d1:空0:否QueueEmptyq;printf队列的元素依次为;QueueTr__erseqvisit;i=GetHead_Qqd;ifi==OKprintf队头元素是%d\nd;DeQueueqd;printf删除了队头元素%d\nd;i=GetHead_Qqd;ifi==OKprintf新的队头元素是%d\nd;ClearQueueq;printf清空队列后q.front=%uq.rear=%uq.front-next=%u\nq.frontq.rearq.front-next;DestroyQueueq;printf销毁队列后q.front=%uq.rear=%u\nq.frontq.rear;}
五、实验环境和实验步骤实验环境利用VisualC++集成__环境进行本实验的操作
(一)基本实验的实验步骤顺序栈的定义以及应用1.启动VC++;
2.新建工程/Win32ConsoleApplication,选择输入位置如“d:\”,输入工程的名称如“SqStackDemo”;按“确定”按钮,选择“AnEmptyProject”,再按“完成”按钮,3.加载实验一中的pubuse.h选中菜单的“project”..“addtoproject”..“files”选择已存在文件,确定,然后一定将文件pubuse.h拷贝到所建的工程目录下;
4.新建文件/C/C++HeaderFile,选中“添加到工程的复选按钮”,输入文件名“SqStackDef.h”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;
5.新建文件/C/C++HeaderFile,选中“添加到工程的复选按钮”,输入文件名“SqStackAlgo.h”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;
6.新建文件/C++Sour__File,选中“添加到工程的复选按钮”,输入文件名“SqStackUse.cpp”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;7.构建、调试、运行与实验一相同,在此不再复述;
(二)基本实验的实验步骤链式队列定义以及应用1.启动VC++;
2.新建工程/Win32ConsoleApplication,选择输入位置如“d:\”,输入工程的名称如“LinkQueueDemo”;按“确定”按钮,选择“AnEmptyProject”,再按“完成”按钮,3.加载实验一中的pubuse.h选中菜单的”project”--“addtoproject”--“files”选择已存在文件,确定,然后一定将文件pubuse.h拷贝到所建的工程目录下;
4.新建文件/C/C++HeaderFile,选中“添加到工程的复选按钮”,输入文件名“LinkQueueDef.h”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;
5.新建文件/C/C++HeaderFile,选中“添加到工程的复选按钮”,输入文件名“LinkQueueAlgo.h”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;
6.新建文件/C++Sour__File,选中“添加到工程的复选按钮”,输入文件名“LinkQueueUse.cpp”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;7.构建、调试、运行与实验一相同,在此不再复述;
六、思考题1.利用一个堆栈,将一个线性表中的元素按逆序重新存放例如原来的顺序为12,8,6,4,2,要求改为2,4,6,8,12[实验说明]设原始数据已存入数组a中,堆栈为stack,已清空,栈指针为top,初始top=0首先从线性表第1个元素开始,依次将其元素压入栈中,然后将栈中元素依次弹出,重新放入数组a中
2.设数组QU[0,mo-1]中存放循环队列的元素编写能向该循环队列插入一个结点数据和删除一个结点数据的程序[实验说明]1队列的特点是在队尾入队,在队首出队在循环队列中,最初队列为空时队首指针front和队尾指针rear都指向同一位置,当有元素入队时,由于是循环的,所以rear位置前移,即QU.rear=QU.rear+1%mo将插入元素放到rear的新位置上2当有元素出队时,先将front前移一个位置,即QU.front=QU.front+1%mo将front新位置的元素取出即可实验三二叉树的结构定义及基本操作(必做2学时)
一、实验目的.熟练掌握二叉树的二叉链表存储结构.掌握二叉树的非线性和递归性特点.熟练掌握二叉树的递归遍历操作的实现方法.掌握线索二叉树的定义和基本操作.加深对二叉树结构和性质的理解,逐步培养解决实际问题的编程能力
二、实验内容:
(一)基本实验内容.定义二叉树的链式存储结构;.实现二叉树的基本操作建空树、销毁二叉树、生成二叉树先序中序或后序、判二叉树是否为空、求二叉树的深度、求二叉树的根等基本算法;.实现二叉树的递归先序、中序或后序遍历算法;1.问题描述利用二叉树的链式存储结构,设计一组输入数据(假定为一组整数或一组字符),能够对二叉树进行如下操作.创建一棵空二叉树;.对一棵存在的二叉树进行销毁;.根据输入某种遍历次序输入二叉树中结点的值,依序建立二叉树;.判断某棵二叉树是否为空;.求二叉树的深度;.求二叉树的根结点,若为空二叉树,则返回一特殊值;.二叉树的遍历,即按某种方式访问二叉树中的所有结点,并使每个结点恰好被访问一次;.编写主程序,实现对各不同的算法调用;其他算法的描述省略,参见实现要求说明2.实现要求.“构造空二叉树算法”操作结果构造一个空二叉树T;.“销毁二叉树算法”初始条件:二叉树T存在;操作结果:销毁二叉树T;.“创建二叉树算法”初始条件:可以根据先序、中序和后序输入二叉树中结点的值(可为字符型或整型);操作结果:以选择的某种次序建立二叉树T;.“判二叉树是否为空算法”初始条件:二叉树T存在;操作结果:若T为空二叉树则返回TRUE否则FALSE;.“求二叉树的深度算法”初始条件:二叉树T存在;操作结果:返回T的深度;.“求二叉树的根算法”初始条件:二叉树T存在;操作结果:返回T的根;.“先序递归遍历算法”初始条件:二叉树T存在Visit是对结点操作的应用函数;操作结果:先序递归遍历T对每个结点调用函数Visit一次且仅一次;.“中序递归遍历算法”初始条件:二叉树T存在Visit是对结点操作的应用函数;操作结果:中序递归遍历T对每个结点调用函数Visit一次且仅一次;.“后序递归遍历算法”初始条件:二叉树T存在Visit是对结点操作的应用函数;操作结果:后序递归遍历T对每个结点调用函数Visit一次且仅一次;
三、实验指导
(一)基本实验指导1.首先将二叉树的链式存储结构定义放在一个头文件如取名为BinTreeDef.h2.将二叉树的基本操作算法也集中放在一个文件之中,如取名为BinTreeAlgo.h包含关于二叉树的链式结构操作的一些基本算法,如InitBiTree、DestroyBiTree、CreateBiTree、BiTreeEmpty、BiTreeDepth、Root、PreOrderTr__erse等3.将函数的测试和主函数组合成一个文件,如取名为BinTreeUse.cpp
四、参考程序
(一)基本实验的参考程序
1、文件pubuse.h,与实验一相同;2.文件BinTreeDef.h中实现了二叉树的链式存储结构定义typedefstructBiTNode{TElemTypedata;structBiTNode*lchild*rchild;/*左右孩子指针*/}BiTNode*BiTree;3.文件BinTreeAlgo.h中实现二叉树的基本操作(存储结构由BinTreeDef.h定义)/*BinTreeAlgo.h二叉树的二叉链表存储存储结构由BinTreeDef.h定义的基本操作*/StatusInitBiTreeBiTreeT{/*操作结果:构造空二叉树T*/T=NULL;returnOK;}voidDestroyBiTreeBiTreeT{/*初始条件:二叉树T存在操作结果:销毁二叉树T*/ifT/*非空树*/{ifT-lchild/*有左孩子*/DestroyBiTreeT-lchild;/*销毁左孩子子树*/ifT-rchild/*有右孩子*/DestroyBiTreeT-rchild;/*销毁右孩子子树*/freeT;/*释放根结点*/T=NULL;/*空指针赋0*/}}#defineClearBiTreeDestroyBiTreevoidCreateBiTreeBiTreeT{/*算法
6.4:按先序次序输入二叉树中结点的值(可为字符型或整型,*//*在主程中定义),构造二叉链表表示的二叉树T变量Nil表示空(子)树有改动*/TElemTypech;#ifdefCHARscanf%cch;#endif#ifdefINTscanf%dch;#endififch==Nil/*空*/T=NULL;else{T=BiTree__llocsizeofBiTNode;if!TexitOVERFLOW;T-data=ch;/*生成根结点*/CreateBiTreeT-lchild;/*构造左子树*/CreateBiTreeT-rchild;/*构造右子树*/}}StatusBiTreeEmptyBiTreeT{/*初始条件:二叉树T存在*//*操作结果:若T为空二叉树则返回TRUE否则FALSE*/ifTreturnFALSE;elsereturnTRUE;}intBiTreeDepthBiTreeT{/*初始条件:二叉树T存在操作结果:返回T的深度*/intij;if!Treturn0;ifT-lchildi=BiTreeDepthT-lchild;elsei=0;ifT-rchildj=BiTreeDepthT-rchild;elsej=0;returniji+1:j+1;}TElemTypeRootBiTreeT{/*初始条件:二叉树T存在操作结果:返回T的根*/ifBiTreeEmptyTreturnNil;elsereturnT-data;}TElemTypeValueBiTreep{/*初始条件:二叉树T存在,p指向T中某个结点*//*操作结果:返回p所指结点的值*/returnp-data;}voidAssignBiTreepTElemTypevalue{/*给p所指结点赋值为value*/p-data=value;}voidPreOrderTr__erseBiTreeTStatus*VisitTElemType{/*初始条件:二叉树T存在Visit是对结点操作的应用函数算法
6.1,有改动*//*操作结果:先序递归遍历T对每个结点调用函数Visit一次且仅一次*/ifT/*T不空*/{VisitT-data;/*先访问根结点*/PreOrderTr__erseT-lchildVisit;/*再先序遍历左子树*/PreOrderTr__erseT-rchildVisit;/*最后先序遍历右子树*/}}voidInOrderTr__erseBiTreeTStatus*VisitTElemType{/*初始条件:二叉树T存在Visit是对结点操作的应用函数*//*操作结果:中序递归遍历T对每个结点调用函数Visit一次且仅一次*/ifT{InOrderTr__erseT-lchildVisit;/*先中序遍历左子树*/VisitT-data;/*再访问根结点*/InOrderTr__erseT-rchildVisit;/*最后中序遍历右子树*/}}voidPostOrderTr__erseBiTreeTStatus*VisitTElemType{/*初始条件:二叉树T存在Visit是对结点操作的应用函数*//*操作结果:后序递归遍历T对每个结点调用函数Visit一次且仅一次*/ifT/*T不空*/{PostOrderTr__erseT-lchildVisit;/*先后序遍历左子树*/PostOrderTr__erseT-rchildVisit;/*再后序遍历右子树*/VisitT-data;/*最后访问根结点*/}}4.在文件BinTreeUse.cpp中,测试二叉树基本算法的调用/*BinTreeUse.cpp检验BinTreeAlgo.h的主程序利用条件编译选择数据类型另一种方法*//*二叉树的数据类型可以以是字符型,也可以是整型,可在程序中使用条件编译作出判断和控制*/#defineCHAR/*字符型,本例是采用字符型作为数据类型*//*#defineINT/*整型(二者选一)*/#includepubuse.h/*与实验一的意义相同*/#ifdefCHARtypedefcharTElemType;TElemTypeNil=;/*字符型以空格符为空*/#endif#ifdefINTtypedefintTElemType;TElemTypeNil=0;/*整型以0为空*/#endif#includeBinTreeDef.h/*二叉树链式存储结构定义*/#includeBinTreeAlgo.h/*二叉树基本算法和扩展算法定义*/StatusvisitTTElemTypee{#ifdefCHARprintf%ce;#endif#ifdefINTprintf%de;#endifreturnOK;}void__in{BiTreeT;TElemTypee1;/*1---基本实验算法的验证*/InitBiTreeT;printf构造空二叉树后树空否?%d1:是0:否树的深度=%d\nBiTreeEmptyTBiTreeDepthT;e1=RootT;ife1!=Nil#ifdefCHARprintf二叉树的根为:%c\ne1;#endif#ifdefINTprintf二叉树的根为:%d\ne1;#endifelseprintf树空,无根\n;#ifdefCHARprintf请先序输入二叉树如:ab三个空格表示a为根结点b为左子树的二叉树\n;#endif#ifdefINTprintf请先序输入二叉树如:12000表示1为根结点2为左子树的二叉树\n;#endifCreateBiTreeT;printf建立二叉树后树空否?%d1:是0:否树的深度=%d\nBiTreeEmptyTBiTreeDepthT;e1=RootT;ife1!=Nil#ifdefCHARprintf二叉树的根为:%c\ne1;#endif#ifdefINTprintf二叉树的根为:%d\ne1;#endifelseprintf树空,无根\n;printf中序递归遍历二叉树:\n;InOrderTr__erseTvisitT;printf后序递归遍历二叉树:\n;PostOrderTr__erseTvisitT;}
五、实验环境和实验步骤实验环境利用VisualC++集成__环境进行本实验的操作
(一)基本实验的实验步骤1.启动VC++;
2.新建工程/Win32ConsoleApplication,选择输入位置如“d:\”,输入工程的名称如“BinTreeDemo”;按“确定”按钮,选择“AnEmptyProject”,再按“完成”按钮,3.加载实验一中的pubuse.h选中菜单的”project”—“addtoproject”—“files”选择已存在文件,确定,然后一定将文件pubuse.h拷贝到所建的工程目录下;
4.新建文件/C/C++HeaderFile,选中“添加到工程的复选按钮”,输入文件名“BinTreeDef.h”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;
5.新建文件/C/C++HeaderFile,选中“添加到工程的复选按钮”,输入文件名“BinTreeAlgo.h”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;
6.新建文件/C++Sour__File,选中“添加到工程的复选按钮”,输入文件名“BinTreeUse.cpp”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;7.构建、调试、运行与实验一相同,在此不再复述;实验四图的结构定义及其基本操作(必做2学时)
一、实验目的.熟练掌握图的两种存储结构邻接矩阵和邻接表的表示方法.掌握图的基本运算及应用.加深对图的理解,逐步培养解决实际问题的编程能力
二、实验内容:.采用邻接表或邻接矩阵方式存储图,实现图的深度遍历和广度遍历;.用广度优先搜索方法找出从一顶点到另一顶点边数最少的路径1.问题描述利用邻接表存储结构,设计一种图(有向或无向),并能够对其进行如下操作.创建一个可以随机确定结点数和弧(有向或无向)数的图;.根据图结点的序号,得到该结点的值;.根据图结点的位置的第一个邻接顶点的序号,以及下一个邻接顶点的序号;.实现从第v个顶点出发对图进行深度优先递归遍历;.实现对图作深度优先遍历;.实现对图进行广度优先非递归遍历;.编写主程序,实现对各不同的算法调用2.实现要求(以邻接表存储形式为例)编写图的基本操作函数:对图的各项操作一定要编写成为C(C++)语言函数,组合成模块化的形式,每个算法的实现要从时间复杂度和空间复杂度上进行评价.“建立图的邻接表算法”CreateGraphALGraph*G操作结果采用邻接表存储结构构造没有相关信息的图G.“邻接表表示的图的递归深度优先遍历算法”DFSTr__erseALGraphGvoid*Visitchar*初始条件图G已经存在;操作结果返回图的按深度遍历的结果.“邻接表表示的图的广度优先遍历算法”BFSTr__erseALGraphGvoid*Visitchar*初始条件图G已经存在;操作结果返回图的按广度遍历的结果.“邻接表从某个结点开始的广度优先遍历算法”BFSALGraphGintv初始条件图G已经存在;操作结果返回图从某个结点开始的按广度遍历的结果分析:修改输入数据,预期输出并验证输出的结果,加深对有关算法的理解
三、实验指导:本实验以图的邻接表存储结构为例,要求完成基本要求,同时对无向图,有向网,无向网也一并实现其相关的操作,课后同学们可以用邻接矩阵式存储结构完成以上操作1.首先将图的链接存储结构定义放在一个头文件如取名为ALGraphDef.h2.链接表式存储图的基本操作也放在一个文件中ALGraphAlgo.h.3.将函数的测试和主函数组合成一个文件,如取名为文件ALGraphUse.cpp.由于要用到队列技术,对于队列的数据结构定义和基本操作函数的描述就可以借助实验二的结果,不必重写
四、参考程序:1.文件pubuse.h头文件;2.文件LinkQueueDef.h是链式队列的存储结构;3.文件LinkQueueAlgo.h是链式队列的基本操作;4.文件ALGraphDef.h定义了图的链接存储结构(以邻接表存储表示)#define__X_VERTEX_NUM20typedefenum{DGDNAGAN}GraphKind;/*{有向图有向网无向图无向网}*/typedefstructArcNode{intadjvex;/*该弧所指向的顶点的位置*/structArcNode*nextarc;/*指向下一条弧的指针*/InfoType*info;/*网的权值指针)*/}ArcNode;/*表结点*/typedefstruct{VertexTypedata;/*顶点信息*/ArcNode*firstarc;/*第一个表结点的地址指向第一条依附该顶点的弧的指针*/}VNodeAdjList[__X_VERTEX_NUM];/*头结点*/typedefstruct{AdjListverti__s;intvexnumarcnum;/*图的当前顶点数和弧数*/intkind;/*图的种类标志*/}ALGraph;5.文件ALGraphAlgo.h定义了链接表式存储图的基本操作/*ALGraphAlgo.cpp图的邻接表存储存储结构由ALGraphDef.h定义的基本操作*/intLocateVexALGraphGVertexTypeu{/*初始条件:图G存在u和G中顶点有相同特征*//*操作结果:若G中存在顶点u则返回该顶点在图中位置;否则返回-1*/inti;fori=0;iG.vexnum;++iifstrcmpuG.verti__s[i].data==0returni;return-1;}StatusCreateGraphALGraphG{/*采用邻接表存储结构构造没有相关信息的图G用一个函数构造4种图*/intijk;intw;/*权值*/VertexTypevavb;ArcNode*p;printf请输入图的类型有向图:0有向网:1无向图:2无向网:3:;scanf%dG.kind;printf请输入图的顶点数边数以作为间隔:;scanf%d%dG.vexnumG.arcnum;printf请输入%d个顶点的值%d个字符以空格作为间隔:\nG.vexnum__X_NAME;fori=0;iG.vexnum;++i/*构造顶点向量*/{scanf%sG.verti__s[i].data;G.verti__s[i].firstarc=NULL;}ifG.kind==1||G.kind==3/*网*/printf请顺序输入每条弧边的权值、弧尾和弧头以空格作为间隔,回车作为每条弧边的间隔:\n;else/*图*/printf请顺序输入每条弧边的弧尾和弧头以空格作为间隔,回车作为每条弧边的间隔:\n;fork=0;kG.arcnum;++k/*构造表结点链表*/{ifG.kind==1||G.kind==3/*网*/scanf%d%s%swvavb;else/*图*/scanf%s%svavb;i=LocateVexGva;/*弧尾*/j=LocateVexGvb;/*弧头*/p=ArcNode*__llocsizeofArcNode;p-adjvex=j;ifG.kind==1||G.kind==3/*网*/{p-info=int*__llocsizeofint;*p-info=w;}elsep-info=NULL;/*图*/p-nextarc=G.verti__s[i].firstarc;/*插在表头*/G.verti__s[i].firstarc=p;ifG.kind=2/*无向图或网产生第二个表结点*/{p=ArcNode*__llocsizeofArcNode;p-adjvex=i;ifG.kind==3/*无向网*/{p-info=int*__llocsizeofint;*p-info=w;}elsep-info=NULL;/*无向图*/p-nextarc=G.verti__s[j].firstarc;/*插在表头*/G.verti__s[j].firstarc=p;}}returnOK;}voidDestroyGraphALGraphG{/*初始条件:图G存在操作结果:销毁图G*/inti;ArcNode*p*q;G.vexnum=0;G.arcnum=0;fori=0;iG.vexnum;++i{p=G.verti__s[i].firstarc;whilep{q=p-nextarc;ifG.kind%2/*网*/freep-info;freep;p=q;}}}VertexType*GetVexALGraphGintv{/*初始条件:图G存在v是G中某个顶点的序号操作结果:返回v的值*/ifv=G.vexnum||v0exitERROR;returnG.verti__s[v].data;}intFirstAdjVexALGraphGVertexTypev{/*初始条件:图G存在v是G中某个顶点*//*操作结果:返回v的第一个邻接顶点的序号若顶点在G中没有邻接顶点则返回-1*/ArcNode*p;intv1;v1=LocateVexGv;/*v1为顶点v在图G中的序号*/p=G.verti__s[v1].firstarc;ifpreturnp-adjvex;elsereturn-1;}intNextAdjVexALGraphGVertexTypevVertexTypew{/*初始条件:图G存在v是G中某个顶点w是v的邻接顶点*//*操作结果:返回v的相对于w的下一个邻接顶点的序号*//*若w是v的最后一个邻接点则返回-1*/ArcNode*p;intv1w1;v1=LocateVexGv;/*v1为顶点v在图G中的序号*/w1=LocateVexGw;/*w1为顶点w在图G中的序号*/p=G.verti__s[v1].firstarc;whilepp-adjvex!=w1/*指针p不空且所指表结点不是w*/p=p-nextarc;if!p||!p-nextarc/*没找到w或w是最后一个邻接点*/return-1;else/*p-adjvex==w*/returnp-nextarc-adjvex;/*返回v的相对于w的下一个邻接顶点的序号*/}Booleanvisited[__X_VERTEX_NUM];/*访问标志数组全局量*/void*VisitFuncchar*v;/*函数变量全局量*/voidDFSALGraphGintv{/*从第v个顶点出发递归地深度优先遍历图G算法
7.5*/intw;VertexTypev1w1;strcpyv1*GetVexGv;visited[v]=TRUE;/*设置访问标志为TRUE已访问*/VisitFuncG.verti__s[v].data;/*访问第v个顶点*/forw=FirstAdjVexGv1;w=0;w=NextAdjVexGv1strcpyw1*GetVexGwif!visited[w]DFSGw;/*对v的尚未访问的邻接点w递归调用DFS*/}voidDFSTr__erseALGraphGvoid*Visitchar*{/*对图G作深度优先遍历算法
7.4*/intv;VisitFunc=Visit;/*使用全局变量VisitFunc使DFS不必设函数指针参数*/forv=0;vG.vexnum;v++visited[v]=FALSE;/*访问标志数组初始化*/forv=0;vG.vexnum;v++if!visited[v]DFSGv;/*对尚未访问的顶点调用DFS*/printf\n;}typedefintQElemType;/*队列类型*/#includeLinkQueueDef.h#includeLinkQueueAlgo.hvoidBFSTr__erseALGraphGvoid*Visitchar*{/*按广度优先非递归遍历图G使用辅助队列Q和访问标志数组visited算法
7.6*/intvuw;VertexTypeu1w1;LinkQueueQ;forv=0;vG.vexnum;++vvisited[v]=FALSE;/*置初值*/InitQueueQ;/*置空的辅助队列Q*/forv=0;vG.vexnum;v++/*如果是连通图只v=0就遍历全图*/if!visited[v]/*v尚未访问*/{visited[v]=TRUE;VisitG.verti__s[v].data;EnQueueQv;/*v入队列*/while!QueueEmptyQ/*队列不空*/{DeQueueQu;/*队头元素出队并置为u*/strcpyu1*GetVexGu;forw=FirstAdjVexGu1;w=0;w=NextAdjVexGu1strcpyw1*GetVexGwif!visited[w]/*w为u的尚未访问的邻接顶点*/{visited[w]=TRUE;VisitG.verti__s[w].data;EnQueueQw;/*w入队*/}}}printf\n;}voidDisplayALGraphG{/*输出图的邻接矩阵G*/inti;ArcNode*p;switchG.kind{caseDG:printf有向图\n;break;caseDN:printf有向网\n;break;caseAG:printf无向图\n;break;caseAN:printf无向网\n;}printf%d个顶点\nG.vexnum;fori=0;iG.vexnum;++iprintf%sG.verti__s[i].data;printf\n%d条弧边:\nG.arcnum;fori=0;iG.vexnum;i++{p=G.verti__s[i].firstarc;whilep{ifG.kind=1/*有向*/{printf%s→%sG.verti__s[i].dataG.verti__s[p-adjvex].data;ifG.kind==DN/*网*/printf:%d*p-info;}else/*无向避免输出两次*/{ifip-adjvex{printf%s-%sG.verti__s[i].dataG.verti__s[p-adjvex].data;ifG.kind==AN/*网*/printf:%d*p-info;}}p=p-nextarc;}printf\n;}}6.文件ALGraphUse.cpp是检验ALGraphAlgo.h的主程序#includepubuse.h#define__X_NAME3/*顶点字符串的最大长度+1*/typedefintInfoType;/*存放网的权值*/typedefcharVertexType[__X_NAME];/*字符串类型*/#includeALGraphDef.h#includeALGraphAlgo.hvoidprintchar*i{printf%si;}void__in{ALGraphg;CreateGraphg;Displayg;printf深度优先搜索的结果:\n;DFSTr__ersegprint;printf广度优先搜索的结果:\n;BFSTr__ersegprint;DestroyGraphg;/*销毁图*/}
五、实验环境和实验步骤实验环境利用VisualC++集成__环境进行本实验的操作实验步骤1.启动VC++;2.新建工程/Win32ConsoleApplication,选择输入位置如“d:\”,输入工程的名称如“ALGraphDemo”;按“确定”按钮,选择“AnEmptyProject”,再按“完成”按钮;3.加载实验一中的pubuse.h选中菜单的“project”..“addtoproject”..“files”选择已存在文件,确定,然后一定将文件pubuse.h拷贝到所建的工程目录下;4.加载实验二中的LinkQueueDef.h和LinkQueueAlgo.h,选中菜单的“project”..“addtoproject”..“files”选择以上两个已存在文件,确定,然后一定将文件LinkQueueDef.h和LinkQueueAlgo.h拷贝到所建的工程目录下;5.新建文件/C/C++HeaderFile,选中“添加到工程的复选按钮”,输入文件名“ALGraphDef.h”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;6.新建文件/C++HeaderFile,选中“添加到工程的复选按钮”,输入文件名“ALGraphAlgo.h”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;7.新建文件/C++Sour__File,选中“添加到工程的复选按钮”,输入文件名“ALGraphUse.cpp”,按“确定”按钮,在显示的代码编辑区内输入如上的参考程序;8.构建、调试、运行与实验一相同。