数据结构与简单算法广东汕头华侨中学欧阳玲用计算机解决问题一般步骤：一般来说，用计算机解决一个具体问题时，大致经过以下几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序进行测试调整知道的到最终解答。寻求数学模型的实质就是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。三种经典的数学模型图书书目自动检索系统——线性关系博弈问题——树城市道路问题——图数据结构（datastructure）简单的解释：相互之间存在一种或多种特定关系的数据元素的集合。数据间的联系有逻辑关系、存储联系，通常的数据结构指的是逻辑结构。前面提到的三种经典的数学模型体现了数据结构的基本结构，数据结构通常有如下四种关系：（1）集合结构（2）线性结构（3）树形结构（4）图状结构☆线性表（一）N个数据元素的有限序列存储结构：顺序存储结构、链式存储结构（1）（2）（3）（4）（5）（6）（7）（8）12131522343843当需要在顺序存储的线性表中插入一个数据元素时，需要顺序移动后续的元素以“腾”出某个合适的位置放置新元素。删除元素呢？☆线性表（二）链式存储插入新元素的时候只需要改变指针所指向的地址。1具体问题数学模型算法编程、调试得到答案20☆二维数组与线性表如果某一线性表，它的每一个数据元素分别是一个线性表，这样的二维表在数据实现上通常使用二维数组。二维数组的一个形象比喻——多个纵队形成的方块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);Fori:=1tokdoforj:=1toidoifk=(trunc(I*(I-1)/2)+j)thenwriteln(k,’对应的i,j为：‘,i,’,’,j)☆栈特殊的线性表操作特点：后进先出（LastInFirstOut）栈顶——表尾栈底——表头空栈☆栈（考题分析）（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}2☆队列先进先出允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。☆循环队列头指针指向队列中队头元素的前一个位置，尾指针指示队尾元素在队列中的当前位置。☆树根、叶子、子树结点的度：结点拥有的子树数二叉树☆二叉树特点：每个结点至多只有二棵子树，并且二叉树的子树有左右之分。第i层至多有2i-1个结点（i>=1）深度为K的二叉树最多有2k-1个结点（K>=1）☆二叉树的遍历3(R-F+N)modN先（根）序遍历ABDFGCEH中（根）序遍历BFDGACHE后（根）序遍历FGDBHECA☆例题分析给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA，画出此二叉树。☆图☆图的存储结构邻接矩阵有向图、无向图、带权图的邻接矩阵4☆排序冒泡排序选择排序快速排序希尔排序一、插入排序(InsertionSort)1.基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。2.排序过程：【示例】：[初始关键字][49]38659776132749J=2(38)[3849]659776132749J=3(65)[384965]9776132749J=4(97)[38496597]76132749J=5(76)[3849657697]132749J=6(13)[133849657697]2749J=7(27)[13273849657697]49J=8(49)[1327384949657697]ProcedureInsertSort(VarR:FileType);//对R[1..N]按递增序进行插入排序,R[0]是监视哨//BeginforI:=2ToNDo//依次插入R[2],...,R[n]//beginR[0]:=R[I];J:=I-1;WhileR[0]<R[J]Do//查找R[I]的插入位置//beginR[J+1]:=R[J];//将大于R[I]的元素后移//J:=J-1endR[J+1]:=R[0];//插入R[I]//endEnd;//InsertSort//二、选择排序1.基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。2.排序过...