2020年数据结构与算法实习-实验指导书.pdf

《2020年数据结构与算法实习-实验指导书.pdf》由会员分享，可在线阅读，更多相关《2020年数据结构与算法实习-实验指导书.pdf（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法实习-实验指导书数据结构与算法课程实习实验指导书资料仅供参考目录实验一 顺序表的基本操作错误!未定义书签。实验二 链表的基本操作.错误!未定义书签。实验三二叉树的基本操作错误!未定义书签。实验四 综合应用.错误!未定义书签。附录A实验报告示例.错误!未定义书签。附录B实验报告封面、评语得分表错 误！未定义书签。资料仅供参考实验一顺序表的基本操作【实验目的】1、掌握顺序存储的概念,学会对顺序表的基本操作。2、加深对顺序存储数据结构的理解,逐步培养解决实际问题的能力。【实验性质】设计型实验【实验内容】1、实现顺序表显示；2、实现顺序表插入；3、实现顺序表查找（显示比较次数）；4、实现

2、顺序表删除（显示移动次数）；5、实现顺序表排序（分别实现简单选择、快速，显示比较次数、移动次数）；6、实现顺序表的折半查找（显示比较次数）；7、编程实现一个顺序表的就地逆置，即利用原表的存储空间将顺序表逆置；资料仅供参考8、顺序表有序插入（显示比较次数、移动次数），屏幕提示后，从键盘输入一个元素值,在经过排序的线性表中插入这个元素；屏幕显示比较次数和移动次数，应有溢出判断和报告；9、要求以较高的效率实现删除顺序表中元素值在x 到 y（x 和 y 自定）之间的所有元素；10、编程实现将两个非递减的顺序表进行合并，要求同样的数据元素只出现一次；*11、编程实现顺序表的shell排 序（步长为5,3

3、,1）；*12、编程实现堆排序算法；*13、利用三元组顺序表存储矩阵，实现矩阵的转置（请独立写程序实现）。【实验环境】VC+6.0【实验要求】将如上文件保存在命名为“学号+姓名”的文件夹中并上传到指定的服务器。资料仅供参考实验二链表的基本操作【实验目的】1、掌握链表的概念，学会对链表进行操作。2、加深对链式存储结构的理解,逐步培养解决实际问题的编程能力。【实验性质】设计型实验【实验内容】1、实现单链表的创立；2、实现单链表的显示；3、实现单链表的查找（显示比较次数）；4、实现单链表的插入；5、实现单链表的删除（显示比较次数）；6、对已创立的链表（数据不限）进行直接插入排序；资料仅供参考7、将链

4、接存储线性表逆置，即最后一个结点变成第1 个结点，原来倒数第2 个结点变成第2 个结点，如此等等；8、生成有序的两个单链表A 和 B（链表的数据和个数自定），其首结点指针分别为a 和 b,要求将两个单链表合并为一个有序的单链表C,其首结点指针为c,而且合并后的单链表的数据不重复；9、将一个首结点指针为a 的单链表A 分解成两个单链表A和 B,其首结点指针分别为a和 b,使 得 链 表 A 中含有原链表A 中序号为奇数的元素，而 链 表 B 中含有原链表A 中序号为偶数的元素，且保持原来的相对顺序；10、请编程实现链栈的基本操作函数，并经过调用这些基本函数，实现十进制和八进制转换的功能。【实验环

5、境】V C+6.0【实验要求】资料仅供参考将如上文件保存在命名为“学号+姓名”的文件夹中并上传到指定的服务器。资料仅供参考实验三二叉树的基本操作【实验目的】【实验性质】设计型实验【实验内容】1、实现二叉树的创立；2、用递归方法分别先序、中序、后序遍历以Tree为根指针的二叉树；3、编写递归算法，计算二叉树中叶子结点的数目；4、编写递归算法，计算二叉树的深度；5、编写递归算法,将二叉树中所有结点的左、右子树相互交换；6、使用数组elem中的随机数序列（以 0 表示结束，不包括0）,生成以Tree为根指针的二叉排序树；7、在 以 Tree为根指针的二叉排序树中查找资料仅供参考结点；8、从以Tree

