・ｌ８８・ 价值工程 数据结构论述 Ｔｈｅ Ｄｉｓｃｕｓｓｉｏｎ ｏｆ Ｄａｔａ Ｓｔｒｕｃｔｕｒｅ 庞新法ＰＡＮＧ Ｘｉｎ—ｆａ （陕西党校科技教研部，西安７１００６１） （Ｓｈａａｎｘｉ Ｐｒｏｖｉｎｃｅ Ｐａｒｔｙ Ｓｃｈｏｏｌ ｏｆ ｔｈｅ ＣＰＣ，Ｘｉ ａｎ ７１００６１，Ｃｈｉｎａ） 摘要：数据结构是计算机及相关专业的基础课程，是提高计算机程序设计能力的必要条件。数据结构是介于数学、计算机软件和 计算机硬件之间的一门课程，它是计算机程序设计、数据库、操作系统、编译原ＪＥ￣ｓ－智能等重要基础，广泛的应用于信息学、系统 工程学等各种领域。本文简述了数据结构的基本概念，基本原理，运算方法。 Ａｂｓｔｒａｃｔ：Ｄａｔａ ｓｔｒｕｃｔｕｒｅ ｉｓ ａ ｂａｓｉｃ ｃｏｕｒｓｅ ｉｎ ｃｏｍｐｕｔｅｒ ａｎｄ ｒｅｌａｔｅｄ ｐｒｏｆｅｓｓｉｏｎａｌ ｗｈｉｃｈ ｉｓ ａ ｎｅｃｅｓｓａｒｙ ｃｏｎｄｉｔｉｏｎ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ａｂｉｌｉｔｙ ｏｆ ｃｏｍｐｕｔｅｒ ｐｒｏｇｒａｍｍｉｎｇ．Ｔｈｅ ｄａｔａ ｓｔｒｕｃｔｕｒｅ ｉｓ ａ ｃｏｕｒｓｅ ｂｅｔｗｅｅｎ ｍａｔｈｅｍａｔｉｃｓ，ｃｏｍｐｕｔｅｒ ｓｏｆｔｗａｒｅ ａｎｄ ｃｏｍｐｕｔｅｒ ｈａｒｄｗａｒｅ ｗｈｉｃｈ ｉｓ ｔｈｅ ｉｍｐｏｒｔａｎｔ￣ｕｎｄａｔｉｏｎ ｏｆ ｃｏｍｐｕｔｅｒ ｐｒｏｇｒａｍ ｄｅｓｉｇｎ，ｄａｔａｂａｓｅ，ｏｐｅｒａｔｉｎｇ ｓｙｓｔｅｍ，ｃｏｍｐｉｌｅｒ ｔｈｅｏｒｙ ａｎｄ ａｒｔｉｉｆｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ，ｉｔ ｉｓ ｗｉｄｅｌｙ ｕｓｅｄ ｉｎ ｉｎｆｏｒｍ￣ｉｏｎ ｓｃｉｅｎｃｅ，ｓｙｓｔｅｍ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ｏｔｈｅｒ ｆｉｅｌｄｓ．Ｔｈｉｓ ｐａｐｅｒ ｂｒｉｅｆｌｙ ｉｎｔｒｏｄｕｃｅｓ ｔｈｅ ｂａｓｉｃ ｃｏｎｃｅｐｔ，ｐｒｉｎｃｉｐｌｅｓ ａｎｄ ｏｐｅｒａｔｉｏｎ ｍｅｔｈｏｄｓ ｏｆ ｄａｔａ ｓｔｒｕｃｔｕｒｅ． 关键词：数据结构；逻辑结构；物理结构；算法 Ｋｅｙ ｗｏｒｄｓ：ｄａｔａ ｓｔｒｕｃｔｕｒｅ；ｌｏｇｉｃａｌ ｓｔｕｃｔｒｕｒｅ；ｐｈｙｓｉｃａｌ ｓｔｕｃｔｕｒｅ；ａｌｒｇｏｒｉｔｈｍ 中图分类号：ＴＰ３—０ 文献标识码：Ａ 文章编号：１００６—４３１１（２０１４）０７—０１８８—０２ ０引言 数据结构＝数据＋结构，既有数据又有结构，结构就是 关系，根据关系确定结构，结构又体现关系。本门课程所要 １基本概念和术语 １．１数据数据就是计算机化的信息。 １．２数据结构的概念如果从数据元素之间的组织形 研究的主要问题，第一，根据数据之间的逻辑关系如何组 式来看，可以认为数据结构指的是计算机所处理的数据元 数据元素都不 织这批数据？第二，如何将这批数据存储在计算机的存储 素之间的组织形式和相互关系。自然界中，器中？第三，对于存储在计算机中的这批数据可以进行那 是孤立存在的，它们之间必定存在着某种固有的必然的内 些操作？这些操作如何实现？同一问题的不同解决方法好 在的关系或者是根据需要人为定义的关系，这种关系就是 这些数据元素的数据结构。 坏如何进行评价？ 数据结构一般包括以下三个方面的内容： １．２．１数据元素之间的逻辑关系，即数据的逻辑结构， 作者简介：庞新法（１９６２一），男，陕西礼泉人，副教授，研究方向为 计算机教学。 是用户根据需要而建立起来的。是用户看到的感觉到的表 ３－２．１数据库安全需求由于本系统是面向Ｉｎｔｅｍｅｔ 功能，该部分不仅要完成流转这一基本功能，还牵涉到工 开放的，所以说数据库的安全是非常重要的。为了确保数 作流实体对象的持久化，工作流事务等方面。Ｍｏｎｉｔｏｒ主要 据库的安全可靠，本系统将应用服务器和ＷＥＢ服务器以 判断是否有超时的过程实例或者节点实例存在，但 及数据库服务器分开隔离。将应用服务器和数据库服务器 Ｍｏｎｉｔｏｒ不对发现的超时对象进行处理，而是采用消息通 安置在第二级防火墙的内部网络上，这样用户就无法直接 信的方式，通过引擎消息队列通知Ｅｘｅｃｕｔｏｒ来处理这些超 访问到网站数据库。对于数据库本身，还需要设定好用户 时的对象＿８Ｉ９１。 密码级别和用户权限。数据库的备份和恢复是必不可少的 参考文献： ［１】冯栋．浅谈高等院校办公自动化系统构建的必要性［Ｊ］．电脑 份工作，备份和恢复对于维护数据库十分重要。在面对 ２０１０年８月． 系统故障造成数据丢失或损坏时，可以通过备份的数据库 学习，［２］盛宇华，朱晓锋．企业办公自动化管理系统［ＭＪ．科学出版 快速地恢复数据，可以有效地减少或者减免损失。 一３．２＿２网络安全需求２００４年７月． 网络安全是指网络系统的硬件 社，和软件以及系统中的数据信息受到保护，不因意外或者人 ［３１汪维清主编．ＡＳＰ．ＮＥＴ Ｗｅｂ程序设计与应用ｆＭ］．清华大学 出版社．２０１１：０８． 为恶意的破坏，系统能连续正常地运行，网络服务不中止。 网络安全不仅仅包括网络安全产品，是一个比较复杂的系 统工程。具体到某一个网站上还涉及到它的功能和需求以 ［４］ｑｚ能斌．数据库系统原理【Ｍ］．北京：电子工业出版社，２０１０． ［５】傅勇，王儿珍．工作流技术在办公自动化系统中的应用研 究［Ｊ］．小型微型计算机系统，２００１，６． 及与之相配套的安全策略。从网络安全产品的多种多样， 【６］元春欣，江建慧主编．安全关键计算机系统［Ｍ１．中国铁道出 除了防火墙外，还包括安全评估系统、入侵检测系统、和防 版社，２ｏ０３． 病毒产品等等。而每一种安全产品都是构建在一种或几种 ［７】夏听，曹晓钢，唐勇主编．深入浅出Ｈｉｂｅｒｎａｔｅ［Ｍ］．电子工业 安全技术之上的【６ｊ７１。 出版社。２００５：６． ３．３工作流引擎的系统结构的设计本论文设计的工 ［８］Ｔｏｍ Ｂａｅｙｅｎｓ著．工作流现状［Ｍ１．丁宏译．中国水利水电出 作流引擎被划分为了两个功能子系统：Ｅｘｅｃｕｔｏｒ和 版社．２００６：３． Ｍｏｎｉｔｏｒ．Ｅｘｅｃｕｔｏｒ实现了绝大多数的复杂工作流程的流转 ［９ 长海藩．软件工程［Ｍ］．人民邮电出版社，２００４年８月． Ｖａｌｕｅ Ｅｎｇｉｎｅｅｒｉｎｇ ・１８９・ 面的就是逻辑的。例如逻辑上计算机认识十进制物理上计 两大类。顺序存储的特点是数据在内存中存放时每个单元 算机只认识二进制。逻辑上感觉计算机有四个硬盘Ｃ、Ｄ、 彼此相邻，即逻辑上相邻的结点物理上也必须相邻。非顺 Ｅ、Ｆ，物理上计算机只有一个硬盘，Ｃ、Ｄ、Ｅ、Ｆ称为四个分 序存储则比较灵活，可以将数据分散存储在内存中，即逻 区。不穿高跟鞋，物理高度１．７米，穿上高跟鞋逻辑高度 辑上相邻的结点物理上不一定相邻。常用的非顺序存储有 Ｉ．７５米。 链式存储、Ｈａｓｈ存储和索引存储。 １－２＿２数据元素及其关系在计算机存储器内的表示、 存贮，即数据的存储结构，又称数据的物理结构。 １．２．３数据的运算，即对数据元素所进行的操作。 可以把数据结构定义为：对计算机处理的一批数据， ３．１顺序存储结构优缺点优点：随机存取，省时间。 存贮效率高，省空间，无额外附加的链接信息。缺点：插入 删除要移动大量数据。 ３．２链式存储结构优缺点优点：插入删除无需移动 首先按某种逻辑关系把它们组织起来，再按一定的存储表 数据。缺点：顺序存取，费时间。存贮效率低，费空间，有额 示方式把它们存储在计算机的存储器中，然后给这批数据 外附加的链接信。规定一组操作。如对学生的管理，有成千上万个学生，先按 一４算法（Ａｌｇｏｒｉｔｈｍ） 简单地说，算法就是计算的方法、解决特定问题的方 （非顺序）结构存于内存，尔后对学生定义操作，增加、删 法。严格地说，算法就是操作的集合。例如：将一组给定的 数据由小到大进行排序，解决的方法有若干种，而每一种 除、修改、查询、统计、排序、打印等。 排序方法就是一种算法。 ２逻辑结构 个接一个的顺序组织所有学生，再按顺序结构或链式 ４．１算法的特性①有穷性。一个算法在执行有限条 根据数据元素之间的不同特性，可以把数据的逻辑 永远没有结束。②确 结构分为四种基本类型：集合、线性结构、树形结构和图 指令后必须要完成，不能无限次进行，定性。每条语句必须含义清楚，不能有二义性。③可行性。 ｒ，必须有待 ２．１集合集合中的数据元素之间除了“同属于一个 所有操作均可实现。④输入。算法用于数据３Ｄ－集合”的关系外，没有其它任何关系。大街上人来人往的人 加工的数据。⑤输出。算法用于数据加工，必须有对数据加 程序可以不满足上述的有 群可以看成是一个集合。集合是数据结构的一种特例。大 工的结果。算法程序有所不同，穷性。例如，Ｗｉｎｄｏｗｓ操作系统在用户未操作之前一直处 形结构。 街上人来人往的人群除了其共性属于人类以外，人与人之 于“等待”的循环中，直到出现新的用户操作为止。 间没有任何关系。 ４．２算法的评价标准对于一个特定的问题，采用不 ２．２线性结构数据元素之间存在一个对一个的前驱 一后继关系。火车站熙熙攘攘的人群，是集合关系，人与人之 同的存储结构，其算法描述一般是不相同的，对于解决同 问题的不同算法，如何评价哪一种算法较好，这就是算 间无任何关系，但一旦排成长长的购票队列，人与人之间 法评价。 就有关系，我在你前，你在我后，我的前边有且仅有一个 算法优劣标准：正确性。一个算法能否正确地执行预 人，我的后边有且仅有一个人，人与人之间就有前后关系， 先的功能，这是评价一个算法的最重要也是最基本的标 就是线性结构。 ２．３树形结构自然生活中，家谱、行政组织机构、语 法结构树。即每个结点最多只有一个直接前驱，每个结点 可以有多个直接后继，只有一个结点没有前驱，称为根结 点，叶子结点没有后继结点，它是一种层次结构。中国是由 省、市、区县、镇、乡村，户，个人的层次结构就是一种典型 的树形结构，中国是根，而个人就是叶子，ｗｉｎｄｏｗｓ的文件 夹就是一个倒立的树。一个父亲几个儿子，一个ｊＬ－Ｔ－有且 仅有一个父亲就是树形结构。 ２．４图形结构数据元素之间是任意关系，一对一、一 准。其要求是：①可读性：可读性好能帮助人们更好的理解 算法、更方便的排除算法中潜在的错误、更重要的是便于 算法的交流、改进和移植。②健壮性：算法应具有很强的容 错能力，即算法能对非法数据的输入进行检查和处理，不 会因非法数据的输入而导致异常中断或死机等现象。③运 行时间：算法中每条语句执行时间的总和。执行时间越短 则算法的效率越高、性能越好。④占用空间：占用空间是指 算法在计算机存储器上所占用的存储空间。越节省存储空 间，算法越好。 实际上，算法的时间效率和空间效率经常是一对矛盾 对多、多对多均可。树形、线形均可看作是图形的特例。即 体，二者很难求全，有时增加辅助的存储空间可以加快算 每个结点可以有多个直接前驱，也可以有多个直接后继而 法的运行速度，即用空间换取时间：有时因为内存空间不 形成的网状结构。四通八达的公路网就是图形结构。计算 够，必须压缩辅助的存储空间，从而降低了算法的运行速 机网、电网、通信网、销售网等都是图形结构。树形结构和 度，即用时间换取空间。其中运行时间，占用空间是衡量一 图形结构统称非线性结构。 个算法好坏的两个主要标准。 ３存储结构 ５结语 存储结构也就是物理结构，数据在计算机中如何存 编程就要涉及大量数据的处理，为了提高程序运行效 放、安排、组织、表示。既有数据元素的表示又有关系的表 率，必须对数据进行有效组织，本文简述了数据的逻辑结 示。按照关系确定表示，表示又反映出关系。如５在计算机 构，存储结构以及算法。 中如何表示，一５在计算机中如何表示，小数在计算机中如 何表示等。数据在内存不能乱堆乱放，为了节省空间、提高 查找速度必须对大量数据在内存进行有效组织。 存储结构可以分为顺序存储结构和非顺序存储结构 参考文献： 『１１王国钧．数据结构ｆＭ１．科学出版社． 『２１方贤进．数据结构ｉｒａ］．国防科技大学出版社． ｆ３１赵文静．数据结构［Ｍ】．科学出版社．
