《应用数据结构》实验指导书2013.doc

《应用数据结构》实验指导书 课程编号：4170159110 课程名称：应用数据结构/Applied Data Structure 实验学时：16 适应专业：工科类 承担实验室：管理学院实验中心 一、实验目的和任务 1．实验教学的目的 本课程的教学要求之一是训练学生进行复杂程序设计的技能和培养良好程序设计的习惯，其重要程度绝不亚于知识传授。实验的作用在于帮助学生深入理解教材内容，巩固基本概念，促使学生在动手过程中进一步体会C语言中数据结构的运用技巧，并锻炼学生在调试过程中分析和发现问题的能力。 2．实验教学的要求 学生应掌握C语言基本编程能力并运用数据结构的原理和方法解决具体问题。除按时上机外，学生应具备构造算法并用程序实现的能力；在程序调试过程中，学生应能正确解读程序的错误提示并找到有效的解决办法。此外，规范书写算法也是一个值得高度重视的问题，教师有责任在教学过程中提醒学生，避免形成一系列难以纠正且贻害无穷的程序设计坏习惯。此外，本门课程设计的算法比较多，要求教师熟练掌握C语言和数据结构各类算法，并能准确理解和回答学生提出的编程问题。 二、实验项目及学时分配 序号 实 验 项 目 名 称 实验学时 实验类型 开出要求 1 线性数据结构算法验证 4 验证及演示 必做 2 非线性数据结构算法验证 4 验证及演示 必做 3 查找及排序 4 验证及演示 必做 4 综合算法设计 4 综合 必做 三、参考资料 李业丽、郑良斌编著，数据结构（C）实验教程，北京理工大学出版社，2005年12月出版 严蔚敏，吴伟民编著，数据结构习题集（C语言版），清华大学出版社，1999年2月出版。 四、单项实验的内容和要求（包括实验所用的主要仪器设备，实验所需主要耗材） 实验一 线性数据结构算法验证 1．实验目的与意义 熟悉C语言的上机环境，进一步掌握C语言的结构特点 掌握线性表的顺序存储结构的定义及C语言实现 掌握线性表的链式存储结构——单链表的定义及C语言实现 掌握线性表在顺序存储结构——即顺序表中的各种基本操作 掌握线性表在链式存储结构——单链表中的各种基本操作 掌握栈的顺序表示和实现 掌握栈的链式表示和实现 掌握队列顺序表示和实现 掌握队列链式表示和实现 2．基本原理和方法 本实验涉及各类线性数据结构——线性表、栈和队列等。 单链表的各种操作，包括单链表的建立，结点的查找、插入、删除等基本运算。链表中插入结点的指针变化和删除p所指结点的指针变化参见讲义。 栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。 对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为p-top==MAXNUM-1，栈 出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空 注意： 顺序栈中元素用向量存放。栈底位置是固定不变的，可设置在向量两端的任意一个端点。栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称to为栈顶指队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。 入队时，将新元素插入rear所指的位置，然后将rear加1，出队时，删去front所指的元front加1并返回被删除元素。 顺序队列中的溢出现象： “下溢”现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常“真上溢”现象。当队列满时，做进找运算产生空间溢出的现象。“真上溢”是一种出“假上溢”现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的define MAXLEN 100 typedef struct node { int num；//学号 char name[MAXLEN]；//姓名 float score；//成绩 struct node *next; }linklist; B．栈部分 此部分的算法独立性较强，因此可直接采用教材或讲义上的算法实现，但教材或讲义上的算法并非可执行的算法，故学生须自行进行算法上的转换。 C．队列部分 本实验主要由教师课堂演示，以一个具体的实例——机场事件模拟来实现。 5．实验内容及步骤 A．线性表部分——学生成绩管理是学校教务管理的重要组成部分，其处理信息量很大，本实验是对学生的成绩管理作一个简单的模拟，用菜单选择操作方式完成下列功能： 登记学生成绩 查询学生成绩 插入学生成绩 删除学生成绩 【参考程序】 /*头文件hh.h的内容*/ #includestdio.h #includestdlib.h #includemalloc.h #define MAXLEN 100 typedef struct node { int num; char name[MAXLEN]; int score; struct node *next; }list; /*头文件