数据结构数据结构复习课件.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）先序遍历递归

26、算法）先序遍历递归算法 void PreOrder(BTree BT)if(BT)Visit(BT);PreOrder(BT-Lchild);PreOrder(BT-Rchild);数 据 结 构 测 绘 学 院（2）中序遍历递归算法）中序遍历递归算法void InOrder(BTree BT)if(BT)InOrder(BT-Lchild);Visit(BT);InOrder(BT-Rchild);数 据 结 构 测 绘 学 院（3）后序遍历递归算法）后序遍历递归算法void PostOrder(BTree BT)if(BT)PostOrder(BT-Lchild);PostOrder(BT

27、-Rchild);Visit(BT);数 据 结 构 测 绘 学 院将树转换成二叉树加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转45ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空数 据 结 构 测 绘 学 院将二叉树转换成树加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构ABCDEFGHIABCDEFG

28、HIABCDEFGHIABCDEFGHIABCDEFGHI数 据 结 构 测 绘 学 院森林转换成二叉树森林转换成二叉树将各棵树分别转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构心，顺时针旋转，构成二叉树型结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ数 据 结 构 测 绘 学 院二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原

29、：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ数 据 结 构 测 绘 学 院3树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为wpl=，其中n 为叶子结点数目，wi为第i 个叶子结点的权值，li 为第i 个叶子结点的路径长度。二、构造赫夫曼树1赫夫曼树的定义设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫赫夫曼树。数 据 结 构 测 绘 学 院 在远程通讯中，要将待传字符转换成由二进制组成的字符串：设要传送的字符为：ABACCDA若编码为：A00 B01

30、 C10 D-11 若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。100三、赫夫曼树的应用2(赫夫曼编码)数 据 结 构 测 绘 学 院例：已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。W（权）=2，4，2，3，3，叶子结点个数n=5 148464220001113301构造的Huffman树 T B A C S数 据 结 构 测 绘 学 院由Huffman树得Huffman编码为：T B A C S00 01 10 110 1111484642

31、20001113301 T B A C S出现频率越大的字符，其Huffman编码越短。数 据 结 构 测 绘 学 院设要传送的字符为：ABACCDA若编码为：A0 B00 C1 D-01问题:A 是B,D编码的前缀,有重码!关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀。这种编码称作前缀编码。ABACCDA 000011010但：0000AAAA ABA BB重码数 据 结 构 测 绘 学 院设要传送的字符为：ABACCDA若编码为：A0 B110 C10 D-111 10ACBD000111采用二叉树设计二进制前缀编码规定：左分支用“0”表示；右分支用“1”

32、表示赫夫曼编码数 据 结 构 测 绘 学 院译码过程：分解接收字符串：遇“0”向左，遇“1”向右；一旦到达叶子结点，则译出一个字符，反复由根出发，直到译码完成。10ACBD000111ABACCDA数 据 结 构 测 绘 学 院求Huffman编码：由叶子根，若：（1）从左分支下去，则分支为“0”；（2）从右分支下去，则分支为“1”。ACBD000111数数据据结结构构测测绘绘学学院院7.1图的基本概念图的基本概念7.1.1图的定义图的定义 图图G是由顶点集是由顶点集V和顶点间的关系集合和顶点间的关系集合E（边的集合）组成的一种数据结构，可以用二（边的集合）组成的一种数据结构，可以用二元组定义

33、为：元组定义为：G=（V,E）数数据据结结构构测测绘绘学学院院7.1.2图的基本术语图的基本术语1.有向图和无向图有向图和无向图在在图图中中，若若用用箭箭头头标标明明了了边边是是有有方方向向性性的的，则则称称这这样样的的图图为为有有向向图图，否否则则称称为为无无向向图图。如如图图7-1中中，G1为无向图，为无向图，G2为有向图。为有向图。在无向图中，一条边（在无向图中，一条边（x,y）与（）与（y,x）表示的结果）表示的结果相同，用圆括号表示，在有向图中，一条边相同，用圆括号表示，在有向图中，一条边与与表示的结果不相同，故用尖括号表示。表示的结果不相同，故用尖括号表示。表表示从顶点示从顶点x发

34、向顶点发向顶点y的边，的边，x为始点，为始点，y为终点。有向为终点。有向边也称为弧，边也称为弧，x为弧尾，为弧尾，y为弧头为弧头,则则表示为一条表示为一条弧弧,而而表示表示y为弧尾，为弧尾，x为弧头的另一条弧为弧头的另一条弧。数数据据结结构构测测绘绘学学院院7.2.1邻接矩阵邻接矩阵1图的邻接矩阵表示图的邻接矩阵表示(数组表示法数组表示法)在在邻邻接接矩矩阵阵表表示示中中，除除了了存存放放顶顶点点本本身身信信息息外外，还还用用一一个个矩矩阵阵表表示示各各个个顶顶点点之之间间的的关关系系。若若（i,j）E(G)或或i,j E(G),则则矩矩阵阵中中第第i行行第第j列列元素值为元素值为1，否则为，

