数据结构绪论

第一章你我无猜，四下里管中窥豹每学一门新事物，就像重回童年，那种懵懂那种好奇，令我四处窥望。大千世界，变化万千，我童年的每一眼都如管中窥豹，只见一斑。现在想来，这种好奇是美丽的，它会让我不自觉地爱上对方。初恋，便是人生初见。1．谈起我心爱的《数据结构》遥想20年前……先泪崩20秒——致我们终将失去的学妹！——老师，不是《致我们终将失去的青春》吗？——有多远死多远。没有学妹，青春有毛用啊？没有和学妹绯闻的青春都不是青春，至少是不完整的。——老师，请节哀！——人生自是有情痴，此恨不关风和月。——老师，要不我们先下课吧！好方便您去寻找旧爱。——想得美！每当数据结构上课铃响的时候，我就化悲痛为力量。好了，眼泪咽回去了，初恋的都不懂爱情，把这一页揭过去，我们继续来讨论母猪的产后护理问题——我们讲到哪啦？话说当年，本小生风华正茂，挥斥方遒，左手一把折扇，右手一只鸟笼。有个基友叫国城，见到我就倾倒，从上个世纪开始，一直追求我到今天，我打死都不从他。爱我的人为我付出一切，我却为我爱的人狂乱心碎。同学们哪，一失足成千古恨啊，当年就因为我夜长梦多，数据结构课上一不小心继续盗梦空间，我那呕血追求的学妹就此跟我决裂。她跟我的分手宣言就是：“数据结构课上你都敢睡？别扯淡IT界，就连计算机二级你都过不了，我跟一个拿不到学位证书的人谈什么谈？近墨者黑。”从此，我在她美丽的瞳孔里，始终是鲍鱼之肆。公元一九九四年某个深夜，我的日记上写道：“文人独酌当晓月，思者孤形缠林间，一醉红尘多少事，眉上沟壑增云烟。”此诗写罢，十余年再未写诗。小声自言自语一句，学妹的名字就在诗里，你懂的。2．数据结构是什么东东？要搞清数据结构是什么东东，首先要搞懂计算机是什么东东。很久很久以前，多久？至少是几百万年前吧，我们的某一位曾曾曾曾……曾爷爷，一身拉风的毛根根丝滑，虽然没有用潘婷，但他刚在泥巴坑里和一群泥鳅躲了半天猫猫，然后又在清溪里被一排乌龟拌了几个大跟头，发质比林志玲还好。就在他逍遥地仰天长啸后不久，他看到了树上那个跟他有缘的苹果，谁说不是呢？人类的历史就是人类和苹果扯不清的关系。恰巧，祖先爷爷肚子奏响了进军的号角，他伸长手臂，努力地上窜下跳，但就是够不着。也不知道这树吸收了什么养分，怎么长那么高。曾的无数次方爷爷看看天上飞翔的鸟，于是坐在地上开始困惑，但人类困惑的根源却是几百万年后的我，在公交3路车上才恍然大悟的——人类困惑的根源是没有进化好！曾的无数次方爷爷困惑着困惑着，抓耳挠腮，不自觉地抓起了地上的一根枯树杈，那根树杈很长，他坐着一挥正巧打到了那个苹果，那个苹果在枝上一荡，掉了下来。这一刻，一不经意成为了永恒，就像我的人生里不经意地在人群里对文思眉多看了一眼。这根枯树杈和你的计算机一样，都是人类的工具，都是协助人类器官功能延伸的，只是树杈是协助手脚，计算机协助的也许是你的大脑。计算机既然是人类的工具，那我想请他帮我把宿舍里那盆脏衣服和臭袜子洗了。可以，谁叫计算机是工具呢！但为了防止你回宿舍没有衣服换，你必须要有相应的程序。透露一个天机：实际上，在我们这个时代，大多数计算机真正只会干一样活——执行程序，其他的都是假象。在这儿，我们用到计算机界一个常用的公式：程序=算法+数据结构你要求处理的衣服（包括各种款色加各种颜色的内裤、外套、袜子）就是你所面临的数据结构，或许这儿我们该叫它们“结构数据”才对，它所承担的责任便是怎么将现实中的问题转化成计算机能够接受的格式，计算机不是你孙子，你光扯着嗓门对着计算机喊，嗓子哑了也没用。“数据结构”这个术语从字面上看，分成数据和结构两部分。数据就是将来计算机要处理的数字化信息。前些年有本很火的书，叫《数字化生存》，讲的就是我们的社会生活正在走向全面数字化，原因之一，就是我们在依赖数字计算机。味觉、视觉、触觉等等所有人类感知世界的途径都在一步步用冷冰冰的数字代替，你的臭袜子脏衣服要想要计算机帮你洗，就得进行数字化，也就是变成数据。我们把每一个数据作为一个结点。数据来了，得按照数据间的关系进行组织，这个组织就形成结构，胡子辫子不能一把抓，袜子内裤不能完全一样处理。总之，数据结构就是待解决的现实问题转换成的有组织有纪律的数字形式，以便数字计算机处理，本门课程更关注的是数据的组织问题，也就是结构。至于算法嘛，说白了就是计算机怎么来加工数据结构的，具体步骤如何，先做什么再做什么。算法因人而异，各个人想到的算法是经常不一样的，否则怎么会有的人衬衫洗完了领口依然脏，有的人洗完了衬衫内裤更加脏呢？要想对算法有个更清晰的认识，大家不妨去《水浒传》里看看，王婆是怎么撮合西门官人和潘金莲的。从第一步王婆请潘金莲代做寿衣，到最后西门官人故意掉筷子，每一步都是精彩纷呈。我坚信，中国人如此热衷于兵法和算计，算法人才定然是个顶个的绝顶高手。3．常见的数据结构有哪些？数据的结构分成逻辑和物理两种情况，这就好比是一个军人，在逻辑上组织，他可以是少将师长或中士排长，在物理上组织，他可以在大上海的南京路巡逻，也可以在南沙群岛驻扎。数据的逻辑结构就是在意识上，我们用什么方法组织管理他们，是排成一个心型，还是摆成一条直线；数据的物理结构是这些数据在存储器上的实际位置安排，存储器可以是内存，也可以是外存（硬盘、U盘等）。先来说说逻辑结构。马克思主义哲学里讲，世界是运动的，普遍联系的，所以你想说，你和美国的一只狗毫无关系是完全错误的，在数据结构的世界里，你们至少是属于同一个集合的。集合的概念是很松散的，加个特征我们就可以把风牛马不相及的事物搁到一起去。大作家肖伯纳说，全世界适合做你终身伴侣的人至少有五百万，那相信爱情缘分的人简直就是傻子呆子，哪来的缘分啊？纯粹巧合地运动了一些跟人类情感有关的细胞而已。那些“非你不嫁”和“非你不娶”，原来是那么的愚不可及。我就是这样的愚不可及，但正因为有像我这样的傻蛋，才点缀得这个世界美妙得如繁星点点。除了集合，我们常说的数据结构有：线形结构、树形结构和图形结构。年轻的时候，喜欢《三国演义》这部把军事历史武侠化的小说，里面的大小武将就是一个个身怀武功的高手，于是，喜欢将这些武将按照武力高低进行排名，像梁山一百零八将那样，一一排个座次。比如，我们假设如下，第一是吕布，第二是赵云，第三是张飞，第四是典韦，依次往后。这种结构就是线型结构，它每一个位置都是唯一的一个人，而且前后的人也是确定不变的。可以根据这种关系，画成图1-1，就像体育课老师让他们站成一队，这就是线形结构。但事实上，我们做不到这一点，所以无论我怎么给三国武将排名，到网上都是被人一顿臭骂。咱中国自打网络开始民用，网上骂人便成为一种司空见惯，这让本人极为反感，所以发誓在网上绝不骂人，无论别人怎么说。希望读者诸君也能黾勉同心，不在网络对陌生人恶语相向。图1-1线形结构示例话回正题，有些武将是无法分出高下的。比如张飞对马超，两人挑灯夜战，不分白天晚上，废寝忘食地打，也没决出雌雄，现在非要给他们分个子丑寅卯，似乎不合适，所以，我们不妨将他们放在同一层次，这种情况在三国演义里不占少数。比如，我们假设（不要再骂我）：吕布单挑能赢赵云、张飞、关羽；关羽胜张辽、曹操；张飞能胜典韦。这样，他们之间就可以画出一个如图2一样的层次关系，这个结构就是树形结构。图1-2树形结构示例为啥叫树形结构呢？因为这结构画出来有那么一丁点像倒着的树，不妨看看图3。大家如果去黄山旅游的话，会听导游说，哪个山峰像猴子，哪块石头像猪八戒，基本都是三分神似，七分想象。我跟部分人一样，刚开始觉得一点都不像，学完了这门课后，感觉就是树，一点都不差的。树的结构里，主要特点是层次关系，从一个树根开始，一旦形成分支，便各自发展不再交汇，如果发生交汇，那树的基本特征就被打破，变成了一种称为图的较为复杂的结构。图1-3树和倒着的树假如如图2所示的树形结构里，曹操作为关羽的手下败将，却能大发神威，击败关羽克星吕布，也就是出现了棒打老虎，老虎吃鸡，鸡啄棒子这种环形关系，树形结构就不再存在，形成图的结构。图结构可以参考图1-4。图1-4图形结构示意图这门课里，我们基本上把集合这种结构打入冷宫了，因为小主说了，这是极好的。由刚才三国武将的叽里咕噜，我们不难看出，线形结构对数据的要求是最高的，其次是树形，再次是图形。但处理起来，最方便是线形，其次树形，最后图形。看到了吧，这就是辨证的无处不在。我们要处理树形和图形结构的时候，经常要想着法子将他转换成线形，就因为它最方便。所以，数据结构中的逻辑结构粗分也可以分成两大类：线形结构和非线性结构。说完逻辑结构，我们来说物理结构。物理结构现在主要有两种：顺序存储结构和链式存储结构。假如我们每个人都是数据，有一天我们江大四少（对外称江苏大学四大杰出青年，对内称江大四大流氓）出去旅游，晚上需要找个宾馆休息，相当于数据进入存储器，每人一个房间。我们人是排着队去的，如果宾馆给我们安排房间是老大住K号房，老二住K+1号房，老三住K+2号房，四弟住K+3号房，这就叫顺序存储。如果老大晚上睡不着觉，想跟老三聊会，他出门之后直接往后数两个房间就到了，很方便。专业一点讲，所谓顺序存储，就是逻辑上相邻的数据到物理上也完全一模一样地相邻。如果物理结构上就这两种，那我们说，非此即彼，不满足顺序存储的那就是链式存储，专业上讲：逻辑上相邻的数据到物理存储上不相邻。大家如果有点旅游经历就会知道，如果你们一大票子人住旅馆，房间能够给你们顺序存储，那这家旅店今天的生意肯定好不到哪儿去。旅店有了客人后，再来一大堆人，住宿就势必要分散房间，有的还可能要住到别的旅店去。但大家被打散了，怎么联络呢？怎么才能把大家的顺序再还原呢？这就需要“链”了。在希腊神话里，有个忒修斯进迷宫杀弥诺陶洛斯（也就是米诺牛）的故事，故事的前因后果都很精彩，有兴趣的读者可以去看看。忒修斯为了解决在迷宫里不迷路的问题——据说这迷宫已经被考古学家发现了，真的会让人转晕——用一个线团来标记方向，最后成功了。数据被打散了扔进浩瀚如宇宙的存储器中，如果不用个类似于线团这样的东西链着，找不到是迟早的事。图1-5忒修斯与弥诺陶洛斯搏斗，作者：\o"让-埃蒂安·拉梅（页面不存在）"让-埃蒂安·拉梅我们的“链”事实上很简单，也就是在每个数据后面加个尾巴，尾巴上面标注上它后面的数据所在的位置。存储器像宾馆房间一样，每个单元都有个类似门牌号的地址，链式存储就是在每个数据后面加一个后续数据的地址。这样虽说是需要增加额外的存储空间开销，但却能实现数据离散的放置，提高存储器使用的灵活性。再啰嗦一句：逻辑结构是针对需要解决的现实问题而提出来的，物理结构是计算机内如何解决数据存放的。4．学霸模式数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关间题的学科。数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。我们把每一个独立的小数据作为一个结点。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。按照视点的不同，我们把数据结构分为逻辑结构和物理结构。逻辑结构:是指数据对象中数据元素之间的相互关系。这也是我们今后最需要关注的问题。逻辑结构分为以下四种：1．集合结构集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。2．线性结构线性结构：线性结构中的数据元素之间是一对一的关系。3．树形结构树形结构：树形结构中的数据元素之间存在一种一对多的层次关系。4．图形结构图形结构：图形结构的数据元素是多对多的关系。物理结构：是指数据的逻辑结构在计算机中的存储形式。数据元素的存储结构形式有两种：顺序存储和链式存储。顺序存储结构是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。链式存储结构二是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。程序=数据结构+算法算法是基于数据结构的，它是在一定数据结构上的一系列操作步骤。5．亮出你的牛刀我们来看个例子，看看数据结构这把武器的威力。面对恶化的交通情况，我们通常是设置信号灯来规范各种车辆行人的通行问题，红灯用来禁止某条线路的通行，绿灯用来放行某条线路，如果有些路线不存在冲突，则可以用一个灯来约束。我们现在的问题是，面对如图1-6这样的不规则多岔路口，至少需要多少个灯才能保障此处的交通。图1-6多岔路口类似这样的问题，用计算机解决，就必须将它转换成计算机能够处理的数据。这儿的数据主要是这个多岔路口的信息，更进一步讲是若干条通行线路的信息，这些通行线路有的可以同时放行，有的不可以。如何来组织这些信息，就要借助数据结构的力量。在这里，这些数据之间没有绝对的前驱和后继的关系，也没有层次关系，所以需要用到图的结构去处理这些数据，每条线路作为图的一个结点，把这些可以