数据结构应用

1、数据结构的应用一、数据结构的定义数据结构是计算机存储，组织数据的方式。数据结构是指相互之间存在一种或多种特定 关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效 率。数据结构往往同高效的检索算法和索引技术有关。二、数据结构的应用1、数据结构在操作系统中的应用涉及到内核进程结构及其相关组织，进程调度，主要涉及了 Linux的时钟中断、定时器、 Linux内核机制以及系统调用nanosleep、pause等。当然还有包括页面置换、请求分页系统 的性能问题、I/O系统的组成、I/O控制方式、文件系统、磁盘存储器管理等。(1)、双向链表(list)linux内核中的双向链

2、表通过结构struct list_head来将各个节点连接起来，此结构会作 为链表元素结构中的一个参数：struct list_head struct list_head *next, *prev;)；最常用的链表操作：插入到链表头：void list_add(struct list_head *new, struct list_head *head);插入到链表尾：void list_add_tail(struct list_head *new, struct list_head *head);删除链表节点：void list_del(struct list_head *entry);将节点

3、移动到另一链表：void list_move(struct list_head *list, struct list_head *head);将节点移动到链表尾：void list_move_tail(struct list_head *list,struct list_head *head);判断链表是否为空，返回1为空，。非空int list_empty(struct list_head *head);把两个链表拼接起来：void list_splice(struct list_head *list, struct list_head *head)；(2)、 HASH 表HASH表适用于不

4、需要对整个空间元素进行排序，而是只需要能快速找到某个元素的场 合，是一种以空间换时间的方法，本质也是线性表，但由一个大的线性表拆分为了多个小线 性表，由于只需要查找小表，因此搜索速度就会线性查整个大表提高很多，理想情况下，有 多少个小线性表，搜索速度就提高了多少倍，通常把小线性表的表头综合为一个数组，大小 就是HASH表的数量。HASH表速度的关键是HASH函数的设计，HASH函数根据每个元素中固定的参数进行计 算，算出一个不大于HASH表数量的索引值,表示该元素需要放在该索引号对应的那个表中， 对于固定的参数，计算结果始终是固定的，但对于不同的参数值，希望计算出来的结果能尽 可能地平均到每个

5、索引值，HASH函数计算得越平均，表示每个小表中元素的数量都会差不 多，这样搜索性能将越好。HASH函数也要尽可能的简单，以减少计算时间，常用的算法是 将参数累加求模，在include/linux/jhash.h中已经定义了一些HASH计算函数，可直接使用。 HASH表在路由cache表，状态连接表等处用得很多。(3)、定时器(timer)linux内核定时器由以下结构描述：/* include/linux/timer.h */struct timerjist struct list head list;unsigned long expires;unsigned long data;void

6、 (*function)(unsigned long);)；list： timer 链表expires：到期时间function：到期函数，时间到期时调用的函数data：传给到期函数的数据，实际应用中通常是一个指针转化而来，该指针指向一个结 构timer的操作：增加timer,将timer挂接到系统的timer链表：extern void add_timer(struct timerjist * timer);删除timer,将timer从系统timer链表中撤除：extern int del_timer(struct timerjist * timer);(del_timer()函数可能会失

7、败，这是因为该timer本来已经不在系统timer链表中了,也 就是已经删除过了)对于SMP系统，删除timer最好使用下面的函数来防止冲突：extern int del_timer_sync(struct timerjist * timer);修改timer,修改timer的到期时间：int mod_timer(struct timer_list *timer, unsigned long expires);(4)、内核线程(kernel_thread)内核中新线程的建立可以用kernel_thread函数实现，该函数在kernel/fork.c中定义： long kernel_thread

8、(int (*fn)(void *), void * arg, unsigned long flags)fn：内核线程主函数；arg：线程主函数的参数；flags：建立线程的标志；内核线程函数通常都调用daemonize()进行后台化作为一个独立的线程运行，然后设置 线程的一些参数，如名称，信号处理等，这也不是必须的，然后就进入一个死循环，这是 线程的主体局部，这个循环不能一直在运行，否那么系统就死在这了，或者是某种事件驱动 的，在事件到来前是睡眠的，事件到来后唤醒进行操作，操作完后继续睡眠；或者是定时 睡眠，醒后操作完再睡眠；或者加入等待队列通过schedule。调度获得执行时间。总之是不

