计算机软件基础教案2009(研)费下载

《计算机软件基础教案2009(研)费下载》由会员分享，可在线阅读，更多相关《计算机软件基础教案2009(研)费下载（62页珍藏版）》请在装配图网上搜索。

1、 课程名称：计算机软件基础教学目的及教学设想： 本课程是非计算机专业的一门公共计算机课程，综合性与实践性强，内容有一定的深度和难度。本课程是形成本专业专门人才知识结构与能力结构的重要环节，也是学习本专业相关课程的计算机软件基础课程。 通过教学，使学生具有计算机软件方面的必备知识。要求：掌握计算机软件技术的基础知识；掌握操作系统的基本原理；掌握数据结构的基本知识和常用算法；掌握软件工程的基本概念、理论和方法；了解数据库的基本知识，掌握数据库技术的应用；了解计算机网络的基础知识，掌握使用因特网的基本技术；了解信息和计算机系统的安全保护技术。 根据非计算机专业的特点，教学以课堂上教师的讲课为主，自学

2、、讨论、答疑和完成作业为辅进行。主要教材或参考文献： 1沈被娜，刘祖照，姚晓冬.计算机软件技术基础.清华大学出版社，2000年7月第3版. 2 郑守春，许占文，徐全生，张胜男.计算机软件技术基础.大连理工大学出版社，1998年2月第1版.考核方式及说明：笔试（开卷） 90 分；平时成绩10分。第1周第1 章 信息与计算机1.1 信息与信息时代 什么是信息 1. 信息（information）的定义 (1)信息是对现实世界中存在的客观实体、现象、关系进行描述的数据。 (2)信息是消息。 (3)信息是知识。 (4)信息是经过加工后并对实体的行为产生影响的数据。 (5)构成一定含义的一组数据。 2.

3、 数据（data）的定义 数据是现实世界客观存在的实体或事物的属性值，即指人们听到的事实和看到的现象。 数据可以是数字、文字或符号，还可以是声音、语言、图形等。 3. 信息与数据的关系 (1)信息是有一定含义的数据。 (2)信息是经过加工（处理）后的数据。 (3)信息是对决策有价值的数据。 (4)数据是信息的物理形式，是信息的载体。 4. 信息的基本特性 (1)事实性：第一和基本的性质，也是信息的中心价值。 (2)等级性：不同的使用目的要求不同等级的信息，例如有战略信息、策略信息、执行信息等等。 (3)可压缩性：可以对信息作浓缩处理，即进行集中、综合和概括而又不丢失信息的本意。 (4)可扩散性

4、：信息可以通过各种渠道和手段向四面八方扩散。 (5)可传输性：信息可以通过多种形式迅速传输，如 、电报、计算机网络系统、书报杂志、磁带光盘等。 (6)共享性：信息可以被多个用户共享而得到充分的利用。 (7)增值性与再生性：信息是有价值的，而且可以增值。 (8)转换性：信息、物质和能源是人类的三项重要的宝贵资源，三位一体而又可以互相转换。 5. 三种不同层次的信息产品 (1)数据：通过数据采集获得，用于事务处理系统。 (2)信息：通过数据处理获得，用于管理信息系统。 (3)知识：通过数据融合获得，是经过分析与综合的信息，用于决策支持系统。知识管 理决策事务处理信息数据 图1.2 信息的三中不同层

5、次示意图 信息化是社会经济发展的必然结果 1. 信息科学的巨大发展-认识基础 (1)自然科学-理论基础 自然科学领域在信息科学方面的研究，为现代信息处理技术和信息传输技术的进一步发展准备了理论基础。 (2)社会科学-经济属性 在社会科学领域，通过对信息效用性、稀缺性、成本、价值的研究，发现了信息已经具备的经济属性，从而在理论上确立了信息作为经济资源的重要地位。 信息科学的巨大发展构成现代信息化的认识基础，将信息在社会经济中的重要性提高到了理论的高度。 2. 信息技术的长足进步-技术基础 (1)信息处理技术 信息处理技术领域中新的计算机元器件技术使得计算机在微型化的同时，性能大幅度提高，成本大幅

6、度降低。计算机正在向智能化、集成化、综合化发展。 (2)信息传输技术（通信技术） 在通信技术领域，各种物理信道的通信技术和通信方式不断推出和更新。宽带、高速、大容量已经成为现代通信信道的主要特征。 信息处理技术和通信技术的发展为当代信息化提供了技术手段和工具，成为当代信息化的技术基础。 3. 社会生产力的提高-经济基础 经济的高速增长反映了社会生产力的空前提高，社会经济资源，包括资金、原料、人力、智力等资源，有可能从传统的生产领域转向信息领域。 生产力水平的提高为当代信息化提供了经济基础。 4. 信息需求已成为普遍的社会需求-社会基础 随着人们对信息重要性认识的深化以及信息利用水平的提高，在社

