计算机科学导论 课件 第1-3章 计算与计算机、逻辑思维、数据思维

第1章计算与计算机本章目录

计算机的概念01计算与计算工具02计算思维（自学）0301计算机的概念计算机是20世纪最先进的科学技术发明之一，其应用领域从最初的军事科研应用扩展到社会的各个领域，业已成为信息社会中必不可少的工具。一、计算机的应用01计算机的概念Computersareeverywhere！第一节计算机的概念

计算机是一种能够按照事先存储的程序，自动地、高速地、精确地进行大量数值计算，具有记忆（存储）能力、逻辑判断能力以及数字化信息处理能力的现代化智能电子设备。二、什么是计算机01计算机的概念第一节计算机的概念输入：一个实数C例如：9输出：例如：3中央处理器CPU存储器内存硬件软件C=input()B=do_sqrt(C)print(B)软件描述了用户的需求，硬件则实现了用户的需求01计算机的概念操作系统（OS）第一节计算机的概念02计算与计算工具一、什么是计算计算3+2=5计算规则及其简化计算方法，便于人应用规则进行计算，获得计算结果。自动计算要解决的几个问题:表示-存储-执行“数据”的表示“计算规则”的表示：程序数据与计算规则的“自动存储”计算规则的“自动执行”自动计算是指计算过程不再依赖人类的大脑，而是按照某种步骤和程序机械地、自动地完成计算，并获得计算结果第一节计算机的概念02计算与计算工具二、计算工具手工计算工具机械计算机机电计算机电子计算机原始计数法算筹算盘第一节计算机的概念02计算与计算工具手工计算工具原始计数法结绳计数事大，大其绳；事小，小其绳；结之多少，随物众寡。第一节计算机的概念02计算与计算工具算筹算筹始于商周时代，并在古代军事中发挥着巨大的作用《汉书·张良传》

“运筹策帷幄中，决胜千里之外”手工计算工具我国古代数学家利用算筹创造了璀璨的数学成果祖冲之3.1415926~3.1415927之间比西方早了近一千年圆周率之父秦九韶算法天文历法第一节计算机的概念02计算与计算工具算盘中国计算机之称手工计算工具第二节数制及转换01巴贝奇现代计算机：一般程序--任意可变的计算规则Pascal机械计算机:第一台机械计算机-能够自动完成计算Babbage分析机:特定程序--可有限变化的计算规则莱布尼茨机械计算机:自动计算--固定的计算规则1642年1673年1833年计算与计算工具第二节数制及转换01超大规模集成电路(VLSI)电子管:可自动控制0和1变化的元件集成电路:可自动实现一定变换的元件晶体管：可自动控制0和1变化的元件电子管计算机ENIAC,1946年,17468只电子管人类第一只电子管(真空二极管),1895人类第一只晶体管(点接触晶体管),1947第一台晶体管计算机TRADIC，1953集成电路的发明,1959第三代计算机IBM360,1964第四代计算机—个人计算机,1981VLSI出现,1974计算与计算工具第一节计算机的概念01计算与计算工具1958年1959年1960年1964年1965年第一台电子计算机诞生：八一型数字电子计算机。该机在738厂小批量生产，改名为103型计算机(即DJS-1型)，共生产了38台。中国计算机发展第一台大型通用电子计算机(104机)的研制完成夏培肃院士领导的科研小组首次自行设计并研制成功一台小型通用电子计算机，即107机第一台自行设计的大型通用数字电子管计算机119机研制成功，平均浮点运算速度达到5万次/秒成功研制了第一台大型晶体管计算机(109乙机，共用2万多支晶体管，3万多支二极管)，随后对109乙机加以改进，两年后又推出109丙机，在我国两弹试验中发挥了重要作用，被用户誉为“功勋机”。第一节计算机的概念02计算与计算工具1983年1983年1983年1992年1993年中国科学院计算所完成我国第一台大型向量机（757机）计算速度达到1000万次/s。国防科技大学研制的银河-Ⅰ亿次巨型计算机，是我国高速计算机研制的一个重要里程碑，它标志着我国十年动乱时期与国外拉大的距离又缩小到7年左右(银河-Ⅰ的参考机克雷-Ⅰ于1976年推出)。国防科技大学成功研制了银河-Ⅱ通用并行巨型机，总体上达到80年代中后期国际先进水平电子部六所研制成功与IBMPC机兼容的DJS-0520微机。国家智能计算机研究开发中心成功研制曙光一号全对称共享存储多处理机。第一节计算机的概念02计算与计算工具1995年1997-1999年2000年2011年2013年中心又推出了中国第一台具有大规模并行处理机(MPP)结构的并行机曙光1000(含36个处理机)1997年国防科技大学成功研制银河-Ⅲ百亿次并行巨型计算机系统，系统综合技术指标达到90年代中期国际先进水平。国家智能计算机研究开发中心与曙光公司于1997-1999年先后在市场上推出具有机群结构的曙光1000A、曙光2000-Ⅰ、曙光2000-Ⅱ超级服务器推出浮点运算速度为3000亿次/秒的曙光3000超级服务器推出浮点运算速度为1271万亿次/秒的曙光6000超级服务器。天河二号第四十一届世界大型超级计算机TOP500排行榜的第一名第一节计算机的概念03计算思维我们使用的工具影响着我们的思维方式和思维习惯，从而也将深刻地影响着我们的思维能力。计算思维是数字化计算时代的产物，成为这个时代每个人都具备的一种基本能力。艾兹格·迪科斯彻EdsgerWybeDijkstra著名计算机科学家1972年图灵奖获得者计算思维是运用计算机科学的基础概念求解问题、设计系统以及理解人类行为，它涵盖计算机科学领域的一系列思维活动。周以真本部分自学！第一节计算机的概念总结