9、能一直占着CPUo(5)、结构地址在C中，结构地址和结构中第一个元素的地址是相同的，因此在linux内核中经常出现 使用结构第一个元素的地址来表示结构地址的情况，在读代码时要注意这一点，lisjentry 宏的意思一样。2、数据结构在数据库中的应用这里主要提到到B-Tree和B+Tree的应用。MySQL官方对索引的定义为：索引(Index)是帮助MySQL高效获取数据的数据结 构。提取句子主干，就可以得到索引的本质：索引是数据结构。我们知道，数据库查询是数据库的最主要功能之一，例如下面的SQL语句：SELECT * FROM my_table WHERE col2 = 77可以从表my_ta

10、ble中获得col2为”7的数 据记录。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的 角度进行优化。最基本的查询算法当然是顺序查找(linear search),遍历my_table然后 逐行匹配812的值是否是77，这种复杂度为0(n)的算法在数据量很大时显然是糟糕的， 好在计算机科学的开展提供了很多更优秀的查找算法，例如二分查找(binary search)、二 叉树查找(binary tree search)等。如果稍微分析一下会发现，每种查找算法都只能应用于 特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉 查找树上，但是数据

11、本身的组织结构不可能完全满足各种数据结构(例如，理论上不可能 同时将两列都按顺序进行组织)，所以，在数据之外，数据库系统还维护着满足特定查找 算法的数据结构，这些数据结构以某种方式引用(指向)数据，这样就可以在这些数据结 构上实现高级查找算法。这种数据结构，就是索引。那么为什么使用B-Tree (B+Tree) ? 一般来说，索引本身也很大，不可能全部存储在 内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要 产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据 结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复

12、杂度。换 句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和 磁盘存取原理，然后再结合这些原理分析B-/+Tree作为索引的效率。3、数据结构在软件工程中的应用提到数据结构的应用，人们往往联想到其应用在系统软件开发中。例如计算机操作系 统中，先来先服务的调度方式就应用队列结构帮助快速找到首要完成的任务，帮助提高系 统的性能。我们这里以游戏软件为例来介绍数据结构在软件工程中的一些应用。谈到数据结构与 网络游戏使人觉得似乎不相关，其实在网络游戏中随处应用到数据结构。如果数据结构与 网络游戏很好的结合起来，可帮助提高游戏程序的运行速度众所周知一个好的程序应该包 括合理的

13、数据结构，即合理组织待处理的数据，以及相应的数据结构的好的算法。将数据 结构要与网络游戏融合，就是网络游戏中需要处理的数据应用合理数据结构并应用高效算 法处理。网络游戏中需要处理的问题包括游戏涉及的数据、角色的动作及游戏规那么等等。 接下来就浅谈一下对于数据结构在网络游戏中的各方面的应用。(1)、游戏数据处理网络游戏包括很多的数据，这些数据都被存储在服务器上的数据库里。当玩家成功登 录到游戏的那一刻，玩家就会从服务器的数据库里获得有关其自身的数据。玩家获得的数 据包括他选择的角色、当前玩到的级别、已经得到的道具、已经完成的任务及将要完成的 任务等等。数据信息种类繁多，数量庞大。为了处理方便，首

14、先应该根据数据的种类选择 其合理的数据结构进行临时存储，便于服务器为登录成功的玩家处理数据。玩家的道具会 随着级别的提升，种类和数量都会不断增多。如果用线性表的结构存储，就要为每一种道 具建立一个线性表结构，那么多种道具要建立的线性表同时会有多个。如果玩家同时以多 个账号登录时，这时就会产生一个难题，如何标志每个线性表涉及的道具是属于哪个账号 的，此时不便于服务器查找。玩家在玩时随时都有可能获得新的道具对于新的道具如何快 速存储到玩家的道具的数据结构中也是一个难题。这个问题可以通过链式存储的方式解 决，如果采用单链表存储用户的所有道具就会是种类混乱，那么接下来亟待解决的问题就 是对于种类问题的

