《《数据结构》课程实验报告 (7)》由会员分享，可在线阅读，更多相关《《数据结构》课程实验报告 (7)（47页珍藏版）》请在金锄头文库上搜索。
1、课 程 实 验 报 告课程名称： 数据结构 专业班级： 信安 学 号： 姓 名： 指导教师： 报告日期： 2015.4.5 计算机科学与技术学院目 录1 课程实验概述 .12 实验一 基于顺序结构的线性表实现2.1 问题描述 .22.2 系统设计 .22.3 系统实现 .72.4 效率分析 .113 实验二 基于链式结构的线性表实现3.1 问题描述 .123.2 系统设计 .123.3 系统实现 .143.4 效率分析 .224 实验三 基于二叉链表的二叉树实现4.1 问题描述 .234.2 系统设计 .234.3 系统实现 .324.4 效率分析 .435 实验总结与评价 .4511 课程实
2、验概述上机实验是对学生的一种全面综合训练，是与课堂听课、自学和练习相辅相成的必不可少的一个教学环节。实验目的着眼于原理与应用的结合，使学生学会如何把书上的知识用语解决实际问题，能够理解和运用常用的数据结构，如线性表、栈、队列、树、图、查找表等，并在此基础上建立相应的算法；通过上机实验使学生了解算法和程序的区别，培养学生把算法转换为程序的能力，提高学生解决实际问题的能力；学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。22 实验一 基于顺序结构的线性表实现2.1 问题描述编写一个程序，实现顺序表的各
3、种基本运算，并在此基础上完成以下功能: 1) 初始化顺序表； 2) 释放顺序表；3) 判断顺序表 L 是否为空； 4) 输出顺序表 L 的长度；5) 输出顺序表 L 的第 i 个元素； 6) 输出元素 e 的位置； 7) 输出元素 e 的前一个元素； 8) 输出元素 e 的后一个元素； 9) 在第 i 个元素位置上插入 f 元素； 10) 删除 L 的第 i 个元素；11) 输出顺序表 L；12) 保存顺序表 L 的数据。2.2 系统设计1、数据类型顺序表：typedef structElemType * elem; /线性表首地址int length; /线性表当前长度int listsiz
4、e; /线性表最大长度SqList;数据类型：int（可以在头文件中更改数据类型）输入形式：文件读取、键盘输入输入范围：-2152162、函数返回状态判断为真：TRUE 0判断为假：FALSE -1函数正确执行：OK -2函数执行错误：ERROR -3元素不存在：NOTEXIST -4内存分配溢出：OVERFLOW -533、函数设计InitList(&L) 操作前提：L 是一个未初始化的线性表。 操作结果：将 L 初始化为一个空的线性表。 DestroyList(&L) 操作前提：线性表 L 已存在。 操作结果：销毁线性表 L。 ListEmpty(L) 操作前提：线性表 L 已存在。 操作
5、结果：若 L 为空表，则返回 TURE，否则返回 FALSE。 ListLength(L) 操作前提：线性表 L 已存在。 操作结果：返回 L 中数据元素个数。 GetElem(L, i,&e) 操作前提：线性表 L 已存在，1iListLength（L） 。 操作结果：用 e 返回 L 中第 i 个元素的值。 LocateElem (L,e) 操作前提：线性表 L 已存在。 操作结果：返回 L 中第一个 e 的位序。 若这样的数据元素不存在，则返回值为 0。PriorElem (L,e,&proi) 操作前提：线性表 L 已存在。 操作结果：返回 L 中第一个 e 的前一个数据元素。 若这样
6、的数据元素不存在，则返回值为 0。NextElem (L,e,&next) 操作前提：线性表 L 已存在。 操作结果：返回 L 中第一个 e 的后一个的数据元素。 若这样的数据元素不存在，则返回值为 0。ListInsert (&L,i ,e) 操作前提：线性表 L 已存在，1iListLength（L）+1。 操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度+1。 ListDelete (&L,i, e) 操作前提：线性表 L 已存在且非空，1iListLength（L ） 。 操作结果：删除 L 的第 i 个元素数据，并用 e 返回其值，L 的长度1。 Display
7、List(L) 操作前提：线性表 L 已存在。 操作结果：打印表中元素。SaveList(L)操作前提：线性表 L 已存在。 操作结果：保存表中元素。44、主要函数流程图ProiElem：这里的查找元素操作可直接调用 LocateElem 函数返回元素的位置，NextElem 函数的流程图与此相似，这里不在赘述）5ListInsert：这个函数最主要的部分就是检查参数与元素的移位操作，若参数不合法（传入空线性表、插入位置在线性表之外）极易出现访问数组外元素问题；元素移位操作要在不丢失数据的前提下（从最后一个元素开始）进行。6ListDelete删除函数同样最主要的部分就是检查参数与元素的移位操
8、作，若参数不合法（传入空线性表、删除位置在线性表之外）极易出现访问数组外元素问题；元素移位操作要在不丢失数据的前提下（从被删除的元素开始）进行。72.3 系统实现这里也只给出主要函数的代码，完整代码会在附录给出函数名：LocateElem参数：线性表 L、要查找的元素返回值：若元素存在，返回位置，否则返回错误信息函数功能：获取元素的位置status LocateElem(SqList L,ElemType e)if( !L.elem )return ERROR;for( int i=1; iL.length+1 | ii; j- )L.elemj = L.elemj-1;L.elemi = e
9、;L.length+;return OK;函数名：ListDelete参数：线性表 L（引用） 、位置、带回被删除的元素 e返回值：是否删除元素成功函数功能：删除指定位置的元素并带回元素status ListDelete(SqList & L,int i,ElemType & e)/*不可获取线性表长度之外的元素，第 0 号元素不用 */if( !L.elem | iL.length | idata = e )return loc;L.cur_p = L.cur_p-next;return NOTEXIST;函数名：NextElem参数：线性表 L、查找的元素、带回元素值的形参返回值：函数执行
10、情况成功为 OK，否则 ERROR函数功能：获取元素的后继节点元素status Link:NextElem(Link L, ElemType cur, ElemType &e)if( L.head=NULL )return ERROR;int pos;pos = LocateElem( L, cur );if( posL.length+1 )return ERROR;if( !L.head )L.head = (LinkList*)malloc( sizeof(LinkList) );if( !L.head )return OVERFLOW;L.head-data = e;L.head-nex
11、t = NULL;L.length = 1;return OK;L.cur_p = L.head;for( int j=1; jnext;if( !L.cur_p )return ERROR;L.tail = (LinkList*)malloc( sizeof(LinkList) );if( !L.tail )return OVERFLOW;L.tail-data = e;if( i=1 )L.tail-next = L.head;L.head = L.tail;elseL.tail-next = L.cur_p-next;L.cur_p-next = L.tail;L.length+;return OK;19函数名：ListDelete参数：线性表 L（引用） 、位置、带回被删除的
