计算机软件基础教案

课程名称：计算机软件基础

教学目的及教学设想：

本课程是非计算机专业的一门公共计算机课程，综合性与

实践性强，内容有一定的深度和难度。本课程是形成本专业专

门人才知识结构与能力结构的重要环节，也是学习本专业相关

课程的计算机软件基础课程。

通过教学，使学生具有计算机软件方面的必备知识。要求:

掌握计算机软件技术的基础知识；掌握操作系统的基本原理；

掌握数据结构的基本知识和常用算法；掌握软件工程的基本概

念、理论和方法；了解数据库的基本知识，掌握数据库技术的

应用；了解计算机网络的基础知识，掌握使用因特网的基本技

术；了解信息和计算机系统的安全保护技术。

根据非计算机专业的特点，教学以课堂上教师的讲课为主,

自学、讨论、答疑和完成作业为辅进行。

主要教材或参考文献：

[1]沈被娜，刘祖照，姚晓冬.《计算机软件技术基础》.清华大学

出版社，2000年7月第3版.

[2]郑守春，许占文，徐全生，张胜男.《计算机软件技术基础》.

大连理工大学出版社，1998年2月第1版.

考核方式及说明：

笔试（开卷）90分；平时成绩10分。

第1周

第1章信息与计算机

1.1信息与信息时代

1.1.1什么是信息

1.信息(information)的定义

(1)信息是对现实世界中存在的客观实体、现象、关系进行描述

的数据。

(2)信息是消息。

(3)信息是知识。

(4)信息是经过加工后并对实体的行为产生影响的数据。

(5)构成一定含义的一组数据。

2.数据(data)的定义

数据是现实世界客观存在的实体或事物的属性值，即指人们听

到的事实和看到的现象。

数据可以是数字、文字或符号，还可以是声音、语言、图形等。

3.信息与数据的关系

(1)信息是有一定含义的数据。

(2)信息是经过加工(处理)后的数据。

(3)信息是对决策有价值的数据。

(4)数据是信息的物理形式，是信息的载体。

4.信息的基本特性

(1)事实性：第一和基本的性质，也是信息的中心价值。

(2)等级性：不同的使用目的要求不同等级的信息，例如有战略

信息、策略信息、执行信息等等。

(3)可压缩性：可以对信息作浓缩处理，即进行集中、综合和概

括而又不丢失信息的本意。

(4)可扩散性：信息可以通过各种渠道和手段向四面八方扩散。

(5)可传输性：信息可以通过多种形式迅速传输，如电话、电报、

计算机网络系统、书报杂志、磁带光盘等。

(6)共享性：信息可以被多个用户共享而得到充分的利用。

(7)增值性与再生性：信息是有价值的，而且可以增值。

(8)转换性：信息、物质和能源是人类的三项重要的宝贵资源，

三位一体而又可以互相转换。

5.三种不同层次的信息产品

(1)数据：通过数据采集获得，用于事务处理系统。

(2)信息：通过数据处理获得，用于管理信息系统。

(3)知识：通过数据融合获得，是经过分析与综合的信息，用于

决策支持系统。

图1.2信息的三中不同层次示意图

1.1.2信息化是社会经济发展的必然结果

1.信息科学的巨大发展--一认识基础

(1)自然科学一一理论基础

自然科学领域在信息科学方面的研究，为现代信息处理技术和

信息传输技术的进一步发展准备了理论基础。

(2)社会科学一一经济属性

在社会科学领域，通过对信息效用性、稀缺性、成本、价值的

研究，发现了信息已经具备的经济属性，从而在理论上确立了信息

作为经济资源的重要地位。

信息科学的巨大发展构成现代信息化的认识基础，将信息在社

会经济中的重要性提高到了理论的高度。

2.信息技术的长足进步一一技术基础

(1)信息处理技术

信息处理技术领域中新的计算机元器件技术使得计算机在微型

化的同时，性能大幅度提高，成本大幅度降低。计算机正在向智能

化、集成化、综合化发展。

(2)信息传输技术(通信技术)

在通信技术领域，各种物理信道的通信技术和通信方式不断推

出和更新。宽带、高速、大容量已经成为现代通信信道的主要特征。

信息处理技术和通信技术的发展为当代信息化提供了技术手段

和工具，成为当代信息化的技术基础。

3.社会生产力的提高一一经济基础

经济的高速增长反映了社会生产力的空前提高，社会经济资源,

包括资金、原料、人力、智力等资源，有可能从传统的生产领域转

向信息领域。

生产力水平的提高为当代信息化提供了经济基础。

4.信息需求已成为普遍的社会需求一一社会基础

随着人们对信息重要性认识的深化以及信息利用水平的提高，

在社会、经济、文化、军事等各领域，以及政府、企业、公众等不

同层次的行为主体，对信息和信息技术的需求都有很大的增长。

5.信息时代的特点

(1)市场环境变化巨大

(2)机遇与挑战并存

(3)风险与效益并存

(4)多媒体、全球互联网、信息高速公路，是信息时代革命浪潮

中的三大主干技术。

1.1.3信息与计算机应用

1.信息技术(InformationTechnology缩写为IT)的三大组

成部分

(1)计算机硬件技术

(2)计算机软件技术

(3)通信技术

它包含了信息的产生、检测、变换、存储、传递、处理、显示、

识别、控制和利用拄的活动。

2.计算机的最主要特点

(1)高速自动的操作功能

(2)具有记忆的能力

