数据结构与简单算法概要.ppt

《数据结构与简单算法概要.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与简单算法广东汕头华侨中学欧阳玲老师数据结构什么是数据结构线性表二维数组与线性表栈队列树图用计算机解决问题一般步骤：具体问题数学模型算法编程、调试得到答案三种经典的数学模型图书书目自动检索系统——线性关系博弈问题——树城市道路问题——图数据结构（datastructure）简单的解释：相互之间存在一种或多种特定关系的数据元素的集合。数据间的联系有逻辑关系、存储联系，通常的数据结构指的是逻辑结构。线性表（一）N个数据元素的有限序列存储结构：顺序存储结构、链式存储结构121315223438432

2、012345678线性表（二）链式存储12131522^20^Lhead二维数组与线性表二维数组的一个形象比喻——多个纵队形成的方块m*na11a12a13a14……a1na21a22a23a24……a2na31a32a33a34……a3n………………………………am1am2am3am4……amn数组地址计算问题题目描述：已知N*(N+1)/2个数据，按行的顺序存入数组b[1],b[2],…中。其中第一个下标表示行，第二个下标表示列。若aij(i>=j,j=1,2,…,,n)存于b[k]中，问：k,i

3、,j之间的关系如何表示？给定k值，写出能决定相应i,j的算法。a11a21a22a31a32a33………………………………an1an2an3an4……ann答案①K=i*(i-1)/2+j②Read(k);Fori:=1tokdoforj:=1toidoifk=(trunc(I*(I-1)/2)+j)thenwriteln(k,’对应的i,j为：‘,i,’,’,j)栈特殊的线性表操作特点：后进先出（LastInFirstOut）栈顶——表尾栈底——表头空栈栈（考题分析）（1998）栈S初始状态为空，现

4、有5个元素组成的序列{1，2，3，4，5}，对该序列在栈S上一次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是______(A){5,4,3,2,1}(B){2,1}(C){2,3}(D){3,4}队列先进先出允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。循环队列a1a2a3a4……an出队列入队列循环队列12345678RF(R-F+N)modN树根、叶子、子树结点的度：结点拥有的子树数二叉树ACFEBDG层

5、次123二叉树特点：每个结点至多只有二棵子树，并且二叉树的子树有左右之分。第i层至多有个结点（i>=1）深度为K的二叉树最多有个结点（K>=1）ACFEBDGACFEBD满二叉树完全二叉树二叉树的遍历先（根）序遍历中（根）序遍历后（根）序遍历ACEDBHFG例题分析给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA，画出此二叉树。ACEDBHFGI图ACEDB无向图ACEDB有向图图的存储结构邻接矩阵145231234510110021000130100141010050000

6、0排序冒泡排序选择排序快速排序希尔排序讲座完毕