《数据结构》全套教学课件.pptx

;;;;1.1.1数据结构的概念;1.1.1数据结构的概念;;;;;;;;1.2.2算法分析;1.2.2算法分析;;;;;;;;;;;;;;;;;2.2.1顺序表的定义;;;;;;;;;;;2.3.1链表的定义;;;;;;;;;;;;;;;2.3.3循环链表概述;;2.3.4双向链表概述;;;;;;;;;;;;;;;;;;;;;;;;3.1.3链栈;;;3.1.4顺序栈和链栈的比较;3.1.5栈的应用;;;;;;;;;;;;;3.2.4链队列;;;;3.2.5循环队列和链队列的比较;3.2.6队列的应用;;;;;;;;;;;;;;4.1.2串的存储结构;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;5.1.2树结构的逻辑特征;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;6.1.2图的基本术语;6.1.2图的基本术语;;6.1.3图的基本操作;;;;;;;;;6.2.4图的遍历;;;;6.3.2生成树与最小生成树;一个连通图G的极小连通子图T的特点是：

(1)T包含G的所有顶点。

(2)T为连通子图。

(3)T包含的边数最少。

性质1一个有n个顶点的连通图的生成树有且仅有n-1条边。

性质2一个连通图的生成树不唯一。

在一个网中，所有生成树中必有一棵边的权值总和最小的生成树，因此称这棵生成树为最小代价生成树，简称为最小生成树(简称MST)。MST具有以下重要性质：假设G=(V，E)是一个无向连通网，U是顶点集V的一个非空子集，若(u，v)是一条具有最小权值的边，其中u∈U，v∈V-U，则必定存在一棵包含(u，v)的最小生成树。

构造最小生成树的算法有两种：普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。;;;;;;;;;;;;;;;;;;;;;;;;;7.2.1顺序查找;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;