7、会、经济、文化、军事等各领域，以及政府、企业、公众等不同层次的行为主体，对信息和信息技术的需求都有很大的增长。 5. 信息时代的特点 (1)市场环境变化巨大 (2)机遇与挑战并存 (3)风险与效益并存 (4)多媒体、全球互联网、信息高速公路，是信息时代革命浪潮中的三大主干技术。 信息与计算机应用 1. 信息技术（Information Technology 缩写为IT）的三大组成部分 (1)计算机硬件技术 (2)计算机软件技术 (3)通信技术 它包含了信息的产生、检测、变换、存储、传递、处理、显示、识别、控制和利用扥的活动。 2. 计算机的最主要特点 (1)高速自动的操作功能 (2)具有记忆的

8、能力 (3)可以进行各种逻辑判断 (3)精确高速的计算能力 3. 计算机应用计算机科学与技术的划时代的意义是为人类提供了通用智力工具。1.2 计算机发展简史 计算机发展的几个重要阶段（略） 1. 从硬件的角度分 (1)20世纪40 - 50年代：第一代，电子管 (2)20世纪50年代末 - 60年代中：第二代，晶体管 (3)20世纪60年代中 - 70年代初：第三代，集成电路 (4)20世纪70年代中：第四代，超大规模集成电路 2. 从应用的角度分 (1)20世纪40 - 60年代：大型机时代 (2)20世纪70年代：中小型机时代 (3)20世纪80年代：个人计算机时代 (4)20世纪90年代

9、：全球网络时代 3. 数字化信息的特点 (1)容易交换，只要有传输媒体，即可以畅通无阻，无处不达； (2)可以大容量、高速度传输，以满足人们对信息的需求； (3)稳定性高，传输途中不受干扰，可以还其本来面貌。 计算机应用的领域（略） 根据学科划分： (1)科学研究与科学计算 (2)事务处理 (3)计算机辅助功能 (4)生产过程控制 (5)人工智能 (6)计算机网络通信 (7)计算机教育 (8)多媒体 计算机在现代人类活动中的地位和作用 1. 改变人类的工作和生活方式 分散 集中 分散 2. 社会转型 (1)从工业时代转向信息时代 (2)从工业社会转向知识社会 计算机的现在和未来（自学） 1.

10、计算机的现在 (1)计算机在微小型化的同时，性能有了大幅度的提高 (2)计算机系统正向智能化、集成化、综合化发展 2. 计算机和信息技术的未来发展 (1)建立未来的应用 (2)管理企业的应用 (3)新的电子商务应用 (4)解决人机文化差异的问题1.3 计算机与计算机系统 1. 系统的定义 从技术的角度，定义：为完成特定任务而由相关部件或要素组成的有机整体，成为系统。 2. 系统的特点 (1)整体性 (2)层次性 (3)适应性 计算机系统的组成（自学） 1. 硬件系统说 (1)计算机硬件系统的组成 (2)计算机裸机 2. 硬件与软件结合说 (1)计算机软件系统 (2)计算机系统的狭义说法 3.

11、计算机广义系统说 由五部分组成： (1)人员 (2)数据 (3)设备 (4)程序 (5)规程 计算机的硬件与软件（自学） 1. 微型计算机的硬件系统 (1)主机：CPU和内存 (2)外存储器 (3)输入设备 (4)输出设备 (5)微机系统总线：数据总线、地址总线和控制总线 2. 微型计算机的软件系统 (1)系统软件 (2)应用软件 3. 计算机硬件与软件的关系 (1)互相依存 (2)无严格界面 (3)相互促进 多媒体计算机（自学） 1. 什么是多媒体计算机 (1)媒体 1)存储信息的实体：磁带、磁盘、光盘、半导体存储器。 2)表现信息形式的载体：数字、文字、图形、图像、视频。 (2)多媒体计算

