算法合集之《基本数据结构在信息学竞赛中的应用》

《算法合集之《基本数据结构在信息学竞赛中的应用》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2006年全国信息学冬令营讲座基本数据结构在信息学竞赛中的应用安徽省芜湖市第一中学朱晨光目录Ø摘要2Ø关键字2Ø正文2u引言2u第一部分——基本数据结构的介绍3ü一、线性表..................................................................3ü二、栈5ü三、队列......................................................................5u第二部分——基本数据结构的应用6ü一、栈的应用6ü二、线性

2、表的应用10ü三、队列的应用12Ø总结16Ø参考文献16Ø感谢16Ø附录17第29页共29页2006年全国信息学冬令营讲座摘要本文介绍了几种基本数据结构（例如线性表、队列）在信息学竞赛中的应用，并通过文中的几道例题集中体现了这些数据结构的重要作用。全文可以分为如下几个部分：一、介绍几种常用的基本数据结构；二、通过几道例题说明基本数据结构的重要作用；三、总结全文并探讨应用基本数据结构在思想上带来的启示。关键字基本数据结构线性表队列双向链表栈编程复杂度时间复杂度辨证关系螺旋式发展正文引言在当今的信息学竞赛中，各种高难度的题目层

3、出不穷。而与这些题目相伴而来的便是很高的编程复杂度。随着计算机科学的不断进步，有越来越多高效而实用的数据结构应运而生。但是，其惊人的编程复杂度使得我们在比赛时必须小心翼翼，慎之又慎，并且经常因为一个微小的疏漏而导致全盘皆输。然而，并非所有的题目都只能运用复杂的数据结构加以解决。有些时候，常常被我们忽略的基本数据结构也大有用武之地。灵活地运用基本数据结构，可以使我们在紧张的信息学比赛中赢得宝贵的时间，增加成功的概率。第一部分——基本数据结构的介绍其实，这一部分的内容可以在所有介绍数据结构的书中找到，这里只做比较简单的介绍。一

4、、线性表线性表是最常用且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。对线性表进行的基本操作有如下几种：1)INITIATE(L)初始化操作2)LENGTH(L)求长度函数3)GET(L,i)取元素函数4)PRIOR(L,element)求前驱函数5)NEXT(L,element)求后继函数第29页共29页2006年全国信息学冬令营讲座6)LOCATE(L,x)定位函数7)INSERT(L,i,b)前插操作8)DELETE(L,i)删除操作9)EMPTY(L)判空表操作10)CLEAR(L)表置空操作线

5、性表的顺序存储结构在计算机内，可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续的存储单元依次存储线性表的元素（即我们通常所说的“一维数组”）（如图1）。存储地址内存状态元素在线性表中的序号ba11b+La22………………b+(i-1)Laii………………b+(n-1)Lannb+nL……b+(maxlen-1)L图1空闲应用这种存储结构，可以实现对线性表中任一数据元素的随机存取。所以线性表的顺序存储结构是一种随机存取的存储结构。在Pascal与C语言中可以用一维数组描述之。可以很容易证明，在线性表的顺

6、序存储结构中，删除与插入任意一个元素的时间复杂度为O(N)，而定位一个元素的时间复杂度为O(1).线性表的链式存储结构1、线性链表线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。对于每个数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。这两部分信息组成数据元素ai的存储映象，称为结点，其中包括存储数据元素信息的数据域和存储直接后继存储位置的指针域（称为指针或链）。n个节点的链组成一个链表，称为线性链表或单链表（如图2）。head图2ZHAOQIANSUN第29页共29页20

7、06年全国信息学冬令营讲座其中head为头节点，它的指针域存储第一个元素结点的存储位置。1、循环链表循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环（如图3）。head图3ZHAOQIANSUN2、双向链表顾名思义，双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前驱。当然，双向链表也有循环表，其结构如图4所示。head图4ZHAOQIANSUN可以很容易证明，在线性表的链式存储结构中，删除与插入任意一个已经定位的元素的时间复杂度为O(1)，而定位一个元素的时

8、间复杂度为O(N).一、栈栈是限定仅在表尾进行插入或删除操作的线性表。因此，表尾端称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。根据图5可以很明显地看出，栈的修改是按后进先出的原则进行的。因此，栈又称后进先出（LastInFirstOut）的线性表（简称LIFO结构）。栈的基本操作有：INI