数据结构(C描述)电子教案第1章

中等职业学校教材数据结构（C语言版）电子教学资料朱若愚张秋璞等编著Publishing House of Electronics Industry北京•BEIJING前言为了配合《数据结构（C语言版）》课程的教学，体现教材的编写特色，更好地为读者服务，编写了此教学资料。

教学资料内容有三个部分：第一部分是教学指南，包括了课程性质与任务、课程内容和要求、教学建议、教学时间分配。

第二部分是电子教案，采用PowerPoint课件形式。

教师可以根据不同的教学要求按需选取和重新组合。

第三部分是习题答案，给出了每道习题的详细解答过程。

限于编著者水平，教学资料中有错误或不妥之处，请读者给予批评指正。

编者2003年8月《数据结构（C语言版）》教学指南一、课程的性质与任务数据结构作为C语言的后继课程，是程序设计的重要基础。

计算机程序的主要任务是处理数据，而大量的数据在计算机中怎样存储就成为一个重要而基本的问题，什么样的存储结构节省存储空间？什么样的存储结构有利于提高处理效率？哪类问题适合于用哪类存储结构？某种存储结构适合于哪种算法？此算法的计算复杂性如何？此存储结构占用多少内存？...这一系列的问题都属于这门课研究的范围。

这里所说的存储结构包括内存中的物理存储结构和体现数据之间逻辑关系的逻辑结构。

而这里所说的算法则是解决某个具体问题的处理过程(多以函数形式来体现)，研究算法将使我们思路更开阔、技巧更灵活，将大大有利于我们程序设计水平的提高。

二、教学提要、课程内容、教学要求第1章绪论本章教学提要教学重点：数据结构的基本概念和术语类C语言的各种句型及算法描述的规范教学难点：数据结构的基本概念和术语本章教学内容数据结构是研究数据元素（data element）之间抽象化的相应关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

数据结构与算法（C语言篇）教学设计课程名称：数据结构与算法（C语言篇）_____授课年级：___________________________ 授课学期：___________________________ 教师姓名：___________________________2020年03月01日第一课时（数据结构的概念、逻辑结构与物理结构）了解数据结构与算法1.讲述数据结构与算法内容，引出本课时主题。

数据结构是计算机专业的一门基础课，其主要研究程序设计中的操作对象及它们之间的关系。

算法指的是解决问题的策略，只要有符合一定规范的输入，在有限时间内就能获得所要求的输出。

虽然数据结构与算法属于不同的研究课题，但优秀的程序设计离不开二者的相辅相成。

因此，本章将主要介绍数据结构与算法的基本概念，包括数据结构的基本术语、数据的结构分类以及算法的各种特性。

2.明确学习目标（1）能够了解数据（2）能够了解数据元素与数据项（3）能够了解数据对象（4）能够掌握数据结构（5）能够掌握逻辑结构（6）能够掌握物理结构知识讲解➢数据数据（Data）在计算机科学中是指计算机操作的对象，是输入到计算机中被计算机程序处理的符号集合。

例如，一个读取终端输入的程序，其操作的对象可能是字符串，那么字符串就是计算机程序处理的数据。

数据不仅可以是整型、字符型等数值类型，也可以是音频、图片、视频等非数值类型。

综上所述，数据的本质就是符号，且这些符号都满足以下特定的需求。

（1）可以输入到计算机中。

（2）可以被计算机程序处理。

其中数值类型的数据可以被执行数值计算，而非数值类型的数据可以被执行非数值的处理，例如，音频、图片、视频等资源在计算中都是被编码转换为字符数据来处理的。

➢数据元素与数据项数据元素（Data Element）是组成数据的基本单位。

数据的基本单位是一种抽象的概念，并没有具体的数值化标准。

例如，可以将公司看作一个数据元素，也可以将员工视为一个数据元素。

《数据结构（C语言版）》教案《数据结构（C语言版）》教案2020 至2020 学年第一学期教案课程名称数据结构使用教材《数据结构（C语言版）》教学时数56课程性质必修任课班级（人数）信管（53人）信息系（部）信管教研室任课教师山东科技大学泰山科技学院课时授课计划2020-2020学年第二学期第1周授课日期2月20 日星期1 月日星期月日星期月日星期月日星期班级信管10-1 基本课题第1章绪论 1.1-1.2 教学目的与要求：1. 了解数据结构的基本概念2. 理解常用术语教学重点：数据结构的基本概念和术语教学难点：数据元素之间的四种结构关系作业及参考书：1、什么是数据结构？《数据结构算法实现及解析》/高一凡编著教具：多媒体板书课堂类型：讲授教学过程：自我介绍——开课——引入——展开——举例——小结——作业一、自我介绍和课程介绍约8min 课时：64 二、引入约2min 由问题的提出引入三、讲课进程设计1.1 什么是数据结构 1.1.1、数据结构与其它的关系约15min 数据结构+算法=程序程序设计: 为计算机处理问题编制一组指令集算法: 处理问题的策略数据结构: 问题的数学模型 1.1.2、当今计算机应用的特点：约25min l) 所处理的数据量大且具有一定的关系；2) 对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。

举例说明：1) 学生成绩表2)井安棋对弈3)交通管理结论计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理；我们将此称为非数值性处理。

要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。

1.2 基本概念和术语1.1.1、数据与数据结构约20min 数据：是对客观事物的符号表示。

所有能被输入到计算机中，且能被计算机处理的符号的集合。

是计算机操作的对象的总称。

