数据结构数据结构复习课件.ppt
《数据结构数据结构复习课件.ppt》由会员分享,可在线阅读,更多相关《数据结构数据结构复习课件.ppt(123页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数数据据结结构构武汉大学测绘学院武汉大学测绘学院&数据结构定义数据结构定义1-是相互之间存在一种或多种特定关系的数据元素的集合。据结构定义据结构定义2-按某种逻辑关系按某种逻辑关系组织起来的一批数据(或称带结构的数据元素的集合)应用计算机语言并按一定的存储表示按一定的存储表示 方式方式把它们存储在计算机的存储器中,并在其上定义了一个运算在其上定义了一个运算的集合。的集合。数据结构包含三个方面的内容,即数据的逻辑结构,数据的存贮结构和对数据所施加的运算(操作)。数数据据结结构构武汉大学测绘学院武汉大学测绘学院&逻辑结构逻辑结构-划分方法划分方法&一、集合 结构中的数据元素除了同属于一种类型外,别
2、无其它关系。二、线性结构 结构中的数据元素之间存在一对一的关系。三、树型结构 结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。a1a2a3a4数数据据结结构构武汉大学测绘学院武汉大学测绘学院存储结构分为:顺序存储结构借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针表示数据 元素间的逻辑关系数数据据结结构构武汉大学测绘学院武汉大学测绘学院数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构数据的运算:检索、排序、插入、删除、修改等数据的运算:检索、排序、插入、删除、修改等线性结构线性结构非线性结
3、构非线性结构顺序存储顺序存储链式存储链式存储线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面:数据结构的三个方面:数数据据结结构构武汉大学测绘学院武汉大学测绘学院数数据据结结构构武汉大学测绘学院武汉大学测绘学院1.4 算法和算法分析算法和算法分析一、算法的概念和描述:一、算法的概念和描述:1、什么是算法?、什么是算法?是对特定问题求解步骤的一种描述,算法是指令的有限序列,其中每一条指令表示一个或多个操作。N.Wirth:算法:算法+数据结构数据结构=程序程序程序就是在数据的某特定的表示方式(结构)的基础上对抽象算法的具体表述。Turing 1936 第一个系统地提出 算法
4、思想算法思想算法思想算法思想 (Turing Machine)(Turing Machine)数数据据结结构构武汉大学测绘学院武汉大学测绘学院2、算法描述算法具有以下五个特性:1)有穷性 一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。2)确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。3)可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。4)输入 一个算法有零个或多个输入,这些输入取自于某个特定的对象集合。5)输出 一个算法有一个或多个输出,这些输出是同输入有着某些特定关系的量。数数据据结结构构
5、武汉大学测绘学院武汉大学测绘学院算法设计的要求:评价一个好的算法有以下几个标准:(1)正确性(Correctness)算法应满足具体问题的需求。(2)可读性(Readability)算法应该好读。以有利于阅读者对程序的理解,便于调试和修改。(3)健状性(Robustness)算法应具有容错处理。当输入非法数据时,算法应对其作出反应,而不是产生莫名其妙的输出结果。(4)效率与存储量需求 效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大存储空间。一般,这两者与问题的规模有关。数数据据结结构构武汉大学测绘学院武汉大学测绘学院数数据据结结构构武汉大学测绘学院武汉大学测绘学院2、时间复杂
6、度、时间复杂度在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。为此,我们引入时间复杂度概念。一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=(f(n),称(f(n)为算法的渐近时间复杂度渐近时间复杂度,简称时间复杂度。例如,若T(n)=n(n+1)/2,则有 1/4T(n)/n21,故它的时间复杂度为(n2),即(n)与n2 数量级相同。数数据据结结构构武汉大学测绘学院武汉大学测
7、绘学院 四、空间复杂度空间复杂度 与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:l S(n)=O(f(n)l 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似,不再赘述。数数据据结结构构武武汉汉大大学学测测绘绘学学院院虞晖虞晖数数据据结结构构武武汉汉大大学学测测绘绘学学院院虞晖虞晖顺序存储方法:顺序存储方法:用一组地址连续的存储单元依次存储线用一组地址连续的存储单元依次存储线性表的元素,可通过数组来实现。性表的元素,可通过数组来实现。顺序表的特点是以元素在计算机内物理位置相邻来表示顺序表的特点是以元素在计算机内物理位置相邻来表示
8、线性表中数据元素之间的逻辑关系线性表中数据元素之间的逻辑关系数数据据结结构构武武汉汉大大学学测测绘绘学学院院虞晖虞晖数数据据结结构构武汉大学测绘学院虞晖武汉大学测绘学院虞晖3.4 3.4 队列队列3.4.1 3.4.1 抽象数据类型队列的定义抽象数据类型队列的定义 队列队列队列队列(Queue(Queue(Queue(Queue)也是一种运算受限的线性表。它只允许在也是一种运算受限的线性表。它只允许在表的一端进行插入,而在另一端进行删除。允许删除的表的一端进行插入,而在另一端进行删除。允许删除的一端称为一端称为队头队头队头队头(front(front(front(front),允许插入的一端称
9、为,允许插入的一端称为队尾队尾队尾队尾(rear)(rear)(rear)(rear)。数数据据结结构构武汉大学测绘学院虞晖武汉大学测绘学院虞晖n队空:队空:Q.front=Q.rearn队满:队满:Q.rear=maxsize(假溢出)(假溢出)求队长:求队长:Q.rear-Q.frontn入队:新元素按入队:新元素按 rear指示位置加入,再指示位置加入,再将队尾指针加一将队尾指针加一,即,即rear=rear+1n出队:将出队:将front指示的元素取出,再将队指示的元素取出,再将队头指针加一,即头指针加一,即front=front+1,非循环队列非循环队列数数据据结结构构武汉大学测绘学
10、院虞晖武汉大学测绘学院虞晖数数据据结结构构测测绘绘学学院院3.1 栈(栈(stack)一、一、栈的定义:限定仅在栈的定义:限定仅在表尾表尾进行插入或删除操进行插入或删除操作的线性表,表尾作的线性表,表尾栈顶栈顶,表头,表头栈底栈底,不含元,不含元素的空表称空栈素的空表称空栈特点:先进后出(特点:先进后出(FILO)或后进先出)或后进先出(LIFO)ana1a2.栈底栈底栈栈顶顶.出栈出栈进栈进栈栈栈s=(a1,a2,an)数数据据结结构构测测绘绘学学院院栈的特点栈的特点根据栈的定义可知,最先放入栈中元素在栈底,根据栈的定义可知,最先放入栈中元素在栈底,最后放入的元素在栈顶,而删除元素刚好相反,
11、最后放入的元素在栈顶,而删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后最后放入的元素最先删除,最先放入的元素最后删除。删除。也也就就是是说说,栈栈是是一一种种后后进进先先出出(LastInFirstOut)的线性表,简称为的线性表,简称为LIFO表。表。stack数数据据结结构构测测绘绘学学院院 设设S S是是SeqStackSeqStack类型的指针变量。若栈底位置在向类型的指针变量。若栈底位置在向量的低端,即量的低端,即s sdata0data0是栈底元素,那么栈顶指是栈底元素,那么栈顶指针针s stoptop是正向增加的,即进栈时需将是正向增加的,即进栈时需将s stopt
12、op加加1 1,退栈时需将,退栈时需将s stop top 减减1 1。因此,因此,s stop=0top=0表示空栈,表示空栈,s stop top=stacksize=stacksize表示栈满。当栈满时再做进栈运算必定产表示栈满。当栈满时再做进栈运算必定产生空间溢出,简称生空间溢出,简称“上溢上溢”;当栈空时再做退栈运算当栈空时再做退栈运算也将产生溢出,简称也将产生溢出,简称“下溢下溢”。上溢是一种出错状态,。上溢是一种出错状态,应该设法避免之;下溢则可能是正常现象,因为栈在应该设法避免之;下溢则可能是正常现象,因为栈在程序中使用时,其初态或终态都是空栈,所以下溢常程序中使用时,其初态或
13、终态都是空栈,所以下溢常常用来作为程序控制转移的条件。常用来作为程序控制转移的条件。数数据据结结构构武汉大学测绘学院虞晖武汉大学测绘学院虞晖讨论(代本章小结)线性表、栈与队的异同点线性表、栈与队的异同点相相同同点点:逻逻辑辑结结构构相相同同,都都是是线线性性的的;都都可可以以用用顺顺序序存存储储或或链链表表存存储储;栈栈和和队队列列是是两两种种特特殊殊的的线线性性表表,即即受受限的线性表限的线性表(只是对插入、删除运算加以限制)。(只是对插入、删除运算加以限制)。不同点:不同点:运运算算规规则则不不同同,线线性性表表为为随随机机存存取取,而而栈栈是是只只允允许许在在一一端端进进行行插插入入和和
14、删删除除运运算算,因因而而是是后后进进先先出出表表LIFOLIFO;队队列列是是只只允允许许在在一一端端进进行行插插入入、另另一一端端进进行行删删除除运运算,因而是先进先出表算,因而是先进先出表FIFOFIFO。用途不同,线性表比较通用;堆栈用于函数调用、用途不同,线性表比较通用;堆栈用于函数调用、递归和简化设计等;队列用于离散事件模拟、多道作递归和简化设计等;队列用于离散事件模拟、多道作业处理和简化设计等。业处理和简化设计等。数数据据结结构构武汉大学测绘学院武汉大学测绘学院虞晖虞晖 5.2 5.2 数组的顺序表示和实现数组的顺序表示和实现 由于计算机的内存结构是一维的,因此用一由于计算机的内
15、存结构是一维的,因此用一维内存来表示多维数组,就必须按某种次序将维内存来表示多维数组,就必须按某种次序将数组元素排成一列序列,然后将这个线性序列数组元素排成一列序列,然后将这个线性序列存放在存储器中。存放在存储器中。又由于对数组一般不做插入和删除操作,也又由于对数组一般不做插入和删除操作,也就是说,数组一旦建立,结构中的元素个数和就是说,数组一旦建立,结构中的元素个数和元素间的关系就不再发生变化。因此,一般都元素间的关系就不再发生变化。因此,一般都是采用顺序存储的方法来表示数组。是采用顺序存储的方法来表示数组。数数据据结结构构武汉大学测绘学院武汉大学测绘学院虞晖虞晖数数据据结结构构武汉大学测绘
16、学院武汉大学测绘学院虞晖虞晖广义表广义表LS=(1,2,n)的结构特点的结构特点:1)广义表中的数据元素有相对次序次序;2)广义表的长度长度定义为最外层包含元素个数;3)广义表的深度深度定义为所含括弧的重数;注意:“原子”的深度为 0 “空表”的深度为 1数数据据结结构构武汉大学测绘学院武汉大学测绘学院虞晖虞晖5.5 广义表的存储结构广义表的存储结构由于广义表的元素类型不一定相同,因此,难以用顺由于广义表的元素类型不一定相同,因此,难以用顺序结构存储表中元素,通常采用链接存储方法来存储序结构存储表中元素,通常采用链接存储方法来存储广义表中元素,并称之为广义链表。有广义表中元素,并称之为广义链表
17、。有2种结点形式种结点形式表结点表结点:原子结点:原子结点:tag=1hptptag=0data数数据据结结构构武汉大学测绘学院武汉大学测绘学院虞晖虞晖广义表从结构上可以分解成广义表广义表 =表头表头 +表尾表尾 或者或者广义表广义表 =子表子表1+子表子表2+子表子表n 因此常利用分治法求解之。算法设计中的关键问题是,如何将如何将 l 个子问题的解组合成原问题的解。个子问题的解组合成原问题的解。数数据据结结构构武汉大学测绘学院武汉大学测绘学院虞晖虞晖数数据据结结构构武汉大学测绘学院武汉大学测绘学院虞晖虞晖int GlistDepth(Glist L)/返回指针L所指的广义表的深度for(ma
18、x=0,pp=L;pp;pp=pp-ptr.tp)dep=GlistDepth(pp-ptr.hp);if(dep max)max=dep;return max+1;/GlistDepthif(!L)return 1;if(L-tag=ATOM)return 0;数数据据结结构构武汉大学测绘学院武汉大学测绘学院虞晖虞晖111L for(max=0,pp=L;pp;pp=pp-ptr.tp)dep=GlistDepth(pp-ptr.hp);if(dep max)max=dep;例如例如:pppp-ptr.hppppppp-ptr.hppp-ptr.hp数 据 结 构 测 绘 学 院数 据 结
19、构 测 绘 学 院Root(T)/求树的根结点 查找类:Value(T,cur_e)/求当前结点的元素值 Parent(T,cur_e)/求当前结点的双亲结点 LeftChild(T,cur_e)/求当前结点的最左孩子 RightSibling(T,cur_e)/求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树 TreeDepth(T)/求树的深度TraverseTree(T,Visit()/遍历数 据 结 构 测 绘 学 院InitTree(&T)/初始化置空树 插入类:CreateTree(&T,definition)/按定义构造树Assign(T,cur_e,value)/给
20、当前结点赋值InsertChild(&T,&p,i,c)/将以c为根的树插入为结点p的第i棵子树数 据 结 构 测 绘 学 院ClearTree(&T)/将树清空 删除类:DestroyTree(&T)/销毁树的结构DeleteChild(&T,&p,i)/删除结点p的第i棵子树数 据 结 构 测 绘 学 院基本术语基本术语结点结点(node)表示树中的元素,包括数据项及若干表示树中的元素,包括数据项及若干指向其子树的分支指向其子树的分支结点的度结点的度(degree)结点拥有的子树数结点拥有的子树数叶子叶子(leaf)度为度为0的结点的结点孩子孩子(child)结点子树的根称为该结点的孩子结
21、点子树的根称为该结点的孩子双亲双亲(parents)孩子结点的上层结点叫该结点的双孩子结点的上层结点叫该结点的双亲亲兄弟兄弟(sibling)同一双亲的孩子同一双亲的孩子树的度树的度一棵树中最大的结点度数一棵树中最大的结点度数结点的层次结点的层次(level)从根结点算起,根为第一层,从根结点算起,根为第一层,它的孩子为第二层它的孩子为第二层深度深度(depth)树中结点的最大层次数树中结点的最大层次数数 据 结 构 测 绘 学 院ABCDEFGHIJKLM结点A的度:3结点B的度:2结点M的度:0叶子:K,L,F,G,M,I,J结点A的孩子:B,C,D结点B的孩子:E,F结点I的双亲:D结点
22、L的双亲:E结点B,C,D为兄弟结点K,L为兄弟树的度:3结点A的层次:1结点M的层次:4树的深度:4结点F,G为堂兄弟结点A是结点F,G的祖先数 据 结 构 测 绘 学 院任何一棵非空树是一个二元组任何一棵非空树是一个二元组 Tree=(root,F)其中:其中:root被称为根结点被称为根结点F被称为子树森林被称为子树森林森林:是是m(m0)棵互)棵互不相交的树的集合不相交的树的集合ArootBCDEFGHIJMKLF数 据 结 构 测 绘 学 院任何一棵非空树是一个二元组任何一棵非空树是一个二元组 Tree=(root,F)其中:其中:root被称为根结点被称为根结点F被称为子树森林被称
23、为子树森林森林:是是m(m0)棵互)棵互不相交的树的集合不相交的树的集合ArootBCDEFGHIJMKLF数 据 结 构 测 绘 学 院几种特殊形式的二叉树几种特殊形式的二叉树满二叉树满二叉树定义:定义:特点:每一层上的结点数都是最大结点数完全二叉树定义:深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为特点叶子结点只可能在层次最大的两层上出现对任一结点,若其右分支下子孙的最大层次为L,则其左分支下子孙的最大层次必为L 或L+1数 据 结 构 测 绘 学 院实现:按满二叉树的结点层次编号,依次存放二叉树实现:按满二叉树的结点层次编号,依
24、次存放二叉树中的数据元素中的数据元素特点:特点:结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中浪费空间,适于存满二叉树和完全二叉树浪费空间,适于存满二叉树和完全二叉树abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11数 据 结 构 测 绘 学 院ADEBCFrootlchilddatarchild结点结构:1.二叉链表数 据 结 构 测 绘 学 院ADEBCFroot2三叉链表parent lchild data rchild结点结构:数 据 结 构 测 绘 学 院void preorder(JD*bt)if(bt!=NULL)p
25、rintf(%dt,bt-data);preorder(bt-lchild);preorder(bt-rchild);主程序Pre(T)返回返回返回返回pre(TR);返回返回返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回返回T左是空返回左是空返回pre(TR);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(TR);先序序列:先序序列:ABDC数 据 结 构 测 绘 学 院1)先序遍历递归
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习 课件
限制150内