基础试验四.DOC

基础实验题目 目录 实验一 线性表的基础训练（2次上机） 2 实验二 栈、队列及其应用（1.5~2.5次上机） 3 实验三 二叉树及其应用（2次上机） 5 实验四 图及其应用（2~3次上机） 7 附录 Makefile 、GCC、pkg-config 使用说明 8 1．GCC的使用 8 2．pkg-config的作用 11 3．Makefile的作用 11 实验一 线性表的基础训练（1~2次上机） 【上机时间】 第1～2次 【实验目的】 熟悉掌握本门课程所使用的程序设计语言(C语言)体会算法与程序之间的区别： /输出、参数传递； 熟练使用C中的动态分配与释放函数(malloc, realloc, free)； 熟悉带参数的main函数的编写与运行； 类C的引用参数在C中的变换处理； 利用输入导向，从文件中获取输入数据。 初步理解线性表的顺序存储和链式存储特性,掌握在不同存储结构、不同约定下，其基本操作的实现方法与差异。体会以下几点（注意你所做的约定）： 静态分配的顺序表及增量式分配的顺序表在表示与实现上的差别，各有何特点； 有头结点的链表与无头结点链表在操作实现上的区别； 头插法与尾插法的操作方法及应用效果对比； 插入、删除操作在顺序存储和链式存储上的差别； 非循环单链表、循环单链表各适用于解决哪些问题，它们在数据类型定义、操作的定义及实现上各有什么区别？ 静态链表与动态链表之间的映射与差别（自选）。 【实验要求】 下载Gzip的相关资源，用VC为Gzip建立project，编译运行Gzip；给出3种以上的命令行输入，单步跟踪Gzip对命令行参数的处理；目的：开展程序理解的第一阶段。 下载ch2.rar其中c1.h是第1章预设的一些宏和类型名， c2-1.h是顺序表的类型定义，c2-2.h是链表的类型定义，bo2-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()函数。命令行格式： 〈可执行程序名〉〈人数n〉〈初始的报数上限m〉〈密码1〉 …… 〈密码n〉·第1个参数是你所编写的程序的可执行文件名，·第2个参数是指定形成约瑟夫环的人数n·第3个参数是指定初始的报数上限m·后面n个参数是n个人所持有的整数密码。当除可执行程序名外，没有参数时，将继续执行程序并提示用户输入这些参数。基本要求：1）假设命令行参数是齐全的且是正确的，运行所编写的程序能正确地输出结果；2）能将输出结果导到文件中。实验提示：该实验的处理可分以下几个模块：1）命令行参数的处理；2）单循环链表的创建；3）根据m和起始报数人对应在单循环链表中的位置，确定出列人的位置；4）删除出列人对应的结点。选作要求：1）程序有对命令行参数不全或不正确的处理(如提示输入、报错等)；2）将约瑟夫环用顺序表实现。 撰写实验报告。 【检查期限】 上机内容检查时间：第2次和第3次上机时，以第3次上机为截止时间； 报告上交截止时间：第2次上机后的第一次课的上课前截止。 实验二 栈、队列及其应用（1.5~2.5次上机） 【上机时间】 第3次，第4次 【实验目的】 深入理解栈和队列的特性，领会它们各自的应用背景。熟练掌握它们在不同存储结构、不同的约定中，其基本操作的实现方法与差异。体会以下几点（注意你所做的约定）： 栈：顺序栈（栈空/栈满条件，入栈/出栈）、链栈（栈空条件，入栈/出栈）； 队列：链队列（队空条件，入队/出队）、顺序队列/循环顺序队列（队空/队满条件，入队/出队）； 【实验内容】 本次实验共五个题目，可任选其中的一题或多题。 魔王语言解释 具体要求参见《数据结构题集》P97,实习2.2中的描述。 算术表达式求值的演示 具体要求参见《数据结构题集》P99实习2.5中的描述。 N-皇后问题 假设有一N×N的棋盘和N个皇后，请为这N个皇后进行布局使得这N个皇后互不攻击(即任意两个皇后不在同一行、同一列、同一对角线上。 要求： 1) 输入N，输出N个皇后互不攻击的布局； 2) 要求用非递归方法来解决N-皇后问题，即自己设置栈来处理。 背包问题 假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , … , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + … + wn=T，要求找出所有满足上述条件的解。 例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解： （1，4，3，2） （1，4，5） （8，2）