12、机的定义 多媒体计算机是以计算机为核心，可以综合处理数值计算、文本文件、图形、图像、声频、视频等多种信息的计算机系统。 2. 多媒体的基本要素 基本要素有：文本、图形、图像、动画、声频、视频。 3. 多媒体计算机的基本配置 (1)硬件配置：CPU、内存大小、硬盘容量、光驱、视频卡和显示器、声卡和音响设备。 (2)软件配置：最主要的是支持多媒体的操作系统（MPCOS）。1.4 计算机软件技术发展过程 高级语言阶段 20世纪60年代，FORTRAN、ALGOL60、COBOL、LISP、PL/1。 编译系统主要靠手工编制，自动化程度很低。 结构程序设计阶段 20世纪60年代末发生了软件危机。 1.

13、 程序的正确性 (1)三种基本结构：顺序、选择和循环 (a) 顺序 (b) 选择 (c) 循环 图1.7 程序的三种基本结构 (2)语义形式化 用数学符号严格地按照一定规则形式地表达某种程序语言，以达到语义的精确化合编译自动化。 2. 程序设计方法论 (1)由顶向下法 由顶向下、逐步细化，是结构程序设计的一种方法。分解一个大系统为若干个子系统。 (2)自底向上的方法 自底开发程序模块，再处理各模块之间的联系，组合成整个软件系统。 (3)模块化 模块划分的的基本原则。 3. 软件生产管理 (1)软件工程：软件生产作为一种工程需要某种合理管理的体制。 (2)软件生命周期法（见第6章） 自动程序设计

14、阶段 1. 软件工程支撑环境 把过去分散编制的软件开发工具，集成为整体性的系统，称为软件工程支撑环境，也称为CASE（computer aided software engineering）。它支持软件开发和维护的全过程。 Rational软件公司是由Paul Levy和Mike Devlin于1991年在硅谷成立的。它的一个CASE工具是Rational Rose，在面向对象技术和面向对象工具市场上占到领先位置。 2. 程序设计基本方法的进一步改进 (1)传统软件开发方法的缺点 1)要求开发者有一定的计算机专业知识和程序设计经验； 2)软件开发的各阶段缺少反馈。 (2)改进 1)快速原型法

15、2)甚高级语言（非过程化语言） 3)软件可重用法 3. 第四代语言（4GL） (1)语言分代 1)第一代语言：1946-1950，机器语言； 2)第二代语言：1950-1960，汇编语言； 3)第三代语言：1960-1980，过程化编程语言； 4)第四代语言：1980-1995，非过程化高级语言； 5)第五代语言：1995- ，应用程序开发用专家系统。 (2)第四代语言与其他软件技术的关系 1)与数据库的关系：数据库是4GL的基础 2)与第三代语言的关系：依赖3GL，转换成3GL 3)与图形软件的关系：有可视化4GL 4. 面向对象编程语言（见节）第2 章 常用数据结构与算法2.1 概述 什么

16、是数据结构 作为一门课程，数据结构是研究非数值运算的程序设计问题。 有关数据结构的基本概念和术语 1. 数据 数据（Data）是信息的载体，它可以用计算机表示并加工，如数、字符、符号等的集合。 2. 数据元素 数据元素（data element）是数据集合中的一个个体，是数据的基本单位。如集合N=1,2,3,4,5中的整数1至5均为数据元素。学生登记表中的一条记录，也是一个数据元素。 3. 数据对象 具有相同性质的数据元素的集合称为世界对象（data object）。 4. 数据结构 数据结构(data structure)是指同一数据对象中各数据元素间存在的关系。用集合论方法定义数据结构为

17、S = (D,R) 数据结构S是一个二元组，其中D是一个数据元素的非空有限集合，R是定义在D上的关系的非空有限集合。 5. 逻辑结构与物理结构 (1)数据的逻辑结构：研究数据元素及其关系的数学特性，简称数据结构。 (2)数据的物理结构：是逻辑结构在计算机中的映像，也就是具体实现，简称存储结构。 6. 数据类型 (1)概念 数据类型（data type）是指程序设计语言中允许的变量类型。 (2)数据类型的分类 1)基本数据类型：如整型、实型、布尔型等，它们变量的值是不可再分的。 2)结构数据类型：如数组、结构体等，它们变量的值是可再分的，或者说它们是带结构的数据。 7. 数据结构与算法 (1)算

18、法 算法是解决某一特定类型问题的有限运算序列。 (2)数据结构与算法的关系 算法的实现必须借助程序设计语言中提供的数据类型及其运算；数据结构是算法和程序设计的基本部分，它对程序设计的质量影响很大。 算法描述语言 1. 自然语言 2. 流程图（框图）等图形工具 3. 高级程序设计语言，如C语言 4. 类高级程序设计语言，如类C语言 算法分析技术初步 1. 时间复杂度 (1)例 设对一个nn矩阵A自乘后送入矩阵B，其算法步骤为 for i = 1 to n for j = 1 to n Bi,j0 for k = 1 to n Bi,jbi,j + ai,k * ak,j end (k) end

