数据结构
——数据结构在生活中的应用
专 业： 学 号： 姓 名：
数据结构在生活中的应用
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。
数据结构包括的主要内容有数组 (Array) 栈 (Stack) 队列 (Queue) 链表 (Linked List)树 (Tree) 图 (Graph) 堆 (Heap) 散列表 (Hash)等。
数据结构在生活中的很多地方又有应用，在我们的日常生活中，应用到数据结构的地方有很多地方，实例到处都是，比如说，做搜索引擎，对字符串的各种查找、索引的算法就有很高要求；做人工智能，对模式识别、搜索的要求就很高；做数据库设计，对字典、内外排序、搜索与索引以及数据的连接方式都有很高要求；做通讯密码，对数论、Fourier分析有要求；等等。
具体内容的应用也有很多，例如：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系等;。
栈是数据结构中重要的线性结构，是一种特殊的线性表，只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶，另一端称为栈底。栈项的当前位置是动态的，对栈顶当前位置的标记称为栈项指针。当栈中没有数据元素时，称为空栈。栈的插入操作称为进栈或入栈，栈的删除操作称为退栈或出栈。栈的应用非常广泛，在日常生活中，有许多类似栈的例子，如刷洗盘子时，依次把每个洗净的盘子放到洗好的盘子上。相当于进栈；取用盘子时，从一摞盘子上一个接一个地向下拿，相当于出栈。在计算机中进行算术表达式的计算是通过栈来实现的。除此之外，栈还在游戏中应用到，例如迷宫问题。
队列（Queue）是运算受到的一种线性表。只允许在表的一端进行插入，而在另一端进行删除元素的线性表。队尾（rear）是允许插入的一端。队头（front）是允许删除的一端。空队列是不含元素的空表。在日常生活中有许多“队列“的例子，如车站售票口买票的队伍，排在前面的人先买到票离开队伍，后来的人则加入队伍的末尾等候买票；其特点是“先进先出”(First In First Out)或“后进后出”(Last In Last Out)。队列还可以很好地异步处理数据传送和存储，当你频繁地向数据库中插入数据、频繁地向搜索引擎提交数据，就可采取队列来异步插入。另外，还可以将较慢的处理逻辑、有并发数量的处理逻辑，通过消息队列放在后台处理，例如FLV视频转换、发送手机短信、发送电子邮件等。（
数据结构里最重要的两个结构就是树和图。比如一个公司由上到下的成员职位、一天中要做的事、一生的计划、你的目标可以分为一个个小的目标等等都是相当于数据结构中的树的应用。图是描述事物之间关系的，当你询问GPS时，GPS系统为什么能给指出一条两地之间的路线，这就是利用了图的存储和遍历运算，求出最优解。在现实生活中很多复杂的关系都可以用图来描述并利用图去解决一些问题。
数据结构是计算机软件和计算机应用专业的核心课程之一，在众多的计算机系统软件和应用软件中都要用到各种数据结构。因此，仅掌握几种计算机语言是难以应付众多复杂的课题的。要想有效地使用计算机，还必须学习数据结构的有关知识。
数据结构解决的实际应用问题： 1． 计算机处理问题的分类 （1）数值计算问题
在计算机发展初期，人们使用计算机主要是处理数值计算问题。 （2）非数值性问题
随着计算机应用领域的扩大和软、硬件的发展，\"非数值性问题\"越来越
显得重要。据统计，当今处理非数值性问题占用了90%以上的机器时间，这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决此类问题的关键已不再是分析数学和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。
2．非数值问题求解
著名的瑞士计算机科学家沃思（N.Wirth）教授曾提出： 算法+数据结构=程序
数据结构：是指数据的逻辑结构和存储结构 算法：是对数据运算的描述
例如电话号码查询问题：编一个查询某个城市或单位的私人电话号码的程序。要求对任意给出的一个姓名，若该人有电话号码，则迅速找到其电话号码；否则指出该人没有电话号码。
要解此问题首先构造一张电话号码登记表。表中每个结点存放两个数据项： 姓名和电话号码。
要写出好的查找算法，取决于这张表的结构及存储方式。最简单的方式是将表中结点顺序地存储在计算机中。查找时从头开始依次查对姓名，直到找出正确的姓名或是找遍整个表均没有找到为止。这种查找算法对于一个不大的单位或许是可行的，但对一个有成千上万私人电话的城市就不实用了。若这张表是按姓氏排列的，则可另造一张姓氏索引表，采用如下图所示的存储结构。那么查找过程是先在索引表中查对姓氏，然后根据索引表中的地址到电话号码登记表中核查姓名，这样查找登记表时就无需查找其它姓氏的名字了。因此，在这种新的结构上产生的查找算法就更为有效。
又比如田径赛的时间安排问题：假设某校的田径选拔赛共设六个项目的比赛，即跳高、跳远、标、铅球、100米和200米短跑，规定每个选手至多参加三个项目的比赛。现有五名选手报名比赛，选手所选择的项目如参赛选手比赛项目表所示。现在要求设计一个竞赛日程安排表，使得在尽可以短的时间内安排完比赛。
（1）为了能较好地解决这个问题，首先应该选择一个合适的数据结构来表示它。2表示该问题的数据结构模型图如右下图（图中顶点代表竞赛项目，在所有的两个不能同时进行比赛的项目之间连上一条边）。显然同一个选手选择的几个项目是不能在同一时间内比赛的，因此该选手选择的项目中应该两两有边相连。
（2）竞赛项目的时间安排问题可以抽象为对无向图进行\"着色\"操作：即用尽可能少的颜色去给图中每个顶点着色，使得任意两个有边连接的相邻顶点着上不同的颜色。每一种颜色表示一个比赛时间，着上同一种颜色的顶点是可以安排在同一时间内竞赛的项目。由此可得：只要安排4个不同的时间竞赛即可。时间1内可以比赛跳高（A）和标（C），时间2内可以比赛跳远（B）和铅球（D），时间3和时间4内分别比赛100米（E）和200米（F）。
在游戏中,链表主要应用在有大规模删除,添加的应用上。不过,它也有相应的缺点,就是查询是顺序查找,比较耗费时间,并且存储密度较小,对空间的需求较大。 如果通过对游戏数据的一些控制,限定大规模的添加,也就是确定了内存需求的上限,可以应用顺序表来代替链表,在某些情况下,顺序表可以弥补链表时间性能上的损失。当然,应用链表,顺序表还是主要依靠当时的具体情况。
栈和队列是两种特殊的线性结构,在游戏当中,一般应用在脚本引擎,操作界
面,数据判定当中。
在游戏中,大多数应用图的地方是路径搜索，在情节脚本中,描述各个情节之间的关系。
诸如此类的还有很多例子，数据结构与算法，在做游戏程序的时候用的最多了。
比如求迷宫的最短路径：现要求设计一个算法找一条从迷宫入口到出口的最短路径。
本算法要求找一条迷宫的最短路径，算法的基本思想为：从迷宫入口点（1,1）出发，向四周搜索，记下所有一步能到达的坐标点；然后依次再从这些点出发，再记下所有一步能到达的坐标点，…，依此类推，直到到达迷宫的出口点(m,n)为止，然后从出口点沿搜索路径回溯直至入口。这样就找到了一条迷宫的最短路径，否则迷宫无路径。
有关迷宫的数据结构、试探方向、如何防止重复到达某点以避免发生死循环的问题与例3.2处理相同，不同的是：如何存储搜索路径。在搜索过程中必须记下每一个可到达的坐标点，以便从这些点出发继续向四周搜索。由于先到达的点先向下搜索，故引进一个“先进先出”数据结构------队列来保存已到达的坐标点。到达迷宫的出口点(m,n)后，为了能够从出口点沿搜索路径回溯直至入口，对于每一点，记下坐标点的同时，还要记下到达该点的前驱点，因此，用一个结构数组sq[num]作为队列的存储空间，因为迷宫中每个点至多被访问一次，所以num至多等于m*n。sq的每一个结构有三个域：x,y和pre，其中x,y分别为所到达的点的坐标，pre为前驱点在sq中的坐标，是一个静态链域。除sq外，还有队头、队尾指针：front和rear用来指向队头和队尾元素。
队的定义如下：
typedef struct { int x,y; int pre; }sqtype; sqtype sq[num]; int front,rear;
初始状态，队列中只有一个元素sq[１]记录的是入口点的坐标（１,１），因为该点是出发点，因此没有前驱点，pre域为－１，队头指针front和队尾指针rear均指向它，此后搜索时都是以front所指点为搜索的出发点，当搜索到一个可到达点时，即将该点的坐标及front所指点的位置入队，不但记下了到达点的坐标，还记下了它的前驱点。front所指点的８个方向搜索完毕后，则出队，继续对下一点搜索。搜索过程中遇到出口点则成功，搜索结束，打印出迷宫最短路径，算法结束；或者当前队空即没有搜索点了，表明没有路径算法也结束。
算法如下：
void path(maze，move)
int maze[m][n]；/*迷宫数组*/ item move[8]；/*坐标增量数组*/ { sqtype sq[NUM]; int front,rear；
int x,y,i,j,v; front=rear=0;
sq[０].x=1; sq[０].y=1; sq[０].pre=-1; /*入口点入队*/ maze[1,1]=-1;
while (front<=rear) /*队列不空*/ { x=sq[front].x ; y=sq[front ].y ; for (v=0;v<8;v++)
{ i=x+move[v].x; j=x+move[v].y; if (maze[i][j]==0) { rear++;
sq[rear].x=i; sq[rear].y=j; sq[rear].pre=front; maze[i][j]=-1; }
if (i==m&&j==n)
{ printpath(sq,rear); /*打印迷宫*/ restore(maze); /*恢复迷宫*/ return 1; }
} /*for v*/
front++; /*当前点搜索完，取下一个点搜索 */ } /*while*/ return 0; } /*path*/
void printpath(sqtype sq[],int rear) /*打印迷宫路径*/ { int i; i=rear;
do { printf(＂ (%d,%d)＂,sq[i].x , sq[i].y) ; i=sq[i].pre; /*回溯*/ } while (i!=-1); } /*printpath*/
学习数据结构课程除了要学习和研究已有的数据存储结构和数据处理算法之外，更重要的是根据自己解决实际问题的需要，进行有效的数据存储和数据处理。相信只要我们不断的将所学的理论知识在实际应用中摸索和实践，就一定能够熟能生巧，把这门知识运用的炉火纯青。
