大学计算机基础— Windows 7+Office 2010第09章.ppt

9.3 数据结构基础 3．队列（Queue） 队列是指允许在一端进行插入，而在另一端进行删除的线性表。允许插入的一端称为队尾（Rear），允许删除的一端称为队头（Front）。 “先进先出”（First In First Out，FIFO）或“后进后出”（Last In First Out，LILO）的线性表。 往队列的队尾插入一个元素称为入队操作，从队列的队头删除一个元素称为退队操作。 9.3 数据结构基础 4．字符串（String） 字符串是数据元素类型为字符的线性表。字符串一般表示为“a1a2…ai…an”。 常用的字符串操作有： 连接：将两个字符串首尾相连成一个字符串； 取子串：从一个字符串中取出从某个位置（或某个字符）开始的若干个连续字符； 删除子串：从一个字符串中删除从某位置（或某个字符）开始的若干个连续字符； 插入子串：在一个字符串的某个位置处插入另一个字符串（称为子串）； 求子串位置：在一个字符串中找出首次与另一字符串（子串）相同的起始位置。 9.3 数据结构基础 5．链表 线性表的链式存储结构称为线性链表。线性链表中的第i个存储结点Ai，由数据域A(i)和指针域NEXT(i)两部分组成 单向链表和双向链表的逻辑结构 9.3 数据结构基础 线性链表的基本操作有： 在线性链表中包含指定元素的结点之前插入一个新元素； 在线性链表中删除包含指定元素的结点； 将两个线性链表按要求合并成一个线性链表或将一个线性链表按要求进行分解； 逆转线性链表或者复制线性链表； 线性链表的排序和查找。 9.3 数据结构基础 相关概念： 树（Tree）是n（n≥0）个结点的有限集合。当n=0时，集合为空集，称为空树。当n≠0时，称为非空树， 在任意一棵非空树T中： 有且仅有一个特定的称为根（Root）的结点。 当n1时，除根结点以外的其余结点可分成m（m0）个互不相交的有限集合T1，T2，…，Tm。其中每一个集合本身又是一棵树，并称其为根的子树（Subtree）。 树的递归特性：一棵树是由根及若干棵子树构成的，而子树又可由更小的子树构成。 9.3.3 树形结构 树的结点包括一个数据元素及若干指向其子树的分支。结点拥有的子树个数称为结点的度（Degree）。树中所有结点的度的最大值称为该树的度。度为0的结点称为叶子结点（Leaf）。结点的子树的根称为该结点的孩子结点（Child），该结点是其孩子结点的双亲结点（Parent）。具有同一双亲结点的孩子结点之间互称为兄弟（Sibling）。某结点的祖先是指从根结点到该结点所经分支上的所有结点。以某结点为根的子树中的所有结点都称为该结点的子孙。结点的层次（Level）从根开始算起，根为第一层，根的孩子为第二层，某结点所在的层从根开始向下计算。在树的同一层上而双亲结点不同的结点互为堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度。 9.3 数据结构基础 9.3 数据结构基础 （a）只有树结点的树 （b）一般的树 根结点、度、叶子结点 、双亲结点？ 9.3 数据结构基础 树的一些基本操作： TreeEmpty(T)：判断树T是否为空操作。若T为空树，返回TRUE，否则返回FALSE。 Root(T)：求根操作。返回树T的根结点地址。若T为空树，返回一特殊值。 TreeDepth(T)：求树的深度操作。返回树T的深度。 Value(T,a)：结点a是树T中的结点，函数返回a结点地址。 Parent(T,a)：求a结点的双亲。a是树T中的结点，当a是非根结点时，返回其双亲结点地址。 Child(T,a,i)：求a结点的孩子。a是树T中的结点，函数返回a结点的第i个孩子结点的地址。 Create(T,T1,…,Tk)：建树操作。当k≥1，建立一棵以T为根，以T1，T2，…，Tk为第1，2，…，k棵子树的树。 9.3 数据结构基础 9.3.4 网状结构 图（Graph）是一种较线性表和树更为复杂的非线性数据结构。 常用G=(V,E)代表一个图，其中，V（Vertex）是顶点（结点或者称为数据元素）的有穷（非空）集合；E是边（V中顶点的偶对）的集合。E可以是空集，若E为空，则G中只有顶点没有边。通常，顶点总数记为|V|，边的总数记为|E|，并把边数相对较少的图称为稀疏图，边数相对较多的图称为密集图，把包括所有可能边的图称为完全图。 图中代表一条边的顶点的偶对如果无序（即无方向的），称此图为无向图。 9.3 数据结构基础 有向图G1和无向图G2 边数恰好为n(n-1)/2的无向图称为无向完全图。边数恰好为n(n-1)的有向图称为有向完全图。有时图的边或弧附有相关的数值，这种数值称为权（Weight）。每条边或弧都带权的图又称为网（Network）。