数据结构讲义全

第 一 章 ： 绪 论课程：数据结构课题：第一章 1.1—1.4小节（共4 个课时）1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表现与实现1.4 算法和算法分析目的要求：理解数据、数据元素、数据项的概念；掌握逻辑结构和存储结构的关系；理解算法的基本概念；学会分析算法的时间复杂性和空间复杂性。新课重点、难点：数据、数据元素、数据项、时间复杂性和空间复杂性教学方法：课堂讲解、例题演示，课件演示教学容与过程：……………………………第1-2 课时……………………………计算机的应用不再局限于科学计算，更多地用于控制，管理，数据处理等非数值计算的处理工作。计算机加工处理的对象：数值，字符，表格，图形声音，图象等具有一定结构的数据。进行程序设计时必须分析待处理的对象的特性与各对象之间存在的关系———产生背景。1.1 什么是数据结构计算机解题步骤：建立数学模型——设计解此数学模型的算法——编制程序——进行测试调整——解答。其中建立数学模型的实质：找出操作对象之间的关系。例1. 图书馆书目检索 ——对应线性关系例2. 博奕树 ——对应树型关系例3. 交叉路口交通灯管理 ——对应图状结构。数据结构是一门讨论非数值计算的程序设计问题中计算机的操作对象与它们之间的关系和操作等的学科。（地位）1.2 数据结构的基本概念和术语1. 数据（Data）数据是描述客观事物的数值、字符以与能输入机器且能被处理的各种符号集合。换句话说，数据是对客观事物采纳计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。包括数值、字符、声音、图象等。2. 数据元素（Data Element）数据元素是组成数据的基本单位, 是数据集合的个体，在计算机常作为一个逻辑整体进行考虑和处理。一个数据元素可由若干个数据项组成（Data Item ）。3. 数据对象（Data Object ）数据对象是性质一样的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1 ，±2 ， …} ，字母字符数据对象是集合C={′A′，′B′ ，…，′Z′}，表1-1 所示的学籍表也可看作一个数据对象。由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只要性质一样，都是同一个数据对象。综上1~3 所述，再分析数据概念：4. 结构（Data Structure）数据元素相互之间的关系称为结构（ Structure ），有四种基...