西安文理学院精品课《数据结构》教案计算机科学系韩利凯《数据结构》第一章绪论[教学目标]掌握数据结构的定义、内容、方法、描述、评价。

[重点、难点]数据结构的研究范围，研究采用的方法，算法规则描述的工具，对算法作性能评价。

[教学方法]用多媒体课件（ ppt ）以及与生活实例相结合等方法讲授，这样便于描述相关概念及学生记笔记，加深他们的印象，使基础知识掌握地比较牢固。

[学习要点]1. 熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。

分清哪些是逻辑结构的性质，哪些是存储结构的性质。

2. 了解抽象数据类型的定义、表示和实现方法。

3．理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。

4．掌握计算语句频度和估算算法时间复杂度的方法。

1.1 什么是数据结构（定义）首先介绍数据结构的相关名词。

1.数据（Data）数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。

2.数据元素（Data Element）数据元素是组成数据的基本单位 ,是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。

例如：学生登记表是数据，每一个学生的记录就是一个数据元素。

3.数据对象（Data Object）数据对象是性质相同的数据元素的集合，是数据的一个子集。

4.数据结构（DA TA Structure）数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。

5.数据类型(Data Type)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。

6.数据抽象与抽象数据类型１）数据的抽象高级语言中提供整型、实型、字符、记录、文件、指针等多种数据类型，可以利用这些类型构造出象栈、队列、树、图等复杂的抽象数据类型。

课程教案课程名称：数据结构授课教师：学习对象：任课时间：一、学生情况分析数据结构是计算机专业的一门核心专业课程。

学生在前期的学习中已经学习了C语言程序设计课程。

通过本课程学习使学生对提高编写程序的能力以及解决实际问题的能力。

二、课程教学目标《数据结构》是计算机学科中一门核心专业基础课。

主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。

通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。

三、课程教学内容第一章绪论教学内容：1）什么是数据结构2）抽象数据类型概念；数据类型；数据抽象与抽象数据类型；用于描述数据结构的语言3）数据结构的抽象层次4）算法定义5）性能分析与度量；算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；教学要求：了解：数据结构基本概念及数据结构的抽象层次了解：抽象数据类型概念了解：算法的定义及算法特性掌握：算法的性能分析与度量方法第二章线性表教学内容：1）线性表的定义和特点2）线性表的顺序存储及查找、插入和删除操作3）线性表的链式存储及查找、插入和删除操作4）使用线性表的实例教学要求：了解：线性表的定义和特点熟练掌握：线性表的顺序存储结构的查找、插入和删除等基本操作熟练掌握：单链表、循环链表及双向链表的定义及实现掌握：熟练掌握单链表的应用方法第三章栈和队列教学内容：1）栈：栈的抽象数据类型；栈的顺序存储表示；栈的链式存储表示2）队列：队列的抽象数据类型；队列的顺序存储表示；队列的链式存储表示3）队列的应用举例教学要求：熟练掌握：栈的定义及实现熟练掌握：队列的定义及实现掌握：能运用栈和队列解决简单实际问题教学:内容：1)字符串的抽象数据类型2)字符串操作的实现3)字符串的模式匹配教学要求：熟练掌握：字符串的定义方式熟练掌握：字符串的各种操作的实现了解：字符串的模式匹配算法第五章数组和广义表教学:内容：1)数组的定义和初始化2)作为抽象数据类型的数组的顺序存储方式教学要求：了解：作为抽象数据类型的数组的定义熟练掌握：顺序表的数组定义方式及实现第六章树和二叉树教学内容：1)树和森林的概念：树的定义；树的术语；树的抽象数据类型；森林的概念2)二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型3)二叉树的表示：数组表示；链表存储表示4)二叉树的遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的实例；二叉树的中序非递归算法5)线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化6)树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历7)二叉树的计数8)霍夫曼树：路径长度；霍夫曼树；霍夫曼树编码教学要求：了解：树和森林的概念掌握：二叉树的概念、性质及二叉树的表示熟练掌握：二叉树的遍历方法掌握：线索化二叉树的特性及寻找某结点的前驱和后继的方法掌握：树和森林的实现及遍历方法掌握：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法掌握：霍夫曼树的实现方法及霍夫曼编码的概念第七章图教学内容：1）图的基本概念：图的基本概念；图的抽象数据类型2）图的存储表示：邻接矩阵；邻接表；邻接多重表3）图的遍历与连通性；深度优先搜索；广度优先搜索；连通分量4）最小生成树：克鲁斯卡尔算法；普里姆算法教学要求：掌握：图的基本概念和图的存储表示熟练掌握：图的两种遍历方法与求解连通性问题的方法掌握：构造最小生成树的Prim和Kruskal方法教学内容：1)静态查找表：顺序表的查找；有序表的查找；索引顺序表的查找2)二叉排序树：二叉排序树上的搜索、插入和删除教学要求：熟练掌握：静态搜索表的顺序搜索和折半搜索方法熟练掌握：二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法第十章内部排序教学内容：1)概述2)插入排序：直接插入排序；对分插入排序；链表插入排序；希尔排序3)选择排序：直接选择排序；堆排序教学要求：掌握：排序的基本概念和性能分析方法掌握：插入排序、选择排序、等内排序的方法及性能分析方法单元名称：第一讲：绪论一、教学目标1.了解《数据结构》课程的体系结构2.掌握本章介绍的各种基本概念和术语3.了解数据结构的二元组表示4.掌握逻辑结构与物理结构之间的映像关系。