数据结构复习资料

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

1、数据关系：在数据对象中各数据元素之间存在着某种关系，这种关系反映了数据对象中数据元素所固有的一种结构。关键字：数据元素中能够起标识作用的数据项。能够起唯一标识作用的关键字称为“主关键字”，反之称为“次关键字”。数据结构：是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍然是原来的结构类型。四种基本结构（逻辑结构）线性结构：该结构中的数据元素之间存在一个对一个的关系。树型结构：该数据结构中数据元

2、素之间存在一个对多个的关系。图状结构或网状结构：该数据结构中数据元素之间存在多个对多个的关系。数据结构的四中存储方式顺序存储结构：把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里，数据元素之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。链式存储结构：不要求逻辑上相邻的数据元素其物理位置相邻，数据元素之间的逻辑关系通过附加的指针字段来表示。由此得到的存储表示称为链式存储结构。索引存储方式：在存储数据元素信息的同时，还建立附加的索引表，索引表中的每一项称为索引项。索引项的一般形式是：（关键字

3、，地址）。关键字是能够唯一标识一个数据元素的数据项。由此得到的存储表示称为索引存储结构。哈希存储方式：根据数据元素的关键字直接计算出该数据元素的存储地址。数据结构的算法分析·算法效率的度量对解决问题的算法进行时间上的度量分析，或对解决同一问题的两种或两种以上算法运行的时间加以比较，这种度量分析称为算法的时间复杂度分析。算法的效率指的是算法的执行时间随“问题规模”的增长而增长的趋势。“规模”指的是输入量的数目。假如随着问题规模n的增长，算法执行时间的增长率和问题规模的增长率相同，则可记为：T(n)=O(f(n)),f(n)为

4、问题规模n的某个函数，T(n)被称为算法的时间复杂度。估算算法的时间复杂度的方法：原操作的执行时间对问题规模来说是常量，则算法的执行时间与原操作执行次数之和成正比。从算法中选取一种对于所研究的问题来说是“基本操作”的原操作，以该“基本操作”在算法中重复执行的次数作为算法时间复杂度的依据。一般来说，都以最坏情况下的时间复杂度作为算法的时间复杂度。·算法的空间需求算法的存储量是指算法执行过程中所需要的最大存储空间。随问题规模n的增长，算法运行时所需要的存储量的增长率和问题规模的增长率相同，则可记为：S(n)=O(g(n)),g

5、(n)为问题规模n的某个函数，S(n)被称为算法的空间复杂度。通常以空间复杂度作为算法所需要的存储空间的度量。估算算法的空间复杂度算法在执行期间所需要的存储量包括以下3个部分：输入数据所占用的空间；——只取决于问题本身，与算法无关程序代码所占用的空间；——对不同算法不会有数量级的差别辅助变量所占用的空间。——随算法的不同而异只需分析辅助变量所占用的空间。一般来说，都以最坏情况下的空间复杂度作为算法的空间复杂度。数据结构的算法分析voidmult_matrix(intc[][],inta[][],intb[][]){for(

6、i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}}两个n*n的矩阵相乘时间复杂度：空间复杂度：#include#definem2voidmult_matrix(intc[][m],inta[][m],intb[][m],intn){inti,j,k;for(i=0;i

7、[j]=c[i][j]+a[i][k]*b[k][j];}}main(){inta1[2][m]={{1,1},{1,1}};intb1[2][m]={{1,1},{1,1}};intc[2][m];inti,j;mult_matrix(c,a1,b1,2);for(i=0;i<2;i++){for(j=0;j<2;j++)printf("%d",c[i][j]);printf("");}}第二章线性表是n(n>=0)个具有相同属性的数据元素的有限序列，表中各个数据元素具有相同的特性。线性数据结构简称线性结构，其特点是

8、：在数据元素的非空有限集合中，（1）存在唯一的一个被称作“第一个”的数据元素。（2）存在唯一的一个被称作“最后一个”的数据元素。（3）除第一个数据元素之外，集合中的每个数据元素均只有一个前驱。（4）除最后一个数据元素之外，集合中的每个数据元素均只有一个后继。/*插入操作的算法实现*/算法思想：一般情况下