1、基本数据结构在信息学竞赛中的应用安徽省芜湖市第一中学朱晨光IOI2006中国国家集训队论文 安徽省芜湖市第一中学 朱晨光引言n 题目难 应用高级数据结构基本数据结构！n 本篇论文将介绍几种基本数据结构在信息学竞赛中的应用，并通过几道例题集中体现这些数据结构的重要作用。 n 编程复杂度高n 容易出错第一部分 基本数据结构的介绍n 一、线性表（线性表的顺序存储结构）b+(maxlen-1)Lb+nLnanb+(n-1)Liaib+(i-1)L2a2b+L1a1b元素在 线 性表中的序号内存状态存 储 地址空闲线性表n 二、线性表的链式存储结构线性链表：ZHAO QIAN SUNhead线性表的链式
2、存储结构循环链表：ZHAO QIAN SUNhead线性表的链式存储结构双向链表：ZHAO QIAN SUNhead栈a1a2an删除 插入栈顶栈底队列a1 a2 a3 a n队头 队尾入队列出队列第二部分 基本数据结构的应用栈的应用 例 1 求 01矩阵中最大的全零矩形 线性表的应用 例 2 营业额统计队列的应用 例 3 瑰丽华尔兹线性表的应用 营业额统计n 给定 N（ 1N32767）天的营业额 a1,a2,an. n 定义一天的最小波动值等于min|该天以前某一天的营业额 -该天营业额 |n 特别地，第一天的最小波动值即为 a1试求 N天的最小波动值之和n 例如： N=3,a1=9,a2=3,a3=8，则各天最小波动值依次为 9， 6， 1，和为 16
