数据结构--大学公开视频课
数据结构视频课程绪论:
1.关于数据组织
我们这门课的名字呢,叫做数据结构基础。所以我们第一个最自然的问题就是,到底什么是数据结构呢?其实这还真不是一个很简单的问题,因为直到今天为止,我们都没有一个统一的标准的答案,那接下来呢,我自己随便找了一些定义给大家看一下。哎,这个呢,是萨尼在数据结构,算法与应用里面给的定义。这一块呢,是这个沙尔在数据结构与算法分析这本书里给的定义。这个定义呢,是从这个中文维基百科上面找到的。你能看懂这些定义吗?呃,其实看不懂不要紧的,看不懂很正常,因为你还没开始学呢,等你学完这门课以后,再回过头来看,呃,可能发现他们其实说的都是同一回事情。如果现在你就能看懂的话,那我很佩服你。不过呢,我们可以观察一下哈,有两个词好像经常在一起出现的,你看萨尼的这本书,叫做数据结构、算法与应用。S这本书呢,也叫数据结构与算法分析。在中文维基百科的定义里面呢?他干脆说,精心选择的数据结构可以带来最优效率的算法。所以看起来呢,数据结构和算法是两个经常挨在一起的东西,那么到底要怎么定义数据结构这个东西呢?呃,我想一句话两句话是讲不清楚的,不如我来给你讲三个例子,我们的第一个例子是说如何在书架上摆放图书。也就是说,我给了你一些书架,然后又有一堆书进来,你要把它们怎么放到书架上去呢?换言之说,我给了你一堆数据,然后给了你一些存储空间,你要怎么把这些数据存起来呢?考虑一会儿再回来。
其实呢,我刚才那个问题问的很不科学,因为我没有告诉你说,我给你的书架到底是长这样呢,还是长这样呢,还是长成这样呢?所以你就知道了,当我问你一个数据怎么组织的时候,其实是跟这个数据的规模有关系的啊,不一样规模的问题,它处理起来的难度就不一样,难在什么地方呢?难不在于说你要把它怎么放,而在于放这个书是为了做事情用的。所以我们说图书的摆放其实是跟两个操作直接相关的。一个呢,是新书怎么插入的问题,再一个呢,是怎么找到某一本指定书的问题,我不知道你刚才是怎么考虑的哈,那我呢,拍拍脑袋就想到三个不一样的办法,我们先来看最简单最直接的那个叫做随便放,随便放一个好处,新书怎么插入,这个操作是非常简单的,哪有空就放哪,那我最简单的呢,就是把所有的书一本一本一本挨着放,新来一本书呢,就直接贴在最后,所以呢,所有的。新书哪里有空放哪里,是一步到位的,很简单。放起来简单。第二个操作怎么办呢。查找怎么办呢?那就会成为一件很恐怖的事情。累死。什么时候真的累死呢?其实你如果只有一个很小的书架,就这么几本书,那是累不死的。如果是我们第三张图片上看到那个巨型的书城,然后你想象里面的图书全部都是随便放的。然后我来问你说你这个书城里有没有某一本书,其实那本书呢,你没有,但是你忘了,你有没有。那你怎么能确定它到底有还是没有呢?你就只好从头到尾把每一本书都过一遍,然后才能叹一口气说,啊,不好意思,这本书我们真的没有。所以说我们有没有一种稍微聪明一点的办法去解决问题呢?这就来了,怎么能让我找书找的方便一点呢?第二个方法就是按照书名的拼音字母顺序放,有了这个字母序以后,查找就方便多了。一个最聪明的办法是什么?二分查找,什么叫二分查找呢?我想你可能是知道的,就比如说我们有这么一长排的书放在这。然后呢,我们来找我们这本教材,数据结构,它是S开头的,那我先从这一排的中间找一本书出来看一下,它是可能是离散数学,比如说啊,L开头的,那我知道S在L的后面,所以呢,离散数学前面的书我就不用管它了,我的查找范围缩小了一半,从L开始往后找,然后再找这一半的中间啊,比如说我看到一本书是网络技术基础,那是W。那我知道S呢,是在L和W中间的,于是呢,我的范围又缩小了一半,那以此类推,呃,我可以每次都找,跟中间这一本比,跟中间这一本比,很快的就会把范围缩小到一本书上,我就会知道我这本书到底是有还是没有。那这个方法呢,看上去就比前面那个聪明的多了,它很好的解决了这个查找的问题,但是。但是第一个怎么办呀?新书来了,怎么插入呢?它就会成为一个新的头痛的问题,比如说我新买了一本书,叫做阿Q正传,它是a开头的。呃,惨了,那我们得把所有的书差不多,所有的书都要一本一本,一本一本往后错位,一直到前面留出一个空当给新书插进去,所以呢,你说要找一个两全其美的方法,还真不是很容易的一件事情。那你刚才想的那个方法是什么呢?我们来想一下,书店里面到底是怎么摆书的呢?我们进到一个书城,然后想买这本数据结构。我们要怎么开始找?你不可能是从第一本开始找,也不可能是摸到随便中间某个位置开始找,不是这样的。你进到一个书城里面,第一件事情要找的是计算机类的书在哪里?对不对啊?书店里的书呢,通常它都是按照书的类别来分的,比如说我们有社会科学类,有文学类、艺术类,有理科,有工科,然后工科下面呢,还会再分的更细一点,比如说我们计算机类可能就分在工科的下面,这种分法有什么好处呢?我们把书架划分成几块区域。哪块区域对应着一个类,在每一个类里面呢?按照书名的拼音字母来顺序排放。这种方法的一个最大的好处是说,不管我在每一个类里面做什么样的操作,总归来说这个图书的规模都小了很多。跟我整个书城的书的规模相比,我是某一类的。那么无论是查找还是插入。都会方便一点,查找呢,就是在二分查找之前,我们先定一个类别。然后在一个类的一个小范围里面做二分查找,那可以更快的找到我们想要的书,如果是插入呢。那么也是先进类别,呃,用二分查找来确定一下它应该被插在什么位置,然后一控位这件事情可能还是要做的,但是总归比我们最开始的那个要移的书的数量要少得多了。于是呢,我们的问题就来了。当然这个问题跟挖掘机没有关系哈,我们的问题呢有两个方面,一个呢是说空间要怎么分配好,我们分的各种类别的书,它的藏书量应该是不一样的,你是统一都给它分,每一种类都多少个书架。事先分好吗?所以这是一个很头痛的问题,你如果书架给多了呢,就会有一些空间始终空在那浪费着,你如果书架给小了呢,你进新书的时候会不断的要加新柜子,这个也是一件很讨厌的事情,这是一个问题。另外一个问题呢,就是类别到底要分多细比较好呢?你要是分的比较粗,那么同一类里面的书就有很多,那你的工作量就还是会很大。呃,你要想减小工作量呢,最好类别分的比较细一点,但是类别一分细,带来的什么副作用呢,就是类别太多了。你想象一下,你要进到一个书城里找书,然后人家告诉你说,我们这个书城里头有3万个种类的图书,于是你要找那本书属于哪一类呢?这个又傻掉了是吧,呃,所以呢,就是这个类要怎么分,也是要斟酌的问题,你有没有什么更好的办法呢?我们这个故事想说明的问题是说,解决问题方法的效率跟数据的组织方式是直接相关的。
2.算法的定义
我们来看一下什么是算法。算法的定义呢,要比这个数据结构容易定义一点。那算法的英文名称呢,是叫做alism,它包含这么几个要素,首先呢,说算法是一个有限的指令集,它就是堆指令放在一起去做一件事情,而这个指令集呢,一定是有限的,他有的时候会接受输入,有的时候呢,不需要输入,但是无论如何,它一定会产生至少一个输出,否则的话呢,这个算法就没有什么意义了。那么算法一定是在有限步骤之后终止的,那他跟我们程序不一样,有些程序呢,可以一直跑,比如说操作系统,只要你不关机,它就一直跑在上面,呃,在我们描述一个算法的时候,它是不能有这种无限循环的概念的。描述算法的每一条指令的时候,一定要每一条指令必须有充分明确的目标,是不可以有歧义的。另外,就算清楚明白,但是目标不可以太远大,要在计算机能处理的范围之内。描述的手段要抽象,就是描述应该不依赖于任何一种计算机的语言以及具体的实现手段。怎么理解这句话呢?我们来看下面一个例子啊,这个例子呢,是关于选择排序算法的一个伪码描述,我们看一下上面这个伪码描述,看上去它非常像C语言的一个函数,它有一些C语言的关键字,比如说VO,比如说int诸如此类的啊,它还有一个for循环的外壳在外面,所以它看上去很像是C语言,但是呢,它又不是一个C语言的函数,因为它中间两个最核心的步骤是用自然语言来描述的啊,那么选择排序算法是怎么一回事呢?我从还没有排好序的这堆元素中间,每次选一个最小的元素,把它贴到已经排好序的那个子序列的最后面,于是呢,每次挑一个最小的贴上去,每次挑一个最小的贴上去,最后得到的就是一个从小到大排好序的序列。在这个伪代码的描述里面,我们注意看一下,它说的是从list I到list n减一中找一个最小圆,那就意味着我们没排好序的那个子序列放在哪里呢?就是放在从this I一直放到list n减一。隐含着,也就是说排好序的部分是放在哪里的呢?放在LIST01直到list I减一这个位置。OK,那么我们从没排好序的这一部分中间找一个最小圆,呃,然后我们记录一下它的位置叫main position,呃,记给这个变量,然后我们把这个位置的这个变量换到有序部分的最后位置。事实上呢,这个描述呢,还是很不清楚的,比如说哪是有序部分,哪是他的最后位置,都写的不是很清楚,呃,我们可以换一种更加清楚一点的维码描述,比如说从这里头找最小圆,我可以把它写的,诶,这看上去更像一个C语言的函数了哈,我给这函数取个名字叫scan for m,就是扫描去找这个最小圆,我把这个list这个表传进去,呃,它是从I到N减一去找它的最小圆,找到这个位置,把它赋值给main position这个变量,呃,这句话什么意思呢?什么叫把未排序部分的最小圆换到有序部分最后位置呢?我们这么一写就看的比较明白了,也就是说把这个位置上的元素换到list I这个位置,List I就是有序部分的最后位置。上面这段伪码描述一个很重要的特点是抽象。呃,很抽象吗?我们看上去好像他很具体的样子,其实他还是抽象的,抽象在哪里呢?呃,第一点就是说这个list虽然我们写的好像把它写成了一个数组的样子,但是他非要是个数组不可吗?不一定的,呃,我如果传进来的是一个链表的话,整个的算法依然是正确的。Swap这个我们写上去呢,好像是把它写成了一个函数的样子,但是我一定要用一个函数去实现swap吗?我是不是可以写一个宏去实现?那么这个都是具体实现的细节,在我们描述算法的时候是不关心的。