《数据结构》陈慧南_第01章基础常识[优质文档].pptVIP

数据结构 ;《数据结构A》课程性质、任务和目的;第1章 基础知识;1.1 算法与数据结构 1.2 什么是数据结构 1.3 数据抽象和抽象数据类型 1.4 描述数据结构和算法 1.5 算法分析的基本方法;1.1 算法与数据结构;数据结构和算法是计算机学科的基础之一，更是软件技术的基础。 数据的组织和表示方法直接影响使用计算机求解问题的效率。 算法设计通常建立在所处理数据的一定组织形式之上的，它们之间有着本质的联系。当讨论一种算法时，自然要涉及算法所处理的数据问题。 ;1.2? 什么是数据结构;1.2.1 基本概念;数据结构的由来 数据结构主要是为研究和解决如何使用计算机组织和处理这些非数值问题而产生的理论、技术和方法。它已成为计算机学科研究的基本课题之一。 ; 数据结构包括三个方面 逻辑结构：数据元素间的逻辑关系； 存储结构：数据在计算机内的表示形式； 运算：在数据上执行的操作。;赖掖景棋盲昧犬笺钥立华睬早番覆庞售牧整余秘站耽针毁苛期泳凳慧浊慕《数据结构》陈慧南_第01章基础知识《数据结构》陈慧南_第01章基础知识;1.2.2? 数据的逻辑结构; 四类基本逻辑结构 （a）集合结构 （b）线性结构 （c）树形结构 （d）图状结构 ;1.2.3 数据的存储表示; 链接存储 ;1.2.4 数据结构的运算; 静态数据结构和动态数据结构 如果一个数据结构一旦创建，其结构不发生改变，则称为静态数据结构，否则成为动态数据结构。;例1.1 栈数据结构 堆栈是一种线性数据结构，可以向栈中加入元素，但只允许访问和删除最后入栈的元素 （1）向栈中加入一个元素（Push运算）； （2）从栈中删除最后加入的元素(Pop运算)； （3）访问最后加入栈中的元素(Top运算)；; 什么是数据结构 一个数据结构是由数据元素依据某种逻辑联系组织起来的，对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。;1.3 数据抽象和抽象数据类型; 1.3.1 抽象、数据抽象和过程抽象 ; 整型int的规范 变量 a ???取值范围是：-32768~32767 对变量 a 执行的操作有： 算术运算 +、-、*、/、% 关系运算 、、=、=、==、!= 赋值运算 = 整型int的实现 变量 a 在计算机内存储表示方法。 操作的具体实现方法。; 1.3.2 封装与信息隐蔽 ;模块应采用封装和信息隐蔽原则来设计,这样的模块被称为黑盒子。 封装和信息隐蔽的作用：错误局部化，降低问题求解的复杂性，提高程序的可靠性。 C++语言的类 可以封装数据和运算，其公有、保护和私有成员机制有利于实现信息隐蔽。; 1.3.3 数据类型和抽象数据类型 ; 抽象数据类型（abstract data type ADT）是一个数据类型，其主要特征是该类型的对象及其运算的规范,与该类型对象的表示和运算的实现分离，实行封装和信息隐蔽，即所谓使用和实现分离。 ; 1.3.4 数据结构与抽象数据类型 ;数据结构的抽象层次 抽象层：讨论数据的逻辑结构及其运算定义， 实现层：讨论数据的存储表示以及运算的算法实现。;1.4 描述数据结构和算法;1.4.1 数据结构的规范;ADT 1.1 栈ADT ADT Stack { 数据： 0个或多个元素的线性序列（a0,a1,...,an-1）,　其最大允许长度为MaxStackSize。 运算： Create()： 建立一个空栈 Destroy()：撤消一个栈 Push(x)：值为x的新元素进栈，成为栈顶元素 Pop()：从栈中删除栈顶元素 Top(x)：在x中返回栈顶元素 };templateclass T class Stack {// 栈类Stack是一个模板抽象类， 其成员函数为纯虚函数，未定义数据成员。 public: virtual bool Push(T x)=0; virtual bool Pop()=0; virtual bool Top(T x) const=0; …… }; ;1.4.2 实现数据结构;templateclass T SeqStackT::SeqStack(int mSize) { maxTop=mSize-1; //设置栈的容量值 s=new T[mSize]; //生成存储栈的数组