数据结构 第1章-新1.ppt

引 言 数据结构的概念及其研究的问题，是本章中重要的概念，它们贯穿整本书。除了数据结构研究的三个方面，我们对每种数据结构都会给出应用的实例。 要学会描述数据结构和算法，分析算法的时、空复杂度。;内容提要 1．给出数据结构的概念 2．介绍数据抽象和抽象数据类型 3．说明数据结构和算法描述的方法 4．介绍算法和算法分析的基本方法;1.1 算法和数据结构;1.1 算法和数据结构;;;，;;1. 数据：计算机加工处理的对象 2.数据元素：是组成数据的基本单位，在计算机程序中通常作为一个整体来处理。 数据元素由若干数据项组成。 3.数据项是不可再分割的。;表1.1 学生情况表;数据结构的由来 数据结构主要是为研究和解决如何使用计算机组织和处理这些非数值问题而产生的理论、技术和方法。它已成为计算机学科研究的基本课题之一。 ;什么是数据结构 定义1---- 数据元素之间的相互关系称为结构，带有结构的数据元素的集合称为数据结构。 定义2---- 按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示 方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。 ; 数据结构包括三个方面 逻辑结构：数据元素间的逻辑关系； 存储结构：数据在计算机内的表示形式； 运算：在数据上执行的操作。;数据结构举例 ;1.2.2 数据的逻辑结构;4种基本的逻辑结构; ;; 顺序存储 顺序（或称连续）表示方法需要一块连续的存储空间，并把逻辑上相关的数据元素一次存储在该连续的存储区中。; 链式存储 ;;1.2.4 数据结构的运算; 静态数据结构和动态数据结构 如果一个数据结构一旦创建，其结构不发生改变，则称为静态数据结构，否则成为动态数据结构。; 小结 数据结构是一门研究程序设计问题中计算机的操作对象（数据）以及它们之间的关系和运算的学科。;1.3 数据抽象和抽象数据类型 ; 1. C 语言的数据类型 (1)基本类型：字符、整型 …… (2)构造类型：数组、结构和联合 (3)指针类型：指针;抽象数据类型（Abstract Data Type, ADT）是一个数据类型，其主要特征是该类型的对象及其操作的规范,与该类型对象的表示和操作的实现分离，实行封装和信息隐蔽，即使用和实现分离。; 规范指明“做什么”， 实现解决“怎样做”。 规范是实现的准则和依据 ;一个数据结构包含两个层次： (1)数据结构的规范（抽象层）： 逻辑结构和运算的定义组成了数据结构的规范 (2)数据结构的实现（实现层）： 存储结构和运算算法实现构成了数据结构的实现;1.4 描述数据结构和算法;本书是怎样描述每种数据结构？ ; （1）用格式化的自然语言来描述数据结构的规范。 （2）用一个C++的抽象模板类描述数据结构的规范。;数据结构描述举例---堆栈;ADT 1.1 栈抽象数据类型 ADT Stack { Data: 　　　　　(描述逻辑结构) 0个或多个元素的线性序列（a0，a1，? ，an-1)， 遵循LIFO原则。 Operations:　　(描述运算的定义) Create()：创建一个空栈。 Destroy():撤消一个栈。 Push(x)：元素x插入栈顶。 Pop()：删除栈顶元素。 Top(x)：在x中返回栈顶元素。 }　　　　　　　　　　　　　　　　;程序 1.1 栈的C++模板抽象类 templateclass T class Stack { public: virtual void Push(T x)=0; virtual void Pop()=0; virtual T Top(T x)const=0; … }; 除了构造函数，其余成员函数都是纯虚函数。顺序栈类SeqStack是类Stack在顺序存储表示下的一种实现，它是从抽象类Stack派生出来的，它可以实例化。;templateclass T bool SeqStackT::Push(T x) { if(IsFull()) { coutOverflowendl; return false; } s[++top]=x; return true; };1.5 算法分析的基本方法;1.什么是算法 一个算法(algorithm)是对特定问题的求解步骤的一种描述，它是指令的有限序列；此外，算法具有下列五个特征： (1)输入 算法有零个或多个输入。 (2)输出