《数据结构》知识点.doc

,是对客观事物的抽象,是信息的载体。对计算机科学而言,经抽象(数字化)后,能被计算机识别、存储和加工处理的客观事物均称作数据。。数据集中的元素称作数据元素,简称元素,又称结点、顶点、记录等。数据对象={数据元素,数据元素,…,数据元素},分为原子型和结构型,前者是不可分解或无须分解的数据,后者可分解为若干个数据项。,数据项是无须分解或不可分解的所谓最小数据单位,数据元素是作为整体对待的基本数据单位。,即,数据类型=数据集+一组操作=(数据集,一组操作)[了解]狭义地说,数据类型侧重于数据的值,不区分值相同的数据,忽略数据的自身结构。=(复数集,运算集),复数集以复数为基本元素,复数由两个数据项组成:实部和虚部或模和幅角。,即,数据结构=数据对象+数据关系=(数据对象,数据关系)。逻辑结构分为:①集合结构;②线性结构;③树形结构(简称树结构);④图形结构(简称图结构)。。。存储结构分为:①顺序存储;②链式存储;③索引存储;④散列存储。,即,抽象数据类型=数据结构+基本操作=数据对象+数据关系+,是合法指令的有限序列,具有以下主要特性:①有穷性;②确定性;③可行性。,通常用算法中执行次数最多(频度最高)的操作的执行次数(频度)或数量级表示。时间复杂度又称时间效率,但两者的高低是相反的。。空间复杂度又称空间效率,但两者的高低是相反的。,算法的时间复杂度和空间复杂度与规模n的某个函数同级。常见数量级由低到高排列如下:1、logan、nk、an、n!、nn(k>0,a>1)对同一个具体问题,数据本身所用存储量与算法无关,通常,空间复杂度只考虑附加存储空间复杂度。。。有序关系简称弧(或有向弧、有向边),无序关系简称边(或无向弧、无向边),分别表为:<前驱,后继>、(元素,元素)或前驱→后继、元素—。f0=f1=…=fk-2=0,fk-1=1,n≥k时,fn=fn-1+fn-2+…+fn-。Pn(x)=p0+p1x+p2x2+…+pnxn=p0+x(p1+x(…Pn-1+xpn…))递推算法为:for(P=p[n],i=n-1;i>=0;i--)(P*=x)+=p[i];。简记为(a1,a2,…,an)或a1,a2,…,an或({ai|i=1,2,…,n},{<ai,ai+1>|i=1,2,…,n-1}),表长为0的线性表称作空表。,第一个元素称作首元,它没有前驱,其