计算机组成原理复习要点总结.ppt
- 文档编号:18743378
- 上传时间:2023-10-26
- 格式:PPT
- 页数:45
- 大小:175.50KB
计算机组成原理复习要点总结.ppt
《计算机组成原理复习要点总结.ppt》由会员分享,可在线阅读,更多相关《计算机组成原理复习要点总结.ppt(45页珍藏版)》请在冰点文库上搜索。
1,数据结构,主讲教师:
高滢,2,课程相关信息,教材:
数据结构,刘大有等编著,高等教育出版社,2001年.参考书目:
清华大学出版社、高等教育出版社和机械出版社等出版的数据结构教材.学时:
主讲64学时实验36学时.考核方式:
考试,3,数据结构,计算机学科中一门重要的专业基础课。
是程序设计的重要基础,也是许多计算机专业课的基础,如算法分析、编译原理、操作系统、数据库系统等。
4,什么是数据结构,为什么学习数据结构?
5,数据是计算机程序要处理的“原料”;数据的表示方法和组织形式直接关系到程序对数据的处理效率;系统程序和许多应用程序的规模很大,结构相当复杂,合理组织数据,可以提高计算机工作的效率;因此,要研究数据的特性以及数据间存在的关系数据结构。
6,第一章绪论,1.1数据结构概念1.2面向对象程序设计OOP与抽象数据类型ADT1.3算法概念和算法描述语言,7,1.数据,数据是计算机程序要处理的“原料”,它可以被计算机识别、存储和加工处理。
包括:
数值、文字、表格、图像、声音、源程序等。
8,例如,个人书库管理程序所要处理的数据可能是如下的表格。
9,数据元素,数据元素是组成数据的基本单位。
在程序中通常把一个数据元素作为一个整体来考虑和处理。
例如,在上表中,把其中的每一行(代表一本书)作为一个基本单位来考虑。
10,数据项,一个数据元素含有若干个数据项。
例如,在上表数据中,每个数据元素由登录号、书号、书名、作者、出版社和价格六个数据项构成。
数据项是构成数据的最小单位。
11,2.逻辑结构,数据元素之间的逻辑关系称为数据的逻辑结构。
在个人书库管理程序中,各数据元素之间在逻辑上有一种线性关系,它指出了10个数据元素在表中的排列顺序。
根据这种线性关系,可以看出表中第一本书是什么书,第二本书是什么书。
12,逻辑结构,集合线性树图,13,逻辑结构的形式化表示,逻辑结构表示为二元组L=(N,R),其中N是结点的有限集合,R是N上的关系集合。
一般地,R=r。
例1L=(N,R),N=a,b,c,d,e,R=r,r=,14,例2L=(N,R),N=a,b,c,d,e,R=r,r=,若a,bN,且关系r,则称a是b的前趋结点,称b是a的后继结点,称a和b是相邻结点。
如果不存在aN,使r,则称b为始结点;如果不存在bN,使r,则称a为终结点;既非始结点又非终结点的结点被称为内结点。
15,例3L=(N,R),N=k1,k2,k9R=r,r=,,16,逻辑结构的分类线性结构结构中有且仅有一个始结点和一个终结点,始结点只有一个后继结点,终结点只有一个前趋结点,每个内结点有且仅有一个前趋结点和一个后继结点。
非线性结构(树、图)结构中的结点可能有多个前趋结点和多个后继结点。
17,3存储结构数据及其逻辑关系在计算机中的存储表示称为数据的存储结构。
数据的存储结构是建立一种由逻辑结构到存储空间的映射个人书库数据,在计算机中可以有多种存储表示。
如,可以表示成数组,存放在内存中;也可以表示成文件,存放在磁盘上,等等。
18,存储结构分类,顺序存储结构链接存储结构索引存储结构散列存储结构,19,4.数据处理,数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。
进入八十年代以后,计算机主要用于数据处理。
据有关统计资料表明,现在计算机用于数据处理的时间比例达到80%以上,随着时间的推移和计算机应用的进一步普及,计算机用于数据处理的时间比例必将进一步增大。
20,数据结构的组成:
数据的逻辑结构数据的存储结构数据需要施加的操作,21,6.数据结构的定义,按某种逻辑关系将一批数据元素组织起来;按一定的存储方式把它们存储起来;在数据上定义需要施加的操作。
22,教学计划,第一章绪论第二章算法分析基础第三章面向对象程序设计与C+语言第四章线性表、堆栈、队列第五章数组、字符串和集合类第八章递归第六章树第七章图第九章排序第十章查找,23,第一章绪论,1.1数据结构概念1.2面向对象程序设计OOP与抽象数据类型ADT1.3算法概念和算法描述语言,24,“面向过程”程序设计:
是围绕功能进行的。
系统功能的实现是通过对若干个功能模块的调用来完成的。
适用于设计小规模的专用软件包,软件的通用性、重用性、扩展性差。
“面向对象”程序设计:
是以数据为中心。
以“类”作为构造程序的基本单位,类具有封装、数据抽象、继承和多态性等特点。
有助于提高软件的重用性、扩展性、移植性,提高编程效率和程序自动化水平。
25,抽象数据类型ADT(ADT:
AbstractDataType),由用户定义,用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的操作信息隐蔽和数据封装,使用与实现相分离,26,ADTNameisData构成该抽象类型所必需的基本数据项Operations构造函数InitialValues:
赋给基本数据项的值Process:
初始化对象操作1Input:
操作1要求用户输入的值Preconditions:
系统执行操作1前数据所需的状态Process:
对数据执行操作1Output:
操作1结束后返回的数据Postconditions:
执行操作1后数据的状态,27,操作2操作nendADTName,28,例矩形(Rectangle)的ADT描述,长,宽,29,ADTRectangleisDatafloatLengthfloatWidthOperationsConstructorInitialvalues:
构造矩形时赋给长和宽的初值Process:
给矩形的长和宽赋初值GiveLengthInput:
赋给变量Length的新值Preconditions:
无Process:
将矩形的长度值修改为新值Output:
无Postconditions:
矩形长度值被修改GiveWidthInput:
赋给变量Width的新值Preconditions:
无Process:
将矩形的宽度值修改为新值,30,Output:
无Postconditions:
矩形宽度值被修改GetAreaInput:
无Preconditions:
无Process:
计算矩形面积Output:
返回矩形面积值Postconditions:
无GetPerimeterInput:
无Preconditions:
无Process:
计算矩形周长Output:
返回矩形周长值Postconditions:
无endADTRectangle,31,第一章绪论,1.1数据结构概念1.2面向对象程序设计OOP与抽象数据类型ADT1.3算法概念和算法描述语言,32,计算机解决问题的步骤:
首先,从具体问题中抽象出一个适当的数学模型;然后,设计解此模型的算法;最后,编出程序、进行测试、调试,直至得到最终解答。
计算机算法与数据结构密切相关:
算法无不依附于具体的数据结构,数据结构直接关系到算法的选择和效率。
操作是由计算机来完成,这就要设计相应的插入、删除和修改的算法。
也就是说,数据结构还需要给出每种结构类型所包含操作的算法。
33,计算机处理问题,以适当的数据结构为基础,制定出的切实可行的方法和步骤计算机算法。
1976年,沃斯提出:
算法+数据结构=程序算法描述语言:
算法可以用自然语言、数学语言或者约定的符号语言来描述。
如类Pascal语言、C语言或伪代码等。
ADL语言直观方便。
34,2.算法描述语言ADLADL的格式算法(变量i1,变量im.变量j1,变量jn)/单行注释(或/*/多行注释)步骤名1步骤1所执行操作的高度概括语句序列.步骤名n步骤n所执行操作的高度概括语句序列.,35,表达式算术运算符+,-,*,/,DIV,MOD,取地板运算,取天棚运算关系运算符=、逻辑运算符AND,OR,NOT逻辑常量true,false集合运算符,(差),语句每条语句都用“.”作为结束符赋值语句ab.ab.abc.,36,条件语句IFTHEN(语句1.语句m).IFTHEN(语句1.语句m).ELSE(语句1.语句n).CASEDO(:
(语句1.语句n1).:
(语句1.语句nm).,37,循环语句WHILEDO(语句1.语句n).FOR=TOSTEPDO(语句1.语句n).FORDO(语句1.语句n).,38,转移语句GOTO().EXIT语句可以提前结束WHILE或者FOR循环的执行RETURN语句指出算法执行的终点其它每个算法都用“”表示算法书写完毕输入或输出语句使用READ和PRINT,39,例1.1A是一个含有n个不同元素的实数数组,给出求A之最大和最小元素的算法。
算法SM(A,n.max,min)SM1初始化maxminA1.SM2比较FORI=2TOnDO/求最大和最小元素(IFAImaxTHENmaxAI.IFAIminTHENminAI).,40,3.算法由有限条指令构成,规定了解决特定问题的一系列操作。
算法有如下5个特性:
(1)有限性:
当执行一个算法时,不论是何种情况,在经过了有限步骤后,这个算法一定要终止。
(2)确定性:
算法中的每条指令都必须是清楚的,指令无二义性。
(3)输入:
具有0个或0个以上由外界提供的量。
(4)输出:
产生1个或多个结果。
(5)可行性:
每条指令都十分基本,原则上可由人仅用笔和纸在有限的时间内也能完成。
注意:
算法和程序是有区别的,程序未必满足有限性。
41,本章小结,本章主要介绍了如下一些基本概念:
数据:
数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。
在计算机科学中,把一切能够输入到计算机中并被计算机程序处理的信息,包括文字、表格、图象等,都称为数据。
数据元素:
它是组成数据的基本单位逻辑结构:
结点和结点之间的逻辑关系,42,存储结构:
数据在计算机中的存储表示数据处理:
数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程数据结构:
数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示,并对这种结构定义相适应的操作,设计出相应的算法,而且确保经过这些操作后所得到的新结构仍然是原来的结构类型。
43,练习题1简述下列术语:
数据、结点、逻辑结构、存储结构、数据处理、数据结构。
2试根据以下信息:
校友姓名、性别、出生年月、毕业时间、所学专业、现在工作单位、职称、职务、电话等,为校友录构造一种适当的数据结构(作图示意),并定义必要的操作和用文字叙述相应的算法思想。
3什么是算法?
算法的主要特点是什么?
44,HistoryACM(AssociationforComputingMachinery)TuringAwardD.E.Knuth美国,1974年获得TuringAward贡献:
名著TheArtofComputerProgramming、排版系统TEX1967年,他在TheArtofComputerProgramming中指出,“计算机科学是有关算法的学问”,并指出“对所有的计算机程序设计来说,算法的概念总是最基本的”。
这本书是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。
C.A.R.Hoare美国,1980年获TuringAward贡献:
Quicksort,HoareLogic,ProcessesAlgebra、CommunicatingSequentialProcesses(CSP)1969年,他在论文“计算机程序设计公理化基础”和“数据结构札记”中指出,“程序的构成与数据结构是不可分割地联系在一起的”。
45,HistoryE.W.Dijkstra美国,1972年获ACMTuringAward贡献:
语言方面(ALGOL60、结构化程序设计、消除goto语句等)和操作系统方面(层次结构、死锁、并行程序设计等)1972年,他在论文“结构程序设计札记”中深入研究了算法和数据结构。
N.Wirth瑞士,1984年获TuringAward贡献:
发明了Pascal、EULER、ALGOL-W、MODULA等多个程序语言1976年,他用“算法+数据结构=程序”作为其专著的题目,旗帜鲜明地表达了“数据结构和算法是程序设计的核心问题”这一观点。
1968年“数据结构”课程在国外开始设立。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 组成 原理 复习 要点 总结