19、(j) end (i) 分析：语句3重复次数为n2，语句5重复次数为n3。若语句3执行1次的时间为t1，语句5执行1次的时间为t2，忽略控制语句的执行时间，次算法耗用的时间近似为 T(n) = t1n2 + t2n3 当n很大时，有 表明当n很大时，T(n)和n3的比值是常数，即T(n)和n3是同阶的，记作T(n) = O(n3) 。 (2)频度 在算法中，一条语句重复的次数，称为该语句的频度，记作F(n)。例子中n2，n3分别是语句3和5的频度。 (3)时间复杂度 时间复杂度是以算法中频度最大的语句的频度来度量的，记作T(n) = O(F(n)。例子中，时间复杂度为T(n) = O(n3)。

20、 (4)常见的时间复杂度 O(1)：常量型 O(n)，O(n2)， ，O(nk)：多项式型 O(log2n)，O(nlog2n)：对数型 O(2n)，O(en)：指数型 (5)时间复杂度比较 O(1)O(log2n) O(n)O(nlog2n)O(n2) O(2n)O(en) 2. 空间复杂度 (1)概念 空间复杂度是指在算法中所需的辅助空间单元，而不包括问题的原始数据占用的空间。 (2)表示 空间复杂度的表示与实践复杂度类似。 本例中所需的辅助空间单元为i、j、k，所以空间复杂度为 S(n) = O(1) 。作业：（P101）2.5(1)(2)(3)，注意(4)(5)有错，不要了。2.2 线

21、性表 线性表的定义和运算 1. 什么是线性表 线性表是数据元素的有限序列。例： n维向量x=(a1,a2,an)，其中每个分量为一个数据元素；学生表，一个学生的记录为一个数据元素。 2. 线性表的一般表示形式 L = (a1,a2,an)其中L为线性表，ai(i = 1,2,n)是属于某数据对象的元素， n(n0)为元素个数，又称为表长，n = 0为空表。 3. 线性表的结构特点 数据元素之间是线性关系，具体有四句话： (1)线性表中必存在唯一的一个“第一个”元素； (2)必存在唯一的一个“最后一个”元素； (3)除第一个元素以外，每个元素有且只有一个前驱元素； (4)除最后一个元素以外，每个

22、元素有且只有一个后继元素。 4. 线性表的形式定义 L = (D,R)其中 D = a1,a2,.,an R = |ai-1,aiD,2in 若线性表中的数据元素相互之间可比较，且aiai-1, i = 2,3,.,n, 则称L为有序表，否则称为无序表。 5. 线性表的基本运算 (1)插入：在两个确定元素之间插入一个新元素； (2)删除：删除线性表中某个元素； (3)查找：按某种要求查找线性表的一个元素，需要时可以进行更新； (4)排序：按给定要求对表中元素重新排序。 6. 线性表的存储结构 (1)顺序存储结构：向量； (2)链式存储结构：链表。 顺序存储线性表 1. 顺序存储结构 (1)顺序

23、存储结构的含义 是用一组地址连续的存储单元存放线性表的数据元素，称为线性表的顺序存储结构，也称为向量式存储结构，又称为随机存储结构。用高级语言中的一维数组类型表示,例如A1:n。 (2)求顺序存储线性表中第i个元素的存储地址 设：已知线性表中每个元素占l个单元，且线性表在内存中的首地址为：adr(a1) = b，则线性表中第i个元素的存储地址为 adr(ai) = adr(a1) + (i-1)l 2. 顺序存储结构的插入、删除运算 (1)插入 设长度为n的线性表(a1,a2,an)，要求在第i-1与第i个元素之间插入一个新元素x 。 1)顺序存储线性表的插入过程 将第n至第i个元素一次向后移

24、动一个位置，原第i个元素的位置被空出来了； 将x放入被空出的存储单元； 将线性表的长度增1。 2)插入算法 设存放线性表的向量为V1,m(mn)，算法如下： INSERTLIST(V,n,i,x) if (in+1) then 参数错 return for j = n to i step(-1) Vj+1Vj end (j) Vix nn+1 return 3)插入算法说明 语句1是将异常情况作出错处理。 语句2-4是将后移n-(i-1)个元素，即i-1个元素不用移动；step(-1)表示j从n开始每次减1，j为i-1时停止循环。 语句5是将元素x送入原第i个元素的位置。 语句6是将线性表的长

