C增量之数据结构与算法.ppt

《C增量之数据结构与算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、封面数据结构与算法姜学锋西北工业大学计算机学院参考教材：清华大学《数据结构》1.1概述算法+数据结构=程序设计—N.Wirth1.1.1基本概念和术语数据（data)客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(dataelement)数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象（dataobject)性质相同的数据元素的集合，是数据的一个子集。数据结构（datastr

2、ucture)相互之间存在一种或多种特定关系的数据元素的集合.数据元素之间的关系称为结构，通常有四类基本结构.集合线性结构树形结构图状结构1.1.1基本概念和术语1.1.1基本概念和术语数据的逻辑结构抽象地描述数据元素逻辑关系。数据的物理结构（存储结构）数据结构在计算机中的表示。102030102030^顺序映像用相对位置表示数据元素间的逻辑关系非顺序映像用指针表示数据元素间的逻辑关系D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)}D={1,2,3}

3、R={<1,2>,<2,3>,<3,2>,<1,3>}例1:英文26个字母表的数据结构是一个线形表，可表示为:B={D,R}D={a,b,c,·······，x,y,z}R={(a,b),(b,c),……，(y,z)}此例数据元素是简单项。1.数据的逻辑结构2.数据的存储结构3.数据的运算：检索、排序、插入、删除、修改等。A.线性结构B.非线性结构A.顺序存储B.链式存储线性表栈队树形结构图形结构数据结构的三个方面反映数据元素之间的逻辑关系数据元素在计算机内部的组织方式1.1.2算法描述算法（alg

4、orithm)对特定问题求解步骤的一种描述，它是指令的有限序列。算法的特性有穷性、确定性、可行性、输入、输出。算法设计的要求正确性、可读性、健壮性、效率。1.1.2算法描述算法的时间复杂度:以算法中基本操作重复执行的次数作为算法的时间度量。例2:(a)x=x+1;O(1)(b)for(i=0;i

5、逻辑结构线性表由n(n≥0)个数据元素a1,a2,...,an构成的有限序列记作:L＝(a1,a2,...,an)其中，a1称为首元素，an称为尾元素。表的长度(表长)线性表中数据元素的数目。空表不含数据元素的线性表(n=0)。一、线性表的逻辑结构线性表(a1,a2,...,an)的特征:直接前驱ai－1在ai之前，称ai－1是ai的直接前驱(1＜i≤n)直接后继ai＋1在ai之后，称ai＋1是ai的直接后继(1≤i＜n)a1没有前驱an没有后继。ai(1＜i＜n)有且仅有一个直接前驱和一个直接后继

6、一、线性表的逻辑结构线性表L＝(a1,a2,...,an)的运算1)initiate(L)初始化L为空表2)length(L)求长度3)get(L,i)取元素ai4)prior(L,elm)求前驱函数5）next(L,elm)求后继函数6）locate(L,x)定位函数7）insert(L,i,x)在元素ai之前插入新元素ｘ8)delete(L,i)删除第i个数据元素9)empty(L)判空表函数10)clear(L)表置空函数二、线性表的顺序存储结构序号存储状态存储地址┌──┐b1│a1│├──┤

7、b+k2│a2│..├──┤..│....│.├──┤b+(i-1)*ki│ai│├──┤│....│├──┤b+(n-1)*kn│an│├──┤│////│├──┤b+(maxlen-1)*kmaxlen│////│└──┘其中:b:表的首地址(基地址),即元素a1的首地址;K:每个数据元素占有的存储单元的个数;Maxlen:线性表的最大长度,为某个常数。二、线性表的顺序存储结构插入一个元素┌─┬─┬─┬─┬─┬─┬─┬─┬─┐│2│4│17│20│25│35│40│││└─┴─┴─┴─┴─┴─┴

8、─┴─┴─┘123456789

9、

10、插入8n┌─┬─┬─┬─┬─┬─┬─┬─┬─┐│2│4││17│20│25│35│40││└─┴─┴─┴─┴─┴─┴─┴─┴─┘123456789

11、

12、插入8n┌─┬─┬─┬─┬─┬─┬─┬─┬─┐│2│4│8│17│20│25│35│40││└─┴─┴─┴─┴─┴─┴─┴─┴─┘123456789

13、

14、插入8之后n二、线性表的顺序存储结构算法分析假设在线性表的第ｊ个位置插入一个元素的概率为Pj，ｎ是线性表的长度,1≤ｊ≤n,那么每插入一