数据结构与简单算法.doc

数据结构与简单算法 广东汕头华侨中学 欧阳玲 用计算机解决问题一般步骤： 一般来说，用计算机解决一个具体问题时，大致经过以下几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序进行测试调整知道的到最终解答。寻求数学模型的实质就是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。 三种经典的数学模型 图书书目自动检索系统——线性关系 博弈问题——树 城市道路问题——图 数据结构（data structure） 简单的解释：相互之间存在一种或多种特定关系的数据元素的集合。 数据间的联系有逻辑关系、存储联系，通常的数据结构指的是逻辑结构。 前面提到的三种经典的数学模型体现了数据结构的基本结构，数据结构通常有如下四种关系：（1）集合结构 （2）线性结构 （3）树形结构 （4）图状结构 ☆ 线性表（一） N个数据元素的有限序列 存储结构：顺序存储结构、链式存储结构 （1） （2） （3） （4） （5） （6） （7） （8） 12 13 15 22 34 38 43 当需要在顺序存储的线性表中插入一个数据元素时，需要顺序移动后续的元素以“腾”出某个合适的位置放置新元素。删除元素呢？ ☆ 线性表（二） 链式存储 插入新元素的时候只需要改变指针所指向的地址。 ☆ 二维数组与线性表 如果某一线性表，它的每一个数据元素分别是一个线性表，这样的二维表在数据实现上通常使用二维数组。 二维数组的一个形象比喻—— 多个纵队形成的方块 m * n ☆ 数组地址计算问题 题目描述：已知N* N+1 / 2个数据，按行的顺序存入数组b[1],b[2],…中。其中第一个下标表示行，第二个下标表示列。若aij i j ,j 1,2,…,,n 存于b[k]中，问：k,i,j之间的关系如何表示？给定k值，写出能决定相应i,j的算法。 答案 ① K i* i-1 /2+j ② Read k ; For i: 1 to k do for j: 1 to i do if k trunc I* I-1 /2 +j then writeln k,’对应的i,j为：‘,i,’,’,j ☆ 栈 特殊的线性表 操作特点：后进先出（Last In First Out） 栈顶——表尾 栈底——表头 空栈 ☆ 栈 （考题分析） （1998） 栈S初始状态为空，现有5个元素组成的序列 1，2，3，4，5 ，对该序列在栈S上一次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是______D A 5,4,3,2,1 B 2,1 C 2,3 D 3,4 ☆ 队列 先进先出 允许插入的一端称为队尾 rear ，允许删除的一端称为队头 front 。 ☆ 循环队列 头指针指向队列中队头元素的前一个位置，尾指针指示队尾元素在队列中的当前位置。 ☆ 树 根、叶子、子树 结点的度：结点拥有的子树数 二叉树 ☆ 二叉树 特点：每个结点至多只有二棵子树，并且二叉树的子树有左右之分。 第i层至多有 2i-1 个结点（i 1） 深度为K的二叉树最多有 2k-1 个结点（K 1） ☆ 二叉树的遍历 先（根）序遍历 ABDFGCEH 中（根）序遍历 BFDGACHE 后（根）序遍历 FGDBHECA ☆ 例题分析 给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA ，画出此二叉树。 ☆ 图 ☆ 图的存储结构 邻接矩阵 有向图、无向图、带权图的邻接矩阵 ☆ 排序 冒泡排序 选择排序 快速排序 希尔排序 一、插入排序 Insertion Sort 1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程：　 【示例】： [初始关键字] [49] 38 65 97 76 13 27 49 J 2 38 [38 49] 65 97 76 13 27 49 J 3 65 [38 49 65] 97 76 13 27 49 J 4 97 [38 49 65 97] 76 13 27 49 J 5 76 [38 49 65 76 97] 13 27 49 J 6 13 [13 38 49 65 76 97] 27 49 J 7 27 [13 27 38 49 65 76 97] 49 J 8 49 [13 27 38 49 49 65 76 97] Procedure InsertSort