25、度增加1。 (2)删除 设长度为n的线性表(a1,a2,an)，要求删除第i个元素。 1)顺序存储线性表的删除过程 将第i个元素ai以后的元素ai+1,an依次向前移动一个位置。 将线性表的长度减1。 2)删除算法 设存放线性表的向量为V1,m(mn)，算法如下： DELETELIST(V,n,i) if (in) then 参数错 return for j = i to n-1 VjVj+1 end (j) nn-1 return 3)删除算法说明 语句1是将异常情况作出错处理。语句2-4是将前移n-(i-1)个元素，即i-1个元素不用移动。 语句5是将线性表的长度减少1。 3. 顺序存储结

26、构的插入、删除运算的时间分析 运算的时间主要移动元素上，且移动元素的个数与线性表的程度，以及与被插入或删除元素在线性表中的位置i有关。 用最少移动次数，最多移动次数，平均移动次数来分析。 (1)插入算法 最少移动次数0（i=n+1），最多移动次数n（i=1），平均移动次数=(0+1+ +n)/(n+1) = n/2 (2)删除算法 最少移动次数0（i=n），最多移动次数n-1（i=1），平均移动次数=(0+1+ +(n-1)/n = (n-1)/2第2周 线性链表 1. 链式存储结构 (1)顺序存储线性表的插入、删除运算的不足 1)可能要移动大量的数据元素，当n很大的时候，花费很多时间； 2)

27、需要预留存储单元，浪费资源；若预留资源不足，会溢出。 (2)链式存储结构的含义 链式存储结构不需要一组连续的存储单元，它的数据元素可以分散存放在存储空间中，为了使线性表在逻辑上保持连续，必须在每个元素中存放其后继元素的地址。这样由n个结点组成的序列便构成一个链表，称为线性表的链式存储结构。 (3)链式存储结构的概念 链式存储结构（又称指针类型结构）示意图如下：a data next 1)数据域与指针域：指针类型结构中，每一个数据元素由两部分组成：一部分是存放元素的值，称为数据域，用“data”表示；另一部分为存放后继元素的存储地址，称为指针域，用“next”表示。 2)头指针：指示链表中第一个

28、结点地址的指针，称为头指针，用“head”表示。 3)空指针：链表中最后一个结点的指针为空指针，用“nil”或“”表示。 2. 线性链表的基本运算 (1)基本操作 线性链表的四种基本操作，如29页的表2.2所示。 设p、q、s均为指针型变量，指向数据域为data，指针域为next的结点。 1)指针赋值 将某地址指针值赋给一个指针变量。有两种情况： sp /将指针变量p的内容赋给另一个指针变量s/ 例：若p=2000，经过语句sp后，s=2000 qnext(p) /将指针变量p的next域内容赋给 另一个指针变量s / 例：若p=2000，p指向的结点的指针域内容为1200，经过语句qnext

29、(p)后，q=1200 。 2)指针移动 当前指针指向链表的下一个结点的地址指针。 pnext(p) /将指针变量p的next域内容赋给指针变量p/ 例：若p=2000，p指向的结点的指针域内容为1200，经过语句pnext(p)后，p=1200 。 3)后插 在p指向的结点地址后插入一个新元素。 s是保存新元素的指针变量（新的）。 next(s)next(p) /将指针变量p的next域内容赋给指针 变量s的next域/ next(p)s/将指针变量s的地址赋给指针变量p的next域/ 例：若p=2000，p指向的结点的指针域内容为1200，s的地址为3000。经过语句next(s)next

30、(p)和后，p的next域内容为3000，s的next域内容为1200 。 注意：这两条语句的次序不能换。 4)前插 在p指向的结点地址前插入一个新元素。 先要找到p指向的结点之前的结点指针q，然后利用3)的后插算法。找到方法是从头指针（赋给q）开始，判断“next(q)=p？”。 qhead /将头指针变量head的地址赋给指针变量q / While (next(q)p） do qnext(q)/在next(q)=p时退出循环，否则指针移动/ next(q)s /将新结点的地址s赋给q的指针域/ next(s)p /将已知结点的地址p赋给s的指针域/ 注意：后两条语句的次序可以交换。思考为什

31、么？ (2)结点的动态生成与回收 设存储器中有一个空白链表，表示没有使用的存储单元，可供用户使用。空白链表的头指针为av 。 1)从空白链表中获得一个结点，地址指针是p 。算法如下： （将空白链表的第1个结点给用户使用。） GETNODE(P) pav /取走空白链表中的第1个结点，将av赋给p/ avnext(av)/将空白链表中原第2个结点置为头结点/ return 2)回收一个由p指针指向的结点。算法如下： （将回收的结点作为空白链表的第1个结点） RET(P) next(p)av/原空白链表中的头指针av赋给p的指针域/ avp /将指针p赋给头指针av/。 return (3)插入运

