《2007-2008学年第一学期new》由会员分享，可在线阅读，更多相关《2007-2008学年第一学期new（15页珍藏版）》请在金锄头文库上搜索。
1、 数据结构 教案教 案2007-2008学年第一学期 课 程 名 称： 数据结构 课 程 编 号： 411101 学院、专业、年级： 信息科学与工程学院 计本06 任 课 教 师： 郑志华 教 师 所 在 单 位： 信息科学与工程学院 山东师范大学课 程 简 介数据结构是计算机专业的一门重要的专业技术基础课程，主要介绍软件设计中常用的数据结构及其运算，包括：线性表、栈、队列、串、数组、广义表、树、二叉树、图结构等几种基本的数据结构及其存储结构和所施加的运算与实现等。另外还介绍软件设计中常用的几种查找和排序运算，以及递归技术等，在介绍各项内容的同时，还涉及到算法设计与分析的基本技术和面向对象程序
2、设计的理论与技术等内容。通过本课程的学习，学生应能熟练掌握上述结构及其运算的实现和性能特点，掌握各种排序和查找运算以及递归技术，并能对给定的实际问题，建立准确的问题模型，设计有效的问题求解方法，选择合理的数据结构及其运算集，设计有效的算法，从而为提高软件设计水平打好基础。 教学大纲课程编号：4111201英文课程名：Data Structure 总 学 时：88学时（其中含实验教学 16 学时）学 分：4学分 课程类别：专业基础课适用专业：计算机科学与技术、通信工程、信息技术方向先修课程：高级程序设计一、课程性质与目的、要求数据结构是计算机科学与技术专业本科生的一门必修的专业基础课，是计算机程
3、序设计的重要理论技术基础，也是计算机专业的核心课程。本课程的主要目标是使学生深入了解数据结构的思想和数据结构的实现方法，特别是数据结构在实际工作中的应用和技术。本课程以C或C+语言作为算法的描述工具，强化数据结构基本知识和程序设计能力的双基训练，加深学生对所学内容的理解，追求理论联系实际，实践教学与相应的教学内容相呼应。培养发展学生从事发展算法与程序设计研究和实践的能力，为后续专业课的学习和专业素质的培养奠定坚实的基础。二、教学内容及学时分配第一章： 绪论 2课时1、数据结构定义、基本概念：数据、数据元素、数据的逻辑结构、物理结构、算法等。 2、抽象数据类型。描述算法的程序语言3、算法与算法复
4、杂度分析第二章 线性表 8课时1、线性表的基本概念及抽象数据类型 2、线性表的顺序表的表示和实现：顺序表的定义和特点；顺序表的定义、查找、插入和删除3、线性表的链式表示和实现：（1）单链表：单链表的结构定义；单链表的查找、插入与删除；带表头结点的单链表及静态链表；（2）循环链表、双向链表的定义和基本操作4、一元多项式的表示和相加第三章 栈和队列 6课时1、栈。栈的定义、抽象数据类型及特点，栈的顺序存储表示和实现，栈的链接存储表示和实现。2、栈的应用：数制转换、括号匹配的检验及表达式求值3、栈与递归的实现4、队列 ：队列的定义、抽象数据类型及特点，循环队列队列的顺序存储表示和实现；5、队列的链接
5、存储表示和实现； 第四章 串 4课时1、串类型的定义2、串的表示和实现3、定长顺序存储、堆分配存储、块链存储表示，4、串的模式匹配算法：第五章 数组和广义表 6课时1、数组的定义、数组的表示和实现2、矩阵的压缩存储：特殊矩阵，稀疏矩阵的表示和存储、矩阵转置与快速转置、矩阵乘法3、广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；广义表的递归算法第六章 树和二叉树 12课时1、 树和二叉树：树的定义；树的术语；二叉树的定义；二叉树的性质；二叉树的顺序表示；二叉链表表示 2、二叉树遍历及应用：中序遍历；前序遍历；后序遍历； 3、线索二叉树：线索；线索化二叉树 4、树与森林：树的存储结
6、构；森林与二叉树的转换；树和森林的遍历5、哈夫曼树及其应用：最优二叉树（哈夫曼树）、构造哈夫曼树、哈夫曼编码的方法及带权路径长度的计算； 第八章 图 12课时1、图的基本概念：图的基本概念；图的抽象数据类型 2、图的存储表示：邻接矩阵；邻接表；邻接多重表 3、图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；关节点与重连通分量 4、最小生成树：kruskul算法；prim算法 5、最短路径问题：dijkstra算法 和Floyd算法6、活动网络：AOV网络与拓扑排序；AOE网络与关键路径 第九章 查找 8课时1、静态查找表：顺序表的查找，有序表的查找，静态表的搜索；索引顺序表 2、动态查
7、找表：二叉排序树和AVL树（AVL树定义；平衡化旋转；AVL树的插入和删除；AVL树高度）；B树和B+树；键树的查找 3、哈希表：哈希表，哈希函数，哈希函数的构造方法；处理冲突的方法；哈希表的查找及其分析 第十章 内部排序 10课时1、插入排序：直接插入排序；折半插入排序；2-路排序；希尔排序 2、交换排序：冒泡排序；快速排序3、选择排序：简单选择排序；树型选择排序；堆排序 4、归并排序 5、基数排序6、各种内部排序方法的比较第十一章 外部排序 2课时1、外部信息存储2、外排序方法：外排序的基本过程；k路平衡归并；置换-选择排序；3、最佳归并树第十二章 文件 2课时1、文件的基本概念2、顺序文
8、件、索引文件及组织三、教学方法以教师讲授为主，结合学生的大量练习与实践四、成绩考核方式考试以闭卷形式进行，笔试包含实验考核内容。五、教材与参考书教材：数据结构(C语言版)，严蔚敏等，清华大学出版社，2006.5参考资料：1 数据结构与程序设计(C语言第二版)，(美)Robert L.Kuse等著，敖富江译，清华大学出版社，2006.2 数据结构习题与解析(C语言版)，李春葆等，清华大学出版社，20063 数据结构习题集(C语言版)，严蔚敏等，清华大学出版社，2006 授课时间 9. 28 第 1、2 次课 授课章节第一章 绪论 任课教师及职称郑志华教学方法与手段多媒体课时安排4使用教材和主要参
9、考书数据结构（C语言版）严蔚敏著，清华大学出版社教学目的与要求：ch1 1.1了解课程的研究内容，课程的地位，什么是数据，理解数据结构和算法等基本概念1.2 理解基本术语：介绍数据、记录、字段、数据结构、逻辑结构、存储结构、运算、算法及其内在关系等。 1.3 理解算法及其描述：介绍算法的定义和描述语言。 1.4 算法分析：评价算法的几项指标，算法的时间复杂度及其基本求解方法和常用的时间复杂度。教学重点，难点：1.数据、数据的逻辑结构和存储结构、算法和算法复杂度2. 线性表的定义教学内容：第一章 绪论随着计算机的发展及应用领域的迅速扩展，计算机已不再仅仅适用于科学计算，而更多的是用于控制、管理、
10、数据处理等多方面的非数值计算。因此，计算机加工的对象不再是单纯的数值，而更多的是字符、图像、声音、表格等。这些数据不能随意堆放，而是要分析数据的特性及数据之间的关系后，对数据进行有效的存储和处理。什么是数据结构数据结构主要研究非数值应用问题中数据之间的逻辑关系和对数据的操作，同时还研究如何将具有逻辑关系的数据按一定的存储方式存放在计算机内。分析数据之间的逻辑关系和确定数据在计算机内的存储结构是程序设计前两个必须完成的任务。处理非数值计算问题和数值计算问题的解决方案不同。例1 求一组整数中的最大值求一组(n个)整数中的最大值 1 3 7 9 32 50 20 2 6这是一个线性结构例2 学生的数
11、据库管理学生档案表就是一个数据结构。计算机档案管理的主要功能包括： 查找、浏览、插入、修改、删除、统计等。如果把表中的一行看成一个记录并称为一个结点，则在此表中，结点和结点之间的关系是一种最简单的线性关系。例3：人机对弈将一个棋局看成一个结点，这就是一个树型结构。ABCDE例4 多叉路口交通灯的管理问题。在多叉路口设计几种颜色的信号灯才能使车辆间不相撞，且达到车辆最大流。设如图的五叉路口，其中，C和E为单行线，将如何设置交通灯？ 这是一个图型结构的问题。假设一条通路为一个顶点, 通路之间互相矛盾的关系以两个顶点之间的连线表示。设置红绿灯问题等价与对图的顶点的染色问题。综上所述：描述这类非数值计
12、算问题通常用表、树、图等结构。简单地说：数据结构是一门研究非数值计算问题中计算机的操作对象以及它们之间的关系和操作等的学科。1.2 基本概念和术语数据 (data) 指所有能输入到计算机中并被计算机程序处理的符号的总称。计算机输入和处理的数据除数值外，还有字符串、表格、图像甚至声音等，它们都是数字编码范畴。数据元素(data element) 数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成，也可以只由一个数据项组成。数据元素又被称为元素、结点(node)或记录(record)。数据项(data item) 指数据的不可分割的、含有独立意义的最小
13、单位，数据项有时也称字段(field)或域。上面的学生档案表格是要存放到计算机中进行处理的数据，表中每一行记录了一个学生的档案信息，在数据操作中作为一个整体考虑，对应为一个数据元素，又称为一个记录。这个记录中包含有学号、姓名等若干个数据项。操作的基本单位是记录，如学生的插入或删除一定是作用于一个学生的全部信息即一个记录，而不可能是作用于其中的某个数据项。设想删除操作只删除某个学生的姓名或学号，将引起数据的不完整等严重后果。每个数据项(如学生的姓名或学号)均有独立的含义，但在档案管理这个实际问题中并无完整的意义，而组合在一个记录中构成学生的档案，就具有了完整的实际意义。数据、数据元素、数据项实际上反映了数据组织的三个层次：数据可由若干个数据元素构成，而数据元素又可以由一个或若干个数据项组成。数据逻辑结构 (data logical structure) 数
