搜索
华北电力大学科技学院实验报告实验名称数据结构试验课程名称数据结构专业班级：学生姓名：学号：成绩：指导老师：实验日期：2010年3月-5月（实验报告如打印，纸张用A4，左装订；页边距：上下2.5cm，左2.5cm，右2.0cm；字体：字体小四号，1.25倍行距。）验证性、综合性实验报告应包含的主要内容：一、实验目的及要求1．实验目的2．实验要求二、所用仪器、设备1．所需的硬件设备2．所需的软件列表三、实验原理1．实验所用到的原理或理论2．结合本实验阐述如何将理论与实验相结合四、实验步骤（附程序流程图）五、程序源代码六、讨论与结论（对实验现象、实验故障及处理方法、实验中存在的问题等进行分析和讨论，对实验的进一步想法或改进意见）七、所附实验输出的结果或数据（按照以上格式书写报告）华北电力大学科技学院实验报告第1页实验一顺序表及其应用一、实验目的及要求1、实验目的(1)熟悉VC++上机环境，进一步掌握C语言的结构特点。(2)掌握线性表的顺序存储结构的定义及C语言实现。(3)掌握线性表在顺序存储结构即顺序表中的各种基本操作的实现。(4)掌握栈和队列的顺序表示和实现。2、实验要求(1)用顺序存储结构实现栈和循环队列。(2)编写完整程序完成下面的实验内容并上机运行。(3)整理并上交实验报告。二、实验内容1.约瑟夫环的实现：设有n个人围坐在圆桌周围，现从某个位置i上的人开始报数，数到m的人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。例如：当n=8,m=4,i=1时，得到的新序列为：4，8，5，2，1，3，7，6编写程序选择循环队列（顺序存储方式）模拟整个过程，并依次输出出列的各人的编号。2、表达式的计算：1）问提描述：输入形如：某单字母变量=中缀表达式。其中中缀表达式可以包括整数、单字母变量、二元操作符+、-、*、/、以及括号（）。根据输入，所有单字母变量都能够求得数值解，设计算法要求：①将等式右边的中缀表达式转换成后缀表达式，并求值。然后以单字母变量后缀表达式值的形式，存放在内存，并打印输出。华北电力大学科技学院实验报告第2页②在①的基础上，对用户提出的中缀表达式求值，若变量在内存表格中，则算法返回表达式的值（若非整数，则四舍五入取整），若变量不在表中，则返回一个错误信息。2)例如：输入A=8*DB=3C=(A-10)*(B+D/2)D=6①求得的后缀表达式及值A8D*48B33CA10-BD2/+*228D66②用户输入算法返回D6B3B+C/A8C+D-A186A+D+Eerror实现提示：数据结构采用顺序存储实现线性表，在中缀表达式转化为后缀表达式时，利用顺序存储实现栈。华北电力大学科技学院实验报告第3页实验二链表及其应用一、实验目的及要求1、实验目的(1)熟悉VC++上机环境，进一步掌握C语言的结构特点。(2)掌握线性表的链式存储结构即单链表的定义及C语言实现。(3)掌握线性表在链式存储结构即单链表中的各种基本操作。(4)掌握栈和队列的链式存储结构的表示和实现。2、实验要求(1)用链式存储结构实现单链表（和单向循环链表）的建立、查找和删除等运算。(2)编写完整程序完成下面的实验内容并上机运行。(3)整理并上交实验报告。二、实验内容1.约瑟夫环的问题：设有n个人围坐在圆桌周围，现从某个位置i上的人开始报数，数到m的人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。例如：当n=8,m=4,i=1时，得到的新序列为：4，8，5，2，1，3，7，6用单向循环链表存储结构模拟此过程。实现提示：typedefstructNode{intdata;structNode*next;}*nodetype;//定义指向链节点类型的指针1）先建立单向循环链表。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址：p=(nodetype)malloc(sizeof(structNode));该语句的功能是申请分配一个类型为结构体类型为Node的结点的地址空间，并将首地址存入指针变量p中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。华北电力大学科技学院实验报告第4页2）注意在删除第m个节点时，需要一个辅助指针指向删除节点的前驱节点，删除节点只需要修改指针即可。2.若已知非空线性链表第一个结点的指针为list（即非空不带头节点的单链表头指针为list），请写一个算法并实现,将该链表中数据域值最小的那个结点移到链表的最前端。实现提示：此算法需要四个辅助指针，扫描链表节点指针p以及其前驱节点指针r,数据域小的节点指针q以及其前驱节点指针s.华北电力大学科技学院实验报告第5页实验三二叉树一、实验目的及要求1、实验目的(1)通过实验，掌握二叉树的建立与存储(2)通过实验，掌握二叉树的遍历方法2、实验要求(1)二叉树需要用二叉链表作为节点类型描述。(2)二叉树的遍历递归算法能够转换为非递归算法。(3)编写完整程序完成下面的实验内容并上机运行。(4)整理并上交实验报告。二、实验内容1、问题描述利用先序遍历建立一棵二叉树，并分别用前序、中序、后序遍历该二叉树2、节点形式LchilddataRchild3、说明(1)输入数据：1，2，3，0，0，4，0，0，5，0，0其中“0”表示空子树。(2)输出数据：先序：1，2，3，4，5中序：3，2，4，1，5后序：3，4，2，5，1三、实验步骤1.建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。2.建立二叉树,并通过调用函数,输出先序遍历、中序遍历与后序遍历的结果。实现提示：二叉链表的类型定义如下：typedefstructbtnode{intdata;structbtnode*Lchild,*Rchild;}*bitreptr华北电力大学科技学院实验报告第6页实验四图一、实验目的及要求1、实验目的(1)掌握图的基本存储方法。(2)掌握有关图的操作算法并用c语言实现。(3)熟练掌握图的两种搜索路径的遍历方法。2、实验要求(1)图的存储结构采用邻接表结构。(2)分别用深度优先和广度优先搜索对图进行遍历。(3)编写完整程序完成下面的实验内容并上机运行。(4)整理并上交实验报告。二、实验内容1、问题描述对给定的下图采用邻接表结构存储，并分别用深度优先和广度优先搜索对图进行遍历。123546782、说明(1)图的邻接表存储：V112^3V22145^V33167^V442^8V552^8V773^8V663^8V884567^华北电力大学科技学院实验报告第7页(2)输出数据：深度优先序列：1→2→4→8→5→3→6→7广度优先序列：1→2→3→4→5→6→7→8三、实验步骤1.建立自己的头文件TU.H，内容包括邻接表的结构描述、邻接表的建立、图的深度优先与广度优先遍历算法。2.建立图的邻接表存储结构,并通过调用函数,输出深度优先、广度优先遍历的结果。实现提示：邻接表形式弧节点adjvexnext顶点节点：vertexlink邻接表的类型定义：#definemax_vertex_num//图的顶点数typedefstructEdgeNode//弧节点的结构{intadjvex;//该弧所指向的顶点位置StructEdgeNode*next;//指向下一条弧的指针}；typedefstructVnode//顶点节点结构{intvertex;//顶点信息StructEdgeNode*link;//指向第一条依附该顶点的弧}AdjList[max_vertex_num];华北电力大学科技学院实验报告第8页实验五查找与排序一、实验目的及要求1、实验目的(1)掌握查找的不同方法，并能用c语言实现查找算法。(2)掌握常用的排序方法，并掌握用c语言实现排序算法的方法。(3)深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。(4)了解各种方法的排序过程及其时间复杂度的分析方法。2、实验要求(1)根据题目要求选择合适的查找算法和排序算法。(2)按照题目要求将结果输出。(3)编写完整程序完成下面的实验内容并上机运行。(4)整理并上交实验报告。二、实验内容1、问题描述假设某公司招工n名，报考者的政审、体检已通过，现在要根据报考者的考试成绩择优录取。考试课程有：政治、语文、数学、英语四门。考试成绩分为四类：第一类为四门都及格；第二类为一门成绩不及格；第三类为两门成绩不及格；其余为第四类。录取方法是按类次并在每一类中按总分从高到低录取。试设计一个成绩处理程序，要求打印输出n份录取通知书，列出录取者四门课程的成绩及总分，最后查找并输出在第一类中英语成绩最好者的纪录。（假设第i名和第i+1名一定不会同类且总分相等。）2、说明(1)输入数据：输入每个考生的姓名及各门课程的考试成绩。(2)输出数据：按照择优录取的次序打印出n份录取通知书如下图：ADMISSIONNOTICEⅹⅹⅹⅹⅹ(姓名)YouhavebeenadmittedYourscores:Politicsⅹⅹ(成绩)ChineseⅹⅹMathematicsⅹⅹEnglishⅹⅹTotalⅹⅹⅹⅹⅹⅹCOMPANY华北电力大学科技学院实验报告第9页(3)每个考生建立一个纪录、格式如下姓名政治语文数学英语总分类别三、实验步骤1、用户输入每个考生姓名、考试成绩等信息，根据题目给的纪录格式存储。2、根据类别及每一类按总分从高到低排序，根据排序结果输出n份录取通知书。3、根据排序结果查找并输出在第一类中英语成绩最好者的纪录信息。