32、算 1)要求：在头指针为head的链表中，值为a的结点前，插入一个值为b的结点。 2)分析：主要是要寻找包含指定元素a的结点及之前的结点q 。 分析没有找到包含指定元素a的结点的异常情况及解决方法： 若链表为空表：b为链表的第1个结点。 若链表中无值为a的结点：将b添加到链表的末尾。 3)在非空链表中，寻找包含指定元素a的结点之前的结点q。算法如下：（排除了a包含在第1个结点及空表） LOOKFOR(head,a,q) qhead /将头指针变量head的地址赋给指针变量q / while (next(q)nil)and (data(next(q)a) do qnext(q) /如果q的下一个

33、结点存在，同时它的data 域的值不等于a，则移动q指向下一个结点 退出循环时有两种情况：q为最后一个结点， 或者q的下一个结点的data域的值为a/ return 4)插入算法 INLINKST(head,a,b) GETNODE(p);data(p)b; /取一个空结点p，并将值b放入p的data域/ if (head=nil) then headp;next(p)nil;return /处理空表情况，p为头指针，p的指针域为空/ if (data(head)=a)thennext(p)head;headp;return /处理第1个结点值为a的情况：p的指针域是 原来的头指针head，再

34、将p置为头指针head/ LOOKFOR(head,a,q)/调用函数，寻找元素a之前的结点q/ next(p)next(q);next(q)p /处理返回值的情况：找到q，它的下一个结点的data 域的值为a ：将q的指针域内容赋给新结点p的指针域， 再将新结点的地址指针赋给q的指针域。 q为最后一个结点，将q的指针域内容（为空）赋给新 结点p的指针域，再将新结点的地址指针赋给q的指针域/ 从上可以看出，这两种情况的程序可以合并。 return (4)删除运算 1)要求：在头指针为head的链表中，删除元素值为a的结点。 2)分析：同样也要寻找包含指定元素a的结点及之前的结点q 。算法还需要

35、处理四种情况： 若链表为空表：不删除。 若链表中只有一个值为a的结点：删除元素a的结点后，链表变为空表。 在链表中找到值为a的结点，且不是第1个结点：删除。 若链表中无值为a的结点：不删除。 4)删除算法 DELINKST(head,a) if (head=nil) then 空表 return/空表情况/ if (data(head)=a) then snext(head);RET(head); heads;return /处理头结点值为a的情况： 将第2个结点指针（在a结点的指针域中）先暂存在s 变量中，在删除第1个结点（回收），最后修改头指针/ LOOKFOR(head,a,q)/调用函

36、数，找元素a之前的结点q/ if (next(q)=nil) then 无此结点 return /处理未找到a的情况/ pnext(q);next(q)next(p) /处理找到a的情况/ RET(p) return 3. 线性链表的其他形式 (1)具有头结点的线性链表 在链表的第一个结点之前附加一个头结点，该结点的结构和链表中的其他结点相同，只是它的数据域中不存放线性表的元素，它的指针指向线性表的第一个元素。 具有头结点的线性链表为空表时，只有一个头结点，其指针域为空。 (2)循环链表 1)循环链表的定义 循环链表是另一种链式存储结构，它的特点是表中最后一个结点的指针域不为空，而是指向表头，

37、整个链表形成一个环。 2)具有头结点的循环链表 是指带有头结点的循环链表。 3)循环链表的优点 只要给出循环链表中任一结点的地址，就可以查遍表中所有结点，而不必从头指针开始。 (3)双向链表 1)双向链表的定义 在线性链表中增加一个指针域，其指针指向直接前驱，称为双向链表。 2)双向链表的优点 从表中某一给定的结点可以随意向前或向后查看。 但在做插入、删除运算时，需同时修改两个方向上的指针。 4. 线性链表的应用实例 一元多项式相加（略） 向量和链表的比较（自学） 1. 线性表的长度是否固定 向量 固定， 线性链表 不固定 2. 线性表的主要操作是什么 向量 查询， 线性链表 插入和删除 3.

