等级考基础数据结构

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

1、等级考基础《数据结构与算法》东华大学计算机学院孙莉2012年2月12日1.1数据结构的研究对象数据结构的研究内容：非数值数据之间的结构关系，及如何表示，如何存储，如何处理。归纳为三部分：逻辑结构、存储结构和运算集合。按某种逻辑关系把一批数据组织起来，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义一个运算的集合。逻辑结构是数据结构的抽象，存储结构是数据结构的实现存储结构的二种类型:顺序存储结构—通过在存储器中的相对位置，表示数据的逻辑结构。非顺序存储结构（链式存储结构）--由指针表示数据

2、间的逻辑关系。1.3常用的数据结构(1)线性结构：结构中的数据元素之间存在着一对一的线性关系。线性表、栈、队、字符串、数组(2)树形结构：结构中的数据元素之间存在着一对多的层次关系。---非线性结构(3)图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。---非线性结构1．4算法与算法分析1.4算法与算法分析一算法的概念算法是对特定问题求解步骤的一种描述算法的基本特征：1）可行性：组成算法的操作必须能够在计算机上实现。2）确定性：算法的每一步操作必须清晰无二义性。3）有穷性：算法必须在

3、有限步内结束；4）有足够的情报：0个或多个输入；1个或多个输出；算法描述的方法很多，如自然语言、框图、类C等例:求两个正整数m，n中的最大数MAX的算法（1）若m>n则max=m（2）若m<=n则max=n1、正确性：(1)没有语法错误；(2)对于几组输入数据能够得出满足要求的结果；(3)对于精心选择的典型而苛刻的几组输入数据能够得到满足要求的结果。(4)对于一切合法的输入数据都能产生满足要求的结果。2、可读性：便于阅读、理解、调试、修改；3、健壮性：对不合法的输入能作出正确的反映与处理；4、高效性：

4、执行时间短（时间复杂度）、需求存储空间省（空间复杂度）评价算法标准1时间复杂度T（n）以求解问题的基本操作的执行次数作为算法时间的度量。1．4算法与算法分析O（n3）称为矩阵相乘算法时间复杂度；O（n3）表示矩阵相乘算法执行时间与n3成正比,即O（n3）与n3同一数量级；例n阶矩阵相乘的算法For(i=1;i<=n;i++)For(j=1;j<=n;j++){c[i][j]=0;For(k=1;k<=n;k++)c[i][j]+=a[i][k]*b[k][j]}乘法加法执行次数均为n3矩阵相乘的基

5、本运算：乘法加法；数据结构中常用的时间复杂度频率计数有7个：O(1)常数型O(n)线性型O(n2)平方型O(n3)立方型O(2n)指数型O(log2n)对数型O(nlog2n)二维型1．4算法与算法分析2算法空间复杂度用执行算法所需的内存空间的大小作为算法所需空间的度量。设执行算法所需的内存空间是问题规模n的某个函数g(n),则算法空间复杂度记作：S（n）=O(g(n))表示算法所需空间的增长率与g(n)的增长率相同例计算解法1先计算x的幂,存于power[]中,再分别乘以相应的系数#defi

6、neN100floatevaluate(floatcoef[],floatx,intn){floatpower[N],f;inti;for(power[0]=1,i=1;i<=n;i++)power[i]=x*power[i-1];for(f=0,i=0;i<=N;i++)f=f+coef[i]*power[i];return(f);}问题规模为n,算法时间复杂度:O(n)空间复杂度：O(N)线性表线性表是最简单、最常用的数据结构。栈、队列、串是特殊的线性表，数组和广义表是线性表的扩展--线性结构线性

7、表是n个数据元素的有限序列，通常记作（a1,a2,a3,…,an）。姓名电话号码蔡颖63214444陈红63217777刘建平63216666王小林63218888张力63215555...2.1线性表的概念例、英文字母表（A,B,C,D,EZ）。某单位的电话号码簿。一线性表的逻辑结构2.1线性表的概念设A=（a1,a2,...,ai-1,ai,ai+1,…,an）是一线性表，1）同一线性表中的元素必须是同一类型的；2）在表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的前件，ai+1是

8、ai的后件；3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个前件，有且仅有一个后件；4）线性表中元素的个数n称为线性表的长度，n=0时称为空表；用一组连续的内存单元依次存放线性表的数据元素。a1a2ai-1aiai+1an线性表（a1,a2,a3,...an）的顺序存储结构用顺序存储结构存储的线性表——称为顺序表2.2线性表的顺序存储和实现一线性表的顺序存储结构2.2线性表的顺序存储和实现说明：元素之间的逻辑关系，通过