还剩45页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
课程实验报告课程名称数据结构实验专业班级计算机科学与技术202008学号U202015533_______________姓名徐瑞达___________________指导教师互凌__________________报告日期2021年5月6日计算机科学与技术学院华中科技大学计算机学院数据结构实验报告LocateElem查75该元素不在线请选择你的操作[0~17]:7清输入元素5该元素不找某元素性表中在线性表中PriorElem获取83该元素无直接请选择你的操作[0~17]:8谙输入元素3该元素无直接前驱前驱宣法前驱PriorElem获取87线性表中元素请选择你的操作
[017]:8直接前驱7的直接前驱憎输入兀素7元素是3线性表中元素7的直接前驱元索是3PriorElem获取82该元素不在线请选择你的操作[0~17]:8语输入元素2该元素不直接前驱性表中在线性表中Next日em获取93线性表中元素请选择你的操作[0~17]:9直接后继3的直接后继请输入元素3元素是7线性及中元素3的直接后继元索是797NextElem获取该元素无直接请选择你的操作[0~17]:9请输入元素7该元素无直接后继后继直接后继92NextElem获取该元素不在线请选择你的操作[0~17]:9清输入元素2该元素不直接后继性表中在线性表中ListDelete删除元素112删除元素成|谛选择你的操作功,被删除元请输入删除的元素位置:2眄除元素成功,被删除元素为
7.当前线性衣的长度为1素为
7.当前线性表的长度为1元素位置不ListDelete删除110心心土口/A请选择你的操作[0~17]请编入删除的元素位置0元素元素位置不合法元素位置不ListDelete删除113心心土口/A请选择你的操作[0~1元素7]:11请输入加除而元衰位置3元素位置不合法Listinsert插入在第一个元素后依次插入5791123等5个元素,过程截图略元素12357911ListTraverse遍历线性表23请选择你的操作
[017]:1235791123SaveList保存13test文件成功保存请选择你的操作
[017]:13文件至test请输入文件保存路径或文件名test文件成功保存至test1test U实验.cpp9华中科技大学计算机学院数据结构实验报告DestroyList销毁2线性表销毁线性表成功请选择你的操作[0~17]:2线性表销毁成功ListTraverse遍12线性表未创建历线性表请选择你的操作[0~17]:12线性衣未创建LoadList加载14test文件成功加载请选择你的操作[0~17]:14文件至当前线性表请输入待加载文件路径或文件名test文件成功加载至当前线性表ListTraverse遍12357911请选择你的操作[0~17]:12历线性表2335791123iaohong123Add List添加1513其余X请选择你的操作15讲选择从文件加载0或键盘输入D1请输入要添加的线输入见截Xiaogang线性表性衣个数3Xiaoming请依次输入线性表名称和线性衣元萦图Xiaohong1230Xiaogang0Xiaoming0插入线样表完毕当前管理衣为:Xiaohong123Xiaogang XiaomingRemoveList移16删除线性表失请选择你的操作[0~17]:16除线性表Xiaoxiao败请输入要删除的线性衣名称Xiaoxiao删除线性太失败RemoveList移16Xiaogan Xiaohong123请选择你的操作
[017]:16除线性表g Xiaoming请输入要删除的线性表名称Xiaogang Xiaohong123Xiaoming LocateList查找17该线性表不在请选择你的操作[0~17]:17线性表Xiaogan g此管理表中而输入要我防线性走名称:Xi aogang该线性表不在此管理表中17Xiaohong123LocateList查找请选择你的操作[0~17]:17Xiaohon清输入要《我而线性衣名祢:Xi aohong线性表Xiaohong123g12123ListTraverse遍请选择你的操作
[017]:12历线性表123退出系统0盾选择你的操作
[017]:0Welcome touse thissystem againnext time!Process exitedafter
116.8seconds withreturn value0请按任意键继续...10华中科技大学计算机学院数据结构实验报告
1.5实验小结在实验中,我遇到了如下几个错误
(1)在功能演示系统中,调用插入元素函数时将参数写反,导致出错,由于自己在测试时使用的数据中位置和元素一样未发现错误,后来在助教检查时方测试出来这也给我提了醒,以后在测试时要尽量使测试数据随机
(2)在添加case语句时,由于忘记添加break而导致了两个函数的测试过程相连接,经过同学提醒才意识到这一点
(3)在代码健壮性方面,未能及时添加文件是否打开成功,文件指针的释放等代码,尽管在测试中可能影响不大,但在实际应用中可能是隐患同时,对于判断分配空间是否成功这一点也是在后来优化代码时添加的
(4)在代码优化部分,在对多线性表的管理程序的测试时发现每次输入数据过程繁琐,因此添加了从文件读入的选择,大大节省了测试时间在以后的实验中,也要注意使用文件输入来进行测试11华中科技大学计算机学院数据结构实验报告2基于链式存储结构的线性表实现
2.1问题描述该实验要解决的基本问题是实现单链表的各个基本功能,如初始化表、销毁表、清空表、判定空表、求表长和获得元素等等其中,在主程序中完成函数调用所需实参值的准备和函数执行结果的显示可选择以文件的形式进行存储和加载,也即将生成的单链表存入到相应的文件中,也可以从文件中获单链表进行操作
2.
1.1需实现的基本运算依据最小完备性和常用性相结合的原则,以函数形式定义了单链表的初始化表、销毁表、清空表、判定空表、求表长和获得元素等17种基本运算,具体运算功能定义如下⑴初始化表函数名称是InitListL;初始条件是单链表L不存在;操作结果是构造一个空的单链表⑵销毁表:函数名称是DestroyListL;初始条件是单链表L已存在;操作结果是销毁单链表Lo⑶清空表:函数名称是ClearListL;初始条件是单链表L已存在;操作结果是将L重置为空表⑷判定空表函数名称是ListEmptyL;初始条件是单链表L已存在;操作结果是若L为空表则返回TRUE,否则返回FALSEo⑸求表长函数名称是ListLengthL;初始条件是单链表已存在;操作结果是返回L中数据元素的个数⑹获得元素函数名称是GetElemL,i,e;初始条件是单链表已存在,l^i^ListLengthL;操作结果是用e返回L中第i个数据元素的值⑺查找元素函数名称是LocateElemL,e,compare;初始条件是单链表己存在;操作结果是返回L中第1个与e满足关系compare关系的数据元素的位序,若这样的数据元素不存在,则返回值为0⑻获得前驱:函数名称是PriorElemL,cur_e,pre e;初始条件是单链表L12华中科技大学计算机学院数据结构实验报告己存在;操作结果是若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义⑼获得后继函数名称是NextElemL,cur_e,next_e;初始条件是单链表L已存在;操作结果是若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败,next,无定义⑩插入元素函数名称是Listinsert L,i,e;初始条件是单链表L已存在,lWiWListLengthL+l;操作结果是在L的第i个位置之前插入新的数据元素e ID删除元素函数名称是元stDeleteL,i,e;初始条件是单链表L已存在且非空,iWiWListLcngthL;操作结果删除L的第i个数据元素,用e返回其值⑫遍历表:函数名称是ListTraverseL,visit,初始条件是单链表L己存在;操作结果是依次对L的每个数据元素调用函数visito⑬保存单链表函数名称是5@丫0以51亿卢”6岫田,初始条件是单链表1已存在;操作结果是将单链表元素按顺序保存至文件名为FileName的文件中⑷加载单链表函数名称是LoadList L,FileName,初始条件是单链表L不存在;操作结果是将文件名为FileName的文件加载到单链表中⑮在管理表中插入一个单链表函数名称是AddList Lists,ListName,无初始条件;操作结果是将文件名为ListName的单链表添加到管理表中⑹在管理表中删除一个单链表函数名称是RemoveList Lists,ListName,初始条件是多单链表非空;操作结果是将文件名为ListName的单链表删除17在管理表中查找一个单链表:函数名称是LocateList Lists,ListName,初始条件是多单链表非空;操作结果是查找文件名为ListName的单链表并可对其进行操作
2.2系统设计本次实验的系统设计如下将菜单演示和用户选择写入到while循环中,用0P获取用户的选择,0P初始化为1,以便第一次能进入循环进入循环后系统首先显示功能菜单,然后用户输入选择0T7,其中1T7分别代表对单链表13华中科技大学计算机学院数据结构实验报告或单链表的管理表的一个基本运算,在主函数中通过switch语句对应到相应的函数功能,执行完该功能后break跳出switch语句,继续执行while循环,直至用户输入0退出当前演示系统(演示系统结构如图2T所示)Menu forLinear TableOn SequenceStructure
1.InitList
10.Listinsert
2.DestroyList
11.ListDelete
3.ClearList
12.ListTraverse
4.ListEmpty
13.SaveList
5.ListLength
14.LoadList
6.GetElem
15.AddList
7.LocateElem
16.RemoveList
8.PriorElem
17.LocateList
9.NextElem
0.Exit请选择你的操作[
0、17]图27演示系统结构图本次实验使用的数据结构定义为#defme TRUE1#define FALSE0#define OK1#define ERROR0#define INFEASIBLE-1#define OVERFLOW-2#dcfine LIST_INIT_SIZE10#define LISTINCREMENT1typedef intstatus;typedef intElemType;〃数据元素类型定义typedef struct LNode{//单链表链式结构结点的定义ElemType data;structLNode*next;LNodc,*LinkList;typedef struct{〃单链表的管理表定义struct{char name
[30];LinkList L;华中科技大学计算机学院数据结构实验报告}elem
[10];int length;}LISTS;
2.3系统实现单链表运算算法思想与设计如下⑴初始化单链表思想将单链表初始化过程写成函数,其中传入函数的参数是主函数中定义的结构型变量L的引用在函数中,首先判断L是否创建,如果未创建则使用malloc函数分配一个结点的内存空间,并把L的next指针域置为空经分析,算法的时间复杂度为01⑵销毁单链表思想将销毁单链表的过程写成函数,其中传入函数的参数是主函数中定义的结构性变量L的引用在函数中,使用循环依次将每个结点的内存空间释放,最后将头指针置为空经分析,该算法的时间复杂度为0n o⑶清空单链表的思想将清空单链表的过程写成函数,其中将主函数中定义的结构性变量L的引用作为函数参数在函数中,使用循环从头结点开始依次释放内存,最后将L的指针域置为空经分析,该算法的时间复杂度为0n o⑷求单链表表长的思想将求表长过程写成函数,其中主函数中定义的结构性变量L的引用作为函数的参数,在函数中,通过循环和计数变量记录结点数,最后返回计数结果即为表长经分析,该算法的时间复杂度为0n⑸获得元素的算法思想将获得单链表元素写成函数,其中函数的参数是结构型变量L以及数据元素的序号i,由于采取的是链式存储结构,故通过循环依次访问结点并比较数据域的方式来获取元素,当然,如果位置不合法应返回ERRORo经分析,该算法的时间复杂度为0n⑹查找元素的算法思想将查找单链表特定值的数据元素写成函数,其中函数的参数是主函数中定义的结构类型变量L以及查找的数据元素的值,通过循环对单链表中的每一个结点的数据域与给定值比较是否相等,如果相等就返回该元素的位置经分析,该算法的时间复杂度为0n15华中科技大学计算机学院数据结构实验报告⑺获得直接前驱算法思想将获得直接前驱元素的过程写成函数,函数的参数是结构体类型变量以及特定数据元素的值,接受前驱的变量在函数中,首先判断单链表是否为空,若不为空则通过循环遍历元素比较,如果头结点元素即为所找元素则表明无直接前驱,如果头结点不是则用另一个指针指向当前遍历结点的前一个结点,当找到元素时将前一个结点的值赋给pre,若找不到则返回ERROR经分析,该算法的时间复杂度为0n⑻获得直接后继算法思想将获得直接后继元素的过程写成函数,函数的参数是结构体类型变量以及特定数据元素的值,接受后继的变量在函数中,首先判断单链表是否为空,若不为空则通过循环遍历元素比较,当找到元素时将后一个结点的值赋给next,若该元素对应最后一个结点则表明无直接后继,若找不到元素则返回ERROR经分析•,该算法的时间复杂度为0n⑼插入元素算法思想将插入元素写成函数,函数的参数是结构型变量的引用,插入元素的值以及插入位置在函数中,首先判断插入位置的合法性,即是否在单链表中合适的位置,插入元素时如果单链表结点数为,则直接令L指向新创建的待插入结点,若不是则先定位至插入位置处更改结点的指针域来实现插入经分析,该算法的时间复杂度为n⑩删除元素算法思想将删除单链表中元素写成函数,函数的参数是结构类型变量的引用,待删除元素的位置,接受待删除元素的变量在函数中,先定位至待删除元素的位置.,将其赋值给接受变量,然后通过改变指针域移除该结点,最后释放该结点的内存空间经分析,该算法的时间复杂度为0n ID遍历单链表算法思想将遍历单链表写成一个函数,函数的参数是结构类型变量,直接用一个循环来对单链表中的每一个元素进行操作此处进行输出操作经分析,该算法的时间复杂度为0n⑫保存单链表到文件中的算法思想函数的参数是结构体变量L和待保存文件的路径或名称在函数中,创建一个指向待保存文件的文件指针,通过循环依次将单链表中的数据写入文件中经分析,该算法的算法复杂度是0n⑬加载文件到单链表中的算法函数的参数是结构体变量L的引用和待加载文件的路径在函数中,创建一个指向待加载文件的文件指针,并根据读写逐个分配单链表L中结点的内存空间,最后将尾结点的指针域置为空并释放文16华中科技大学计算机学院数据结构实验报告件指针经分析,该算法的算法复杂度是0n14插入一个单链表算法思想函数的参数是管理表的引用和待插入单链表的名称在函数中,先在已存在的管理表中的末尾处开辟新的单链表的存储空间,并将管理表长度增加L经分析,该算法的时间复杂度是01⑸删除一个单链表算法思想函数的参数是管理表的引用和待删除单链表的名称在函数中,通过循环比较单链表名称和待删除单链表的名称,如果没有找到则返回ERROR,否则就先摧毁待删除单链表,然后自该位置起从前往后将下一个单链表复制到前一个单链表中经分析,该算法复杂度是0r16定位一个单链表算法思想函数参数是管理表Lists和待查找的单链表名称在函数中,通过循环比较待查找单链表名称和管理表中单链表的名称,如果匹配成功则返回该单链表位序,否则返回ERROR经分析,该算法复杂度是0n
2.4系统测试输入样例解释第一个数字为测试序号,代表该测试序号所调用的函数;然后是需要输入的数据函数输入预期输出实际输出2DestroyList销毁单链表未创建,单链表无需销毁请选择你的操作[0~17]:2单链表未创建,无需销毁ClearList清空3请选择你的操作[0」7]:3单链表单链表未创建,单链表未创建,单链表清除失败单链表清除失败ListLength求表5单链表未创建长请选择你的操作[0~17]:5单链表未创建.1单链表创建成功清选择你的操作
[017]:1单链表创建成功InitList创建单1单链表已创建请选择你的操作单链衣己创建链表ListEmpty判空4单链表为空表请选择你的操作[0〜17]:4单链表为空表ListLength求表5单链表的长度长为0请选择你的操作[0~17]:5单链表的长度为0Listinsert插入1031插入元素成功,请选择你的操作
[017]:10元素当前单链表的长请输入插入的元素及插入的位置31插入元素成功.当前单链衣的长度为1度为117华中科技大学计算机学院数据结构实验报告Listinsert插入1052插入元素成功,请选择你的操作[0~17]:10元素当前单链表的长清输入插入的元素及插入的位置52度为2插入元素成功.当前单链女的长度为21074Listinsert插入元素位置不合请选择你的操作[0~17]:10元素法i背输入插入的元素及插入的位置74元素位置不合法Listinsert插入1073插入元素成功,请选择你的操作[
[017]:9直接后继的直接后继元素请输入元素3是5单链表中元素3的直接后继元素是594NextElem获取该元素不在单链请选择你的操作
[017]:9清输入元素4该元素呆在单链表中直接后继表中ListDelete删除110元素位置不合法请选择你的操作[0~17]:11清输入删除的元素位置0元知立置元素彳、合疾ListDelete删除元素114元素位置不合法请选择你的操作请输入删除的元素位置4元素位置不合法ListDelete删除112删除元素成功,被元素删除元素为5,当前单链表的长度为1请选择你的操作[0~17]请输入丽除药元素位置:2删除元索成功,被删除元索为5,当前单链表的长度为2Listinsert插入元素依次调用插入函数使单链表结点的数据域依次为3571113171923等8个元素,过程截图略ListTraverse遍历单链表123571113171923请选择你的操作[
0、17]:123571113171923SaveList保存文件13LinkList文件成功保存至LinkList请选择你的操作
[017]:13请输入文件保存路径或文件名:LinkList女件成功俅存室LinkList□LinkList2021/5/1921:50』基于链式存储结构的线性表功能演示系统.cpp2021/5/1921:46DestroyList销毁单链表2单链表销毁成功请选择你的操作[0~17]:2单链表销毁成功ListTraverse遍历单链表12单链表未创建请选择你的操作[0~17]:12单链表条蓟建Load List加载文件14LinkList文件成功加载至当前单链表请选择你的操作
[017]:14请输入待加载文件路径或文件名:LinkList文件成功加载至当前单链表ListTraverse遍历单链表123571113171923请选择你的操作[0~17]:123571113171923Add List添加单链表150d:\\lists.t xtLihua9883966788Liming9934132364668Ligang87573782968423598Lixiao345667请选择你的操作[0~17]:15请选择从文件加载0或键盘输入10请输入待加载文件路径或文件名:d:\\lists.txt插入单链表完毕当前管理表为Lihua9883966788Liming9934132364668Ligang87573782968423598Lixiao3456677889901234234519华中科技大学计算机学院数据结构实验报告78899012342345RemoveList移16Lihua988396请选择他的操作[0~17]:16除单链表Liming6788Ligang清输入要删除的小链正名称:L im ing875737829Lihua988396678868423598Ligang87573782968423598Lixiao345667Lixiao3456677889901234234578899012342345RemoveList移16删除单链表失败请选择你的操作[0~17]:16清输入要删除的单链衣名称:Lihong除单链表Lihong删除单链表失败17LocateList查该单链表不在此请选择你的操作[0~17]:17Liming找单链表管理表中请输入要去找的中链衣名称:L iming该单链式不在此管理表中LocateList查17Ligang8757请选择你的操作[0~17]:17找单链表Ligang378296842话输入耍荏我的单链袤名称Li gang3598Ligang87573782968423598ListTraverse遍12875737829卜青选择你的操作
[017]:12历单链表6842359887573782968423598退出系统而选择你的操作
[017]:00Welcome touse thissystem againnext time!Process exitedafter
111.9seconds withreturn value0请按任意键继续...
2.5实验小结在实验中,我遇到了如下几个错误1在写各个函数的代码中,总是因为混淆L和L-next而导致程序总是出现千奇百怪的输出结果,后来重新看了一遍关于单链表的结点的有关知识才避免了各种错误,这告诉我,在处理一种数据结构之前先要了解其逻辑结构2在编写程序时,我有几次都忘记了要释放链表中不需要的结点或者文件指针这与上次实验中我犯的错误有相似之处,我会吸取教训,不再给代码埋下这种隐患20华中科技大学计算机学院数据结构实验报告3基于二叉链表的二叉树实现
3.1问题描述该实验要解决的基本问题是实现二叉链表的各个基本功能,如创建、销毁、清空、判空二叉树,求二叉树深度,查找结点,结点赋值,获得兄弟结点,插入和删除结点,前中后序遍历及其非递归算法,按层遍历等其中,在主程序中完成函数调用所需实参值的准备和函数执行结果的显示可选择以文件的形式进行存储和加载,也即将生成的二叉链表存入到相应的文件中,也可以从文件中获取二叉链表进行操作同时也实现了多树管理
3.
1.1需实现的基本运算依据最小完备性和常用性相结合的原则,以函数形式定义了二叉树的创建二义树、销毁二叉树、清空二又树、判定空二叉树和求二又树深度等22种基本运算同时又添加了求结点个数,获得父结点,获取从叶子结点到根结点的路径等功能具体运算功能定义和说明如下⑴创建二叉树函数名称是CrealeBiTreeT,definition;初始条件是definition给出二叉树T的定义,如带空子树的二叉树前序遍历序列、或前序+中序、或后序+中序;操作结果是按definition构造二叉树T注
①要求T中各结点关键字具有唯一性后面各操作的实现,也都要满足一棵二叉树中关键字的唯一性,不再赘述;
②Create BiTree中根据definition生成T,不应在Create BiTree中输入二叉树的定义⑵销毁二叉树函数名称是DestroyBiTreeT;初始条件是二叉树T已存在;操作结果是销毁二叉树T⑶清空二叉树函数名称是ClcarBiTrccT;初始条件是二叉树T存在;操作结果是将二叉树T清空⑷判定空二叉树函数名称是BiTreeEmptyT;初始条件是二叉树T存在;操作结果是若T为空二叉树则返回TRUE,否则返回FALSEo⑸求二叉树深度函数名称是BiTreeDepthT;初始条件是二叉树T存在;操作结果是返回T的深度21华中科技大学计算机学院数据结构实验报告⑹查找结点函数名称是LocateNodeT,e;初始条件是二叉树T已存在,e是和T中结点关键字类型相同的给定值;操作结果是返回查找到的结点指针,如无关键字为e的结点,返回NULL⑺结点赋值函数名称是Assign,e,value;初始条件是二叉树T已存在,e是和T中结点关键字类型相同的给定值;操作结果是关键字为e的结点赋值为value o⑻获得兄弟结点函数名称是GetSiblingT,e;初始条件是二叉树T存在,e是和T中结点关键字类型相同的给定值;操作结果是返回关键字为e的结点的左或右兄弟结点指针若关键字为e的结点无兄弟,则返回NULL⑼插入结点函数名称是InscrtNodeT,e,LR,c;初始条件是二叉树T存在,e是和T中结点关键字类型相同的给定值,LR为或I,c是待插入结点;操作结果是根据LR为或者1,插入结点c到T中,作为关键字为e的结点的左或右孩子结点,结点e的原有左子树或右子树则为结点c的右子树特殊情况,c插入作为根结点?可以考虑LR为・1时,作为根结点插入,原根结点作为c的右子树⑩删除结点函数名称是DclctcNodcT,e;初始条件是二叉树T存在,c是和T中结点关键字类型相同的给定值操作结果是删除T中关键字为e的结点;同时,如果关键字为e的结点度为0,删除即可;如关键字为e的结点度为1,用关键字为e的结点孩子代替被删除的e位置;如关键字为e的结点度为2,用e的左孩子代替被删除的e位置,e的右子树作为e的左子树中最右结点的右子树Q1前序遍历函数名称是PreOrderTraverseT,Visit;初始条件是二叉树T存在,Visit是一个函数指针的形参可使用该函数对结点操作;操作结果先序遍历,对每个结点调用函数Visit一次且一次,一旦调用失败,则操作失败注前序、中序和后序三种遍历算法,要求至少一个用非递归算法实现⑫中序遍历函数名称是InOrderTraverseT,Visit;初始条件是二叉树T存在,Visit是一个函数指针的形参可使用该函数对结点操作;操作结果是中序遍历I,对每个结点调用函数Visit一次且一次,一旦调用失败,则操作失败⑶后序遍历函数名称是PostOrderTraverseT,Visit;初始条件是二叉树T22华中科技大学计算机学院数据结构实验报告存在,Visil是一个函数指针的形参可使用该函数对结点操作;操作结果是后序遍历t,对每个结点调用函数Visil一次且一次,一旦调用失败,则操作失败按层遍历函数名称是LevclOrdcfTraverseT,Visit;初始条件是二叉树T存在,Visit是对结点操作的应用函数;操作结果是层序遍历3对每个结点调用函数Visit一次且一次,一旦调用失败,则操作失败⑮保存文件函数名称是LevelOrderTraverseT,FileName;初始条件是二叉树T存在;操作结果是将二叉树结点按definition对二叉树的定义保存至文件名为FileName的文件中16加载文件函数名称是LevelOrderTraverseT,FileName;初始条件是二叉树T存在;操作结果是将文件名为FileName的文件加载到二叉链表中17求结点个数函数名称是CountNode T;初始条件是二叉树T存在;操作结果是得到二叉树中结点的数目⑻获得父结点函数名称是GetParent T,e;初始条件是二叉树T存在;操作结果是找到关键字为e的结点并获得其父结点,否则返回NULLo⑲插入一个树函数名称是AddTreeTrees,TreeName;初始条件是多树管理表Trees存在;操作结果是在该管理表中插入一个二叉树Q0删除一个树函数名称是RemoveTreeTrees,TreeName;初始条件是多树管理表Trees存在;操作结果是在该管理表中删除和TreeName相同名称的二叉树,若没有匹配的树返回ERROR21查找一个树函数名称是LocateTreeTrees,TreeName;初始条件是多树管理表Trees存在;操作结果是在该管理表中查找和TreeName相同名称的二叉树并定位至该树对其进行操作,若没有匹配的树返回ERRORo22获得叶子结点到根结点的路径:函数名称是PrintPath T,path,pathlen;初始条件是二叉树T存在;操作结果是输出每个叶子结点到根结点的路径
3.2系统设计本次实验的系统设计如下将菜单演示和用户选择写入到while循环中,用0P获取用户的选择,0P初始化为1,以便第一次能进入循环进入循环后系统首先显示功能菜单,然后用户输入选择0-24,其中1-24分别代表对二叉链23华中科技大学计算机学院数据结构实验报告表的一个基本运算,在主函数中通过switch语句对应到相应的函数功能,执行完该功能后break跳出switch语句,继续执行while循环,直至用户输入0退出当前演示系统(演示系统结构如图3-1所示)Menu forLinear TableOn SequenceStructure
1.CreateBiTree ClearBiTree
3.BiTreeDepth LocateNode
5.Assign GetSibling
7.InsertNode DeleteNode
9.PreOrderTraverse PreOrderTraverse_recursive
11.InOrderTraverse InOrderTraverse_recursive
13.PostOrderTraverse PostOrderTraverse_recursive SaveBiTree
15.LevelOrderTraverse
17.LoadBiTree
18.CountNode
19.GetParent
20.AddTree
21.RemoveTree
22.LocateTree
23.EmptyTree
24.PrintPath输出所有叶子站点到根站点的路径请选择你的操作[0~24]:图3T演示系统结构图本次实验使用的数据结构定义为#define TRUE1#define FALSE0#define OK1#dcfinc ERROR0#define INFEASIBLE-1#define OVERFLOW-2typedef intstatus;typedef intKey Type;typedef structKey Typekey;char othcrs[20J;}TElemType;〃二叉树结点类型定义TEleinType definition!100];typedef struct BiTNode{〃二叉链表结点的定义TElemType data;structBiTNode*lchild,*rchild;BiTNode,*BiTree;24华中科技大学计算机学院数据结构实验报告
24.O.Z
4.S1A1A1±IX typedef struct〃二叉链表的管理表定义struct{char name
[30];BiTree T;}elem
[10];intlength;LISTS;
3.3系统实现二叉链表运算算法思想与设计如下⑴创建二叉链表思想将利用前序带空输入方式创建二叉链表过程写成函数,其中传入函数的参数是主函数中定义的结构型变量T的引用在函数中,先判断是否有关键字冲突的情形,如果有返回ERROR;若关键字不冲突,则判断结点是否为空,若不为空则赋值并递归创建左右子树,若为空则将结点指针赋为空经分析,算法的时间复杂度为0r⑵清空二叉链表思想将清空二叉链表的过程写成函数,其中传入函数的参数是主函数中定义的结构性变量T的引用在函数中,首先判断树是否为空,如果为空则无需清空,如果不为空那么递归清空根结点的左右子树最后释放根结点,并将T置为空经分析,该算法的时间复杂度为0n⑶求二义链表深度的思想将求深度过程写成函数,其中主函数中定义的结构性变量T作为函数的参数在函数中,先判断树是否为空,为空则返回深度0,若不为空,递归计算左右子树的深度,最后取左右子树深度的最大值加1为二叉树的深度经分析,该算法的时间复杂度为02⑷查找元素的算法思想将查找二叉链表元素写成函数,其中函数的参数是结构型变量T以及待查找结点的关键字°在函数中若树不为空则递归查找结点及其左右子树,如果查找成功就返回查找到的结点的指针,否则返回NULLo经分析,该算法的时间复杂度为0n⑸给某个结点赋值的算法思想将给树中的某个结点赋值的操作写成函数,其中函数的参数是主函数中定义的结构类型变量T的引用,待查找的结点的关键字e以及赋值数据项value通过递归算法查找待赋值的关键字同时判25华中科技大学计算机学院数据结构实验报告断赋值后的关键字是否与树中的关键字冲突,查找成功则进行赋值,否则返回ERRORo经分析,该算法的时间复杂度为0n⑹获得兄弟结点算法思想将获得兄弟结点的过程写成函数,函数的参数是结构体类型变量T以及待查找其兄弟结点的结点的关键字在函数中,首先判断二叉链表是否为空,若不为空则判断当前结点是否有左右孩子及左右孩子是否为待查找结点,若是则返回兄弟结点,若不是则递归进行查找,若查找失败则返回NULL经分析,该算法的时间复杂度为0n⑺插入一个结点算法思想将插入一个结点的过程写成函数,函数的参数是结构体类型变量T的引用,待插入位置的结点的关键字,插入方式LR,待插入结点的数据在函数中,首先判断树是否为空,若不为空则先创建待插入的结点,找到待插入位置的结点,判断待插入结点的关键字是否与原有树中的结点的关键字是否冲突,如果未找到结点或者关键字冲突则返回INFEASIBLE或ERROR,否则根据LR的不同分别做插入操作经分析,该算法的时间复杂度为0n o⑻删除结点算法思想将删除结点写成函数,函数的参数是结构型变量T的引用,待删除结点的关键字在函数中,首先树是否为空,若不为空则先获得关键字为的结点及其父结点,并计算待删除结点的度若度为0,则直接将父结点的对应孩子置为空并释放被删除结点,若度为1,则判断被删除结点是父结点的左孩子还是右孩子并分别做删除操作,若度为2,则将父结点的对应孩子置为待删除结点的左孩子,并通过循环操作找到待删除结点的左子树的最右结点,并将右子树连接至此其中,每种情况均需要对待删除结点是根结点的情况进行特判经分析,该算法的时间复杂度为0n⑼前序遍历算法思想将对二叉树的前序遍历过程写成函数,函数的参数是结构类型变量T,遍历二叉树结点的visit函数的指针对于递归算法,在函数中,首先判断树是否为空,若不为空则通过访问根结点,遍历左子树,遍历右子树的过程实现递归遍历对于非递归算法,则利用栈的存储结构,依次将根结点,左子树,右子树入栈并出栈的循环操作实现遍历经分析,递归与非递归算法的时间复杂度均为0n⑩中序遍历算法思想将对二叉树的中序遍历过程写成函数,函数的参数26华中科技大学计算机学院数据结构实验报告是结构类型变量T,遍历二叉树结点的visit函数的指针对于递归算法,在函数中,首先判断树是否为空,若不为空则通过遍历左子树,访问根结点,遍历右子树的过程实现递归遍历对于非递归算法,则利用栈的存储结构,通过将结点按顺序入栈并出栈的操作实现遍历经分析,递归与非递归算法的时间复杂度均为0n ID后序遍历算法思想将对二叉树的后序遍历过程写成函数,函数的参数是结构类型变量T,遍历二叉树结点的visit函数的指针对于递归算法,在函数中,首先判断树是否为空,若不为空则通过访问根结点,遍历左子树,遍历右子树的过程实现递归遍历对于非递归算法,则利用栈的存储结构,通过将结点按顺序入栈并出栈的操作实现遍历其中,后序遍历比前两种遍历的非递归实现都要复杂原因是,我们访问完左结点后,弹栈时并不能立即访问根结点的值,因为遍历顺序为左->右-〉根,在访问根结点之前,我们还要确定根结点的右子树是否己经被访问过因此可以利用flag来判断此结点是从左孩子结点还是右孩子结点来的经分析,递归与非递归算法的时间复杂度均为0n o⑫按层遍历算法思想将对二叉树的按层遍历过程写成函数,函数的参数是结构类型变量T,遍历二叉树结点的visit函数的指针在函数中,利用循环队列的数据结构来实现遍历首先将根结点入队,接着通过判断队列是否为空来控制循环,在循环中,先将队首结点出队并访问,同时将其左右孩子依次入队经分析,该算法的时间复杂度均为0n⑬保存文件算法思想函数的参数是结构类型变量T和待保存文件的名称在函数中,利用前序遍历的非递归算法过程依次将各个结点通过带空前序遍历序列的方式输出到文件FileName中经分析,该算法的时间复杂度是0n o⑷加载文件到二叉链表算法思想函数的参数是结构类型变量T和待加载文件的名称在函数中,先将文件读入到definition数组中,接着利用该数据定义创建二叉树经分析,该算法的时间复杂度是0n Q5添加一个二叉树的算法思想函数参数是管理表Trees和待添加的二叉链表名称在函数中,通过与创建二叉树类似的过程在Trees中添加一个二叉27华中科技大学计算机学院数据结构实验报告树经分析,该算法复杂度是0南⑯删除一个二叉树的算法思想函数参数是管理表Trees的引用和待删除的二叉链表名称在函数中,通过循环比较名称查找到待删除的二叉树,利用清空函数清空树,并利用循环从后至前覆盖被删除的二叉树经分析,该算法复杂度是050判空二又链表的思想将判空二叉链表的过程写成函数,其中将主函数中定义的结构性变量T的引用作为函数参数在函数中,如果T=NULL则表明树为空返回0K,否则返回ERROR经分析,该算法的时间复杂度为0118查找一个二叉树的算法思想函数参数是管理表Trees和待查找的二叉链表名称在函数中,通过循环比较名称查找到待删除的二叉树,并定位至该树,返回该树的位置,若未找到则返回ERROR经分析,该算法复杂度是0n o⑲计算结点数目的算法思想函数参数是结构体变量T在函数中,通过递归遍历左右子树将存放结点数目的变量依次增加,最终得到结点数目经分析,该算法复杂度是06⑳获得父结点的算法思想将获得父结点的过程写成函数,函数的参数是结构体类型变量T以及待查找其父结点的结点的关键字在函数中,首先判断二叉链表是否为空,若不为空则判断当前结点是否有左右孩子及左右孩子是否为待查找结点,若是则返回该结点,若不是则递归进行查找,若查找失败则返回NULL经分析,该算法的时间复杂度为0n
3.4系统测试说明输入样例解释第一个数字为测试序号,代表该测试序号所调用的函数;然后是需要输入的数据该全局测试所用的二叉树如图3-2和3-3图3-2用到的二叉树128华中科技大学计算机学院数据结构实验报告1基于顺序存储结构的线性表实现
1.1问题描述该实验要解决的基本问题是实现线性表的各个基本功能,如初始化表、销毁表、清空表、判定空表、求表长和获得元素等等其中,在主程序中完成函数调用所需实参值的准备和函数执行结果的显示可选择以文件的形式进行存储和加载,也即将生成的线性表存入到相应的文件中,也可以从文件中获取线性表进行操作
1.
1.1需实现的基本运算依据最小完备性和常用性相结合的原则,以函数形式定义了线性表的初始化表、销毁表、清空表、判定空表、求表长和获得元素等17种基本运算,具体运算功能定义如下⑴初始化表函数名称是InitListL;初始条件是线性表L不存在;操作结果是构造一个空的线性表⑵销毁表:函数名称是DestroyListL;初始条件是线性表L已存在;操作结果是销毁线性表Lo⑶清空表:函数名称是ClearListL;初始条件是线性表L已存在;操作结果是将L重置为空表⑷判定空表函数名称是ListEmptyL;初始条件是线性表L已存在;操作结果是若L为空表则返回TRUE,否则返回FALSEo⑸求表长函数名称是ListLengthL;初始条件是线性表已存在;操作结果是返回L中数据元素的个数⑹获得元素函数名称是GetElemL,i,e;初始条件是线性表已存在,l^i^ListLengthL;操作结果是用e返回L中第i个数据元素的值⑺查找元素函数名称是LocateElemL,e,compare;初始条件是线性表己存在;操作结果是返回L中第1个与e满足关系compare关系的数据元素的位序,若这样的数据元素不存在,则返回值为0⑻获得前驱:函数名称是PriorElemL,cur e,pre e;初始条件是线性表L华中科技大学计算机学院数据结构实验报告输入的前序带空序列为1a2bo null3c4d0null0null0null5e6f0null0null7g0null0null-1nul1图3-3用到的二叉树2输入的前序带空序列为1a2bo null0null3c4d0null0null5e0null0null-1null调用函数输入预期输出实际输出ClearBiTree清2无需清空请选择你的操作[0~24]:2二叉链表己空,无需清空空二叉树1二叉树二叉链表创建成功CreateBiTre e1的输入请选择你的操作[
0、24]:1创建二叉链表序列”请依次输入各结点的关键字和数据1a2b0null3c4d0null0null0null5e6f0null0(该树为二叉null7g0null0null-1null树1)二义链表创建成功BiTreeDept h求3二叉树的深度为4清选择你的操作[0~24]:3二叉树的深度为4深度PreOrderTr9l,a2,b3,c4,d5,e6,f请选择你的操作
[024]:9averse前序遍7,g1,a2,b3,c4,d5,e6,f7,g历InOrderTra112,b4,d3,c l,a6,f请选择你的操作
[024]:U verse中序遍5,e7,g2,b4,d3,c1,a6,f5,e7,g历PostOrderT144,d3,c2,b6,f7,g5,e l.a请选择你的操作[0~24]:14reverse后序4,d3,c2,b6,f7,g5,e1,a非递归算法遍历LevelOrder15l.a2,b5,e3,c6,f Traverse按层7,g4,d请选择你的操作
[024]:151,a2,b5,e3,c6,f7,g4,d遍历CountNode求18二叉树中结点个数为结点数目7请选择你的操作[
0、24]:18二叉树中结点个数为7EmptyTree判23二叉树不为空请选择你的操作
[024]:23二叉树不为空空树29华中科技大学计算机学院数据结构实验报告LocateNod e查45该结点为
5.e请选择你的操作[0〜24]:4请输入待杳找结点的关键字:5该结点为5,e找结点LocateNod e查48查找失败,二叉链表请选择你的操作[
0、24]:4请输入待代找结点的关键字:8查中无此结点找失败,二义链表中无此结点找结点GetSibling查找61无兄弟结点请选择你的操作[0~24]:6请输入待查找结点的关键字1无兄弟结点兄弟结点GetSibling查找62兄弟结点为5,e请选择你的操作[0〜24]:6请输入待查找结点的关键字2兄弟结点兑用结点为5,e68GetSibling查找二叉链表中无待查找请选择你的操作[0~24]:6兄弟结点结点请输入待杳找结点的关键字8二文铺装中无待往及结点GetParent查找191二叉链表中无待查找请选择你的操作[0~24]:19父结点结点或查找结点为根请输入待查找结点关键字却结点二叉链衣中无待杳找结点或有找结点为根结点19234GetParent查找二叉链表中无待查找请选择你的操作
[024]:19父结点结点或查找结点为根请输入待杳找结点关键字234结点:又链表中无待杳找结点或查找结点为根结点197GetParent查找5,e请选择你的操作
[024]:19请输入待查找结点关键字7父结点5,e Assign赋值51010赋值失败,二叉链表请选择你的操作[
0、24]:5new中无待查找结点请输入待杳找结点的关键字10谙输入待赋值的结点数据10new赋值失败,二义链表中无待查找结点Assign赋值532赋值失败,待赋值的请选择你的操作[0~24]:5new结点关键字与当前二请输入待查找结点的美键字3请输入待赋值的结点数据:2new叉树中的结点关键字赋值失败,待赋值的结点关键字与当前二叉树中的结点关冲突键字冲突Assign赋值577赋值成功请选择你的操作[0~24]:5new请输入待代找结点的关键字7请输入待赋值的结点数据:7new赋值成功PreOrderTr9l.a2,b3,c4,d5,e6,f请选择你的操作[0〜24]:9averse前序遍7,new1,a2,b3,c4,d5,e6,f7,new历InsertNode插7808old插入失败,无待查找请选择你的操作[0〜24]:7请输入待杳找结点关键字8请入结点结点输入插入结点方式:0请输入待插入结点的数据:8old插入失败,无待杳找结点30华中科技大学计算机学院数据结构实验报告InsertNode插7207old插入失败,待插入结请选择你的操作[0~24]:7请输入待杏找结点关健字:2入结点点与二叉链表中结点请输入插入结点方式0关键字冲突请输入待插入结点的数据7old插入失败,待插入结点二叉链衣中结点关键字冲突InsertNode插72-18root插入成功请选择你的操作[0~24]:7请输入待查找结点关键字2请筋入插入结点方式:T入结点请输入待插入结点的数据8root插入成功InsertNode插7319h插入成功请选择你的操作[0~24]:7请输入待行找结点关键字3请输入插入结点方式1请输入待插入结点的数据9h隔入成入结点功PreOrderTr averse前序遍历98,root l,a2,b3,c4,d9,h请选择你的操作[0~24]:95,e6,f8,root1,a2,b3,c4,d9,h5,e6,f7,new7,new DeleteNod e删除结点88成功删除结点请选择你的操作
[024]:8请输入待删除结点关键字8成功删除结点DeleteNod e删810该二叉链表中无该结请选择你的操作[0~24]:8请输入待删除结点关键字10该除结点点二叉链袅币元该结点DeleteNode删除结点89成功删除结点请选择你的操作[
0、24]:8请输入待删除结点关键字9成功删除结点PreOrderTr averse9l.a2,b3,c4,d5,e6,f7,new请选择你的操作[0~24]:91,a2,b3,c4,d5,e6,f7,new SaveBiTree保存文件16test成功保存至文件test请选择你的操作
[024]:16请输入文件名称test成功保存至文件test jtest U基于二叉链表的二叉脚实现《cpp ClearBiTree清空树2二叉链表清空成功请选择你的操作[
0、24]:2二叉链表清空成功BiTreeDept h求深度3二叉树的深度为0请选择你的操作[
0、24]:3二叉树的深度为0EmptyTree判空树23二叉树为空请选择你的操作[0~24]:23二义树为空PreOrderTr averse前序9由于二叉树已经清空,将无输出请选择你的操作[0~24]:9LoadBiTree加载文件17test成功加载文件test至二叉链表请选择你的操作[0~24]:17请输入文件名称:test血宓加载支择test至二叉链表31华中科技大学计算机学院数据结构实验报告PreOrderTr10l,a2,b3,c4,d5,e6,f请选择你的操作[
0、24]:10averse.recu7,new rsive1,a2,b3,c4,d5,e6,f7,InOrderTra122,b4,d3,c l,a6,f new请选择你的操作[024]:;verse_recur5,e7,new sive2,b4,d3,c1,a6,f5,e7,PrintPath输出244,d3,c2,b l,a new请选择你的操作[024]:24所有叶子结点6,f5,e l,a4,d3,c2,b1,a到根结点的路7,new5,e l,a6,f5,e1,a7,new5,e1,a径xiao AddTree添加202其余hong树输入数据l,a2,b3,c4,d5,e请选择你的操作[0~24]:202tb l,a4,d3,c5,e请输入要添加的义链及个数2见截图请依次输入,义链表名称和义链次结点xiaohong1a2b0xiaoming null0null3c4d0null0null5e0null0null_1l,a2,b3,c
4.d5,e nullxiaoming1a2b0null3c4d0null0null0null5e6f0null0null7g0n ull0null-1null
6.f7,g插入二义链表完毕2,b4,d3,c l,a6,f当前管理衣为(依次输出每个树的前序和中序遍历)xiaohong5,e7,g1,a2,b3,c4,d5,e2,b1,a4,d3,c5,e xiaoming1,a2,b3,c4,d5,e6,f7,g2,b4,d3,c1,a6,f5,e7,g RemoveTree21xiaohon xiaomingl,a2,b3,c4,d请选择你的操作[
0、24]:21移除树g5,e6,f7,g请输入要删除的二义链衣名称:x iaohong2tb4,d3,c l,a6,f xiaoming1,a2,b3,c4,d5,e6,f7,g5,e7,g2,b4,d3,c1,a6,f5,e7,g RemoveTree移除树21xiaogan删除二叉链表失败请选择你的操作[0~24]:21g请输入要删除的二叉链表名称:xiaogang删除二叉链表失败LocateTree查22xiaohon该二叉链表不在此管请选择你的操作[0~24]:22找树g理表中谙输入要在我的义卷表名称x iaohong该二叉链表不在此管理表中22xiaomin xiaomingl,a2,b3,c4,d LocateTree查找树g5,e6,f7,g请选择你的操作[0~24]:222,b4,d3,c l,a6,f清输入要否按防义链发名称:xiaoming xiaoming1,a2,b3,c4,d5,e6,f7,g5,e7,g2,b4,d3,c1,a6,f5,e7,g LevelOrderTraverse10l.a2,b3,c4,d5,e6,f7,g请选择你的操作[
0、24]101,a2,b3,c4,d5,e6,f7,g退出系统0请选择你的操作C0~24]0Welcome touse thissystem againnext time!Process exitedafter1026seconds withreturn value0只按任意键继续...32华中科技大学计算机学院数据结构实验报告
3.5实验小结在实验中,我遇到了如下几个错误1本次实验中有许多函数都是利用递归实现的,在这个过程中,我因为不清楚递归的过程,而导致返回值时有错误的现象同时,也因为不清楚如何计算递归方式实现的函数的时间复杂度而浪费了很多时间2在创建二叉树的函数中,为了实现递归过程中使用definition定义的正确性,我使用到了全局变量i,因此在每次调用该函数时都应该将全局变量i重置,但在需要调用的过程中总是因为忘记重置而导致测试时出现问题33华中科技大学计算机学院数据结构实验报告4基于邻接表的图实现
3.1问题描述该实验要解决的基本问题是实现邻接表的各个基本功能,如创建表、销毁表、清空表、判空表和获得顶点的位序等等其中,在主程序中完成函数调用所需实参值的准备和函数执行结果的显示可选择以文件的形式进行存储和加载,也即将生成的邻接表保存到相应的文件中,也可以从文件中获取邻接表进行操作同时,也可以对图的管理表进行添加、删除和查找操作
3.
1.1需实现的基本运算依据最小完备性和常用性相结合的原则,以函数形式定义了邻接表的创建表、销毁表、清空表、判定空表和获得顶点的位序等19种基本运算,具体运算功能定义如下⑴创建邻接表函数名称是CreateCraph G,V,VR;初始条件是邻接表G未创建;操作结果是构造一个邻接表⑵销毁邻接表函数名称是DestroyGraphG;初始条件是邻接表G已创建;操作结果是销毁邻接表G⑶查找邻接表函数名称是LocateVex G,e;初始条件是邻接表G已创建;操作结果是返回关键字为e的顶点的位序⑷判空邻接表函数名称是EmptyGraphG;初始条件是邻接表G已创建;操作结果是若G为空表则返回TRUE,否则返回FALSEo⑸赋值顶点:函数名称是PutVexG,e,value;初始条件是邻接表G已创建;操作结果是将关键字为e的顶点的信息赋值为value⑹获得第一邻接点函数名称是FirstAdjVcxG,c;初始条件是邻接表G已创建;操作结果是返回关键字为e的顶点的第一邻接点的位序⑺获得下一邻接点函数名称是NextAdjVexG,v,w;初始条件是邻接表G已创建;操作结果是返回关键字为v的顶点的相对于邻接点w的下一邻接点的位序华中科技大学计算机学院数据结构实验报告⑻插入顶点函数名称是InsertVexG,value;初始条件是邻接表G已创建;操作结果是在邻接表的顶点数组中插入信息为value的顶点⑼删除顶点:函数名称是DeleteVexG,e;初始条件是邻接表G已创建;操作结果是删除关键字为e的顶点⑩插入边函数名称是InsertArcG,v,w;初始条件是邻接表G己创建;操作结果是插入与关键字为v和w的顶点关联的边11删除边函数名称是DeleteArcG,v,w;初始条件是邻接表G已创建;操作结果是删除与关键字为v和w的顶点关联的边⑫深度优先搜索遍历图函数名称是DFSTraverseG,visit,初始条件是邻接表G已创建;操作结果是通过DFS算法依次对G的每个表头顶点调用函数visito⑬广度优先搜索遍历图函数名称是BFSTraverseG,visit,初始条件是邻接表G已创建;操作结果是通过BFS算法依次对G的每个表头顶点调用函数visito⑷保存邻接表函数名称是SaveGraphG,FileName,初始条件是邻接表G已创建;操作结果是将邻接表保存到名为FileName的文件中15加载邻接表函数名称是LoadGraphG,FilcNamc,初始条件是邻接表G未创建;操作结果是将名为FileName的文件加载到邻接表中16在管理表中添加一个图函数名称是AddGraphGraphs,bileName;初始条件是多邻接表非空;操作结果是将文件名为FileName的邻接表添加到管理表中17在管理表中删除一个图函数名称是RemoveGraphGraphs,FileName;初始条件是多邻接表非空;操作结果是将文件名为FileName的邻接表删除18在管理表中查找一个图函数名称是LocatcGraphGraphs,FileName;初始条件是多邻接表非空;操作结果是查找文件名为FileName的邻接表并定位以可对其进行操作⑲打印邻接表函数名称是PrintGraphG;初始条件是邻接表已创建;操作结果是打印邻接表的表头顶点数组及对应的邻接链表35华中科技大学计算机学院数据结构实验报告
4.2系统设计本次实验的系统设计如下将菜单演示和用户选择写入到while循环中,用0P获取用户的选择,0P初始化为1,以便第一次能进入循环进入循环后系统首先显示功能菜单,然后用户输入选择0T9,其中179分别代表对二叉链表的一个基本运算,在主函数中通过switch语句对应到相应的函数功能,执行完该功能后break跳出switch语句,继续执行while循环,直至用户输入0退出当前演示系统(演示系统结构如图4-1所示)Menu forLinear TableOn SequenceStructure
1.CreateCraph DestroyGraph
3.LocateVex PutVex
5.FirstAdjVex NextAdjVex
7.InsertVex DeleteVex
9.InsertArc DeleteArc
11.DFSTraverse BFSTraverse
13.SaveGraph LoadGraph
15.EmptyGraph AddGraph
17.RemoveGraph LocateGraph
19.PrintGraph Exit请选择你的操作KH9]图47功能演示系统结构图本次实验用到的数据结构定义为#define TRUE1#define FALSE0#define OK1#define ERROR0#define INFEASIBLE-1#define OVERFLOW-2#dcfinc MAX_VERTEX_NUM20typedef intstatus;typedef intKey Type;typedef enum{DG,DN,UDG,UDN GraphKind;typedef struct{Key Typekey;char othcrs[20J;36华中科技大学计算机学院数据结构实验报告}VerlexType;//顶点数据类型定义typedef struct ArcNode{〃表结点类型定义int adjvex;〃顶点位置编号structArcNode*nextarc;〃下一个表结点指针}ArcNode;typedef structVNode{〃头结点及其数组类型定义VertexType data;〃顶点信息ArcNode*firslarc;〃指向第一条边}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{〃邻接表的类型定义AdjList vertices;〃头结点数组int vexnum,arcnum;〃顶点数、边数Graph Kind kind;〃图的类型}ALGraph;typede fstruct{〃邻接表的管理表定义struct{char name[30J;ALGraph G;}elem
[1];int length;}LISTS;
4.3系统实现本次实验函数的算法思想及设计如下⑴创建邻接表函数的参数是邻接表G的引用,顶点数组V,存储边的信息的二维数组VR0在函数中先判断顶点关键字是否唯一,然后将顶点读入头结点数组中,并采用头插法依次插入边,同时要修改边数和顶点数经分析,该算法的时间复杂度为0南⑵销毁邻接表函数的参数是图G的引用在函数中,先判断图是否创建,如未创建则通过循环依次邻接链表中的结点,并将firstarc结点置为空经分析,该算法的时间复杂度为/37华中科技大学计算机学院数据结构实验报告⑶查找邻接表函数的参数是图G,待查找关键字u在函数中,通过循环比较关键字查找待查找结点,如未找到返回-1经分析,该算法的时间复杂度为0n o⑷判空邻接表函数参数是图G的引用在函数中,判断arcnum是否为0,如果为0,则返回0K代表图为空经分析,该算法的时间复杂度是01⑸赋值顶点函数的参数是图G的引用,被赋值的结点的关键字u,待赋值的结点的信息value在函数中,先查找关键字为u的结点是否在图中,如不在返回ERROR;然后查找value,key是否在图中并且是否与u相等,如果在图中且不与u相等返TERROR;其余情况下,直接赋值经分析,该算法的时间复杂度为0n o⑹获得第一邻接点函数参数是图G,待查找第一邻接结点的结点的关键字u在函数中,先判断关键字为u的结点是否在图中,如果不在返回INFEASIBLE,否则判断firstarc是否为空,不为空则返回其存储的第一邻接点信息经分析,该算法的时间复杂度为0n⑺获得下一邻接点函数参数是图G,待查找下一邻接结点的结点的关键字v,相对的邻接点的关键字w在函数中,先判断关键字为v和w的结点是否在图中,如果不在返回INFEASIBLE,否则通过循环查找关键字为、v的邻接链表结点,如果其下一邻接点不为空则返回下一邻接点关键字,否则返回经分析,该算法的时间复杂度为0n⑻插入顶点函数参数是图G的引用,被插入顶点的信息valueo在函数中,先判断关键字为value,key的结点是否在图中,如果在返回ERROR,否则在表头顶点数组中插入顶点并修改vexnum信息经分析,该算法的时间复杂度为0n⑼删除顶点函数参数是图G的引用,待删除顶点的关键字V在函数中,先判断关键字为v的结点是否在图中,如果不在返回ERROR,否则清空找到的表头结点的邻接链表,覆盖被删除的表头结点并修改vexnuni信息,删除与被删除的表头结点相关的边并更新结点的位序经分析,该算法的时间复杂度为0r⑩插入边函数参数是图G,待插入边的两端的关键字v和w在函数中,先判断关键字为v或w的结点是否在图中,如果不在返回ERROR,否则先判断该边是否已经在图中,如果不在则插入边经分析,该算法的时间复杂度为0n.38华中科技大学计算机学院数据结构实验报告己存在;操作结果是若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义⑼获得后继函数名称是NextElemL,cur_e,next_e;初始条件是线性表L已存在;操作结果是若cur_e是L的数据元素,且不是最后一个,则用ncxt_e返回它的后继,否则操作失败,next,无定义⑩插入元素:函数名称是Listinsert L,i,e;初始条件是线性表L已存在,lWiWListLengthL+l;操作结果是在L的第i个位置之前插入新的数据元素e ID删除元素函数名称是元stDeleteL,i,e;初始条件是线性表L已存在且非空,iWiWListLcngthL;操作结果删除L的第i个数据元素,用e返回其值⑫遍历表:函数名称是ListTraverseL,visit,初始条件是线性表L已存在;操作结果是依次对L的每个数据元素调用函数visit⑬保存线性表函数名称是SaveList L,Fil eName,初始条件是线性表L已存在;操作结果是将线性表元素按顺序保存至文件名为FileName的文件中⑷加载线性表函数名称是LoadList L,FileName,初始条件是线性表L不存在;操作结果是将文件名为FileName的文件加载到线性表中⑮在管理表中插入一个线性表函数名称是AddList Lists,ListName,无初始条件;操作结果是将文件名为ListName的线性表添加到管理表中⑹在管理表中删除一个线性表函数名称是RemoveList Lists,ListName,初始条件是多线性表非空;操作结果是将文件名为ListName的线性表删除⑰在管理表中查找一个线性表:函数名称是LocateList Lists,ListName,初始条件是多线性表非空;操作结果是查找文件名为ListName的线性表并可对其进行操作
1.2系统设计本次实验的系统设计如下将菜单演示和用户选择写入到while循环中,用0P获取用户的选择,0P初始化为1,以便第一次能进入循环进入循环后系统首先显示功能菜单,然后用户输入选择0T7,其中1T7分别代表对线性表华中科技大学计算机学院数据结构实验报告11删除边函数参数是图G,待删除边的两端的关键字v和w在函数中,先判断关键字为v或w的结点是否在图中,如果不在返回ERROR,否则删除相关联顶点的邻接链表中与此边相关的结点如果此边不在图中则不会删除而返回INFEASIBLEo经分析,该算法的时间复杂度为0n⑫深度优先搜索遍历图函数参数是图G,访问函数的指针visit在函数中,先将visited数组初始化为0,代表未访问;然后从某个顶点v出发,首先访问该顶点,然后利用DFS核心函数依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止经分析,该算法的时间复杂度为0n+⑬广度优先搜索遍历图函数参数是图G,访问函数的指针visit在函数中,利用循环队列的数组实现方法进行遍历;首先将visited数组初始化为0,代表未访问;然后将第一个访问的结点v入队;然后通过判断队列是否为空控制循环,在循环中,先将队首出队,并将与该顶点相连的顶点入队,最后通过一次次的循环使得图中所有和v有路径相通的顶点都被访问到若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止经分析,该算法的时间复杂度为0n+e⑷保存邻接表函数参数是图G,待保存文件的路径名称在函数中,先将表头顶点数组写入文件中,然后,通过循环一次将边写入到文件中经分析,该算法的时间复杂度为0/15加载邻接表函数参数是图G,待加载文件的路径名称在函数中,先将数据读到存放顶点和边的数组V和VR中,然后调用CreateGraph函数创建图经分析,该算法的时间复杂度为0一⑹在管理表中添加一个图函数的参数是邻接表的管理表Graphs的引用,待添加邻接表的名称FileNameo在函数中,首先在管理表的末端添加一个名称为FileName的图,然后将数据读到存放顶点和边的数组V和VR中,调用CreateGraph函数创建图经分析,该算法的时间复杂度为0/0在管理表中删除一个图函数的参数是邻接表的管理表Graphs的引用,待删除邻接表的名称FileNameo在函数中,通过循环比较名称查找待删除的图,39华中科技大学计算机学院数据结构实验报告查找成功则先销毁图,并从前至后移动管理表中的图经分析,该算法的时间复杂度为06⑻在管理表中查找一个图函数的参数是邻接表的管理表Graphs的引用,待查找邻接表的名称FilcNamc在函数中,通过循环比较名称查找待查找的图,查找成功则定位至该图并返回其位序经分析,该算法的时间复杂度为0n⑲打印邻接表函数的参数是邻接表的引用G在函数中,先判断vexnum是否为0,若为0则说明为空图,否则依次打印顶点数组的位序,顶点数组信息,顶点数组的邻接链表经分析,该算法的时间复杂度为
054.4系统测试输入样例解释第一个数字为测试序号,代表该测试序号所调用的函数;然后是需要输入的数据函数输入预期输出实际输出DestroyGr2邻接表未创请选择你的操作[0~19]:2邻接表未创建,无需销毁aph销毁邻建,无需销接表毁EmptyGra ph15邻接表未创判空建请选择你的操作
[019]:15邻接表未创建11邻接表未创请选择你的操作[0~19]邻接表未创建DFSTrave rse建深度优先搜索遍历CreateCra ph15线性表8集邻接表创建谛选择你的操作创建图合7二叉树6成功请依次输入及头结点的信息及边5线性衣8加合
71.XW6无向图-1nil56576778-1-1第接无向图-1nil56去创建成功576778-1-1CreateCra ph1邻接表已创请选择你的操作济依次输入表头结点的信息及边创建图建5线性8集合7:义树6无向图-1nil56576778-1-1铭按表己创建EmptyGra ph15图不为空判空请选择你的操作
[019]:15图不为空40华中科技大学计算机学院数据结构实验报告PrintGrap h19见截图请选择你的操作
[019]:19打印邻接表当前图包含4个顶点,4条边位序顶点数组信息邻接表05线性表2-318集合227二义树1-3-036无向图2-0LocateVe X35查找顶点信请选择你的操作[0~19]:3查找顶点息为5线性表请输入待杳找顶点的关键字:5查找顶点信息为5线性表39图中无此顶LocateVe X点请选择你的操作
[019]:3请输入待查找顶点的关健字:9查找顶点图中无此顶点LocateVe X36查找顶点信请选择你的操作[0~19]:3查找顶点息为6无向图请输入待杳找顶点的关键字:6查找顶点信息为6无向图PutVex给顶499new查找失败,邻请选挣你的,操作[0~19]:4点赋值接表中无此请输入待%请找纨点的关键字9丁思9new顶点输入赋值查找邻接表中无此顶点失败,PutVex给顶485new请选择你的4蒙作
[019]:4点赋值赋值失败.待清输入待祚请茎结点的关键字8赋值的顶点输入赋值彳赋言息:5new值失败.彳顶3赋值的顶点关键字与当前图中的中突关键字与当点关键字1前图中的顶点关键字冲突PutVex给顶455单链表赋值成功请选择你的请操作[0」9]:4点赋值输入待祚谙输找结点的关键字5言息:5单铢表入赋值赋值成功LocateVe X35查找顶点信请选择你的操作[0~19]:3请输入待杳找顶点的关键查找顶点息为5单链表字:5查找顶点信息为5单链表FirstAdjVe X59请选择你的操作[0~19]:5第一邻接点查找失败,邻请输入待查找结点的关键字9查找失败,邻接表中无此顶点接表中无此顶点57FirstAdjVe x第一邻接点请选择你的操作[0~19]:5第一邻接点的信息为8请输入待查找结点的关键字7第一邻接点的信息为8集集合合41华中科技大学计算机学院数据结构实验报告NextAdjV ex697谙选择你的操作[0~19]:6下一邻接点输入信息有请输入待查找顶点的关键字9误,邻接表请输入该结点的一个邻接点的关键字7输入信息有误.邻接表中不存在输入的顶点中不存在输入的顶点NextAdjV ex656相对于该邻请选择你的操作[0~19]:6下一邻接点接点没有下请输入待查找顶点的关键字:5一邻接点请输入该结点的•个邻接点的关键字:6相对于该邻接点没有下一邻接点678NextAdjV ex第一邻接点请选择1尔的操作[0〜19]:6下一邻接点的信息为6请输入彳审查找顶点的关键字:7无向图请输入,亥结点的•个邻接点的关键字:8第一邻」要点的信息为6无向图InsertVex插76欧拉图插入失败,请选择你的操作[
0、清19]:7入顶点关键字冲突输入待插入顶点门插入勺信息:6欧拉图突失败,关神字”InsertVex插79哈密顿图插入成功请选择你的操作[019]:7入顶点盾输入待插入顶点的信息:9哈密顿图捕入成功PrintGrap h19见截图请选择你的操作[
0、当19]:19打印邻接表前图包含5个顶点,4条边位序顶点数组4ts邻接表05单链18集合表2-327二叉236无向对
1.-3-〉049哈密图2-0顿图8DeleteVex删4删除失败,除顶点邻接表中无请选择你的操作[0~19]:8请输入待删除顶点关键待删除顶点字4删除失败,邻接式中无待删除顶点DeleteVex删86成功删除顶请选择你的操作[09]:8请输入待删除顶点关键除顶点点字6成功删除顶点PrintGrap h19见截图请选择你的操作[0~19]:19打印邻接表当前图包含4个顶点,2条边位序顶点数组信息邻接表05单链式218集合227二叉树1-039哈密顿图InsertArc插978该边已存请选择,你的操作[019]:9入边在谙输入:断入的边的信息:78存在该边一,42华中科技大学计算机学院数据结构实验报告InsertArc插967邻接表中不请选择1东的操作
[019]:9题入的边的信息:67中不存在其中某顶点入边存在其中某清输入:顶点邻接表।InsertArc插959插入成功请选择1你的操作[0~19]:9入边清输入J断入的边的信息:59功插入成.InsertArc插979插入成功请选择1你的操作
[019]:9入边盾输入1断入的边的信息:79功插入成.PrintGrap h19见截图请选择你的操作
[019]:19打印邻接表当前图包含4个顶点,4条边位序顶点数组信息邻接表05单送表3-218集合227二叉树3-广〉039哈密顿图2-0DeleteArc1058该边不存请选择你的操作[0~19]:10删除边在请输入删除的边的信息58该边小石在DeleteArc删1076邻接表中不请选择你的操作
[019]:10除边存在其中某请输入删除的边的信息76邻接表中不存在其中某顶顶点点1079DeleteArc删删除成功请选择你的操作[
0、19]:10除边请输入删除的边的信息79删除成功PrintGrap h19见截图请选择你的操作[0~19]:19打印邻接表当前图包含4个顶点,2条边位序顶点数组信息邻接表05单链式3-218集合227二叉树1-039哈密顿图0DFSTrave rse11请选择你的操作[0~19]:11深度优先搜5单链表9哈5单链表9哈密顿图7二叉树8集合索遍历密顿图7二叉树8集合BFSTraver se125单链表9哈请选择你的操作[0~19]:12广度优先搜密顿图7二5单链表9哈密顿图7二叉树8集合索遍历叉树8集合43华中科技大学计算机学院数据结构实验报告SaveGrap h13Graph成功将邻接请选择你的操作[0~19]:13请输入文件名称:Graph成保存文件表保存至文功将邻接表保存至文件Graph件Graph DGraph/基于邻接表的图实现E基于邻接表的图实现2邻接表销毁请选择你的操作[0~19]:2邻接表销毁成功DestroyGr成功aph销毁图19空图,无需请选择你的操作
[019]:19空图,无需打印!PrintGrap h打印!打印邻接表14Graph LoadGraph请选择你的操作
[019]:14请输入文件名称:Graph加载文件成功将文件龙场将文彳牛Graph加莪至邻接表Graph加载至邻接表PrintGrap h19见截图请选择你的操作[0~19]19打印邻接表当前图包含4个顶点,3条边位序顶点数组信息邻接表05单链式2-318集合227二叉树1-039哈密顿图0DeleteArc删1078删除成功请选择你的操作
[019]:10请输入删除的边的信息7除边8删除成功FirstAdjVe X58无第一邻接请选择你的操作[0~19]:5第一邻接点点请输入待查找结点的关键字:8无第一邻接点AddGrap h添162其余数见截图加图据见截图请选择你的操作[0~19]:16请输入要添加的邻接表个数2请依次输入邻接衣名称和邻接表佶息xiaohong5级性表8条仆7二叉树6无向图-1null56576778-1-1xiaoming1G12G23G34G45G56G67G78G89G910GIO11Gil12G1213G1314G1415G1516G1617G1718G1819G1920G20-1null-1-1插入邻接及完毕当前管理表为xiaohong5线性表7•.义树8集合6无向图xiaoming1G12G23G34G45G56G67G78G89G910G1011G1112G1213G1314G1415G1516G1617G1718G1819G1920G bo44华中科技大学计算机学院数据结构实验报告RemoveG17请选择你的操作[0~19]:17raph删除图xiaogang该邻接表不请输入要刷除的况接火名称:x iaogang该邻接表不在在管理表管理表中,删除邻接表失败中,删除邻接表失败RemoveG17见截图请选择你的操作[0~19]:17raph删除图xiaohong清输A要删唳他邻接云名称:x iaohong xiaoming1G12G23G34G45G56G67G78G89G910GIO11Gil12G1213G1314G1415G1516G1617G1718G1819G1920G20LocateGra18xiaohong该邻接表不请选择你的操作[0~19]:18ph查找图在此管理表iij输入要在按的邻接W名称x iaohong该邻接表不中在此管理表中LocateGra18xiaoming见截图请选择你的操作[019]:18ph查找图请输入要在我向邻接表名称:x iaomi ngxiaoming1G12G23G34G45G56G67G78G89G910GIO11Gil12G1213G1314G1415G1516G1617G1718G1819G1920G2019PrintGrap h见截图请选择你的操作[0~19]:19打印邻接表当前图包含20个顶点,0条边位序顶点数组信息邻接表01G112G223G334G445G556G667G778G889G9910G101011G111112G121213G131314G141415G151516G161617G171718G181819G191920G20退出系统0谙选你的操作[
0、19]0Jelcoae touse thissystem againnext time!Process exitedafter
121.2seconds withreturn value0请按任意健维续・・・45华中科技大学计算机学院数据结构实验报告
4.5实验小结在实验中,我遇到了如下几个错误1本次实验中有许多函数的边界情况很多,最突出的比如插入删除弧和顶点在写这几个函数的过程中,我常常会因为没有进行特判而无法通过一些特殊样例这是我以后写程序的时候需要考虑的健壮性问题2在书写创建图的函数的过程中,由于未理解头插法是什么意思,以及样例的特殊性让我以为是将结点按照顶点位序插入到链表中,结果导致浪费了很长时问,以后在写程序时,我会注意理解清楚要求再开始写程序46华中科技大学计算机学院数据结构实验报告参考文献
[1]严蔚敏等.数据结构(C语言版).清华大学出版社
[2]Larry Nyhoff.ADTs,Data Structures,and ProblemSolving withC++.Second Edition,Calvin College,2005
[3]殷立峰.Qt C++跨平台图形界面程序设计基础.清华大学出版社,2014:192〜197
[4]严蔚敏等.数据结构题集(C语言版).清华大学出版社47华中科技大学计算机学院数据结构实验报告或线性表的管理表的一个基本运算,在主函数中通过switch语句对应到相应的函数功能,执行完该功能后break跳出switch语句,继续执行while循环,直至用户输入0退出当前演示系统(系统功能设计结构如图1T所示)Menu forLinear TableOn SequenceStructure
1.InitList
10.Listinsert
2.DestroyList
11.ListDelete
3.ClearList
12.ListTraverse
4.ListEmpty
13.SaveList
5.ListLength
14.LoadList
6.GetElem
15.AddList
7.LocateElem
16.RemoveList
8.PriorElem
17.LocateList
9.NextElem
0.Exit请选择你的操作图1-1演示系统结构图其中,本次实验使用的数据结构定义为#define TRUE1#define FALSE0#define OK1#dcfine ERROR0#define INFEASIBLE-1#define OVERFLOW-2#define LISTJNIT_SIZE10#define LISTINCREMENT10typedef intstatus;typcdef intElemType;〃数据元素类型定义typedef struct〃顺序表顺序结构的定义ElemType*elem;intlength;int listsize;JSqList;typedefstruct//线性表的管理表定义struct{华中科技大学计算机学院数据结构实验报告char name
[30];SqList L;elem[10J;intlength;int listsize;LISTS;
1.3系统实现线性表运算算法思想与设计如下⑴初始化线性表思想将线性表初始化过程写成函数,其中传入函数的参数是主函数中定义的结构型变量L的引用在函数中,首先判断L是否创建,如果未创建则使用malloc函数分配LIST」NIT_SIZE大小的连续内存空间,如果分配成功则将newbase赋值给L.elem,由于线性表的长度为0,将L.length初始化为0,L.listsize初始化为LIST」NIT_SIZE,即完成了线性表的初始化经分析,算法的时间复杂度为01⑵销毁线性表思想将销毁线性表的过程写成函数,其中传入函数的参数是主函数中定义的结构性变量L的引用在函数中,首先使用freo函数释放掉以L.elem为首地址的连续内存空间,再将L.length,L.listsize重新赋值为0o经分析,该算法的时间复杂度为01⑶清空线性表的思想将清空表的过程写成函数,其中将主函数中定义的结构性变量L的引用作为函数参数在函数中,由于清空操作并不释放内存空间,故只需将线性表的长度置为0即可经分析,该算法的时间复杂度为0lo⑷求线性表表长的思想将求表长过程写成函数,其中主函数中定义的结构性变量L的引用作为函数的参数,在函数中,直接返回L.length即为所求线性表的表长经分析,该算法的时间复杂度为01⑸获得元素的算法思想将获得线性表元素写成函数,其中函数的参数是结构型变量L以及数据元素的序号i,由于采取的是线性存储结构,故直接通过访问数组的方式即L.elem[iT]来获取元素,当然,在这之前需要判断合法华中科技大学计算机学院数据结构实验报告性经分析,该算法的时间复杂度为01⑹查找元素的算法思想将查找线性表特定值的数据元素写成函数,其中函数的参数是主函数中定义的结构类型变量L以及查找的数据元素的值,通过循环对线性表中的每一个元素与给定值比较是否相等,如果相等就返回该元素的位置经分析,该算法的时间复杂度为0n⑺获得直接前驱算法思想将获得直接前驱元素的过程写成函数,函数的参数是结构体类型变量以及特定数据元素的值,接受前驱的变量在函数中,首先判断线性表是否为空,若不为空则调用获得元素的函数判断该线性表中特定数据元素的位序,如果位置为1,则返回ERROR,否则将其前一个元素即L.clcm[i-2]赋给接受前驱的变量经分析,该算法的时间复杂度为0n⑻获得后继算法思想将获得直接后继元素的过程写成函数,函数的参数是结构体类型变量以及特定数据元素的值,接受后继的变量在函数中,首先判断线性表是否为空,若不为空则调用获得元素的函数判断该线性表中特定数据元素的位序如果位置为L.length,则返回ERROR,否则将其后一个元素即L.elem[i]赋给接受后继的变量经分析,该算法的时间复杂度为0n⑼插入元素算法思想将插入函数写成函数,函数的参数是结构型变量的引用,插入元素的值以及插入位置在函数中,首先判断插入位置的合法性,即是否在线性表中合适的位置,其次还要判断当前存储空间是否已满,如果存储空间已满则要用realloc函数重新分配空间,插入元素时要先从L.length开始将元素依次后移,然后将待插入元素插入到空位中经分析,该算法的时间复杂度为0n10删除元素算法思想将删除线性表中元素写成函数,函数的参数是结构类型变量的引用,待删除元素的位置,接受待删除元素的变量在函数中,首先判断位序的合法性,然后直接将删除元素位置后一个元素直到最后一个元素从前往后向前移动一个单元经分析,该算法的时间复杂度为0n ID遍历线性表算法思想将遍历线性表写成一个函数,函数的参数是结构类型变量,直接用一个循环来对线性表中的每一个元素进行操作此处进行输出操作经分析,该算法的时间复杂度为0n⑫保存线性表到文件中的算法思想函数的参数是结构体变量L和待保存华中科技大学计算机学院数据结构实验报告文件的路径在函数中,创建一个指向待保存文件的文件指针,通过循环依次将线性表中的数据写入文件中经分析,该算法的算法复杂度是0n13加载文件到线性表中的算法函数的参数是结构体变量L的引用和待加载文件的路径在函数中,创建一个指向待加载文件的文件指针,并要为线性表L分配空间,通过循环依次将文件中的数据读入线性表中,如果存储已满,还要增加分配空间经分析,该算法的算法复杂度是0n⑷插入一个线性表算法思想函数的参数是管理表的引用和待插入线性表的名称在函数中,先在已存在的管理表中的末尾处开辟新的线性表的存储空间,并将管理表长度增加1经分析,该算法的时间复杂度是0115删除一个线性表算法思想函数的参数是管理表的引用和待删除线性表的名称在函数中,通过循环比较线性表名称和待删除线性表的名称,如果没有找到则返回ERROR,否则就先摧毁待删除线性表,然后自该位置起从前往后将下一个线性表复制到前一个线性表中经分析,该算法复杂度是0n2⑯定位一个线性表算法思想函数参数是管理表Lists和待查找的线性表名称在函数中,通过循环比较待查找线性表名称和管理表中线性表的名称,如果匹配成功则返回该线性表位序,否则返回ERROR经分析,该算法复杂度是0n
1.4系统测试输入样例解释第一个数字为测试序号,代表该测试序号所调用的函数;然后是需要输入的数据调用函数输入预期输出实际输出DestroyList销2线性表未创请选择你的操作毁线性表建,无需销毁2线性表未创建,无需销毁3ClearList清线性表清除失请选择你的操作[0~17]:3线性表清除失败线性表未空线性表败线性表未创创建建5ListLength求线性表未创建请选择你的操作[0~17]:5线性表未创建表长1线性表创建成功请选择你的操作[0」7]:1线性表创建成功7华中科技大学计算机学院数据结构实验报告InitList创建线1线性表已创建性表请选择你的操作线性表上创建ListEmpty判空4线性表为空表请选择你的操作[0~17]:4线性表为空表ListLength求表5线性表的长度长为0请选择你的操作[0~17]:5线性表的长度为01034Listinsert插入元素位置不合请选择你的操作
[017]:10元素法请输入插入的元素及插入的位置34元薪立置不合雇1031Listinsert插入插入元素成请选择你的操作[0~17]:10元素功,当前线性府输入插入的元素及插入的位置:31表的长度为1插入元素成功,当前线性式的长度为11072Listinsert插入插入元素成请选择你的操作
[017]:10元素功,当前线性请输入插入的元素及插入的位置72表的长度为2插入元素成功,当前线性表的长度为2ListTraverse遍1237请选择你的操作
[017]:12历线性表37ListEmpty判空4线性表不为空表请选择你的操作[0~17]:4线性表不为空表ListLength求表5线性表的长度长为2请选择你的操作[0~17]:5线性表的长度为263输入位置不Get日em获取心心生口/Z请选择你的:i柒作[0~17]:6某位置的元素疗输入元素,立置:3蛤入彳立置不,合法GetElem获60输入位置不柒作[0~17]:6取某位置的元口/A请选择你的」汇置0素倡输入元恐合法GetElem获取62线性表中第2请选择你的:柒作[0~17]:6某位置的元素个元素是7清揄入元素一立置:2线性收中第:2个元索是7LocateElem查73线性表中元素找某元素3的位置是1请选择你的操作[0~17]:7请输入元素3线性表中元素3的位置是1。