(3)可以进行各种逻辑判断

(3)精确高速的计算能力

3.计算机应用

计算机科学与技术的划时代的意义是为人类提供了通用智力工

具。

1.2计算机发展简史

1.2.1计算机发展的几个重要阶段(略)

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年代：全球网络时代

3.数字化信息的特点

(1)容易交换，只要有传输媒体，即可以畅通无阻，无处不达;

(2)可以大容量、高速度传输，以满足人们对信息的需求；

(3)稳定性高，传输途中不受干扰，可以还其本来面貌。

1.2.2计算机应用的领域(略)

根据学科划分：

(1)科学研究与科学计算

(2)事务处理

(3)计算机辅助功能

(4)生产过程控制

(5)人工智能

(6)计算机网络通信

(7)计算机教育

(8)多媒体

1.2.3计算机在现代人类活动中的地位和作用

1.改变人类的工作和生活方式

分散一集中一分散

2.社会转型

(1)从工业时代转向信息时代

(2)从工业社会转向知识社会

1.2.4计算机的现在和未来(自学)

1.计算机的现在

(1)计算机在微小型化的同时，性能有了大幅度的提高

(2)计算机系统正向智能化、集成化、综合化发展

2.计算机和信息技术的未来发展

(1)建立未来的应用

(2)管理企业的应用

(3)新的电子商务应用

(4)解决人机文化差异的问题

1.3计算机与计算机系统

1.系统的定义

从技术的角度，定义：为完成特定任务而由相关部件或要素组

成的有机整体，成为系统。

2.系统的特点

(1)整体性(2)层次性(3)适应性

1.3.1计算机系统的组成(自学)

(1)计算,硬件系统的组成

(2)计算机裸机

2.硬件与软件结合说

(1)计算机软件系统

(2)计算机系统的狭义说法

3.计算机广义系统说

由五部分组成：

(1)人员(2)数据(3)设备

(4)程序(5)规程

1.3.2计算机的硬件与软件(自学)

1.微型计算机的硬件系统

(1)主机：CPU和内存

(2)外存储器

(3)输入设备

(4)输出设备

(5)微机系统总线：数据总线、地址总线和控制总线

2.微型计算机的软件系统

(1)系统软件

(2)应用软件

3.计算机硬件与软件的关系

(1)互相依存

(2)无严格界面

(3)相互促进

1.3.3多媒体计算机(自学)

L什么是多媒体计算机

(1)媒体

1)存储信息的实体：磁带、磁盘、光盘、半导体存储器。

2)表现信息形式的载体：数字、文字、图形、图像、视频。

(2)多媒体计算机的定义

多媒体计算机是以计算机为核心，可以综合处理数值计算、文

本文件、图形、图像、声频、视频等多种信息的计算机系统。

2.多媒体的基本要素

基本要素有：文本、图形、图像、动画、声频、视频。

3.多媒体计算机的基本配置

(1)硬件配置：CPU、内存大小、硬盘容量、光驱、视频卡和显

示器、声卡和音响设备。

(2)软件配置：最主要的是支持多媒体的操作系统(MPCOS)0

1.4计算机软件技术发展过程

1.4.1高级语言阶段

20世纪60年代,FORTRAN、ALG0L60.COBOL、LISP、PL/1O

编译系统主要靠手工编制，自动化程度很低。

1.4.2结构程序设计阶段

20世纪60年代末发生了软件危机。

1.程序的正确性

(1)三种基本结构：顺序、选择和循环

(a)顺序(b)选择(c)循环

图1.7程序的三种基本结构

(2)语义形式化

用数学符号严格地按照一定规则形式地表达某种程序语言，以

达到语义的精确化合编译自动化。

2.程序设计方法论

(1)由顶向下法

由顶向下、逐步细化，是结构程序设计的一种方法。分解一个

大系统为若干个子系统。

(2)自底向上的方法

自底开发程序模块，再处理各模块之间的联系，组合成整个软

件系统。

(3)模块化

模块划分的的基本原则。

3.软件生产管理

(1)软件工程：软件生产作为一种工程需要某种合理管理的体

制。

⑵软件生命周期法(见第6章)

1.4.3自动程序设计阶段

1.软件工程支撑环境

把过去分散编制的软件开发工具，集成为整体性的系统，称为

软件工程支撑环境，也称为CASE（computeraidedsoftware

engineering）0它支持软件开发和维护的全过程。

Rational软件公司是由PaulLevy和MikeDevlin于1991年

在硅谷成立的。它的一个CASE工具是RationalRose,在面向对象

技术和面向对象工具市场上占到领先位置。

2.程序设计基本方法的进一步改进

（1）传统软件开发方法的缺点

1）要求开发者有一定的计算机专业知识和程序设计经验；

2）软件开发的各阶段缺少反馈。

⑵改进

1）快速原型法

2）甚高级语言（非过程化语言）

3）软件可重用法

3.第四代语言（4GL）

⑴语言分代

1）第一代语言:1946-1950,机器语言；

2）第二代语言:1950-1960,汇编语言；

3）第三代语言：1960T980,过程化编程语言;

4）第四代语言：1980-1995,非过程化高级语言；

5）第五代语言：1995-，应用程序开发用专家系统。

（2）第四代语言与其他软件技术的关系

1）与数据库的关系：数据库是4GL的基础

2）与第三代语言的关系：依赖3GL,转换成3GL

3）与图形软件的关系：有可视化4GL

