《数据结构》知识点.doc

《《数据结构》知识点.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章绪论1.1数据是表示客观事物的符号，是对客观事物的抽象，是信息的载体。对计算机科学而言，经抽象(数字化)后，能被计算机识别、存储和加工处理的客观事物均称作数据。1.2具有某种共同属性的数据集合称作数据对象。数据集中的元素称作数据元素，简称元素，又称结点、顶点、记录等。数据对象={数据元素，数据元素，…，数据元素}1.3就数据的自身结构而言，分为原子型和结构型，前者是不可分解或无须分解的数据，后者可分解为若干个数据项。1.4通常，数据项是无须分解或不可分解的所谓最小数据单位，数据元素是作为整体对待的

2、基本数据单位。1.5数据集和其上定义的一组操作合称数据类型，即，数据类型=数据集+一组操作=(数据集，一组操作)[了解]狭义地说，数据类型侧重于数据的值，不区分值相同的数据，忽略数据的自身结构。例.复数类=(复数集，运算集)，复数集以复数为基本元素，复数由两个数据项组成：实部和虚部或模和幅角。1.6数据集和其元素间的一组关系合称数据结构，即，数据结构=数据对象+数据关系=(数据对象，数据关系)1.7数据结构的抽象描述称作逻辑结构。逻辑结构分为：①集合结构；②线性结构；③树形结构(简称树结构)；④图形结构

3、(简称图结构)。1.8树结构和图结构统称非线性结构。1.9数据结构在计算机上的具体实现称作存储结构或物理结构。存储结构分为：①顺序存储；②链式存储；③索引存储；④散列存储。1.10数据结构和其上定义的一组操作的抽象描述合称抽象数据类型，即，抽象数据类型=数据结构+基本操作=数据对象+数据关系+基本操作1.11求解问题的步骤称作算法，是合法指令的有限序列，具有以下主要特性：①有穷性；②确定性；③可行性。1.12算法所用的总时间称作时间复杂度，通常用算法中执行次数最多(频度最高)的操作的执行次数(频度)或数

4、量级表示。时间复杂度又称时间效率，但两者的高低是相反的。1.13算法所用最大存储量称作空间复杂度。空间复杂度又称空间效率，但两者的高低是相反的。1.14从数量级上说，算法的时间复杂度和空间复杂度与规模n的某个函数同级。常见数量级由低到高排列如下：1、logan、nk、an、n!、nn(k>0,a>1)对同一个具体问题，数据本身所用存储量与算法无关，通常，空间复杂度只考虑附加存储空间复杂度。1.15算法的性能分析主要包括时间复杂度和空间复杂度。1.16数据元素间的关系分为有序关系和无序关系。有序关系简称弧

5、(或有向弧、有向边)，无序关系简称边(或无向弧、无向边)，分别表为:<前驱，后继>、(元素，元素)或前驱→后继、元素—元素1.17k阶斐波那契序列的定义及其化简式。f0=f1=…=fk-2=0，fk-1=1，n≥k时，fn=fn-1+fn-2+…+fn-k1.18一元多项式的高效计算式。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];第2章线性表2.1同类型元素的有限序

6、列称作线性表。简记为(a1,a2,…,an)或a1,a2,…,an或({ai

7、i=1,2,…,n},{

8、i=1,2,…,n-1})2.2线性表中元素的个数称作表长，表长为0的线性表称作空表。2.3在线性表中，第一个元素称作首元，它没有前驱，其它元素均有唯一前驱；最后一个元素称作尾元，它没有后继，其它元素均有唯一后继。线性表的这种关系称作一对一关系，记作1:1。例.既有首元又有尾元的线性表的表长≥1，某元素既有前驱又有后继的线性表的表长≥3。2.5用连续的一片存储空间依次顺序存放线性表的

9、元素，称作线性表的顺序存储，简称顺序表。顺序表中逻辑相邻者的存储位置也相邻。顺序表有三个要素：①基址；②表长(或尾元下标)；③预留表长(或最大下标)。如果顺序表的预留表长是常量，可用普通数组存储(称作静态顺序表，只有两个要素)，否则，用动态数组存储(称作动态顺序表)。对于顺序表，附加存储空间复杂度为O(1)，插入、删除、查找操作的时间复杂度为O(n)，其它基本操作的时间复杂度均为O(1)。2.6附加“链”将逻辑相邻数据元素的存储位置链接起来的存储结构称作链式存储。链式存储的线性表称作线性链表，简称链表。

10、附加一个链的线性链表称作单链表。习惯上，链域指向其后继。单链表中第一个结点的地址称作头指针。作为线性链表首元的形式前驱的附加结点称作头结点。对于单链表，附加存储空间复杂度为O(n)，初始化操作的时间复杂度为O(1)，其它基本操作的时间复杂度均为O(n)。2.7静态顺序表的具体实现⑴存储结构typedefstruct{//用静态数组存储的顺序表intlast;//尾元下标(表长-1)DataTypedata[MAX];//MAX为最大表长(常