数据结构范文
时间：2023-11-22 19:31:27
数据结构篇1
关键词:数据结构;教学改革;教材研究
中图分类号:G642文献标识码:B
1引言
提起“数据结构”,大多数人都认为它是一门基础性课程。从某种角度看,“数据结构”有点像“高等数学”,一是两者内容大多早已成熟,二是它们都积累了大量习题可供学生练习。这样一来,应试倾向的“数据结构”课程应运而生,无论是在教学和学习中,这种倾向性都非常明显。比如在链表这部分内容的讲授中,教师一般会给出各种不同的链表变种作为习题。又比如在讨论二叉树遍历时,学生要花费大量精力去学习各种遍历的非递归形式。虽然学习这些内容可以提高逻辑思维能力,但学习“数据结构”的目的是为程序设计、更是为算法设计而服务,因此其重点应放在如何挑选或设计合适的数据结构,而不是把大量精力花在这些不太实用的细节问题上。
另一方面,数据结构还有许多值得研究的问题。许多数据结构不但性能优越,而且构造精巧,比如二项堆与Fibonacci堆。而发展成熟的数据结构很快便可应用于工业界,如STL中的vector容器。研究人员不但需要设计新的数据结构以获得好的性能,并且还要对它们进行细致的分析以了解其性能极限(即下界问题)。此外,目前有若干专门的学术会议致力于数据结构的设计与分析,如交替举办的The Workshop on Algorithms and Data Structures (WADS)和The Scandinavian Workshop on Algorithm Theory(SWAT)。今年是WADS举办20周年,这也充分说明了数据结构这个经典的主题依然有着蓬勃的生命力。
因此,在数据结构的教学过程中,我们需要一本合适的数据结构教材,既能学习到如何使用和选择数据结构,还能深入了解数据结构的设计与分析。
2一本历久弥新的教材
关于“数据结构”,最权威的阐述当推Knuth的The Artof Computer Programming第1卷(首版于1968年出版,这也是关于数据结构最早的著作),此书对数据结构作了简洁精当的讲解。但该书过于简略,对于初学者来说难度较大。
1976年,Computer Science Press出版了由Ellis Horowitz和Sartaj Sahni编著的《数据结构基础》,(下文简称《数》)此书相比Knuth的巨著而言则显得较为平易近人,不但内容详实、深入,而且覆盖面很广。因此,《数》一面世便受到了极大的欢迎,总印数高达约10万册,在当时已属天文数字。另外,该书的姐妹篇《计算机算法基础》于1978年出版,此书秉承了《数》的优点,也是一本畅销教材。不夸张地说,这两本书不但是优秀的教材,还是小型的百科全书,畅销也在意料之中。
20世纪80年代正是Pascal语言风靡全球之时,而首版《数》是以SPARK语言描述算法,所以作者于1983年推出了《数》的Pascal版,直到1994年,一共出了4版。其间作者还推出了《数》的IBM-PC Turbo Pascal版。进入20世纪90年代后,上面两位作者和Susan Anderson-Freed合作,推出了《数》的C语言版,又与Dinesh Mehta合作编写了《数》的C++语言版,该书版本之多也说明了它受欢迎的程度很高。
时至2006年,也就是《数》出版30年后,作者重新推出了《数》的C++语言第2版,在2007年又推出了《数》的C语言新版。一本计算机教材延绵30余年且不断更新,这是不多见的。
3数据结构的“圣经本”
在网络上搜索“资料结构”(即数据结构)和“圣经本”,便能找到众多成功考生的经验之谈,而他们无一例外地都会提到《数》。原来,中国台湾地区的许多大学和研究所都非常推崇《数》,并在其硕士入学考试资料结构这个科目中指定《数》英文版为标准参考书,考生们自然是人手一册,而此书也被誉为“资料结构的圣经本”。单就其作为教材生命力旺盛这一点而言,《数》就能担得起“圣经本”这一称号。
随手翻开《数》新版前几章,所见内容似乎是老生常谈,如稀疏矩阵的操作、多项式运算、迷宫问题、表达式求值等。这些问题在许多国内的教材中也有详细的论述,于是有些读者可能会觉得《数》“盛名之下,其实难副”。实际上,国内的数据结构教材大多是依据《数》为蓝本编写而成。要是仔细比对,会发现这些教材无论是从结构编排上,还是从内容选择上,都与《数》极为类似,由此可见《数》的影响力之大。选择此书作为教材蓝本的原因之一,应该是《数》的讲授方式类似前苏联的教科书,全面、详细、深入,因此它便作为范本一直流传。由于该书的前几章都是其1976年版中已经过精心锤炼的经典内容,因此在新版中未作较大改动。新版的更新主要从“树”这一章开始,而此后的内容相当丰富,不但可作为教材,还能可供专业人士参考之用,确为同类之翘楚,后文将对此以专节论述。
事实上,《数》之所以得到教师的厚爱,其原因不仅仅是它的内容远比一般教材丰富,我们试举几例以说明《数》的特色所在。
(1) 书中对树的定义是“A tree is a finite set of one or more nodes …”,请注意这里不嫌麻烦地强调了“一个或更多结点”。这个定义与Knuth的书中所给出的权威定义基本类似,但许多教材视而不见,早已抛弃了“树不能为空”的这个限制。这说明《数》体会到了这个细节问题,也即以森林的观点来看待树。此限制意味着存在空森林(恰好对应空二叉树),但不存在空树。从集合的观点看,树是基本元素/实体,不可为虚空,但允许定义空集/空森林。此乃该书特色之一――严谨性。
(2) 书中在数组的编程题中给了一道随机行走问题,此题虽不难,但能引发学生展开深入思考:① 如何利用数组高效表示几何结构。虽然普通的矩形网格很容易表示,但实际上,许多复杂几何或空间结构仍可用数组精巧地表示,这也是作者的用意之所在;② 进行随机模拟的重要性。这里虽然只实现了简单的仿真,但仿真这个主题在书中多次出现,还给出了多个编程题以供练习。而在仿真别强调效率,选用好的数据结构(如优先级队列)能极大提高仿真速度;③ 对于更复杂的图上随机行走问题,应如何结合后文中表示图的数据结构进行优化,这也非常值得思考。此乃该书特色之二――启发性。
(3) 书中在栈和队列的编程题中要求实现纸牌游戏,而该游戏直到现在依然非常流行,在各种操作系统中也都是必备的附加软件。纸牌游戏的实现只需要综合使用栈和队列的ADT即可搭建完毕,完成此实验不但能获得乐趣,而且还能对ADT的功用更为明了,可谓一举两得。相信讲授此部分内容时,打开操作系统所带的纸牌游戏演示,一定能引起学生的极大兴趣。此乃该书特色之三――趣味性。
《数》中的此类实例不胜枚举,在此不多赘述。
4百科全书式组织
《数》的特色在于其全面、详细、深入,这也是它作为参考书的优势。一方面,《数》对许多数据结构给出了详细的描述,这样使用和挑选数据结构的范围就不会局限于常用的那些基础结构。比如讲解树结构时,《数》以较大的篇幅作了相当详细的描述,还列出了不相交集和选拔树,以供读者选用。另一方面,《数》对许多结构给出了性能分析,它虽然不像原始文献那么详细,但也足以让读者明了。比如在讲树的计数时,有些书上只是给出结果,而《数》则通过简单的递归式求解获得了Catalan数,让读者不至于感到此数的突兀。
最值得一提的是《数》关于堆结构和查找结构部分的讲解,这两类结构是现代数据结构中最重要的两部分,书中对此着墨最深。新版中删除了一些用处不大的堆结构,加入了较为有用的配对堆并更换了最小―最大堆。讲授堆时,仍从重要的分摊复杂度入手,详细讲解了二项堆、Fibonacci堆、配对堆,并给出了相应的分摊复杂度,后面又介绍了最小―最大堆的几种实例,需要从事仿真、算法设计的读者基本都能中获取所想要了解的内容。而对于查找结构部分,新版则将一章扩充为三章,系统地阐述了各种查找结构。先详细阐述内存中的查找,又转向外存中的查找,最后着重讲解了数字/字符查找,尤其是trie和后缀树这两类结构。此外,在查找结构中,作者还以互联网中的包转发作为应用实例。
当然,作为教材的《数》还不足以反映数据结构的全貌。在编写此书的过程中,作者意犹未尽,还主持编写了一本系统阐述数据结构理论和应用的“百科全书”,全面、系统地阐述了各种数据结构,并给出了众多实际应用。有兴趣的读者学完《数》后,自然想了解更多、更深的内容,不妨去翻看这本“百科全书”。
需要指出的是,目前,北美的许多大学基本都将数据结构按难度拆分成两部分:基本内容与面向对象程序设计一起讲授;而高等内容则融入算法设计与分析的课程。每个大学所采用的教材也各有不同,而传统名校还特别偏爱本校教授编写的教材,既难且深,还特别侧重自己的研究方向(比如Maryland大学的Hanan Samet教授就特别偏重空间数据结构)。然而,值得我们注意的是,许多学者正积极倡导重新审视数据结构,将注意力放在如何挑选出合适的数据结构、设计并分析数据结构性能上,也即重新将数据结构作为计算机科学的一个重要研究主题。这种关于数据结构的新思路的重点在于:不要过多地将数据结构与面向对象揉合,要关注数据结构本身。事实上,作者的这种“百科全书”式努力的目的,正是为了让更多的人关注数据结构本身,而不是将数据结构和面向对象程序设计视为一体。从这个观点看,作者确实用心良苦。
当然,国内对于“数据结构”一直相当重视,各校都将其作为重要的基础课单独开设。而关于数据结构的这种新思路,不但值得借鉴,而且非常适宜于目前的课程设置。因此,我们需要一本纯粹的数据结构教材。考虑到国内的“数据结构”课程一直以《数》为范本,换言之,此书和目前国内的教学内容相当贴近,在不进行大改动的情况下,在“数据结构”的讲授和学习中采用这本教材,不但可以锻炼学生的基本能力,还将对他们今后的研究工作大有裨益。
5新版本,新译本
最早的《数》中文译本(对应1976年的英文版)于1983年出版,该译本极大地推动了数据结构在国内的普及,功不可没。此版的特色是对某些数据结构进行了公理化定义,如今的教材已不再讲解此内容。
2009年,清华大学出版社一次性引入《数》的两个版本(C语言版和C++语言版),分别由朱仲涛和张力老师翻译,该译本不但准确流畅,而且风趣诙谐。值得一提的是,朱仲涛所翻译的《数据结构基础(C语言版)》全书均采用LaTeX排版,还自行绘制了所有插图,从而使整本书异常精美。事实上,《数》英文版的版式略显粗糙,朱仲涛的译本从某种意义上说是对原书的再创作。翻看良久,确实叹服译者的敬业精神,这在当前的计算机专业图书翻译中是相当少见的。
目前,研究生入学考试在计算机专业课程中采用了统一考试的方式,不过2009年的考试成绩却不尽如人意,原因大约是没有一本材的缘故。我们不去评论考试形式的优劣,但准备考试的考生不妨以这本数据结构“圣经本”的译本作为教材,认真学习、备考,也许会有意想不到的效果。
6总结与展望
“数据结构”课程也需要不断改革和发展,但我们肯定不能完全照搬北美各大学的做法。从教材上说,从一本改良的教材入手,在此基础上逐步改进,或许能创出适合于自己的教材,进而推广先进的教学方式。《数》优点突出,尤其适合国内的数据结构教学现状,确实是一本难得的优秀教材,值得推广使用。
此外,《数》的姐妹篇《计算机算法》也于2008年推出了新版,我们希望尽快看到它的中译本。
参考文献:
[1] D. E. Knuth. The Art of Computer Programming Volume 1: Fundamental Algorithms[M]. 3rd ed . Addison Wesley, 1997.
[2] Hanan Samet. Foundations of Multidimensional and Metric Data Structures[M]. Morgan Kaufmann,2006.
[3] Dinesh P. Mehta, Sartaj Sahni. Handbook of Data Structures and Applications[M]. CRC, 2004.
[4] Hanan Samet. Data Structures Course 2003 [EB/OL].cs.umd.edu/class/fall2003/cmsc420-0101/.
[5] Peter Brass. Advanced Data Structure[M]. Cambridge University Press,2008.
[6] Ellis Horowitz, Sartaj Sahni. 数据结构基础[M]. 程惟宁,译. 北京:新时代出版社,1983.
[7] Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed. 数据结构(C语言版)[M]. 朱仲涛,译. 2版. 北京:清华大学出版社,2009.
数据结构篇2
关键字数据结构高效学习知识框架
1 引言
数据结构课程主要讨论各种数据组织中的逻辑结构、存储结构以及有关算法，研究如何根据实际应用的要求，对数据进行有效的组织、存储和处理，进而编制出高效率的程序，是一门逻辑性和实践性很强的课程。不少同学刚开始学习时，觉得这门课程很难学，知识点很多而且灵活多变，有些同学花很长时间学习该课程，却收效甚微。因此，如何充分利用时间，高效地学习数据结构成为很多同学共同关注的话题。
2 关于高效学习的界定
不同时期和不同课程高效学习的内涵与特征会有所不同，目前关于高效学习的定义主要有以下几种。
第一种定义认为高效学习应强调有效学习，认为那种死记硬背、生搬硬套的学习是无效的学习，不能够真正理解、灵活运用所学知识。
第二种定义认为所谓“高效”是指能够掌握有效的学习策略和思维策略，提高学习效率，从而既减轻学习负担，又提高学习质量。
这些“高效学习”的界定或强调学习的结果，对学习质量的要求侧重于认知和能力；或重视学习效率，但对学习结果没有给出具体的评价标准。本文所讨论的高效学习是指高效率、高效益的学习。高效益学习是学习效率追求的目标，而高效率学习是提高学习效益的前提。高效地学习数据结构，一方面指学生能充分利用时间，积极、主动地参与学习；另一方面是指学生能够达到获取知识、形成技能、培养能力的目的。
3 数据结构的高效学习
本课程的学习过程中，同学们应根据数据结构课程的特点，注意改进学习方法，提高学习效率，以达到高效学习的目的。此外，还应注意如下几个问题。
3.1熟悉课程大纲，学习循序渐进
要学好数据结构，首先应该熟悉课程的教学大纲。整个大纲是本课程的主体知识框架，所涉及的范围不是一些“点”的东西，而是“面”的东西。掌握课程大纲，就能容易地理清知识框架，抓住课程重点，可以充分利用有限时间掌握课程主要的知识结构。了解课程的知识框架和各种结构的关系后，可以从简单到复杂、循序渐进、逐步深入地学习。
例如，对图1所示的数据结构内容体系，可以围绕线性结构、树型结构、图型结构和查找、排序这两种重要的算法，以顺序和链式两种存储结构为贯穿整个课程的主线进行理论学习和实践学习。
对于每个章节的内容，也应该按照一定的流程进行学习。例如，首先掌握每章节的基本概念，再熟悉该结构的抽象数据类型定义和主要操作的实现方法，然后要理清算法实现的思路，以及算法实现的框架，最后通过上机调试进一步掌握该算法。
3.2不要过分关注数据结构的语言实现
数据结构是存在一种或多种特定关系的数据元素的集合，并不是“某种语言的”数据结构，它和具体语言无关。一些同学在学习数据结构的时候，往往不自觉地把数据结构与某种具体的程序设计语言（如C语言）联系起来。
例如，讲到数组时，同学的第一反应很可能是“[ ]”符号；说到链表时，也许很多同学首先联想到的是“*”符号。虽然在实际应用中，数据结构总是要由某种高级语言来实现，但在学习数据结构的过程中，如果过分关注于数据结构的语言实现，思想就会被束缚在这些语言的语法规范中。
学习数据结构时，应该关注的是不同数据结构的特点是什么，为什么要用这种数据结构，在什么情况下用什么样的数据结构，几种数据结构的联系和区别是什么……计算机程序设计语言作为数据结构的实现方式，是多变的，但数据结构作为框架和思想，是相对稳定的。学习数据结构，重要的是学习数据结构中的框架、原理和思想，只有理解和掌握这些，才能够很好地运用数据结构来解决实际问题。
3.3加深理解，培养思维能力
学习数据结构，特别是学习算法时，应重视对知识的深刻理解，理解得越深，学习效果越好。首先应该从根本上认识数据结构的本质、数据结构和算法之间的密切关系，对知识应该“知其然，也知其所以然”，不然很容易陷入各种数据结构的复杂特性中。
有部分学生学习数据结构时会做大量的习题，但希望大家了解数据结构课程的逻辑性很强，同学在学习过程中应注意培养自己的逻辑思维能力，锻炼理解能力，使自己分析问题的综合能力得到提高。无论做的题多还是题少，都应将解题过程当作训练自己思维的过程。应该在每次做完练习之后及时地归纳、整理、总结，从中找出自己的缺点加以补救，要注意比较，善于总结和反思，这样就能够做到举一反三，提高效率。
3.4重视实践
我们不过分关注数据结构的语言实现，并非不重视动手实践，而是因为学习并掌握数据结构中的框架、原理和思想，目的是为应用打好扎实的理论基础。
例如，在设计一个新的数据结构时，我们脑中产生的数据结构设计思路并不一定是完美的，而是不完备的，甚至是错误的。“实践是检验真理的唯一标准”，通过上机编写程序，可以验证想法的正确性。在动手实践的过程中，会遇到很多细节问题，这些是在思考时无法考虑到的，但对解决问题又是十分必要的。因此，动手实践的过程，实际上是培养完整、彻底地解决问题能力的过程。只有将理论与实践紧密结合，才能学好数据结构。
4 结束语
本文对于什么是高效学习进行了初步探讨，并结合数据结构课程的特点，讨论了高效学习数据结构需要注意的事项。
参考文献
1 张庆林.高效率教学[M].北京：人民教育出版社，2002
2 严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2002
数据结构篇3
关键词： 教学方法改革 降低理论性程度 增强直观性
《数据结构》课程是计算机及相关学科的一门重要的专业基础课，也是一门锻炼程序设计能力的实践课程。它相对于其他应用性课程来说抽象、枯燥，学生学习起来有一定的难度，教师讲起来也比较难。那么如何降低理论性程度，增强直观性，提高学生的学习兴趣呢？我在教学中尽量做到以下几点：
1.讲好第一堂课，以调动学生的学习兴趣
《数据结构》虽然包含了较多的理论内容，但具有实践应用的特点。“兴趣是最好的老师”。因此在进行数据结构课的第一次授课中，我并不急于介绍理论，而是强调应用，通过介绍数据结构在实际中的应用来激发学生的学习兴趣。如图书馆的书目检索系统，如何组织图书的登录号、书名、分类号等数据，才能快速实现查找、插入、删除操作；旅游线路设计问题，如想去北京、上海、天津等地旅游，怎样安排线路以求花费最少；在铁路建设中，如何施工以求花费最少，等等。以上应用贴近生活，学生都比较熟悉，兴趣就能够被激发起来，形成想学好这门课的愿望。其实上述例子就已经囊括了本门课中涉及的几大类数据结构――线性表、树和图，这样教师就可以水到渠成地归结出数据结构的概念，以及本章涉列的几种数据结构的类型，为后续章节的讲解打下了良好的基础。
2.解决C语言的不足
《C语言程序设计》是数据结构的前导课程之一，学生对它的熟悉掌握程度直接关系到数据结构课程的教学效果。C语言本身极具灵活性，刚刚学完C语言程序设计的学生运用不是很自如。另外，C语言的难点是指针、函数、数组作为函数参数，以及结构体类型等，而数据结构课程教学过程中主要运用这些知识点来分析、解决问题。对于大部分学生来说，C语言运用能力不是很强，如果上课时直接切入主题，他们就会有“云遮雾罩”的感觉。如何解决这个问题呢？我们可以利用一两次课的时间来复习C语言的相关知识，即数组、指针、函数和结构体等。可以将这些学时纳入到教学进度表中，教师在复习并不是面面俱到，而是将与本课相关的内容加以归纳总结，这样既可以复习以前的知识，加深印象，强化理解，又可以为数据结构课程的教学作铺垫。
3.教学内容的归纳提炼
不少教师常说《数据结构》这门课难讲，学生也反映这门课不好学，这是因为《数据结构》不但有很强的理论性，而且具有一定的抽象性。同时《数据结构》课程又有较强的实践性，要求学生能够使用一种语言(PASCAL、C、C++或Java)，对算法进行程序设计，并且能够进行上机调试，对于基础薄弱的学生这就好似“雪上加霜”。既然“教”与“学”都有困难，那么在“教”与“学”的过程中就应该首先解决教师应该怎么“教”的问题。教师首先应对理论概念和算法思想进行处理，避免“照本宣科”，教师自己要熟悉教材、精通教材，把握本课程的重点和难点，能够将前后内容联系起来分析思考，尽量从中寻找共性的、规律性的东西进行归纳与提炼，并将其系统化、具体化。例如从数据结构的定义出发包含三方面的内容：逻辑结构、存储结构和算法。在讲到每种数据结构(线性表、栈、队列、树、图)都会涉及它的逻辑结构、存储结构和算法。我在讲授的过程中用数据结构包含的三方面内容作为一条主线贯穿整本书，每讲到一种新的数据结构时都可以拿出这条主线来阐明其上的三方面内容，这样，学生学起来就会觉得有系统性，容易把握。综观全书，不论是线性表、树还是图，最基本的、典型的存储结构就是两类:顺序存储结构、链式存储结构，只要把它们掌握好，整个课程学习的难度就不觉得大。所以在教学过程中，我一方面紧扣课程的主脉(即各种数据结构的基本概念、逻辑结构、存储结构、主要算法与相关应用)，把基本的概念与术语解释清楚，把各种数据结构与操作运算分析清楚，把有关算法的设计思路与实现方法讲解清楚。另一方面，我更注重有关内容的前后呼应，把握其内在联系，对各种相关结构的特点与操作，进行相应的归纳、总结与对比。
4.教学模式的更新
“问题”是创新的起点，是引发学生兴趣、诱发学生动机的理想载体。《数据结构》教学中，特别是算法设计中可以设计许多问题。我在备课时，不仅消化教材内容，深入探究知识的奥秘，更精心设计课堂情景，准备好“问题”；课堂教学时不仅生动详尽地讲解知识，更努力激发学生思维；教学过程中不仅要求学生认真听，更引导学生积极思考，逐步培养学生发现问题、分析问题、解决问题的能力。例如，在讲到栈时，为了让学生掌握栈的特点，我让学生先用数组来编写算法，然后用栈进行编写，最后我来进行点评，让学生清楚了解什么情况下使用栈比较方便。这样既有助于讲清问题，又能提高学生的积极性。
5.加强实践环节
为使学生真正学好《数据结构》，我除了在课堂上采用行之有效的教学方法外，还让学生多做习题。要学好《数据结构》，只“看”不“练”肯定是不行的，习题的作用是极其重要的，学生不仅要做，而且必须交作业，这样我才能知道学生的掌握情况，然后对出现的问题进行总结、归纳、讲评。讲评时我细讲解题思路，规范解题方法，并强调有关的注意事项，同时，对于作业中的可取之处加以表扬，鼓励学生开拓创新。
当然实践还包括上机实验。上机实验不仅能进一步巩固对有关内容的理解，而且能提高学生灵活运用数据结构和算法的能力，使学生在编程、上机操作、程序调试与正确性验证等基本技能方面得到训练。
以上就是我在《数据结构》教学中的教学方法改革，有不当之处希望广大同仁多多指点。
参考文献：
［1］严蔚敏，吴伟民.数据结构.北京:清华大学出版社，1992.
数据结构篇4
一、大型作业（课程设计）题目和内容
1、用二叉链表作存储结构
（1）以回车（‘\n’）为输入结束标志，输入数列L，生成二叉排序树T；
（2）对二叉排序树T作中序遍历,输出结果；
（3）计算二叉排序树T的平均查找长度，输出结果；
（4）输入元素x，查找二叉排序树T，如果存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则输出信息“无结点x”；
（5）判断二叉排序树T是否为平衡二叉树，输出信息“OK!”/“NO!”;
*（6）再用数列L，生成平衡二叉排序树BT：当插入新元素后，发现当前二叉排序树BT不是平衡二叉排序树，则立即将它转换成新的平衡二叉排序树BT；
*（7）计算平衡二叉排序树BT的平均查找长度，输出结果。
2、用顺序表（一维数组）作存储结构
（1）以回车（‘\n’）为输入结束标志，输入数列L，生成二叉排序树T；
（2）对二叉排序树T作中序遍历,输出结果；
（3）计算二叉排序树T的平均查找长度，输出结果；
（4）输入元素x，查找二叉排序树T，如果存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则输出信息“无结点x”；
（5）判断二叉排序树T是否为平衡二叉树，输出信息“OK!”/“NO!”。
二、程序中所采用的数据结构及存储结构的说明
程序中的数据采用“树形结构”作为其数据结构。具体的，我采用的是“二叉排序树”。
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）它的左右子树也分别为二叉排序树。
程序中分别采用了“二插链表”和“一维数组”作为其存储结构。
二插链表存储结构中二插树的结点由一个数据元素和分别指向其左、右子树的两个分支构成。如：我的程序中采用的结构是：
typedefstructTnode{
intdata;/*数据元素*/
structTnode*lchild,*rchild；/*左右指针*/
}*node,BSTnode;
一维数组顺序表存储结构是用一组地址连续的存储单元依次自上而下、自左而右存储完全二插树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。利用顺序表作为存储结构：
typedefstruct{
int*data;/*一维数组基址*/
intlenth;/*一维数组的长度*/
}BST;
一维数组存储结构中结点i的父母亲为|_i/2_|,左孩子为2i，右孩子为2i+1.
三、算法的设计思想
a)二插链表作存储结构：
建立二插排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找成功则不应再插入原树，否则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。
对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。
计算二插排序树的平均查找长度时，仍采用类似中序遍历的递归方式，用s记录总查找长度，j记录每个结点的查找长度，s置初值为0，采用累加的方式最终得到总查找长度s。平均查找长度就等于s/i(i为树中结点的总个数)。
删除结点函数，采用边查找边删除的方式。如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论：1、该结点左右子树均为空；2、该结点仅左子树为空；3、该结点仅右子树为空；4、该结点左右子树均不为空。
判断二插排序树是否为平衡二叉树的函数，也是采用递归函数的方式，分别判定以树中每个结点为根结点的子树是否为平衡二叉树。只要有一个子树不为平衡二叉树，则该树便不是平衡二叉树。
b)一维数组作存储结构：
建立二插排序树，首先用一个一维数组记录下读入的数据，然后再用边查找边插入的方式将数据一一对应放在完全二叉树相应的位置，为空的树结点用“0”补齐。
中序遍历二叉树也采用递归函数的方式，先访问左子树2i,然后访问根结点i,最后访问右子树2i+1.先向左走到底再层层返回，直至所有的结点都被访问完毕。
计算二插排序树的平均查找长度时，采用类似中序遍历的递归方式，用s记录总查找长度，j记录每个结点的查找长度，s置初值为0，采用累加的方式最终得到总查找长度s。平均查找长度就等于s/i(i为树中结点的总个数)。
删除二插排序树中某个结点，采用边查找边插入的方式，类似重新建立一个一维数组作为存储新树的空间。将原数组中的数据一个一个的插入树中，若遇到需要删除的结点则不执行插入操作。
判断二插排序树是否为平衡二叉树的函数，也是采用递归函数的方式，分别判定以树中每个结点为根结点的子树是否为平衡二叉树。只要有一个子树不为平衡二叉树，则该树便不是平衡二叉树。
四、平衡二叉树与未平衡化的二叉树查找效率比较
(1)对于未平衡化的二叉树：
当先后插入的关键字有序时，构成的二插排序树蜕变为单支树。树的深度为n,其平均查找长度为（n+1）/2.这是最差的情况。这种情况下比较关键字的最大次数为n次。
(2)最好的情况是：
建成的树是一棵平衡二叉树。在这种情况下，二插排序树的平均查找长度和log2(n)成正比。比较关键字的最大次数为：0.5logψ（5）＋logψ(n+1)-2次（其中ψ＝（1＋根号5）/2）。
(3)那么，平均情况下分析：
假设在含有n(n>=1)个关键字的序列中，i个关键字小于第一个关键字，n-i-1个关键字大于第一个关键字，则由此构造而得的二插排序树在n个记录的查找概率相等的情况下，其平均查找长度为
：P(n,i)=[1+i*(P(i)+1)+(n-i-1)(P(n-i-1)+1)]/n
其中P(i)为含有i个结点的二插排序树的平均查找长度，则P(i)+1为查找左子树中每个关键字时所用比较次数的平均值，P（n-i-1）+1为查找右子树中每个关键字时所用比较次数的平均值。又假设表中n个关键字的排列是“随机”的，即任一个关键字在序列中将是第1个，或第2个，…，或第n个的概率相同，则可对上式从i等于0至n-1取平均值。最终会推导出：
当n>=2时，P（n）<=2（1＋1/n）ln(n)
由此可见，在随机的情况下，二插排序树的平均查找长度和log（n）是等数量级的。
五、时间复杂度的分析
说明：对时间复杂度的分析，均指在最坏情况下的时间复杂度。
二插链表存储结构中：
（1）查找函数最坏的情况是要找的点正好是二叉树的最深的叶子结点，此时时间复杂度＝O（n）。
（2）插入函数最坏的情况是要插入的点正是二叉树的最深的那一支的叶子结点，此时时间复杂度＝
O（n）。
（3）中序遍历函数，求平均查找长度的函数，删除函数以及判断二插排序树是否为平衡二叉树的函数，其时间复杂度均与以上情况类似，等于O（n）。
一维数组顺序表存储结构中：
（1）插入函数最坏的情况是要插入的点正是二叉树的最深的那一支的叶子结点，此时时间复杂度＝O（n）。
（2）创建函数最坏的情况就是调用插入函数时插入函数遇到最坏的情况。因此，创建函数的时间复杂度也等于O（n）。
（3）中序遍历函数，求平均查找长度的函数，查找函数，以及判断二插排序树是否为平衡二叉树的函数，其时间复杂度均与以上情况类似，等于O（n）。
（4）删除函数不采用递归手法，而是采用重新建立一颗不含要删结点的二插排序树。其时间复杂度＝O（n）。
六、心得和总结
这次暑假的课程设计作业我选择做数据结构是出于我对用高级语言编程的极大兴趣。通过这次实验我也着实又感受了一次编程的乐趣，从中也学到了不少知识。
虽然都说“程序＝数据结构＋算法”，但我在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。
我感受最深的一点是：以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。感觉有点像张飞打仗，有勇无谋，只要能完成任务就行。但现在编程感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么？然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。
另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。
我以前对递归算法一直很害怕，总是看不明白究竟这递归是怎么进行的。在这次实验中我终于克服了这一障碍，一次次单步执行书中递归函数的例子，并一遍遍在心中自己默默的走，终于弄明白了，真的是功夫不负有心人啊！同时我还根据自己的理解写出了类似的递归函数实现了新的功能，真是受益良多啊！
在这次实验中，我对参数的调用也进行了很多种尝试，已经能够相对准确的选择合适的参数形式来实现函数之间的数据传输交互了。
这次实验中我也出现过一些比较严重的错误。在用一维数组顺序表结构编写程序时我错误的运用静态链表来实现函数功能。这是我对基本概念理解的模糊不清造成的。我原以为只要采用一维数组作为存储结构它就一定也是顺序表结构，而实质上这根本是两个不相干的概念。后来在同学的指点下我意识到自己的错误。不过收获也很不少。至少我又练习了运用静态链表来实现同样的功能，同时我也发现两者在很多函数上是互通的，只需稍作修改即可移植。
数据结构篇5
摘 要 本文详细阐述了数据结构间的纵横联系，所谓“横向联系”是对各种数据结构研究都从逻辑结构、存储结构、操作运算三方面出发的模式思想，所谓“纵向联系”是以简单数据结构类型为基础来实现对较复杂数据结构类型的研究。 关键词 逻辑结构 存储结构 操作运算 横向联系 纵向联系
数据结构篇6
关键词：数据结构；算法；教学方法；教学手段；实践教学
中图分类号：G642.4 文献标识码：A 文章编号：1009-3044(2008)36-2938-01
The Exloration on Data Structure Teaching
ZHOU Si-lin,YIN Xu-dong
(Changshu Institute of Technology,Changshu 215500,China)
Abstract: "Data Structure" is a professional and basis course of computer specialty,and moreover,it is highly theoretical and practical.This paper combined with my own teaching practice,and elaborated some my experience and perspective in teaching about the course features.
Key words: Data Structure;algorithm;teaching method;teaching means;teach in Pratice
1 引言
《数据结构》在计算机科学中是一门主干课、专业基础课。主要介绍用计算机解决一系列问题、特别是非数值信息处理问题时所用的各种组织数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。本课程还是《编译原理》、《操作系统》、《数据库原理》等其他课程的重要基础。
本课程的目的是使学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用。培养、训练学生选用合适的数据结构、设计质量高的算法、编写风格好的程序等综合能力，并为后续课程的学习打下良好的理论基础和实践基础。因此，本文从教学方法、教学手段、实践教学等各个环节着手，不断改进以提高教学效果。
2 改进教学方法
《数据结构》课程中有许多抽象的概念和算法，要使学生掌握这些知识并取得良好的教学效果，就要求任课教师运用高效易懂的教学方法提高教学质量。
1) 正确认识本课程
《数据结构》这门课程比较抽象，容易被学生认为这是一门纯粹的理论课程，枯燥难学，没有兴趣将这门课程学好，甚而有部分学生认为不学《数据结构》照样能编程。所以从第一堂课开始，就要引导他们正确认识这门课程的性质和作用。通过编程中的实例来告诉他们这门课程的作用，如以前完成的C语言课程设计中链表的使用，编译程序中堆栈的使用，操作系统中队列的应用，文字处理软件中串的模式匹配的应用等；同时这门课程在本专业的各类考试中都是必考内容，如考研、各级软考、求职笔试等。通过这些学生能够感受到的实例，使学生正确认识这门课程性质，同时使学生产生对这门课程的兴趣，充分调动他们的求知欲，提高他们的学习积极性和主动性。
2) 问题导入教学法
本课程的基本概念很多，如果每堂课一开始就介绍大量的基本概念，教学效果不明显。因此，对于每一个内容，先提出问题，自始至终围绕问题展开教学活动，引导学生不断的发现问题、提出问题、解决问题，培养学生学习的主动性、创新性。比如在表达式转换、求值的问题讲解中，不是每碰到一个运算符就能马上运算，提出用什么存储结构来保存运算符的问题，再分析需要保存的数据具有的特性，然后再解决需要利用具有后进先出的栈来保存扫描过程中碰到的运算符。再如图的最短路径问题中，可以考虑提出问题，需要去杭州、普陀山、上海、苏州等几个城市旅游，如何选择路线最合算？围绕这个问题开始讲解图的最短路径问题，让学生有兴趣且比较容易接受抽象的概念和算法。
3) 由易入难，循序渐进
本课程中各类算法非常多，要引导学生依次灵活掌握各类算法。例如在讲解删除顺序表中某个数据元素的基础上，再提出问题：删除某顺序表中所有值等于key的元素。首先根据之前的解决思路，逐个进行扫描删除，算法的时间复杂度为O(n2)；然后再进一步分析该问题，在前面的移动数据元素的过程中，移动实际上可以一步到位，即对所有的不等于key的数据元素，可以一次将其移动到最后所在的位置，这样算法的时间复杂度就提高为O(n)。再如在串的模式匹配中，共有五次提到模式匹配的概念，第一个是利用五个最基本的操作实现Index( )操作，第二次是模式匹配BF算法，第三次是模式匹配KMP算法，第四次是next( )的求解，第五次是改进的nextval( )，依次在前问题的解决方案上提出新的问题并进行解决，得到新的解决方案，循序渐进的讲解各个算法。
4) 因材施教，层次分明一般理论课都采用大班上课，可能每个学生的基础不同、理解和吸收能力也不同，如果所有内容都在同一层次和高度，很可能造成“有的同学吃不了，有的同学吃不饱”的局面，因此课程内容的安排等方面都要分不同的层次以适合所有同学。授课的内容分基础部分和提高部分，对于基础部分，强调每个同学都必须掌握，对于有能力的同学，争取掌握提高部分，对于课后作业，也分为基础题和附加题，附加题增加一定的难度和趣味性，让大家主动的去完成。
3 提高教学手段
1) 教学手段多样化，生动教学过程
教学过程中合理利用教学手段，不但能提高效率，而且能生动课堂。通过制作动画在课堂上演示，比如：线性表中数据元素的插入和删除过程，栈和队列的应用，二叉排序树，平衡二叉树，各类排序等过程中数据元素的变化过程，通过动画演示生动易理解，而且节省时间提高效率。当然有的相对复杂的过程引入必要的道具也是有所必要的，如串的模式匹配KMP算法相关部分，非常的抽象，学生不好理解，可以拿出一条一条的串作为移动对象演示匹配过程，感觉比动画演示更加的贴切。所以课堂中不用拘泥于某一固定的手段，应该不断的找出更利于学生掌握的手段应用。
2) 利用网路平台，扩大课堂容量
充分利用教学网站，提供更多的信息支持教学。比如在教学主页上放上课程材料，如课件、作业、实践等相关内容。另外可以选择一些经典的参考书籍，典型的习题放上面，供同学课外进行练习和参考。同时利用网络平台提供多种交流方式与学生交流，做到知己知彼教学相长。
4 实践与理论并进
计算机相关专业学生的最终目标是要能设计实现出好的软件，因此，实践技能的提高才是教学的最终目的。实践课堂是理论课堂的延伸，是灵活运用理论的一个重要环节，起到让学生真正掌握和巩固所学知识的作用，因此本课程的实验教学也越来越得到重视。
精心选择实践内容，着重于基础知识知识点的应用，针对不同层次的学生，可以给予一定的参考资料或代码，能让所有的学生都能动手起来，不会有学生觉得无从下手。如对于线性表这一部分：顺序表、链表的存储实现、插入删除查找等基本操作的实现。另外可以在实验中给出提高难度的附加部分，激发掌握好的同学的潜能，提升兴趣，如单向循环链表的Joseph问题，双向循环链表的实现与基本操作等，使不同层次的学生都能理解并运用自己层次的内容。
5 结束语
《数据结构》是计算机专业的核心课程，同时也是程序设计的基础，因此要上好这门课程，必须分析教学对象，从教学方法、教学手段、实践教学等各个教学方面进行研究，激发学生的学习兴趣，让他们愿意学、努力学，并且能学好，以真正提高该课程的教学效果，达到教学目的。
参考文献：
[1] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2001.
[2] 杨永斌.“数据结构”教学策略探讨[J].合肥:合肥工业大学学报(社会科学版),2008（22）.
数据结构篇7
在大数据时代中，大数据的应用效能、应用方便度、应用当地覆盖面是未来大数据应用所关注的重点，而目前在大数据应用方面存在许多的问题，这些问题的存在影响了未来大数据的应用，如何解决这些问题，重现在开始从最基础方面开始，解决这些问题是大数据未来应用的重要工作。本文首先列举了目前大数据应用中存在的问题，分析了产生这些问题的原因，针对这种情况提出了基于基础数据结构体系建立的解决方案设想，为未来大数据应用发挥更大效益的解决方法。
【关键词】大数据 基础数据结构 软件工程 数据标准
随着智慧城市建设项目的开展，作为智慧城市建设的重要基础就是围绕大型基础数据平台的建设，在业界定义为大数据时代的来临。围绕大数据的概念，在全国范围内的各领域各行业都在大数据的如何组织、如何应用、如何共享、如何关联召开了各类研讨会。大数据应用的云计算技术、数据仓库技术等成为业内讨论的重要话题。本人认为，在做了这些工作后，应回过头来看一看，无论数据量有多大，都离不开基础数据结构与体系的建设，在此要阐明的一个基本观点就是在大数据时代更应该重视基础数据结果的研究与应用。
1 大数据的概念
什么是大数据， IBM 最早的定义是：将大数据的特征归纳为4个“V”（量Volume，多样Variety，价值Value，速Velocity），或者说特点有四个层面：第一，数据体量巨大。大数据的起始计量单位至少是P（1000个T）、E（100万个T）或Z（10亿个T）；第二，数据类型繁多。比如，网络日志、视频、图片、地理位置信息等等。第三，价值密度低，商业价值高。第四，处理速度快。最后这一点也是和传统的数据挖掘技术有着本质的不同。
在大数据概念中的第一条是数据量大，这是大数据的特点，而却随着信息系统应用的深入，数量的数量级也在不断的提高，这是毋容置疑的。我们在此要讨论的是第二条数据类型繁多的问题。
2 目前大数据应用存在的主要问题
随着信息化系统应用的深入，在社会、自然界、生活中所涉及的数据面越来越广，由此使得数据类型也越来越多，数据类型的数量在不断增加，这些数据类型之间的关系和相互关联性也越来越复杂，大数据量下的数据应用造成了困难。数据结构类型繁多造成问题主要表现在以下几个方面。
2.1 数据类型是有限量的认识不清楚
未来大数据情况下，数据类型是有限量的还是无限量的概念模糊，为此首先要么明确一个基本的概念，那就是，数据类型在繁多，但是数据类型的数量是有限量的，只是这个限量的数量级大一些而已。在数据类型是有限量的情况下，对于解决数据类型繁多的方法是完全不同的。
如果数据类型的量是无限量的，那么解决问题的方法是要研究解决数据类型问题的方式是研究规律，拿出解决问题的方式与方法，对于具体数据类型时，按照方式方法理论与技术去解决问题。如果数据类型是有限量的话，那么解决问题的方式就不只是从理论上的解决问题方法，而应该更加切合实际的去针对每一种数据类型直接进行研究，形成数据标准，指导各个系统对每一个具体数据类型的应用。
2.2 相同数据在不同系统中的表现类型繁多
由于系统开发方各自的开发经验、所开发系统的规模不同，系统应用方对系统要求不同，系统应用行业的不同，使得在开发过程中，对于数据类型的定义只遵循本系统使用需要进行定义，没有完整的标准，即是有相应的国家或国际标准，也不能完全遵循。
2.3 各个行业制定的标准相互矛盾
各个行业在制定相应的标准时，是以满足自身需要为主导，造成了数据类型在其数据定义时不但长度不同，就是数据类型都不相同。这也就造成了各个系统在未来大数据应用中出现了严重的数据应用障碍。
2.4 大数据应用的实现效率低
由于不同系统技术数据结构的不统一，使得对于大数据的应用上要对不同系统的数据结构进行分析，构建关联，而后才能进行数据的应用，这项工作的工作量大，技术含量高，降低数据的应用效率。这些都是事后分析数据存在的问题。
2.5 数据浪费巨大
由于数据各个系统间数据结构的不同，加上分析手段的局限性，使许多的数据无法进行使用，由此也降低了数据的使用率。并造成数据的大量浪费。
3 造成目前对大数据应用存在问题原因
由于以上几方面的问题存在，为了做好大数据的应用，许多相应的技术应运而生，数据仓库技术、网格技术、云计算的数据处理技术等等。这些技术促进了数据应用的发展，提高了数据应用效率，为大数据应用发挥了巨大作用。但是这种做法只能针对具体的大数据应用项目起到作用，不能从根本上解决问题。那么造成这种问题根本是什么呢？
3.1 理论基础有偏差
目前所有这些高精尖技术的发展，为大数据应用的发展起到了不可替代的作用，但是这些技术在理论出发点上存在偏差，那就是，这些技术的理论出发点设定的是，数据类型是无限量的，是无穷尽的，所以所有的技术研究都不面对具体的数据项，这样做的结果是促进技术的发展，弊端是不能面对具体的应用，所有的技术应用都要在这就技术下进行二次应用研究。也就是，这些理论是治标不治本的做法。
有限量数据类型与无限量数据类型是两个根本不同的概念，对于技术的发展影响也是完全不同的。为此，目前在无限量数据类型概念下的大数据应用技术与体系将会存在极大的局限性，对未来的大数据应用造成影响。
3.2 对大数据认识有偏差
目前在各个系统对大数据的应用中，对大数据的认识是，只要有足够量的数据，就是大数据，而对于数据之间的关系，整体的数据结构体系没有很深的认识，甚至将原有的多个分散的系统中的数据库，做一个小的关联数据库，就认为是数据云计算，就是综合数据平台了，而在这种情况下，对于大数据的应用，因为系统的独立，数据库的独立、数据结构的不统一造成了大数据应用的瓶颈和障碍，在系统应用到一定程度后，数据量是很大，但是无法进行大数据应用，或者说是要进行大数据的应用，需要另外投入很高的成本进行数据整理、数据管理和数据分析。所以应该明确的是，在数据结构混乱的情况下，在大的数据量也不能称为大数据，这个观念上的偏差，是造成目前数据应用困难的原因之一。
3.3 数据结构不规范
这些情况的出现，归结的一起，就是数据结构不规范，不统一。在三方面主要原因造成这个局面，一是目前的应用系统的开发，由不同的公司进行，每个开发单位对数据结构的定义有各自的标准，基本都是按照多年开发经验总结出来的，因此各个公司开发的系统在数据结构上相差很远。二是对于同一个公司不同时期开发的系统所涉及的数据结构不统一，到后期，开发单位不愿意在投入成本对前期开发的系统进行重新开发，这就造成了前期开的的系统中的数据结构与后期开发的数据结构不统一。三是对于应用开发单位在开发每一个具体应用项目时，由于是不同的开发小组在进行，为此，在进行数据结构设定时，只为了满足本系统开发的需要，而没有考虑系统未来的发展和系统的整体架构，这也造成了不同应用系统中对相同字段的设定不相同，数据结构不统一。以上这些都是在应用系统开发过程中遗留的问题，而这些问题严重影响了大数据的使用。
3.4 有统一的标准不用
在系统开发过程中涉及的数据结构，许多都有相应的标准，主要有以下几个方面，一是国家法律层面的，对于一些重要的数据要求以立法方式进行规范。二是国家标准，制定和规范了国家层面的有关方面的数据要求和限定。三是部颁标准，由各个部委办局制定的相应标准，这些标准有一大部分直接针对信息化系统建设的应用和数据标准。四是行业标准，作为每一个行业内进行行为约束的标准，这种标准虽然不具备强制性，但是在行业内是一个自觉遵守的标准。四是国际相关标准，虽然国际标准没有任何的法律约束性，但是为了走出去，各行各业都在遵循这个标准。
这些标准都是在系统建立时的数据结构依据，但是目前许多系统在进行数据结构设定时，都没有按照这些标准执行，而是根据自己系统的需要进行设定的。这使得许多的系统中的数据不能相互交换使用，由此而影响了大数据的应用。
3.5 不同行业对标准的设定不统一
在国家标准体系中，由于标准制定的年代不同，同是一个部门颁布的标准对相同的数据要求也不同，各个部门由于独立制定标准，同样出现相同数据在不同部门制定的标准中规定的不同，这几方面原因也就造成了即使遵照标准，也存在着相同数据在不同应用系统中的数据结构不同的现象。
以上是大数据应用问题出现的主要原因，作为大数据应用的刚刚起步阶段，应针对这些问题进行研究给出相应的解决方案，为未来大数据应用的发展打下一个良好的基础，避免今后的大数据应用走弯路。
4 解决大数据应用问题的对策
解决大数据应用存在的问题，应从最基础的数据结构建立开始，从根本上去解决问题，也为未来大数据应用的发展打下一个良好的基本数据结构基础，对此提出以下几方面的对策。
4.1 开展和加强对基础数据结构建立的理论研究
从软件工程学的角度出发，以数据结构类型是有限量的概念为依托，围绕具体的数据类型开展数据结构体系的理论研究。依托一个数据结构分类的理论体系来支撑整个数据结构体系的划分，其中包括划分方法、划分层次、划分的软件工程学理论支撑等内容，制定大数据底层数据结构划分的理论体系，形成在大数据下的数据结构构建的理论体系。
4.2 开展对具体数据结构的研究
按照建立的数据结构理论体系要求，对每一个具体数据结构进行研究，针对数据项的名称、类型、含义、层次、结构、与其他数据的关系、涉及内容规定等方面制定出具体数据的标准。这项工作可以在有组织的情况下由全社会共同参与，按照指导理论的要求进行研究，这样，随着应用系统的不断深入，所涉及的数据类型项将逐步扩展，最终实现数据的全覆盖，而完成整个架构体系的建立。
4.3 制定相应的数据结构标准
对于由各个方面制定的数据结构进行分类、筛选、审核，而后想这些结构形成一个统一的架构体系，制定相应的技术标准，通过这个标准来规范应用系统的开发，形成完整的、规范的、统一的数据结构体系，为大数据应用打下坚实的基础。
4.4 成立相应的机构来负责这项工作的完成
对于这项工作的开展，应在软件工程相应的有关组织下，建立一个专门的机构，负责指导这项工作的完成。由这个机构成立专门的实验室，负责整体架构的制定，数据类型项的搜集、分类、筛选，并形成统一的数据库体系，为所有的应用系统的开发提供数据库基础支撑和服务。
综上所述，通过对基础数结构的研究与体系的建立，从根本上解决大数据应用的效率，充分发挥未来大数据的作用，简化大数据应用的方式与过程。
参考文献
[1]严霄凤，张德馨.大数据研究[J].计算机技术与发展，2013（04）.
[2]李学龙，龚海刚.大数据系统综述[J].中国科学：信息科学，2015（01）.
[3]方璐.大数据时代的科学研究方法[J].浙江工业大学，2014.
作者简介
李铧（1962-），男，江苏省无锡市人。学士学位，现为无锡科技职业学院教师、高级工程师。主要研究方向为软件工程学、物联网概论。
作者单位
数据结构篇8
关键词：实时数据库；索引；信息化
中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）15-0008-02
1 实时数据库简介及应用背景
实时数据库是一种特殊类型的数据库，目前广泛应用于电力、石油、石化、交通、航空、水利、环保等重要领域，在“信息化与工业化融合”过程中发挥着重要作用。
目前数据库技术广泛应用于工业控制、企业MES环境、智能交通、智能楼宇、通信等领域。这些应用的特点主要有：维护大量共享数据和控制数据；有很强的时间性，要求在规定的时刻或在一定的时间范围内完成处理；而且，所处理的数据有一定的有效时间，过时则会有新的数据产生，所以，这种应用对数据库和实时处理功能及特性均有需求。但传统的数据库系统主要处理永久、稳定的数据，强调维护数据的完整性、一致性，考虑有关数据及其处理的定时限制。所以，传统的数据库管理系统不能满足这种实时应用的需要。
2 实时数据库的特点
实时数据库所面向的应用领域有如下特点：
1）单位时间内响应的数据量很大
例如：一个企业的SIS系统使用实时数据库来存储数据，需要处理的测点数量超过一万。这些测点的变化周期通常在1秒钟之内，即，超过一万点的数据在1秒钟之内要保存到数据库中。
2）存储数据的量大
实时数据库的核心就是对大量实时信息进行处理，大量的数据将占据大量的硬盘空间。如果同时处理一万点的系统，每 1秒钟存储一次，每次单点占用 8个字节，那么保存10年的数据量将有 10000*8*10*365*86400=25228800000000字节，接近 23TGB。
3）时效性非常强
由于每个需要处理的测点的值都与时间相关，一秒钟之后的数据与一秒钟之前的数据很有可能就不一样，所以在保存测点值的同时，必须通过某种方法将其对应的时间也纪录起来。
3 实时数据库的历史数据存储结构及索引机制
实时数据库的历史存储模块是整个实时数据库的核心的部分。对用户提供数据存储和查询的作用。该模块面对的需求有以下特点：
1） 数据量巨大。如果数据不设置压缩，一个测点一秒存储一次，那么一天就有86400条记录。每个数据库有10万个左右的测点。数据库运行时间都在几年以上。产生的数据量会很巨大。
2） 用户对数据的访问方式特殊，多数情况下用户查询一个测点一段时间的数据。如查看某个测点一天内的趋势。
3） 插入新数据并更新索引的效率必须非常高。因为在现实应用中实时数据库不停的写入新的实时数据。如果存储并更新索引的效率低，会影响整个数据库的效率。
4） 在不影响读写效率的前提下，必须尽可能地节省磁盘空间。
3.1 存储结构及索引机制
针对以上的需求特点，设计了特殊的存储和索引机制。主要特点如下：
1） 在磁盘中以页为基本单位进行数据存储。每个页的大小为4K。
2） 按照每条记录的时间戳建立索引，索引只访问到页，而不是页内的每条记录。
3） 每个页内存放的记录都是属于一个测点。并且页内所有的记录都按照时间戳严格升序排列。
4） 属于同一个测点的所有的页的时间区间，都不存在交集。如果由于特殊情况造成了交集，必须通过拆分、移动页，来避免交集。
5） 对于已经写满的归档文件采用B+树的数据结构组织索引。如果归档文件已经写满，重新生成B+树的索引。提高查询效率。
6） 对于当前活动的归档文件采用链表的数据结构组织索引。提高实时数据归档的效率。只需要将新的页的地址添加到链表的尾部即可。如果采用B+的索引方式，需要进行复杂的树的平衡操作，影响了写的效率。
整个实时数据库的存储结构如图1所示：
3.2 B+树的索引机制
B+树是B树的一个变种，因此必须先介绍B树。
B树也叫平衡多路查找树。B树是一个平衡多路查找树结构。与二叉查找树，平衡二叉查找树，红黑树等树结构相比虽然查找的时间复杂度相同都是O（logN）。B树是一种多叉的树结构，树的深度更低。降低了磁盘I/O频率，从而提高了访问及查询效率。
一个n阶的B 树 （n叉树）的特性如下：
1）树中每个结点最多有n个孩子（n>=2）；
2）除根结点和叶子结点之外，其他每个结点至少有[ceil（n / 2）]个孩子（其中ceil（x）是一个取上限的函数）；
3）如果根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
4）所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息（可以看做是外部接点或查询失败的接点，而实际上这些结点不存在，指向这些结点的指针都为null）；
5）每个非终端结点中包含有m个关键字信息： （n，P0，K1，P1，K2，P2，…，Km，Pm）。其中：
a）Ki （i=1…n）为关键字，且关键字按顺序升序排序K（i-1）< Ki。
b）Pi为指向子树根的接点，且指针P（i-1）指向子树种所有结点的关键字均小于Ki，但都大于K（i-1）。
c） 关键字的个数m必须满足： [ceil（n/2）-1]
B+树：是B树的一个变种，相对于B树在每个叶子节点增加了指向下一个叶子节点的指针。
一棵n阶的B+树和n阶的B树的差异在于：
1）有m棵子树的结点中含有m个关键字（B 树是m棵子树有m-1个关键字）
2）所有的叶子结点包含了全部关键字的信息，以及指向含有这些关键字记录的指针，而且叶子结点本身依关键字的大小自小而大的顺序链接。 （B 树的叶子节点并没有包括全部需要查找的信息）
3）所有非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。
B+树广泛应用于文件索引和数据库索引中。无论是随机查找还是顺序查找，都表现出了很好的效率。
目前电厂厂级监控信息系统SIS是实时数据库主要应用领域。SIS系统是介于DCS系统和MIS系统之间的具有独立功能的系统，它的核心是实时数据库。实时数据库向下负责集成各个不同控制系统的实时数据，而且能够长期保存这些历史数据。向上可以提供开放的实时数据库和历史数据服务，为ERP系统所用。实时数据库开发的其他模块，例如：生产过程监控，厂级机组性能计算，经济指标分析，优化运行操作指导，故障诊断等，可以帮助企业提高自身的生产力和竞争力。
参考文献：
[1] 张志檀.实时数据库原理及应用[M].中国石化出版社，2001.
[2] 张少敏，李志雄.一种面向智能电网的实时数据库数据完整性方法[J].电力系统自动化，2013，37（13）：93-98.
[3] 李蔚，盛德仁.火电厂SIS系统中实时数据库平台的选择[J].中国电机学报，2003，23（12）：218-221.
[4] 刘云生.实时数据库系统[M].科学出版社，2012.
[5] 曹志英，李冠字，谢益武，等.企业现有应用系统的概念层数据整合技术与方法[J].计算机工程与应用，2003，39（8）：222-224.