4.面向对象编程语言（见6.3.3节）

习题1.1-1.9

第2章常用数据结构与算法

2.1概述

2.1.1什么是数据结构

作为一门课程，数据结构是研究非数值运算的程序设计问题。

2.1.2有关数据结构的基本概念和术语

1.数据

数据(Data)是信息的载体，它可以用计算机表示并加工，如

数、字符、符号等的集合。

2数据元素

数据元素(dataelement)是数据集合中的一个个体，是数据

的基本单位。如集合N={1,2,3,4,5}中的整数1至5均为数据元素。

学生登记表中的一条记录，也是一个数据元素。

3.数据对象

具有相同性质的数据元素的集合称为世界对象(dataobject)。

4.数据结构

数据结构(datastructure)是指同一数据对象中各数据元素间

存在的关系。用集合论方法定义数据结构为

S=(D,R)

数据结构S是一个二元组，其中D是一个数据元素的非空有限

集合，R是定义在D上的关系的非空有限集合。

5.逻辑结构与物理结构

(1)数据的逻辑结构：研究数据元素及其关系的数学特性，简称

数据结构。

(2)数据的物理结构：是逻辑结构在计算机中的映像，也就是具

体实现，简称存储结构。

6.数据类型

⑴概念

数据热(datatype)是指程序设计语言中允许的变量类型。

(2)数据类型的分类

1)基本数据类型：如整型、实型、布尔型等，它们变量的值是

不可再分的。

2)结构数据类型：如数组、结构体等，它们变量的值是可再分

的，或者说它们是带结构的数据。

7.数据结构与算法

(1)算法

算法是解决某一特定类型问题的有限运算序列。

(2)数据结构与算法的关系

算法的实现必须借助程序设计语言中提供的数据类型及其运

算；数据结构是算法和程序设计的基本部分，它对程序设计的质量

影响很大。

2.1.3算法描述语言

1.自然语言

2.流程图(框图)等图形工具

3.高级程序设计语言，如C语言

4.类高级程序设计语言，如类C语言

2.1.4算法分析技术初步

1.时间复杂度

⑴例

设对一个nXn矩阵A自乘后送入矩阵B,其算法步骤为

①fori=1ton

②forj=1ton

③B[i,j]*-0

④fork=1ton

⑤B[i,j]*-b[i,j]+a[i,k]*a[k,j]

⑥end(k)

⑦end(j)

⑧end(i)

分析：语句3重复次数为3语句5重复次数为一°若语句3

执行1次的时间为3语句5执行1次的时间为3忽略控制语句

的执行时间，次算法耗用的时间近似为

7(〃)=t山+t2n

当〃很大时，有

T(〃)23

hm——=limt\n+tin

72n32

表明当〃很大时，T(〃)和跟的比值是常数,即7(A)和跟是同阶

的，记作7(A)=0(〃,)。

(2)频度

在算法中，一条语句重复的次数，称为该语句的频度，记作

例子中//分别是语句3和5的频度。

⑶时间复杂度

时间复杂着是以算法中频度最大的语句的频度来度量的，记作

T5)=0(尸(力)。例子中,时间复杂度为75)=05)。

(4)常见的时间复杂度

0(1)：常量型

0(/7),0(力，…，0(泊：多项式型

0(log27?),0(/71Og2/7)：对数型

0⑵)，0(e0)：指数型

(5)时间复杂度比较

0(1)<0(log27?)<0(77)<0(771og2Z?)<0(72')<…<0⑵)<0④)

2.空间复杂度

(1)概念

空间复杂度是指在算法中所需的辅助空间单元，而不包括问题

的原始数据占用的空间。

(2)表示

空间复杂度的表示与实践复杂度类似。

本例中所需的辅助空间单元为i、j、k,所以空间复杂度为S®

0(1)O

作业：(P101)2.5(1)(2)(3),注意(4)(5)有错，不要了。

2.2线性表

2.2.1线性表的定义和运算

1.什么是线性表

线性表是数据元素的有限序列。例：

n维向量x=(a］，a2,…，4),其中每个分量为一个数据元素;学

生表，一个学生的记录为一个数据元素。

2.线性表的一般表示形式

L=(ai,&2,,,,,an)

其中L为线性表，a.(i=1,2,…,n)是属于某数据对象的元素，n(n

20)为元素个数，又称为表长，n=。为空表。

3.线性表的结构特点

数据元素之间是线性关系，具体有四句话：

(1)线性表中必存在唯一的一个“第一个”元素；

(2)必存在唯一的一个“最后一个”元素；

(3)除第一个元素以外，每个元素有且只有一个前驱元素；

(4)除最后一个元素以外，每个元素有且只有一个后继元素。

4.线性表的形式定义

L=(D,R)

其中D={aba2,...,an}

R={<a，ii,a)|a,,CD,2WiWn}

若线性表中的数据元素相互之间可比较，且42即1,i=

2,3,...,n,则称L为有序表，否则称为无序表。

5.线性表的基本运算

(1)插入：在两个确定元素之间插入一个新元素；

(2)删除：删除线性表中某个元素；

(3)查找：按某种要求查找线性表的一个元素，需要时可以进行

更新；

(4)排序：按给定要求对表中元素重新排序。

6.线性表的存储结构

(1)顺序存储结构：向量；

(2)链式存储结构：链表。

2.2.2顺序存储线性表

1.顺序存储结构

(1)顺序存储结构的含义

是用一组地址连续的存储单元存放线性表的数据元素，称为线

性表的顺序存储结构，也称为向量式存储结构，又称为随机存储结

构。用高级语言中的一维数组类型表示，例如A[l:n]0

(2)求顺序存储线性表中第i个元素的存储地址

设：已知线性表中每个元素占1个单元，且线性表在内存中的

首地址为：adrCa.)=b,则线性表中第i个元素的存储地址为