15、解决。玩家、道具种类及道具之间可以采用树形结构存储，为了使道具 采用链式存储的方式，可采用孩子兄弟表示法为这种树的存储结构。树的根结点为玩家， 下一层为该玩家正在使用的所有角色，每个角色的下一层为已经获得的道具种类，种类下 为该道具。当添加新道具时，首先判断道具是否已经在道具树中，如果已经在，那么就在 树中该道具的数量加上新获得的数量；否那么，应该判断新道具的种类是否已经在树中，如 果在树中，那么将道具放置所属种类的结点下面，如果此道具的种类未在树中存在，那么应在 道具树的种类层中加入新的种类，在把新道具放到此种类下面，同时更新服务器上数据库 的道具信息，保持信息同步。当玩家的某个角色需要获得

16、自己的某种道具时，用遍历算 法，先找到种类，再沿着种类找到所有的道具。通过这样的树结构，防止了每次玩家的角 色浏览道具时都要访问数据库中数据，节省了时间，更便于对道具进行分类管理，查找道 具的速度也更快。通过对道具的信息管理举例，可以发现，数据结构对于游戏数据在获取 之后，有组织的管理，读取信息的速度更快，从而提高游戏的运行速度。(2)、角色动作管理玩家通过输入设备控制角色动作，经常同时控制运动动作和攻击动作。玩家同时输入 多个动作的速度极快，需要系统快速响应。无论何种动作，众所周知都动作都是由线程来 控制，多个动作同时提交等于向系统提交了多个线程。玩家希望多个动作能够同时运行， 但对于系统而

17、言，线程不能同时运行。因为系统响应每个线程的时间比拟短，给玩家的感 觉是同时响应的，实际上采用的是并发的方式。合理的安排线程运行的顺序，便于系统的 调度，角色能够快速展现玩家输入的动作。可以按照玩家输入的动作到达系统的时间为线 程排序，用队列存储线程。先到达的排在队头，后到达排在队尾。队列的特征为先进先 出，因此，用此种结构组织线程的时候，系统直接调出队头的线程进行运行，节省了查找 的时间。随之而来的问题就是采用何种队列的存储结构？如果采用循环队列的结构，就需 要预先知道大概需要的存储区大小，但是玩家随时都会输入新的动作，无法得知所需存储 区的大小，那么可以采用链队列来存储玩家的动作线程更加适

18、合。当有新的动作来时，可 以将为其申请任意的空间存储，只需把地址告知之前的队尾，就连入了队尾。采用链队列 的方式调度动作线程，使角色的动作展现更加协调，系统响应速度明显提高。通过角色动 作线程调度举例，可以看到数据结构对于角色的动作同样可以进行管理，进一步提高游戏 运行的速度。(3)、游戏规那么的实现不管是何种游戏，游戏规那么是游戏设计的核心，游戏规那么的好坏不但会影响到玩家对 游戏的兴趣程度，同样会影响到游戏的运行速度。制定了好的游戏规那么后，如何实现就是 难题。首先就应该为其设计好的算法，以连连看游戏为例，两个同样的图像选择后满足三 根以内折线联通就可以消掉。满足条件的连线方式可能有多种，

19、使用最短路径连接消除会 大大提高游戏运行的速度，关键是如何找到最短路径？对于图的逻辑结构存在这样的算 法一一每一对顶点间的最短路径算法，Floyd算法的基本思想是：假设从vi到vj的弧(假设 从vi到vj的弧不存在，那么将其弧权值看为8)是最短路径，然后进行n次试探，没找到最 短路径之前，就在vi和vj之间加入顶点，直到找到最短路径为止。游戏玩家选中的两张一 模一样的图片作为顶点vi和vj,判断它们是否能被消掉，也就是判断能不能找到满足条件 的最短路径。每次试探的时候加入新顶点的位置不是任意的，除了 vi和vj之外没有被消掉 的图片区域是不能够添加顶点的。顶点与顶点之间的弧在连连看游戏中连线必

