Pascal简单的数据结构类型应用.ppt

1、第七天 简单的数据结构类型应用,二维数组，队列，栈，树，图,用计算机解决问题一般步骤：,具体问题,数学模型,算法,编程、调试,得到答案,今天主要内容,二维数组和线性表 队列 栈 树 图,线性表表示（一）,N个数据元素的有限序列（一般用数组表示） 存储结构：顺序存储结构、链式存储结构,20,12345678,线性表表示（二）,链式存储（不要求掌握，有兴趣可以阅读指针一章）,L,head,二维数组,二维数组的一个形象比喻 多个纵队形成的方块 m * n,二维数组在内存的存 储方式是线性的。1：按照行存储：即先 存储第一行然后在存 储第二行，那么aij的值应 该是A11+（i-1)*n+j-1 2:

2、 1：按照列存储：即先 存储第一列然后在存 储第二列，那么aij的值应 该是A11+（j-1)*m+i-1 (很好记啊，I,j调换位置 *的值n-m）,思考：如果数组的定义为var num:array2.n,2.m，要求AIJ的位置，结果应该是是什么呢！,另外数组地址计算问题,题目描述：已知N*(N+1) / 2个数据，按行的顺序存入数组b1,b2,中。其中第一个下标表示行，第二个下标表示列。若aij (i=j ,j=1,2,n)存于bk中，问：k,i,j之间的关系如何表示？给定k值，写出能决定相应i,j的算法。, K=i*(i-1)/2+j Read(k); For i:=1 to k do

3、 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） 栈顶表尾 栈底表头 空栈（top=bottom),A,B,C,D,栈顶指针： 指想下一个元素的存放位置,栈底指针,栈 （考题分析）,（1998） 栈S初始状态为空，现有5个元素组成的序列1，2，3，4，5，对该序列在栈S上一次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是_ (A) 5,4,3,2,1 (B) 2

4、,1 (C) 2,3 (D) 3,4,队列,特点：先进先出 允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。,出队列,入队列,循环队列,REAR,FRONT,现在栈中存放的元素个数：(R-F+N) mod N,树,根、叶子、子树 结点的度：结点拥有的子树数 二叉树(每个节点最多只有两个子节点的树）,层次 1 2 3,二叉树,特点：每个结点至多只有二棵子树，并且二叉树的子树有左右之分。 第i层至多有 个结点（i=1） 深度为K的二叉树最多有 个结点（K=1）,满二叉树,完全二叉树,二叉树的遍历,先（根）序遍历 中（根）序遍历 后（根）序遍历 先（根）序遍历 ABDFGC

5、EH 中（根）序遍历 BFDGACHE 后（根）序遍历 FGDBHECA 若左子树非空先访问左子树 访问根节点 若左子树非空先访问左子树,中序遍历的程序,Procedure (I,j:integer)I表示层数，j表示第几个节点 Begin If in then如果非根节点 begin procedure(i+1,2*i-1);遍历左子树 write(aI,j; 遍历子树节点 procedure (i+1,2*i); 遍历右子树 end； end.;,例题分析,给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA ，画出此二叉树。,思考过程 先在后序中找到最后面的节点A

6、，那我们 知道这棵树的根目录是A，A将中序的遍 历分成两个部分前面部分“DBGE”是左子 树的中序遍历，后面部分“CHFI”是右子 树的中序遍列，在后序遍历中找到这两个 字符串中最先出现的字符，那就是左子树 和右子树的根节点，再在中序遍历中划分 .,图,无向图,有向图,图的存储结构邻接矩阵,邻接矩阵（二维数组）,遍历是指从图的某个点出发，沿着与之相连的边访问图中的每个一次且仅一次。基本方法有两种：深度优先遍历和广度优先遍历。 深度优先和广度优先遍历，与前面所说的树的深度与广度优先遍历是类似的：比下图中，如果从点V1出发，那么： 深度优先遍历各点的顺序为：v1，v2，v4，v7，v5，v3，v6

7、，v8。 广度优先遍历各点的顺序为：v1，v2，v3，v4，v5，v6，v7，v8。,图的遍历,学生练习题一（2004）,利用今天学习的知识解决下列问题 1：二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为（ ）。 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 1 2：满二叉树的叶结点个数为N，则它的结点总数为（ ）。 N B. 2 * N C. 2 * N 1 D. 2 * N + 1 E. 2N 1 某个车站

8、呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为1，2，3，则车辆出站的顺序为（ ）。 A：1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 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,

9、 C2, C3, C4, C6, C7, C5 C. C0, C1, C6, C7, C2, C3, C4, C5 D. C0, C1, C6, C7, C5, C2, C3, C4 E. C0, C1, C2, C3, C6, C7, C5, C4,二问题求解 （每题5分，共10分）2004,一个家具公司生产桌子和椅子。现在有113个单位的木材。每张桌子要使用20个单位的木材，售价是30元；每张椅子要使用16个单位的木材，售价是20元。使用已有的木材生产桌椅（不一定要把木材用光），最多可以卖 元钱。 75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西

10、都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有 名儿童没有玩过其中任何一种。,问题求解 （每题5分，共10分）2004,编号为1到13的纸牌顺时针排成一圈，有人从编号为1的牌从数字1开始顺时针数下去，1、2、3、20、21、，一圈又一圈。问：当数到数字N时，所在纸牌的编号为多少?,Noip2008相应的题目,7设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（ ）。 A. 6 B. 5 C. 4 D. 3 完全二叉树共有2*N-1个结点，则它的叶节点数是（ ）。 A. N-1 B.

11、 N C. 2*N D. 2N-1 设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为真的是（ ）。 A. (AB)(CDA) B. (AB)C)D C. (BCD)DA D. A(DC)B 13. 二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），中根遍历是2 4 1 5 7 3 6，则该二叉树的后根遍历是（ ）。 A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 7 4 2 5 6 3 1 D. 4 2 7 6 5 3 1,Noip2008相应的题目,18. 设T是一棵有n个顶点的树，下列说法不正确的

12、是（ ）。 A. T有n条边 B. T是连通的 C. T是无环的 D. T有n-1条边,二问题求解（共2题，每题5分，共计10分）,1. 书架上有4本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这4本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_种。满足 A必须比C靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有_种摆法。 2有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为_。,四完善程序,1（字符串替换）给定一个字符串S（S仅包含大小写字母），下面的程序将S中的每个字母用规定的字母替换，并输出S经

13、过替换后的结果。程序的输入是两个字符串，第一个字符串是给定的字符串S，第二个字符串S由26个字母组成，它是a-z的任一排列，大小写不定，S规定了每个字母对应的替换字母：S中的第一个字母是字母A和a的替换字母，即S中的A用该字母的大写替换，S中的a用该字母的小写替换；S中的第二个字母是字母B和b的替换字母，即S中的B用该字母的大写替换，S中的b用该字母的小写替换； 以此类推。,var change:string; str:string; procedure CheckChangeRule; var i:integer; begin for i:=1 to 26 do begin if then changei:= chr(ord(changei) - ord(A) + ord(a); end; end; procedure ChangeString; var len,i:integer;