38、 采用的算法语言 向量 随意， 线性链表 提供指针类型变量 补充题：对具有头结点的线性表，写出插入算法。2.3 栈与队 栈的结构和运算 1. 栈的定义 (1)栈（stack）：栈是限定只能在表的一端进行插入和删除操作的线性表。又称为后进先出的线性表。 (2)栈顶（top）：栈中允许插入或删除的一端称为栈顶。 (3)栈底(bottom)：栈中不允许插入或删除的一端称为栈底。 (4)空栈：栈中没有元素时，称为空栈。 (5)进栈（入栈，push）：向栈中插入元素，称为进栈。 (6)退栈（出栈,pop）：将栈中元素删除，称为退栈。 2. 顺序栈 (1)顺序栈的定义 1)顺序栈：用向量作为栈的存储结构。

39、高级语言中用一维数组s1:m来表示，其中m表示栈允许的最大容量。 2)栈顶指示器：设置一个简单变量（top）用来指示栈顶位置，称为栈顶指示器。 3)栈空：当栈顶指示器top=0时，表示栈空。 4)栈满：当栈顶指示器top=m时，表示栈满。 5)栈上溢：当栈顶指示器top=m时再有元素进栈，栈将溢出，称为上溢。 6)栈下溢：当栈空时要作退栈操作，栈也将溢出，称为下溢。 (2)顺序栈的插入运算（进栈） 1)要求：将元素x插入顺序栈s1:m。 2)分析：先令top加1，再将元素x送入stop中。但要先判断是否会“上溢”。 3)算法： PUSH(s,m,top,x) /将元素x送入栈中/ if (to

40、p=m) then 上溢,return toptop+1 stopx /处理正常入栈/ return (3)顺序栈的删除运算（退栈） 1)要求：将栈顶元素取出。 2)分析：先将栈顶元素放入y，再将栈顶指针top减1。但要先判断是否会“下溢”。 3)算法： POP(s,top,y) /退栈，将栈顶元素送入y中/ if (top=0) then 下溢,return ystop toptop-1 /处理正常出栈/ return 3. 链栈（自学） (1)链栈的定义：用链表作为栈的存储结构，称为链栈。若top=nil，则表示栈空。链栈不会出现“上溢”，除非内存中已不存在可用空间。 (2)链栈的插入运算

41、 (3)链栈的删除运算 4. 栈的应用（自学） 5. 栈的练习题（自学） 已知有四个元素，它们关键字分别是1，2，3，4。如果入栈的次序是4321，假设入栈时可以出栈，问：哪几种排列是可能的出栈过程？第3周 队的结构和运算 1. 队的定义 (1)队（queue）：队是限定只允许在一端进行插入，在另一端进行删除操作的线性表。又称为先进先出的线性表。 (2)队尾：队中允许插入的一端称为队尾。 (3)队尾指示器（rear）：指向队尾元素。 (4)排头：队中允许删除的一端称为排头。 (5)排头指示器（front）：指向排头元素。 2. 顺序队 (1)顺序队的定义 1)顺序队：用向量作为队的存储结构。高

42、级语言中用一维数组Q1:m来表示，其中m表示队允许的最大容量。 2)顺序队空：front=rear（初始时front = rear = 0）。 3)入队：rear增1，front不变。即初始时front=0，rear=1。 4)出队：front增1，rear不变。 5)队上溢：当队中已有m个元素时再有元素入队，队将溢出，称为队上溢。 6)队下溢：当队空时要作出队操作，队也将溢出，称为队下溢。 7)假溢出：当rear=m时，无法再继续入队，但队不满，这时称为队假溢出。因为只有当rear - front = m时，才是真满。 8)循环队列：把存放队列的数组形成一个头尾相接的环形，称为循环队列。 (

43、2)循环队列的插入运算 1)要求：将元素x插入循环队列CQ0:m-1。假设头尾指示器初始时front = rear = m - 1。 注意front指向队列第一个元素的前一个位置。 2)分析：有两种算法：先找到插入位置，然后进行判断队是否满，若不满，再插入数据x 。先判断队是否满，若不满，再找到插入位置，最后插入数据x 。 3)循环队列的插入算法1 ADDCQ(CQ,m,front,rear,x) /将x插入队列CQ中/ rear(rear+1) mod m /求模运算，找到应插入的位置/ if (front=rear) then 队满；rear(rear-1) mod m； return /