adr(aj=adr(aj+(i-l)1

2.顺序存储结构的插入、删除运算

⑴插入

设长度为n的线性表(a,a2,a“)，要求在第iT与第i个元

素之间插入一个新元素XO

1)顺序存储线性表的插入过程

将第n至第i个元素一次向后移动一个位置，原第i个元素的

位置被空出来了；

将x放入被空出的存储单元；

将线性表的长度增lo

2)插入算法

设存放线性表的向量为算法如下：

①INSERTLIST(V,n,i,x)

②if(i<l)OR(i>n+l)then{参数错return}

③forj=ntoistep(-1)

④V[j+1]-V[j]

⑤end(j)

⑥V[i]—x

⑦n-n+1

return

3)插入算法说明

语句1是将异常情况作出错处理。

语句2-4是将后移n-(iT)个元素，即i-1个元素不用移动；

step(T)表示j从n开始每次减1,j为iT时停止循环。

语句5是将元素x送入原第i个元素的位置。

语句6是将线性表的长度增加lo

⑵删除

设长度为n的线性表(a,a2,an),要求删除第i个元素。

1)顺序存储线性表的删除过程

将第i个元素ai以后的元素ai.1,,,,,an依次向前移动一个位置。

将线性表的长度减1。

2)删除算法

设存放线性表的向量为算法如下：

DELETELIST(V,n,i)

①if(i<l)OR(i>n)then｛参数错return)

②forj=iton-1

③V[j]-V[j+1]

④end(j)

⑤n-n-1

⑥return

3)删除算法说明

语句1是将异常情况作出错处理。

语句2-4是将前移n-(i-l)个元素，即i-1个元素不用移动。

语句5是将线性表的长度减少lo

3.顺序存储结构的插入、删除运算的时间分析

运算的时间主要移动元素上，且移动元素的个数与线性表的程

度，以及与被插入或删除元素在线性表中的位置i有关。

用最少移动次数，最多移动次数，平均移动次数来分析。

(1)插入算法

最少移动次数0(i=n+l),最多移动次数n(i=l),

平均移动次数=(0+1+…+n)/(n+l)=n/2

(2)删除算法

最少移动次数0(i=n),最多移动次数n-1(i=l),

平均移动次数=(0+1+…+(nT))/n=(n-l)/2

作业:(P102)2.8,2.11

第2周

2.2.3线性链表

1.链式存储结构

(1)顺序存储线性表的插入、删除运算的不足

1)可能要移动大量的数据元素，当n很大的时候，花费很多时

间；

2)需要预留存储单元，浪费资源；若预留资源不足，会溢出。

(2)链式存储结构的含义

链式存储结构不需要一组连续的存储单元，它的数据元素可以

分散存放在存储空间中，为了使线性表在逻辑上保持连续，必须在

每个元素中存放其后继元素的地址。这样由n个结点组成的序列便

构成一个链表，称为线性表的链式存储结构。

(3)链式存储结构的概念

链式存储结构(又称指针类型结构)示意图如下：

datanext

1)数据域与指针域：指针类型结构中，每一个数据元素由两部

分组成：一部分是存放元素的值，称为数据域，用“data”表示；

?一部分为存放后继元素的存储地址，称为指针域，用“next”表

/J,So

2)头指针：指示链表中第一个结点地址的指针，称为头指针，

用“head”表示。

3)空指针：链表中最后一个结点的指针为空指针，用“nil”或

“A”表示。

2.线性链表的基本运算

(1)基本操作

线性链表的四种基本操作，如29页的表2.2所示。

设P、q、s均为指针型变量，指向数据域为data,指针域为next

的结点。

1)指针赋值

将某地址指针值赋给一个指针变量。有两种情况：

①s-p〃将指针变量p的内容赋给另一个指针变量s//

例：若p=2000,经过语句s<—p后，s=2000

②q-next(p)〃将指针变量p的next域内容赋给

另一个指针变量s//

例：若p=2000,p指向的结点的指针域内容为1200,经过语句

q-next(p)后，q=1200。

2)指针移动

当前指针指向链表的下一个结点的地址指针。

p-next(p)//将指针变量p的next域内容赋给指针变量p//

例：若p=2000,p指向的结点的指针域内容为1200,经过语句

p—next(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(p)和后，p的next域内容为3000,

s的next域内容为1200。

注意：这两条语句的次序不能换。

4)前插

在P指向的结点地址前插入一个新元素。

先要找到P指向的结点之前的结点指针q，然后利用3)的后插

算法。找到方法是从头指针(赋给q)开始，判断“next(q)=p?

①q-head//将头指针变量head的地址赋给指针变量q〃

②While(next(q)Wp)do

③{q—next(q)}〃在next(q)=p时退出循环，否则指针移动〃

④next(q)-s〃将新结点的地址s赋给q的指针域〃

⑤next(s)-p〃将已知结点的地址p赋给s的指针域〃

注意：后两条语句的次序可以交换。思考为什么？

(2)结点的动态生成与回收

设存储器中有一个空白链表，表示没有使用的存储单元，可供

