版权声明：尊重劳动成果，转载请标明原作者、出处；请勿用于任何商业目的！！！
2.1 队员管理小程序
作者：左光 出处：http://blog.csdn.net/wlnh_2004 时间：2005年4月27日
假如你是一个棒球队的管理人员，你想掌握目前哪些队员正在场上训练，那么你需要为你的笔记本电脑安装一个队员管理程序，这个程序将当前正在训练的所有队员保存在一组数据中，你可以用一个简单的数据结构来处理这些数据，同时你可能会需要以下几个操作：
·当某个队员来训练时，可以将他的相关信息插入到这组数据项中；
·想知道某个队员是否正在训练，可以通过在这组数据项中搜索他的号码是否存在来判断；
·当某个队员回家时，可以在这组数据项中删除它。
这三个操作构成了我们以后将学到的大部分数据结构的基本操作。
在这本书中，我们经常会通过小程序来演示一些特定的数据结构，这将使我们对数据结构和算法有一个感性的认识，在我们开始详细讨论之前，我们先来分析一个叫做 队员管理 的小程序，它会向我们演示如何对一个数组进行插入、搜索和删除操作。
图2.1显示了这个小程序的样子
图2.1显示了一个大小为20个单元的数组，其中包含了10个数据。你可以把这些数据看作是你的棒球队员。我们假设每个队员都有一件球衣，在球衣背面标有队员的号码，为了使程序运行起来更好看，假设球衣是由各种不同的颜色组成的。在数组中你可以看到队员的号码和他球衣的颜色信息。
图2.1 ：队员管理小程序
这个小程序演示了上面提到的三个基本功能：
·插入按钮插入一个新的数据；
·搜索按钮搜索某个特定的数据；
·删除按钮删除一个特定的数据；
利用新建按钮，你可以创建一个确定大小的数组；利用填充按钮，你可以填充一些数据到这个数组中。这些数据会有随机的号码和颜色值，号码的大小在0到999之间。
你也可以决定你创建的新数据是否可以有重复，这个问题我们将稍后讨论，在这里默认的情况是无重复，“无重复”单选按钮将被选定。
插入数据
初始情况是：一个大小为20个单元的数组，其中包含了10个数据，且没有重复数据。当你的一个队员到达训练场地时，你可以将他的号码插入到这个数组中，首先单击一下插入按钮，这时系统会提示你：
请输入要插入数据的关键值(在这里是球员的号码)
在右上角的文本框中输入这个球员的号码，比如说678，然后再单击一下插入按钮，系统将证实你的选择：
将要插入数据，关键值为678
最后再单击一下插入按钮，这时将创建一个数据，它由一个关键值(球员的号码)和一个随机的颜色值组成，被存入数组的第一个空单元中，这时系统将有如下的提示：
插入数据成功，关键值678，位置10
在图中每一个按钮都都代表一种算法，算法的步骤越多，算法所花费的时间越长。在 Array 小程序中，插入数据的过程是非常快，仅仅需要一个步骤，这是因为一个新的数据总是被插入到数组的第一个空单元中，算法总是知道这个空单元的具体位置，因为它知道数组中已经存在的多少个数据，最后一个数据的后面就是第一个空单元。然而，搜索和删除算法就没有那么快了。
在无重复情况下，你不可能插入一个已经存在的球员号码，如果你这样做了，系统会显示一个错误信息，但不会阻止数据的插入，我们只是假设你不会犯这样的错误。
搜索数据
单击查询按钮，系统将要求你输入要查询球员的关键值（在这里是球员的号码），你可以从图中显示的数据中选出正中间的一项，将它的数值输入，然后再一次单击查询按钮，这时红色的箭头将会从第0项向下移动，每单击一下，程序都会比较箭头所指的数据和你输入的数据是否相同，同时系统会给出类似下面的提示信息：
正在比较当前数据，位置2
当找到你需要的数据时，你会看到这样的信息：
发现要查找的数据，关键值505
无论你键入的是什么值，在无重复的情况下，第一次找到所需的数据后，查询便停止了。
如果你输入了一个不存在的数值，系统将查找每一个非空单元，直到最后一个数据，完了它会告诉你无法找到你需要的数据。
注意，在无重复值的情况下，搜索算法找到所需数据，平均需要查找一半的数据项。如果查找的数据在数组中靠前，将会被发现的更快一点；如果要查找的数据在数组中靠后，将会被发现的更慢一点。在一个有N个数据项的数组中，找到所需数据平均需要查找N/2个数据项；在最坏的情况下，如果要查找的数据排在最后一个，找到它需要从头至尾查找所有N个数据项。
从上面我们可以看出，为什么搜索数据比插入数据要花费更长的时间。
删除数据
删除算法假设所有的数据项都是连续的，即在数据之间没有空单元。删除算法的第一步是查找需要删除的数据，确定它的位置，然后将该数据之后所有的数据向前移动一个单元，该数据即被删除，如图2.2所示：
图2.2：删除一个数据
在图2.2中，第5单元中的数据（数值38）被删除，第6单元的内容向上移动至第5单元，第7单元的数据向上移动至第6单元，依次类推直至最后一个单元。
在无重复的情况下，删除算法平均需要查找N/2个数据，然后移动剩下N/2个数据，总共需要N个步骤。
关于重复
在一个无重复的数据结构中，我们插入一条新的数据时应该先检查一下这条数据是否已经存在，这个过程通常需要花费N个步骤，这时效率非常低下的，所以在这里我们通常不做这项检查。
有重复情况下的搜索
在右重复的情况下进行搜索，通常在查找到第一个数据后还需要继续向下查找，直到最后一条数据。当然你也可以在找到第一条匹配数据后停止，这完全看你的需要，是要找“每一个蓝眼睛的人”还是要找“一个蓝眼睛的人”。
有重复情况下的插入
有重复情况下的插入和无重复情况下的插入，方法是一样的，仅仅需要一个步骤。但是需要注意的是，如果重复不被允许，插入一条新的数据通常要将所有的数据检测一遍。
有重复情况下的删除
在有重复的情况下，删除数据可能更复杂一些，通常依据你对删除的定义。如果仅仅删除第一条被发现的数据，平均情况下，需要进行N/2次查找和N/2次移动，这和无重复的情况下是一样的。
如果要删除所有具有同样关键值的数据，就需要进行多次同样的删除操作，通常是N次查找和最少N/2次移动，移动次数的多少要看找到了多少个重复数据。
表2.1显示了在无重复和有重复的情况下，各种算法所需要的查找次数和移动次数。
表2.1：无重复和有重复的对比
无重复
有重复
搜索
N/2次查找
N次查找
插入
不用查找
不用查找
删除
N/2次查找
N次查找
N/2次移动
最少N/2次移动
备注:
原文参考英文版《Data Structures & Algorithms in Java》，第一次翻译，英文水平有限，如果有错误的地方请大家指正。文中去掉了一些关于 Java 语法和面向对象编程的内容，主要关注数据结构与算法，相关内容请自己查找资料。
原文参考英文版《Data Structures & Algorithms in Java》，第一次翻译，英文水平有限，如果有错误的地方请大家指正。文中去掉了一些关于 Java 语法和面向对象编程的内容，主要关注数据结构与算法，相关内容请自己查找资料。