35、否则为0。图的邻接矩阵定义为：图的邻接矩阵定义为：1 若若（i,j）E(G)或或i,j E(G)Aij=0其它情形其它情形数数据据结结构构测测绘绘学学院院7.2.2邻接表邻接表1图的邻接表表示图的邻接表表示图的邻接表存储方法是一种顺序分配与链式分配图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法，它包括两部分：一部分是单链表，相结合的存储方法，它包括两部分：一部分是单链表，用来存放边的信息；另一部分是数组，主要用来存放用来存放边的信息；另一部分是数组，主要用来存放顶点本身的数据信息。顶点本身的数据信息。adjvexweightnext边结点边结点顶点结点顶点结点数数据据结结构构测测绘

36、绘学学院院邻接表的邻接表的缺点：缺点：邻接表的邻接表的优点：优点：空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵两结点对应的单链表，没有邻接矩阵方便。方便。数数据据结结构构测测绘绘学学院院讨论：邻接表与邻接矩阵有什么异同之处？1.1.联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2.2.区别：区别：对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定

37、的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。与顶点编号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)O(n+e)。3.3.用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-n(n-1)/2)1)/2)；而邻接表多用于稀疏图的存储（；而邻接表多用于稀疏图的存储（enen2 2)数数据据结结构构测测绘绘学学院院7.3.1深度优先搜索遍历深度优先搜索遍历1深度优先搜索思想深度优先搜

38、索思想深深度度优优先先搜搜索索遍遍历历类类似似于于树树的的先先序序遍遍历历。假假定定给给定定图图G的的初初态态是是所所有有顶顶点点均均未未被被访访问问过过，在在G中中任任选选一一个个顶顶点点i作作为为遍遍历历的的初初始始点点，则则深深度度优优先先搜搜索索遍遍历历可可定定义义如如下：下：(1)首先访问顶点首先访问顶点i，并将访问标记置为，并将访问标记置为visitedi=1；(2)然然后后搜搜索索与与顶顶点点i有有边边相相连连的的下下一一个个顶顶点点j，若若j未未被被访访问问过过，则则访访问问它它，将将j的的访访问问标标记记置置为为，visitedj=1，然然后后从从j开开始始重重复复此此过过程

39、程，若若j已已访访问问，再再看看与与i有有边边相连的其它顶点；相连的其它顶点；(3)若若与与i有有边边相相连连的的顶顶点点都都被被访访问问过过，则则退退回回到到前前一一个个访访问问顶顶点点重重复复刚刚才才过过程程，直直到到图图中中所所有有顶顶点点都都被被访访问完为止。问完为止。数数据据结结构构测测绘绘学学院院8.3.2广度优先搜索遍历广度优先搜索遍历1广度优先搜索的思想广度优先搜索的思想广广度度优优先先搜搜索索遍遍历历类类似似于于树树的的按按层层次次遍遍历历。设设图图G的的初初态态是是所所有有顶顶点点均均未未访访问问，在在G中中任任选选一一顶顶点点i作作为为初初始始点，则广度优先搜索的基本思想

40、是：点，则广度优先搜索的基本思想是：(1)首首先先访访问问顶顶点点i，并并将将其其访访问问标标志志置置为为visitedi=1；(2)接接着着依依次次访访问问与与顶顶点点i有有边边相相连连的的所所有有顶顶点点W1，W2，Wt；(3)然然后后再再按按顺顺序序访访问问与与W1，W2，Wt有有边边相相连连又又未曾访问过的顶点；未曾访问过的顶点；依此类推，直到图中所有顶点都被访问完为止依此类推，直到图中所有顶点都被访问完为止。数数据据结结构构测测绘绘学学院院下面将介绍求最小生成树普里姆算法下面仅讨论无向网的最小生成树问题。普里姆方法的思想是：在图中任取一个顶点K作为开始点，令U=k，W=V-U，其中V

41、为图中所有顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离,使之保持最小，再重复此过程，直到W为空集止。求解过程参见图8-20。数数据据结结构构测测绘绘学学院院2.2.求最小生成树求最小生成树首先明确：首先明确：使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。可能得到不同的生成树。按照生成树的定义，按照生成树的定义，n n 个顶点的个顶点的连通

42、网络连通网络的生成树有的生成树有 n n 个顶点、个顶点、n-n-1 1 条边。条边。即有权图即有权图目标：目标：在网络的多个生成树中，寻找一个在网络的多个生成树中，寻找一个各边权值之和最小各边权值之和最小的生成树。的生成树。构造最小生成树的准则构造最小生成树的准则v必须只使用该网络中的必须只使用该网络中的边边来构造最小生成树；来构造最小生成树；v必须使用且仅使用必须使用且仅使用n n-1-1条边条边来联结网络中的来联结网络中的n n个顶点；个顶点；v不能使用产生回路的边。不能使用产生回路的边。数数据据结结构构测测绘绘学学院院欲在欲在n n个城市间建立通信网，则个城市间建立通信网，则n n个城