计算无所不在，古有运筹帷幄，决胜于千里之外，今有春风化雨，潜入千家万户，计算文明的发展，计算工具的迭代，计算环境的演变，计算机的发展业已成为社会发展的标志。人类运用计算工具不断影响、改变着人类社会形态、思维方式。计算思维的本质是抽象和自动化，这不仅是数字化时代实施自动计算的产物，也是这个时代的人们必备信息素养和能力。谢谢！第2章逻辑思维数据表示03数制及转换01数据存储与运算02本章目录图灵机模型0401数制及转换

数制是用一组固定的数码和一套统一的规则来表示数值的方法。

日常生活中通常用十进制来计数。计算机内部，一切信息的存取、处理和传输均采用二进制计数。

一、为什么选择二进制01数制及转换实现简单、工作可靠

具有两种稳定状态的器件容易找运算规则简单。3个运算规则逻辑操作简单

对象是真和假，两种状态与之对应计算机中用二进制优势在计算机的世界里，没有文字、没有电影、没有音乐，只有无数个0和1！01数制及转换

10100101第二节数制及转换二进制八进制十进制十六进制数码0,10~70~90~9，A~F基数281016位权2n8n10n16n进位原则逢2进1逢8进1逢10进1逢16进1借位原则借1当2借1当8借1当10借1当16表示方法(101)2

101B(17)8

17O(45)1045D(1A)16

1AH二、数制转换D(Decimal)B(Binary)O(Octonary)H(Hexadecimal)01数制及转换第二节数制及转换按权展开式：每位上的数码乘以对应位权之和305.56的按权展开式：

305.56=3×102+0×101+5×100+5×10-1+6×10-201数制及转换N=an-1×rn-1＋an-2×rn-2＋…＋a0×r0＋a-1×r-1＋…＋a-m×r-mR进制数N展开式可表示为：第二节数制及转换

101.01B

=1×22+0×21+1×20+0×2-1+1×2-2=5.25D（1）二进制/八进制/十六进制转十进制101.01B按权展开式01数制及转换【例】将101.01B转换为十进制数第二节数制及转换整数部分:除基取余逆排列