6、为根指针的二叉排序树中删除结点(适用各种位置的结点)；9、用非递归算法，先序遍历以Tree为根指针的二叉树；提示：用数组 BiTNode*stackmax构成堆栈，利用这个堆栈实现功能。10、用凹入表示法的表示以Tree为根指针的二叉树，例如：/324/123/746/690/56711、用广义表表示以Tree为根指针的二叉树,例如/(324(123(746,690),567)12、对以Tree为根指针的二叉树，从根结点开始，逐层从左到右输出各结点的数据。提示：用数组 BiTNode*queuemax构成队列，利用这个队列实现功能13、根据Huffman编码原理，使用数组elem资料仅供参考中

7、的随机数序列（以 0 表示结束，不包括0）作为结点的权重,生成赫夫曼树，以及赫夫曼编码,计算平均带权径长度。14、（1）随机生成二叉树。（2）生成并保存 先（后）序、中序输出序列。（3）按照保存的一对输出序列恢复出二叉树。（4）生成先（后）序输出序列。【实验环境】VC+6.0【实验要求】将如上文件保存在命名为“学号+姓名”的文件夹中并上传到指定的服务器。实验四综合应用一、运动会分数统计问题描述参加运动会的n 个学校编号为1联比赛分成 m 个男子项目和w 个女子项目，项目编号分资料仅供参考别 为lm和m+1-m+Wo由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7,5,3,2,1；还有

8、些项目只取前三名，得分顺序为5,3,2O写一个统计程序产生各种成绩单和得分报表。基本要求产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名 次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。测试数据对于n=4,m=3,w=2,编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。实现提示能 够 假 设n=20,m=30,wv串 l v串 2v回车和 mv串 v 回车资料仅供参考【实验环境】VC+6.0【实验要求】将如上文件保存在命名为“学号+姓名”的文件夹中并上传到指定的服务器。资料仅供参考附录A实验报告示例“学生通讯录管理

9、系统”的设计与实现一、设计要求1、问题描述纸质的通讯录已经不能满足大家的要求，容易丢失，查找困难等问题是纸质通讯录所不能克服的缺点。“学生通讯录管理系统”是为了帮助老师、同学，或者其它一些需要使用通讯录的人员进行管理和分析的一种应用程序。2、需求分析(1)输入数据建立通讯录(2)查询通讯录中满足要求的信息(3)插入新的通讯录信息(4)删除不需要的通讯录信息(5)查看所有的通讯录信息二、概要设计为了实现需求分析中的功能，能够从3 个方面着手设计1、主界面设计为了实现学生通讯录管理系统各功能的管资料仅供参考理，设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本系统。2、存

10、储结构设计本系统主要采用链表结构类型来表示存储在“学生通讯录管理系统”中的信息。其中,链 表 结 点 有 4 个分量构成：通讯录成员学号、姓名、电话号码、指向该结构体的指针。另外，本系统还设置一个全局变量seat,表示成员序号。3、系统功能设计本系统设置5 个子功能：(1)建立通讯录系统：能够一次输入多个成员的信息，建立通讯录。(2)插入通讯录记录：每次能够插入一个成员的信息。(3)查询通讯录记录：能够按两种方式查询所要的记录，一是按学号查询，二是按姓名查询。(4)删除通讯录记录：能够按三种方式删除信息，按序号删除，按学号删除，按姓名删除。资料仅供参考(5)显示通讯录记录：能够查看通讯录中所有

11、成员信息。三、模块设计1、模块设计本程序包含两个模块：主程序模块和链表操作程毋 xn-必+启2、系统子程序及功能设计本系统共设置10个子程序，各程序的函数名及功能说明如下：(1 )LinkList CreateIncreLink()链表的创立(2)deleteElem(LinkList L,int i)/从通讯录中按序号删除第i各元素(3)delName(LinkList L,char n)/按姓名删除通讯者纪录(4)delNum(LinkList L,int n)/按学号删除通讯者纪录(5 )void insertYouXu(LinkList L,LinkList Elem)插入一条通讯录资

12、料仅供参考(6)printList(LinkList L)/打印通讯录(7)prior(LinkList L,LinkList p)/查找位于当前地址元素的前一元素的地址(8)searchName(LinkList L,int n /按姓名查找通讯者记录(9)int searchNum(LinkList L,int n)/按学号查找通讯者记录(10)void main()主函数。设定界面的颜色和大小，调用链表操作模块3、函数主要调用关系图资料仅供参考四、详细设计1、数据类型定义本系统采用链式结构存储通讯录结点。结点定义如下：typedef struct LNode(int number;dou

13、ble telenum;char name20;struct LNode*next;LNode,*LinkList;2、系统主要子程序详细设计(1)建立链表的函数，主要用来建立通讯录。(流程图略)(2)显示链表中所有节点的信息，用于查看通讯录所有的纪录。(流程图略)资料仅供参考五、测试分析系统运行主界面，各子功能测试运行结果如下：(略)六、源程序清单(略)七、用户手册(1)本程序执行文件为“学生通讯录管理系统 exe”。(2)进入本系统之后，随即显示系统主菜单界面。用户可在该界面下输入各子菜单前对应的数字并按回车，执行相应子菜单命令。(3)本系统没有提供直接修改通讯录信息的功能，可经过删除和插入操作完成修改功能。资料仅供参考资料仅供参考附录B实验报告封面、评语得分表数据结构与算法实习实习报告学院：计算机与信息专业：_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _班级：_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _资料仅供参考学号：_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _姓 爸 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _.6.资料仅供参考评语:成绩: