《数据结构实验与课程设计》实验教学大纲

《《数据结构实验与课程设计》实验教学大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构实验与课程设计》实验教学大纲课程名称：数据结构实验与课程设计英文名称：ExperimentandCourseProjectofDataStructure课程编号：2215201101~107课程性质：课程类型：专业基础课是否为独立设课的实验课：是适用专业：计算机与软件学院学时与学分：总学时：72总学分：2实验学时：72实验学分：2执笔人：蔡茂国制定时间：2012年9月一、实验课的任务、性质与目的本实验课程与《数据结构》理论课堂教学有机结合，相辅相成。在理论课堂教学中，比较全面、概括性地讲述数据结构学科中一些基础性知识、重要概念及各种算法，而在本实验课程中，将这些基础性

2、知识、重要概念及各种算法，在计算机上编程实现，使学生能够达到以下教学目标：⑴、掌握计算机处理数据的基本方法⑵、了解算法需用的时间及空间分析方法⑶、能够为实际应用所涉及的数据选择适当的逻辑结构、存储结构及相应的算法⑷、通过在计算机上编程实现课程中介绍的各种算法，在程序设计能力方面得到提升。二、主要仪器设备及环境1．计算机2．Windows软件环境3．TurboC/VC编程环境三、实验项目的设置与实验内容序号实验项目名称实验内容实验算法实验要求实验时数每组人数实验类型1顺序表实验顺序表类定义顺序表创建、插入、删除、查找等功能的实现顺序表的测试运行（1）顺序表的存储结构包含三个部分：

3、数据数组、最大长度、实际长度（2）顺序表的创建：分配空间、参数初始化（3）顺序表的插入：位置i和后面的数据全部后移一位，在指定位置i插入一个数据，长度加1（4）顺序表的删除：位置i后面的数据全部前移一位，覆盖掉位置i的数据，长度减一（5）顺序表的查找：给出位置i的数据必做41验证2必做41验证单链表实验1、链表结点表类定义2、单链表类定义3、单链表的创建、插入、删除、查找等功能的实现4、单链表的测试运行（1）链表结点的存储结构包含两部分：数据、下一结点指针（2）单链表的创建：分配空间、参数初始化（3）单链表的插入：创建新的结点，在位置i-1和位置i之间插入新的结点，修改相关指针

4、指向，长度加1（4）单链表的删除：修改位置i-1结点的下一结点指针指向i+1结点，删除位置i结点，长度减一（5）单链表的查找：给出位置i结点的数据3堆栈应用括号匹配1、顺序栈类的定义2、成员函数，包括入栈、出栈、取栈顶元素3、匹配判断函数4、主程序算术表达式中右括号和左括号匹配的次序正好符合后到括号要最先被匹配的“后进先出”堆栈操作特点，因此可以借用一个堆栈来进行判断。具体方法：⑴顺序扫描算术表达式（表现为一个字符串）；⑵当遇到三种类型的左括号时，让该括号进栈；⑶当遇到某一种类型的右括号时，比较当前栈顶括号是否与之匹配，⑷若匹配则退栈，转（1）继续进行判断；⑸若不匹配，则左右括

5、号配对次序不正确，结束。⑹若字符串当前为某一类型的右括号而堆栈为空，则右括号多于左括号，结束。⑺若字符串扫描结束而堆栈非空，则左括号多于右括号，结束。⑻若字符串扫描结束而堆栈为空，则左右括号匹配正确，结束。必做41验证4堆栈和队列应用回文创建队列节点类和链式队列类链式队列的实现，包括构造函数、析构函数及入队、出队、队列空否等成员函数创建堆栈节点类和链式堆栈类链式堆栈的实现，包括构造函数、析构函数及进栈、退栈、堆栈空否等成员函数设字符数组str中存放了要判断的字符串。把字符数组中字符逐个分别存入一个队列和一个堆栈，然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等，若全部

6、相等则该字符序列是回文，否则就不是回文。选做41验证判断是否回文函数5串应用KMP算法1、顺序串类的定义，包括构造函数、析构函数2、模式子串的next[j]函数3、KMP匹配算法函数4、主程序将主串和模式子串从第一位进行一一比较，当一趟匹配过程中出现字符比较不等(失配)时，不需回溯主串指针i，而是利用已经得到的“部分匹配”的结果，将模式子串向右“滑动”尽可能远的一段距离(next[j])后，继续进行比较。必做41验证6二叉树的遍历及相关应用1、定义二叉树结点类BiTreeNode2、定义二叉树类BiTree3、编写主程序2．先序遍历递归算法(1)、若二叉树为空，则返回；否则：(

7、2)、访问根结点(D)(3)、先序遍历左子树(L)(4)、先序遍历右子树(R)选做41设计7Huffman编码的设计与应用1、定义huffman树的结点结构HuffNode2、定义存放哈夫曼编码的数据元素结构Code3、定义huffman类4、编写主程序⑴、从huffman树的每一个叶子结点开始⑵、依次沿结点到根的路径，判断该结点是父亲结点的左孩子还是右孩子，如果是左孩子则得到编码0，否则得到编码1，先得到的编码放在后面⑶、直到到达根结点，编码序列即为该结点的编码的⑷、对所有的叶子结点重复2