数据结构与算法实习实验指导书.docx
- 文档编号:11580080
- 上传时间:2023-06-01
- 格式:DOCX
- 页数:9
- 大小:25.02KB
数据结构与算法实习实验指导书.docx
《数据结构与算法实习实验指导书.docx》由会员分享,可在线阅读,更多相关《数据结构与算法实习实验指导书.docx(9页珍藏版)》请在冰点文库上搜索。
数据结构与算法实习实验指导书
数据结构与算法课程实习
实验指导书
实验一顺序表的基本操作
【实验目的】
1、掌握顺序存储的概念,学会对顺序表的基本操作。
2、加深对顺序存储数据结构的理解,逐步培养解决实际问题的能力。
【实验性质】
设计型实验
【实验内容】
1、实现顺序表显示;
2、实现顺序表插入;
3、实现顺序表查找(显示比较次数);
4、实现顺序表删除(显示移动次数);
5、实现顺序表排序(分别实现简单选择、快速,显示比较次数、移动次数);
6、实现顺序表的折半查找(显示比较次数);
7、编程实现一个顺序表的就地逆置,即利用原表的存储空间将顺序表逆置;
8、顺序表有序插入(显示比较次数、移动次数),
屏幕提示后,从键盘输入一个元素值,在经过排序的线性表中插入这个元素;
屏幕显示比较次数和移动次数,应有溢出判断和报告;
9、要求以较高的效率实现删除顺序表中元素值在x到y(x和y自定)之间的所有元素;
10、编程实现将两个非递减的顺序表进行合并,要求同样的数据元素只出现一次;
*11、编程实现顺序表的shell排序(步长为5,3,1);
*12、编程实现堆排序算法;
*13、利用三元组顺序表存储矩阵,实现矩阵的转置(请独立写程序实现)。
【实验环境】
VC++
【实验要求】
将如上文件保存在命名为“学号+姓名”的文件夹中并上传到指定的服务器。
实验二链表的基本操作
【实验目的】
1、掌握链表的概念,学会对链表进行操作。
2、加深对链式存储结构的理解,逐步培养解决实际问题的编程能力。
【实验性质】
设计型实验
【实验内容】
1、实现单链表的创建;
2、实现单链表的显示;
3、实现单链表的查找(显示比较次数);
4、实现单链表的插入;
5、实现单链表的删除(显示比较次数);
6、对已创建的链表(数据不限)进行直接插入排序;
7、将链接存储线性表逆置,即最后一个结点变成第1个结点,原来倒数第2个结点变成第2个结点,如此等等;
8、生成有序的两个单链表A和B(链表的数据和个数自定),其首结点指针分别为a和b,要求将两个单链表合并为一个有序的单链表C,其首结点指针为c,并且合并后的单链表的数据不重复;
9、将一个首结点指针为a的单链表A分解成两个单链表A和B,其首结点指针分别为a和b,使得链表A中含有原链表A中序号为奇数的元素,而链表B中含有原链表A中序号为偶数的元素,且保持原来的相对顺序;
10、请编程实现链栈的基本操作函数,并通过调用这些基本函数,实现十进制和八进制转换的功能。
【实验环境】
VC++
【实验要求】
将如上文件保存在命名为“学号+姓名”的文件夹中并上传到指定的服务器。
实验三二叉树的基本操作
【实验目的】
【实验性质】
设计型实验
【实验内容】
、实现二叉树的创建;
2、用递归方法分别先序、中序、后序遍历以Tree为根指针的二叉树;
3、编写递归算法,计算二叉树中叶子结点的数目;
4、编写递归算法,计算二叉树的深度;
5、编写递归算法,将二叉树中所有结点的左、右子树相互交换;
6、使用数组elem中的随机数序列(以0表示结束,不包括0),生成以Tree为根指针的二叉排序树;
7、在以Tree为根指针的二叉排序树中查找结点;
8、从以Tree为根指针的二叉排序树中删除结点(适用各种位置的结点);
9、用非递归算法,先序遍历以Tree为根指针的二叉树;
提示:
用数组BiTNode*stack[max]构成堆栈,利用这个堆栈实现功能。
10、用凹入表示法的表示以Tree为根指针的二叉树,例如:
(1)回车>
将文本插入活区中第<行号>行之后。
(2)行删除。
格式:
d<行号1>[<空格><行号2>]<回车>
删除活区中第<行号1>行(到第<行号2>行)。
例如“d10”和“d1014”
(3)活区切换。
格式:
n<回车>
将活区写入输出文件,并从输入文件中读入下一段,作为新的活区。
(4)活区显示。
格式:
p<回车>
逐页的(每页20行)显示活区内容,每显示一页之后请用户决定是否继续显示以后各页(如果存在)。
印出的每一行要前置行号和一个空格符,行号固定占4位,增量为1。
各条命令中的行号均须在活区中各行行号范围之内,只有插入命令的行号可以等于活区第一行行号减一,表示插入当前屏幕中第一行之前,否则命令参数非法。
测试数据
自行设定,注意测试将活区删空等特殊情况。
实现提示
(1)设活区的大小用行数ActiveMaxLen(可设为100)来描述。
考虑到文本文件行长通常为正态分布,且峰值在60到70之间,用320*ActiveMaxLen大小的字符数组实现存储将造成大量浪费,可以以标准行块为单位为各行分配存储,每个标准行块可含81个字符。
这些行块可以组成一个数组,也可以利用动态链表连接起来。
一行文字可能占多个行块。
行尾可用一个特殊的ASCII字符(如(012)8)标识。
此外,还应记住活区起始行号。
行插入将引起随后各行行号的顺序下推。
(2)初始化函数包括:
请用户提供输入文件名(空串表示无输入文件)和输出文件名,两者不能相同。
然后尽可能多地从输入文件中读入各行,但不超过ActiveMaxLen-x。
x的值可以自定,例如20。
(3)在执行行插入命令的过程中,每接收到一行时都要检查活区大小是否已达ActiveMaxLen。
如果是,则为了在插入这一行之后仍保持活区大小不超过ActiveMaxLen,应将插入点之前的活区部分中第一行输出到输出文件中;若插入点为第一行之前,则只得将新插入的这一行输出。
(4)若输入文件尚未读完,活区切换命令可将原活区中最后几行留在活区顶部,以保持阅读连续性;否则,它意味着结束编辑或开始编辑另一个文件。
(5)可令前三条命令执行后自动调用活区显示。
选作内容
(1)对于命令格式非法等一切错误作严格检查和适当处理。
(2)加入更复杂的编辑操作,如对某行进行串替换;在活区内进行模式匹配等,格式可以为S<行号>@<串1>@<串2><回车>和m<串><回车>。
【实验环境】
VC++
【实验要求】
将如上文件保存在命名为“学号+姓名”的文件夹中并上传到指定的服务器。
附录A实验报告示例
“学生通讯录管理系统”的设计与实现
一、设计要求
1、问题描述
纸质的通讯录已经不能满足大家的要求,容易丢失,查找困难等问题是纸质通讯录所不能克服的缺点。
“学生通讯录管理系统”是为了帮助老师、同学,或者其它一些需要使用通讯录的人员进行管理和分析的一种应用程序。
2、需求分析
(1)输入数据建立通讯录
(2)查询通讯录中满足要求的信息
(3)插入新的通讯录信息
(4)删除不需要的通讯录信息
(5)查看所有的通讯录信息
二、概要设计
为了实现需求分析中的功能,可以从3个方面着手设计
1、主界面设计
为了实现学生通讯录管理系统各功能的管理,设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能,方便用户使用本系统。
2、存储结构设计
本系统主要采用链表结构类型来表示存储在“学生通讯录管理系统”中的信息。
其中,链表结点有4个分量构成:
通讯录成员学号、姓名、电话号码、指向该结构体的指针。
此外,本系统还设置一个全局变量seat,表示成员序号。
3、系统功能设计
本系统设置5个子功能:
(1)建立通讯录系统:
可以一次输入多个成员的信息,建立通讯录。
(2)插入通讯录记录:
每次可以插入一个成员的信息。
(3)查询通讯录记录:
可以按两种方式查询所要的记录,一是按学号查询,二是按姓名查询。
(4)删除通讯录记录:
可以按三种方式删除信息,按序号删除,按学号删除,按姓名删除。
(5)显示通讯录记录:
可以查看通讯录中所有成员信息。
三、模块设计
1、模块设计
本程序包含两个模块:
主程序模块和链表操作模块,其调用关系如下:
2、系统子程序及功能设计
本系统共设置10个子程序,各程序的函数名及功能说明如下:
(1)
(1)LinkListCreateIncreLink()xe”。
(2)
进入本系统之后,随即显示系统主菜单界面。
用户可在该界面下输入各子菜单前对应的数字并按回车,执行相应子菜单命令。
(3)本系统没有提供直接修改通讯录信息的功能,可通过删除和插入操作完成修改功能。
附录B实验报告封面、评语得分表
数据结构与算法实习
实习报告
学院:
计算机与信息
专业:
班级:
学号:
姓名:
2012.6.
评语:
成绩:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 实习 实验 指导书