数据结构线性表栈队列叉树图.ppt

常见数据结构 线性表、栈、队列、二叉树、图 （一）、线性表 线性表是n个类型相同的数据元素的有限序列，数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继，如图2.1所示。例如：英文字母表(A,B,…,Z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素， （二）、栈 栈是允许在一端进行插入和删除操作的特殊线性表。 允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动； 栈中元素个数为零时称为空栈。栈结构也称为后进先出表（LIFO）。 三、队列 队列(Queue)的定义 队列是限定仅在表的一端进行插入，在另一端进行删除操作的线性表。 允许插入的一端称为队尾(rear)，允许删除的一端称为队首(front)。 队列的插入操作，称为入队；队列的删除操作，称为出队。当队列中没有元素时称为空队列。 设队列q=(a0，a1，a2，…，an-1)，则a0称为队头元素，an-1称为队尾元素。元素按a0，a1，a2， …，an-1的次序入队，出队也只能按照这个次序。 队列和栈相反，队列的操作是按先进先出（First In First Out）的原则进行的，又称为先进先出的线性表（简称FIFO表）。 介绍基本术语 叶子结点 结点 结点总数 深度 层 前缀、后缀表达式 二叉树的应用。 中缀表达式转换后缀表达式 从左向右扫描表达式、运算数送到输出队列、运算符进栈、如果运算优先级大于栈顶元素直接进栈，如果运算优先级小于或等于栈顶元素，则先弹出栈顶元素，再进栈、左括号直接进栈、右括号则依次弹出栈中的元素，直到遇到第一个左括号为止。 有些题目要求写出前缀、中缀和后缀表达式，做这类题目时，可以先通过优先级画出一棵二叉树再分别利用先根、中根和后根遍历写出对应的序列，就是它们的前缀、中缀和后缀表达式。 表达式a*(b+c)-d的后缀表达式是： A)abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd 假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为 。 一棵二叉树的中序遍历序列为：DGBAECHF，后序遍历序列为：GDBEHFCA，则前序列遍历序列是 __。 数据结构之——图 什么是图 又如，有6个足球队之间进行循环赛，他们比赛的场次可以用图1-3(1)来表示。有3个人相互写信，可以用图1—3(2)来表示。 从上面两个例子可看出，我们这里所说的图(graph)，与人们通常所熟悉的图，如圆、四边形、函数图象等是很不相同的。是指某些具体事物和这些事物之间的联系。如果我们用点来表示事物(如地点、队)，用线段来表示两事物之间的联系，那么一个图就是表示事物的点集和表示事物之间联系的线段集合所构成。其中线段仅表示两点的关系，它的长短与曲直是无关紧要的。例如图1-4中3个图，被认为是同一个图。 图的基本概念 定义：图G定义为一个偶对(V，E)，记作G：(V，E)。其中??? 1)V是一个非空有限集合，它的元素称为顶点；??? 2)E也是一个集合，它的元素称为边??? 例如图1-4中的图有4个顶点，4条边。??? 或者定义：图G（Graph）是由顶点的集合V和边的集合E所组成的二元组，记作：G =（V，E） 其中V是顶点的集合，E是边的集合。 顶点的度：与顶点关联的边的数目，有向图顶点的度等于该顶点的入度与出度之和。? 入度——以该顶点为终点的边的数目和 出度——以该顶点为起点的边的数目和 图的阶：图中顶点的个数。例如图1—3中分别是6和3。 ? 度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。 [定理1] 图G中所有顶点的度数之和等于边数的2倍。因为计算顶点的度数时。每条边均用到2次。[定理2] 任意一个图一定有偶数个奇点。 连通：如果顶点u，v属于G，u，v之间有一条从u通过若干条边到达v的通路，则认为顶点u和v是连通的。 连通图：如果对于图G中每一对不同顶点u，v都有一条(u，v)通路，则称G是连通图。??? 通路指u--边1--顶点1--边2--顶点2--……--v，点和边交替相接，且互不相同。 图的遍历 1、概念：从图中某一结点出发系统地访问图中所有结点，使每个结点恰好被访问一次，这种运算 称图的遍历。为了避免重复访问某个结点，可以设一个标志数组visited[I]，未访问时值为FALSE，访问一次后就改为TRUE。 2、分类：深度优先遍历和广度优先遍历