43、市应铺个城市应铺n-1n-1条线路；但因为每条线路都条线路；但因为每条线路都会有对应的经济成本，而会有对应的经济成本，而n n个城市可能有个城市可能有n(n-1)/2 n(n-1)/2 条线路，那么，条线路，那么，如何选择如何选择n n1 1条线路，使总费用最少？条线路，使总费用最少？典型用途：典型用途：数学模型：数学模型：顶点顶点表示城市，有表示城市，有n n个；个；边边表示线路，有表示线路，有n n1 1条；条；边的权值边的权值表示线路的经济代价；表示线路的经济代价；连通网连通网表示表示n n个城市间通信网。个城市间通信网。显然此连通网是一个显然此连通网是一个生成树！生成树！问题抽象：问题

44、抽象：n个顶点的生成树很多，需要从中选一棵个顶点的生成树很多，需要从中选一棵代价最小代价最小的生成树，即该树的生成树，即该树各边的代价之和各边的代价之和最小。此树便称为最小生成树最小。此树便称为最小生成树MST(Minimum cost Spanning Tree)数数据据结结构构测测绘绘学学院院#defineINFINITE 9999#define MAXN 100void prim(int costMAXN,int n,int v)int lowcostMAXN,min,closestMAXN,i,j,k;for(i=1;i=n;i+)lowcosti=costvi;closesti=v;

45、for(i=1;in;i+)min=INFINITE;for(j=1;j=n;j+)if(lowcostj!=0&lowcostjmin)min=lowcostj;k=j;数数据据结结构构测测绘绘学学院院printf(“%d%d%d”,closestk,k,min);lowcostk=0;for(j=1;j=n;j+)if(costkj!=0)&(costkjlowcostj)lowcostj=costkj;closestj=k;分析分析:时间复杂度为O(n2)以顺序表或线性链表表示静态查找表一、顺序查找表顺序查找表ST.elem回顾顺序表的查找过程：回顾顺序表的查找过程：假设给定值 e=64

46、,要求 ST.elemk=e,问:k=?kkint location(SqList L,ElemType&e,Status(*compare)(ElemType,ElemType)k=1;p=L.elem;while(k=L.length&!(*compare)(*p+,e)k+;if(k=L.length)return k;elsereturn 0;/location见书见书25页页ST.elemiST.elemi60ikey=64key=60i64int Search_Seq(SSTable ST,KeyType key)/在顺序表ST中顺序查找其关键字等于 /key的数据元素。若找到，则

47、函数值为 /该元素在表中的位置，否则为0。ST.elem0.key=key;/“哨兵”for(i=ST.length;ST.elemi.key!=key;-i);/从后往前找 return i;/找不到时，i为0/Search_Seq定义：定义：查找算法的平均查找长度平均查找长度(Average Search Length)为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值其中:n 为表长，Pi为查找表中第i个记录的概率，且 ，Ci为找到该记录时，曾和给定值比较过的关键字的个数。分析顺序查找的时间性能在等概率查找的情况下，顺序表查找的平均查找长度为：对顺序表顺序表而言，Ci=

48、n-i+1ASL=nP1+(n-1)P2+2Pn-1+Pn 上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。二、有序查找表二、有序查找表 若以有序表有序表表示静态查找表，则查找过程可以基于“折半折半”进行。ST.elemST.length例如例如:key=64 的查找过程如下：lowhighmidlow mid high midlow 指示查找区间的下界high 指示查找区间的上界mid=(low+high)/2int Search_Bin(SSTable ST,KeyType key)low=1;high=ST.length;/置区间初值 while(low

49、data.key)elseif(LT(key,T-data.key)else p=f;returnFALSE;/查找不成功 p=T;returnTRUE;/查找成功SearchBST(T-lchild,key,T,p);/在左子树中继续查找SearchBST(T-rchild,key,T,p);/在右子树中继续查找但是，对于动态查找表动态查找表而言，因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key)作为关键字为 key 的记录在表中的位置，通常称这个函数 f(key)为哈希函数。1)表长不确定；2)在设计查找表时，只知道关键字所 属范围，而不知道确切的关键

50、字。Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei 例如：对于如下 9 个关键字设设哈希函数哈希函数f(key)=(Ord(第一个字母第一个字母)-Ord(A)+1)/2 ChenZhaoQian SunLiWuHanYeDei问题问题:若添加关键字 Zhou,怎么办？怎么办？能否找到能否找到另一个哈希函数？1)哈希函数是一个映象映象，即：将关键字的集合映射到某个地址集合上，将关键字的集合映射到某个地址集合上，它的设置很灵活灵活，只要这个地址集地址集合的 大小不超出允许范围不超出允许范围即可；从这个例子可见：从这个例子可见：2)由于哈希函数是一个压缩映象压缩映象，因此，