用户使用。空白链表的头指针为avo

1)从空白链表中获得一个结点，地址指针是Po算法如下：

(将空白链表的第1个结点给用户使用。)

GETNODE(P)

①p-av〃取走空白链表中的第1个结点，将av赋给p〃

②av-next(av)〃将空白链表中原第2个结点置为头结点〃

(3)return

2)回收一个由p指针指向的结点。算法如下：

(将回收的结点作为空白链表的第1个结点)

RET(P)

①next(p)-av//原空白链表中的头指针av赋给p的指针域〃

②av-p〃将指针p赋给头指针av//。

③return

(3)插入运算

1)要求：在头指针为head的链表中，值为a的结点前，插入一

个值为b的结点。

2)分析：3要是要寻找包含指定元素a的结点及之前的结点qo

分析没有找到包含指定元素a的结点的异常情况及解决方法：

①若链表为空表：b为链表的第1个结点。

②若链表中无值为a的结点：将b添加到链表的末尾。

3)在非空链表中，寻找包含指定元素a的结点之前的结点q。

算法如下：(排除了a包含在第1个结点及空表)

LOOKFOR(head,a,q)

①q-head〃将头指针变量head的地址赋给指针变量q//

②while(next(q)Wnil)and(data(next(q))Wa)do

③{q-next(q)}〃如果q的下一个结点存在，同时它的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{head-p;next(p)-nil;return}

〃处理空表情况，p为头指针，p的指针域为空〃

③if(data(head)=a)then{next(p)-head;head*-p;return}

//处理第1个结点值为a的情况：p的指针域是

原来的头指针head,再将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的结点及之前的结点qo

算法还需要处理四种情况：

①若链表为空表：不删除。

②若链表中只有一个值为a的结点：删除元素a的结点后，链

表变为空表。

③在链表中找到值为a的结点，且不是第1个结点：删除。

④若链表中无值为a的结点：不删除。

4)删除算法

DELINKST(head,a)

①if(head=nil)then{空表return}〃空表情况〃

②if(data(head)=a)then(s*-next(head);RET(head);

head-s;return}//处理头结点值为a的情况：

将第2个结点指针(在a结点的指针域中)先暂存在s

变量中，在删除第1个结点(回收)，最后修改头指针〃

③LOOKFOR(head,a,q)〃调用函数,找元素a之前的结点q//

④if(next(q)=nil)then{无此结点return}

〃处理未找到a的情况〃

⑤p-next(q);next(q)-next(p)〃处理找到a的情况〃

⑥RET(p)

⑦return

3.线性链表的其他形式

（1）具有头结点的线性链表

在链装的第二个结点之前附加一个头结点，该结点的结构和链

表中的其他结点相同，只是它的数据域中不存放线性表的元素，它

的指针指向线性表的第一个元素。

具有头结点的线性链表为空表时，只有一个头结点，其指针域

为空。

（2）循环链表

1）循环链表的定义

循环链表是另一种链式存储结构，它的特点是表中最后一个结

点的指针域不为空，而是指向表头，整个链表形成一个环。

2）具有头结点的循环链表

是指带有头结点的循环链表。

3）循环链表的优点

只要给出循环链表中任一结点的地址，就可以查遍表中所有结

点，而不必从头指针开始。

（3）双向链表

1）双向链表的定义

在线性链表中增加一个指针域，其指针指向直接前驱，称为双

向链表。

2）双向链表的优点

从表中某一给定的结点可以随意向前或向后查看。

但在做插入、删除运算时，需同时修改两个方向上的指针。

4.线性链表的应用实例----元多项式相加（略）

2.2.4向量和链表的比较（自学）

1.线性表的长度是否固定

向量一固定，线性链表一不固定

2.线性表的主要操作是什么

向量一查询，线性链表一插入和删除

向量一随意，“口线性链表一提供指针类型变量

作业:(P102)2.12,2.13

补充题：对具有头结点的线性表，写出插入算法。

2.3栈与队

2.3.1栈的结构和运算

1.栈的定义

(1)栈(stack)：栈是限定只能在表的一端进行插入和删除操作

的线性表。又称为后进先出的线性表。

(2)栈顶(top)：栈中允许插入或删除的一端称为栈顶。

(3)栈底(bottom)：栈中不允许插入或删除的一端称为栈底。

(4)空栈：栈中没有元素时，称为空栈。

(5)进栈(入栈，push)：向栈中插入元素，称为进栈。

(6)退栈(出栈,pop)：将栈中元素删除，称为退栈。

2.顺序栈

(1)顺序栈的定义

1)顺序栈：用向量作为栈的存储结构。高级语言中用一维数组

来表示，其中m表示栈允许的最大容量。

2)栈顶指示器：设置一个简单变量(top)用来指示栈顶位置，

称为栈顶指示器。

3)栈空：当栈顶指示器top=0时，表示栈空。

4)栈满：当栈顶指示器top=m时，表示栈满。

5)栈上溢：当栈顶指示器top=m时再有元素进栈，栈将溢出，

称为上溢。

6)栈下溢：当栈空时要作退栈操作，栈也将溢出，称为下溢。

(2)顺序栈的插入运算(进栈)

1)要求：将元素x插入顺序栈

2)分析：先令top加1,再将元素x送入s[top]中。但要先判

断是否会“上溢”。

3)算法:

PUSH(s,m,top,x)〃将元素x送入栈中〃

①if(top=m)then{“上溢”,return}

②top-top+1

