基础实验题目.doc
《基础实验题目.doc》由会员分享,可在线阅读,更多相关《基础实验题目.doc(15页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、基础实验题目目录实验一 线性表的基础训练(2次上机)2实验二 栈、队列及其应用(1.52.5次上机)3实验三 二叉树及其应用(2次上机)5实验四 图及其应用(23次上机)7附录 Makefile 、GCC、pkg-config 使用说明81GCC的使用82pkg-config的作用113Makefile的作用11实验一 线性表的基础训练(12次上机)【上机时间】第12次【实验目的】熟悉掌握本门课程所使用的程序设计语言(C语言),体会算法与程序之间的区别:1、 熟悉VC等编程环境,学会单步跟踪、调试自己的程序;2、 了解project的创建、使用以及意义;3、 熟练定义含指向结构体自身的指针域的
2、结构体类型,掌握此类变量、指针变量的初始化、赋值、输入/输出、参数传递;4、 熟练使用C中的动态分配与释放函数(malloc, realloc, free);5、 熟悉带参数的main函数的编写与运行;6、 类C的引用参数在C中的变换处理;7、 利用输入导向,从文件中获取输入数据。初步理解线性表的顺序存储和链式存储特性,掌握在不同存储结构、不同约定下,其基本操作的实现方法与差异。体会以下几点(注意你所做的约定):1、 静态分配的顺序表及增量式分配的顺序表在表示与实现上的差别,各有何特点;2、 有头结点的链表与无头结点链表在操作实现上的区别;3、 头插法与尾插法的操作方法及应用效果对比;4、 插
3、入、删除操作在顺序存储和链式存储上的差别;5、 非循环单链表、循环单链表各适用于解决哪些问题,它们在数据类型定义、操作的定义及实现上各有什么区别?6、 静态链表与动态链表之间的映射与差别(自选)。【实验要求】1、 下载Gzip的相关资源,用VC为Gzip建立project,编译并运行Gzip;给出3种以上的命令行输入,单步跟踪Gzip对命令行参数的处理;学习带参的main的使用与编程。消化理解一些标识符和文件操作。目的:开展程序理解的第一阶段。2、 下载ch2.rar并阅读其中的代码。其中c1.h是第1章预设的一些宏和类型名, c2-1.h是顺序表的类型定义,c2-2.h是链表的类型定义,bo
4、2-1.c是ADT List中基本操作的顺序表实现, bo2-2.c是ADT List中基本操作的链表实现,algo2-1.c是例2-1的顺序表实现,algo2-12.c是例2-1的链表实现,algo2-12a.c是改写algo2-12.c的Union()函数。目的:体会用伪C表示的算法和C程序之间的差异。3、 阅读数据结构题集P79 1.2约瑟夫环,理解约瑟夫环的定义。编写一个程序,该程序根据输入的命令行参数创建一个单循环链表表示的约瑟夫环,然后输出约瑟夫环出列的顺序。命令行格式: 可执行程序名人数n初始的报数上限m密码1 密码n第1个参数是你所编写的程序的可执行文件名,第2个参数是指定形成
5、约瑟夫环的人数n第3个参数是指定初始的报数上限m后面n个参数是n个人所持有的整数密码。当除可执行程序名外,没有参数时,将继续执行程序并提示用户输入这些参数。基本要求:1)假设命令行参数是齐全的且是正确的,运行所编写的程序能正确地输出结果;2)能将输出结果导到文件中。实验提示:该实验的处理可分以下几个模块:1)命令行参数的处理;2)单循环链表的创建;3)根据m和起始报数人对应在单循环链表中的位置,确定出列人的位置;4)删除出列人对应的结点。选作要求:1)程序有对命令行参数不全或不正确的处理(如提示输入、报错等);2)将约瑟夫环用顺序表实现。4、 撰写实验报告。【检查期限】1、 上机内容检查时间:
6、第2次和第3次上机时,以第3次上机为截止时间;2、 报告上交截止时间:第2次上机后的第一次课的上课前截止。实验二 栈、队列及其应用(1.52.5次上机)【上机时间】第3次,第4次【实验目的】深入理解栈和队列的特性,领会它们各自的应用背景。熟练掌握它们在不同存储结构、不同的约定中,其基本操作的实现方法与差异。体会以下几点(注意你所做的约定):1、 栈:顺序栈(栈空/栈满条件,入栈/出栈)、链栈(栈空条件,入栈/出栈);2、 队列:链队列(队空条件,入队/出队)、顺序队列/循环顺序队列(队空/队满条件,入队/出队);【实验内容】本次实验共五个题目,可任选其中的一题或多题。1. 魔王语言解释具体要求
7、参见数据结构题集P97,实习2.2中的描述。2. 算术表达式求值的演示具体要求参见数据结构题集P99实习2.5中的描述。3. N-皇后问题假设有一NN的棋盘和N个皇后,请为这N个皇后进行布局使得这N个皇后互不攻击(即任意两个皇后不在同一行、同一列、同一对角线上。要求:1) 输入N,输出N个皇后互不攻击的布局;2) 要求用非递归方法来解决N-皇后问题,即自己设置栈来处理。4. 背包问题假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , , wn 的物品,能否从n件物品中挑选若干件恰好装满背包,即使w1 +w2 + + wn=T,要求找出所有满足上述条件的解。例如:当T=10,各件
8、物品的体积1,8,4,3,5,2时,可找到下列4组解:(1,4,3,2) (1,4,5) (8,2) (3,5,2)。提示:可利用回溯法的设计思想来解决背包问题。首先将物品排成一列,然后顺序选取物品装入背包,假设已选取了前i 件物品之后背包还没有装满,则继续选取第i+1件物品,若该件物品“太大”不能装入,则弃之而继续选取下一件,直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包,则说明“刚刚”装入背包的那件物品“不合适”,应将它取出“弃之一边”,继续再从“它之后”的物品中选取,如此重复,直至求得满足条件的解,或者无解。5. MML命令解释说明:MML命令又称人机交互语言,作用就是
9、客户端通过发送有意义的命令字符串来获取服务器的服务。它的格式有很多种,它的格式有很多种,我们要支持下面两种:1) 命令字:参数1=参数1值,参数2=参数2值,.,.,.有一个命令字和很多的参数块,每个参数块中有很多的参数,参数之间用逗号隔开参数值的类型有两种,整型和字符串。2) 命令字:.,.;命令字:.,.;命令字:.,.有很多的命令字,每两个命令字之间用分号隔开,每个命令字可以有很多的参数块,每个参数块的内容同格式1);基本要求:1) 提取所有的参数及其值,其中值为用双/单引号括住的字符串值或者整型值;2) 打印有多少个命令字和参数块个数以及参数的个数;3) 遇到非法输入要报警;附加要求:
10、1) 对非法输入报告其类型,如字符串没有引号等等;2) 限定参数必须为合法的标识符(即字母或下划线开始的、由字母数字下划线组成的字符串),对非法的标识符要报错;补充:如果程序的健壮性很强,即遇到精心设计的测试用例不会死机,可以提示输入错,则加分。【实验要求】1. 要求所编写的程序应:a) 必须带命令行参数;b) 必须通过命令行参数指定输入、输出文件的文件名,练习对文件的操作。2. 撰写实验报告。【检查期限】1 上机内容检查时间:第35次上机时,以第5次上机为截止时间;2 报告上交截止时间:第4次上机后的第一次课的上课前截止。实验三 二叉树及其应用(2次上机)【上机时间】第57次【实验目的】树是
11、一种应用极为广泛的数据结构之一,是本课程的重点。树是一种1:N的非线性结构。本章首先以二叉树这种特殊、简单的树为原型,讨论数据元素(结点)之间的1:N(N=0,1,2)关系的表示(顺序映像完全二叉树的顺序存储;链式映像二叉链表、三叉链表);重点介绍二叉树的各种遍历算法(先序、中序、后序、层次遍历);并以这些遍历算法为基础,进一步讨论二叉树的其他各种问题的求解算法。然后,展开对一般树的表示(双亲表示法、孩子表示法、孩子-兄弟表示法)和操作算法的讨论;强调树(森林)的孩子-兄弟表示法及其相关应用;并将表示树(森林)的孩子-兄弟链映射到表示二叉树的二叉链,从而获得树(森林)与二叉树的相互转换。本实验
12、以二叉树的链式表示、建立和应用为基础,旨在让学生深入了解二叉树的存储表示特征以及遍历次序与二叉树的存储结构之间的关系,进一步掌握利用遍历思想解决二叉树中相关问题的方法。本实验的另一个目的是让学生通过思考、上机实践与分析总结,理解计算机进行算术表达式解析、计算的可能方法,初步涉及一些编译技术,增加自己今后学习编译原理的兴趣,并奠定一些学习的基础。【实验内容】本实验由以下环节组成:1) 存储结构以二叉链表或三叉链表作为二叉树的存储结构;2) 二叉树的创建(链式存储)以某一种遍历的次序录入二叉树的元素,写出相应的二/三叉链表的创建算法,并上机实现该算法;二叉树的输入次序可以有如下几种方法,你可以选择
13、其中之一来作为二/三叉链表创建程序的输入:ABCEDFGH图 1(1) 添加虚结点补足成完全二叉树,对补足虚结点后的二叉树按层次遍历次序输入。如图1的二叉树输入次序为: A, B, C, F, D, E, F, F, F, G, F, F, H也可以通过添加虚结点,为每一实在结点补足其孩子,再对补足虚结点后的二叉树按层次遍历的次序输入。如图1的二叉树输入次序为: A, B, C, F, D, E, F, G, F, F, H, F, F, F, F, F, F进一步改进,可以在输入列表中忽略出现在列表尾部的虚结点,即: A, B, C, F, D, E, F, G, F, F, H(2) 通过
14、添加虚结点,将二叉树中的每一实在结点补足成度为2的结点,对补足虚结点后的二叉树按先序遍历的次序输入。如图1的二叉树输入次序为: A, B, F, D, G, F, F, F, C, E, F, H, F, F, F, F, F(3) 依次输入二叉树的中序和后序遍历的结果。如图1的二叉树输入次序为: 中序:B, G, D, A, E, H, C, F 后序:G, D, B, H, E, F, C, A(4) 依次输入二叉树的中序和先序遍历的结果。如图1的二叉树输入次序为: 中序:B, G, D, A, E, H, C, F 先序:A, B, D, G, C, E, H, F3) 二叉树的遍历对所
15、建的二叉树进行验证:按初始输入元素采用的遍历方法遍历该二叉树,看遍历的结果是否与初始输入一致;4) 二叉树的应用:线索二叉树的创建基于二叉树遍历思想的其它问题的求解:扩展二叉树的存储结构,增加表示直接后继线索的链域,给出创建给定二叉树的后序线索化二叉树的程序;5) 线索二叉树的遍历编写在后序线索化树上的遍历算法。6) 二叉树创建的特例表达式树在2)基础上,设计并实现为输入表达式(仅考虑运算符为双目运算符的情况)创建表达式树的程序:A) 先实现输入为合法的波兰式;B) 进一步考虑输入为中缀表达式(需要分析优先级和结合性)C) 考虑输入为合法的逆波兰式;7) 二叉树遍历的特例表达式树针对用6)创建
16、的表达式树,用3)遍历(先序/中序/后序)该树,比较它与实际的波兰式、中缀式和逆波兰式之间的区别;8) 二叉树的应用表达式求值与转换基于3)的后序遍历或基于5),A)完成给定表达式树的表达式求值运算;B)输出表达式的另一种表示方法(如波兰式、逆波兰式或中缀表达式)。 【实验要求】1. 每一学生必须完成以下内容:a) 1)至5)b) 6)中的A)、B)、C)之一c) 7)以及8)中的A)、B) 之一。2. 其余部分可以根据自己的实际情况酌情处理。【检查期限】1 上机内容检查时间:第68次上机时,以第8次上机为截止时间;2 报告上交截止时间:第7次上机后的第1次课上课前截止。实验四 图及其应用(2
17、3次上机)【上机时间】第810次【实验目的】图是另一种应用极为广泛的数据结构,是本课程的重点。图是一种M:N的非线性结构。在图的学习中,首先要解决如何表示图中顶点之间的关系。在教材中给出了邻接矩阵、邻接表、邻接多重表、十字链表四种存储结构,不同的存储结构有不同的应用范围(要求熟练掌握前两种存储结构)。其次,必须理解深度优先搜索和广度优先搜索的特征,熟练写出它们在ADT Graph以及在不同存储结构下的算法实现,并基于它们进一步掌握生成森林(树)的构造、连通分量的确定、关节点的查找等算法。再次,要能理解最小生成树的普里姆和克鲁斯卡尔算法,分析它们各自的特征以及时空特性。最后,掌握有向无环图的应用
18、,重点掌握拓扑排序(入度),理解如何利用拓扑排序进行关键路径的求解;理解在网中如何求从某源点到其它顶点以及任意两个顶点之间的最短路径(可以结合最小生成树理解)。本实验是图的基础实验,旨在让学生熟练掌握图的存储表示特征,各类图的创建、遍历方法以及基于遍历的算法应用。【实验题目】1、 图的存储结构的定义和图的创建图的种类有:有向图、无向图、有向网、无向网。图的存储结构可采用:邻接矩阵、邻接表。要求:分别给出邻接矩阵和邻接表在某一种图上的创建算法2、 图的遍历:非递归的深度优先搜索算法、广度优先搜索算法。3、 图的深度遍历的应用:求无向连通图中的关节点(教材P177-178,算法7.10和7.11)
19、4、 图的广度遍历的应用:给定图G,输出从顶点v0到其余每个顶点的最短路径,要求输出各路径中的顶点信息。【实验要求】1. 每一学生必须完成上述所有题2. 进一步熟悉静态链的应用:习题集7.25,以及依据此存储结构的3和4的实现本项内容可以根据自己的实际情况酌情处理,但是必须在实验报告中附上自己对静态链的体会(可以结合在树中的作业练习等来阐明)。【检查期限】1 上机内容检查时间:第910次上机时,以第10次上机为截止时间;2 报告上交截止时间:第10次上机后的第1次课上课前截止。附录 Makefile 、GCC、pkg-config 使用说明1. GCC的使用2. pkg-config的作用3.
20、 Makefile的作用此教程还不够完整,很多地方比较简陋,打算以后再不断完整它,现在来说用这个教程的内容已经能够开发程序了。1GCC的使用通常所说的GCC是GUN Compiler Collection的简称,除了编译程序之外,它还含其他相关工具,所以它能把易于人类使用的高级语言编写的源代码构建成计算机能够直接执行的二进制代码。GCC是Linux平台下最常用的编译程序,它是Linux平台编译器的事实标准。同时,在Linux平台下的嵌入式开发领域,GCC也是用得最普遍的一种编译器。GCC之所以被广泛采用,是因为它能支持各种不同的目标体系结构。例如,它既支持基于宿主的开发(简单讲就是要为某平台编
21、译程序,就在该平台上编译),也支持交叉编译(即在A平台上编译的程序是供平台B使用的)。目前,GCC支持的体系结构有四十余种,常见的有X86系列、Arm、 PowerPC等。同时,GCC还能运行在不同的操作系统上,如Linux、Solaris、Windows等。除了上面讲的之外,GCC除了支持C语言外,还支持多种其他语言,例如C+、Ada、Java、Objective-C、FORTRAN、Pascal等。程序的编译过程对于GUN编译器来说,程序的编译要经历预处理、编译、汇编、连接四个阶段。从功能上分,预处理、编译、汇编是三个不同的阶段,但GCC的实际操作上,它可以把这三个步骤合并为一个步骤来执行
22、。在预处理阶段,输入的是C语言的源文件,通常为*.c。它们通常带有.h之类头文件的包含文件。这个阶段主要处理源文件中的#ifdef、 #include和#define命令。该阶段会生成一个中间文件*.i,但实际工作中通常不用专门生成这种文件,因为基本上用不到;若非要生成这种文件不可,可以利用下面的示例命令:gcc -E main.c -o main.i在编译阶段,输入的是中间文件*.i,编译后生成汇编语言文件*.s 。这个阶段对应的GCC命令如下所示:gcc -S main.i -o main.s在汇编阶段,将输入的汇编文件*.s转换成机器语言*.o。这个阶段对应的GCC命令如下所示:gcc
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基础 实验 题目
限制150内