数据结构上机指导书_实验一
- 格式:doc
- 大小:335.00 KB
- 文档页数:15
实验一线性表操作一、实验目的1熟悉并掌握线性表的逻辑结构、物理结构。
2熟悉并掌握顺序表的存储结构、基本操作和具体的函数定义。
3熟悉VC++程序的基本结构,掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。
4熟悉VC++操作环境的使用以及多文件的输入、编辑、调试和运行的全过程。
二、实验要求1实验之前认真准备,编写好源程序。
2实验中认真调试程序,对运行结果进行分析,注意程序的正确性和健壮性的验证。
3不断积累程序的调试方法。
三、实验内容基本题:1对元素类型为整型的顺序存储的线性表进行插入、删除和查找操作。
加强、提高题:2、编写一个求解Josephus问题的函数。
用整数序列1, 2, 3, ……, n表示顺序围坐在圆桌周围的人。
然后使用n = 9, s = 1, m = 5,以及n = 9, s = 1, m = 0,或者n = 9, s = 1, m = 10作为输入数据,检查你的程序的正确性和健壮性。
最后分析所完成算法的时间复杂度。
定义JosephusCircle类,其中含完成初始化、报数出圈成员函数、输出显示等方法。
(可以选做其中之一)加强题:(1)采用数组作为求解过程中使用的数据结构。
提高题:(2)采用循环链表作为求解过程中使用的数据结构。
运行时允许指定任意n、s、m数值,直至输入n = 0退出程序。
实验二栈、队列、递归应用一、实验目的1熟悉栈、队列这种特殊线性结构的特性2熟练掌握栈、队列在顺序存储结构和链表存储结构下的基本操作。
二、实验要求1实验之前认真准备,编写好源程序。
2实验中认真调试程序,对运行结果进行分析,注意程序的正确性和健壮性的验证。
3不断积累程序的调试方法。
三、实验内容基本题(必做):1分别就栈的顺序存储结构和链式存储结构实现栈的各种基本操作。
2、假设以带头结点的循环链表表示队列,并且只设一个指针指向对尾结点,不设头指针,试设计相应的置队空、入队和出队的程序。
加强题:3设线性表A中有n个字符,试设计程序判断字符串是否中心对称,例如xyzyx和xyzzyx都是中心对称的字符串。
《数据结构和算法》实验指导书实验及学时数分配序号实验名称学时数(小时)1 实验一线性表 42 实验二树和二叉树 23 实验三图 24 实验四查找 25 实验五内部排序 2合计12几点要求:一、上机前:认真预习相关实验内容,提前编写算法程序,上机时检查(未提前编写程序者,扣除平时成绩中实验相关分数)。
二、上机中:在Turbo C或VC6.0环境中,认真调试程序,记录调试过程中的问题、解决方法以及运行结果。
上机时签到;下机时验收签字。
三、下机后:按要求完成实验报告,并及时提交(实验后1周内)。
实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法;2、掌握线性表的基本操作,插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算;3、运用线性表解决线性结构问题。
【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现;2、单链表的插入、删除操作的实现;3、两个线性表合并算法的实现。
(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时,必须先将线性表中第i个元素之后的所有元素依次后移一个位置,以便腾出一个位置,再把新元素插入到该位置。
若是欲删除第i个元素时,也必须把第i个元素之后的所有元素前移一个位置;2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时,只需先确定第i个元素前一个元素位置,然后修改相应指针将新元素插入即可。
若是欲删除第i个元素时,也必须先确定第i个元素前一个元素位置,然后修改相应指针将该元素删除即可;3、详细原理请参考教材。
【实验步骤】一、用C语言编程实现建立一个顺序表,并在此表中插入一个元素和删除一个元素。
1、通过键盘读取元素建立线性表;(从键盘接受元素个数n以及n个整形数;按一定格式显示所建立的线性表)2、指定一个元素,在此元素之前插入一个新元素;(从键盘接受插入位置i,和要插入的元素值;实现插入;显示插入后的线性表)3、指定一个元素,删除此元素。
华南农业大学数据结构上机实验指导书及答案目录实验一线性表 (1)(一) 实验目的 (1)(二) 实验内容 (1)(三) 实验报告 (45)实验二堆栈 (47)(一) 实验目的 (47)(二) 实验内容 (47)(三) 实验报告 (86)实验三队列 (87)(一) 实验目的 (87)(二) 实验内容 (87)(三) 实验报告 (102)实验四模式匹配 (104)(一) 实验目的 (104)(二) 实验内容 (104)(三) 实验报告 (117)实验五二叉树 (119)(一) 实验目的 (119)(二) 实验内容 (119)(三) 实验报告 (176)实验六查找 (177)(一) 实验目的 (177)(二) 实验内容 (177)(三) 实验报告 (197)实验七内部排序 (198)(一) 实验目的 (198)(二) 实验内容 (198)(三) 实验报告 (233)实验八图和图的遍历 (234)(一) 实验目的 (234)(二) 实验内容 (234)(三) 实验报告 (272)数据结构课程设计(2007级用,仅做参考) (273)(一) 数据结构课程设计安排 (273)(二) 图算法实验题目 (273)(三) 团队题目(各种排序算法效率分析) (274)《数据结构》模拟试卷一 (283)《数据结构》模拟试卷二 (290)附录1:实验报告及习题 (298)实验名称:线性表(一) (298)实验名称:堆栈(二) (302)实验名称:队列(三) (306)实验名称:模式匹配(四) (313)实验名称:二叉树(五) (318)实验名称:查找(六) (324)实验名称:内部排序(七) (329)实验名称:图和图的遍历(八) (339)设计性、综合性实验 (344)附录2 数据结构课程设计完成情况登记表 (347)附录3 图的应用 (350)实验一线性表(一) 实验目的(1)掌握线性表的顺序存储(2)掌握线性表的链式存储(3)掌握基本算法(建表、插入、删除)的实现(二) 实验内容1. 线性表的顺序存储:掌握线性表的顺序存储结构及其基本操作、合并、逆置等算法设顺序表的存储结构定义如下:(同学们可扩展考虑其他形式的存储结构定义)#define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量#define LISTINCREMENT 10 // 线性表存储空间的分配增量typedef struct{int *elem; // 存储空间基址int length; // 当前长度int listsize; // 当前分配的存储容量(以sizeof(int)为单位)}SqList;[题目1:编写算法,创建初始化容量为LIST_INIT_SIZE的顺序表T,并实现插入、删除、遍历操作。
《数据结构》实验指导书实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法;2、掌握线性表的基本操作,插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算;3、运用线性表解决线性结构问题。
【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现;2、单链表的插入、删除操作的实现;3、两个线性表合并算法的实现。
(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时,必须先将线性表中第i个元素之后的所有元素依次后移一个位置,以便腾出一个位置,再把新元素插入到该位置。
若是欲删除第i个元素时,也必须把第i个元素之后的所有元素前移一个位置;2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时,只需先确定第i个元素前一个元素位置,然后修改相应指针将新元素插入即可。
若是欲删除第i个元素时,也必须先确定第i个元素前一个元素位置,然后修改相应指针将该元素删除即可;3、详细原理请参考教材。
【实验步骤】一、用C语言编程实现建立一个顺序表,并在此表中插入一个元素和删除一个元素1、通过键盘读取元素建立线性表;2、指定一个元素,在此元素之前插入一个新元素;3、指定一个元素,删除此元素。
二、用C语言编程实现建立一个单链表,并在此表中插入一个元素和删除一个元素1、通过键盘读取元素建立单链表;2、指定一个元素,在此元素之前插入一个新元素;3、指定一个元素,删除此元素。
三、用C语言编程实现两个按递增顺序排列线性表的合并1、编程实现合并按递增顺序排列的两个顺序表算法;2、编程实现合并按递增顺序排列的两个单链表算法。
【思考问题】结合实验过程,回答下列问题:1、何时采用顺序表处理线性结构的问题为最佳选择;2、何时采用链表处理线性结构的问题为最佳选择。
【实验报告要求】1、根据对线性表的理解,如何创建顺序表和单链表;2、实现顺序表插入和删除操作的程序设计思路;3、实现链表插入和删除操作的程序设计思路;4、实现两表合并操作的程序设计思路;5、调试程序过程中遇到的问题及解决方案;6、本次实验的结论与体会。
《数据结构与算法》实验指导书实验及学时数分配几点要求:一、上机前:认真预习相关实验内容,提前编写算法程序,上机时检查(未提前编写程序者,扣除平时成绩中实验相关分数)。
二、上机中:在Turbo C或VC6.0环境中,认真调试程序,记录调试过程中的问题、解决方法以及运行结果。
上机时签到;下机时验收签字。
三、下机后:按要求完成实验报告,并及时提交(实验后1周内)。
实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法;2、掌握线性表的基本操作,插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算;3、运用线性表解决线性结构问题。
【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现;2、单链表的插入、删除操作的实现;3、两个线性表合并算法的实现。
(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时,必须先将线性表中第i个元素之后的所有元素依次后移一个位置,以便腾出一个位置,再把新元素插入到该位置。
若是欲删除第i个元素时,也必须把第i个元素之后的所有元素前移一个位置;2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时,只需先确定第i个元素前一个元素位置,然后修改相应指针将新元素插入即可。
若是欲删除第i个元素时,也必须先确定第i个元素前一个元素位置,然后修改相应指针将该元素删除即可;3、详细原理请参考教材。
【实验步骤】一、用C语言编程实现建立一个顺序表,并在此表中插入一个元素和删除一个元素。
1、通过键盘读取元素建立线性表;(从键盘接受元素个数n以及n个整形数;按一定格式显示所建立的线性表)2、指定一个元素,在此元素之前插入一个新元素;(从键盘接受插入位置i,和要插入的元素值;实现插入;显示插入后的线性表)3、指定一个元素,删除此元素。
(从键盘接受删除元素位置i,实现删除;显示删除后的线性表)二、用C语言编程实现建立一个单链表,并在此表中插入一个元素和删除一个元素。
数据结构实验指导书实验一线性表[实验目的]1.了解顺序表的结构特点及有关概念,掌握顺序表建立、插入、删除的基本操作算法。
2.了解单链表的结构特点及有关概念,掌握单链表建立、插入、删除的基本操作算法。
[实验内容]1.顺序表的实践。
1)建立4个元素的顺序表list[]={2,3,4,5},实现顺序表建立的基本操作。
2)在list[]={2,3,4,5}的元素4和5之间插入一个元素9,实现顺序表插入的基本操作。
3)在list[]={2,3,4,9,5}中删除指定位置(i=3)上的元素9,实现顺序表的删除的基本操作。
2.单链表的实践。
1)建立一个包括头结点和3个结点的(4,2,1)的单链表,实现单链表建立的基本操作。
2)在已建好的单链表中的指定位置(x=2)插入一个结点3,实现单链表插入的基本操作。
3)在一个包括头结点和4个结点的(4,2,3,1)的单链表的指定位置删除一个结点,实现单链表删除的基本操作。
[实验要点及说明]线性表(linear list)是n(n≥0)个数据元素a1,a2,…a n组成的有限序列。
其中n 称为数据元素的个数或线性表的长度,当n=0时称为空表,n>0时称为非空表。
通常将非空的线性表记为(a1,a2,…,a n),其中的数据元素a i(1≤i≤n)是一个抽象的符号,a i是第i个数据元素,称i为数据元素a i在线性表中的位置。
其具体含义在不同情况下是不同的,即它的数据类型可以根据具体情况而定,本书中,我们将它的类型设定为elemtype,表示某一种具体的已知数据类型。
顺序表也称为线性表的顺序存储结构。
其存储方式为:在内存中用一组地址连续的存储单元依次存储线性表的数据元素,但该连续存储空间的大小要大于或等于顺序表的长度。
一般让线性表中第一个元素存放在连续存储空间第一个位置,第二个元素紧跟着第一个之后,其余依此类推。
可定义顺序表如下:#define maxnumelemtype list[maxnum];int num=-1;线性表的链式存贮结构,也称为链表。
数据结构上机实验指导(1)《数据结构》课程上机实验指导书实验一【实验名称】顺序表的基本算法【实验目的】创建一个顺序表,掌握线性表顺序存储的特点。
设计和验证顺序表的查找、插入、删除算法。
【实验要求】(1)从键盘读入一组整数,按输入顺序形成顺序表。
并将创建好的顺序表元素依次打印在屏幕上。
(2)设计一个带选择菜单的主函数,菜单中具备任意选择删除、插入、查找数据元素的功能。
(3)当选择删除功能时,从键盘读入欲删除的元素位置或元素值,按指定方式删除;当选择插入功能时,从键盘读入新元素值和被插入位置,在指定位置插入;当选择查找功能时,从键盘读入欲查找的元素值,返回其位置序号。
(4)每种操作结束后,都能在屏幕上打印出此时顺序表元素的遍历结果。
【实验步骤】1、实验前先写好算法。
2、上机编写程序。
3、编译。
4、调试。
例程:书上参考算法2-1,2-4,2-5,2-6,2-8!带菜单的主函数参考书上2.5综合实例!注意:顺序表的结构体!typedef struct{datatype items[listsize];int length;}SpList;实验二【实验名称】单链表的基本算法【实验目的】创建一个单链表,掌握线性表链式存储的特点。
设计和验证链表的查找、插入、删除、求表长的算法。
【实验要求】(1)从键盘读入一组整数,按输入顺序形成单链表。
并将创建好的单链表元素依次打印在屏幕上。
(注意:选择头插法或者尾插法!)(2)设计一个带选择功能菜单的主函数,菜单中至少具备任意选择删除、插入、查找数据元素,和求单链表表长等几项功能。
(3)当选择删除功能时,从键盘读入欲删除的元素位置,按指定位置删除;当选择插入功能时,从键盘读入新元素值和被插入位置,在指定位置插入;当选择查找功能时,从键盘读入欲查找的元素值,返回其位置序号;当选择求表长功能时,返回该单链表表长的数值。
(4)每种操作结束后,都能在屏幕上打印出此时单链表元素的遍历结果。
数据结构实验指导书数据结构实验指导书目录数据结构实验指导书 (1)目录 (1)实验指导书概述 (2)实验题目 (3)实验一单链表的插入、删除 (3)[实验目的] (3)[实验内容] (3)[测试数据] (3)[实现提示] (3)实验二栈及其应用 (5)[实验目的] (5)[实验内容] (5)[测试数据] (5)实验三二叉树的递归算法 (5)[实验目的] (5)[实验内容] (6)[测试数据] (6)实验四查找及排序算法的应用 (7)[实验目的] (7)[实验内容] (7)[测试数据] (7)实验指导书概述“数据结构”是计算机专业一门重要的专业技术基础课程,是一门关键性核心课程。
本课程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法,介绍了多种常用的查找和排序技术,并对其进行了性能分析和比较,内容非常丰富。
本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。
由于以下原因,使得掌握这门课程具有较大难度:∙内容多,时间短,给学习带来困难;∙贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点;∙隐含在各部分的技术和方法丰富,也是学习的重点和难点;∙先修课程中所介绍的专业性知识不多,加大了学习难度。
由于数据结构课程的技术性与实践性,《数据结构课程实验》的设置十分必要。
为了帮助学生更好地学习本课程,理解和掌握算法设计所需的技术,为整个专业学习打好基础,要求运用所学知识,上机解决一些典型问题,通过分析、设计、编码、调试等各环节的训练,使学生深刻理解、牢固掌握所用到的一些技术。
数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法,如算法设计的构思方法,动态链表,算法的编码,递归技术,与特定问题相关的技术等,要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。
在掌握基本算法的基础上,掌握分析、解决实际问题的能力。
通过实验实践内容的训练,突出构造性思维训练的特征, 提高学生组织数据及编写大型程序的能力。
目录实验1 顺序表的应用 (2)实验2 链表的应用 (5)实验3 栈的应用 (6)实验4 队列的应用 (7)实验5 树的应用 (9)实验6 图的应用 (10)实验7 图的应用 (11)实验8 查找与排序 (12)0 实验要求一、实验步骤⒈问题分析充分地分析和理解问题本身,弄清要求做什么,包括功能要求、性能要求、设计要求和约束以及基本数据特性,数据间的联系等。
⒉数据结构设计针对要求解决的问题,考虑各种可能的数据结构,并且力求从中找出最佳方案(必须连同算法一起考虑),确定主要的数据结构及全局变量。
对引入的每种数据结构和全局变量要详细说明其功能、初值和操作特点。
⒊算法设计算法设计分概要设计和详细设计,概要设计着重解决程序的模块设计问题,这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模块,并决定模块的接口,即模块间的相互关系以及模块之间的信息交换问题.详细设计则要决定每个模块内部的具体算法,包括输入、处理和输出,采用类C语言描述。
⒋测试用例设计准备典型测试数据和测试方案,测试数据要有代表性、敏感性,测试方案包括模块测试和模块集成测试。
⒌上机调试对程序进行编译,纠正程序中可能出现的语法错误,测试前,先运行一遍程序看看究竟将会发生什么,如果错误较多,则根据事先设计的测试方案并结合现场情况进行错误跟踪,包括打印执行路径或输出中间变量值等手段。
二、实验报告每次实验结束后,均应撰写实验报告。
实验报告应包括如下内容:1、问题描述:简述题目要解决的问题是什么。
2、设计:概要设计采用抽象数据类型描述,详细设计包括存储结构的定义、主要操作算法设计等。
用类C语言或用框图描述。
3、调试报告:调试过程中遇到的问题是如何解决的;对设计和编码的讨论和分析。
4、运行结果。
可以贴相应的运行结果截图。
5、算法分析与改进:算法的时间复杂度和空间复杂度分析;算法改进的设想。
6、经验和体会所有实验做完后,上交上机实验源程序和相应的运行结果截图。
数据结构与算法实验指导书中国石油大学()计算机科学与技术系前言《数据结构》是计算机及相关专业的一门核心基础课程,也是很多高校考研专业课之一。
它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现,在此基础上介绍一些典型算法及时、空效率分析。
这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。
通过学习,要求学生能够掌握典型算法的设计思想及程序实现,能够根据实际问题选取合适的存储方案,设计出简洁、高效、实用的算法,为后续课程的学习及软件开发打下良好的基础。
学习这门课程,习题和实验是两个关键环节。
学生理解算法,上机实验是最佳的途径之一。
因此,实验环节的好坏是学生能否学好《数据结构》的关键。
为了更好地配合学生实验,特编写实验指导书。
一、实验目的更好的理解算法的思想、培养编程能力。
二、实验要求1、每次实验前学生必须根据试验容认真准备实验程序及调试时所需的输入数据。
2、在指导教师的帮助下能够完成实验容,得出正确的实验结果。
3、实验结束后总结实验容、书写实验报告。
4、遵守实验室规章制度、不缺席、按时上、下机。
5、实验学时必须做数据结构的有关容,不允许上网聊天或玩游戏,如发现上述现象,取消本次上机资格,平时成绩扣10分。
6、实验报告有一次不合格,扣5分,两次以上不合格者,平时成绩以零分记。
三、实验环境 VC++6.0或者VC2010四、说明1、本实验的所有算法中元素类型可以根据实际需要选择。
2、实验题目中带*者为较高要求,学生可自选;其余部分为基本容,应尽量完成(至少完成70%,否则实验不合格)。
3、数据结构是很多高校的硕士研究生入学考试的专业课之一,希望有志于考研的学生能够在学习过程中注意各种算法的理解,以便为考研做一定的准备。
五、实验报告的书写要求1.明确实验的目的及要求;2.记录实验的输入数据和输出结果;3.说明实验中出现的问题和解决过程;4.写出实验的体会和实验过程中没能解决的问题;六、参考书目《数据结构》(C++语言描述)王红梅等清华大学《DATA STRUCTURE WITH C++》 William Ford,William Topp清华大学(影印版)实验平台控制台程序1、启动Microsoft VC6.0集成开发环境如图所示:2、单击“文件”菜单,选择“新建”项。
数据结构上机实验一实验内容:单链表的基本操作实验要求:1)链表的显示要作为函数被调用.2)把自己使用的单链表结构明确的表达出来.3)要求都是带头结点的单链表.分组要求:可单独完成,也可两人一组。
实验目的:1)熟悉C/C++基本编程,培养动手能力.2)通过实验,加深对链表的理解.评分标准:1) 第一题必做;2)其它题为选做,不设上限。
3)上机结束后,由助教检查结果并适当提问,根据情况给出成绩。
上机题目:一)建立单链表+求长度+显示(3分)(1) 由键盘逐个输入正整数,建立相应的链表,输入-1时,链表结束;(2) 显示链表中的元素 (要求在显示器可见);(3) 求链表的长度;(4)求链表的第i个元素;(i为参数)二)查找+插入+删除+显示(1分)在题目(一)的单链表中:(1)在链表中第i个位置插入新的数据元素,显示链表;(2)删除链表的第i个元素,输出该元素,显示链表;三)就地置逆+求最大最小值(1分)在题目(一)的单链表中:(1)将链表就地逆置,显示链表;(2)求链表中的最大,最小值,显示结果;#include<stdio.h>#include<malloc.h>typedef struct Lnode{int data;struct Lnode *next;}LNode, *LinkList;LinkList CreatList_L(void){LinkList head;LinkList p1,p2;head=p1=p2=(LinkList)malloc(sizeof(LNode));scanf("&d",&p1->data);head->next=p1;while(p1->data!=-1){p2->next=p1;p2=p1;p1=(LinkList)malloc(sizeof(LNode));scanf("%d",&p1->data);}p2->next=NULL;return head;}void ShowList(LinkList L){printf("\nHere is the list:\n");LinkList p;p=L->next;while(p!=NULL){printf("%d\n",p->data);p=p->next;}printf("\n");}int LenList(LinkList L){LinkList p;p=L->next;int n=0;while(p!=NULL){n++;p=p->next;}return n;}LinkList InsertList(LinkList L,LinkList InsertNode,int i){ LinkList p0,p1,p2,p3;int n=1;p3=p1=L;p0=InsertNode;while(n<=i){p2=p1;p1=p1->next;n++;}p0->next=p1;p2->next=p0;return p3;}LinkList DeleteList(LinkList L,int i){LinkList p1,p2,p3;int n=1;p3=p1=L;while(n<=i){p2=p1;p1=p1->next;n++;}p1=p1->next;p2->next=p1;return p3;}int GetElem(LinkList L,int i){LinkList p;int n=1,m;p=L;while(n<=i){p=p->next;n++;}m=p->data;return m;}void InverseList(LinkList L){LinkList p,q;p=L->next;L->next=NULL;while(p){q=p->next;p->next=L->next;L->next=p;p=q;}}void MostList(LinkList L){LinkList p;int i,j;p=L->next;i=j=p->data;while(p){if(i<p->data)i=p->data;if(j>p->data)j=p->data;p=p->next;}printf("The maximum is:%d\n",i);printf("The minimum is:%d\n",j); }void main(){int n,i,j,k;LinkList L,InsertNode;printf("Input the list:");L=CreatList_L();ShowList(L);n=LenList(L);printf("\nThe length of List is %d\n",n);InsertNode=(LinkList)malloc(sizeof(LNode));printf("Input the inertnode(data and location):");scanf("%d,%d",&InsertNode->data,&i);L=InsertList(L,InsertNode,i);ShowList(L);printf("Input the deletenode(location):");scanf("%d",&j);k=GetElem(L,j);printf("The delete elem is %d\n",k);DeleteList(L,j);ShowList(L);printf("The inverselist is:");InverseList(L);ShowList(L);MostList(L);}四) 链表的合并(1分)(1)创建两个链表LA,LB(各链表按升序排列),分别显示两链表;(2)将两个链表合并成一个新的有序表(升序排列),显示链表. #include<stdio.h>#include<malloc.h>typedef struct Lnode{int data;struct Lnode *next;}LNode, *LinkList;LinkList CreatList_L(void){LinkList head;LinkList p1,p2;head=p1=p2=(LinkList)malloc(sizeof(LNode));scanf("&d",&p1->data);head->next=p1;while(p1->data!=-1){p2->next=p1;p2=p1;p1=(LinkList)malloc(sizeof(LNode));scanf("%d",&p1->data);}p2->next=NULL;return head;}void ShowList(LinkList L){printf("\nHere is the list:\n");LinkList p;p=L->next;while(p!=NULL){printf("%d\n",p->data);p=p->next;}printf("\n");}int LenList(LinkList L){LinkList p;p=L->next;int n=0;while(p!=NULL){n++;p=p->next;}return n;}LinkList SortList(LinkList L){LinkList first,last,head,min,p,q;first=NULL;head=L->next;while(head){for(p=head,min=head;p->next!=NULL;p=p->next){if (p->next->data < min->data){q=p;min=p->next;}}if (first == NULL){first=min;last=min;}else{last->next=min;last=min;}if (min == head)head = head->next;else q->next=min->next;last->next=NULL;}head=first;return head;}LinkList MergeList(LinkList La,LinkList Lb){ LinkList L3,p1,p2,p3;p1=La->next;p2=Lb->next;L3=p3=La;while(p1&&p2){if(p1->data<=p2->data){p3->next=p1;p3=p1;p1=p1->next;}else{p3->next=p2;p3=p2;p2=p2->next;}}if(p1)p3->next=p1;else p3->next=p2;return L3;}void main(){LinkList L1,L2,L3;printf("Input List1:");L1=CreatList_L();printf("Input List2:");L2=CreatList_L();printf("L1\n");ShowList(L1);printf("L2\n");ShowList(L2);L1->next=SortList(L1);L2->next=SortList(L2);printf("The new L1\n");ShowList(L1);printf("The new L2\n");ShowList(L2);L3=MergeList(L1,L2);printf("The new merge list\n");ShowList(L3);}五)单循环链表(2分)(1)建两个带头结点的循环单链表LA,LB单循环链表,(2)将两个循环单链表合并为一个循环单链表,其头指针为LA。
计算机系第一部分数据结构课程实验概述一.实验目的《数据结构》是计算机专业的主干课程和必修课程之一,其目的是让大家学习、分析和研究数据对象特征,掌握数据组织方法和计算机的表示方法,以便选择合适的数据逻辑结构和存储结构,设计相应的运算操作,把现实世界中的问题转化为计算机内部的表示与处理的方法,要求掌握算法的时间、空间复杂度分析基本技术,培养良好的程序设计风格,掌握进行复杂程序设计的技能。
在计算机科学领域,尤其是在系统软件和应用软件的设计和应用中要用到各种数据结构,因此,掌握数据结构对提高软件设计和程序编制水平有很大的帮助。
二.实验要求2.1实验步骤设计步骤的规范不但可以培养学生科学的工作方法和作风,而且还能有效地减少错误,提高工作效率。
因此必须严格执行良好的实验步骤规范(包括上机操作规范)。
本课程实验的基本步骤是:2.1.1问题分析充分地分析和理解问题本身,明确问题要求做什么。
对问题的描述应避开算法和所涉及的数据类型,而是对所需完成的任务作出明确的回答。
例如;输入、输出数据的类型、值的范围以及形式等。
同时为调试程序准备好测试数据,包含合法的输入数据和非法形式输入的数据。
2.1.2设计和编码设计即是对问题描述中涉及的操作对象定义相应的数据类型,定义主程序模块和各抽象数据类型;定义相应的存储结构并写出各过程和函数的伪码算法。
在这个过程中,要综合考虑系统功能,使得系统结构清晰、合理、简单和易于调试。
编码即把详细设计的结果进一步求精为程序设计语言程序,写出源程序。
对程序中的疑问应作出记号,以便上机时注意解决。
每个明确的功能模块程序一般不超过60行,程序的每一行不得超过60个字符,否则要进一步划分。
2.1.3上机前程序静态检查上机前程序静态检查可有效提高调试效率,减少上机调试程序时的无谓错误。
静态检查主要有两种途径:用一组测试数据手工执行程序;通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。
把程序中的明显错误事先排除。
课程名称:数据结构上机学时:16适用专业:计算机科学与技术先修课程:C语言一、上机实验总体目标数据结构是信息管理与信息系统专业的一门综合性的专业基础课,实践性很强,要求学生具备应用所学理论知识独立解决实际问题的能力,上机实验正是针对此目标进行的重要训练。
通过上机实验,使学生对本课程的知识体系有较深入的理解,在运用本课程的知识解决实际问题方面得到锻炼,对锻炼学生的实践能力以及运用本课程的知识、方法解决更为复杂的实际问题有较好的启发和指导作用,从而为后续软件课程的学习、毕业设计环节以及将来的实际工作打好坚实的基础。
三、上机实验环境硬件:CPU P3 500Hz,内存256MB,硬盘500MB或以上软件:Windows XP Professional简体中文版,Visual C++ 6.0或Turbo C 2.0四、参考书(3种以上)1、《数据结构》,颜为民编,清华大学出版社2004年2、《数据结构教程》,李春葆编著,清华大学出版社,2005年。
3、《数据结构基础教程》文益民等编著,清华大学出版社/北京交通大学出版社,2005。
4、《数据结构(面向对象方法与C++描述)》,殷人昆/陶永雷/谢若阳等,清华大学出版社,2004年。
实验二线性链表2.1 实验目的1、理解线性链表的基本概念和存储结构。
2、掌握线性链表的基本运算方法。
3、掌握线性链表的基本应用。
2.2 实验内容1、实验准备本程序是一个完整且子函数较多的线性链表源程序,目的是为学生提供一个示范,以供学生分析、比较程序与算法设计的不同。
要求学生阅读程序时给出函数具体执行的详细注释。
#include <stdio.h>#include <stdlib.h>#include <conio.h>#include <math.h>typedef int ElemType;typedef struct LNode{ ElemType data;struct LNode *next;} LNode;LNode *L;//建立线性链表,输入-111时终止LNode *creat( ){LNode *h, *p, *s; ElemType x;h = (LNode *)malloc(sizeof(LNode));h->next = NULL;p = h;printf("\ndata=? ");scanf("%d", &x);while(x != -111){s = (LNode *)malloc(sizeof(LNode));s->data = x; s->next = NULL;p->next = s; p = s;printf("data=? ");scanf("%d", &x);}return (h);}//输出单链表中的数据元素void out_L(LNode *L){LNode *p; char ch;p = L->next; printf("\n\n线性链表:");while(p != NULL){printf("%5d",p->data);p = p->next;} ch = getch();}//在i位置插入元素evoid insert_L(LNode *L, int i, ElemType e){LNode *s, *p; int j;p = L; j = 0;while(p !=NULL && j<i-1){p = p->next; j++;}if(p == NULL || j>i-1) printf("\n i ERROR !");else {s = (LNode *)malloc(sizeof(LNode));s->data = e;s->next = p->next; p->next = s;}}//查找值为e的元素,返回它的位置int locat_L(LNode *L, ElemType e){LNode *p; int j=1;p = L->next;while(p !=NULL && p->data!=e){p = p->next; j++;}if(p != NULL) return (j);else return (-1);}int main( ){int i, k, loc; ElemType e; char ch;do{printf("\n\n\n");printf("\n\n 1. 建立线性链表");printf("\n\n 2. 在i位置插入元素e");printf("\n\n 3. 查找值为e的元素");printf("\n\n 4. 结束程序运行");printf("\n\n 如果输入-111,则结束循环!");printf("\n===================================");printf("\n 请输入您的选择(1,2,3,4): "); scanf("%d", &k);switch(k){case 1: { L = creat( ); out_L(L); } break;case 2: { printf("\n i,e=?"); scanf("%d%d",&i,&e);insert_L(L,i,e); out_L(L); } break;case 3: { printf("\n e=? "); scanf("%d",&e); loc=locat_L(L,e);if(loc==-1) printf("\n 未找到%d",loc);else printf("\n 该元素位置为:%d",loc);} break;}printf("\n ----------------------------------------------------------");} while(k>=1 && k<4);printf("\n 按回车键,返回。
《数据结构》实验指导书(适用于计算机科学与技术、网络工程、软件工程专业)计算机科学与技术学院软件教研室2006-8目录前言 (3)实验一、单链表的基本操作 (4)实验二、二叉树的遍历 (6)实验三、折半查找和二叉排序树 (8)实验四、内部排序 (10)前言《数据结构》是计算机科学与技术、网络工程等专业的专业基础必修课,主要介绍如何合理地组织数据、有效地存储和处理数据,正确地设计算法以及对算法进行分析和评价。
本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法,培养学生基本的、良好的程序设计技能以及针对具体问题,选择适当的数据结构,设计出有效算法的能力。
《数据结构》是一门理论和实践相结合的课程,它在整个计算机专业教学体系中处于举足轻重的地位,是计算机科学的算法理论基础和软件设计的技术基础,其上机实验的目的主要是编程实现数据结构各章的主要算法,训练学生实际动手进行程序设计和程序调试的能力,加深对数据结构相关概念和算法的理解。
实验一、单链表的基本操作一、实验目的1、掌握线性链表的操作特点,即指针是逻辑关系的映像。
2、掌握动态产生单链表的方法。
3、熟练掌握单链表的插入、删除操作特点,即指针赋值的先后次序。
4、熟练掌握单链表的取元素操作二、实验内容1、定义单链表类型并动态创建单链表2、实现线性表链式存储结构下元素的插入操作3、实现线性表链式存储结构下元素的删除操作4、实现线性表链式存储结构下取元素操作三、实验环境TC或VC++或Java四、实验步骤1、单链表的存储定义2、从键盘上依次输入21、18、30、75、42、56,逆序创建单链表,并输出单链表中的各元素值。
3、分别在单链表的第3个位置和第9个位置插入67和10,给出插入成功或失败的信息,并输出单链表中的各元素值。
4、删除单链表中的第6个数据元素和第8个数据元素,给出删除成功或失败的信息,并输出单链表中的各元素值。
5、取单链表中的第5个数据元素和第7个数据元素五、问题讨论1、单链表具有什么优缺点?2、单链表的定义与顺序表的定义有什么区别?3、逆序创建单链表有什么好处?4、为什么单链表中取元素、插入和删除操作在开始不判断给定位置i的合法性?5、如何改进单链表的定义,使其可以在操作前判断判断给定位置i的合法性?六、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录,实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果6、问题回答7、实验心得实验二、二叉树的遍历一、实验目的1、掌握二叉树的特点及其存储方式。
实验一线性表的操作一、实验目的1.掌握在VC++6.0的集成环境中调试程序的基本方法。
2.掌握线性表的插入和删除操作在顺序存储结构和链式存储结构上的实现。
二、实验内容(三选一)(一)线性表的插入和删除操作在顺序存储结构和链式存储结构上的实现。
(1)线性表的插入和删除操作在顺序存储结构上的实现。
其中函数ListInsert_Sq的功能是在顺序线性表中第i个元素之前插入一个元素,函数ListDelete_Sq的功能是删除顺序线性表中第i个元素。
#define LIST_INIT_SIZE 1000#define LISTINCREMENT 10#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define OK 1#define ERROR 0#define OVERFLOW -2//顺序表的存储结构定义typedef int Status;typedef int ElemType;typedef struct{ElemType *elem; //首地址int length; //顺序表的长度int listsize; //顺序表的存储容量} SqList;Status InitList_Sq(SqList &L) // 顺序表的初始化{}// InitList_Sq(Status ListInsert_Sq (SqList &L, int i, ElemType e) //插入{ //在顺序表的第i个位置插入值e为的元素}// ListInsert_SqStatus ListDelete_Sq(SqList &L, int i, ElemType &e) //删除{ //在顺序表的第i个位置删除一个元素,值在存进e中}// ListDelete_Sqint main( ){ElemType y;SqList L;int i,n;InitList_Sq(L); /* 初始化线性表*/printf("输入顺序表需存进的元素数量!\n");scanf("%d",&n);while(n<1 || n>10){printf("请输入1--10之间的整数!\n");scanf("%d",&n);}/* 以上循环语句的功能是控制输入数据个数的合法性,可以修改*/printf("依次输入存进顺序表中的数据元素:\n");for(i=1;i<=n;i++){scanf(“%d”,&y);ListInsert_Sq(L,i,y) ;}/* 以上循环语句的功能是依次输入要存进顺序表中的元素,并存进顺序表*/printf("顺序表中的元素为:");for(i=0; i<L.length; i++) printf("%d\t",L.elem[i]);/* 以上循环语句的功能是依次输出顺序表中的元素*/printf("\n");printf(“输入要删除元素的位置!\n”);scanf(“%d”,&n);if(ListDelete_Sq(L,n,y)==OK) { printf(“删除成功!”); printf("被删除的元素是:%d\n",y); }printf("顺序表中的元素为:");for(i=0; i<L.length; i++) printf("%d\t",L.elem[i]);/* 以上循环语句的功能是依次输出顺序表中的元素*/printf("\n");system("pause");return 0;}实验程序运行示例:(2)线性表的建立、插入、删除、打印和查找操作在链式存储结构上的实现。
数据结构实验指导书含答案《数据结构》实验指导书专业:__电子商务___班级:___ 级电商2班_____组序:_____________学号:__12134675_____姓名:____王苏桐____中国矿业大学管理学院年 12 月上篇程序设计基础实验一 Java编程环境【实验目的】1.掌握下载Java sdk软件包、Eclipse软件的安装和使用方法2.掌握设置Java程序运行环境的方法3.掌握编写与运行Java程序的方法4.了解Java语言的概貌【实验内容】一 JDK下载与安装1. 下载JDK为了建立基于SDK的Java运行环境,需要先下载免费SDK软件包。
SDK包含了一整套开发工具,其中包含对编程最有用的是Java编译器、Applet查看器和Java解释器。
下载链接。
2.安装SDK运行下载的JDK软件包,在安装过程中能够设置安装路径及选择组件,默认的组件选择是全部安装,安装成功后,其中bin文件夹中包含编译器(javac.exe)、解释器(java.exe)、Applet查看器(appletviewer.exe)等可执行文件,lib文件夹中包含了所有的类库以便开发Java程序使用,demo文件夹中包含开源代码程序实例。
安装成功后,文件和子目录结构如图1所示。
其中bin文件夹中包含编译器(javac.exe)、解释器(java.exe)、Applet查看器(appletviewer.exe)等可执行文件,lib文件夹中包含了所有的类库以便开发Java程序使用,sample文件夹包含开源代码程序实例,src压缩文件中包含类库开源代码。
图1二.设置环境变量JDK中的工具都是命令行工具,需要从命令行即MS-DOS提示符下运行它们。
很多人可能会不习惯,但这是Sun特意采取的策略,为的是把精力更多投入到Java语言本身而不是花在开发工具上。
以Windows XP 为例说明设置过程。
右击桌面“我的电脑”图标,选择“属性”菜单图 2在“高级”选项卡中单击“环境变量”按钮,将出现“环境变量”设置界面图 3在“系统变量”框中点击“新建”按钮,在出现的“编辑系统变量”对话框中,在“变量名”栏的文本框内输入“JavaHome”,在变量值栏的文本框内输入jdk安装的主目录。
《数据结构》实验指导(一)数据结构实验指导(一)1. 实验背景数据结构是计算机科学中的一个重要概念,它描述了如何组织和存储数据以及如何通过不同的操作来访问和修改这些数据。
在本实验中,我们将学习和实践数据结构中的线性表和链表。
2. 实验目的通过本次实验,我们将达到以下目的:- 理解线性表和链表的概念- 学会如何使用线性表和链表来解决常见的问题- 掌握线性表和链表的基本操作3. 实验内容3.1 线性表线性表是由 n 个数据元素 a1, a2, , an 组成的有序序列。
常见的线性表有数组和链表两种实现方式。
3.1.1 线性表的基本操作线性表的基本操作包括:- 初始化线性表- 判断线性表是否为空- 获取线性表的长度- 获取线性表中的元素- 在线性表的指定位置插入元素- 删除线性表中的指定元素- 清空线性表3.1.2 数组数组是一种连续的内存空间,可以存储相同类型的数据元素。
在数组中,每个元素的位置是通过下标来访问的,下标从 0 开始。
3.1.2.1 数组的插入操作数组的插入操作是将一个元素插入到数组的指定位置,同时需要将原位置的元素及其后续元素后移一位。
3.1.2.2 数组的删除操作数组的删除操作是将数组中指定位置的元素删除,同时需要将后续元素前移一位。
3.2 链表链表是一种离散的数据结构,它的元素包含两个部分:数据和指针。
每个节点都包含一个数据元素和一个指向下一个节点的指针。
3.2.1 链表的基本操作链表的基本操作包括:- 初始化链表- 判断链表是否为空- 获取链表的长度- 获取链表中的元素- 在链表的指定位置插入元素- 删除链表中的指定元素- 清空链表3.2.2 单链表单链表是最简单的链表形式,它的每个节点只包含一个指向下一个节点的指针。
3.2.2.1 单链表的插入操作单链表的插入操作是将一个元素插入到链表的指定位置,同时需要调整指针的指向。
3.2.2.2 单链表的删除操作单链表的删除操作是将链表中指定位置的节点删除,同时需要调整指针的指向。
运算机系第一部份数据结构课程实验概述一.实验目的《数据结构》是运算机专业的骨干课程和必修课程之一,其目的是让大伙儿学习、分析和研究数据对象特点,把握数据组织方式和运算机的表示方式,以便选择适合的数据逻辑结构和存储结构,设计相应的运算操作,把现实世界中的问题转化为运算机内部的表示与处置的方式,要求把握算法的时刻、空间复杂度分析大体技术,培育良好的程序设计风格,把握进行复杂程序设计的技术。
在运算机科学领域,尤其是在系统软件和应用软件的设计和应用中要用到各类数据结构,因此,把握数据结构对提高软件设计和程序编制水平有专门大的帮忙。
二.实验要求实验步骤设计步骤的标准不但能够培育学生科学的工作方式和作风,而且还能有效地减少错误,提高工作效率。
因此必需严格执行良好的实验步骤标准(包括上机操作标准)。
本课程实验的大体步骤是:问题分析充分地分析和明白得问题本身,明确问题要求做什么。
对问题的描述应躲开算法和所涉及的数据类型,而是对所需完成的任务作出明确的回答。
例如;输入、输出数据的类型、值的范围和形式等。
同时为调试程序预备好测试数据,包括合法的输入数据和非法形式输入的数据。
设计和编码设计即是对问题描述中涉及的操作对象概念相应的数据类型,概念主程序模块和各抽象数据类型;概念相应的存储结构并写出各进程和函数的伪码算法。
在那个进程中,要综合考虑系统功能,使得系统结构清楚、合理、简单和易于调试。
编码即把详细设计的结果进一步求精为程序设计语言程序,写出源程序。
对程序中的疑问应作出记号,以便上机时注意解决。
每一个明确的功能模块程序一样不超过60行,程序的每一行不得超过60个字符,不然要进一步划分。
上机前程序静态检查上机前程序静态检查可有效提高调试效率,减少上机调试程序时的无谓错误。
静态检查要紧有两种途径:用一组测试数据手工执行程序;通过阅读或给他人讲解自己的程序而深切全面地明白得程序逻辑。
把程序中的明显错误事前排除。
上机调试程序上机实验时要带上《C语言》教材、《数据结构》教材、《数据结构上机实验指导书》,调试最好分模块进行,自底向下,即先调试低层进程或函数。
数据结构与算法实验指导书中国石油大学(北京)计算机科学与技术系前言《数据结构》是计算机及相关专业的一门核心基础课程,也是很多高校考研专业课之一。
它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现,在此基础上介绍一些典型算法及时、空效率分析。
这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。
通过学习,要求学生能够掌握典型算法的设计思想及程序实现,能够根据实际问题选取合适的存储方案,设计出简洁、高效、实用的算法,为后续课程的学习及软件开发打下良好的基础。
学习这门课程,习题和实验是两个关键环节。
学生理解算法,上机实验是最佳的途径之一。
因此,实验环节的好坏是学生能否学好《数据结构》的关键。
为了更好地配合学生实验,特编写实验指导书。
一、实验目的更好的理解算法的思想、培养编程能力。
二、实验要求1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。
2、在指导教师的帮助下能够完成实验内容,得出正确的实验结果。
3、实验结束后总结实验内容、书写实验报告。
4、遵守实验室规章制度、不缺席、按时上、下机。
5、实验学时内必须做数据结构的有关内容,不允许上网聊天或玩游戏,如发现上述现象,取消本次上机资格,平时成绩扣10分。
6、实验报告有一次不合格,扣5分,两次以上不合格者,平时成绩以零分记。
三、实验环境VC++6.0或者VC2010四、说明1、本实验的所有算法中元素类型可以根据实际需要选择。
2、实验题目中带*者为较高要求,学生可自选;其余部分为基本内容,应尽量完成(至少完成70%,否则实验不合格)。
3、数据结构是很多高校的硕士研究生入学考试的专业课之一,希望有志于考研的学生能够在学习过程中注意各种算法的理解,以便为考研做一定的准备。
五、实验报告的书写要求1.明确实验的目的及要求;2.记录实验的输入数据和输出结果;3.说明实验中出现的问题和解决过程;4.写出实验的体会和实验过程中没能解决的问题;六、参考书目《数据结构》(C++语言描述)王红梅等清华大学出版社《DATA STRUCTURE WITH C++》William Ford,William Topp清华大学出版社(影印版)实验平台控制台程序1、启动Microsoft VC6.0集成开发环境如图所示:2、单击“文件”菜单,选择“新建”项。
3、选择“Win32 控制台应用程序”选项,如下图所示。
4、在D盘建立文件夹“Test1”,并键入工程名“TestList”。
5、单击“OK”按钮,进入下图界面。
6、选择“An empty project”选项后,点击“Finish”按钮,进入下图界面。
7、单击“文件”菜单,选择“新建”项,如下图所示。
8、在弹出的窗口选择“C/C++HeaderFile”,在名称框内输入“SeqList”,如下图所示。
9、单击“添加”按钮后,进入如下界面。
10、将“实验一”中顺序表定义键入文件SeqList.h中。
11、单击“文件”菜单,选择“新建”项,如下图所示。
12、在弹出的窗口选择“C++ SourceFile”,在名称框内输入“TestSeqList”,如下图所示。
13、将“实验一”中顺序表测试文件代码键入TestSeqList.cpp中。
14、调试并运行程序,完成实验内容1中的要求。
然后参照上述方法,建立链表类的LinkList.h文件和TestLinkList.cpp文件,然后完成实验内容2中的要求。
实验一线性表的操作实验类型:验证性实验要求:必修实验学时:2学时一、实验目的:参照给定的线性表顺序表类和链表类的程序样例,验证给出的线性表的常见算法。
二、实验要求:1、掌握线性表顺序表类和链表类的特点。
掌握线性表的常见算法。
2、提交实验报告,报告内容包括:目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容:1.设计一个静态数组存储结构的顺序表类,要求编程实现如下任务:建立一个线性表,首先依次输人数据元素1,2,3,…,10,然后删除数据元素6,最后依次显示当前线性表中的数据元素。
要求采用顺序表实现,假设该顺序表的数据元素个数在最坏情况下不会超过50个。
2.设计一个带头结点的单链表类,要求:1)生成一个整数线性表,实现将其分解成两个链表,其中一个全部为奇数,另一个全部为偶数(尽量利用已知的存储空间)。
2)设计一个测试主函数,实际运行验证所设计单链表类的正确性。
*3.设计一个不带头结点的单链表类,要求:1)不带头结点单链表类的成员函数包括取数据元素个数、插入元素、删除所有值为k的元素、取数据元素。
(提示:要考虑在第一个数据元素结点前插入和删除第一个数据元素结点时与在其他位置插入和删除其他位置结点时的不同情况。
)2)设计一个测试主函数,实际运行验证所设计循环单链表类的正确性。
*4.设计一个带头结点的循环双向链表类,要求:1)带头结点循环双向链表类的成员函数包括:取数据元素个数、插入、删除、取数据元素。
2)设计一个测试主函数,实际运行验证所设计循环双向链表类的正确性。
*5.设计一个单链表实现一元多项式求和问题。
要求:(1)设计存储结构表示一元多项式;(2)设计算法实现一元多项式相加。
四、程序样例1、顺序表类定义:将该类保存在文件SeqList.h中。
#if !defined SEQ_LIST#define SEQ_LIST#include <iostream>using namespace std;const int MaxSize=100; //100只是示例性的数据,可根据实际问题具体定义template <class T> //定义模板类SeqListclass SeqList{public:SeqList( ) {length=0;} //无参构造函数SeqList(T a[ ], int n); //有参构造函数~SeqList( ) { } //析构函数为空int Length( ) {return length;} //求线性表的长度T Get(int i); //按位查找,取线性表的第i个元素int Locate(T x ); //按值查找,求线性表中值为x的元素序号void Insert(int i, T x); //在线性表中第i个位置插入值为x的元素T Delete(int i); //删除线性表的第i个元素void PrintList(); //遍历线性表,按序号依次输出各元素private:T data[MaxSize]; //存放数据元素的数组int length; //线性表的长度};template <class T>SeqList<T>::SeqList(T a[ ], int n){if (n>MaxSize) throw "参数非法";for (int i=0; i<n; i++)data[i]=a[i];length=n;}template <class T>T SeqList<T>::Get(int i){if (i<1 && i>length) throw "查找位置非法";else return data[i-1];}template <class T>int SeqList<T>::Locate(T x){for (i=0; i<length; i++)if (data[i]==x) return i+1; //下标为i的元素等于x,返回其序号i+1return 0; //退出循环,说明查找失败}template <class T>void SeqList<T>::Insert(int i, T x){if (length>=MaxSize) throw "上溢";if (i<1 | | i>length+1) throw "位置";for (j=length; j>=i; j--)data[j]=data[j-1]; //注意第j个元素存在数组下标为j-1处data[i-1]=x;length++;}template <class T>T SeqList<T>::Delete(int i){if (length==0) throw "下溢";if (i<1 || i>length) throw "位置";T x=data[i-1];for (int j=i; j<length; j++)data[j-1]=data[j]; //注意此处j已经是元素所在的数组下标length--;return x;}template <class T>void SeqList<T> :: PrintList( ){for (int i = 0; i < length; i++)cout << data[i]<<" "; //依次输出线性表的元素值}#endif2、顺序表测试,新建TestSeqList.cpp文件。
#include "SeqList.h"void main( ){int r[]={1,2,3,4,5,6,7,8,9,10};SeqList<int> a(r,50);cout<<"执行删除操作前数据为:"<<endl;a.PrintList( );a.Delete(6);cout<<"执行删除操作后数据为:"<<endl;a.PrintList( );}3、链表类定义:将该类保存在文件LinkList.h中。
#if !defined SEQ_LIST#define SEQ_LIST#include <iostream>using namespace std;template <class T>struct Node{T data;Node<T> *next; //此处<T>也可以省略};template <class T>class LinkList{LinkList( ){first=new Node<T>; first->next=NULL;} //建立只有头结点的空链表LinkList(T a[ ], int n); //建立有n个元素的单链表~LinkList( ); //析构函数int Length( ); //求单链表的长度T Get(int i); //取单链表中第i个结点的元素值int Locate(T x); //求单链表中值为x的元素序号void Insert(int i, T x); //在单链表中第i个位置插入元素值为x的结点T Delete(int i); //在单链表中删除第i个结点void PrintList( ); //遍历单链表,按序号依次输出各元素private:Node<T> *first; //单链表的头指针};template <class T>LinkList<T>:: ~LinkList( ){Node<T> *p=first; //工作指针p初始化while (p) //释放单链表的每一个结点的存储空间{Node<T> *q=p; //暂存被释放结点p=p->next; //工作指针p指向被释放结点的下一个结点,使单链表不断开delete q;}}template <class T>T LinkList<T>::Get(int i){p=first->next; j=1; //或p=first; j=0;while (p && j<i){p=p->next; //工作指针p后移j++;}if (!p) throw "位置";else return p->data;}template <class T>void LinkList<T>::Insert(int i, T x){p=first ; j=0; //工作指针p初始化while (p && j<i-1){p=p->next; //工作指针p后移j++;}if (!p) throw "位置";else {s=new Node<T>; s->data=x; //向内存申请一个结点s,其数据域为xs->next=p->next; //将结点s插入到结点p之后p->next=s;}template <class T>T LinkList<T>::Delete(int i){p=first ; j=0; //工作指针p初始化while (p && j<i-1) //查找第i-1个结点{p=p->next;j++;}if (!p | | !p->next) throw "位置"; //结点p不存在或结点p的后继结点不存在else {q=p->next; x=q->data; //暂存被删结点p->next=q->next; //摘链delete q;return x;}}template <class T>LinkList<T>:: LinkList(T a[ ], int n){first=new Node<T>;first->next=NULL; //初始化一个空链表for (int i=0; i<n; i++){Node<T> *s=new Node<T>;s->data=a[i]; //为每个数组元素建立一个结点s->next=first->next; //插入到头结点之后first->next=s;}}template <class T>void LinkList<T> :: PrintList( ){}#endif4、链表测试,新建TestLinkList.cpp文件。