③s[top]-x〃处理正常入栈〃

④return

(3)顺序栈的删除运算(退栈)

1)要求：将栈顶元素取出。

2)分析：先将栈顶元素放入y,再将栈顶指针top减1。但要先

判断是否会“下溢”。

3)算法:

P0P(s,top,y)〃退栈，将栈顶元素送入y中〃

①if(top=0)then{“下溢",return}

②y-s[top]

③top-topT〃处理正常出栈〃

④return

3.链栈(自学)

(1)链栈的定义：用链表作为栈的存储结构，称为链栈。若

top=nil,则表示栈空。链栈不会出现“上溢”，除非内存中已不存

在可用空间。

(2)链栈的插入运算

(3)链栈的删除运算

4.栈的应用(自学)

5.栈的练习题(自学)

已知有四个元素，它们关键字分别是1,2,3,4。如果入栈的

次序是4321,假设入栈时可以出栈，问：哪几种排列是可能的出栈

过程？

作业：(P103)2.21

第3周

2.3.2队的结构和运算

1.队的定义

（1）队（queue）：队是限定只允许在一端进行插入，在另一端进

行删除操作的线性表。又称为先进先出的线性表。

（2）队尾：队中允许插入的一端称为队尾。

（3）队尾指示器（rear）：指向队尾元素。

（4）排头：队中允许删除的一端称为排头。

（5）排头指示器（front）：指向排头元素。

2.顺序队

（1）顺序队的定义

1）顺序队：用向量作为队的存储结构。高级语言中用一维数组

来表示，其中m表示队允许的最大容量。

2）顺序队空：front=rear（初始时front=rear=0）。

3）入队：rear增1,front不变。即初始时front=0,rear=lo

4）出队：front增1,rear不变。

5）队上溢：当队中已有m个元素时再有元素入队，队将溢出，

称为队上溢。

6）队下溢：当队空时要作出队操作，队也将溢出，称为队下溢。

7）假溢出：当rear=m时，无法再继续入队，但队不满，这时称

为队假溢出。因为只有当rear-front=m时一，才是真满。

8）循环队列：把存放队列的数组形成一个头尾相接的环形，称

为循环队列。

（2）循环队列的插入运算

1）要求:将元素x插入循环队列CQ[0:mT]。假设头尾指示器

初始时front=rear=m-lo

注意front指向队列第一个元素的前一个位置。

2）分析：有两种算法：①先找到插入位置，然后进行判断队是

否满，若不满，再插入数据xo②先判断队是否满，若不满，再找

到插入位置，最后插入数据XO

3）循环队列的插入算法1

ADDCQ(CQ,m,front,rear,x)〃将x插入队列CQ中〃

①rear—(rear+1)modm//求模运算，找到应插入的位置〃

②if(front=rear)then{“队满“；rear*-(rear-1)modm；

return}//判断，若队满，恢复原队尾指示器，返回〃

③CQ[rear]*-x〃插入数据的操作〃

④return

4)循环队列的插入算法2

ADDCQ2(CQ,m,front,rear,x)〃将x插入队列CQ中〃

①if(front=(rear+1)modm)then{“队满“，return}

〃判断，若队满，返回〃

②rear'-(rear+1)modm〃求模运算，找到应插入的位置〃

③CQ[rear]-x〃插入数据的操作〃

④return

(3)循环队列的删除运算

1)要求：将循环队列CQ[0:m-l]的队首元素取出，并删除。假

设头尾指示器初始时front=rear=m-lo

2)分析：先判断队是否空，若不空，找到删除元素的位置，将

队首元素放入y,排头指示器front增1°

3)算法:

DELCQ(CQ,m,front,rear,y)〃删除队首元素送入y中〃

①if(front=rear)then{“队空〃,return}

〃判断，若队空，返回〃

②front-(front+1)modm〃求模运算，找到删除的位置〃

③y-CQ(front)〃删除操作，将队首元素赋值给y〃

④return

3.链队

(1)链队的定义：用链表作为队的存储结构，称为链队。头指针

front固定指向头结点，注意：头结点不放数据；尾指针指向队尾

元素，front=rear表示队空。链队不会出现“上溢”，除非内存

中已不存在可用空间。

(2)链队的插入运算

分析：由于是队，故插入到链表的最后。

ADDLINK(front,rear,x)〃在链队中插入x结点〃

①GETNODE(p)〃获取一个空白结点p〃

②data(p)-x;next(p)-nil〃给空结点赋值〃

③next(rear)-p;rear-p

〃将结点P插入到队尾，修改队尾指示器〃

④return

(3)链队的删除运算

分析：由于是队，故删除链表的第一个元素。

DELLINK(front,rear,y)//删除排头元素，并赋值给y〃

①if(front=rear)then{“队空”,return}

〃判断，若队空，返回〃

②y--data(next(front));next(front)-next(next(front))

〃将排头元素取出赋给y,//

〃修改头结点的指针域，它指向排头结点〃

③if(next(front)=nil)thenrear-front

〃若删除结束时链队已成为空队，修改队尾指示器〃

④return

4.队的应用(略)

2.4数组

2.4.1数组的定义

1.二维数组(数学中的矩阵)

例：

aw412...aI?；

di\Cl22•••din

A=

•・・•••・・・•••

Clm\dm2・・・dinn

2.用线性表定义二维数组

令B=(K,R)

其中K={Ku|IWiWm,IWjWn}

R由两个关系组成

