算法和数据结构

算法(suànfǎ)和数据结构第一页，共37页。算法(suànfǎ)和数据结构第二页，共37页。例5：媒体播放器如何(rúhé)把MP3文件转换成动听的音乐？空间复杂性(SpaceComplexity)：第三十二页，共37页。叙述冗长，很难清楚地表达算法的逻辑流程自然语言描述(miáoshù)i=i+1假设:先X后,第4着的棋局如右图：Word文档中插入的表格和图片如何表示？与首元素交换，第3次循环结束时间复杂性(TimeComplexity)：例：线性表的实现(shíxiàn)方法之1{确定A[i]到A[n]中最小整数的位置，设为j；什么(shénme)是算法？算法(suànfǎ)的流程图表示开发计算机应用的核心是：根据实际问题给出解题的算法，然后再将该算法在计算机上实现(即开发成为软件)然后,X有4种下子的方法:计算机求解问题(wèntí)的步骤(1)确定并理解问题；(2)寻找解决问题的方法与步骤，并将其表示成算法(Algorithm)；(3)使用某种程序设计(chénɡxùshèjì)语言描述该算法(编程),并进行调试；(4)运行程序，获得问题的解答；(5)进行评估，改进算法和程序第三页，共37页。1.什么(shénme)是算法？第四页，共37页。算法是解决问题的方法(fāngfǎ)与步骤例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，如何找出伪币呢？分析：方法明确而有序按提供的条件进行操作任何(rènhé)人均可仿照进行(共享智能)开始C是伪币B是伪币A是伪币A＝B？A＝C？是否否是第五页，共37页。关于算法的三方面(fāngmiàn)问题如何确定算法(suànfǎ)（算法(suànfǎ)设计）？如何表示算法(suànfǎ)（算法(suànfǎ)表示）？如何使算法(suànfǎ)更有效（算法(suànfǎ)分析）？第六页，共37页。2.算法设计(shèjì)举例第七页，共37页。例：对整数进行(jìnxíng)排序问题：任给一组(n个)整数，将它们从小到大进行排序粗略的思路(sīlù)：①从所有整数中选一个最小的，作为已排序的第一个数②从剩下未排序整数中选最小的数，添加到已排序整数的后面③反复执行步骤②，直到所有整数都处理完毕进一步细化：把待排序的整数放在一个数组A中，每个整数是数组A中的一个元素：A[1],A[2],A[3],···],A[n],排好序的元素在A的前面部分，无序的元素留在后面，每“循环”一次，有序部分增加1个元素，无序部分减少1个元素每次“循环”只需在数组的无序元素部分选出最小的数反复进行n-1次即可得到排序后的结果第八页，共37页。“直接选择(xuǎnzé)排序”算法举例2345789第6次循环后，排序结束2937845与首元素交换，第1次循环结束4937825数组的初态，全部是未排序元素4937825在未排序元素中确定最小数位置2397845与首元素交换，第2次循环结束2937845在未排序元素中确定最小数位置2347895与首元素交换，第3次循环结束2397845在未排序元素中确定最小数位置第九页，共37页。“直接(zhíjiē)选择排序”算法的描述将原始数据放在数组A中；设置(shèzhì)i的初值为1，循环执行下列操作，直到i=n：{确定A[i]到A[n]中最小整数的位置，设为j；交换A[i]和[j]；i=i+1}原始数据放在数组A中；令i=1确定A[i]到A[n]中最小整数的位置,设为jA[i]和A[j]交换位置i=i+1i=n?结束开始用伪代码(dàimǎ)表示算法用流程图表示算法第十页，共37页。直接选择排序(páixù)的c语言程序voidsort(intA[],intn)/*sort函数有2个参数:整型数组A和数组元素个数n*/{inti,j,t,k;/*定义4个整型变量*/for(i=0;i<n-1;i++){/*重复执行n-1次，每次增加1个已排序的数*/j=i;for(k=i+1;k<n;k++)if(A[k]<A[j])j=k;/*在未排序整数(zhěngshù)中确定最小数的位置*/t=A[i];A[i]=A[j];A[j]=t;/*把未排序数中的最小数交换到未排序数的首位*/}}第十一页，共37页。3.算法(suànfǎ)的表示第十二页，共37页。算法的表示(biǎoshì)方法文字说明流程图表示用N-S盒图表示算法用PAD图描述算法伪代码（一种介于(jièyú)自然语言和程序设计语言之间的文字和符号表达工具）第十三页，共37页。自然语言描述(miáoshù)“比较Ａ与Ｂ的重量，若Ａ＝Ｂ，则Ｃ是伪造的；否则(fǒuzé)再比较Ａ与Ｃ的重量，若Ａ＝Ｃ，则Ｂ是伪造的；否则(fǒuzé)Ａ是伪造的。”缺点：容易产生歧义，很难“精确”地进行表达叙述冗长，很难清楚地表达算法的逻辑流程第十四页，共37页。算法(suànfǎ)的流程图表示流程图由结点和有向边构成，它描述了算法所执行操作的顺序及执行操作的条件(tiáojiàn)流程图符号：比文字描述简明，但当算法比较复杂时，理解困难，容易产生(chǎnshēng)错误端点符处理判断预定义功能原始数据放在数组A中；令i=1确定A[i]到A[n]中最小整数的位置,设为jA[i]和A[j]交换位置i=i+1i=n?结束开始第十五页，共37页。求最大公约数的伪代码(dàimǎ)表示算法3：辗转(zhǎnzhuǎn)相除法求最大公约数BEGINinputm,n;/*输入正整数m和n*/do{r←mmodn;m←n;n←r;}whiler≠0;printm；/*输出最大公约数*/ENDYNr不等于0?输出m的值输入正整数m和n开始结束r←m被n除的余数m←n;n←r第十六页，共37页。4.算法(suànfǎ)的分析第十七页，共37页。算法分析(fēnxī)的基本内容正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果简单性算法是否容易理解，是否容易验证其正确性，程序是否容易调试简单的算法效率不一定高，要在保证一定效率的前提(qiántí)下力求算法简单时间复杂性(TimeComplexity)：当问题的规模n充分大时，运行该算法所需要的时间的数量级表示空间复杂性(SpaceComplexity)：除原始数据之外，额外占用的存储空间的大小第十八页，共37页。选择排序(páixù)算法的时间复杂性假设参加排序的整数有n个（1）比较操作的次数： 在第i趟排序中选出最小整数时，需做n-i次比较操作， 因此，总的比较操作次数为：n(n-1)/2=(n2-n)/2（2）移动操作的次数： 最好情况(原始数据已经排序)时，移动次数为0