44、判断，若队满，恢复原队尾指示器，返回/ CQrearx /插入数据的操作/ return 4)循环队列的插入算法2 ADDCQ2(CQ,m,front,rear,x) /将x插入队列CQ中/ if (front = (rear+1) mod m) then 队满,return /判断，若队满，返回/ rear(rear+1) mod m /求模运算，找到应插入的位置/ CQrearx /插入数据的操作/ return (3)循环队列的删除运算 1)要求：将循环队列CQ0:m-1的队首元素取出，并删除。假设头尾指示器初始时front = rear = m - 1。 2)分析：先判断队是否空，若不

45、空，找到删除元素的位置，将队首元素放入y ，排头指示器front增1 。 3)算法： DELCQ(CQ,m,front,rear,y) /删除队首元素送入y中/ if (front = rear) then 队空,return /判断，若队空，返回/ front(front+1) mod m /求模运算,找到删除的位置/ yCQ(front) /删除操作，将队首元素赋值给y/ return 3. 链队 (1)链队的定义：用链表作为队的存储结构，称为链队。头指针front固定指向头结点，注意：头结点不放数据；尾指针指向队尾元素，front = rear表示队空。链队不会出现“上溢”，除非内存中已

46、不存在可用空间。 (2)链队的插入运算 分析：由于是队，故插入到链表的最后。 ADDLINK(front,rear,x) /在链队中插入x结点/ GETNODE(p) /获取一个空白结点p/ data(p)x;next(p)nil /给空结点赋值/ next(rear)p;rearp /将结点p插入到队尾，修改队尾指示器/ return (3)链队的删除运算 分析：由于是队，故删除链表的第一个元素。 DELLINK(front,rear,y) /删除排头元素，并赋值给y/ if (front = rear) then 队空,return /判断，若队空，返回/ ydata(next(front

47、);next(front)next(next(front) /将排头元素取出赋给y，/ /修改头结点的指针域，它指向排头结点/ if (next(front)=nil) then rearfront /若删除结束时链队已成为空队，修改队尾指示器/ return 4. 队的应用（略）2.4 数组 数组的定义 1. 二维数组（数学中的矩阵）例： 2. 用线性表定义二维数组 令 B = (K, R)其中 K = Kij | 1im , 1jn R 由两个关系组成 行ROW = Kij ，Kij+1| 1im , 1jn-1 列COL = Kij ，Ki+1j| 1im-1 , 1jn 数组的顺序存储

48、结构 用一维连续单元存放多维的数组。 1. 按行优先顺序存放 (1)二维数组 先第1行n个元素，再第2行n个元素，。 设每个元素仅占一个单元地址，则aij的地址为： Loc(aij) = Loc(a11) + (i-1)n + (j-1) (1im , 1jn) (2)三维数组 以左下标为主序的存储方式。 设每个元素仅占一个单元地址，则aijk的地址为： Loc(aijk) = Loc(a111) + (i-1)mn + (j-1)n + (k-1) (1il , 1jm, 1kn) （c，BASIC语言按行优先） 2. 按列优先顺序存放 (1)二维数组 先第1列m个元素，再第2列m个元素，。

49、 设每个元素仅占一个单元地址，则aij的地址为： Loc(aij) = Loc(a11) + (j-1)m + (i-1) (1im , 1jn) (2)三维数组 以左下标为主序的存储方式。 设每个元素仅占一个单元地址，则aijk的地址为： Loc(aijk) = Loc(a111) + (k-1)lm + (j-1)l + (i-1) (1il , 1jm, 1kn) （FORTRAN语言按列优先） 3. 特殊矩阵的存放方式 (1)下三角矩阵的存储方式 矩阵A是一个下三角矩阵。 其非零元素按行优先顺序存放。 由于第1行到第i-1行的非零元素个数为： 1+2+ +(i-1) = i(i-1)/

50、2 设每个元素仅占一个单元地址，则非零元素aij的地址为： Loc(aij) = Loc(a11) + i(i-1)/2 + (j-1) (1jin) (2)三对角阵的存储方式 主对角线盒两条次对角线上的元素可以是非零，其余元素均为0，这种矩阵称为三对角阵。 非零元素按行优先顺序存放，则非零元素aij的地址为： Loc(aij) = Loc(a11) + 2(i-1) + (j-1) （ i=1, j=1,2 或i=n, j=(n-1),n 或1 i n, j=(i-1),i,i+1 ) 稀疏矩阵（略） 数组的链式存储结构（略）2.5 树与二叉树 树的定义及其存储结构 1. 树的定义和术语 (1)树的递归定义 树（Tree）是由n(n0)个结点组成的有限集合T，其中有且仅有一个结点称为根结点(root)，其余结点可以分为m(m0)个互不相交的有限集合T1,T2,Tm，其中每一个集合Ti本身又是一