行ROW={Kij,Kij+11IWiWm,IWjWnT}

列COL={Kij,KnulIWiWm-1,IWjWn}

2.4.2数组的顺序存储结构

用一维连续单元存放多维的数组。

1.按行优先顺序存放

(1)二维数组

先第1行n个元素，再第2行n个元素，…。

设每个元素仅占一个单元地址，则布的地址为：

Loc(aij)=Loc(an)+(i-1)Xn+(j-1)

(IWiWm,IWjWn)

(2)三维数组

以左下标为主序的存储方式。

设每个元素仅占一个单元地址，则呢”的地址为：

Loc(aijk)=Loc(am)+(i-l)XmXn+(j-1)Xn+(k-l)

(IWiWl,lWjWm,IWkWn)

(c,BASIC语言按行优先)

2.按列优先顺序存放

(1)二维数组

先第1列m个元素，再第2列m个元素，…。

设每个元素仅占一个单元地址，则a”的地址为：

Loc(asj)=Loc(an)+(j-1)Xm+(i-1)

(IWiWm,IWjWn)

(2)三维数组

以左下标为主序的存储方式。

设每个元素仅占一个单元地址，则am的地址为：

Loc(aijk)=Loc(am)+(k-l)X1Xm+(j-1)X1+(i-1)

(lWiWl,lWjWm,IWkWn)

(FORTRAN语言按列优先)

3.特殊矩阵的存放方式

(1)下三角矩阵的存储方式

矩阵A是一个下三角矩阵。

aw0..0

ai\U22..0

A=

a,\dill.■dm

其非零元素按行优先顺序存放。

由于第1行到第iT行的非零元素个数为：

1+2+…+(i-l)=i(i-l)/2

设每个元素仅占一个单元地址，则非零元素呢的地址为：

Loc(au)=Loc(an)+i(i-l)/2+(j-1)

(IWjWiWn)

(2)三对角阵的存储方式

主对角线盒两条次对角线上的元素可以是非零，其余元素均为

0,这种矩阵称为三对角阵。

非零元素按行优先顺序存放，则非零元素a”的地址为：

Loc(a”)=Loc(an)+2(iT)+(j-1)

(i=l,j=l,2

或i=n,j=(n-l),n

或1<i<n,j=(i-l),i,i+1)

2.4.3稀疏矩阵(略)

2.4.4数组的链式存储结构(略)

作业：(P103)2.22,2.25

2.5树与二叉树

2.5.1树的定义及其存储结构

1.树的定义和术语

(1)树的递归定义

树(Tree)是由n(nNO)个结点组成的有限集合T,其中有且仅

有一个结点称为根结点(root),其余结点可以分为m(m20)个互不

相交的有限集合TbT2,Tm,其中每一个集合T,本身又是一棵树，

称为根结点的子树。

当n=0时，称为空树。

(2)用二元组关系定义树

用二元组关系定义树为

Tree=(T,R)

数据结构树(Tree)由数据元素集合T及关系R组成。其中

T是具有相同类型的数据元素集合T={x„X2,…,xn}o若T为

空集(丁=中)，则R=①，称为空树；否则R是T上某个二元关系H

的集合，即1?=恒}。H的描述如下：

1)在T中存在唯一的称为根的元素root,它在H关系下无前驱。

2)若「{root}W中,则存在m个子集TbT2,Tm(m>0),对任意

的j#k(lWj,kWm),有TQTk=①，且存在唯一的数据元素xPTi

(IWiWm),满足〈root,Xi〉。

3)对应于Ti,T2,Tm,H-{〈root,x〉，…，〈root,x)}划分为m

个子集Ik…，乩(m>0),对任意的jWk(lWOkWm),有乩门乩二①，

乩满足「上的二元关系。因此，(T“{HJ)也是一课符合本定义的树,

称为根root的子树。

(3)常用术语

1)结点(node)：表示树中的元素。

2)结点的度、树的度(degree)：结点拥有的子树数，称为结点

的度；一棵树中最大的结点度数，称为这棵树的度。

3)叶子(leaf)：度为零的结点，又称端结点。

4)孩子(child)：除根结点外，每个结点都是其前驱结点的孩

子。又称子女。

5)双亲(parents)：对应于孩子的上层结点，称为这些结点的

双亲O

6)兄弟(sibling)：同一双亲的孩子。

7)结点的层次(level)：从根结点开始，根为第一层，根的直

接后继结点为第二层，其余各层依次类推。

8)深度(depth)：树中结点的层次数。

9)森林(forest)：是m(m，0)棵互不相交的树的结合。

10)有序树：树中结点在同层中按从左至右的有序排列、不能互

换的，称为有序树。反之，称为无序树。

2.树的存储结构——链式结构

(1)指针域个数不同——异构型

每个结点设有多个指针域，其中每一个指针指向一棵子树的根

结点。根据每一个结点的子树数设置相应的指针域，由于树中每个

结点的度数不尽相同，则一棵树中各结点的结构形式也不同，称为

结构异构型。

好处：节省存储空间。缺点：运算不方便。

(2)指针域个数相同——同构型

每个结点的指针域个数均为树的度数，一棵树中各结点的结构

形式相同，称为结构同构型。

好处：运算方便。缺点：出现很多空指针域，浪费空间。

空指针域的计算方法：设一棵有n个结点k叉树，则共有nk个

指针域，有用的指针域为L1个。空指针域的个数是：nk-(nT)

对不同的k值，