最坏情况(原始数据逆序排列)时，每趟均要执行交换操作(3次传送)，总的移动次数取最大值为：3(n-1)所以(suǒyǐ)，直接选择排序的时间复杂性为O(n2)设置i的初值为1，循环执行(zhíxíng)下列操作，直到I=n：{确定A[i]到A[n]中最小的整数元素的位置，设为j；交换A[i]和[j]；i=i+1}第十九页，共37页。4.小结(xiǎojié)第二十页，共37页。计算机中处处(chùchù)是算法！例1：Word程序如何(rúhé)在文档中查找用户指定的词语？例2：在Word文档的表格中如何(rúhé)将表格内容排序？例3：如何(rúhé)把一幅彩色图片转换为灰度(黑白)图片？例4：Windows如何(rúhé)在硬盘中找到用户指定的文件？例5：媒体播放器如何(rúhé)把MP3文件转换成动听的音乐？例6：搜索引擎如何(rúhé)在WWW网中找到用户需要的网页？第二十一页，共37页。算法(suànfǎ)是计算机软件的灵魂计算机的通用性是因为它能运行(yùnxíng)各种各样的程序，而程序之所以能解决问题，是因为它所体现了正确的算法 算法所解决的是一类问题而不是一个特定的问题，例如排序(sort)可以是表格内容的排序，也可以是文件夹中文件的排序，可以按数字或文字排序，也可以按日期排序，等等查找(search)，可以在文档中查找某个单词或在硬盘中查找某个文件，也可在Web上查找某个网页，等等开发计算机应用的核心是：根据实际问题给出解题的算法，然后再将该算法在计算机上实现(即开发成为软件)第二十二页，共37页。计算机算法(suànfǎ)的4个特点目的：完成某个特定的信息处理任务必须满足的性质：①确定性：算法中每一步操作的含义必须清楚明确，无二义性②能行性：算法中有待实现的操作都是计算机可执行的，即必须在计算机的能力范围之内，且在有限时间内能够(nénggòu)完成③有穷性：算法在执行了有限步操作后必须结束④算法结束后至少产生一个输出（包括参量或状态的变化）第二十三页，共37页。算法(程序(chéngxù))的组成算法(程序(chéngxù))由2个部分组成：进行的操作所涉及的操作对象(数据)算法操作对象操作步骤与条件程序说明所要处理的数据的名字和类型描述所要执行的算法说明语句命令语句第二十四页，共37页。什么(shénme)是数据结构？数据结构研究如何在计算机中表示被处理的对象及对象之间的关系，即如何组织数据。例如：选择排序中，未排序整数和已排序整数如何表示？排序算法中，排序的对象若不是(bùshi)整数而是姓名如何表示？是文件夹中的文件名又如何表示？是表格中的“行”又如何表示？Word文档中插入的表格和图片如何表示？Windows操作系统中菜单如何表示？对话框如何表示？窗口如何表示？计算机下棋时，棋盘和棋局如何表示？精心设计的数据结构可使算法获得更高的时间效率或空间效率第二十五页，共37页。数据结构(shùjùjiéɡòu)的内容1数据(shùjù)的抽象(逻辑)结构，即数据(shùjù)结构中包括哪些元素，相互之间有什么关系等。例如：2数据的物理(存储)结构，即数据的抽象结构如何在实际的存储器中予以实现(shíxiàn)，数据元素如何表示，相互关系如何表示等3定义在数据结构上的一组运算(操作)及其实现方法线性结构网状结构树形结构集合结构第二十六页，共37页。2.线性数据结构(shùjùjiéɡòu)第二十七页，共37页。举例(jǔlì)：线性表(Liner-List)定义(dìngyì)：若干个相同类型的数据元素组成的一个有限序列，其中每个数据元素可由多个数据项组成。表中有且仅有一个开始元素和一个结束元素，且所有元素都最多只有一个直接前趋和一个直接后继例：考生成绩登记表(table)数据元素已经排了序的线性表称为(chēnɡwéi)有序线性表，简称有序表34681张雷64834682王宁68234683周光明58834684李霞霞61534685钱欣608………………34700赵刚658准考证号姓名总分表中的每一行是1个数据元素每个数据元素包含3个数据项：准考证号、姓名、总分开始元素结束元素前趋元素后继元素第二十八页，共37页。线性表的运算(yùnsuàn)(操作)增加1个新的数据元素删除1个指定数据元素查找(cházhǎo)指定的数据元素最高分考生最低分考生将表中的数据元素排序对表中的数据进行计算计算平均分···34681张雷64834682王宁68234683周光明58834684李霞霞61534685钱欣608………………34700赵刚658准考证号姓名总分第二十九页，共37页。数据结构的实现——存储(cúnchǔ)结构顺序存储结构：借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系链接表存储结构：利用地址(dìzhǐ)指针来表示元素之间的逻辑关系a1a2低地址高地址a2是a1的后继元素a1a2a2是a1的后继元素第三十页，共37页。假设下面的有序表中姓名已按拼音排序例：线性表的实现(shíxiàn)方法之1使用(shǐyòng)数组实现，在内存中顺序存放元素：如果要在表中加一个(yīɡè)姓名:马明，结果为：程红李军刘林刘建平王晓林张小明010016022028034040046

程红李军刘林刘建平王晓林张小明010016022028034040046马明分析：寻找指定的数据元素很容易插入元素或删除元素很不方便程红李军刘林刘建平王晓林张小明内存地址第三十一页，共37页。线性表的实现(shíxiàn)方法之2使用