《数据结构》教案

《《数据结构》教案》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《数据结构》教案信息技术学院软件教研室课程说明【目的】1.数据结构是研究数据组织、存储和运算的一般方法的学科。——理解并掌握数据的各种数据结构的原理与算法。2.学会分析研究计算机加工的数据结构的性质，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。3.数据结构是编程的基础。程序=数据结构+算法——能够以数据结构为基础，进行复杂程序编程,且符合软件工程的规范。4.数据结构课程重点是培养学生的数据抽象能力。【内容】1.数据结构的基本概念（第1章）2、线性表（第2、3、4、5章）3、

2、树（第6章）4、图（第7章）5、查找和排序（第9、10、11章）【参考书】1．数据结构严蔚敏清华大学出版社2.数据结构（c语言篇）——习题与解析（修订版）李春葆清华大学出版社3.【教学安排】课时分配表1计算机与信管专业43+8=51章目内容讲课时数实验时数第一章绪论2第二章线性表62第三章栈和队列42第四章串1第五章数组和广义表2第六章树和二叉树102第七章图102第九章查找4第十章排序4合计51438第1章绪论【教学目的】1.数据结构的基本概念,介绍数据和数据结构等名词和术语。1.描述算法的类C语言2.从时间和空间角度分析算法的方法

3、【教学要求】掌握基本概念，了解抽象数据类型，掌握计算语句频度和估算算法时间复杂度，熟悉类C语言的书写规范。【教学重点与难点】描述算法的类C语言；抽象数据类型的概念；算法复杂性的分析方法【教学追记】1、熟悉各名词、术语的含义，掌握基本概念，特别是数据结构的三个方面（逻辑结构、存储结构、及其运算）。数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。2、了解抽象数据类型的定义、表示和实现方法。3、理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有

4、输出；⑤可行性（用以描述算法的操作都是足够基本的）。4、掌握计算语句频度和估算算法时间复杂度的方法。5、熟悉类C语言的书写规范，对学过C++的学生，比较输入/输出语句cin/cout；动态分配内存语句new与C语言的区别。6、本章的授课方法：讲授为主，自学为辅，通过练习掌握概念和方法，可以通过1个编程，理解抽象数据类型的概念【教学内容】1.什么是数据结构2.基本概念和术语3.抽象数据类型的表示与实现4.算法和算法分析1.1什么是数据结构一、计算机解决具体问题的步骤1、从具体问题抽象出一个适当的数学模型；2、设计解此数学模型的算法；3、

5、编程，进行测试、调整直至得到最终解答。对数值计算问题可以用数学方程来描述。但是，对许多非数值计算问题无法用数学方程加以描述。需要用表、树、图等数学模型来描述。二、非数值问题的三个例子1、图书馆的书目检索系统自动化问题；——表2、计算机和人对弈问题；——树3、多叉路口交通灯的管理问题。——图线性表例1-1书目自动检索系统001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02……………………分析：在图书馆需要查阅图书目录卡片，可以利用计算机实现自动检索。计算机处理的对象是数目信息，可以由登

6、录号、书名、作者名、分类号、出版单位和出版时间等组成。在书目自动检索系统中可建立一张按登录号顺序排列的书目文件和三张分别按书名、作者名、分类号顺序排列的索引表。这四张表构成的文件便是书目自动检索的数学模型。Seepage2图1.1类似的问题还有查号系统自动化、仓库帐目管理等。结论：树在这类文档管理的数学模型中，计算机处理的对象之间通常存在着的是一种最简单的线性关系(一对一)，这类数学模型可称为线性的数据结构。——表例1-2计算机和人对奕问题分析：计算机能和人对弈是因为有人将对弈的软件事先存入计算机。l在对弈问题中，计算机操作的对象是对

7、弈过程中可能出现的棋盘状态称为格局。l格局之间的关系是由比赛规则决定的，这个关系不是线性的。从一个格局可派生出几个格局。见p2图1.2l若将从对弈开始到结束的过程中所有可能出现的格局都画在一张图上，则可得到一棵倒长的“树”。l“树根”是对弈开始之前的棋盘格局，而所有的“叶子”就是可能出现的结局，对弈的过程就是从树根沿树叉到某个叶子的过程。结论：在人-机对弈问题的数学模型中，计算机处理的对象之间通常存在着一种“树”的关系。“树”可以是某些非数值计算问题的数学模型，它也是一种数据结构。图例1－3多叉路口交通灯管理问题CEDAB分析：在多叉

8、路口需设几种颜色的交通灯才能既使车辆相互之间不碰撞，又能达到车辆的最大流通。见P3图1.3通常，这类交通、道路问题的数学模型是一种称谓“图”的数据结构。l图中的一个顶点表示一条通路，而通路之间矛盾的关系以顶点间的连线表示