lim*D+L

J0°nk

..〃(&-1)+12〃+12

K=3,---------=-----=—

nk3〃3

7.九(左一1)+1〃+11

k=2,---------=----=—

nk2〃2

当k=2时，空指针域的比例最低，这就是二叉树。

2.5.2二叉树及其性质

1.二叉树的定义

(1)二叉树的递归定义

二叉树是由n(nNO)个结点的有限集合，它或为空树(n=0),

或由一个根结点和两棵分别称为左子树与右子树的互不相交的二叉

树构成。

(2)用二元组关系定义二叉树

用二元组关系定义二叉树BT为

BT=(D,R)

其中D为相同类型元素的集合口=区,X2,…,xj,若D为空集(D=

中)，则R=中，称为空二叉树；若DW①，则R是D上某个二元关系

H的集合，即1?=出}°H的描述如下：

1)在D中存在唯一的称为根的元素r,它在H关系下无前驱。

2)若D-{r}W①,则D-{r}={瓦D)且D,GDR=⑦。

3)若DL。①，则在DL中存在唯一的元素XL,满足G,XL>£H,且

存在D上的关系HL£Ho

若DR/①，则在DR中存在唯一的元素XR,满足<r,XR>£H,且存

在DR上的关系HR£Ho

4)(D,„HL)是一棵符合本定义的二叉树，称为根r的左子树；

(及山)是一棵符合本定义的二叉树，称为根r的右子树。

(3)二叉树与树的区别

二叉树的结点的子树有明确的左、右之分，而普通树没有。

(4)二叉树的存储结构

用具有两个指针域的链表作为二叉树的存储结构，其中每个结

点由数据域(data)、左指针域(Lchild)和右指针域(Rchild)

组成。

LchilddataRchild

2.二叉树的基本性质

(1)二叉树的第i层上至多有2-(iNl)个结点。

证明：用数学归纳法证明。

i=l,则结点数为1,只有一个根结点，结论成立。

按数学归纳法，假定第iT层上的结点数至多有2gz=21个。

由于二叉树中每一个结点的度数最大为2,因此，第i层的结点数

至多是第I层上的结点数的2倍，于是2X212=2L证毕！

(2)深度为h的二叉树中至多含有2卜-1个结点。

证明：利用性质(1)的结论。每一层上取最多的结点数，有

1+2+•••+2"+211T=2h-1o证毕！

(3)在任意二叉树中，若有n。个叶子结点，出个度数为2的结点,

则必有n0=n2+1o

证明：增加儿个变量：度数为1的结点结点数为整棵树的

结点数为n,连线(边)数为bo

结点总数是度数为0、1、2的结点的和，n=n0+n,+n2

除根结点外，其他所有结点都有与其双亲的指针，n=b+1

而b又可以看做结点与它的子女之间的联系，b=n,+2n2

后两个式子消去b,得到n=n.+2n2+1

再代入第一个式子，得到n0+ni+n2=n,+2n2+1

于是有n0=n2+1o证毕！

3.几种特殊形式的二叉树

(1)满二叉树

深度为h且含有2h-1个结点的二叉树称为满二叉树。图2.1

所示为一棵深度为4的满二叉树。

可以对满二叉树的结点进行编号，其次序是自上至下，自左至

右。

图2.1满二叉树

(2)完全二叉树

如果一棵有n个结点的二叉树，按与满二叉树相同的的编号方

式对结点进行编号,若树中n个结点和满二叉树1〜n编号完全一致,

则称该树为完全二叉树。图2.2(a)是一棵完全二叉树，图2.2(b)

就不是一棵完全二叉树。

图2.2完全二叉树与非完全二叉树

(3)平衡二叉树

平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列

性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和

右子树的深度之差的绝对值不超过1.

左子树和右子树的深度之差称为平衡因子，只能是T、0、1。

图2.3(a)是一棵平衡二叉树，图2.3(b)是一棵非平衡二叉树。

图2.3平衡二叉树与非平衡二叉树

4.一般树转为二叉树

由于二叉树的优良性质，所以人们想法找出一般树与二叉树的

对应关系，而且是---对应的。

将一棵普通树转换为二叉树的方法如下：

(1)将普通树的兄弟结点之间加一连线；

(2)对每个结点，除了与它的第一个孩子保持联系外，去除与其

他孩子的联系；

(3)以树根为轴心，将整棵树顺时针旋转45°。

图2.4(a)是一课普通树,图2.4(b)是一棵(1)、(2)步后的结

果，图2.4(c)是转换成的二叉树。

这种转换是唯一的。并且右子树是空的。

图2.4一般树转换为二叉树

2.5.3二叉树的遍历

遍历(traversing)是指循某条搜索路线，依次访问某数据结

构中的全部结点，而且每个结点只被访问一次。

1.遍历二叉树的定义

(1)遍历二叉树的递归定义

遍历二叉树是指依次遍历二叉树的根结点、左子树、右子树三

部分的结点。

若果以D、L、R分别表示访问根结点、遍历左子树和遍历右子

树，则可以有DLR、LDR、LRD、DRL、RDL和RLD六种形式。

若规定先左后右，则可以归并成三种形式，并以访问根的先后

来命名：

DLR：先序遍历

LDR：中序遍历

LRD：后序遍历

2.遍历二叉树算法

(1)先序遍历

PREORDER(p)//先序遍历〃

①if(pWnil)then

②{write(data(p));//访问根结点//

③PREORDER(Lch