数据结构《数据结构A》课程性质、任务和目的第1章基础知识1.1算法与数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型1.4描述数据结构和算法1.5算法分析的基本方法1.1算法与数据结构数据结构和算法是计算机学科的基础之一，更是软件技术的基础。数据的组织和表示方法直接影响使用计算机求解问题的效率。算法设计通常建立在所处理数据的一定组织形式之上的，它们之间有着本质的联系。当讨论一种算法时，自然要涉及算法所处理的数据问题。1.2什么是数据结构1.2.1基本概念数据结构的由来数据结构主要是为研究和解决如何使用计算机组织和处理这些非数值问题而产生的理论、技术和方法。它已成为计算机学科研究的基本课题之一。数据结构包括三个方面逻辑结构：数据元素间的逻辑关系；存储结构：数据在计算机内的表示形式；运算：在数据上执行的操作。南京邮电大学计算机学院陈慧南2006年9月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数据类型和抽象数据类型抽象数据类型（abstractdatatypeADT）是一个数据类型，其主要特征是该类型的对象及其运算的规范,与该类型对象的表示和运算的实现分离，实行封装和信息隐蔽，即所谓使用和实现分离。1.3.4数据结构与抽象数据类型数据结构的抽象层次抽象层：讨论数据的逻辑结构及其运算定义，实现层：讨论数据的存储表示以及运算的算法实现。1.4描述数据结构和算法1.4.1数据结构的规范ADT1.1栈ADTADTStack{数据：0个或多个元素的线性序列（a0,a1,...,an-1）,其最大允许长度为MaxStackSize。运算：Create()：建立一个空栈Destroy()：撤消一个栈Push(x)：值为x的新元素进栈，成为栈顶元素Pop()：从栈中删除栈顶元素Top(x)：在x中返回栈顶元素}template<classT>classStack{//栈类Stack是一个模板抽象类，其成员函数为纯虚函数，未定义数据成员。public:virtualboolPush(Tx)=0;virtualboolPop()=0;virtualboolTop(T&x)const=0;……};1.4.2实现数据结构template<classT>SeqStack<T>::SeqStack(intmSize){maxTop=mSize-1;//设置栈的容量值s=newT[mSize];//生成存储栈的数组top=-1;//top==－1表示空栈}1.5算法分析的基本方法1.5.1算法及其性能标准输入：算法有零个或多个输入输出：算法至少产生一个输出确定性：算法的每一条指令都有确切的定义，没有二义性。能行性：算法的每一条指令都足够基本，它们可以通过已经实现的基本运算执行有限次来实现。有穷性：算法必须总能在执行有限步之后终止。算法的性能标准正确性：算法的执行结果应当满足预先规定的功能和性能要求。简明性：一个算法应当思路清晰、层次分明、简单明了、易读易懂。健壮性：当输入不合法数据时，应能做适当处理，不至于引起严重后果。效率：有效使用存储空间，并有高的时间效率。1.5.2算法的时间复杂度fl