小数部分:乘基取整顺排列01数制及转换(2)十进制转二进制/八进制/十六进制【例】将26.25D转换为二进制数第二节数制及转换(3)二进制与八进制、十六进制转换01数制及转换三位一并法（八进制），四位一并法（十六进制）二进制转换为八/十六进制：从小数点开始分别向左（整数）和向右（小数）划分数位，每隔3位/4位一组，最后一组若不足3位/4位则补0,再将每组二进制数转换为八/十六进制数。八/十六进制转换为二进制：将每1位八/十六进制数转换为3位/4位二进制数按次序写出。00110101.10111100010110101.101100（265.54）8（35.BC）16第二节数制及转换十进制、十六进制、八进制与二进制之间的对应关系01数制及转换第二节数制及转换各种进制之间的转换方法总结01数制及转换02数据存储与运算位（bit）比特：1或者0，是二进制信息组成、处理、存储、传输的最小数据单位。字节（Byte）：1Byte=8bits，信息存储的基本单位。字（Word）：计算机在同一时间内处理的一组二进制数，字由若干字节构成，字的位数称为字长。如8bits、16bits、32bits、64bits等。字长是计算机进行数据处理和运算的单位。（1）数据存储单位一、数据存储02数据存储与运算计算机存储容量的常用表示单位第三节计算机中的数据表示（2）大端和小端存储内存：以字节Byte为单位，每个字节有唯一的地址，就可方便地存取数据。数据存放：不同的数据类型占据的字节数不同。02数据存储与运算intn=100；//占4个字节doublex=3.56；//占8个字节第三节计算机中的数据表示02数据存储与运算大端存储小端存储inta=0x11223344较高的有效字节存放在较低的存储器地址，较低的有效字节存放在较高的存储器地址，称为大端存储较高的有效字节存放在较高的存储器地址，较低的有效字节存放在较低的存储器地址，称为大端存储第三节计算机中的数据表示02数据存储与运算二、算术运算第三节计算机中的数据表示02数据存储与运算三、逻辑运算（1）与运算第三节计算机中的数据表示02数据存储与运算（2）或运算第三节计算机中的数据表示02数据存储与运算（3）非运算第三节计算机中的数据表示02数据存储与运算（4）异或运算02性质x∨0

=x,x∨1=1,x∧0

=0,x∧1=xx∨¬x=1,x∧¬x=0

x∧y=y∧x,x∨y=y∨x

(x∧y)∧z=x∧(y

∧z)(x∨y)∨z=x∨(y

∨z)(x∧y)∨z=(x∨z)∧(y∨z)(x∨y)∧z=(x∧z)∨(y∧z)¬(x∨y)=¬x∧¬y¬(x∧y)=¬x∨¬yx→y=¬x∨yx⊕y=(¬x∧y)∨(x∧¬y)(结合律)(分配律)(DeMorgan律)(0-1律)(交换律)(互补律)数据存储与运算02从实际问题到逻辑函数

举重比赛时有A、B、C三个裁判，在两名以上或两名以上裁判判决成功时，才能最终判决运动员举重成功。请分析判决结果Y与三名裁判A、B、C的判断的逻辑关系。解：（1）根据裁判判决与最终结果的关系写出真值表裁判判决成功为1，不成功为0最终结果成立为1，不成立为0列出真值表数据存储与运算02

由真值表写出逻辑函数表达式，先选定输出结果为1的项，顺序写出输入变量，如果对应为1则为原变量，对应为0则为反变量。再将这些项相或。

（2）根据上面的真值表写出函数表达式数据存储与运算03数据表示第三节计算机中的数据表示03数据表示第三节计算机中的数据表示一、数值数据的表示符号位S11101100最高位符号位，“0”表示正，“1”表示负数，其余位为数值位。-108解决符号问题：问题：数值在计算机中二进制形式存放，则正负符号、小数点如何表示？03数据表示机器数是指数在计算机中的表示形式。在计算机中只有机器数，不存在数的真值。

两个数N1和N2的真值分别为：N1＝＋1101010N2＝－1011100所对应的机器数分别为：N1：01101010N2：11011100第三节计算机中的数据表示03数据表示有符号数无符号数无符号机器数的表示范围：0

X<28，即0~255（00000000）2

（11111111）2

数的符号用0和1表达，0表“+”号，1表“-”号（00000000）2

（01111111）2

（10000000）2

（11111111）2

8位机器字长无符号机器数的表示范围：-27<X<27，即-127~127第三节计算机中的数据表示求：-5+4？问题：若符号位参加运算，结果错；若考虑符号位，则运算变得复杂；怎么解决？引入数的编码二进制数值数据在计算机中有原码、反码和补码3种表示方法。03数据表示第三节计算机中的数据表示

123（10）的原码表示是：

01111011-123（10）的原码表示是：

111110110有两种原码表示：0000000010000000原码表示03字长为8bit一个正数的反码与其原码相同；一个负数的反码：对其原码的数值位按位变反（1→0、0→1）。 (123)（反）=(123)（原）=01111011 (-123)（反）=10000100

(11111011→10000100)反码表示0有两种反码表示：00000000111111111数据表示第三节计算机中的数据表示9999999里程表补码表示当字长为8bit，则(123)