20、须是水平直 线和垂直直线，因此添加新的顶点的条件还应该满足按照连接方向，只用水平直线和垂直 直线就可连接成功。总结一下消除满足的条件：(1)连线不能超过三根以上，因此添加的 顶点不能超过两个；（2）添加顶点的位置不能是未消除图片的区域。（3）消除的路径为 最短路径。按照这个条件的改进Floyd算法：（1）玩家选中两个一模一样的图片，两个图 片分别作为顶点vi和vj； （2）如果vi和vj用垂直或水平直线连接后，不经过未消除的图 片那么，此路径为最短，可以直接消掉，结束；否那么转（3） ； （3）在已经消除的图片区 域，如果可以在vi水平或垂直方向添加一个顶点vO,这个顶点可以在水平或垂直方向上

21、成 功连接到vj?顶点，vi和vj可以消掉；否那么新顶点保存，进行（4） ； （4）如果可以在已经 消除的图片区域，在vO水平或垂直方向添加一个新的顶点vl,使得vl在vj的垂直或水平 方向，并且vl与vj的连线不经过未消除的图片区域，vi和vj消除；否那么提示选择错误。 由上述算法可以发现，数据结构可以帮助游戏提高工作效率，从而提高速度，加强了游戏 的可玩性。很多类型的游戏均可以应用上数据结构及其算法，例如解谜游戏，可以应用智 能算法，帮助实现复杂的游戏规那么及其游戏策略。应用数据结构的算法切忌照搬照抄，必 须结合游戏的实际状况进行选择、改进，必要时还要改存储结构，最终目的就是要提高游 戏的

22、工作效率。经过上述讨论，可以发现数据结构适合游戏的各个方面的程序设计，但这不是硬性。 如果为了引入数据结构，使得程序变得复杂，反而会影响游戏的速度，使得玩家对游戏丧 失兴趣。数据结构的用得要合情合理，恰到好处。如果对于数据的处理首先要发现各类数 据的结构特点及组织规律，采用合适的逻辑结构，在采用了合适的逻辑结构之后，就要考 虑便于操作的存储结构。存储结构通常分为顺序存储和链式存储，结合数据操作特性选择 最适合当前游戏的。对于角色的动作，利用数据结构的特殊线性表结构，更好的被系统调 度，从而使动作在画面上更逼真协调。对于游戏规那么，首先要根据游戏的类型进行选择， 依据规那么的要求选择合适的数据结

23、构，并且找到高效的算法，提高游戏的可玩性，提升运 行效率。综上所述，数据结构可以被用在游戏的各个方面，关键在于程序设计人员的开掘。每 进行设计的时候，都要针对问题的特点去找寻合适的数据结构，设计高效的算法。对于算 法多种多样，不是已有的算法就一定适合当前的情况，要求设计人员发现应用已有的算法 的问题，进行改进，并屡次调试，测算算法的时间及空间复杂度，反复改进，争取尽可能 提高算法的性能。如果某些方面不需要数据结构就不要硬搬硬套，防止使游戏程序复杂 化。总而言之，用好数据结构可以帮助游戏被更多玩家接受和喜爱。4、数据结构在人工智能的应用7月2日，微软（亚洲、|）互联网工程院宣布，第二代智能聊天机

24、器人“微软小冰”正式 上线，用户可以登录微软小冰官网进行“领养”操作。那么，微软小冰是个什么样的产品呢？首先，微软小冰是一款智能聊天机器人。除了 智能聊天之外，还兼具提醒、天气、星座、交通指南、餐饮点评等实用功能。其次，微软 小冰集成了微软在大数据、自然语义分析、机器学习和深度神经网络方面的技术积累，具 有非常强大的机器学习能力。所以，微软小冰还是人工智能机器人。人工智能主要有三个分支：第一，基于规那么的人工智能；第二，无规那么，计算机读取 大量数据，通过数据统计、概率分析等方法进行智能处理的人工智能；第三，基于神经元 网络的一种深度学习。基于规那么的人工智能，即在计算机内根据规定的语法结构录入规那么，并用这些规那么进