数据结构第1章 绪论教案由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“第一章数据结构绪论”。
第1章 绪论
本章主要介绍以下内容
1、数据结构的概念及其研究的主要内容
2、基本概念和术语
3、算法的概念、特点以及效率评价方法
本章重点和难点：
1、数据结构、数据类型、ADT、算法等重要概念。
2、算法的描述方法以及评价标准与方法
1.1 数据结构的概念及其研究的主要内容
当我们需要使用计算机去解决实际问题的时候，我们总是希望计算机越智能越好，但是可能多数使用计算机的人都没有去想一个问题，即计算机的智能是如何得来的，如何使计算机智能提高？作为计算机专业的学生，这个问题就必须去问，而且还能够做出正确的回答。先让我们看一个简单的例子：
例1：已知集合A={1，3，4，6，7，8，97}，B={1，3，5，7，10，12}，求集合A和集合B的交集。
对于这个问题的求解过程，如果用纸和笔来运算，是一道非常简单的题目，如果用计算机来解决，我们都应该做些什么呢？
用计算机解决实际问题的一般步骤：
1、问题定义。分析问题是什么？明确问题要求是什么？理解问题做什么？
2、建立模型。将实际问题中的客观对象的属性及联系，抽形成逻辑数据模型。
3、定义数据。将数据模型的对象定义成计算机能存储处理的存储结构。
4、算法设计。根据存储结构，找出求解问题的策略和方法步骤。
5、编写程序。将算法用程序设计语言表示出来。
6、调试运行。将数据和程序输入计算机，查错修改，运行得到结果。
7、分析结果。计算结果是否符合要求，若符合则结束，否则，返回监察修改。上述7个步骤中，从步骤1到步骤5都是人工工作部分，步骤6也不都是计算机的工作，人工要对程序进行调试，步骤7其实也是一个人工工作，所以，大家可以发现，真正计算机做的工作不多，而人工做的是绝大部分。在人工做的这几个步骤中，建立模型和算法设计是较困难的两个步骤。1.1．1 数据结构研究的问题
对数据的操作不单纯是数值计算（仅占计算机数据处理的10%），比如求函数的值，求方差等，更多的是非数值计算，如检索、排序、插入、删除等。数值计算问题在《数值分析》（计算方法）学科中专门研究。非数值计算问题 是 《数据结构》学科所要讨论的内容。上面我们提到的建立模型和算法设计就是数据结构中的问题。
1、数据结构建模举例
例 1 图书管理问题：此例建立的是线性表。
类似的学生管理、人事管理、物资管理、商品管理等大量问题都可以抽象出 类似的线性数据结构。
例 2 计算机对弈问题。此例建立了一种树型数据结构。还有像计算机游戏、组织机构的层次结构等许多实际问题也可以抽象树形数据结构。
例 3 交通管理控制问题。此例建立了一种图状数据结构。另有像课程安排、工程管理等大量问题可以抽象出图状数据结构。
2、数据结构的概念
《数据结构》是研究计算机信息处理中非数值计算程序设计问题中的数据、数据之间的联系以及数据操作的专门学科。
对该定义的理解应该抓住两点：
（1）研究的对象是数据及其联系（称为数据结构）。
（2）研究的问题是非数值操作计算。1.1.2 数据结构研究的主要内容
根据数据结构的研究对象和研究问题，我们对数据结构研究的主要内容概括如下：
1、数据的逻辑结构。就是数据间的联系。这部分的内容是用户按数据间的内在逻辑关系和适当结构描述组织数据。
2、数据的存储结构。要使用计算机去解决问题，就要将要处理的数据存储在计算机内存中，所以数据的存储结构，是从系统实现角度，将逻辑结构映射成存储结构，在机内表示的形式。
3、数据的操作算法。所要解决的问题一定是对所存储的数据进行一系列操作，因此，数据的操作算法，就是在某种存储结构下给出算法的具体实现。
4、算法的效率分析。同一个问题的解决方法不一定是唯一的，不同的算法有不同算法的优劣，算法的效率分析就是分析算法的时间和空间效率，评价算法的优劣。
5、数据结构的应用。这一部分其实是上面4个部分的综合，利用数据结构知识解决某些实际问题
1.2 基本概念
1.2.1 数据的基本概念
1、数据。是对客观事物的符号表示。在计算机科学是指所有能够输入到计 算机中并能被计算机程序处理的符号集合。包括数值、文字、图像、图像、音频、视频等形式。
2、数据项。所谓数据项就是数据中具有独立含义的、不可再分割的最小数 据单位。是客观实体一种特征的数据表示。
3、数据元素。是多个相关数据项的集，是一个客观实体多种特征的数据描 述，是计算机程序中加工处理的基本单位。数据元素按其组成可分为简单型数 据元素和复杂型数据元素。简单型数据元素由一个数据项组成，复杂型数据元素 由多个数据项组成，它通常携带着一个概念的多方面信息。1.2.2 数据结构的概念
数据结构，就是相互之间存在一种或多种特定关系的数据元素的集合。可以简单表示为：数据结构 = 数据 + 关系。同一数据元素集合，所定义的关系不同，构成不同的数据结构。那么，数据之间的都有些什么样的关系呢？
数据结构包括逻辑结构和存储结构两个方面。
1、数据的逻辑结构
数据的逻辑结构，是指对数据之间的关系的一种描述，或者说是一种定义，根据定义的关系不同，数据的逻辑结构分为四种：
（1）集合结构。数据元素之间未定义任何关的松散集合。
（2）线性结构。数据元素之间定义了次序关系的集合（全序集合），描述的是1对1关系。
（3）树形结构。数据元素之间定义了层次关系的集合（偏序集合），描述的是1对多关系。
（4）图状结构。数据元素之间定义了网状关系的集合，描述的是多对多关系。
2、数据的存储结构
数据的存储结构（亦成物理结构）是指数据结构在计算机存储器中的具体实现。存储结构与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。
常见的存储结构有：
（1）顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；
（2）链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。
（3）散列存储结构：顺序+散列。（4）索引存储结构：顺序+索引。1.2.3 数据类型的概念
1、数据类型：一个数据值的集合和定义在该集合上的一组操作构成的整体。
即： 数据类型 = 数据值的集合 + 一组操作的集合2、抽象数据类型： 一个数学模型和定义在该模型上的一组操作构成的整体。
即：抽象数据类型 = 数学模型 + 一组操作的集合定义抽象数据类型是主要是针对面向对象的程序设计。抽象数据类型简称AST，其形式描述格式如下： AST { 数据元素定义：给出数据元素的特性确切描述；
数据关系定义：给出数据元素之间关系的确切描述；
数据操作定义：给出施加在数据元素上的各种操作的确切描述； } 数据操作的形式定义：
函数返值类型 函数名（参数表）
{ 操作过程表示； } 1.3 本课程使用的描述工具
描述数据结构和算法可以用不同的工具。如Pascal、C、C++、Java语言等。本教材使用的描述工具是类 C语言。在为了算法描述过程的方便和意义明确，我们会使用一些指定的标示符表示一些确切的含义。（1）利用宏定义，预定义常量如下： #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW-1（2）数据元素被约定为Elemtype 类型，用户需要根据具体情况，自行定义该数据类型。
（3）算法描述采用C语言的函数形式：
函数类型 函数名（函数参数表）{ 语句序列； }
1.4 算法与算法分析
1.4.1 算法的概念及特征
1、算法的概念。算法是解决某个特定问题的有限步骤的描述。
2、算法的五大特征。
（1）有穷性：一个算法必须在执行有穷步之后结束。
（2）确定性：算法中的每一步，必须有确切的含义，不会产生二义性。（3）可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。
（4）输入：一个算法应该有零个或多个输入。
（5）输出：一个算法应该有一个或多个输出。输出是指与输入有某种特定关系的量。
如果一个过程不具有有穷性，则不能称之为一个算法，只能称之为一个过程（proce），比如操作系统，在没有关闭计算机之前，操作系统一直都在等待命令，这个等待的过程在没有强制终止之前是处于无限等待的状态。此外，这里的有穷应该是有效的又穷，如果一个算法执行的时间是100年，尽管是一个有限的时间，但是不是有效地，因为我们没有办法去等待100年再去看执行结果。1.4.2 算法的描述
1、自然语言描述。用人的语言表是算法过程的具体步骤。
2、图形语言描述。用流程图、N-S图、PAD图等表示算法过程。
3、用程序描述。
4、用专门的描述语言表是算法。是介于计算据程序设计语言和人类自然语 言之间的一种专用工具。如类Parscal、类C语言等。算法表示举例： 问题：求正整数a，b的最大公因数。
用自然语言描述算法如下：
（1）输入a，b的数值，如果有a
（2）任选a或者b中的一个作为最大公因数m；
（3）如果m能够整除a和b，输出m，否则，转到步骤4；
（4）m减小1，转到步骤3.用类C语言描述如下： int gcd(int a ,int b){ if(a
1.4.3 算法的设计要求
1、正确性。算法必须正确，能实现问题解决。
2、清晰性。易读、易懂、便于交流。必须坚持清晰第一原则。
3、健壮性。保证任何情况下都能正确运行。
4、高效性。实践和空间效率高。
1.4.4 算法的评价
1、评价标准
（1）时间复杂度：算法执行所需的总时间。算法的时间效率主要由两个因 素决定：所需处理问题的数据量大小，数据量大，所花费的时间就多；在解决 问题的过程中，基本操作的执行次数。（2）空间复杂度：算法所需的额外空间开销。
2、时间特性的分析
如果我们将一个算法所花费的时间设计成一个以数据量n为自变量的函数 T(n)，这个 函数在正整数定义域范围内一定是单调递增的。好的算法应该能够 在数据量n增长的同时，函数T(n)的增长速度比较缓慢。
具体计算方法有：事后统计法、是前估计法；精确及算法、粗略估计法。
常用的是粗略估计方法是用O(f(n))表示。
求O(f(n))时，一般只计算一种主要操作的执行次数估计时间复杂度。
3、空间效率的分析
一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法临时 开辟的存储空间单元。在有些算法中，占据辅助空间的数量与所处理的数据 量有关，而有些却无关。后一种是较理想的情况。在设计算法时，应该注意 空间效率。
估计方法是：算法中使用的额外存储单元数量。
《数据结构》教案课程性质和任务本课程是计算机专业的主要专业基础课程之一。本课程的参考教学时数为54学时，实际讲课学时为35，实验学时为16。其主要内容包括顺序表、链表、栈......
第一章 《绪论》教案教学目标：1.明确幼儿心理学的研究对象 2.掌握心理现象都有哪些3.掌握遗传与生理发展是怎样影响幼儿的心理发展的 4.了解环境和教育对幼儿的心理发展的影......
绪 论 珍惜大学生活，开拓新的境界目的要求：通过绪论的教学，使学生从对大学的认识和感受出发，了解大学生活的特点，认识自身的责任和使命，认识到学习《思想道德修养与法律基础》课与......
一、单项选择题（ B ）1.计算机算法必须具备输入、输出和 等5个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定......
西京学院机电工程系 第 1 次课学时授课日期：授课班级： 授课教师：王晋鹏批准人： 章节名称 1.1 材料力学的任务1.2 变性固体的基本假设1.3 外力及其分类1.4 内力、截面法和应力的......
