九院专升本第三讲.ppt
《九院专升本第三讲.ppt》由会员分享,可在线阅读,更多相关《九院专升本第三讲.ppt(132页珍藏版)》请在咨信网上搜索。
1、信息科学与技术学院信息科学与技术学院第三讲第三讲计算机软件基础知识计算机软件基础知识1.1 1.1 算法的基本概念及其特征算法的基本概念及其特征1 1.算法:算法:是一组有穷指令集是一组有穷指令集,是解题方案的准确而完整的描述。,是解题方案的准确而完整的描述。通俗地说,算法就是计算机解题的过程。通俗地说,算法就是计算机解题的过程。2.2.*算法的基本特征:算法的基本特征:(1)(1)可行性:算法中的操作能够用可行性:算法中的操作能够用已经已经实现的基本运算执行实现的基本运算执行有限次来实现。有限次来实现。(2)(2)确定性:算法中的每一步都有确切的含义。确定性:算法中的每一步都有确切的含义。(
2、3)(3)有穷性:一个算法在执行有穷步骤后能够结束。有穷性:一个算法在执行有穷步骤后能够结束。(4)(4)拥有足够多情报:拥有足够多情报:算法执行过程中要尽可能考虑各种情算法执行过程中要尽可能考虑各种情况;况;一个算法一个算法至少有一至少有一个输出。个输出。第一部分第一部分 数据结构与算法数据结构与算法23.3.算法的基本要素:算法的基本要素:(1)(1)对数据对象的运算和操作对数据对象的运算和操作 (2)(2)算法的控制结构算法的控制结构 4.4.*算法设计基本方法:算法设计基本方法:(1)(1)列举法列举法 (2)(2)归纳法归纳法 (3)(3)递推递推 (4)(4)递归递归 (5)(5)
3、减半递推减半递推 (6)(6)回溯法回溯法第一部分第一部分 数据结构与算法数据结构与算法35.5.*算法复杂度:算法复杂度:(1)(1)算法的时间复杂度:是指算法所需要的计算工作量。算法的时间复杂度:是指算法所需要的计算工作量。用用基本运算次数基本运算次数来衡量,与程序中的执行的指令条数来衡量,与程序中的执行的指令条数密切相关密切相关。(2)(2)算法的空间复杂度:是指执行这个算法所算法的空间复杂度:是指执行这个算法所需要的内存需要的内存空间空间。第一部分第一部分 数据结构与算法数据结构与算法4例题例题:(1)(1)算法的时间复杂度是指算法的时间复杂度是指()A)A)执行算法程序所需要的时间执
4、行算法程序所需要的时间B)B)算法程序的长度算法程序的长度 C)C)算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数D)D)算法程序中的指令条数算法程序中的指令条数(2)(2)算法的空间复杂度是指算法的空间复杂度是指()A)A)算法程序的长度算法程序的长度B)B)算法程序中的指令条数算法程序中的指令条数C)C)算法程序所占的存储空间算法程序所占的存储空间D)D)算法执行过程中所需要的存储空间算法执行过程中所需要的存储空间第一部分第一部分 数据结构与算法数据结构与算法5(3)(3)下列叙述中正确的是下列叙述中正确的是()()。A)A)算法的效率只与问题的规模有关,而与数据的存
5、储结构无关算法的效率只与问题的规模有关,而与数据的存储结构无关B)B)算法的时间复杂度是指执行算法所需要的计算工作量算法的时间复杂度是指执行算法所需要的计算工作量C)C)数据的逻辑结构与存储结构是一一对应的数据的逻辑结构与存储结构是一一对应的D)D)算法的时间复杂度与空间复杂度一定相关算法的时间复杂度与空间复杂度一定相关(4)(4)下列叙述中正确的是下列叙述中正确的是()()。A)A)一个算法的空间复杂度大,则其时间复杂度也必定大一个算法的空间复杂度大,则其时间复杂度也必定大B)B)一个算法的空间复杂度大,则其时间复杂度必定小一个算法的空间复杂度大,则其时间复杂度必定小C)C)一个算法的时间复
6、杂度大,则其空间复杂度必定小一个算法的时间复杂度大,则其空间复杂度必定小D)D)上述三种说法都不对上述三种说法都不对第一部分第一部分 数据结构与算法数据结构与算法6(5)(5)问题处理方案的正确而完整的描述称为问题处理方案的正确而完整的描述称为【】。(6)(6)算法复杂度主要包括时间复杂度和算法复杂度主要包括时间复杂度和【】复杂度。复杂度。(7)(7)以下不属于算法特性的是以下不属于算法特性的是()A)A)有穷性有穷性B)B)简捷性简捷性C)C)可行性可行性D)D)确定性确定性算法算法空间空间第一部分第一部分 数据结构与算法数据结构与算法71.2 1.2 数据数据结结构的基本概念构的基本概念1
7、、数据数据结结构是构是计计算机科学与技算机科学与技术领术领域广泛使用的一个域广泛使用的一个基本基本术语术语,用来反映数据的内部构成。,用来反映数据的内部构成。数据数据结结构研究的三个方面:构研究的三个方面:(1)数据集合中各数据元素之数据集合中各数据元素之间间所固有的所固有的逻辑逻辑关系关系,即数即数据的据的逻辑结逻辑结构构(2)在在对对数据数据进进行行处处理理时时,各元素在各元素在计计算机中的存算机中的存储储关系关系,即数据的即数据的存存储结储结构构(物理物理结结构构)(3)对对各种数据各种数据结结构构进进行的运算行的运算第一部分第一部分 数据结构与算法数据结构与算法8数据结构类型 1数据的
8、逻辑结构数据的逻辑结构 2、数据的存储结构、数据的存储结构 3、数据的运算:检索、排序、插入、删除、修改等。、数据的运算:检索、排序、插入、删除、修改等。A线性结构线性结构 B非线性结构非线性结构A 顺序存储顺序存储 B 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数数据据结结构构的的三三个个方方面面 9数据的逻辑结构数据的逻辑结构线性结构线性结构(顺序表、链表、队列、堆栈顺序表、链表、队列、堆栈)非线性结构非线性结构(树、图树、图)数据的逻辑结构是数据的逻辑结构是反映数据元素之间逻辑关系的数反映数据元素之间逻辑关系的数据结构据结构(与所使用的计算机无关与所使用的计算
9、机无关)。数据的逻辑结构。数据的逻辑结构包含:包含:(1 1)表示数据元素的信息;表示数据元素的信息;(2 2)表示各数据元素之间的前后件关系。表示各数据元素之间的前后件关系。第一部分第一部分 数据结构与算法数据结构与算法10线线性性结结构:必构:必须满须满足以下两个条件足以下两个条件(1)有且只有一个根有且只有一个根结结点点,(2)每个每个结结点最多有一个前件点最多有一个前件,也最多有一个后件。也最多有一个后件。线线性性结结构也称构也称线线性表。性表。图图1-11-1线性结构线性结构第一部分第一部分 数据结构与算法数据结构与算法11线性结构和非线性结构 线性结构条件线性结构条件(1)有且只有
10、一个根结点;(2)每一个结点最多有一个前件,也最多有一个后件。(3)首节点无前件,尾节点无后件。非线性结构:非线性结构:不满足线性结构条件的数据结构注意:在一个线性结构中插入或删除任何一个节点后还应是线性结构;否则,不能称为线性结构。学学学学 生生生生 成成成成 绩绩绩绩 表表表表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号12图图1-1线线性性结结构构如果一个如果一个结结构不是构不是线线性性结结构构,则则称称为为非非线线性性结结构。构。如如图图1-2、图图1-3图图1-21-2非线性结构中的非线性结构中的“树树”形结构形结构图图1-31-3非线性结构中
11、的非线性结构中的“图图”形结构形结构第一部分第一部分 数据结构与算法数据结构与算法13树形结构全校学生档案管理的树形结构的组织方式全校学生档案管理的树形结构的组织方式全校学生档案管理的树形结构的组织方式全校学生档案管理的树形结构的组织方式非线性非线性结构结构 树树形形结结构构14树形结构ABCDEFGH树形结构树形结构树形结构树形结构 结点间具有分层次的连接关系结点间具有分层次的连接关系结点间具有分层次的连接关系结点间具有分层次的连接关系HBCDEFGA15图形结构 图图形形结结构构:节节点点间间的的连连接任意接任意1423 D=1,2,3,4 R=(1,2),(1,3),(1,4),(2,3
12、)(3,4),(2,4)无向图无向图213 D=1,2,3 R=(1,2),(2,3),(3,2),(1,3)有向图有向图16存储结构存储结构:也称数据的物理结构也称数据的物理结构,是指数据的逻辑结构是指数据的逻辑结构在计算机存储空间中的存放形式。在计算机存储空间中的存放形式。其形式包括顺序、其形式包括顺序、链接、索引等。链接、索引等。顺序存储:顺序存储:顺序存储:顺序存储:逻辑上相邻的结点存储在物理位置相邻的存储单逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系元里,结点间的逻辑关系由存储单元的邻接关系(位置位置)来体来体现现 链式存储:链式存储:链式存储
13、:链式存储:不要求逻辑上相邻的结点在物理位置上亦相邻,不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的结点间的逻辑关系是由附加的指针字段表示的第一部分第一部分 数据结构与算法数据结构与算法17顺序存储与链式存储Lo+(n-1)*m元素n.元素i.元素2元素1LoLo+mLo+(i-1)*m存储地址存储地址存储内容存储内容Loc(a)=Lo+(i-1)*m每个元每个元素所占素所占用的存用的存储单元储单元个数个数 顺序存储顺序存储常用于线性数据结构,将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。三个弱点三个弱点插入或删除操作时,需移动大量元数。长度变化较大时
14、,需按最大空间分配。表的容量难以扩充18顺序存储与链式存储 13461346 元素元素3 3 15361536 .15361536 元素元素2 2 14001400 .元素元素4 4 13461346 14001400 元素元素1 1 13451345 指指针 存存储内内容容存存储地址地址1536元素21400元素11346元素3 元素4head1345链式链式链式链式存储存储存储存储的地的地的地的地址映址映址映址映射表射表射表射表19例题例题(1)(1)数据的存储结构是指数据的存储结构是指()A)A)存储在外存中的数据存储在外存中的数据 B)B)数据所占的存储空间数据所占的存储空间 C)C)
15、数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式 D)D)数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示(2)(2)以下数据结构中不属于线性数据结构的是以下数据结构中不属于线性数据结构的是()()A)A)队列队列 B)B)线性表线性表 C)C)二叉树二叉树 D)D)栈栈第一部分第一部分 数据结构与算法数据结构与算法20(3)(3)下列叙述中正确的是下列叙述中正确的是()A)A)一个逻辑数据结构只能有一种存储结构一个逻辑数据结构只能有一种存储结构 B)B)数据的逻辑结构属于线性结构,存储结构属于非线性结构数据的逻辑结构属于线性结构,存储结构属于非线性结构 C)C)一个逻辑结
16、构可以有多种存储结构,且各种存储结构不影响一个逻辑结构可以有多种存储结构,且各种存储结构不影响数据处理的效率数据处理的效率 D)D)一个逻辑结构可以有多种存储结构,且各种存储结构影响数一个逻辑结构可以有多种存储结构,且各种存储结构影响数据处理的效率据处理的效率第一部分第一部分 数据结构与算法数据结构与算法211.3 1.3 线性表及其顺序存储结构线性表及其顺序存储结构1 1、线性表的基本概念:线性表是一种最简单线性表的基本概念:线性表是一种最简单,最常用的一种数据最常用的一种数据结构。它由一组数据元素构成。结构。它由一组数据元素构成。2 2、线性表的顺序存储结构:线性表的顺序存储结构:(两个特
17、点两个特点)(1)(1)线性表中所有元素所占的存储空间是连续的线性表中所有元素所占的存储空间是连续的 (2)(2)线性表中各元素在存储空间中是按逻辑顺序依次存放的线性表中各元素在存储空间中是按逻辑顺序依次存放的3 3、元素元素a ai i的存储地址为:的存储地址为:ADR(aADR(ai i)=ADR(a)=ADR(a1 1)+(i-)+(i-1)k,1)k,,ADR(aADR(a1 1)为第一个元素的地址,为第一个元素的地址,k k代表每个元素占的字节数。代表每个元素占的字节数。4 4、线线性表的顺序存储基本操作:性表的顺序存储基本操作:插入,删除,查找插入,删除,查找第一部分第一部分 数据
18、结构与算法数据结构与算法221.4 1.4 线性链表线性链表 概念:用一组任意的存储单元来依次存放线性表的各结点。概念:用一组任意的存储单元来依次存放线性表的各结点。这组存储单元既可以是连续的,也可以是不连续的,甚至是这组存储单元既可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的。因此,零散分布在内存中的任意位置上的。因此,链表中结点的逻链表中结点的逻辑次序和物理次序不一定相同辑次序和物理次序不一定相同。线性链表的基本运算:插入、删除、查找线性链表的基本运算:插入、删除、查找第一部分第一部分 数据结构与算法数据结构与算法23 线性链表的结点由两部分组成:线性链表的结点由两部
19、分组成:(1)(1)用于存储数据元素值,称为用于存储数据元素值,称为数据域数据域;(2)(2)用于存放指针,称为用于存放指针,称为指针域指针域,用于指向前一个或后,用于指向前一个或后一个结点。一个结点。在链式存储结构中,存储数据结构的空间可以不连续,各数据在链式存储结构中,存储数据结构的空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。所以,据元素之间的逻辑关系是由指针域来确定的。所以,链式存储链式存储方式即可用于表示线性结构,也可用于表示非线性结构。方式即可用于表示线性结构
20、,也可用于表示非线性结构。第一部分第一部分 数据结构与算法数据结构与算法24几种常见的链表:几种常见的链表:(1)(1)单向链表,单向链表,HEADHEAD称为头指针,称为头指针,HEAD=NULL(HEAD=NULL(或或0)0)称为空表;称为空表;数据数据域域指针指针域域head第一部分第一部分 数据结构与算法数据结构与算法(2)(2)双向链表:左指针双向链表:左指针(LlinkLlink)指向前件结点,右指针指向前件结点,右指针(RlinkRlink)指向后件结点。指向后件结点。(3)(3)循环链表:循环链表:25线性表的顺序存储结构称为线性表的顺序存储结构称为顺序顺序表表线性表的链式存
21、储结构称为线性链表线性表的链式存储结构称为线性链表二者的比较:二者的比较:1)1)顺顺序表存储数据时在逻辑上相连的在物理上也一定相连。序表存储数据时在逻辑上相连的在物理上也一定相连。2)2)链表存储数据时在逻辑上相连的在物理上不一定相连。链表存储数据时在逻辑上相连的在物理上不一定相连。3)3)顺序表插入和删除比较麻烦,但是访问每一个结点比较简单顺序表插入和删除比较麻烦,但是访问每一个结点比较简单4)4)链表插入和删除比较简单,但是访问每一个结点比较麻烦链表插入和删除比较简单,但是访问每一个结点比较麻烦第一部分第一部分 数据结构与算法数据结构与算法261.5 1.5 栈和队列栈和队列 栈:也叫堆
22、栈,是指限定在一端进行插入与删除的线性表。允许栈:也叫堆栈,是指限定在一端进行插入与删除的线性表。允许插入与删除的一端称为插入与删除的一端称为栈顶栈顶;不允许插入与删除的另一端称为;不允许插入与删除的另一端称为栈栈底底。栈按照。栈按照“先进后出先进后出”(FILO)(FILO)或或“后进先出后进先出”(LIFO)(LIFO)组织数据组织数据,栈具有记忆作用。,栈具有记忆作用。栈的基本运算:栈的基本运算:(1)(1)插入元素:也称为入栈运算插入元素:也称为入栈运算 (2)(2)删除元素:也称为退栈运算删除元素:也称为退栈运算 (3)(3)读栈顶元素:将栈顶元素赋给一个指定的变量读栈顶元素:将栈顶
23、元素赋给一个指定的变量 (此时指针无变化此时指针无变化)第一部分第一部分 数据结构与算法数据结构与算法27 队列:允许在一端队列:允许在一端(队尾队尾)进入插入,而在另一端进入插入,而在另一端(队头队头)进行删进行删除的线性表。队列按照除的线性表。队列按照“先进先出先进先出”(FIFO)(FIFO)或或“后进后出后进后出”(LI(LILO)LO)组织数据。组织数据。队列基本运算:队列基本运算:(1)(1)入队运算:从队尾插入一个元素;入队运算:从队尾插入一个元素;(2)(2)退队运算:从队头删除一个元素。退队运算:从队头删除一个元素。循环队列:是将队列的存储空间的最后一个位置绕到第一个位循环队
24、列:是将队列的存储空间的最后一个位置绕到第一个位置,形成逻辑上的形状空间,供队列循环使用置,形成逻辑上的形状空间,供队列循环使用,其实质还是顺其实质还是顺序存储结构序存储结构。第一部分第一部分 数据结构与算法数据结构与算法28例题例题(1)(1)下列关于栈叙述正确的是下列关于栈叙述正确的是()A)A)在栈中只能插入数据在栈中只能插入数据 B)B)在栈中只能删除数据在栈中只能删除数据 C)C)栈是先进先出的线性表栈是先进先出的线性表 D)D)栈是先进后出的线性表栈是先进后出的线性表(2)(2)下列关于队列的叙述中正确的是下列关于队列的叙述中正确的是()A)A)在队列中只能插入数据在队列中只能插入
25、数据 B)B)在队列中只能删除数据在队列中只能删除数据 C)C)队列是先进先出的线性表队列是先进先出的线性表 D)D)队列是先进后出的线性表队列是先进后出的线性表第一部分第一部分 数据结构与算法数据结构与算法29(3)(3)栈和队列的共同特点是栈和队列的共同特点是()A)A)都是先进先出都是先进先出 B)B)都是先进后出都是先进后出 C)C)只允许在端点处插入和删除元素只允许在端点处插入和删除元素 D)D)没有共同点没有共同点(4)(4)设输入序列为设输入序列为1 1、2 2、3 3、4 4,则借助一个栈可以得到的输出序,则借助一个栈可以得到的输出序列是列是()A)1 A)1,3 3,4 4,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 九院专升 第三
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。