文档介绍：数据结构考核知识点数据计算机加工处理的对象数据元素组成数据的基本单位数据项数据元素可由若干个数据项( data item ) 组成, 数据项是数据的不可分割的最小单位逻辑结构数据元素间的逻辑关系存储结构数据在计算机内的表示形式数据结构数据结构主要是为研究和解决如何使用计算机组织和处理这些非数值问题而产生的理论、技术和方法。它已成为计算机学科研究的基本课题之一. 一个数据结构是由数据元素依据某种逻辑联系组织起来的, 对数据元素间逻辑关系的描述称为数据的逻辑结构; 数据必须在计算机内存储, 数据的存储结构是数据结构的实现形式, 是其在计算机内的表示; 此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。数据类型是程序设计语言中的概念,它是数据抽象的一种方式。一个数据类型定义了一个值的集合以及作用于该值集的运算集合。程序设计语言中, 一个数据类型不仅规定了该类型的变量(或常量)的取值范围,还定义了该类型允许的运算。数据抽象使程序设计者可以将数据元素间的逻辑关系和数据在计算机内的具体表示分别考虑。过程抽象使程序设计者将一个运算的定义与实现运算的具体方法分开考虑。抽象的好处主要在于降低了问题求解的难度。抽象数据类型( abstract data type ADT ) 是一个数据类型, 其主要特征是该类型的对象及其运算的规范, 与该类型对象的表示和运算的实现分离,实行封装和信息隐蔽, 即所谓使用和实现分离数据结构的规范数据结构被看成是一个类属抽象数据类型(ADT) ,用格式化的自然语言来描述。数据结构可以形式地用一个 C++ 的抽象模板类描述数据结构的实现 template<class T> class SeqStack:public Stack<T> { public: …… private: int top; //top 记录最后入栈的元素在 s 的下标 int maxTop; // 最大栈顶指针 T *s; //s 指向动态生成的一维数组,存放元素}; template<class T> SeqStack<T>::SeqStack(int mSize) { maxTop=mSize-1; // 设置栈的容量值 s=new T[mSize]; // 生成存储栈的数组 top=-1; //top== -1 表示空栈} 算法描述笼统的说, 算法是求解一类问题的任意一种特殊的方法。较严格的说法是一个算法是对特定问题的求解步骤的一种描述, 它是指令的有限序列; 此外, 算法具有下列五个特征: 输入:算法有零个或多个输入输出:算法至少产生一个输出确定性:算法的每一条指令都有确切的定义,没有二义性。能行性:算法的每一条指令都足够基本,它们可以通过已经实现的基本运算执行有限次来实现。有穷性:算法必须总能在执行有限步之后终止。算法分析算法的性能标准正确性:算法的执行结果应当满足预先规定的功能和性能要求。简明性:一个算法应当思路清晰、层次分明、简单明了、易读易懂。健壮性:当输入不合法数据时,应能做适当处理,不至于引起严重后果。效率:有效使用存储空间,并有高的时间效率。算法的时间复杂度是程序运行从开始到结束所需的时间算法的空间复杂度一个算法的空间复杂度是指算法运行所需的存储量线性表线性表是 n(? 0) 个元素 a 0,a 1,…,a n-1 的线性序列, 记为: (a 0 ,a 1,…,a n-1)。其中 n是线性表中元素的个数,称为线性表的长度; n=0 时称为空表。 a i 是表中下标为 i 的元素( i=0,1, …,n-1 ) ,称 a i是 a i+1 的直接前驱元素, a i+1是 a i 的直接后继元素。线性表是动态数据结构,它的表长可以改变。顺序表顺序表示的线性表称为顺序表顺序表长度顺序表中数据的个数顺序表在程序中的表示 template <class T> class SeqList:public LinearList<T> { public: // 公有函数 SeqList(int mSize); ~SeqList() { delete [] elements;} bool Find(int i,T& x) const; int Search(T x) const; bool Insert(int i,T x); bool Delete(int i); ………… private:// 私有数据 int maxLength; // 顺序表的最大长度 T *elements; // 动态一维数组的指针}; 顺序表插入算法 Insert(i,x) :在表中下标为 i 的元素 a i 后插入 x。若 i=-1 ,则将新元素 x 插在最前面。若插入成功,返回 true ; 顺序表删除算法 Delete(i) : 删除元素 a i。