noip2012简单的数据结构类型应用
时间：2025-04-29
noip2012初赛赛前集训第一讲(二维数组,队列,栈,树,图,HASH表)谷哥
Lesson1 NOIP2012国庆初赛培训一——简单的数据结构类型应用 二维数组，队列，栈，树，图
noip2012初赛赛前集训第一讲(二维数组,队列,栈,树,图,HASH表)谷哥
今天主要内容 简单的数据结构类型应用 二维数组和线性表 队列 栈 树 图
哈希表(Hash Table)马鞍山市成功学校 谷老师讲座
noip2012初赛赛前集训第一讲(二维数组,队列,栈,树,图,HASH表)谷哥
一:线性表表示(一) N个数据元素的有限序列(一般用数组表示) 存储结构：顺序存储结构、链式存储结构112
213
315
422
534
638
743
8
20马鞍山市成功学校 谷老师讲座
noip2012初赛赛前集训第一讲(二维数组,队列,栈,树,图,HASH表)谷哥
线性表表示(二) 链式存储(不要求掌握，有兴趣可以阅读指针一章)head
12
13
15
22 ^
L
20 ^
马鞍山市成功学校
谷老师讲座
noip2012初赛赛前集训第一讲(二维数组,队列,栈,树,图,HASH表)谷哥
二维数组 二维数组的一个形象比喻—— 多个纵队形成的方块 m * n二维数组在内存的存 储方式是线性的。 1:按照行存储：即先 存储第一行然后在存 储第二行，那么aij的值应 该是A11+(i-1)*n+j-1
a11 a21 a31 ……
a12 a22 a32 ……
a13 a23 a33 ……
a14 a24 a34 ……
…… …… …… ……
a1n a2n a3n ……
2: 1:按照列存储：即先 存储第一列然后在存 储第二列，那么aij的值应 该是A11+(j-1)*m+i-1 (很好记啊，I,j调换位置 *的值n->m)
am1
am2
am3
am4
……
amn
马鞍山市成功学校 谷老师讲座 思考：如果数组的定义为var num:array[2..n,2..m],要 求AIJ的位置，结果应该是是什么呢！
noip2012初赛赛前集训第一讲(二维数组,队列,栈,树,图,HASH表)谷哥
另外数组地址计算问题 题目描述：已知N*(N+1) / 2个数据，按行的顺序存入数 组b[1],b[2],…中。其中第一个下标表示行，第二个下标 表示列。若aij (i>=j ,j=1,2,…,,n)存于b[k]中，问： k,i,j之间的关系如何表示？给定k值，写出能决定相应i,j的 算法。 a11
a21
a22
a31
a32
a33
… …
… …
… …
… …
… … … …
… …
① 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)
an1
an2
an3
an4
ann马鞍山市成功学校 谷老师讲座
noip2012初赛赛前集训第一讲(二维数组,队列,栈,树,图,HASH表)谷哥
二:栈的定义1.栈的定义 栈(stack)是一种只允许在一端进行插入和删除的线性表，它是一种操作 受限的线性表。在表中只允许进行插入和删除的一端称为栈顶(top),另 一端称为栈底(bottom)。栈的插入操作通常称为入栈或进栈(push),而栈的 删除操作则称为出栈或退栈(pop)。当栈中无数据元素时，称为空栈。 根据栈的定义可知，栈顶元素总是最后入栈的，因而是最先出栈；栈底元 素总是最先入栈的，因而也是最后出栈。这种表是按照后进先出(LIFO, last in first out )的原则组织数据的，因此，栈也被称为“后进先出”的线 性表。 图3-3是一个栈的示意图，通常用指针top指示栈顶的位置，用指针bottom 指向栈底。栈顶指针top动态反映栈的当前位置。 入栈 栈顶 top 出
栈an-1.. .
1 栈底 a bottom马鞍山市成功学校 谷老师讲座 图3-3栈的示意图0
a
noip2012初赛赛前集训第一讲(二维数组,队列,栈,树,图,HASH表)谷哥
栈 特殊的线性表 操作特点：后进先出(Last In First Out) 栈顶——表尾 栈底——表头 栈顶指针： 空栈(top=bottom)DC B 栈底指针马鞍山市成功学校 谷老师讲座
指想下一个元素 的存放位置
A
noip2012初赛赛前集训第一讲(二维数组,队列,栈,树,图,HASH表)谷哥
栈 (考题分析)(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}
马鞍山市成功学校
谷老师讲座
noip2012初赛赛前集训第一讲(二维数组,队列,栈,树,图,HASH表)谷哥
三:队列 特点：先进先出 允许插入的一端称为队尾(rear),允许删除 的一端称为队头(front)。出队列 入队列
a1
a2
a3
a4
…… an
FRONT
REAR
马鞍山市成功学校
谷老师讲座
noip2012初赛赛前集训第一讲(二维数组,队列,栈,树,图,HASH表)谷哥
循环队列FRONTREAR 2 1 8 7 3 4 5 6
现在栈中存放的元素个数：(R-F+N) mod N马鞍山市成功学校 谷老师讲座
noip2012初赛赛前集训第一讲(二维数组,队列,栈,树,图,HASH表)谷哥
四:树的概念 树(Tree)是n(n>=0)个结点的有限集。在一棵非空树中： (1) 有且仅有一个特定的称为根的结点; (2) 当n>1时其余结点可分为m(m>0)个互不相交的有限集T1,T2...Tm, 其中,每一个集合 本身 又是一棵树, 并且称为根的子树(subtree)例如,在图6.1中,(a)是只 有一个根 结点的树;(b)是有 13个结点的树,其中A是根,其余结点分成三个互不相交 的子树
马鞍山市成功学校
noip2012简单的数据结构类型应用.doc
将本文的Word文档下载到电脑
