下载文档原格式
《数据结构》实验指导书实验一顺序表实验目的：熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作。
实验要求：了解并熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作的实现和应用。
实验内容：1、编写程序实现在线性表中找出最大的和最小的数据元素，并符合下列要求：（1）设数据元素为整数，实现线性表的顺序存储表示。
（2）从键盘输入10个数据元素，利用顺序表的基本操作建立该表。
（3）利用顺序表的基本操作，找出表中最大的和最小的数据元素（用于比较的字段为整数）。
2、编写一个程序实现在学生成绩中找出最高分和最低分，并符合下列要求：（1）数据元素为学生成绩（含姓名、成绩等字段）。
（2）要求尽可能少地修改第一题的程序来得到此题的新程序，即要符合第一题的所有要求。
（这里用于比较的字段为分数）实验二链表实验目的：熟悉链表的逻辑特性、存储表示方法的特点和链式表的基本操作。
实验要求：了解并熟悉链式表的逻辑特性、存储表示方法和链式表的基本操作的实现和应用。
实验内容：1、编写一个程序建立存放学生成绩的有序链表并实现相关操作，要求如下：（1）设学生成绩表中的数据元素由学生姓名和学生成绩字段组成，实现这样的线性表的链式存储表示。
（2）键盘输入10个（或若干个，特殊数据来标记输入数据的结束）数据元素，利用链表的基本操作建立学生成绩单链表，要求该表为有序表并带有头结点。
（用于比较的字段为分数）。
（3）输入关键字值x，打印出表中所有关键字值<=x的结点。
（用于比较的关键字字段为分数）。
（4）输入关键字值x，删除表中所有关键字值<=x的结点。
（用于比较的关键字字段为分数）。
（5）输入关键字值x，并插入到表中，使所在的链表仍为有序表。
（用于比较的字段为分数）。
实验三栈的应用实验目的：熟悉栈的逻辑特性、存储表示方法和栈的基本操作。
实验要求：了解并熟悉栈的逻辑特性、顺序和链式存储表示方法和栈的基本操作的实现和应用。
实验内容：(1)判断一个表达式中的括号（仅有一种括号，小、中或大括号）是否配对。
《数据结构与算法》实验指导书大连民族学院信息与通信工程学院2013 年10 月10 日基本要求1.学生必须按时到实验室做实验，不得迟到早退，未经老师批准不得中途离开。
凡迟到者，应给予批评并作适当扣分。
实验课迟到20分钟以上及无故缺席者视为旷课，旷课者不予补做实验，本次实验以零分计。
学生因病或特殊情况不能按时到实验室做实验时，应办理正常请假手续。
请病假必须有医生签字的病假条，请事假必须有班主任签字的事假条。
不符合请假手续的，以旷课论处。
请假的学生由指导教师安排补做实验。
对于未做实验数达三分之一以上（含三分之一）的学生，实验课程按0分计。
2.学生在每次实验课之前，应仔细阅读实验教材，查阅相关的资料，写出预习报告。
预习报告的具体内容包括：实验内容、实验目的、实验原理图、实验步骤、实验数据记录表格等。
实验课前由任课教师检查预习报告，未写预习报告者不予做实验。
3.做实验前，了解设备的原理和正确使用方法。
在没有弄懂仪器设备的使用方法前，不得贸然使用，否则因使用不当造成仪器设备损坏的，根据大连民族学院《仪器设备损坏丢失处理暂行办法》规定进行处理。
实验室内设备在实验过程中不准任意搬动和调换，非本次实验所用仪器设备，未经指导教师允许不得动用。
4.要求每位学生在实验过程中，要具有严谨的学习态度、认真、踏实、一丝不苟的科学作风。
实验过程中学生按照预习的内容进行实验，且重视实验的调试过程，学会如何根据实验现象判断问题所在。
坚持每次实验都要亲自动手，不可“坐车”，每个实验每个学生都要独立完成，不允许抄袭，无特殊原因，中途不得退出实验，否则本次实验无效。
5.实验中若接线、改接、拆线都必须在切断电源的情况下进行，线路连接完毕再送电。
实验中，特别是设备刚投入运行时，要随时注意仪器设备的运行情况，如发现有过热、异味、冒烟、火花等，应立即断电，并请指导老师检查、处理。
6.实验过程中，如出现事故，就马上拉开电源开关，然后找指导教师和实验技术人员，如实反映事故情况，并分析原因和处理事故。
数据结构实验指导书一、实验目的数据结构是计算机科学中的重要基础课程，通过实验，旨在帮助学生更好地理解和掌握数据结构的基本概念、原理和算法，提高学生的编程能力和问题解决能力。
具体而言，实验的目的包括：1、加深对常见数据结构（如数组、链表、栈、队列、树、图等）的理解，掌握其特点和操作方法。
2、培养学生运用数据结构解决实际问题的能力，提高算法设计和程序实现的能力。
3、增强学生的逻辑思维能力和调试程序的能力，培养学生的创新意识和团队合作精神。
二、实验环境1、操作系统：Windows 或 Linux 操作系统。
2、编程语言：C、C+＋、Java 等编程语言中的一种。
3、开发工具：如 Visual Studio、Eclipse、Code:：Blocks 等集成开发环境（IDE）。
三、实验要求1、实验前，学生应认真预习实验内容，熟悉相关的数据结构和算法，编写好实验程序的代码框架。
2、实验过程中，学生应独立思考，认真调试程序，及时记录实验过程中出现的问题及解决方法。
3、实验完成后，学生应撰写实验报告，包括实验目的、实验内容、实验步骤、实验结果、问题分析与解决等。
四、实验内容（一）线性表1、顺序表的实现与操作实现顺序表的创建、插入、删除、查找等基本操作。
分析顺序表在不同操作下的时间复杂度。
2、链表的实现与操作实现单链表、双向链表的创建、插入、删除、查找等基本操作。
比较单链表和双向链表在操作上的优缺点。
（二）栈和队列1、栈的实现与应用实现顺序栈和链式栈。
利用栈解决表达式求值、括号匹配等问题。
2、队列的实现与应用实现顺序队列和链式队列。
利用队列解决排队问题、广度优先搜索等问题。
（三）树1、二叉树的实现与遍历实现二叉树的创建、插入、删除操作。
实现二叉树的前序、中序、后序遍历算法，并分析其时间复杂度。
2、二叉搜索树的实现与操作实现二叉搜索树的创建、插入、删除、查找操作。
分析二叉搜索树的性能。
（四）图1、图的存储结构实现邻接矩阵和邻接表两种图的存储结构。
数据结构实验指导书实验1：顺序表基本操作一、实验目的1.学会定义线性表的顺序存储类型，实现C程序的基本结构，对线性表的一些基本操作和具体的函数定义。
2.掌握顺序表的基本操作，实现顺序表的插入、删除、查找以及求并集等运算。
3.掌握对多函数程序的输入、编辑、调试和运行过程。
二、实验要求1．预习C语言中结构体的定义与基本操作方法。
2．对顺序表的每个基本操作用单独的函数实现。
3．编写完整程序完成下面的实验内容并上机运行。
4．整理并上交实验报告。
三、实验内容：1．编写程序实现顺序表的下列基本操作：(1)初始化顺序表La。
(2)将La置为空表。
(3)销毁La。
(4)在La中插入一个新的元素。
(5)删除La中的某一元素。
(6)在La中查找某元素，若找到，则返回它在La中第一次出现的位置，否则返回0。
(7)打印输出La中的元素值。
2．编写程序完成下面的操作：(1)构造两个顺序线性表La和Lb，其元素都按值非递减顺序排列。
(2)实现归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减顺序排列。
(3)假设两个顺序线性表La和Lb分别表示两个集合A和B，利用union_Sq操作实现A=A∪B。
四、思考与提高假设两个顺序线性表La和Lb分别表示两个集合A和B，如何实现A=A ∩B ？一、实验目的1.学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。
2.掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。
二、实验要求1．预习C语言中结构体的定义与基本操作方法。
2．对单链表的每个基本操作用单独的函数实现。
3．编写完整程序完成下面的实验内容并上机运行。
4．整理并上交实验报告。
三、实验内容1．编写程序完成单链表的下列基本操作：(1)初始化单链表La。
(2)在La中插入一个新结点。
(3)删除La中的某一个结点。
(4)在La中查找某结点并返回其位置。
数据结构实验指导书适用所有开设数据结构实验的专业雷文赵攀编写概述一、课程目的《数据结构》是一门实践性很强的软件基础课程，为了学好这门课，每个学生必须完成一定数量的上机作业。
通过本课程的上机作业，要求在数据结构的选择和应用、算法的设计及实现等方面加深对课程基础内容的理解，同时，实验题中的问题比平时的练习题要复杂，也更接近实际，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
本课程实验的目的是旨在使学生进一步巩固课堂上所学的理论知识；深化理解和灵活掌握教学内容；培养学生算法设计的能力和解决实际问题的程序设计的能力。
二、实验名称与学时分配三、实验要求⒈问题分析充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。
⒉数据结构设计针对要求解决的问题，考虑各种可能的数据结构，并且力求从中出最佳方案(必须连同算法一起考虑)，确定主要的数据结构及全程变量。
对引入的每种数据结构和全程变量要详细说明其功能、初值和操作特点。
⒊算法设计算法设计分概要设计和详细设计，概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题.详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，采用类C语言描述。
⒋测试用例设计准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。
⒌上机调试对程序进行编译，纠正程序中可能出现的语法错误，测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。
三、实验考核每次实验结束后，均应上交实验报告。
数据结构课程实验成绩单独考核，占1个学分。
实验报告应包括如下内容：1、问题描述：简述题目要解决的问题是什么。
数据结构实验指导书数据结构实验指导书目录数据结构实验指导书 (1)目录 (1)实验指导书概述 (2)上机实验题目 (3)实验一 C语言相关知识复习 (3)一、实验目的 (3)二、实验内容 (3)实验二单链表的插入、删除 (3)一、实验目的 (3)二、实验内容 (3)三、实现提示 (4)实验三栈及其应用 (5)一、实验目的 (5)二、实验内容 (5)实验四二叉树的递归算法 (6)一、实验目的 (6)二、实验内容 (6)实验五图的遍历 (7)一、实验目的 (7)二、实验内容 (7)实验六有序表的查找 (7)一、实验目的 (7)二、实验内容 (7)实验七哈希表 (7)一、实验目的 (7)二、实验内容 (7)实验八内部排序算法的应用 (8)一、实验目的 (8)二、实验内容 (8)实验指导书概述“数据结构”是计算机专业一门重要的专业技术基础课程，是一门关键性核心课程。
本课程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了多种常用的查找和排序技术，并对其进行了性能分析和比较，内容非常丰富。
本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。
由于以下原因，使得掌握这门课程具有较大难度：∙内容多，时间短，给学习带来困难；∙贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点；∙隐含在各部分的技术和方法丰富，也是学习的重点和难点；∙先修课程中所介绍的专业性知识不多，加大了学习难度。
由于数据结构课程的技术性与实践性，《数据结构课程实验》的设置十分必要。
为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。
上机实践是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。
通过上机实践，使学生在可能短的时间内对数据结构知识的实践和应用有一个比较全面和系统的认识，达到理论与实践相结合的目的。
《数据结构》实验指导书第一部分前言一、实验的目的《数据结构》是计算机学科一门重要的专业基础课程,也是计算机学科的一门核心课程。
本课程的另一重要教学目的是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，要做到这一点，上机实习是必须的。
数据结构实验是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。
通常，实验课题中的问题比平时的习题复杂得多，也更接近实际。
实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，训练学生实际动手进行程序设计和调试程序的能力，加深对数据结构相关概念和算法的理解。
通过完成本实验课程的实验，学生应学会并掌握本课程的基本和重点知识，深刻理解逻辑结构、物理结构和算法设计之间的关系，初步学会算法分析的方法，并能在一定范围内运用所掌握的分析方法进行算法分析，培养软件工作所需要的动手能力和作为一个软件工作者所应具备的科学工作方法和作风。
二、实验前的准备工作1．每个学生需配备一台计算机，操作系统需Windows2000/XP以上版本，软件需Visual C++6.0以上版本。
2．实验前要求学生按实验要求编写好相关实验程序，准备上机调试运行。
三、实验的步骤（一）建立一个文件夹，如“数据结构”，用来存放自己的所有实验程序，在该文件夹中建立子目录用来存放每个项目（一个子目录一个项目），如“顺序表”，项目中需要的所有文件都存在该文件夹中。
（二）新建一个项目文件1．双击Visual C++ 6.0快捷图标，进入Visual C++ 6.0集成开发环境；或者点击“开始”→“程序”→“Microsoft Visual Studio 6.0”→“Microsoft Visual C++ 6.0”进入Visual C++ 6.0集成开发环境。
2．单击“File”菜单，选择“New”命令3．创建一个项目文件并保存在项目所在文件夹中；3. 创建源程序文件并保存在项目所在文件夹中；4．输入源程序；5．单击“保存”按钮保存源程序。
《数据结构》实验指导书实验一线性表【实验目的】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、本次实验的结论与体会。
数据结构实验指导书院别专业班级姓名计算机学院编实验一线性表的顺序存储实验一、实验目的及要求1、掌握在TC环境下调试顺序表的基本方法2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现。
二、实验学时2学时三、实验任务1、生成一个顺序表并动态地删除任意元素和在任意位置插入元素。
2、将两个有序表合并成一个有序表。
四、实验重点、难点1、在顺序表中移动元素。
2、在顺序表中找到正确的插入位置。
五、操作要点(一)顺序表基本操作的实现[问题描述] 当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。
若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。
[基本要求] 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。
[实现提示] 要实现基本操作，可用实现的基本操作，也可设计简单的算法实现。
[程序实现]#include <stdio.h>#include <conio.h>typedef int DataType ;# define maxnum 20typedef struct{int data[maxnum];int length;}SeqList;/*插入函数*/int insert(SeqList *L , int i , DataType x)/* 将新结点x插入到顺序表L第i个位置 */{ int j ;if( i<0 || i>(*L).length +1){ printf(" \n i 值不合法 ! ");return 0;}if((* L).length >=maxnum-1){ printf(" \n 表满不能插入!");return 0;}for(j=(*L).length;j>=i;j--) (*L).data[j+1]=(*L).data[j];(*L).data[i] = x;(*L).length++;return 1;}/*删除函数*/int delete( SeqList *L ,int i)/*从顺序L中删除第i个结点*/{ int j ;if( i<0|| i>(*L).length ){ printf(" \n 删除位置错误 ! ") ;return 0;}for(j=i+1;j<=(*L).length;j++)(*L).data[j-1] =(*L).data[j];(*L).length--;return 1;}/*生成顺序表*/void creatlist(SeqList * L){ int n , i , j ;printf("请输入顺序表 L 的数据个数：\n") ;scanf("%d" , &n) ;for(i=0 ; i<n ; i++){ printf("data[%d] =" , i) ;scanf("%d",&((*L).data[i]));}(*L).length=n-1;printf("\n") ;}/*creatlist *//*输出顺序表 L*/printout(SeqList * L){ int i ;for (i=0 ; i<=(* L).length ; i++){ printf(" data[%d]=", i) ;printf("%d", (*L).data[i]);}/*printout */printf("\n");}main(){ SeqList *L ;char cmd ;int i , t , x;clrscr() ;creatlist(L);do{printf("\ni , I ----- 插入\n") ;printf("d , D ----- 删除\n") ;printf("q , Q ----- 退出\n") ;do{cmd=getchar() ;}while((cmd!='i')&&(cmd!='I')&&(cmd!='d')&&(cmd!='D')&&(cmd!='q')&&(cmd!='Q')); switch(cmd){ case 'i':case 'I':printf("\nPlease input the DATA: ");scanf("%d",&x) ;printf("\nWhere? ");scanf("%d",&i) ;insert(L,i,x) ;printout(L);break ;case 'd':case 'D' :printf("\nWhere to Delete? ");scanf("%d",&i);delete(L,i);printout(L);break ;}}while((cmd!='q')&&(cmd!='Q'));}（二）有序顺序表的合并[问题描述] 已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc[基本要求] lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表[程序实现]# include <stdio.h># define maxnum 20typedef int DataType ;typedef struct{ DataType data[maxnum] ;int length ;}SeqList ;int MergeQL(SeqList la , SeqList lb , SeqList *lc){ int i , j , k ;if (la.length+1 + lb.length+1>maxnum){ printf("\narray overflow!") ;return 0;}i=j=k=0;while(i<=la.length && j<=lb.length){ if (la.data[i]<=lb.data[j])lc->data[k++]=la.data[i++] ;elselc->data[k++]=lb.data[j++];}/* 处理剩余部分 */while (i<=la.length) lc->data[k++]=la.data[i++];while (j<=lb.length) lc->data[k++]=lb.data[j++];lc->length=k-1;return 1;}main(){ SeqList la={{3,4,7,12,15},4} ;SeqList lb={{2,5,7,15,18,19},5} ;SeqList lc ;int i ;if (MergeQL(la,lb,&lc)){ printf("\n") ;for(i=0;i<=lc.length ; i++)printf("%4d",lc.data[i]);}}六、注意事项1、删除元素或插入元素表的长度要变化。
《数据结构》实验指导书实验类别：课内实验实验课程名称：数据结构实验室名称：软件工程实验室实验课程编号：02060002总学时：64 学分： 4适用专业：计算机科学与技术、网络工程、软件工程先修课程：计算机导论及操作、离散数学实验在教学培养计划中地位、作用：数据结构是计算机软件相关专业的主干课程，也是计算机软硬件专业的重要基础课程。
数据结构课程实验的目的是通过实验掌握数据结构的基本理论和算法，并运用它们来解决实际问题。
数据结构课程实验是提高学生动手能力的重要的实践教学环节，对于培养学生的基本素质以及掌握程序设计的基本技能并养成良好的程序设计习惯方面发挥重要的作用。
实验一线性表的应用（2学时）1、实验目的通过本实验，掌握线性表链式存储结构的基本原理和基本运算以及在实际问题中的应用。
2、实验内容建立某班学生的通讯录，要求用链表存储。
具体功能包括：（1）可以实现插入一个同学的通讯录记录；（2）能够删除某位同学的通讯录；（3）对通讯录打印输出。
3、实验要求（1）定义通讯录内容的结构体；（2）建立存储通讯录的链表结构并初始化；（3）建立主函数：1）建立录入函数（返回主界面）2）建立插入函数（返回主界面）3）建立删除函数（返回主界面）4）建立输出和打印函数（返回主界面）I）通过循环对所有成员记录输出II）输出指定姓名的某个同学的通讯录记录5）退出实验二树的应用（2学时）1、实验目的通过本实验掌握二叉的建立和递归遍历、非递归遍历算法，了解二叉树在实际中的应用并熟练运用二叉树解决实际问题。
2、实验内容根据前序遍历的顺序建立一棵二叉树，并根据遍历规则遍历二叉树。
打印输出。
3、实验要求（1）根据前序遍历的顺序创建一棵二叉树；（）对二叉树进行前序、中序、后序遍历。
实验三图的应用（2学时）1、实验目的通过本实验掌握图的存储结构与基本运算以及图的深度优先遍历和图的广度优先遍历算法在实际问题中的应用。
2、实验内容按照邻接表对图进行创建，并运用图的深度优先遍历和图的广度优先遍历算法对所创建的无向图进行遍历。
数据结构实验指导书实验的目的、内容和要求一、实验目的与要求1. 通过上机实验加深对课程内容的理解，提高软件设计、编写及程序调试的能力。
2. 上机前要做好准备工作，包括程序框图、数据结构以及算法。
3. 按时实验。
4. 服从实验室老师的安排。
5. 独立实验，有问题可以讨论，但不得翻版。
6. 遵守实验室的各项纪律。
7. 要求所编的程序能正确运行，并提交实验报告。
二、实验内容1. 线性表基本操作：熟练掌握线性表的基本操作，及在两种存储结构上的实现。
要求顺序表的数据域是整型数值，完成顺序表的初始化、插入、删除等操作，插入时不允许重复的值插入表中。
要求单链表的数据域是字符串，完成单链表的初始化、插入、删除、逆向等操作。
2. 栈操作：采用顺序存储结构，完成建栈、数据元素入栈与出栈、判断栈空、判断栈满等操作。
3. 二叉树操作：采用二叉链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作等。
4. 图的遍历操作：可采用邻接矩阵或邻接表作为存储结构，完成有向图和无向图的DFS 和BFS操作。
5. 数据查找：实现顺序查找、折半查找及二叉排序树上的查找算法，比较它们的查找速度。
实验时所输入的数据可按有序和随机产生去组织。
6. 排序：实现直接插入、冒泡、直接选择、快速、堆、归并等排序算法，比较各种排序算法的速度。
三、实验安排第3，5，7，9，11，13，14，15周周二，实验楼0711四、实验报告要求（1）报告内容包括：实验名称实验目的实验内容问题描述问题分析函数说明程序流程图重要算法解释使用说明调试报告心得体会（2）实验报告的基本要求为：1. 需求分析：陈述程序设计的任务，强调程序要做什么，明确规定：①输入的形式和输入值的范围；②输出的形式；③程序所能达到的功能；④测试数据：包括正确的输入输出结果和错误的输入及其输出结果。
2. 概要设计：说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。
3. 详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。
4. 调试分析：①调试过程中所遇到的问题及解决方法；②算法的时空分析；③经验与体会。
5. 用户使用说明：说明如何使用你的程序，详细列出每一步操作步骤。
6. 测试结果：列出对于给定的输入所产生的输出结果。
若可能，测试随输入规模的增长所用算法的实际运行时间的变化。
（3）必须打印。
实验1 线性表基本操作（4学时）实验目的1．掌握使用C++上机调试线性表的基本方法。
2．熟练掌握线性表的基本操作，及在两种存储结构上的实现。
3．熟悉顺序表的基本操作，完成顺序表的初始化、插入、删除等操作，插入时不允许重复的值插入表中。
4．熟悉对单链表的一些基本操作，完成单链表的初始化、插入、删除等操作。
实验内容1．实现顺序表的定义和操作。
该程序包括顺序表结构类型以及对顺序表操作的具体的函数定义。
/* 定义顺序表的最大长度为MAXSIZE */#define MAXSIZE 50/* 定义DataType为int类型*/typedef int DataType;/* 顺序表的类型*/typedef struct list{DataType vec[MAXSIZE];int len; //顺序表的长度} SeqList;将此结构定义放在一个头文件sqlist.h中，并在头文件中给出顺序表的函数及常量的定义。
/* 初始化顺序表*/SeqList* Create();/* 清除顺序表*/void Destroy(SeqList *L);/* 顺序表元素信息打印输出*/void Print(SeqList *L);/* 判断顺序表是否为空*/bool IsEmpty(SeqList *L);/* 判断顺序表是否为满*/bool IsFull(SeqList *L);/* 向顺序表中添加数据*/void Append(SeqList *L, DataType data);/*获取顺序表的长度*/int GetLength(SeqList *L);/*删除顺序表中指定位置的元素*/bool Delete(SeqList *L, int pos);/*在顺序表的指定位置中的添加元素*/bool Insert(SeqList *L, int pos, DataType data);//*VS C++ 函数定义void Create(const int &iMax);void Destroy();void Print();bool IsEmpty();bool IsFull();void Append(const T &data);int GetLength();int GetMax();bool Delete(const int &pos);bool Insert(const int &pos,const T &data);2．实现单链表的定义和操作。
该程序包括单链表结构类型以及对单链表操作的具体的函数定义。
程序中的单链表（带头结点）结点为结构类型，结点值为整型。
/* 定义DataType为int类型*/typedef int DataType;/* 单链表的结点类型*/typedef struct LNode{DataType data;struct LNode *next;} LinkedList;/* 初始化单链表*/LinkedList * LinkedListInit();/* 清空单链表*/void LinkedListClear(LinkedList *L);/* 检查单链表是否为空*/int LinkedListEmpty(LinkedList *L);/* 遍历单链表*/void LinkedListTraverse(LinkedList *L);/* 求单链表的长度*/int LinkedListLength(LinkedList *L);/* 从单链表表中查找元素*/LinkedList LinkedListGet(LinkedList *L，int i);/* 从单链表表中查找与给定元素值相同的元素在链表中的位置*/int LinkedListLocate(LinkedList *L， DataType x);/* 向单链表中插入元素*/void LinkedListInsert(LinkedList *L，int i，DataType x);/* 从单链表中删除元素*/void LinkedListDel(LinkedList *L，DataType x);/* 用尾插法建立单链表*/LinkedList LinkedListCreat( );* 3．约瑟夫环问题：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1顺序报数，如此下去，直到所有人全部出列为止。
例如N=10，K=3，则正确的出列顺序应为3，6，9，2，7，1，8，5，10，4。
利用单向循环链表存储结构模拟约瑟夫环过程，按照出列的顺序输出各个人的编号。
1．输入数据：输入m的初值，n ，输入每个人的密码，建立单循环链表。
2．写出算法，输出正确的序列。
关键代码typedef struct{ char data;struct lnode *next;}lnode，*linklist;linklist creatlist(){ linklist head，p;char ch;head=(linklist)malloc(sizeof(lnode));head->next=NULL;scanf("%c"，&ch);while(ch!='\n'){ p=(linklist)malloc(sizeof(lnode));p->data=ch;p->next=head->next;head->next=p;scanf("%c"，&ch); }return head;}linklist findlist(linklist head，int k){ linklist p=head;int m=0;while(p!=NULL&&m<k){ p=p->next;m++; }return p;}int length(linklist head){ int j=0;linklist p=head->next;while(p!=NULL){ p=p->next;j++; }return(j);}insertlist(linklist head，int i，char x){ linklist p，q;if(i<0||i>length(head)) printf("\nErr!");else{ p=findlist(head，i-1);q=(linklist)malloc(sizeof(lnode));q->data=x;q->next=p->next;p->next=q; }}deletelist(linklist head，int i){ linklist p，q;if(i<1||i>length(head)) printf("\nErr!"); p=findlist(head，i-1);q=p->next;p->next=q->next;free(q);}printlist(linklist head){ linklist p=head->next;printf("\nhead-->");while(p!=NULL){ printf("%c"，p->data);p=p->next; }printf("-->end");}实验2 堆栈与队列（2学时）实验目的1．定义顺序栈和链栈的结点类型。
2．掌握栈的插入和删除结点在操作上的特点。
3．熟悉对栈的一些基本操作和具体的函数定义。
4．定义顺序队列和链队列的结点类型。
实验内容堆栈的操作1．该程序的功能是实现顺序栈的定义和操作。
该程序包括定义的栈结构类型以及对每一种栈操作的具体的函数定义和主函数。
/* 定义DataType为int类型*/typedef int DataType;/* 栈的结点类型*/#define MAXSIZE 1024typedef struct{DataType data[MAXSIZE];int top;}SeqStack;/* 初始化顺序栈*/SeqStack SeqStackInit()/* 检查顺序栈是否为空*/int SeqStackEmpty(SeqStack S)/* 把S置为空栈*/void ClearStack(SeqStack *S)/* 把元素x压入栈，使其成为新的栈顶元素*/void SeqStackPush(SeqStack *S，DataType x)/* 把栈顶元素弹出*/DataType SeqStackPop(SeqStack *S)/* 取栈顶元素*/DataType SeqStackGetTop(SeqStack S)/*输出顺序栈中的元素*/void SeqStackPrint(SeqStack S)2．试利用堆栈将队列中的元素逆置。
