S0050559《据结构实验》教学大纲.docVIP

《数据结构实验》教学大纲 课程名称：数据结构实验 课程号：S0050559 编写日期：2006年6月 一、开设院（部）： 信息工程学院。 二、教学对象： 信息管理与信息系统专业全体学生。 三、教学目的： 数据结构是信息管理与信息系统专业中的一门专业基础课，在计算机软件的各个领域中均会使用到数据结构的有关知识。本实验的目的和任务是使学生较全面地掌握各种常用的数据结构，学习使用所学的数据结构的基本知识和算法解决一定的问题，培养在程序设计中构造各种数据结构和综合使用各种算法的能力，提高运用数据结构解决实际问题的能力。 四、教学要求： 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、栈和队列、数组结构、二叉树和树、图结构、查找和排序相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 五、教学课时及其分配： 共计18个实验教学课时。 实验一、线性表及其应用（2学时） 选题有长整数四则运算，一元多项式简单计算和在线性表中删除某些元素。 实验二、栈和队列（2学时） 选题有算术表达式的求值, 迷宫问题。 实验三、数组及其应用（2学时） 选题有稀疏矩阵运算，n阶魔阵，实现数组中元素循环右移。 实验四、树和二叉树（4学时） 选题有层序遍历二叉树，交换二叉树的所有结点的左右子树。 实验五、图及其应用（4学时） 选题有无向图的遍历程序. 实验六、查找（2学时） 选题有哈希表的构造和查找，折半查找。 实验七、排序（2学时） 六、考核 采用上机情况、程序质量、实验报告相结合的形式，满分为100分。 1、 上机情况（30%） 包括出勤情况、调试表现、是否上网、玩游戏等。 2、 程序质量（50%） 3、 实验报告（20%） 七、选用教材 严蔚敏.数据结构（C语言版）习题集.北京：清华大学出版社，1997 八、主要参考书目 1．李春葆.数据结构（C语言篇）习题与解析.北京：清华大学出版社，2002 2．王小东.算法与数据结构学习指导与习题解析.北京：电子工业出版社，2001 3．朱若愚.数据结构（第二版）.北京：电子工业出版社，2002 4．[美]William Ford.数据结构C++语言描述.北京：清华大学出版社，2001 九、实验教学提纲 实验一 线性表及其应用 [实验目的] 通过实验题的上机实践，帮助学生掌握线性表的基本操作在两种存储结构上算法的实现，特别是链表，实验以各类链表的操作和应用作为重点。 [实验内容] 实验题目一：长整数四则运算 设计一个算法并编写代码，实现将两个任意长的整数相加的运算。 [实验步骤] 1 采用双向循环链表作为存储结构。每个结点含有一个整型变量。输入和输出形式：可以每四位(或每三位)一组，组间用逗号隔开。 2 可以看出这一程序仍是对链表知识的实践，但运用的是双向链表。每个结点可以放相应的若干位十进制数，因为要考虑溢出和进位的问题，任何整型变量的范围是-(215-1)~(215-1)，而215-1=32767，即每个结点中可以存放的最大整数，但这样存放就相当于按32678进制数存放，在十进制数与32678进制数之间转换极为不便，因此建议每个结点中仅存放十进制数的4位，即不超过9999的非负整数，整个链表表示为万进制数。 3 假如要考虑正负的话，可以利用头结点的数据域的符号代表长整数的符号。相加过程中不要破坏两个操作数链表。也不能给长整数位数规定上限。 实验题目二：在线性表中删除某些元素的算法实现 已知A、B和C为三个递增有序的线性表，现要求对A表作如下操作：删除那些既在B表中出现又在C表中出现的元素。 [实验步骤] 1 试对顺序表编写实现上述操作的算法并上机编写代码，要求算法尽可能高效。在实验报告中分析你的算法的时间复杂度。 2 A表中要删除的元素实际上就是在三个表中都存在的元素。注意这三个线性表都是递增有序的线性表！可以利用这一性质减少对线性表“扫描”的趟数。 3 改用单链表作为存储结构编写算法，请释放A表中无用的结点空间，并上机编程实现。 实验二　栈和队列 [实验目的] 通过上机实践掌握队列和栈的顺序存储结构和链式存储结构，以便我们能在相应的应用问题中正确选用它们；掌握栈和队列的特点，即先进后出与先进先出的原则；掌握栈和队列的基本运算，如入栈和出栈、入队与出队等运算在顺序存储结构和链式存储结构上的实现。 [实验内容] 实验题目一：算术表达式的求值 [实验步骤] 1 设计一个程序演示