第19卷 第12期2003年12月
甘肃科技
G ansu Science and T echnology
Vol.19 No.12
Dec. 2003
字符串处理中常用的几种数据结构及其性能分析
郑丽英1,李永昶2
(1.兰州交通大学信息与电气工程学院,甘肃兰州 730070;2.兰州交通大学机电工程学院,甘肃兰州 730070)
摘 要:许多计算机应用涉及字符串处理。为了提高处理效率,设计一个好的数据结构十分重要。分析了几种常用的字符串数据结构及其性能,重点分析了数据结构T rie及其三种形式的结构特性。关键词:T rie;数据结构;索引
中图分类号:TP311
1 前言
许多计算机应用都涉及到对一个非常大的字符串集合的有效管理。例如,从档案管理、文献目录查找、地理信息索引到Web上大量的文本信息处理等等,都涉及到对一个非常大的字符串集合的管理。显然,如何有效管理大的字符串集合的首要问题是如何存储和组织它们即选择一个合适的数据结构。在实际中为一个应用选择一个好的数据结构取决于许多因素,如存储需求、查找速度、是否在内存、是否要求有序存储等等。已有许多用于字符串管理的数据结构,下面将分别进行分析和讨论。
2 常用的字符串数据结构
2.1 BST树
BST树((Binary Search T ree,即二叉搜索树)是最简单且最直观的一种。在一棵BST树中,每一个结点存储一个字符串和两个分别指向左右孩子结点的指针。在BST树中查找一个给定的字符串的过程是:首先和根结点的字符串比较,若相等则查找成功。若不相等则按比较结果决定沿左分支或右分支继续比较。BST树的结构性能主要取决于树的形态,与输入字符串集的排列有关。假设字符串集合的分布是稳定的、且常用词的集合是已知的且常用词分布在根结点的附近,则BST结构是相当快的,如果字符串集合的分布不稳定,特别地如果是有序的,BST的性能最差(为O(n)),BST退化为一棵单枝树。因此,BST特别不适合有序排列的输入字符串集合。
2.2 BST树的变种
实际应用中,有许多BST的变种。如AV L-树和红-黑树及splay树等,它们与BST树的不同在于插入字符串的过程中重组树的结构,保持树的近似平衡,从而保证不会出现单枝树。但是,AV L-树和红-黑树结构的不足在于每一个结点中要保存附加的信息位(AV L-树中2位,红-黑树中1位)。另一方面,由于重组树的结构使一些经常存取的关键词聚集在树的根附近。并且,在不经常作插入运算的情况下,保持树的平衡的代价相对较低。因此保持树的平衡所带来的好处相对于BST树来说可以抵消由于插入运算引起的附加时间。S play树是另一种BST树的变种。其特点是:每一次搜索,都要将操作的结点通过一系列的结点旋转即splaying 运算将结点移到根结点的附近。这样使得一些经常存取的关键词总在根的附近,以便在后续查找中可以快速找到。但是,这种结构也有明显的不足。相对于BST树,一棵S play树需要较多的存储空间(每一个结点中要存储一个指向双亲的指针),其次, S playing运算本身比较复杂。在实际的应用中,应该根据实际的应用需求选择合适的结构。
2.3 Hash表
字符串处理中常用的另外一种数据结构是哈希表(Hash table)。哈希表是一种直接计算记录存放地址的方法,它在关键码(字符串)与存储位置之间直接建立映像。当采用链式哈希表结构、位方式的哈希函数、不要求字符串集合有序存储时,哈希表结构及其查找技术性能最佳。由于哈希表中的字符串通常是随机地分布在表中,不是有序的,在某些要求字符串有序存储(如索引维护及前缀查找)的应用中,不适合采用哈希表。
2.4 T rie树
T rie树是一种有效的字符串处理数据结构,广泛地用于自然语言处理、模式匹配、IP路由表以及文本压缩等。
T rie是一种树型数据结构,用于存储字符串,可以实现字符串的快速查找。有三种类型的trie:标准trie,压缩trie,后缀trie;
?标准trie
定义1:令S ={s1,s2,s3,......sn},是一个定义在字符集合∑上的字符串集合。S 的一个trie 结构是一棵m 分支树T (|∑|=m ),除根以外的所有非终端结点存储∑中的一个字符,每一个叶子结点li 对应一个字符串si ,并且从根到叶子结点li 的路径上的结点字符连接起来就是字符串si 。T 的结构特性如下:
(1)T 是有序树,T 所表示的字符串互不相同;(2)T 最多有n 个叶子结点;
(3)T 的深度为S 中最长字符串的长度;T 的结点个数是O (n )(n 为总的字符串长度)。
.压缩trie (com pressed trie )
为了改进标准trie 的不足,常常要对标准trie 树进行压缩。一种简单直观的压缩方法是路径压缩,基本思想是:若树的某个结点到叶子结点的路径上,每个结点都只有一个分支,可将该路径压缩到一个叶子结点。
若S ={s1,s2,...sn}且|∑|=d ,S 的压缩trie 树T 有下列特性:
(1)每一个非叶子结点至少有两个最多有d 个分支;
(2)T 有s (s =|S|)个叶子结点;(3)T 的结点个数是O (s )。
压缩trie 常常用做文本集合的辅助索引结构,在这种结构里,每个结点并不存储具体的字符,而是用一对数字表示字符(串)在基本结构中的位置。这种结构不仅大大减少存储空间,而且不必考虑实际的文本如何存储(是二进制?还是ACII 码),常常用于文本压缩应用。
.后缀trie (suffix trie )
后缀trie 与标准trie 的不同在于trie 中存储的是一个文本(或字符串)的后缀子串。这种trie 结构的特点是:
(1)减少存储空间;
(2)不必考虑实际的文本如何存储(是二进制?还是ACII 码);
(3)不必担心存储同样的字符串;
(4)当要匹配的模式是一个后缀(或前缀)子串时,可以有效地支持模式匹配运算。
3 结论
尽管有多种字符串数据结构,但是由于其各自的特点,其应用的适应性也不一样,在实际应用中应根据其特点选择。
参考文献
[1] D.E.克努特1计算机程序设计技巧1北京:国防工业出版社,
1982,81
[2] 郑丽英,吕 慧,闫光辉1数据结构1兰州:兰州大学出版社,
2003,51
[3] 严蔚敏1数据结构1北京:清华大学出版社,1991,10,
(上接第34页)
减速时间分别设定为20、10、5S
。
图2 梯形图控制程序
在t =0时按下正转起动按钮X3,电机以7速开
始起动,0-2S ,2-4S 分别以第1、第4加减速时间
加速,4-20S 使用第2加减速时间,t =8S 时改为5速,t =12S 时改为3速,t =16S 时按下停止按钮X5,t =20S 时按下反转按钮,反转起动,20-24S 使用第4加减速时间,t =23S 时发出停车信号。相应的梯形图控制程序如图2所示。
4 效果分析
可编程序控制器体积小,功耗低,控制灵活,使用方便,编程简单,针对不同的控制要求只需更改程序。变频器功能强、节电效果明显。可编程序控制器与变频器结合是一种理想的控制方案,在很多设备或系统中得到广泛推广应用。
参考文献
[1] 廖常初1可编程序控制器的编程方法与工程应用1重庆:重
庆大学出版社,2001,21
[2] 满永奎等1通用变频器及其应用1北京:机械工业出版社,
19991
2
4 甘 肃 科 技 第19卷
第二章作业 2－1 常见的金属晶体结构有哪几种它们的原子排列和晶格常数有什么特点 V、Mg、Zn 各属何种结构答：常见晶体结构有 3 种：⑴体心立方：－Fe、Cr、V ⑵面心立方：－Fe、Al、Cu、Ni ⑶密排六方：Mg、Zn －Fe、－Fe、Al、Cu、Ni、Cr、 2---7 为何单晶体具有各向异性，而多晶体在一般情况下不显示出各向异性答：因为单晶体内各个方向上原子排列密度不同，造成原子间结合力不同，因而表现出各向异性；而多晶体是由很多个单晶体所组成，它在各个方向上的力相互抵消平衡，因而表现各向同性。第三章作业3－2 如果其它条件相同，试比较在下列铸造条件下，所得铸件晶粒的大小；⑴金属模浇注与砂模浇注；⑵高温浇注与低温浇注；⑶铸成薄壁件与铸成厚壁件；⑷浇注时采用振动与不采用振动；⑸厚大铸件的表面部分与中心部分。答：晶粒大小：⑴金属模浇注的晶粒小⑵低温浇注的晶粒小⑶铸成薄壁件的晶粒小⑷采用振动的晶粒小⑸厚大铸件表面部分的晶粒小第四章作业 4－4 在常温下为什么细晶粒金属强度高，且塑性、韧性也好试用多晶体塑性变形的特点予以解释。答：晶粒细小而均匀，不仅常温下强度较高，而且塑性和韧性也较好，即强韧性好。原因是：（1）强度高：Hall-Petch 公式。晶界越多，越难滑移。（2）塑性好：晶粒越多，变形均匀而分散，减少应力集中。（3）韧性好：晶粒越细，晶界越曲折，裂纹越不易传播。 4－6 生产中加工长的精密细杠（或轴）时，常在半精加工后，将将丝杠吊挂起来并用木锤沿全长轻击几遍在吊挂 7~15 天，然后再精加工。试解释这样做的目的及其原因答：这叫时效处理一般是在工件热处理之后进行原因用木锤轻击是为了尽快消除工件内部应力减少成品形变应力吊起来，是细长工件的一种存放形式吊个7 天，让工件释放应力的时间，轴越粗放的时间越长。 4－8 钨在1000℃变形加工，锡在室温下变形加工，请说明它们是热加工还是冷加工（钨熔点是3410℃，锡熔点是232℃）答：W、Sn 的最低再结晶温度分别为: TR(W) =（～×(3410+273)－273 =（1200～1568）(℃)＞1000℃ TR(Sn) =（～×(232+273)－273 =（-71～-20）(℃) ＜25℃ 所以 W 在1000℃时为冷加工，Sn 在室温下为热加工 4－9 用下列三种方法制造齿轮，哪一种比较理想为什么（1）用厚钢板切出圆饼，再加工成齿轮；（2）由粗钢棒切下圆饼，再加工成齿轮；（3）由圆棒锻成圆饼，再加工成齿轮。答：齿轮的材料、加工与加工工艺有一定的原则，同时也要根据实际情况具体而定，总的原则是满足使用要求；加工便当；性价比最佳。对齿轮而言，要看是干什么用的齿轮，对于精度要求不高的，使用频率不高，强度也没什么要求的，方法 1、2 都可以，用方法 3 反倒是画蛇添足了。对于精密传动齿轮和高速运转齿轮及对强度和可靠性要求高的齿轮，方法 3 就是合理的。经过锻造的齿坯，金属内部晶粒更加细化，内应力均匀，材料的杂质更少，相对材料的强度也有所提高，经过锻造的毛坯加工的齿轮精度稳定，强度更好。 4－10 用一冷拔钢丝绳吊装一大型工件入炉，并随工件一起加热到1000℃，保温后再次吊装工件时钢丝绳发生断裂，试分析原因答：由于冷拔钢丝在生产过程中受到挤压作用产生了加工硬化使钢丝本身具有一定的强度和硬度，那么再吊重物时才有足够的强度，当将钢丝绳和工件放置在1000℃炉内进行加热和保温后，等于对钢丝绳进行了回复和再结晶处理，所以使钢丝绳的性能大大下降，所以再吊重物时发生断裂。 4－11 在室温下对铅板进行弯折，越弯越硬，而稍隔一段时间再行弯折，铅板又像最初一样柔软这是什么原因答：铅板在室温下的加工属于热加工，加工硬化的同时伴随回复和再结晶过程。越弯越硬是由于位错大量增加而引起的加工硬化造成，而过一段时间又会变软是因为室温对于铅已经是再结晶温度以上，所以伴随着回复和再结晶过程，等轴的没有变形晶粒取代了变形晶粒，硬度和塑性又恢复到了未变形之前。第五章作业 5－3 一次渗碳体、二次渗碳体、三次渗碳体、共晶渗碳体、共析渗碳体异同答：一次渗碳体：由液相中直接析出来的渗碳体称为一次渗碳体。二次渗碳体：从 A 中析出的渗碳体称为二次渗碳体。三次渗碳体：从 F 中析出的渗碳体称为三次渗碳体共晶渗碳体：经共晶反应生成的渗碳体即莱氏体中的渗碳体称为共晶渗碳体共析渗碳体：经共析反应生成的渗碳体即珠光体中的渗
1.栈和队列的共同特点是（只允许在端点处插入和删除元素） 2.栈通常采用的两种存储结构是（线性存储结构和链表存储结构） 3.链表不具有的特点是（B） A.不必事先估计存储空间 B.可随机访问任一元素 C.插入删除不需要移动元素 D.所需空间与线性表长度成正比 4.用链表表示线性表的优点是（便于插入和删除操作） 5.在单链表中，增加头结点的目的是（方便运算的实现） 6.循环链表的主要优点是（从表中任一结点出发都能访问到整个链表） 7.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D） A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 8.线性表的顺序存储结构和线性表的链式存储结构分别是（随机存取的存储结构、顺序存取的存储结构） 9.具有3个结点的二叉树有（5种形态） 10.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的 结点数为（13）(n 0 = n 2 +1) 11.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（cedba） 12.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（gdbehfca） 13.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。
1.在计算机中，算法是指（解题方案的准确而完整的描述） 2.算法一般都可以用哪几种控制结构组合而成（顺序、选择、循环） 3.算法的时间复杂度是指（算法执行过程中所需要的基本运算次数） 4.算法的空间复杂度是指（执行过程中所需要的存储空间） 5.算法分析的目的是（分析算法的效率以求改进） 6.下列叙述正确的是（C） A．算法的执行效率与数据的存储结构无关 B．算法的空间复杂度是指算法程序中指令（或语句）的条数 C．算法的有穷性是指算法必须能在执行有限个步骤之后终止 D．算法的时间复杂度是指执行算法程序所需要的时间 7.数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及（数据的存储结构） 8.数据结构中，与所使用的计算机无关的是数据的（C） A．存储结构 B．物理结构 C．逻辑结构 D．物理和存储结构 9.下列叙述中，错误的是（B） A．数据的存储结构与数据处理的效率密切相关 B．数据的存储结构与数据处理的效率无关 C．数据的存储结构在计算机中所占的空间不一定是连续的 D．一种数据的逻辑结构可以有多种存储结构 10.数据的存储结构是指（数据的逻辑结构在计算机中的表示） 11.数据的逻辑结构是指（反映数据元素之间逻辑关系的数据结构） 12.根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为（线性结构和非线性结构） 13.下列数据结构具有记忆功能的是（C） A．队列 B．循环队列 C．栈 D．顺序表 14.递归算法一般需要利用（栈）实现。 15.由两个栈共享一个存储空间的好处是（节省存储空间，降低上溢发生的机率）
个六元环共有。每个六元环实际拥有的碳原子数为 ______个。C-C键夹角：_______。C原子的杂化方式是______ SiO2晶体中，每个Si原子与个O原子以共价键相结合，每个O原子与个Si 原子以共价键相结合，晶体中Si原子与O原子个数比为。晶体中Si原子与Si—O键数目之比为。最小环由个原子构成，即有个O，个Si，含有个Si-O键，每个Si原子被个十二元环，每个O被个十二元环共有，每个Si-O键被__个十二元环共有；所以每个十二元环实际拥有的Si原子数为_____个，O原子数为____个，Si-O键为____个。硅原子的杂化方式是______,氧原子的杂化方式是_________. 知该晶胞中实际拥有的Na+数为____个 Cl-数为______个，则次晶胞中含有_______个NaCl结构单元。 3. CaF2型晶胞中，含:___个Ca2+和____个F- Ca2+的配位数： F-的配位数： Ca2+周围有______个距离最近且相等的Ca2+ F- 周围有_______个距离最近且相等的F——。 4．如图为干冰晶胞（面心立方堆积），CO2分子在晶胞中的位置为；每个晶胞含二氧化碳分子的个数为；与每个二氧化碳分子等距离且最近的二氧化
碳分子有个。 5．如图为石墨晶体结构示意图， 每层内C原子以键与周围的个C原子结合，层间作用力为；层内最小环有 _____个C原子组成；每个C原子被个最小环所共用；每个最小环含有个C原子，个C—C键；所以C原子数和C-C键数之比是_________。C原子的杂化方式是__________. 6.冰晶体结构示意如图，冰晶体中位于中心的一个水分子 周围有______个位于四面体顶角方向的水分子,每个水分子通过 ______条氢键与四面体顶点上的水分子相连。每个氢键被_____个 水分子共有，所以平均每个水分子有______条氢键。 7.金属的简单立方堆积是_________层通过_________对 _________堆积方式形成的，晶胞如图所示：每个金属阳离子的 配位数是_____，代表物质是________________________。 8.金属的体心立方堆积是__________层通过 ________对________堆积方式形成的，晶胞如图： 每个阳离子的配位数是__________.代表物质是 _____________________。
第四章字符串的应用 【实验目的】 1. 熟练掌握字符串的数据类型定义以及字符串的五种基本操作的定义，并能利用这些基本操作实现字符串的其他基本操作的方法。 2. 熟练掌握字符串串的定长顺序存储结构上实现字符串的各种操作的方法。 3. 理解字符串的堆分配存储表示以及在其上实现字符串操作的基本方法。 4. 熟练掌握串的基本操作类型的实现方法，其中文本模式匹配方法是一个难点，在掌握了BF算法的基础上理解改进的KMP算法。 5. 了解一般文字处理软件的设计方法。 第一节知识准备 一、有关串几个重要概念 1. 串（字符串）：零个或多个字符组成的有限序列。一般记作s="a1a2 …an"(n≥0) 2. 长度：串中字符的数目 3. 空串：零个字符的串，其长度为零 4. 子串和主串：串中任意个连续的字符组成的子序列称为该串的子串；包含子串的串相应地称为主串，字符在序列中的序号为该字符在串中的位置。 5. 当两个串的长度相等，并且各个对应位置的字符都相等时称为两串相等。 6. 空格串：由一个或多个空格组成的串‘’，同空串是完全不同的。 二、串的抽象数据类型定义 ADT String{ 数据对象：D={ | ∈C haracterSet, i=1,2,...,n, n>=0} 数据关系：R1={< , >| , ∈D, i=2,...,n} 基本操作： Assign(&s,t) 将串t的值赋给串 s Create(&s,ss) 将串s的值设定为字符序列ss Equal(s,t) 判定串s和串t是否相等 Length(s) 求串s的长度 Concat(&s,t) 将串s和串t连接成一个串，结果存于s中
几种常见晶体结构分析 河北省宣化县第一中学 栾春武 邮编 075131 栾春武：中学高级教师，张家口市中级职称评委会委员。河北省化学学会会员。市骨干教师、市优秀班主任、模范教师、优秀共产党员、劳动模范、县十佳班主任。 联系电话：：： 一、氯化钠、氯化铯晶体——离子晶体 由于离子键无饱和性与方向性，所以离子晶体中无单个分子存在。阴阳离子在晶体中按一定的规则排列，使整个晶体不显电性且能量最低。离子的配位数分析如下： 离子数目的计算：在每一个结构单元（晶胞） 中，处于不同位置的微粒在该单元中所占的份额也有 所不同，一般的规律是：顶点上的微粒属于该单元中 所占的份额为18 ，棱上的微粒属于该单元中所占的份额为14，面上的微粒属于该单元中所占的份额为12 ，中心位置上（嚷里边）的微粒才完全属于该单元，即所占的份额为1。 1.氯化钠晶体中每个Na +周围有6个C l －，每个Cl －周围有6个Na +，与一个Na +距离最近且相等的 Cl －围成的空间构型为正八面体。每个N a +周围与其最近且距离相等的Na + 有12个。见图1。 晶胞中平均Cl －个数：8×18 + 6×12 ＝ 4；晶胞中平均Na +个数：1 + 12×14 ＝ 4 因此NaCl 的一个晶胞中含有4个NaCl （4个Na +和4个Cl －）。 2.氯化铯晶体中每个Cs +周围有8个Cl －，每个Cl －周围有8个Cs +，与 一个Cs +距离最近且相等的Cs +有6个。晶胞中平均Cs +个数：1；晶胞中平 均Cl －个数：8×18 ＝ 1。 因此CsCl 的一个晶胞中含有1个CsCl （1个Cs +和1个Cl －）。 二、金刚石、二氧化硅——原子晶体 1.金刚石是一种正四面体的空间网状结构。每个C 原子以共价键与4 个C 原子紧邻，因而整个晶体中无单个分子存在。由共价键构成的最小 环结构中有6个碳原子，不在同一个平面上，每个C 原子被12个六元环 共用，每C —C 键共6个环，因此六元环中的平均C 原子数为6× 112 ＝ 12 ，平均C —C 键数为6×16 ＝ 1。 C 原子数: C —C 键键数 ＝ 1:2； C 原子数: 六元环数 ＝ 1:2。 2.二氧化硅晶体结构与金刚石相似，C 被Si 代替，C 与C 之间插氧，即为SiO 2晶体，则SiO 2晶体中最小环为12环（6个Si ，6个O ）， 最小环的平均Si 原子个数：6×112 ＝ 12；平均O 原子个数：6×16 ＝ 1。 即Si : O ＝ 1 : 2，用SiO 2表示。 在SiO 2晶体中每个Si 原子周围有4个氧原子，同时每个氧原子结合2个硅原子。一个Si 原子可形 图 1 图 2 NaCl 晶体 图3 CsCl 晶体 图4 金刚石晶体
Python常见数据结构整理 2014年10月15日tenking阅读23 次 Python中常见的数据结构可以统称为容器（container）。序列（如列表和元组）、映射（如字典）以及集合（set）是三类主要的容器。 一、序列（列表、元组和字符串） 序列中的每个元素都有自己的编号。Python中有6种内建的序列。其中列表和元组是最常见的类型。其他包括字符串、Unicode字符串、buffer对象和xrange对象。下面重点介绍下列表、元组和字符串。 1、列表 列表是可变的，这是它区别于字符串和元组的最重要的特点，一句话概括即：列表可以修改，而字符串和元组不能。 （1）、创建 通过下面的方式即可创建一个列表： 1 2 3 4list1=['hello','world'] print list1 list2=[1,2,3] print list2 输出： […hello?, …world?] [1, 2, 3] 可以看到，这中创建方式非常类似于javascript中的数组。（2）、list函数
通过list函数（其实list是一种类型而不是函数）对字符串创建列表非常有效： 1 2list3=list("hello") print list3 输出： […h?, …e?, …l?, …l?, …o?] 2、元组 元组与列表一样，也是一种序列，唯一不同的是元组不能被修改（字符串其实也有这种特点）。（1）、创建 1 2 3 4 5 6t1=1,2,3 t2="jeffreyzhao","cnblogs" t3=(1,2,3,4) t4=() t5=(1,) print t1,t2,t3,t4,t5 输出： (1, 2, 3) (…jeffreyzhao?, …cnblogs?) (1, 2, 3, 4) () (1,)从上面我们可以分析得出： a、逗号分隔一些值，元组自动创建完成； b、元组大部分时候是通过圆括号括起来的； c、空元组可以用没有包含内容的圆括号来表示； d、只含一个值的元组，必须加个逗号（,）；（2）、tuple函数
数据结构字符串复制,连接,求子串,KMP #include if(n<1||n>a.length) { printf("插入的位置不合法\n"); return ERROR; } str c; c.length=a.length+b.length; if((c.ch=(char*)malloc(sizeof(char)*(c.length+1)))==NULL) { return ERROR; } inti=0,j=0,l=0,k=0; while(i 几种常见的排序算法之比较 2010-06-20 14:04 数据结构课程 摘要： 排序的基本概念以及其算法的种类，介绍几种常见的排序算法的算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序的算法和分析它们各自的复杂度，然后以表格的形式，清晰直观的表现出它们的复杂度的不同。在研究学习了之前几种排序算法的基础上，讨论发现一种新的排序算法，并通过了进一步的探索，找到了新的排序算法较之前几种算法的优势与不足。 关键词：排序算法复杂度创新算法 一、引言 排序算法，是计算机编程中的一个常见问题。在日常的数据处理中，面对纷繁的数据，我们也许有成百上千种要求，因此只有当数据经过恰当的排序后，才能更符合用户的要求。因此，在过去的数十载里，程序员们为我们留下了几种经典的排序算法，他们都是智慧的结晶。本文将带领读者探索这些有趣的排序算法，其中包括介绍排序算法的某些基本概念以及几种常见算法，分析这些算法的时间复杂度，同时在最后将介绍我们独创的一种排序方法，以供读者参考评判。 二、几种常见算法的介绍及复杂度分析 1.基本概念 1.1稳定排序(stable sort)和非稳定排序 稳定排序是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，。反之，就是非稳定的排序。 比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为 a1,a2,a4,a3,a5， 则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。 1.2内排序( internal sorting )和外排序( external sorting) 在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 #include"stdio.h" #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)>(b)) #define maxsize 20 typedef int keytype; typedef struct{ keytype key; }RedType; typedef struct{ RedType r[maxsize+1]; int length; }Sqlist; //直接插入排序 void insertsort(Sqlist &L){ int i,j; for(i=2;i<=L.length;++i) if(LT(L.r[i].key,L.r[i-1].key)){ L.r[0]=L.r[i]; L.r[i]=L.r[i-1]; for(j=i-2;LT(L.r[0].key,L.r[j].key);--j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; }//if }//insertsort //折半插入排序 void BInsertSort(Sqlist &L) { int i,j,low,high,m; for(i=2;i<=L.length;++i) { L.r[0]=L.r[i]; low=1; high=i-1; while(low<=high){ m=(low+high)/2; if(LT(L.r[0].key,L.r[m].key)) high=m-1; else low=m+1; }//while for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; }//for 几种常见晶体结构分析文档编制序号：[KK8UY-LL9IO69-TTO6M3-MTOL89-FTT688] 几种常见晶体结构分析 河北省宣化县第一中学 栾春武 邮编 075131 栾春武：中学高级教师，张家口市中级职称评委会委员。河北省化学学会会员。市骨干教师、市优秀班主任、模范教师、优秀共产党员、劳动模范、县十佳班主任。 联系电话： E-mail ： 一、氯化钠、氯化铯晶体——离子晶体 由于离子键无饱和性与方向性，所以离子晶体中无单个分子存在。阴阳离子在晶体中按一定的规则排列，使整个晶体不显电性且能量最低。离子的配位数分析如下： 离子数目的计算：在每一个结构单元（晶胞）中，处于不同位置的微粒在该单元中所占的份额也有所不同，一般的规律是：顶点上的微粒属于该 单元中所占的份额为18，棱上的微粒属于该单元中所占的份额为1 4，面上 的微粒属于该单元中所占的份额为1 2，中心位置上（嚷里边）的微粒才完 全属于该单元，即所占的份额为1。 1.氯化钠晶体中每个Na +周围有6个Cl －，每个Cl －周围有6个Na +，与一个Na +距离最近且相等的Cl －围成的空间构型为正八面体。每个Na +周围与其最近且距离相等的Na +有12个。见图1。 图1 图2 NaCl 晶胞中平均Cl－个数：8×1 8 + 6× 1 2 ＝ 4；晶胞中平均Na+个数：1 + 12×1 4 ＝ 4 因此NaCl的一个晶胞中含有4个NaCl（4个Na+和4个Cl－）。 2.氯化铯晶体中每个Cs+周围有8个Cl－，每个Cl－周围有8个Cs+，与一个Cs+距离最近且相等的Cs+有6个。 晶胞中平均Cs+个数：1；晶胞中平均Cl－个数：8×1 8 ＝ 1。 因此CsCl的一个晶胞中含有1个CsCl（1个Cs+和1个Cl－）。 二、金刚石、二氧化硅——原子晶体 1.金刚石是一种正四面体的空间网状结构。每个C 原子以共价键与4个C原子紧邻，因而整个晶体中无单 个分子存在。由共价键构成的最小环结构中有6个碳原 子，不在同一个平面上，每个C原子被12个六元环共用，每C—C键共6 个环，因此六元环中的平均C原子数为6× 1 12 ＝ 1 2 ，平均C—C键数为 6×1 6 ＝ 1。 C原子数: C—C键键数＝ 1:2； C原子数: 六元环数＝ 1:2。 2.二氧化硅晶体结构与金刚石相似，C被Si代替，C与C之间插 氧，即为SiO 2晶体，则SiO 2 晶体中最小环为12环（6个Si，6个O）， 图3 CsCl 晶 图4 金刚石晶 第19卷 第12期2003年12月 甘肃科技 G ansu Science and T echnology Vol.19 No.12 Dec. 2003 字符串处理中常用的几种数据结构及其性能分析 郑丽英1,李永昶2 (1.兰州交通大学信息与电气工程学院,甘肃兰州 730070;2.兰州交通大学机电工程学院,甘肃兰州 730070) 摘 要:许多计算机应用涉及字符串处理。为了提高处理效率,设计一个好的数据结构十分重要。分析了几种常用的字符串数据结构及其性能,重点分析了数据结构T rie及其三种形式的结构特性。关键词:T rie;数据结构;索引 中图分类号:TP311 1 前言 许多计算机应用都涉及到对一个非常大的字符串集合的有效管理。例如,从档案管理、文献目录查找、地理信息索引到Web上大量的文本信息处理等等,都涉及到对一个非常大的字符串集合的管理。显然,如何有效管理大的字符串集合的首要问题是如何存储和组织它们即选择一个合适的数据结构。在实际中为一个应用选择一个好的数据结构取决于许多因素,如存储需求、查找速度、是否在内存、是否要求有序存储等等。已有许多用于字符串管理的数据结构,下面将分别进行分析和讨论。 2 常用的字符串数据结构 2.1 BST树 BST树((Binary Search T ree,即二叉搜索树)是最简单且最直观的一种。在一棵BST树中,每一个结点存储一个字符串和两个分别指向左右孩子结点的指针。在BST树中查找一个给定的字符串的过程是:首先和根结点的字符串比较,若相等则查找成功。若不相等则按比较结果决定沿左分支或右分支继续比较。BST树的结构性能主要取决于树的形态,与输入字符串集的排列有关。假设字符串集合的分布是稳定的、且常用词的集合是已知的且常用词分布在根结点的附近,则BST结构是相当快的,如果字符串集合的分布不稳定,特别地如果是有序的,BST的性能最差(为O(n)),BST退化为一棵单枝树。因此,BST特别不适合有序排列的输入字符串集合。 2.2 BST树的变种 实际应用中,有许多BST的变种。如AV L-树和红-黑树及splay树等,它们与BST树的不同在于插入字符串的过程中重组树的结构,保持树的近似平衡,从而保证不会出现单枝树。但是,AV L-树和红-黑树结构的不足在于每一个结点中要保存附加的信息位(AV L-树中2位,红-黑树中1位)。另一方面,由于重组树的结构使一些经常存取的关键词聚集在树的根附近。并且,在不经常作插入运算的情况下,保持树的平衡的代价相对较低。因此保持树的平衡所带来的好处相对于BST树来说可以抵消由于插入运算引起的附加时间。S play树是另一种BST树的变种。其特点是:每一次搜索,都要将操作的结点通过一系列的结点旋转即splaying 运算将结点移到根结点的附近。这样使得一些经常存取的关键词总在根的附近,以便在后续查找中可以快速找到。但是,这种结构也有明显的不足。相对于BST树,一棵S play树需要较多的存储空间(每一个结点中要存储一个指向双亲的指针),其次, S playing运算本身比较复杂。在实际的应用中,应该根据实际的应用需求选择合适的结构。 2.3 Hash表 字符串处理中常用的另外一种数据结构是哈希表(Hash table)。哈希表是一种直接计算记录存放地址的方法,它在关键码(字符串)与存储位置之间直接建立映像。当采用链式哈希表结构、位方式的哈希函数、不要求字符串集合有序存储时,哈希表结构及其查找技术性能最佳。由于哈希表中的字符串通常是随机地分布在表中,不是有序的,在某些要求字符串有序存储(如索引维护及前缀查找)的应用中,不适合采用哈希表。 2.4 T rie树 T rie树是一种有效的字符串处理数据结构,广泛地用于自然语言处理、模式匹配、IP路由表以及文本压缩等。 T rie是一种树型数据结构,用于存储字符串,可以实现字符串的快速查找。有三种类型的trie:标准trie,压缩trie,后缀trie; ?标准trie 《数据结构》实验报告 院系光电与信息工程学院专业电子信息工程 姓名学号电话 2011级2班2013年4月22日 1．实验题目 实验6. 字符串的基本操作 2．需求分析 (1)字符串匹配。 采用顺序结构存储串，编写一个函数SubStr(str1,str2),用于判定str2是否是str1的子串。 (2)公共字符串。 问题描述编写一个函数，实现在两个已知字符串中找出所有非空最长公共子串的长度和最长公共子串的个数。 实现要求输出非空最长公共子串的长度和最长公共子串的个数。 字符串匹配： ①串长度Strlen(SString str) ②判断是否为子串SubStr(SString str1,SString str2) 公共字符串： ①串长度Strlen(SString str) ②最大公共串长度函数maxlen() ③求公共串个数函数SubStrnum() 输入形式：字符串。 3．概要设计 (1) ADT SString{ 数据对象：D={a i|a i∈IntegerSet,i=0,1,2,…,n,n≥0} 结构关系：R={|a i,a i+1 ∈D} 基本操作： Strlen(SString str) 操作前提：字符串str已存在 操作结果：求str的长度 SubStr(SString str1,SString str2) 操作前提：字符串str已存在 操作结果：判断str2是不是str1的子串 } ADT SString{ 数据对象：D={a i|a i∈IntegerSet,i=0,1,2,…,n,n≥0} 基本操作： Strlen(SString str) 操作前提：字符串str已存在 操作结果：求str的长度 maxlen(SString str1,SString str2,SString str) 操作前提：字符串str1，str2，str已存在 操作结果：求str1和str2的最大公共子串长度，并将该子串赋给str SubStrnum(SString str1,SString str2) 操作前提：字符串str1，str2已存在 操作结果：求在str1中str2子串的个数 } (2)字符串匹配： 本程序包含3个函数： ?主函数main() ?求串长函数Strlen(SString str) ?{字符串匹配函数SubStr(SString str1,SString str2) 各函数调用关系：主函数main调用其他两个函数 公共字符串： 本程序包含4个函数： ?主函数main() ?求串长函数Strlen(SString str) ?最大公共串长度函数maxlen() ?求公共串个数函数SubStrnum() 各函数调用关系：主函数main调用其他三个函数 (3)字符串匹配： 主函数的伪码 main() { 定义SString 变量str1,str2; 输入第一个字符串； 输入第二个字符串； 调用字符串匹配函数； 输出匹配结果； ｝ 公共字符串： 主函数的伪码 一、编程题 (一) 对于二维整数数组A[m][n]，对下列三种情况，分别编写相应的函数。 1.求数组所有边缘元素的数值和。 int sum1(int A[M][N],int m ,int n) { 2.求从A[0][0]开始的互不相邻的所有元素的和 注：一个元素的八个方向上的第一个元素均为相邻元素。 int sum2 (int A[M][N] , int m , int n) { 3. 假定m=n，并为偶数，请分别计算正、反两条对角线上的元素值之和。 int sum3(int A[M][N] , int n) { 答 （1）本小题是计算数组A的最外围的4条边的所有元素之和。可以先累加各个靠边的元素的值，再减去位于4个角上重复相加的元素的值。 int sum1(int A[M][N],int m ,int n){ int s=0,i,j; for(i=0;i 几种常见晶体结构的应用与拓展 中学课本中列举了ＮａＣｌ、ＣｓＣｌ、金刚石、石墨、干冰、二氧化硅等典型晶体的结构示意图。它们的结构都是立体的，如何从平面图想像出三维实物的结构形态，这是解决有关问题的关键。 首先可以利用直观结构模型，逐步建立起准确、清晰的立体形象，提高空间想像力。 其次还需掌握基本的解题技巧：在晶体结构中切割一个基本结构单元，弄清该单元中点、边、面为多少个基本结构单元所共有。构成晶体的结构粒子是按着一定的排列方式所形成的固态群体。在晶体结构中具有代表性的最小重复单位叫晶胞。 根据晶体的晶胞，求粒子数的方法： ①处于顶点上的粒子：同时为8个晶胞共有，每个粒子有1/8属于晶胞。 ②处于棱上的粒子：同时为4个晶胞共有，每个粒子有1/4属于晶胞。 ③处于面上的粒子；同时为2个晶胞共有，每个粒子有1/2属于晶胞。 ④处于体心的粒子：则完全属于该晶胞。 中学阶段所需掌握的几种晶体结构类型及有关问题： 图3 干冰晶体 图1 NａＣｌ晶体图2 ＣｓＣｌ晶体 图4 金刚石晶体图5 ＳｉＯ2晶体 图6 石墨晶体 一、离子晶体 ＮａＣｌ型（如图1） 1．在晶体中，每个Ｎａ＋同时吸引 个Ｃｌ－，每个Ｃｌ－同时吸引着 个Ｎａ＋ ，阴、阳离子数目之比是 。 2．在晶体结构中，每个晶胞由 个小立方体构成，每个小立方体的8个顶点分别由 个 Ｎａ＋、 个Ｃｌ－相邻占据，每个小立方体含Ｎａ＋： 个、含Ｃｌ－ ： 个。故每个晶胞有ＮａＣｌ微粒 个。 3．在晶体中，经过立方体的中心Ｎａ＋的平面有三个，每个平面的四个顶点上的Ｎａ＋ 都同 晶体中与中心Ｎａ＋最接近且距离相等。所以，在晶体中，每个Ｎａ＋ 周围与它最接近的距离 相等的Ｎａ＋的个数共有 个。同理，每个Ｃｌ－周围与它最接近且距离相等的Ｃｌ－ 的个数也有 个。 ＣｓＣｌ型（如图2） 1．在晶体中，每个Ｃｌ－吸引 个Ｃｓ＋，每个Ｃｓ＋吸引 个Ｃｌ－，Ｃｓ＋与Ｃｌ－ 的个数比为 。 2．每个基本结构单元中（小立方体）含Ｃｌ－： 个，含Ｃｓ＋ 个。 3．在晶体中，每个Ｃｓ＋周围与它最接近且距离相等的Ｃｓ＋ 的个数共有 个。同理， 每 个Ｃｌ－周围与它最接近的且距离相等的Ｃｌ－ 共有 个。 [拓展练习] 1．在高温超导领域中，有一种化合物叫钙钛矿，其晶体结构中有代表性的最小单位结构如图所示试回答： (1)在该晶体中每个钛离子周围与它最近且相等距离的钛离子有 多少个? (2)在该晶体中氧、钙、钛的粒子个数化是多少? 2.某物质的晶体中含A 、B 、C 三种元素，其排列方式如图所示(其中前后两面心上的B 原子未能画出)，晶体中A 、B 、C 的中原子个数之比依次为 A.1:3:1 B.2:3:1 C.2:2:1 D.1:3:3 3．2001年曾报道，硼镁化合物刷新了金属化合物超导温度的最高 记录。该化合晶体结构中的晶胞如右图所示。镁原子间形成正六棱柱，六个硼原子位于棱柱内。则该化合物的化学式可表示为 A Mg 14 B 6 B Mg 2B C MgB 2 D Mg 3B 2 4.如图是氯化铯晶体的晶胞(晶体中最小的重复单元)，已知晶体中2个最近的Cs + 离子核间距为a cm ，氯化铯的式量为M ，NA 为阿伏加德罗常数，则氯化铯晶体的 密度为 A. 8M a 3N A g/cm 3 B. M 8a 3N A g/cm 3 C. M a 3N A g/cm 3 D. Ma 3 N A g/cm 3 数据结构中常用的逻辑结构和存储结构 一、概念 数据是指由有限的符号（比如，"0"和"1"，具有其自己的结构、操作、和相应的语义）组成的元素的集合。结构是元素之间的关系的集合。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。 数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系即逻辑结构，而物理上的数据结构反映成分数据在计算机内部的存储安排即存储结构。数据结构是数据存在的形式。 数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。因而研究数据结构的逻辑结构与存储结构显得十分重要。 二、结构分析 （一）逻辑结构 数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。 逻辑结构元素决定输入、存储、发送、处理和信息传递的基本操作功能，常将逻辑结构元素称为逻辑模块。逻辑结构元素可以是计算机操作系统、终端模块、通信程序模块等。逻辑结构元素还可以是相关的几个逻辑模块联合起来的更复杂的实体。分析逻辑结构元素的相互作用，应考虑整个系统的操作，研究处理与信息流有关的进程（操作系统中的一个概念，表示程序的一次执行），并决定系统的逻辑资源。 逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。表和树是最常用的两种高效数据结构，许多高效的算法能够用这两种数据结构来设计实现。 一、基本分类 数据的逻辑结构指数据元素之间的逻辑关系，分两种，线性结构和非线性结构。 线性结构：有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。）线性表就是一个典型的线性结构它有四个基本特征：1．集合中必存在唯一的一个"第一个元素"； 2．集合中必存在唯一的一个"最后的元素"； 3．除最后元素之外，其它数据元素均有唯一的"后继"； 4．除第一元素之外，其它数据元素均有唯一的"前驱"。 相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个直接后继。常见的非线性结构有：树(二叉树等)，图(网等)。 二、常用结构 习题 一、单项选择题 1.空串与空格字符组成的串的区别在于（ B ）。 A.没有区别 B.两串的长度不相等 C.两串的长度相等 D.两串包含的字符不相同 2.一个子串在包含它的主串中的位置是指（ D ）。 A.子串的最后那个字符在主串中的位置 B.子串的最后那个字符在主串中首次出现的位置 C.子串的第一个字符在主串中的位置 D.子串的第一个字符在主串中首次出现的位置 3.下面的说法中，只有（ C ）是正确的。 A.字符串的长度是指串中包含的字母的个数 B.字符串的长度是指串中包含的不同字符的个数 C.若T包含在S中，则T一定是S的一个子串 D.一个字符串不能说是其自身的一个子串 4.两个字符串相等的条件是（ D ）。 A.两串的长度相等 B.两串包含的字符相同 C.两串的长度相等，并且两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同 5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（B ）。 A.“ijing” B.“jing＆” C.“ingNa” D.“ing＆N” 6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（C ）。 A.2 B.3 C.4 D.5 7. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijin g＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（D ）。 A.“Nanjing＆Shanghai” B.“Nanjing＆Nanjing” C.“ShanghaiNanjing” D.“Shanghai＆Nanjing” 8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（C ）。 A.i＞0 B. i≤n C.1≤i≤n D.1≤i≤n+1 9.字符串采用结点大小为1的链表作为其存储结构，是指（ D ）。 A.链表的长度为1 B.链表中只存放1个字符 C.链表的每个链结点的数据域中不仅只存放了一个字符 D.链表的每个链结点的数据域中只存放了一个字符 二、算法设计题 1.设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中（每个单元存放一个字符）。现要求从此串的第m个字符以后删除长度为t的子串，m数据结构中几种常见的排序算法之比较
数据结构各种常用排序算法综合
几种常见晶体结构分析
字符串处理中常用的几种数据结构及其性能分析
数据结构--06字符串的基本操作
几道常用数据结构考试试题及答案
几种常见晶体结构的应用与拓展
数据结构中常用的逻辑结构和存储结构
数据结构字符串
相关主题
文本预览