第七天第七天 简单的数据结构类型应用简单的数据结构类型应用二维数组，队列，栈，树，图用计算机解决问题一般步骤：具体问题具体问题数学模型数学模型算法算法编程、调试编程、调试得到答案得到答案今天主要内容今天主要内容今天主要内容今天主要内容l二维数组和线性表l队列l栈l树l图线性表表示（一）线性表表示（一）线性表表示（一）线性表表示（一）lN个数据元素的有限序列（一般用数组表示）l存储结构：顺序存储结构、链式存储结构121315223438432012345678线性表表示（二）线性表表示（二）线性表表示（二）线性表表示（二）l链式存储（不要求掌握，有兴趣可以阅读指针一章）12131522 20 Lhead二维数组二维数组二维数组二维数组二维数组的一个形象比喻多个纵队形成的方块 m * na11a12a13a14a1na21a22a23a24a2na31a32a33a34a3nam1am2am3am4amn二维数组在内存的存储方式是线性的。1：按照行存储：按照行存储：即先存储第一行然后在存储第二行，那么aij的值应该是A11+（i-1)*n+j-12: 1：按照列存储：按照列存储：即先存储第一列然后在存储第二列，那么aij的值应该是A11+（j-1)*m+i-1(很好记啊，很好记啊，I,j调换位置调换位置*的值的值n-m）思考：如果数组的定义为var num:array2.n,2.m，要求AIJ的位置，结果应该是是什么呢！另外数组地址计算问题另外数组地址计算问题o题目描述：已知题目描述：已知N*(N+1) / 2个数据，按行的顺序存入数个数据，按行的顺序存入数组组b1,b2,中。其中第一个下标表示行，第二个下标中。其中第一个下标表示行，第二个下标表示列。若表示列。若aij (i=j ,j=1,2,n)存于存于bk中，问：中，问：k,i,j之间的关系如何表示？给定之间的关系如何表示？给定k值，写出能决定相应值，写出能决定相应i,j的算法。的算法。a11a21a22a31a32a33an1an2an3an4ann 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)栈o特殊的线性表o操作特点：后进先出（Last In First Out）o栈顶表尾o栈底表头o空栈（top=bottom)ABCD栈顶指针：栈顶指针：指想下一个元素指想下一个元素的存放位置的存放位置栈底指针栈底指针栈 （考题分析）（1998） 栈栈S初始状态为空，现有初始状态为空，现有5个元素组成的序个元素组成的序列列1，2，3，4，5，对该序列在栈，对该序列在栈S上一次进上一次进行如下操作（从序列中的行如下操作（从序列中的1开始，出栈后不再进栈）开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是问出栈的元素序列是_(A) 5,4,3,2,1 (B) 2,1 (C) 2,3 (D) 3,4队列o特点：先进先出先进先出o允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。a1 a2 a3 a4 an 出队列入队列FRONTREAR循环队列循环队列12345678REARFRONT现在栈中存放的元素个数：现在栈中存放的元素个数：(R-F+N) mod N树树树树根、叶子、子树结点的度：结点拥有的子树数二叉树(每个节点最多只有两个子节点的树）ACFEBDG层次123二叉树o特点：每个结点至多只有二棵子树，并且二叉树特点：每个结点至多只有二棵子树，并且二叉树的子树有左右之分。的子树有左右之分。o第第i层层至多有至多有 个结点（个结点（i=1）o深度为深度为K的二叉树最多有的二叉树最多有 个结点个结点（K=1）ACFEBDGACFEBD满二叉树满二叉树完全二叉树完全二叉树二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历l先（根）序遍历l中（根）序遍历l后（根）序遍历先（根）序遍历ABDFGCEH中（根）序遍历BFDGACHE后（根）序遍历FGDBHECA l若左子树非空先访问左子树l访问根节点l若左子树非空先访问左子树ACEDBHFG中序遍历的程序Procedure (I,j:integer)I表示层数，j表示第几个节点BeginIf in then如果非根节点 begin procedure(i+1,2*i-1);遍历左子树 write(aI,j; 遍历子树节点 procedure (i+1,2*i); 遍历右子树 end；end.;例题分析例题分析例题分析例题分析o给出一棵二叉树的中序遍历：给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：与后序遍历：DGEBHIFCA ，画出此二叉树。画出此二叉树。ACEDBHFGI思考过程思考过程 先在后序中找到最后面的节点先在后序中找到最后面的节点AA，那我们那我们那我们那我们知道这棵树的根目录是知道这棵树的根目录是知道这棵树的根目录是知道这棵树的根目录是AA，AA将中序的遍将中序的遍将中序的遍将中序的遍历分成两个部分前面部分历分成两个部分前面部分历分成两个部分前面部分历分成两个部分前面部分“DBGE”DBGE”是左子是左子是左子是左子树的中序遍历，后面部分树的中序遍历，后面部分树的中序遍历，后面部分树的中序遍历，后面部分“CHFI”CHFI”是右子是右子是右子是右子树的中序遍列，树的中序遍列，树的中序遍列，树的中序遍列，在后序遍历中找到这两个在后序遍历中找到这两个在后序遍历中找到这两个在后序遍历中找到这两个字符串中最先出现的字符字符串中最先出现的字符字符串中最先出现的字符字符串中最先出现的字符，那就是左子树，那就是左子树，那就是左子树，那就是左子树和右子树的根节点，再在中序遍历中划分和右子树的根节点，再在中序遍历中划分和右子树的根节点，再在中序遍历中划分和右子树的根节点，再在中序遍历中划分.图图ACEDB无向图无向图ACEDB有向图有向图图的存储结构图的存储结构图的存储结构图的存储结构邻接矩阵邻接矩阵邻接矩阵邻接矩阵l邻接矩阵（二维数组二维数组）1452312345101100210001301001410100500000 遍历是指从图的某个点出发，沿着与之相连的边访问图中的每个一次且仅一次。基本方法有两种：深度优先遍历和广度优先遍历。深度优先遍历和广度优先遍历。 深度优先和广度优先遍历，与前面所说的树的深度与广度优先遍历是类似的：比下图中，如果从点V1出发，那么： 深度优先遍历各点的顺序为：v1，v2，v4，v7，v5，v3，v6，v8。 广度优先遍历各点的顺序为：v1，v2，v3，v4，v5，v6，v7，v8。学生练习题一（学生练习题一（学生练习题一（学生练习题一（20042004）利用今天学习的知识解决下列问题利用今天学习的知识解决下列问题1：二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为（ ）。A.4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 12：满二叉树的叶结点个数为N，则它的结点总数为（ ）。A.N B. 2 * N C. 2 * N 1 D. 2 * N + 1 E. 2N 1l某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为1，2，3，则车辆出站的顺序为（ ）。 A：1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 l D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 7学生练习题二（学生练习题二（2004）3：某大学计算机专业的必修课及其先修课程如下表所示：某大学计算机专业的必修课及其先修课程如下表所示：请你判断下列课程安排方案哪个是不合理的（请你判断下列课程安排方案哪个是不合理的（ ）。A. C0, C6, C7, C1, C2, C3, C4, C5 B. C0, C1, C2, C3, C4, C6, C7, C5C. C0, C1, C6, C7, C2, C3, C4, C5 D. C0, C1, C6, C7, C5, C2, C3, C4E. C0, C1, C2, C3, C6, C7, C5, C4二问题求解二问题求解 （每题（每题5分，共分，共10分）分）2004l一个家具公司生产桌子和椅子。现在有113个单位的木材。每张桌子要使用20个单位的木材，售价是30元；每张椅子要使用16个单位的木材，售价是20元。使用已有的木材生产桌椅（不一定要把木材用光），最多可以卖 元钱。l75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有 名儿童没有玩过其中任何一种。问题求解问题求解 （每题（每题5分，共分，共10分）分）2004l编号为1到13的纸牌顺时针排成一圈，有人从编号为1的牌从数字1开始顺时针数下去，1、2、3、20、21、，一圈又一圈。问：当数到数字N时，所在纸牌的编号为多少?Noip2008相应的题目l7设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（ ）。lA. 6 B. 5 C. 4 D. 3l完全二叉树共有2*N-1个结点，则它的叶节点数是（ ）。lA. N-1 B. N C. 2*N D. 2N-1l 设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为真的是（ ）。lA. (AB)(CDA) B. (AB)C)D lC. (BCD)DA D. A(DC)B l13. 二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），中根遍历是2 4 1 5 7 3 6，则该二叉树的后根遍历是（ ）。lA. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 lC. 7 4 2 5 6 3 1 D. 4 2 7 6 5 3 1Noip2008相应的题目l18. 设T是一棵有n个顶点的树，下列说法不正确的是（ ）。lA. T有n条边 B. T是连通的lC. T是无环的 D. T有n-1条边二问题求解（共二问题求解（共2题，每题题，每题5分，共计分，共计10分）分）o1. 书架上有4本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这4本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_种。满足 A必须比C靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有_种摆法。o2有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为_。四完善程序四完善程序1（字符串替换）（字符串替换）给定一个字符串S（S仅包含大小写字母），下面的程序将S中的每个字母用规定的字母替换，并输出S经过替换后的结果。程序的输入是两个字符串，第一个字符串是给定的字符串S，第二个字符串S由26个字母组成，它是a-z的任一排列，大小写不定，S规定了每个字母对应的替换字母：S中的第一个字母是字母A和a的替换字母，即S中的A用该字母的大写替换，S中的a用该字母的小写替换；S中的第二个字母是字母B和b的替换字母，即S中的B用该字母的大写替换，S中的b用该字母的小写替换； 以此类推。varchange:string;str:string;procedure CheckChangeRule;var i:integer;begin for i:=1 to 26 do beginif then changei:= chr(ord(changei) - ord(A) + ord(a); end;end;procedure ChangeString;var len,i:integer;begin len := length(str); for i:=1 to len do begin if then begin stri := upcase(changeord(stri) ord(A) + 1); end else begin end; end;end;begin readln(str);readln(change); CheckChangeRule; writeln(str);end.