10=(01111011)

2要得到(-123)

10,求一个二进制数c：

c+01111011=0000000这样的c就是|(-123)

10|的二进制表示：

10000101

10000101+）01111011

00000000进位被丢弃03再行进1公里0

0

0

0

0

0

0当限制了数据的表示长度时，要得到与正数对应的负数表示，可以认为：要得到的负数加上对应的正数之后等于0，称之为求补。数据表示第三节计算机中的数据表示负数补码对其原码数值位按位变反后加1原码表示是：10011010按位变反后：11100101加1后得到补码：11100110一个正数的补码表示与它的原码表示相同0只有一种补码表示：00000000补码表示

在计算机系统中，数值用补码来表示。

03求：-5+4？

11111011+）00000100

11111111补码再求补即为原码数据表示第三节计算机中的数据表示小结03数据表示正数负数范围正0负0原码0数值1绝对值-(２ｎ-１-１）~+(２ｎ-１–

１)0000000010000000反码0数值1按位取反-(２ｎ-１-１)~+(２ｎ-１-１)0000000011111111补码0数值1按位取反+1-(２ｎ-１)~+(２ｎ-１-１)0000000000000000解决小数点问题：第三节计算机中的数据表示小数点表示定点浮点03数据表示+11110101.0100011110101.01000111101010100小数点默认在此位置(无需用符号表示)，机器中全部是小数小数点默认在此位置(无需用符号表示)，机器中全部是整数(+245.25)100111101010100解决小数点问题：第三节计算机中的数据表示小数点表示定点浮点实数可以表示成：一个纯小数和一个乘幂之积形式。

(+245.25)10=0.24525×10303数据表示小数点位置变化的数称为浮点数+11110101.0100011110101.010000.111101010100×

2+800.111101010100×

201000N=S.M×2E解决小数点问题：第三节计算机中的数据表示小数点表示定点浮点实数可以表示成：一个纯小数和一个乘幂之积形式。

(+245.25)10=0.24525×103数符S阶码E尾数M

阶码的位数决定数的范围03数据表示小数点位置变化的数称为浮点数+11110101.0100011110101.010000.111101010100×

2+800.111101010100×

2010000010000111101010100N=S.M×2E尾数的位数决定数的精度第三节计算机中的数据表示03数据表示S阶码尾数8bits23bits1bitS阶码尾数11bits52bits1bit浮点数的精度是否还能提高？单精度：32bits双精度：64bits-0.11101

2-1001

能否去掉指数的符号0-127+1270+127+254带正负号的指数不带正负号的指数指数平移：-127~127→0~254，

避免指数符号与整个数符号的混淆能否可多表示1尾数第三节计算机中的数据表示02计算机中的数据表示浮点数的精度是否还能提高？-0.11101

2-1001

能否可多表示1尾数

-1.1101×2-1010

101110101加(27-10)后得到默认存在，但不存储(-127)10-01111111(-0,+0)1000000000(+127)10+01111111+127(0)1000000000(127)1001111111(254)1011111110(-10)10-00001010(117)+01110101S阶码尾数8bits23bits1bit11010000000000000000000IEEE754标准

于1985建立

之前由每个计算机制造商设计自己的规则

支持所有主流的CPU第三节计算机中的数据表示二、字符表示符号和英文字母编码标准：

ASCII码、Unicode码等03数据表示ASCII码(AmericanStandardCodeforInformationInterchange，信息交换美国标准码)ASCII码可表示10个数字，26个小写字母，26个大写字母，以及各种运算符号和标点符号。常规ASCII码（8bits）:最高位为0，其他7位表示128种符号和字母。扩展ASCII码（8bits）:8位表示256种符号和字母，其中前128种与常规ASCII码相同。0b6b5b4b3b2b1b0扩展ASCII标准两个主要障碍：（1）不足以容纳许多亚洲语言和一些东欧语言的字母表。（2）无法支持包含不同语种的语言文本的文档。Unicode为每种语言中的每个字符设定了统一并且唯一的二进制编码，以满足跨语言、跨平台进行文本转换、处理的要求。国际组织制定的Unicode标准，采用两个字节来表示一个数字、字母、符号或文字，并为中文、日文等都分配了相应的码段（码值连续的区间），以实现各种文字的国际交流。第三节计算机中的数据表示Unicode码03数据表示第三节计算机中的数据表示三、汉字表示03“大”da10110100111101110000001100000000000000110000000000000011000000000000001100000100111111111111111100000011000000000000001100000000000000110000000000000011000000000000001110000000000001100100000000001100001000000001100000110000000100000001100000100000000011101100000000000100计算机内部由外到内由内到外2个字节表示一个汉字大汉字内码汉字输入码汉字字形码0011010001110111国标码1011010011110111机内码计算机内部对汉字进行存储、处理的汉字代码。用两个字节表示，每个字节的最高位都是1国标码+8080H

=汉字内码数据表示数字码（区位码和电报码）音码（全拼和双拼）形码（五笔字型）音形码（智能ABC）所有字形编码的集合称为字库点阵:

1代表亮、0代表不亮。

矢量：每个字形通过数学曲线描述。第三节计算机中的数据表示四、音频表示用计算机对音频信息处理，就要将模拟信号（如语音、音乐等）转换成数字信号。模拟信号采样量化编码数字信号时间离散幅值连续3.0129623….136731507703数据表示每秒钟存储声音容量的公式为：

采样频率×采样精度×声道数/8=字节数第三节计算机中的数据表示分辨率（行、列）和颜色深度采样：用多少个像素点的“列数×行数”表示，分辨率越高，图像越清晰，存储量也越大。

图像采样量化数字图像03数据表示五、图形图像表示指单位长度内包含像素点的数量；分辨率单位：dpi（点/英寸）等。第三节计算机中的数据表示①黑白图

图像的颜色深度为1，则用一个二进制位1和0表示纯白、纯黑两种情况；②灰度图

图像的颜色深度为8，占一个字节，灰度级别为256级。通过调整黑白两色的程度（称颜色灰度）来有效地显示单色图像；③RGB24位真彩色由红、绿、蓝三基色通过不同的强度混合而成，当强度分成256级（值为0～255），每个像素点占3个字节24位，就构成了224=16777216种颜色的“真彩色”图像。03数据表示量化：量化是在图像离散化后，将表示图像色彩浓淡的连续变化值化为整数值的过程。把量化时所确定的整数值取值个数称为量化级数,也称为颜色深度.第三节计算机中的数据表示第三节计算机中的数据表示03数据表示一个像素的位数越多，颜色深度越深，表达的颜色数目就越多，所占用的存储空间越大。相反，如果颜色深度太小，图像让人觉得粗糙和很不自然。图像的分辨率和像素位的颜色深度决定了图像文件的大小，计算公式为：

列数×行数×颜色深度÷8=图像字节数视频是将一幅幅独立图像组成的序列按照一定的速率连续播放，利用视觉暂留现象在人的眼前呈现出连续运动的画面。模拟视频常用两种标准：NTSC制式(30帧/秒，525行/帧)PAL制式（25帧/秒，625行/帧），我国采用PAL制式。640×480×3×30×60=1658880000字节分辨率帧/秒采样深度时间第三节计算机中的数据表示六、视频表示容量=列数×行数×像素的颜色深度/8×帧/秒=字节数真彩色03数据表示04图灵机模型04图灵机模型苹果之父：史蒂夫·乔布斯TuringAward一、图灵及贡献图灵是谁？他做了什么？为什么要以他的名字命名？模仿游戏了解图灵的一生04图灵机模型1966年开始，美国计算机学会(AssociationforComputingMachinery—ACM)每年颁发“图灵奖”(TuringAward)给世界上最优秀的计算机科学家1912年6月，生于伦敦，中学期间获国王爱德华六世数学金盾奖章1935年，当选剑桥大学国王学院院士1937年，发表论文-论数字计算在决断难题中的应用，提出图灵机，1938年，美国普林斯顿大学获博士学位1938-1945年二战期间，密码破译工作1946年，获不列颠帝国勋章1950年，发表论文-机器能思考吗，提出“图灵测试”.

(开启了人工智能的研究)1951年，当选英国皇家学会会员(家族中第四位皇家学会会员)1954年，逝世04图灵机模型图灵的贡献

图灵机模型：解决了可计算问题

计算机的理论问题图灵测试：回答什么机器具有智能人工智能的理论基础计算机科学之父人工智能之父1937年，图灵发表著名论文《论可计算在判定问题中的应用》提出理想的计算机的数学模型---图灵机（TuringMachine）1950年，图灵发表了论文“计算机和智能”(ComputingMachineryandIntelligence)—“图灵测试”(TuringTest)。04图灵机模型计算机中的问题

可计算：不可计算：如汉诺塔问题

设函数的定义域为D,值域为R,如果存在一种算法，对D中任意给定的x，都能计算出f(x),则称函数f是可计算的。三、图灵机研究思路：为计算建立一个数学模型，称之为计算模型。计算模型能够完成的任务就是可计算任务，也就是可计算问题。04图灵机模型图灵机由图灵提出的一种抽象计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人们进行数学运算。

图灵机模型是计算机科学最核心的理论之一，它不仅指导了现代电子计算机的设计，为计算机设计指明了方向，并且是算法分析和程序语言设计的基础理论。http://.04图灵机模型1、图灵机的构成无限长的纸带（tape，存储带）纸带被划分为若干小格子，每个格子存储一个数字或符号。

读写头（head）。读写头在纸带上移动，对所指格子上的符号或数字进行读取或修改。控制程序指令状态寄存器。记录图灵机的当前状态，并且有一种特殊状态为停机状态。04图灵机模型1111111q111Rq1q1b1Rq2q211Rq2q2bbLq3q31bHq3q3bbHq3当前状态：q1图灵机开始工作：①读写头读出存储带上当前方格中的字母/数字②根据控制器当前状态和所读到的字符，找到相应程序语句③根据相应语句，做三个动作2、图灵机运行机理04图灵机模型1111111q111Rq1q1b1Rq2q211Rq2q2bbLq3q31bHq3q3bbHq3当前状态：q3图灵机做了什么事？图灵机停机意味着什么？停机表示计算完毕，表示当前存储带上保留的是计算结果。对于一个问题的输入A,问：A能否推证出B?如果能找到一个图灵机，得到对应符号序列B，则A到B是可计算的，否则问题是不可计算的。04图灵机模型图灵机为什么受到重视？

简单！

强大！

可实现！3、图灵机的意义可计算性的判定：凡是能用算法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。给出一个可实现的通用计算模型：思维模型引入通过“读写符号”和“状态改变”进行运算的思想证实基于简单的字母表完成复杂运算的能力引入存储区、程序、控制器等概念的原型：本身没有带来计算机的发明04图灵机模型汉诺塔问题---现实中难以计算的问题64个直径大小不一的盘子从下往上按照从大到小的顺序放在第一根柱子上，形成一座汉诺塔。并按照以下规定将第一根柱子上的64个盘子借助第二根柱子，全部移到第三根柱子。

①每次只能移动一个盘子；

②盘子只能在三根柱子上来回移动，不能放在他处；

③在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上。04图灵机模型搬多少次搬完？一个盘子直接将盘子从A移动到C：一次（21-1）04图灵机模型搬多少次搬完？二个盘子①将盘子1从A移动到B②将盘子2从A移动到C③将盘子1从B移动到C三次（22-1）04图灵机模型搬多少次搬完？三个盘子23-1=7次64个盘子时，最佳移动盘子次数为：264-1=18446744073709551615。假设移动一次盘子需要1秒钟，不停搬动，需要大约5849亿年时间。

理论上可以计算的问题，在实际中并不一定能行。可计算问题需要考虑计算量是否超过了目前的计算能力。谢谢第3章数据思维

数据的组织数据的管理02

数据的价值0301本章目录01数据的组织数据的组织011、数据的逻辑结构数据的组织012、数据的存储结构数据在内存中存放有两种形态：一是存放数据的内存单元地址是相邻的，二是存放数据的内存单元地址不相邻。因此，当数据元素存放在地址连续的存储单元中，其数据之间的逻辑关系和存储关系是一致的，这样的存储结构称为顺序存储结构。当数据元素存放在任意的存储单元中，这组存储单元可以是连续的或不连续的，数据元素的存储关系并不能反映其逻辑关系，通常使用地址指针来表示数据与数据之间的关系，这种存储结构称为链式存储结构。此外，数据的存储结构还有索引存储结构和散列（Hash）存储结构，这两种存储结构并不是一种“全新”的存储结构，而是在前两种存储结构的基础上扩展定义出的存储结构。数据的组织013、数据结构定义数据是计算机处理符号的总称，数据是由数据元素构成的，数据元素之间存在关系，数据的存储需要根据内存的特点选择适当的方式进行存储，由此，数据结构DS可用一个三元组描述为：DS=（E,R,M）其中，E表示数据元素的集合，R表示数据元素之间关系的集合，M表示存储数据元素的存储单元的集合。数据的组织01线性表数据的组织01树（1）度。一个结点的子树个数称为此结点的度，树中所有结点的度的最大值称为树的度。（2）树的高度。树中的结点有层次之分，从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依次类推，树中所有结点的层次的最大值称为树的高度，亦称深度。（3）叶子结点和分支结点。根据结点的度，树中的结点可以分为两类，一类是度为0的结点称为叶子结点或终端结点；一类是度不为0的结点称为分支结点或非终端结点。（4）双亲结点、孩子结点和兄弟结点。一个结点的直接前驱称为该结点的双亲结点。一个结点的直接后继称为该结点的孩子结点。同一双亲结点的孩子结点之间互称兄弟结点。（5）祖先结点和子孙结点。从根结点到某一个结点的路径上的所有结点称为该结点的祖先结点，以某结点为根的子树中的任一结点都称为该结点的子孙结点。树是指在n（n≥0）个结点构成的有限集合T中，当n=0时，称为空树；当n>0时，称为非空树，且满足如下条件：（1）树有一个称为根（Root）的结点，即根结点，该结点没有直接前驱，但有零个或多个直接后继。（2）除根结点之外的其余n-1个结点可以划分成m（m≥0）个互不相交的有限集T1，T2，T3，...，Tm，其中子集Ti又是一棵树，称为根结点的子树。数据的组织01树在一棵树中，如果各子树之间是有先后次序的，则称为有序树，否则称为无序树。二叉树（BinaryTree）是一棵除叶子结点外，每个结点至多只有两棵子树的有序树，即结点的度都不大于2。与此同时，二叉树的这两棵子树有左右之分，其次序不能任意颠倒，位于左边的子树称为左子树，位于右边的子树称为右子树。数据的组织01图图由顶点和顶点之间的边的集合组成，设V为图G顶点的非空有限集合，图G中每一条边的两个顶点互为邻接点，E是图G边的有限集合，则图G可形式化描述为：G=<V，E>若图中的每条边没有方向，则称该图为无向图，无向图中的边均为顶点的无序对。若图中的每条边是有方向的，则称该图是有向图，有向图中的边也称为弧，是由两个顶点构成的有序对02数据的管理02数据的管理一、数据库系统DBMS管理数据库的一种系统软件DBA完成某一功能的应用程序1应用程序2应用程序nDBAP1DBAP2DBAPn相互有关联关系的表形式数据的集合数据库//DatabaseDBMS如何支持用户操纵数据库？数据库(DB):Database数据库管理系统(DBMS):DatabaseManagementSystem数据库应用(DBAP):DataBaseApplication数据库管理员(DBA):DataBaseAdministrator计算机软硬件02数据的管理二、数据模型数据模型是一组严格定义的概念集合，是对现实世界中的事物特征、联系和行为的抽象。数据模型精确地描述了系统的数据结构、数据操作和数据完整性约束条件。02数据的管理概念数据模型简称概念模型，是对现实世界的第一层抽象，用户和数据库设计人员之间进行交流的工具。概念模型是整个数据模型的基础，侧重于对客观世界复杂事物的结构及它们内在联系的描述，与具体的计算机平台和数据库管理系统无关的。目前常用概念模型是实体-联系模型（Entity-RelationshipModel，E-R模型）课程学生选修学号姓名年龄性别系别课程号学分课程名成绩mn用矩形表示实体型；用椭圆表示属性；用菱形表示联系，并标示出联系的类型02数据的管理逻辑数据模型简称逻辑模型，是客观世界的抽象描述到信息世界的转换。逻辑模型直接与DBMS有关，概念模型只有在转换成逻辑模型后才能在数据库中得以表示。目前成熟的逻辑模型有层次模型（HierarchicalModel）、网状模型（NetworkModel）、关系模型（RelationalModel）以及面向对象模型（ObjectOrientedModel）。02数据的管理物理数据模型简称物理模型，是面向计算机物理表示的模型，是信息世界模型在机器世界的实现，即将信息世界的实体及其联系抽象为便于计算机存储的二进制格式。物理模型给出了数据模型在计算机上真正的物理结构的表示。02数据的管理三、关系数据库市场上常见的关系数据库产品包括Oracle、SQLServer、MySQL