tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

信息技术竞赛辅导


信息技术竞赛辅导 目录
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

计算机基础知识 第一章 计算机基础常识 第二章 操作系统简介 第三章 计算机网络 第四章 计算机信息安全基础知识 Pascal 语言 第一章 开始编写 pascal 语言程序 第二章 Pascal 语言基础知识 第三章

顺序结构程序设计 第四章 选择结构程序设计 第五章 循环结构程序设计 第六章 数组与字符串 第七章 函数和过程 第八章 子界与枚举类型 第九章 集合类型 第十章 记录与文件类型 第十一章 指针 第十二章 程序调试 常用算法与策略 第一章 算法的概念 第二章 递归 第三章 回溯 第四章 排序 第五章 查找 第六章 穷举策略 第七章 贪心算法 第八章 分治策略

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

数据结构 第一章 什么是数据结构 第二章 线性表 第三章 栈 第四章 队 第五章 树 第六章 图 动态规划 第一章 什么叫动态规划 第二章 用动态规划解题 第三章 典型例题与习题 第四章 动态规划的递归函数法 第五章 动态规划分类 1 数学知识及相关算法 第一章 有关数论的算法 第二章 高精度计算 第三章 排列与组合 第四章 计算几何 第五章 其它数学知识及算法 图论算法 第一章 最小生成树 第二章 最短路径 第三章 拓扑排序(AOV 网) 第四章 关键路径(AOE 网) 第五章 网络流 第六章 图匹配 搜索算法与优化 第一章 双向广度优先搜索 第二章 分支定界法 第三章 A 算法
*

青少年信息学奥林匹克竞赛情况简介

信息学奥林匹克竞赛是一项旨在推动计算机普及的学科竞赛活动,重在培养学生能力,使得有潜 质有才华的学生在竞赛活动中锻炼和发展。近年来,信息学竞赛活动组织逐步趋于规范和完善,基本上 形成了“地级市——省(直辖市)——全国——国际”四级相互接轨的竞赛网络。 现把有关赛事情况简介 如下: 全国青少年信息学(计算机)奥林匹克分区联赛: 在举办 1995 年 NOI 活动之前,为了扩大普及的面,并考虑到多数省、直辖市、自治区已经开展了多 年省级竞赛,举办了首届全国青少年信息学(计算机)奥林匹克分区联赛。考虑到不同年级学生的知识 层次,也为了鼓励更多的学生积极参与,竞赛设提高组、普及组,并分初、复赛进行,这样可以形成一 个梯队,确保每年的竞赛活动有比较广泛扎实的基础。 从 1995 年起,至 2001 年共举办了七届全国青少年信息学奥林匹克分区联赛,每年举办一次,有选 手个人奖项(省、国家级)、选手等级证书、优秀参赛学校奖项。 广东省青少年信息学(计算机)奥林匹克决赛(简称 GDOI): 省级信息学奥赛是一个水平较高的、有较大影响力的学科竞赛。由各市组织代表队参赛,参赛名额 实行动态分配制度,每年举办一次。从 1984 年起广东省奥林匹克竞赛活动得到了蓬勃发展。奖项有个 人一、二、三等奖,女选手第一、二、三名,奖励学校团体总分 1-8 名、市团体总分 1-8 名。 全国青少年信息学(计算机)奥林匹克竞赛(简称 NOI): 由中国算机学会主办的、并与国际信息学奥林匹克接轨的一项全国性青少年学科竞赛活动。1984 年 举办首届全国计算机竞赛。由各省市组织参赛,每年举办一次。奖项有个人一、二、三等奖,女选手第 一、二、三名,各省队团体总分名次排队。 国际青少年信息学(计算机)奥林匹克竞赛(简称 IOI): 每年举办一次,由各参赛国家组队参赛。 全国青少年信息学(计算机)奥林匹克分区联赛竞赛大纲 一、初赛内容与要求:(#表示普及组不涉及,以下同) * 诞生与发展 *特点 *在现代社会中的应用

计 基 * 计算机系统的基本组成 算 本 * 计算机的工作原理# 机 常 * 计算机信息安全基础知识 *计算机中的数的表示 *计算机网络

的 识 计 基 * MS DOS 与 Windows 的使用基础 算 本 * 常用输入/输出设备的种类、功能、使用 机 操 * 汉字输入/输出方法 的 作 * 常用计算机屏示信息 * 自然语言的描述 程序的表示 * PASCAL 或 BASIC 语言 * 简单数据的类型 数据结构的类型 * 构造类型:数组、字符串 * 了解基本数据结构(线性表、队列与栈) 程 序 设 计 基 本 知 识 程序设计 * 结构化程序的基本概念 * 阅读理解程序的基本能力 * 具有完成下列过程的能力: 现实世界(指知识范畴的问题) —>信息世界(表达解法) —>计算机世界(将解法用计算机能实现的数据结构和算法 描述出来) * 简单搜索 * 排序 基本算法处理 * 统计 * 字串处理 * 查找 * 分类 * 合并

* 简单的回溯算法 * 简单的递归算法 二、复赛内容与要求: 在初赛的内容上增加以下内容(2002 年修改稿): 计算机 软 件 *操作系统的使用知识 *编程语言的使用 *结构类型中的记录类型

数 据 结 构

*指针类型 *文件(提高组必须会使用文本文件输入) *链表 *树 *图 #

程 *程序设计能力 序 *设计测试数据的能力 设 *运行时间和占用空间的估算能力# 计 *排列组合的应用 算 法 处 理 *进一步加深回溯算法、递归算法 *分治法 *搜索算法:宽度、深度优先算法 *表达式处理:计算、展开、化简等# *动态规划# 三、初赛试题类型:注:试题语言两者选一 (程序设计语言:基本 BASIC 或 TURBO PASCAL) *判断 *填空 *完善程序 *读程序写运行结果 *问答 四、推荐读物: *分区联赛辅导丛书 *学生计算机世界报及少年电世界杂志

第一部 计算机基础知识
第一节 计算机的基本常识
1.1 计算机的产生和发展 1.2 计算机的系统及工作原理 1.3 计算机中有关数、编码的基本常识 1.4 原码、反码与补码 1.5 逻辑运算 1.1 计算机的产生与发展 计算机的产生是 20 世纪最重要的科学技术大事件之一。世界上的第一台计算机(ENIAC)于 1946 年诞 生在美国宾夕法尼亚大学,到目前为止,计算机的发展大致经历了四代: ① 第一代电子管计算机,始于 1946 年,结构上以 CPU 为中心,使用计算机语言,速度慢,

存储量小,主要用于数值计算; ② 第二代晶体管计算机,始于 1958 年,结构上以存储器为中心,使用高级语言,应用范围

扩大到数据处理和工业控制; ③ 第三代中小规模集成电路计算机,始于 1964 年,结构上仍以存储器为中心,增加了多种

外部设备,软件得到了一定的发展,文字图象处理功能加强; ④ 第四代大规模和超大规模集成电路计算机,始于 1971 年,应用更广泛,很多核心部件可

集成在一个或多个芯片上,从而出现了微型计算机。 我国从 1956 年开始电子计算机的科研和教学工作,1983 年研制成功 1 亿/秒运算速度的“银河”巨 型计算机,1992 年 11 月研制成功 10 亿/秒运算速度的“银河 II”巨型计算机,1997 年研制了每秒 130 亿运算速度的“银河 III”巨型计算机。 目前计算机的发展向微型化和巨型化、多媒体化和网络化方向发展。计算机的通信产业已经成为 新型的高科技产业。计算机网络的出现,改变了人们的工作方式、学习方式、思维方式和生活方式。

1.2 计算机系统及工作原理 1.计算机的系统组成 计算机系统由软件和硬件两部分组成。硬件即构成计算机的电子元器件;软件即程序和有关文档资料。 (1) 计算机的主要硬件 输入设备:键盘、鼠标、扫描仪等。

输出设备:显示器、打印机、绘图仪等。 中央处理器(CPU):包括控制器和运算器运算器,可以进行算术运算和逻辑运算;控制器是计算机的 指挥系统,它的操作过程是取指令——分析指令——执行指令。 存储器:具有记忆功能的物理器件,用于存储信息。存储器分为内存和外存 ①内存是半导体存储器(主存): 它分为只读存储器(ROM)和随机存储器(RAM)和高速缓冲存储器(Cache); ROM:只能读,不能用普通方法写入,通常由厂家生产时写入,写入后数据不容易丢失,也可以用特殊 方法(如紫外线擦除(EPROM)或电擦除(EEPROM_)存储器); RAM:可读可写,断电后内容全部丢失; Cache:因为 CPU 读写 RAM 的时间需要等待, 为了减少等待时间, 在 RAM 和 CPU 间需要设置高速缓存 Cache, 断电后其内容丢失。 ②外存:磁性存储器——软盘和硬盘;光电存储器——光盘,它们可以作为永久存器; ③存储器的两个重要技术指标:存取速度和存储容量。内存的存取速度最快(与 CPU 速 度相匹配),软 盘存取速度最慢。存储容量是指存储的信息量,它用字节(Byte)作为基本单位, 1 字节用 8 位二进制数表示,1KB=1024B,1MB=1024KB,lGB=1024MB (2)计算机的软件 计算机的软件主要分为系统软件和应用软件两类: ①系统软件:为了使用和管理计算机的软件,主要有操作系统软件如,WINDOWS 95/98/ 2000/ NT4.0、DOS 6.0、UNIX 等;WINDOWS 95/98/2000/NT4.0 是多任务可视化图形 界面,而 DOS 是字 符命令形式的单任务的操作系统。 ②应用软件:为了某个应用目的而编写的软件,主要有辅助教学软件(CAI)、辅助设计软件(CAD)、文 字处理软件、工具软件以及其他的应用软件。 2.计算机的工作原理 到目前为止,电子计算机的工作原理均采用冯.若依曼的存储程序方式,即把程序存储在计算机内,由计 算机自动存取指令(计算机可执行的命令=操作码+操作数)并执行它。工作原理图如下:

1.3 计算机中有关数及编码的知识 1.计算机是智能化的电器设备 计算机就其本身来说是一个电器设备,为了能够快速存储、处理、传递信息,其内部采用了 大量的电子元件,在这些电子元件中,电路的通和断、电压高低,这两种状态最容易实现, 也最稳定、也最容易实现对电路本身的控制。我们将计算机所能表示这样的状态,用 0,1 来 表示、即用二进制数表示计算机内部的所有运算和操作。 2.二进制数的运算法则 二进制数运算非常简单,计算机很容易实现,其主要法则是: 0+0=0 0+1=1 1+0=1 1+1=0 0*0=0 0*1=0 1*0=0 1*1=1

由于运算简单,电器元件容易实现,所以计算机内部都用二进制编码进行数据的传送和计算。 3.十进制与二进制、八进制、十六进制数之间的相互转换 (1)数的进制与基数 计数的进制不同,则它们的基数也不相同,如表 1-1 所示。 进制 二进制 八进制 十六进制 (2)数的权 不同进制的数,基数不同,每位上代表的值的大小(权)也不相同。 如:(219)10=2*10 +1*10 +9*10
4 3 2 2 1 0

基数 0 ,1 0,1,2,3,4,5,6,7 0,1,2,...,9,A,B,C,D,E,F

特点 逢二进一 逢八进一 逢十六进一

(11010)2=1*2 +1*2 +0*2 +1*2 +1*2 (273)8=2*8 +7*8 +3*8
2 1 0

1

0

(27AF)16=2*16 +7*16 +10*16 +15*16 (3)十进制数转换任意进制

3

2

1

0

1) 将十进制整数除以所定的进制数,取余逆序。 (39)10=(100111)2 (245)10=(365)8

2)将十进制小数的小数部分乘以进制数取整,作为转换后的小数部分,直到为零或精确到小数点后几 位。 如:(0.35)10=(0.01011)2 (4)任意进制的数转换十进制 按权值展开: 如:(219)10=2*10 +1*10 +9*10
4 3 2 2 1 0

(0.125)10=(0.001)2

(11010)2=1*2 +1*2 +0*2 +1*2 +1*2 =26 (273)8=2*8 +7*8 +3*8 =187 (7AF)16=7*16 +10*16 +15*16 =1867 4.定点数与浮点数 定点数是指数据中的小数点位置固定不变。由于它受到字长范围的限制,所能表示的数的范围有限,计 算结果容易溢出。 浮点数的形式可写成:N=M*2 (其中 M 代表尾数,E 代表阶码)其形式如下: 阶码 尾数(包括符号位)
E 2 1 0 2 1 0

1

0

5.ASCII 编码 由于计算机是电器设备,计算机内部用二进制数,这样对于从外部输入给计算机的所有信息必须用二进 制数表示,并且对于各种命令、字符等都需要转换二进制数,这样就牵涉到信息符号转换成二进制数所 采用的编码的问题,国际上统一用美国标准信息编码(ASCII)它可用 7 位二进制数表示,存储时用一 个字节,它的最高位为 0。因此基本的 ASCII 字符集有 128 个如: 0-9:48-57:00110000-...

A-Z:65-90 :01000001-... a-z:97-122:01100000-... 6.汉字编码与汉字输入法 (1)机内码 ASCII 码不能表示汉字,因此要有汉字信息交换码,我国国家标准是 gb2312,它也被称作国际码。它由 两个字节组成, 两个字节的最高位都为 1。 gb2312 共收纳 6763 个汉字, 其中, 一级汉字 (常用字) 3755 个按汉字拼音字母顺序排列,二级汉字 3008 个按部首笔画次序排列。 (2)汉字输入码(外码) 目前,汉字输入法主要有键盘输入、文字识别和语音识别。键盘输入法是当前汉字输入的主要方法。它 大体可以分为: 流水码:如区位码、电报码、通信密码,优点重码律少,缺点难于记忆; 音码:以汉语拼音为基准输入汉字,优点是容易掌握,但重码律高; 形码:根据汉字的字型进行编码,优点重码少,但不容易掌握; 音形码:将音码和形码结合起来,能减少重码律同时提高汉字输入速度。 (3)汉字字模 供计算机输出汉字(显示和打印)用的二进制信息叫汉字字形信息也称字模。通用汉字字模点阵规格有 16*16,24*24,32*32,48*48,64*64,每个点在存储器中用一个二进制位((bit)存储,如一个 16*16 点阵汉字需要 32 个字节的存储空间。 1.4 原码、反码与补码 在计算机中,数据是以补码的形式存储的: 在 n 位的机器数中,最高位为符号位,该位为零表示为正,为 1 表示为负; 其余 n-1 位为数值位,各位的值可为 0 或 1。 当真值为正时:原码、反码、补码数值位完全相同; 当真值为负时: 原码的数值位保持原样, 反码的数值位是原码数值位的各位取反, 补码则是反码的最低位加一。 注意符号位不变。 如:若机器数是 16 位: 十进制数 17 的原码、反码与补码均为: 0000000000010001

十进制数-17 的原码、反码与补码分别为:1000000000010001、1111111111101110、1111111111101111 1.5 逻辑运算 1.逻辑运算 逻辑与:同真则真 逻辑或:有真就真 逻辑非:你真我假 逻辑异或:不同则真 2.按位运算 按位与∩:同 1 则 1 如 10010101∩10110111=10010101 按位或∪:有 1 则 1 如 10010101∪10110111=10110111 3.逻辑化简 化简定律: (1)交换律: A + B = B + A ,A·B = B·A (2)结合律: (A + B)+ C = A + (B + C ), (A·B)·C = A·(B·C) (3)幂等律: A·A = A , A + A = A (4)吸收律: A·(A + B )= A , A +(A·B)= A (5)分配律: A·(B + C )= A·B + A·C , A +(B·C)=(A + B)·(A + C) (6)互补律: A + A = 1 ,A·A = 0 (7)非深入:A + B = A·B, A·B = A +B (8)0-1 律: A + 0 = A , A + 1 = 1 , A·1 = A , A·0 = 0 例:化简函数 Q = AD + AD + AB + ACEF。这个函数有 5 个自变量,化简过程如下: Q = AD + AD + AB + ACEF = A + AB + ACEF = A + ACEF = A 练习:求证:(A+B)(A+C)=AB+AC

第二节 操作系统
2.1 DOS 的组成 2.2 DOS 文件和目录 2.3 DOS 命令 2.4 Windows 简介 2.1 DOS(Disk Operating System)的组成 MS—DOS 采用模块结构,它由五部分组成:ROM 中的 BIOS 模块、IO.SYS 模块、 MSDOS.SYS 模块、COMMAND.COM 模块和引导程序。 (1)BIOS 模块:在 PC 机主板上有一个 ROM 芯片,该芯片中存有系统自测试程序, CMOS 设置程序和基本输入输出程序(BIOS)。BIOS 是一组程序和参 表,其中程序部份是可以通过中断方式调用的一组驱动程序,参数 给出外设的地址和参数。BIOS 是计算机硬件和操作系统之间的接口 通过它操作系统管理计算机硬件资源。 (2)IO.SYS 模块:IO.SYS 是 MS—DOS 和 ROMBIOS 之间的接口程序。它和 RON BIOS 一起完成系统设备的管理。 (3)MSDOS.SYS 模块: MSDOS.SYS 用于实现文件管理,包括文件管理、目录管理、 内存管理等功能。它以功能调用的形式实现用户和 MS—DOS 之间的程序级接口。 (4)COMMAND.COM 模块:COMMAND.COM 的主要功能是负责接收、识别、解释和执行 用户从键盘输入的 MS—DOS 命令。 (5)引导程序:引导程序又叫“引导记录”,其作用是检查当前盘上是否有两个系统文件,若有系统文 件则把 DOS 系统从磁盘装人内存。 一张系统盘上应该包含有:引导记录、IO.SYS、MSDOS.SYS 和 COMMAND.COM 等模块。 2.2 DOS 的文件和目录 1)文件概念:文件是指记录在存储介质(如磁盘、光盘)上的一组相关信息的集合。 2)文件标识:驱动器号+路径+文件名(1 到 8 各字符)+扩展名(1 到 3 个字符代表文件的类型) 3)通配符:*代表从该位置起的一个或多个合法字符;?代表所在位置的任一个合法字符。 4)树形目录:DOS 采用树形目录结构。由一个根目录和若干层子目录组成。这种目 录结构一是能够解决文件重名问题, 即不同的目录可以包含相同的文件名或目录名; 二是能够解决文件 多而根目录容量有限带来的问题。在查找某个子目录下的一个文件时,要使用目录路径。指定路径有两

种方法:绝对路径和相对路径。绝对路径是从根目录开始到文件所在目录的路径。例如要查找 UCDOS 子目录下的二级子目录 DATA 下的 README. TXT 文件, 绝对路径为: \UCDOS\DATA。 路径中第一个“\” 符号代表根目录。 相对路径是从当前目录开始到文件所在目录的路径。 当前目录指在不特意指定路径情 况下 DOS 命令所处理的目录。例如系统提示符为:“C:\UCDOS\DATA>”,则 DATA 是当前目录。 2.3 DOS 命令 1.内部命令 1)内部命令:当启动 DOS 系统时,计算机引导程序将系统以及常用的命令处理模块驻留 在计算机的内存中,我们称之为内部命令。 2)常用的内部命令: (1)目录命令: DIR(显示文件目录) MD、CD、RD(子目录的建立、进入、删除命令) (2)文件操作命令: COPY(复制命令)、DEL(删除命令)、REN(更改文件名) TYPE(显示文本文件内容) (3)其他内部命令 DATA、TIME、VER、CLS 等 3.外部命令 1)外部命令:存储在外存储器上的 DOS 可执行的文件,这些文件程序所占的存储容量比较 大,当用户使用外部命令时,计算机从外存调入内存,当执行完外部命令,就自动从内存中退出。 2)常用的外部命令 (1)磁盘格式化命令: FORMAT 盘符 [/S)I/V] 其作用,能够清除原盘中所有信息,并将磁盘规范成计算机所能接受的格式,以便有效存 储信息。 (2)软盘复制命令: DISKCOPY [盘符 1:][盘符 2:] ·

其作用,能够进行软盘之间的全盘复制(以磁道方式),不仅可以复制系统文件而且可以 复制隐含文件。 2.4 Windows 简介 Windows 是一个多任务图形用户界面,该环境可以在基于 MS-DOS 的计算机上运行,在多任务图形用户 环境下,Windows 提供了一个基于下拉菜单、屏幕窗口和鼠标的界面,在该环境下运行的应用程序必须

进行专门的设计才能发挥这些特征的优点。 2.Windows 的特点 Windows 能够充分发挥计算机的作用,其图形接口能够组织用户程序和文件、同时运行几个用户程序、 在文档之间移动和复制信息、在平台上进行应用程序的切换等。为了提高效率,Windows 还提供了一些 辅助程序,如字处理器、画笔及其他标准应用程序等。 Windows 具有以下主要特点。 (1)图形化的用户界面 Windows 提供了一种不同于 DOS 系统下命令行的工作方式,它通过对窗口、图标、选单、对话框、命令 按钮、滚动框等图形符号与画面的操作来实现对计算机的各种操作。 (2)标准化的操作界面 在 Windows 中,所有的操作都是通过窗口中的图形界面进行的。 (3)多任务机制和执行性能 在 Windows 中, 平稳的多任务机制可以同时运行多道程序以及执行多项任务, 各程序与各任务之间不仅 转换容易,而且还可以方便地交换数据。 (4)充分利用内存 Winddws 利用虚拟内存技术,允许应用程序超过 640 阳常规内存的运行空间,从而最大限度地利用了计 算机系统的所有内存资源,从而使内存较小的微机也能运行大型的应用程序。 (5)强大的联网功能 在 Windows 中,可以简单直观地实现网络的安装、配置、浏览,从而可以更加方便地实现网络管理和资 源共享。 (6)丰富的多媒体功能 Windows 提供大量辅助程序,用以实现文字、图形、图像、声音、视频等多媒体功能,同时还支持其他 厂商基于 Windows 标准开发的各种相应软件。 (7)TryType 技术 TryType(真实字体)属于内建式比例字体,可以任意平滑放大与缩小。这种字体能使屏幕上显示的效果 与实际打印机输出的信息完全一致,这就是所谓的“所见即所得”。 [例 4]在 Windows 95 中,“任务栏”的作用是____。 A)显示系统的所有功能 B)只显示当前活动窗口名 C)只显示正在后台工作的窗口名 D)实现窗口之间的切换

解答:在任务栏中,显示了所有打开的程序的图标。 本题正确答案为 D。

第三节 计算机网络常识
3.1 网络基础知识 3.2 Internet 简介 3.1 网络基础知识 1.网络的概念 计算机网络是将地理位置不同的计算机,用通信链路连接起来,共同遵守一定的协议,以实现计算机软硬 件资源共享为目标的通信系统。 2.网络的组成 计算机网络由网络硬件和网络软件组成。 网络软件包括网络操作系统、通信软件、通信协议(计算机之间实现数据通信共同遵守的相关规定)。 网络硬件包括网络的拓扑结构、网络服务器、网络工作站、传输介质和设备。 3.网络的分类 (1)按通信距离分: 局域网(LAN):局限于某个范围(10 公里左右)的网络连接情(校园网)。 广域网(WAN):跨地区的局域网,Internet 是覆盖全球的广域网。 (2)按网络的使用目的分: 共享资源网:使用者可分享网络的各种资源(如 Internet)。 数据处理网:用于数据处理(企业经营管理用的网络)。 数据传输网:用于数据的收集、交换和传输(情报检索网络)。 (3)按网络的拓扑结构分: 星形网:以一台计算机为中心,以放射状连接若干台计算机。 环形网:传输线路构成一个封闭的环,入网的计算机连到这个环形线路上。 总线网:用一条通信线路作主干,入网的计算机通过相应接口连到线路上。 4. 开放系统互联 模型 (OSI 模型) OSI 模型分 7 层:

各层功能如下: 1.物理层 物理层与移动二进制数和维护物理连接有关。 2.数据链路层 数据链路层通过帧在一个给定的物理链路传输分组(报文),保持帧的有序以及发现检测到的各种 错误,包括传输错误,但是数据链路层只了解在链路另一端的对等实体。数据链路层的地址是为了将网 络中一点的数据帧送到另一点。 3.网络层 网络层知道每个数据链路的对等进程,并负责在链路间移动分组,把它送到目的地。网络层地址是 为了把单一分组从网络的一端送到目的地。 4.传输层 传输层注意的是整个网络,该层是第一个端到端层。其对等实体位于分组的最终目的地。传输层依 靠网络层经过中间节点移动分组。 传输层地址是为了把网络一端进程的完整信息送到最终目的地的对等 进程。 5-7.会话层、表示层和应用层提供了如下功能: 处理计算机间数据表示的差别。 确保数据在网络传输中不被窃取和泄露,并且确保网络不允许未经授权就访问数据。 最高效地使用网络资源通过应用程序及活动同步来管理对话和活动。 在网络节点间共享数据。 3.2 Internet 简介 Internet 英文直译为“互联网”,中文名为“因特网”。是世界上众多计算机网络的集合起源于 20 世 纪 80 年代。

1.Internet 的 IP 地址、IP 地址类型和主机域名 (1) 在 Internet 网上采用统一的网络协议 TCP/IP,与 Internet 相连的计算机必须具有唯 一的主机地址,称 IP 地址。IP 地址采用分段地址方式,使用数字表示;如:207.46.130.14, 其中由三个点隔开的四个数是十进制,其大小是 0-255,每个数对应一个 8 位二进制数,所以 IP 地址用 32 位二进制位存放站 4 个字节。 (2)IP 地址类型:最初设计互联网络时,为了便于寻址以及层次化构造网络,每个 IP 地址包括两个标 识码(ID),即网络 ID 和主机 ID。同一个物理网络上的所有主机都使用同一个网络 ID,网络上的一个 主机(包括网络上工作站,服务器和路由器等)有一个主机 ID 与其对应。IP 地址根据网络 ID 的不同 分为 5 种类型,A 类地址、B 类地址、C 类地址、D 类地址和 E 类地址。 A 类 IP 地址 一个 A 类 IP 地址由 1 字节的网络地址和 3 字节主机地址组成, 网络地址的最高位必须是“0”, 地址 范围从 B 类 IP 地址 一个 B 类 IP 地址由 2 个字节的网络地址和 2 个字节的主机地址组成, 网络地址的最高位必须是“10”, 地址范围从 128.0.0.0 到 191.255.255.255。可用的 B 类网络有 16382 个,每个网络能容纳 6 万多个主 机 。 C 类 IP 地址 一个 C 类 IP 地址由 3 字节的网络地址和 1 字节的主机地址组成, 网络地址的最高位必须是“110”。 范 围从 192.0.0.0 到 223.255.255.255。C 类网络可达 209 万余个,每个网络能容纳 254 个主机。 D 类地址用于多点广播(Multicast)。 D 类 IP 地址第一个字节以“lll0”开始,它是一个专门保留的地址。它并不指向特定的网络,目前这 一类地址被用在多点广播(Multicast)中。多点广播地址用来一次寻址一组计算机,它标识共享同一 协议的一组计算机。 E 类 IP 地址 以“llll0”开始,为将来使用保留。 全零(“0.0.0.0”)地址对应于当前主机。全“1”的 IP 地址(“255.255.255.255”)是当前 子网的广播地址。 在 IP 地址 3 种主要类型里,各保留了 3 个区域作为私有地址,其地址范围如下: A 类地址:10.0.0.0~10.255.255.255 B 类地址:172.16.0.0~172.31.255.255 1.0.0.0 到 126.0.0.0。可用的 A 类网络有 126 个,每个网络能容纳 1 亿多个主机。

C 类地址:192.168.0.0~192.168.255.255 (3)为了使用方便,在访问 Internet 上的主机时,通常使用主机域名而不是 IP 地址,但主机域名和 IP 地址一一对应,它由圆点分隔的一序列单词组成如“Public.bta.net.cn"。 IP 地址如同电脑的身份证号码,而域名相当电脑的姓名。 2.Internet 的功能 (1)信息浏览(WWW) WWW(World Wide Web),中文名为”万维网“,是基于超文本的、方便用户信息浏览和信息 搜索的信息服务系统。用户在浏览器中输入网址即可得到需要的信息。人们常用的浏览器有 网景公司的 Netscape 浏览器和 Microsoft 公司的 Internet Explorer 浏览器。网址的输入是 使用协议提供的服务+服务器地址(IP 地址或主机域名)如 http://198.105.232.1; ftp://zsqz.com (2)文件传输(FTP) FTP(File Transfer Protocol)是 Internet 的一种标准协议,这一协议使用户能在联网的计算 机之间传送文件如上载(UPLOAD 把本地计算机上地文件复制到远程计算机上)和下载(DOWNLOAD 把远程计算机上的文件复制到本地计算机上)。 (3)传送电子邮件(E-mail) 电子邮件地址=用户名+@+主机域名;如:zhangming@yahoo.com (4)电子公告牌(BBS) (5)远程登录(telnet) (6)电子商务等 3.TCP/IP 参考模型 TCP/IP 协议的开发研制人员将 Internet 分为五个层次,以便于理解,它也称为互联网分层模型或互联 网分层参考模型,如下表: 应用层(第五层) 传输层(第四层) 互联网层(第三层) 网络接口层(第二层) 物理层(第一层) 各层简要说明如下:

物理层:对应于网络的基本硬件,这也是 Internet 物理构成,即我们可以看得见的硬件设备,如 PC 机、互连网服务器、网络设备等,必须对这些硬件设备的电气特性作一个规范,使这些设备都能够 互相连接并兼容使用。 网络接口层:它定义了将数据组成正确帧的规程和在网络中传输帧的规程,帧是指一串数据,它是 数据在网络中传输的单位。 互联网层: 本层定义了互联网中传输的“信息包”格式, 以及从一个用户通过一个或多个路由器到 最终目标的""信息包""转发机制。 传输层:为两个用户进程之间建立、管理和拆除可靠而又有效的端到端连接。 应用层:它定义了应用程序使用互联网的规程。

第四节 计算机信息安全基础知识
4.1 计算机网络安全 4.2 计算机病毒 4.1 计算机的网络安全 1、不同环境和应用中的网络安全 运行系统安全,即保证信息处理和传输系统的安全。它侧重于保证系统正常运行,避免因为系统的 崩溃和损坏而对系统存贮、处理和传输的信息造成破坏和损失,避免由于电磁泄漏,产生信息泄露,干 扰他人,受他人干扰。 网络上系统信息的安全。包括用户口令鉴别,用户存取权限控制,数据存取权限、方式控制,安全 审计,安全问题跟踪,计算机病毒防治,数据加密。 网络上信息传播安全,即信息传播后果的安全。包括信息过滤等。它侧重于防止和控制非法、有害 的信息进行传播后的后果。避免公用网络上大量自由传输的信息失控。 网络上信息内容的安全。它侧重于保护信息的保密性、真实性和完整性。避免攻击者利用系统的安 全漏洞进行窃听、冒充、诈骗等有损于合法用户的行为。本质上是保护用户的利益和隐私。 网络安全的特征 2、网络安全应具有以下四个方面的特征: 保密性:信息不泄露给非授权用户、实体或过程,或供其利用的特性。 完整性:数据未经授权不能进行改变的特性。即信息在存储或传输过程中保持不被修改、不被破坏 和丢失的特性。

可用性:可被授权实体访问并按需求使用的特性。即当需要时能否存取所需的信息。例如网络环境 下拒绝服务、破坏网络和有关系统的正常运行等都属于对可用性的攻击; 可控性:对信息的传播及内容具有控制能力。 3、主要的网络安全威胁 自然灾害、意外事故; 计算机犯罪; 人为行为,比如使用不当,安全意识差等; “黑客” 行为:由于黑客的入侵或侵扰,比如非法访问、拒绝服务计算机病毒、非法连接等; 内部泄密; 外部泄密; 信息丢失; 电子谍报,比如信息流量分析、信息窃取等; 信息战; 网络协议中的缺陷,例如 TCP/IP 协议的安全问题等等。 4、黑客常用的信息收集工具 信息收集是突破网络系统的第一步。黑客可以使用下面几种工具来收集所需信息: SNMP 协议,用来查阅非安全路由器的路由表,从而了解目标机构网络拓扑的内部细节。 TraceRoute 程序,得出到达目标主机所经过的网络数和路由器数。 Whois 协议,它是一种信息服务,能够提供有关所有 DNS 域和负责各个域的系统管理员数据。(不过这 些数据常常是过时的)。 DNS 服务器,可以访问主机的 IP 地址表和它们对应的主机名。 Finger 协议,能够提供特定主机上用户们的详细信息(注册名、电话号码、最后一次注册的时间等)。 Ping 实用程序,可以用来确定一个指定的主机的位置并确定其是否可达。把这个简单的工具用在扫描 程序中,可以 Ping 网络上每个可能的主机地址,从而可以构造出实际驻留在网络上的主机清单。 4.2 计算机病毒 计算机病毒是一种程序,是人为设计的具有破坏性的程序。 计算机病毒具有破坏性、传播性、可激发性、潜伏性、隐蔽性等特点。 3.病毒的分类 (1)按病毒设计者的意图和破坏性大小,可将计算机病毒分为良性病毒和恶性病毒。 ①良性病毒:这种病毒的目的不是为了破坏计算机系统,而只是为了编制者表现自己。此类病毒破

坏性较小,只是造成系统运行速度降低,干扰用户正常工作。 ②恶性病毒:这类病毒的目的是人为的破坏计算机系统的数据。具有明显破坏目标,其破坏和危害 性都很大,可能删除文件或对硬盘进行非法的格式化。 (2)计算机病毒按照寄生方式可以分为下列四类: ①源码病毒:在源程序被编译之前,就插入到用高级语言编写的源程序当中。编写这种病毒程序较 困难。但是,一旦插入,其破坏性和危害性都很大。 ②入侵病毒:是把病毒程序的一部分插入到主程序中。这种病毒程序也难编写,一旦入侵,难以清 除。 ②操作系统病毒:是把病毒程序加入或替代部分操作系统进行工作的病毒。这种病毒攻击力强、常 见、破坏性和危害性最大。 ④外壳病毒:是把病毒程序置放在主程序周围,一般不修改源程序的一种病毒。它大多是感染 DOS 下的可执行程序。这种病毒占一半以上,易编制,也易于检测和消除。 在日常维护中应隔离计算机病毒的来源,经常要用杀毒软件检查计算机系统和存储器。 例设一张软盘已染上病毒,能清除病毒的措施是____。 A)删除该软盘上的所有文件 B)格式化该软盘 C)删除该软盘上的所有可执行文件 D)删除该软盘上的所有批处理文件 解答:软盘染毒后,病毒隐藏在磁盘内部,并感染磁盘上的文件,而且可能通过磁盘的使用进而扩 散到其他磁盘, 造成更大的破坏。 为了清除病毒, 必须格式化软盘, 从而彻底清除染毒文件和病毒本身。 本题正确答案为 B。

第二部 Pascal 语言
Pascal 语言概述与预备知识
关于 Pascal 1、关于 Turbo Pascal Pascal 是一种计算机通用的高级程序设计语言。它由瑞士 Niklaus Wirth 教授于六十年代末设计 并创立。 以法国数学家命名的 Pascal 语言现已成为使用最广泛的基于 DOS 的语言之一,其主要特点有:严 格的结构化形式;丰富完备的数据类型;运行效率高;查错能力强。 正因为上述特点,Pascal 语言可以被方便地用于描述各种算法与数据结构。尤其是对于程序设计 的初学者,Pascal 语言有益于培养良好的程序设计风格和习惯。IOI(国际奥林匹克信息学竞赛)把 Pascal 语言作为三种程序设计语言之一, NOI(全国奥林匹克信息学竞赛)把 Pascal 语言定为唯一提倡 的程序设计语言,在大学中 Pascal 语言也常常被用作学习数据结构与算法的教学语言。 在 Pascal 问世以来的三十余年间,先后产生了适合于不同机型的各种各样版本。其中影响最大的 莫过于 Turbo Pascal 系列软件。它是由美国 Borland 公司设计、研制的一种适用于微机的 Pascal 编译 系统。该编译系统由 1983 年推出 1.0 版本发展到 1992 年推出的 7.0 版本,其版本不断更新,而功能更 趋完善。 下面列出 Turbo Pascal 的编年史: 年代 版本名称 1983 Turbo Pascal 1.0 Turbo Pascal 2.0 Turbo-87 Pascal 1985 Turbo Pascal 3.0 Turbo BCD Pascal 1987 Turbo Pascal 4.0 1988 Turbo Pascal 5.0 1989 Turbo Pascal 5.5 1990 Turbo Pascal 6.0 1992 Turbo Pascal 7.0 提高实数运算速度并扩大值域 增加图形功能 特别适合应用于商业 提供集成开发环境(IDE),引入单元概念 增加调试功能 支持面向对象的程序设计(OPP) 提供面向对象的应用框架和库(Turbo Vision) 面向对象的应用系统、更完善的 IDE 主要特色 Pascal 的启动

Turbo Vision 2.0 1993 Borland Pascal 7.0 开发 Object Windows 库 (For Windows) 1995 Delphi 提供对 OLE 多媒体应用开发的支持 Visual Pascal

Turbo Pascal 语言是编译型程序语言,它提供了一个集成环境的工作系统,集编辑、编译、运行、 调试等多功能于一体。 2. Pascal 的启动 Pascal 的启动 a.DOS 下的启动(适用于 MS-DOS6.22 之前的版本或 Win9X & Win2000 的 Command Mode) DOS 环境,在装有 Turbo Pascal 的文件目录下,键入 turbo 即可进入 Turbo Pascal 集成环境。 b.Win9X 或 Win2000 模式下的启动(适用于 Turbo Pascal 3.0 以后的版本) 如果在 Win9X 或 Win2000 的“资源管理器”装有 Turbo Pascal 的目录中, 双击 turbo.exe 或在“开 始--程序”菜单中通过 MS-DOS 方式来运行 turbo.exe, 它会提示你“该程序设置为 MS-DOS 方式下运行, 并且其它程序运行时,无法运行它。如果选择继续所有其它程序将关闭”,所以在 Win9X 或 Win2000 下无法直接运行它, 这时你可以在你希望的地方(比如说桌面上)单击鼠标右键“新建--快捷方式”, 单 击“浏览”,找到 turbo.exed 选中,然后单击“打开”,再单击“下一步”,再单击完成;这还没完, 选中前面新建的快捷方式(应该叫 Turbo Pascal 吧),单击右键,单击“属性”,选择“程序”,然后 再单击“高级”, 把“MS-DOS 方式”前面的那个勾去掉, 也就是不要选“MS-DOS 方式”, 然后单击“确 定”,再单击“确定”就大功告成了,以后你运行 Turbo Pascal 的时候,只要双击那个你建立起的快 捷方式就可以直接在 Win9X 或 Win2000 下运行 Turbo Pascal。

第一章 开始编写 pascal 语言程序
1.1 Pascal 编辑环境 1.2 简单的 Pascal 程序的结构 1.3 完整的的 Pascal 程序结构 1.1 Pascal 编辑环境 1.下载 Turbo Pascal6.0 (1)下载 turbo pascal (2)属性设置 2.Turbo Pascal 6.0 环境介绍 (1)进入与退出(注意:退出时必须使用文件菜单中的退出命令或 Alt+X) (2)编辑程序 光标移动键的使用 Backspace 键:删除光标前一个字符 Ctrl+N:在光标前插入一行 Ctrl+Y:删除光标所在行 Home:光标移到行首 End:光标移到行尾 PageUp/PageDown:上下翻页 Insert:插入与改写状态切换 (3)编译程序(Compile):Alt+F9 (4)运行程序(Run):Ctrl+F9 (5)保存程序(Save):F2 (6)打开原有的程序:F3 (7)查看程序运行结果:Alt+F5 (8)调试时增加观察项:Ctrl+F7 1.2 简单 Pascal 程序的结构 例 1 下列是一 Pascal 源程序: program lt1;{程序首部} var {说明部分}

a,b:integer;

sum:integer; begin a:=3355; b:=789; sum:=a+b; writeln('sum=',sum); end. 1.3 完整的 Pascal 程序结构 一个完全的 Pascal 程序结构 program 程序名; uses label const type var 已知单元说明; 标号说明; 常量说明; 类型说明; 变量说明; {执行部分}

function 函数说明; procedure 过程说明; begin 语句; 语句; ?? 语句; end.

作业:

1.熟悉 Pascal 编辑环境. 2.记住快捷键的使用. 3.编写 78*67 的值的 Pascal 程序并运行.

第二章 Pascal 语言基础知识
2.1 Pascal 的字符与符号 2.2 Pascal 数据类型 2.3 常量与变量 2.4 标准函数 2.5 运算符和表达式 练习与作业 2.1 Pascal 字符与符号 1.标识符 (1) 标识符的定义:标识符就是以字母开头的字母数字序列,有效长度为 63 个字符,并且大小写 等效。可以用来标示常量、变量、程序、函数等。例如例 1.1 中的 Area(程序名),pi(符号常量),s、 r(变量名)都是标识符。 (2) 标识符的分类: a.保留字(关键字) 所谓保留字是指在 Pascal 语言中具有特定的含义,你必须了解它的含义,以便于正确的使用,否 则会造成错误。 标准 Pascal 语言中的保留字一共有 35 个, Turbo Pascal 语言一共有 51 个。 下面是 Pascal 语言的保留字: AND,ARRAY,BEGIN,CASE,CONST,DIV,DO,DOWNTO,ELSE,END,FILE,FOR,FUNTION,GOTO, IF,IN,LABEL,MOD,NIL,NOT,OF,OR,PACKED,PROCEDURE,PROGRAM,RECORD,REPEAT,SET,THEN, TO,TYPE,UNTIL,VAR,WHILE,WITH 等 b.标准标识符:指 Pascal 语言预先定义的标识符,具有特殊含义。 以下列举了 Turbo Pascal 语言部分常用的标准表识符: 标准常量 False Maxint True Real Integer Cos Pred Eof Eoln Exp Sqr

标准类型 Boolean Char 标准函数 Abs Ln Sqrt

Arctan Chr Odd Succ Ord Trunc New

Round Sin

标准过程 Dispose Get Readln 标准文件 Input Reset Output

Pack

Page

Put

Read

Rewrite Unpack

Write Writeln

c.用户自定义标识符:由你自己根据需要来定义。 (1)选用的标识符不能和保留字相同。 (2)语法上允许预定义的标准标识符作为你自己定义的标识符使用,但最好还是不要用。 以下列举了你自己在定义标识符时可以用的字符: A——Z; a——z; 0——9; +, -, *, /, =, <>, <=, >=, <, >, (, ), [, ], {, }, :=, , , ; , ., : , .., ',^ 2.2 Pascal 数据类型 数据是程序设计的一个重要内容,其重要特征----数据类型,确定了该数据的形、取值范围以及所 能参与的运算。 Turbo Pascal 提供了丰富的数据类型,这些数据类型可以分为三大类:简单类型、构造类型和指 针类型,其中简单类型可以分为标准类型(整型、实型、字符型和布尔型)和自定义类型(枚举型和子 界型),构造类型可以分为数组类型、集合类型、记录类型和文件类型。这些数据类型中除了指针类型 是动态数据类型外,其他的都是静态数据类型。在这些数据类型中的简单类型都是有序类型,除了实型 以外的简单类型都是顺序类型,所谓顺序类型就是他们的值不仅是有序的而且是有顺序号。 在这里主要介绍整型、实型、字符型和布尔型四种常用的数据类型。 1.整型 一个整型数据用来存放整数。Turbo Pascal 支持五种预定义整型,它们是 shortint(短整型)、 integer(整型)、 longint(长整型)、 byte(字节型)和 word(字类型),Turbo Pascal 分别用 相同的名字作为他们的标识符。每一种类型规定了相应的整数取值范围以及所占用的内存字节数。 类型 shortint inteter 数值范围 -128..128 -32768..32767 占字节数 1 2 4 1 2 格式 带符号 8 位 带符号 16 位 带符号 32 位 带符号 8 位 带符号 16 位

longint -2147483648..2147483647 byte word 0..255 0..65535

Turbo Pascal 规定了两个预定义整型常量标识符 maxint 和 maxlonint,他们各表示确定的常数值, maxint 为 32767, longint 为 2147483647,他们的类型分别是 integer 和 longint 2.实型 一个实型数据用来存放实数。 Turbo Pascal 支持五种预定义实型, 它们是 real (基本实型) 、 single (但精度实型)、double(双精度实型)、extended(扩展实型)、comp(装配实型),Turbo Pascal

分别用相同的名字作为他们的标识符。 每一种类型规定了相应的实数取值范围、 所占用的内存字节数以 及它们所能达到的精度 类型 real single double 数值范围 2.9e-39..1.7e38 1.5e-45..3.4e38 5.0e-324..1.7e308 占字节数 有效位数 6 4 8 11..12 7..8 15..16

Turbo Pascal 支持两种用于执行实型运算的代码生成模式:软件仿真模式和 80x87 浮点模式。除 了 real 可以在软件仿真模式下直接运行以外,其他类型必须在 80x87 浮点模式下运行。 3.布尔型 一个布尔型数据用来存放逻辑值(布尔值)。布尔型的值只有两个:false 和 true,并且 false 的序号是 0,true 的序号是 1。false 和 true 都是预定义常数标识符,分别表示逻辑假和逻辑真。并 且 true<false。boolean 是布尔型的标识符。 4.字符型 字符型用 char 作为标识符。字符型必须用单引号括起来,字母作为字符型时,大小写是不等价的, 并且字符型只允许单引号中有一个字符,否则就是字符串。 2.3 常量与变量 1.常量 (1)常量:在某个程序的整个过程中其值不变的量。 (2)常量定义:常量定义出现在说明部分。它的语法格式是: const <常量标识符>=<常量>; ... <常量标识符>=<常量>; 常量标识符的类型由定义它的常量的类型决定。 例如: const a=12 隐含说明 a 是整型; const r=3.21 隐含说明 r 是实型...... (3)常量定义部分必须以保留字 const 开头,可以包含一个或几个常量定义,而且每个常量均以分 号结束。 (4)Turbo Pascal 类型常量 类型常量,又称变量常数,它是 Turbo Pascal 的一个扩充特性。类型常量的定义与标准 Pascal

规定的常数定义和变量说明有所区别。类型常量定义的语法格式: const <简单类型常量标识符>:简单类型=常数; 例如: const counter:integer=0; flag:boolean=true; index:0..100=0; 2.变量 (1)变量:在某个程序中的运行过程中其值可以发生改变的量 (2)变量说明:变量说明出现在说明部分。它的语法格式是: var <变量标识符列表>:<类型>; ... <变量标识符列表>:<类型>; 其中,保留字 var 表示开始一个变量说明部分。变量标识符列表是一个用逗号隔开的标识符序列, 冒号后面的类型是类型标识符。每个变量说明均以分号结束。 例如: var a,b,c:integer; m,n:real; 2.4 标准函数 1.算术函数 函数标识符 abs arctan cos exp frac int 自变量类型 整型、实型 整型、实型 整型、实型 整型、实型 整型、实型 整型、实型 意义 绝对值 反正切 余弦 指数 小数部分 整数部分 结果类型 同自变量 实型 实型 实型 实型 实型

ln pi sin sqr sqrt

整型、实型 无自变量 整型、实型 整型、实型 整型、实型

自然对数 圆周率 正弦 平方 平方根 abs(-7.49)=7.49 cos(pi)=-1.0

实型 实型 实型 同自变量 实型 arctan(0)=0.0 frac(-3.71)=-0.71 sqrt(4)=2

例:abs(-4)=4 sin(pi)=0.0

int(-3.71)=-3.0 sqr(4)=16 2.标准函数 函数标识符 odd pred succ 自变量类型 整型 离散类型 离散类型 意义 判断奇数 求前趋 求后继 pred(2000)=1999 pred('x')='w

结果类型 布尔型 同自变量 同自变量 succ(2000)=2001 succ('x')='y'

例:odd(1000)=false odd(3)=true 3.转换函数 函数标识符 chr ord round trunc 自变量类型 byte 离散类型 实型 实型

意义 自变量对应的字符 自变量对应的序号 四舍五入 截断取整

结果类型 字符型 longint longint longint trunc(2.88)=2

例:chr(66)='B' 4.杂类函数 函数标识符 random random randomize upcase downcase

ord('A')=65 round(-4.3)=-5

自变量类型 无自变量 word 无自变量 字符型 字符型

意义 [0,1 间的随机实数 [0,自变量间的随机整数)

结果类型 real word

初始化内部随机数产生器 longint 使小写英文字母变为大写 字符型 使小写英文字母变为大写 字符型

2.5

运算符和表达式 1.运算符和优先级 (1)运算符

是实型,如果全部的运算对象都是整型并且运算不是除法,则结果为整型,若运算是除法,则结果是实 型 a.算术运算符 运算符 + * / div mod 运算 加 减 乘 除 整除 取余 运算对象 整型、实型 整型、实型 整型、实型 整型、实型 整型 整型 结果类型 只要有一个运算对象是实型,结果就 是实型,如果全部的运算对象都是整 型并且运算不是除法,则结果为整型, 若运算是除法,则结果是实型。 整型 整型

b.逻辑运算符 运算符 not and or xor 运算 逻辑非 逻辑与 逻辑或 逻辑异或 运算对象 布尔型 布尔型 布尔型 布尔型 结果类型 布尔型 布尔型 布尔型 布尔型

c.关系运算符 运算符 = <> < > <= >= 运算 等于 不等于 小于 大于 小于等于 大于等于 运算对象 简单类型 简单类型 简单类型 简单类型 简单类型 简单类型 结果类型 布尔型 布尔型 布尔型 布尔型 布尔型 布尔型

(2)优先级 运算符 not *,/,div,mod,and 优先级 1(高) 2

xor,+,-,or in,=,<>,>=,<=,<> 2.表达式

3 4(低)

(1)算术表达式:算术表达式是由算术运算符连接常量、变量、函数的式子。算术表达式中各个运 算符的次序为: ( )-->函数-->*,/,div,mod-->+,1 (2)布尔表达式:Turbo Pascal 提供给布尔表达式以下基本操作:逻辑运算和关系运算。 (3)数学上的表达式与 pascal 语言表达式的区别

数学表达式 2a a÷b a≠b a≤b

PASCAL 表达式 2*a a/b a<>b a<=b

注意 *号不能省略 除号的写法 不等号的写法 小于等于号的写法

思考与练习:

1、熟记 Pascal 的保留字和标准标识符,明确自定义标识符的定义要点。 2、取整函数 int 与截断取整函数 trunc 有什么区别?举例说明。 3、判断以下标识符的合法性: a3 3a a17 abcd ex9.5 α β λ

5、将下列的数学表达式改写成 PASCAL 表达式: b^2-4ac 6、求下列表达式的值: 20 mod 19 (4>5) (8>9) 2 and 15 mod 9 (7<8) 7 div 8 19 div 3

or ( 9<10) ((3=3) or (3<7))

and

第三章 顺序结构程序设计
3.1 赋值语句 3.2 读语句 3.3 写语句 练习与作业 3.1 赋值语句 PASCAL 有两个语句可以改变变量的值。赋值语句是其中之一(另一个是读语句)。赋值,顾名思义, 就是把一个值赋予某个量。可以这理解:变量相当于装东西的容器,赋值的过程就是把东西放进容器的 过程。赋值语句格式如下: 变量:=表达式; 写赋值语句有以下几点要注意: 1、赋值号“:=” 赋值号由两个字符构成,是一个运算符。如果把这两个字符拆开,那么这两个字符就是别的意思 了:“:”是分隔符而“=”是关系运算符,判定两个对象是否相等。刚刚写程序的同学要特别注意这 一点。 例:a,b:integer;——是一个说明语句。“:”是变量表和变量类型的分隔符 a=b——是一个表达式。它的值是一个布尔类型的量:TRUE 或 FALSE a:=3;——是一个语句。把整型常量值 3 赋给整型变量 a 2、变量要先说明 在赋值号左边出现的变量,要在程序头的说明部先加以说明,否则编译时出错。

3、表达式必须要有确定的值 赋值号右边出现的表达式,必须是可以求值的。也就是说,经过运算之后,能得出一个具体的、确 定的值出来。 大家想一想, 如果连表达式自己都不知道自己的值是多少, 怎么还能把值“赋予”别人呢?

4、赋值号两边的数据类型必须相同或相容 我们知道,PASCAL 中的量不管是变量还是常量都有一个属性称为“数据类型”。数据类型相同的或相 容的才可以相互赋值。 怎么来理解这句话呢?打个比方,我们沏功夫茶用的是小茶杯,装饭时用饭碗。如果用饭碗来泡 功夫茶,用小茶杯来装饭,那情形一定很滑稽而且是不可行的。回到 PASCAL 中来,赋值号左边变量如

果是整型,右边表达式的值的类型也要是整型;赋值号左边变量如果是字符型,右边表达式的值的类型 也要是字符型??否则的话,也要出错了。这是数据类型相同的情况。 对于数据类型相容的,我们也可以用一个例子来帮助理解。我们都喝过功夫茶,也喝过大杯茶。把 功夫茶倒在大茶杯里, 一般不会出什么问题; 但如果把大杯里的茶倒在功夫茶杯里呢?可能小茶杯装不 下大茶杯里的茶,茶“溢出”了。在 PASCAL 中也会出现这种情况。当一种数据类型的取值范围包含着 另一种数据类型的取值范围时,就可能出现类型相容的情况。如实型与整型,整型、字符型与它们各自 的子界类型??如果把整型值赋给实型变量,把整型子界值赋给整型变量,不会出错;但如果反过来, 就会出现“溢出”,出错了。 因些,我们在写赋值语句时,要注意两边的类型是否匹配。 例:有程序如下: var a,b:integer;c:real;d:0..100; begin a:=100; b:=a; {-------------以上是相同数据类型进行赋值} d:=100; b:=d; c:=b; {-------------以上是相容数据类型进行赋值} d:=b; a:=c; {-------------以上两个赋值语句都出现溢出,编译时出错} end. 3.2 读语句

读语句(read 语句)和赋值语句一样,能够改变变量的值。与赋值语句不同,读语句从键盘或文件接 收值赋予变量,而赋值语句则直接由程序语句获得。读语句格式如下: read(变量名表); readln(变量名表); readln; 读语句是编程中用得最多的语句之一。在使用时有几点要注意:

1、变量名表。写在括号中的变量,都要在变量说明中先预以说明;变量与变量之间,以“,”分隔; 例: var a,b:integer; read(a,b); 2、从键盘接收数据时,要注意各种不同数据类型数据的分隔符不同。所谓分隔符就是两个完整的 数值之间的标记,也可以这样理解,当计算机从键盘读入数据时,一旦碰到分隔符,就认为当前的数据 读入已完成,可以把它赋给相应的变量了。各种数据类型的分隔符如下: 数值型(包括整型、实型以及它们的子界类型)以空格或回车符作为分隔符; 字符型不需分隔符(因为字符型数据的长度固定,只有一个); 字符串以回车符作为分隔符。

3、注意 read 与 readln 的区别 例:有两段程序有相同的变量说明如下,不同的读语句,我们可以通过比较它们执行结果的异同来 理解 read 与 readln 的区别。 变量说 var 明 a,b,c,d:integer; read(a); 程序段 readln(b,c); 一 read(d); readln(a); 程序段 read(b,c); 二 read(d) 输入数 1 2 3 4 5 据 6 7 8 1 6 7 8 1 2 3 6 a 执行结果 b c d

在程序段一执行时,“read(a);”语句接收了第一个数据 1 并将它赋给变量 a;接着执行第二个语 句“readln(b,c);”,接收了第一行数据中的 2、3 并把它们分别赋给变量 b,c,同时,把本行其它数 据全部屏蔽掉,也就是宣布它们全部作废。程序段二的执行情况也是如此。

因此,我们可以得出结论:语句 read 只管接收数据,语句 readln 接收完数据后,还把同行的其它 数据全部宣布作废。

4、“readln;”语句从键盘接收一个回车符。这个语句通常用在需要暂停的地方。如输出时用来等待程 序员看清结果。 3.3 写语句 写(write)语句是 Pascal 中唯一能将运算结果送出显示在显示器屏幕的语句。格式如下: write(输出量表);{输出后不换行} writeln(输出量表);{输出后换行} writeln;{输出一个回车符} 使用写语句时也有一些小问题需要注意。

1、输出量可以是: 变量。输出变量的值。输出多个变量时,变量间用“,”分隔。 表达式。输出的是表达式的值。 常量。直接输出常量值。

2、场宽的限制在输出不同格式的数值时的作用: 例 1:输出多个空格。 write('':n);句子的意思是以 n 个字符宽度输出冒号前数据项,如果数据项长度不足 n,则前面以空 格补齐;如果数据项长度大于 n,则以实际长度输出。如上语句句输出 n 个空格。 例 2:数据项间隔。 如输出最多四位的数据:write(x:5)。则数据间至少分隔一个空格。 例 3:实型数据小数位数的确定。 实型数据不带格式限制时,以科学计数法的形式输出,和我们的一般书写习惯不同。如果加上场宽的限 制,则可以有不同的效果: var a:real; begin a:=15/8; writeln(a);{输出 1.8750000000E+00}

wiiteln(a:0:2);{输出 1.88 整数部分按实际位数输出,小数部分保留两位小数,末位四舍五入.} writeln(a:0:0):{输出 2 只输出整数部分,小数部分四舍五入} end.

3、“writeln;”语句通常用于输出多组数据时在屏幕上输出空行来分隔数据组。

思考与练习:

1、 用字符输出一个猪锦佳的头像。 2、 a,b,c 分别等于 1、12、123,把它们按向左对齐、向右对齐的方式打印出来。 3、 输入一个四位整数,把它的各位数字倒序输出。(提示:用 MOD 和 DIV 运算完成) 4、 从键盘上读入小写的"pascal",利用 CHR()和 ORD()函数,输出大写的"PASCAL"。 5、 从键盘上读入一个实数,利用 ROUND()和 TRUNC()函数,输出该实数本身、整数部分、小数部 分、四舍五入后的值。 要求:分三行输出 ;输出实数本身时,格式与读入时相同;整数部分、小数部分在同一行输出;其它 各占一行。 6、 从键盘上读入长方形的边长 a,b,计算它的面积和周长,输出。 7、 输入一个时、分、秒,把它转换为一个秒数。

第四章 选择结构程序设计
4.1 IF 语句 4.2 CASE 语句 练习与作业 4.1 IF 语句 条件语句用于响应一个条件的两个方面。 例如:今天如果下雨,我们就在家;否则(不下雨)我们就去旅游。 又如:如果已经搜索得到结果,就打印出答案;否则(还没得到结果)就继续搜索。 IF 语句的一般格式是: IF 条件 THEN 语句 1{条件为真时的响应、处理} ELSE 语句 2;{条件为假时的响应、处理} 使用条件语句时要注意: 1、条件语句是一个语句。IF、THEN、ELSE 都是语句的一个部分。所以它只能有一个“;”作为 分隔符,放在句子的结束,特别要注意不能放在 ELSE 之前。 2、如果我们的程序只需对条件为真的情况作出处理,不需要处理条件为假的情况,则 IF 语句省略 ELSE 分句,格式变成: IF 条件 THEN 语句 1;{条件为真时的响应、处理} 如: 如果数 a 大于等于 0 则输出它的平方根。 if a>=0 then writeln(sqrt(a)); 对以上的例子,条件为假时不需处理,于是我们干脆省去 ELSE 分句。 3、if 语句可以多层嵌套。嵌套时为了避免误解,可以用 begin ,end 括起嵌套部分;else 分句一 般和最近的 if 分句配套: IF 条件 THEN BEGIN if 条件 1 then ?? else ??; END ELSE BEGIN

if 条件 2 then ?? else ??; end;

例 1、输入两个数 a,b,输出较大的数。 program tt; var a,b:integer; begin write('please input a,b:'); readln(a,b); if a>b then writeln(a) else writeln(b); end.

4.2 CASE 语句 分情况语句适用于对一个条件的多种情况的响应。 格式: case 表达式 of 标号 1:语句 1; 标号 2:语句 2; ?? 标号 n:语句 n; else 语句 n+1 end; case 语句在使用时有几点要注意: 1. end 与 case 对应;标号与语句之间用“:”分隔;else 与语句之间不用分隔符。 2. 标号必须是一常量,其类型与表达式的类型一致 例 2: 某全自动加油站 a,b,c 三种汽油的单价(元/kg)分别是 1.50、1.35 和 1.18,也提供了“自 己加”或“协助加”两个服务等级, 这样用户可以得到 5%或 10%的优惠。 编一个程序, 用户输入加油量、 汽油品种和服务类型(f-自动,m-自己,e-协助),然后计算应付款。 program pcase1;

var oil,help:char; kg,total:real; begin write('Enter the amount in kilograms(kg):'); readln(kg); write('Which type of the gasoline(a,b,c):'); readln(oil); wirte('Which type for service(f,m,e):'); readln(help); case oil of 'a': total:=1.50*kg; 'b': total:=1.35*kg; 'c': total:=1.18*kg; else writeln('Input Error!') end; {——————处理汽油的类型} case help of 'f':; 'm': total:=total*(1-0.05); 'e': total:=total*(1-0.10); else writeln('Input Error!') end; {——————处理服务类型} writeln; writeln('Total is ',total:10:2); end. 3. 可以多个标号对应同一条语句 4. 语句可以是多个语句,但必须用语句括号(begin??end)括起 5. case 语句也可以嵌套 例 3:从键盘上读入年和月,输出该月有多少天。 program pcase2; var

year,month,day:integer; runnian:boolean; begin write('Enter year and month:'); readln(year,month); case month of 1,3,5,7,8,10,12: day:=31; 4,6,9,11: day:=30;{————以上处理 31 天和 30 天的情况} 2:begin runnian:=(year mod 400=0) or ((year mod 4=0) and (year mod 100<>0)); case runnian of true: day:=28; false: day:=29; end; end; {————以上处理 2 月的情况:闰年 28 天,平年 29 天} end; end. 思考与练习: 1、从键盘上读入长方形的边长 a,b,计算它的面积和周长,输出。 2、 输入一个时、分、秒,把它转换为一个秒数。 3、 从键盘读入一个数,判断它的正负。是正数,则输出"+",是负数,则输出"-"。 4、 输入两个数 a,b,输出较大数的平方值。 5、 铁路托运行李规定:行李重不超过 50 公斤的,托运费按每公斤 0.15 元计费;如超 50 公斤, 超过部分每公斤加收 0.10 元。编一程序完成自动计费工作。 6、 某超市为了促销,规定:购物不足 50 元的按原价付款,超过 50 不足 100 的按九折付款,超过 100 元的,超过部分按八折付款。编一程序完成超市的自动计费的工作。 7、 输入 a,b,c 三个不同的数,将它们按由小到大的顺序输出。 13、 当前小学生的成绩单由以前 的百分制改为优秀、良好、合格、不合格四个等级的等级制。编一程序完成分数的自动转换工作。转换 规则如下:60 分以下的为不合格;60 到 69 分为合格;70 到 89 分为良好;90 分以上的为优秀。 (提示: 可以利用 DIV 运算来使程序更简明)

8、 打印某年某月有多少天。(提示:A、闰年的计算方法:年数能被 4 整除,并且不能被 100 整 除;或者能被 400 整除的整数年份。B、利用 MOD 运算可以判断一个数能否被另一个数整除) 9、编程模拟剪刀、石头、布游戏:用 S 表示剪刀,用 R 表示石头,用 P 表示布。规则是:剪刀剪 布,石头砸剪刀,布包石头。游戏者分别把自己的选择输入,计算机给出结果。

第五章 循环结构程序设计
5.1 For 语句 5.2 While 语句 5.3 Repeat-Until 语句 练习与作业 5.1 For 语句

1.递增型 FOR 循环。 FOR 循环控制变量:=循环初值 TO 循环终值 DO 循环的语句(或语段) 例: FOR I:=5 TO 10 DO WRITELN (I); 输出的结果为: 5 6 7 8 9 10 即循环一共执行了 6 次 如果要重复多个语句,一定要用 BEGIN-END 形式: 例: FOR I:=1 TO 10 DO BEGIN WRITELN (I); WRITELN (10-I); END; 2.递减型 FOR 循环 FOR 循环控制变量:=循环初值 DOWNTO 循环终值 DO 循环语句 递减型 FOR 循环与递增型 FOR 循环基本相同,只是循环控制变量每次递减。 3.FOR 循环的几点注意内容: (1)循环控制变量必须是顺序类型的变量。所谓顺序类型的变量,就是指整型,字符型,枚举型,子界 型,不允许是实型。

(2)不允许在循环体内再对循环控制变量赋值。 例如: A:=10;B:=50; FOR K:=A TO B DO BEGIN K:=K+1;{这一句是错误的!!!!!!!!} WRITELN (K); END; (3)当循环初值或循环终值中包含变量时,允许在循环体内改变这些变量的值,但并不改变原定的循环 次数。 例: A:=1;B:=10; FOR I:=A TO B DO BEGIN A:=5;B:=4; END; 在上面例子中,A,B 的值在循环的内部发生了变化,但并不影响循环的次数,依然是 10 次。 4.多重循环 循环体由 PASCAL 语句构成,当然也可以包含 FOR 语句,这就构成了循环的嵌套,形成多重 循环。 例如,以下 FOR 循环输出 5 行,每行输出 10 个星号(*) FOR i:=1 to 5 DO BEGIN FOR j:=1 TO 10 DO Write('*'); END; 初学者应当特别注意,内层的循环变量不能和外层的循环变量相同。也就是说,嵌套的各层循环应当使 用不同的变量作为循环变量。 5.2 While 语句 1.WHILE 循环的执行形式 WHILE 布尔表达式 DO 语句 例如:

k:=10; WHILE k>0 DO BEGIN Writeln (k); k:=k-1 END; 其中 (1)WHIlE 和 DO 是 PASCAL 保留关键字,是 WHILE 循环语句的组成部分。 (2)保留关键字 DO 后面的“语法”只能是一条语句, 称为“循环体”; 如果循环 体中需要包含多 个语句则应该如上例所示,采用一条复合语句。 2.WHILE 循环的执行功能 (1)求出布尔表达式的值 (2)若布尔表达式的值为真,则执行循环体内的语句;若为“假”,执行步骤 4 (3)重复步骤 1 和 2 (4)循环结束,执行循环后面的语句。 5.3 Repeat-Until 语句 1.REPEAT-UNTIL 类型的循环的执行形式 REPEAT 语句 1 语句 2 ?? 语句 n UNTIL 布尔表达式 例如:以下循环求 n=1+2+3+??+100 n:=0;t:=i; REPEAT n:=n+t; t:=t+1; UNTIL t>100; 其中 (1)REPEAT 和 UNTIL 是 PASCAL 保留关键字。 当执行到 WHILE 语句时

(2)在 REPEAT 和 UNTIL 之间的语句构成循环。在它们之间可以有任意多个语句,这一点和 FOR,WHILE 循环不同,FOR,WHILE 循环体在语法上只允许一条语句。 2.REPEAT-UNTIL 循环的执行功能 (1)遇到 REPEAT 语句后,即进入循环体,顺序执行循环体内的语句。 (2)遇到 UNTIL 语句后,求布尔表达式的值。若值为假,则返回步骤 1;若为“真”,执行步骤 3 (3)循环结束,执行 UNTIL 后面的下一条语句。 思考与练习: 1、计算下列式子的值: (1)1+2+??+100 (2)1+3+5+??+97+99 2、输入一个四位数,求它各位上数字的和。 3、求水仙花数。所谓水仙花数,是指一个三位数 abc,如果满足 a^3+b^3+c^3=abc,则 abc 是水仙花数。 4、宰相的麦子:相传古印度宰相达依尔,是国际象棋的发明者。有一次,国王因为他的贡献要奖励他, 问他想要什么。达依尔说:“只要在国际象棋棋盘上(共 64 格)摆上这么些麦子就行了:第一格一粒, 第二格两粒,??,后面一格的麦子总是前一格麦子数的两倍,摆满整个棋盘,我就感恩不尽了。”国 王一想,这还不容易,刚想答应,如果你这时在国王旁边站着,你会不会劝国王别答应,为什么? 5、打印下列图案:(输入 N 值来控制图案的规模,下列图案均以 N=3 为例) & & & & & & & & & & & & & & & * * * * * * * * * # # # @ @ @

#

#

#

@

@

@

6、输入一整数 A,判断它是否质数。(提示:若从 2 到 A 的平方根的范围内,没有一个数能整除 A, 则 A 是质数。) 7、求两个数的最小公倍数和最大公约数。(提示:公约数一定小于等于两数中的小数,且能整除两数 中的大数。公倍数一定大于等于两数中的大数,且是大数的倍数,又能给两数中的小数整除。) 8、编写一个译码程序,把一个英语句子译成数字代码。译码规则是以数字 1 代替字母 A,数字 2 代替 字母 B,??,26 代替字母 Z,如遇空格则打印一个星号‘*’,英文句子以‘.‘结束。 9、“百钱买百鸡”是我国古代的著名数学题。题目这样描述:3 文钱可以买 1 只公鸡,2 文钱可以买 一只母鸡,1 文钱可以买 3 只小鸡。用 100 文钱买 100 只鸡,那么各有公鸡、母鸡、小鸡多少只?与之 相似,有"鸡兔同笼"问题。 10、输入一个正整数 N,把它分解成质因子相乘的形式。 如:36=1 X 2 X 2 X 3 X 3; 19=1 X 19 (提示:设因子为 I,从 2 开始到 N,让 N 重复被 I 除,如果能整除,则用商取代 N,I 为一个因子; 如果不能整除,再将 I 增大,继续以上操作,直到 I 等于 N。)

第六章 数组与字符串
6.1 一维数组 6.2 二维数组 6.3 字符串 练习与作业 6.1 一维数组 1、定义: var a:array [1..10] of integer; 其中:a 是这一批数据的名称,称为数组名;array、of 是定义数组的保留字;中括号中的数字是 数据编号的下限和上限, 财时也说明了数据的个数 (上限-下限) ; 最后一个是数据的基类型, 如 integer, char,real,boolean。 2、数组元素的输入:

数组名代表的并不是一个变量,而是一批变量,因而,不能直接整个数组读入,而是要逐个数组元素读 入,通常用循环结构来完成这一功能。下面是几个常用输入数组元素的例子: for i:=1 to 10 do read(a[i]); {————从键盘读入数组元素的值;最常用的方法} for i:=1 to 10 do a[i]:=i; {————数组元素 a[1]到 a[10]的值分别为 1 到 10;数据赋初值} for i:=1 to 10 do a[i]:=0; {————数组元素清 0;最常用的数据初始化的方法} for i:=1 to 10 do a[i]:=random(100); {————随机产生 10 个 100 以内的数,赋给各数组元素} 3、数组元素的输出: 和数组元素的输入相同, 数组元素的输出也不能由一个 write 语句直接完成。 同样要逐个数组元素 输出。通常也用循环结构来完成这一功能: for i:=1 to 10 do write(a[i],' ');{————数组元素之间用空格分隔} writeln; 4、数组的应用: 例 1:从键盘输入 10 个数,将这 10 个数逆序输入,并求这 10 个数的和,输出这个和。 program p1; var a:array [1..10] of integer; i,s:integer; begin for i:=1 to 10 do read(a[i]); for i:=10 downto 1 do write(a[i],' '); writeln; s:=0; for i:=1 to 10 do s:=s+a[i]; writeln('s=',s); end. 例 2:用筛法求 100 以内的素数(质数)。

分析:素数是除了 1 和它本身以外没有其它约数的数。用筛法求素数的方法是:用质数筛去合数:从第 一个素数 2 开始, 把它的倍数去掉; 这样 2 以后的第一个非 0 数就一定也是素数, 把它的倍数也删了?? 重复这个删数过程,直到在所找到的素数后再也找不到一个非 0 数。把所有非 0 数输出。 program p2; var a:array [1..100] of integer; i,j,k:integer; begin for i:=1 to 100 do a[i]:=i; a[1]:=0;i:=2; while i<=100 do begin k:=i; while k<=100 do begin k:=k+i; a[k]:=0; end; {————上面将所有 a[i]的倍数清 0} i:=i+1; while a[i]=0 do i:=i+1; {————查找接下来的第一个非 0 数} end; for i:=1 to 100 do if a[i]<>0 then write(a[i],' '); end.

6.2 二维数组 一维数组在编程中多用于描述线性的关系: 如一组数; 一组成绩; 一组解答等。 数组元素只有一个下标, 表明该元素在数组中的位置。二维数组在编程中多数用于描述二维的关系:如地图、棋盘、城市街道、 迷宫等等。而二维数组元素有两个下标:第一个下标表示该元素在第几行,第二个下标表示在第几列。

1.二维数组的定义: var a:array[1..10,1..5] of integer; 其中:a 是数组名,由程序员自定;array 和 of 是定义数组的保留字;(这两点和一维数组定义 的格式一样)中括号中的两个范围表示二维数组共有多少行、多少列(第一个范围表示行数,第二个范 围表示列数);最后一个表示数组元素的类型,规定和一维数组一样。如上例,定义了一个二维数组 a, 共有 10 行 5 列。

2.使用二维数组: 1、数组元素的指称:数组名[行号,列号]。如第三行第四个元素:a[3,4]。 对某一行进行处理。如累加第 4 行的数据。则固定行号为 4。如:for i:=1 to 5 do s:=s+a[4,i]; 对某一列进行处理。如累加第 4 列的数据。则固定列号为 4。如:for i:=1 to 10 do s:=s+a[i,4];

2、二维数组的输入输出要用双重循环来控制: for i:=1 to 10 do{————控制行数} begin for j:=1 to 5 do read(a[i,j]){————第一行读入 5 个元素} readln;{————读入一个换行符} end; {————最常用的方法:从键盘读入数据初始化二维数组} for i:=1 to 10 do for j:=1 to 5 do a[i,j]:=0; {————最常用的方法:将二维数组清 0} for i:=1 to 10 do begin for j:=1 to 5 do write(a[i,j]:4); writeln; end; {————最常用的输出方法:按矩阵形式输出二维数组的值}

例 1:竞赛小组共有 20 位同学,这学期每位同学共参与了三项比赛,请统计每位同学的平均分。 分析:定义一个 20 行 3 列的二维数组来存放这些成绩。定义一个 20 个元素的一维数组来存放平均分。 program p1; var a:array [1..20,1..3] of integer; b:array [1..20] of real; i,j:integer; begin for i:=1 to 20 do begin for j:=1 to 3 do read(a[i,j]); readln; end; {————从键盘上读入 20 个同学的三次竞赛成绩} for i:=1 to 20 do b[i]:=0; {————先将平均分数组清 0} for i:=1 to 20 do begin for j:=1 to 3 do b[i]:=b[i]+a[i,j];{————计算总分} b[i]:=b[i]/3;{————计算平均分} end; for i:=1 to 20 do write(b[i]:5:1); {————输出平均分} writeln; end. 6.3 字符串 1. 字符串用于存放整批的字符数据。 通常编程中使用字符串存放字符化了的数字数据。 如高精度运

算时存放操作数和运算结果。字符串可以看作是特殊的字符串数组来处理。当然,它也有自已的特点。 下面是字符串定义的格式: var

s:string; s1:string[15]; 字符串定义时,如不指定长度,则按该类型的最大长度(255 个字符)分配空间,使用时最大可用长度 为 255 个;如果在中括号中给出一个具体的值(1—255 之间),则按这个值的大小分配空间。使用时, 最大的可用长度即为该值。

2.字符串的输入、输出: 字符串类型既可按数组方式输入、输出,也可直接输入、输出:readln(s);writeln(s);多个字符串 输入时以回车作为数据间的分隔符;每个 readln 语句只能读入一个字符串。 3.有关字符串的操作: 返 类 操作 型 值 函 求字符串 s 的长 整 length(s) 数度 函 复制 s 中从 w 开始 copy(s,w,k) 数的k位 串 var s:string;k,code:integer; 将字符串 s 转为 过 val(s,k,code) 程 code 是错误代码 val(s,k,code); write(k);{k=1234} i:=1234; 过 将数值 i 转为字 str(i,s) 程 符串 s write(s);{s='1234'} 在 s 中删除从第 w 过 Delete(s,w,k) 程 符 Insert(s1, S, w) 过 将 s1 插到 s 中第 Writeln(s); { 'Honest Lincoln' } S := 'Honest Lincoln'; 位开始的 k 个字 Delete(s,8,4); s := 'Honest Abe Lincoln'; str(i,s); 数值,存在 k 中; s:='1234'; begin 符 s1:=copy(s,3,5);{s1 的值是'34567'} 型 字 s:='123456789'; l:=length(s);{l 的值为 9} s:='123456789'; 作用 回 例子

程w位 函 求字符 c 在 s 中的 整 Pos(c, S) 数 位置 运 将两个字符串连 + 算 接起来 符 型

Insert('Abe ', S, 8); { 'Honest Abe Lincoln' } S := ' 123.5'; i :=Pos(' ', S);{i 的值为 1} s1:='1234'; s2:='5678'; s:=s1+s2;{'12345678'}

思考与练习: 1、随机产生 20 个 100 以内的数,输出;按从小到大的顺序排序,输出。 2、求一个 5 X 5 数阵中的马鞍数,输出它的位置。所谓马鞍数,是指在行上最小而在列上最大的数。 如下: 5 6 7 8 9 4 5 6 7 8 3 4 5 2 1 2 3 4 9 0 1 2 5 4 8 则 1 行 1 列上的数就是马鞍数。 3、做一个加法器。完成 30000 以内的加法,两个加数间用“+”连接,可以连加,回车表示式子输入完 成;“#”表示结束运算,退出加法器。

第七章 函数和过程
8.1 过程 8.2 函数 8.3 全局变量和局部变量 8.4 值参数和变量参数 练习与作业 8.1 过程 1.过程的定义 procedure 过程名(形式参数:参数说明);{也可以不带参数} var begin ... end; 2.过程的调用 过程名(实在参数表); 例 1:求 n 个自然数的最大公约数; program gcd1; const maxn=100; var n,i,gcd:integer; a:array[1..maxn] of integer; procedure enter; begin write('n=(<100)');readln(n); for i:=1 to n do repeat write('a[',i,']=');readln(a[i]); until a[i]>0; end; procedure find_gcd(x,y:integer);{定义过程} var r:integer;

begin r:=x mod y; while r<>0 do begin x:=y;y:=r;r:=x mod y; end gcd:=y; end;

procedure print; begin writeln('GCD=' ,gcd); end; begin enter; gcd:=a[1]; for i:=2 to n do find_gcd(gcd,a[i]); print; end. 8.2 函数 1.函数的定义 function 函数名(形参表):函数类型; { ————函数首部} var {————局部变量说明部分} begin {————函数体} ... {————函数语句} ... 函数名:=表达式 end; 2.函数的调用: 函数在语法上相当于一个表达式,所以,调用时,函数不能独立成为一个语句;它可以出现在任何表达 式可以出现的地方。

例如赋值语句的右边: X:=函数名(实在参数表); {————X 的类型与函数类型必须一致} 又,如果函数类型是 boolean,则还可以出现在条件语句中,充当条件表达式: if 函数名(实在参数表) then ?? 例 3:编一程序,求从 10 名同学中选出 3 名代表,有几种不同的选法。 (公式:C(m,n)=m!/n!*(m-n)!从 m 中选 n) program zohe1; var m,n:integer; c:longint; function factor(x:integer):longint;{定义} var i:integer; p:longint; begin p:=1; for i:=1 to x do p:=p*i; factor:=p;{这个语句必须} end; begin write('m,n=');readln(m,n); c:=factor(m) div (factor(n)*factor(m-n));{调用} writeln('c(',m,',',n,')=',c); end. 8.3 全局变量和局部变量 在子程序中定义的变量称为局部变量, 在程序的一开始定义的变量称为全局变量。 全局变量作用域 是整个程序;局部变量作用域是定义该变量的子程序。当全局变量与局部变量同名时:在定义局部变量 的子程序内,局部变量起作用;在其它地方全局变量起作用。 例 4:全局变量和局部变量。 program local_global; var i,k:integer; procedure sub1;

var i,j:integer; begin i:=17; writeln('i in sub=',i); writeln('k in sub=',k); end; begin i:=2;k:=9; writeln('i in main=',i); writeln('k in sub=',k); sub1; writeln('i in main=',i); writeln('j in main=',j); readln; end. 上述程序运行时将出现 Unknown Identfier;因为变量 j 在主程序中没定义。 当删除本语句时。运行结果如下: i in main=2 k in main=9 i in sub=17 k in sub=9 i in main=2 8. 4 值参和变量参数 值形参——传值:调用时可用表达式代替形参,不该变实在参数的值。 变量形参——传地址:调用时必须用变量代替行参变量,改变实在参数的值。 例 4:请看下列程序的运行结果。 program li3_10; var a,b,c:integer;

procedure sub(x,y:integer;var z:integer); begin

x:=x+1;y:=y+1;z:=x+y; writeln('sub:x=',x:2,'y=',y:2,'z=',z:2); end; begin a:=1;b:=4;c:=9; writeln('main:a=',a:2,'b=',b:2,'c=',c); sub(a,b,c); writeln('main:a=',a:2,'b=',b:2,'c=',c); sub(c+5,b*b,a); writeln('main:a=',a:2,'b=',b:2,'c=',c); readln; end. main:a=1 b=4 c=9 sub:x=2 y=5 z=7 main:a=1 b=4 c=7 sub:x=13 y=17 z=30 main:a=30 b=4 c=7 练习与作业 1、 试编写一个将阿拉伯数字转换为中文大写数字的函数。 (如中文状态不方便, 可以替换为 ABCDEFGHIJ) 2、输入一个长字符串和一个短字符串以及一个合适的整数,通过程序从指定位置用指定短字符串替换 长字符串中的内容(要求编写过程来实现),最后输出新字符串。

第八章 子界与枚举类型
8.1 子界类型 8.2 枚举类型 Pascal 有丰富的数据类型,在程序设计中有特殊而方便的应用。 类型定义的语法格式: type <标识符 1>=<类型 1>; <标识符 2>=<类型 2>; ?? <标识符 n>=<类型 n>; 8.1 子界与枚举 1.子界类型: 当某些变量的取值范围很具体时,可用子界类型,它更符合实际、便于查错和节省内存。 定义如下: type riqi=1..31; zimu='A'..'Z'; var day:riqi; ch1:zimu; 也可以直接定义: day:1..31; year:0..200; ch1:'A'..'Z'; 8.2 枚举类型: 通过预定义列出所有值的标识符来定义一个有序集合, 这些值的次序和枚举类型说明中的标识符的次序 是一致的。枚举类型的形式: (标识符 1,??,标识符 n) 例如: type daystype=(sunday,monday,tuesday,wednesday,thursday,friday,saturday) 枚举元素只能是标识符,而不能是数值常量或字符常量。例如以下的定义是错误的:< type daystype=('sun','mon','tue','wed','thu','fri','sat')

枚举元素是标识符,不要把作为枚举元素的标识符视作变量名,它不能被赋值。同一个枚举元素不 能出现在两个或两个以上的枚举类型定义中。例如以下的定义是错误的: type daytype1=(monday,tuesday); daytype2=(monday,wednesday); 可以将枚举类型的定义和变量的定义结合在一起。例如:var a:(monday,tuesday,sunday) 枚举类型属于顺序类型。 根据定义类型时各枚举元素的排列顺序确定它们的序列, 序列号从 0 开始。 例如:已经定义 daystype ord(sunday)=0,succ(sunday)=monday,pred(friday)=thursday 但是枚举类型中的第一个元素没有前趋,最后一个元素没有后继。Turbo Pascal 不允许直接读写 枚举值,所以枚举值的输出常用 case 语句间接的输出。枚举值的输入,则要一一判断读入字符是否是 枚举类型的标识符。若是才能赋给枚举变量,否则就会出错。 例如:枚举值的输出 case day of sunday:write('sunday'); monday:write('monday'); tuesday:write('tuesday'); wednesday:write('wednesday'); thursday:write('thursday'); friday:write('friday'); saturday:write('saturday'); end; 练习: 1.按月、日顺序输入今年的一个日期,输出该日是星期几?已知今年元旦是星期一。

第九章 集合类型
9.1 集合 9.1 集合 1.集合的定义: type 类型名=set of 基类型 例如: type num=set of char; var n:num; 或 var n: set of char; 2.集合的表示: 用一组方括号括号一组元素来表示,元素之间用逗号分隔。如: [A,B,C,D]--有四个枚举量的集合 ['A','B','C','D']--有四个字符的集合 [1..20]--包含了 1 到 20 中所有整数的集合 [0]--只有一个元素 0 的单元素集 []--空集 3.集合的运算: (1)并(a+b):属于 a 或属于 b [0..7]+[0..4]的值为[0..7] (2)交(a*b):既属于 a 又属于 b [0..7]*[0..4]的值为[0..4] (3)差(a-b):属于 a 但不属于 b [0..7]-[0..4]的值为[5..7] (4)相等(a=b):a,b 的元素完全一样 [0..7]=[0..4]的值为 false (5)不等(<>):元素不一样

[0..7]<>[0..4]的值为 true (6)包含于(<=): [0..7]<=[0..4]的值为 false (7)包含(>=): [0..7]>=[0..4]的值为 true (8)成员(in): 1 in [0..4]的值为 true 4.注意事项: (1)集合运算相当快,在程序中常用集合表达式来描述复杂的测试。如 A)条件表达式: (ch='T') or (ch='t') or (ch='Y') or (ch='y') 可用集合表达式表示 为: ch in ['T','t','Y','y'] B)if (ch>=20) and (ch<=50) then ...; 可写成: if ch in [20..50] then ...; (2)集合类型是一种使用简便,节省内存面又运算速度快的数据类型。 (3)Turbo Pascal 规定集合的元素个数不超过 256 个(当实际问题所需的元素个数大于 256 时, 可采 用布尔数组代替集合类型)。所以如下定义是错误的: var i: set of integer; (4)集合类型变量不能进行算术运算,了不允许用读/写语句直接输入/输出集合。 所以集合的建立: A)要通过赋值语句实现; B)或先初始化一个集合,然后通过并运算向集合中逐步加入各个元素. (5)集合元素是无序的,所以 ord,pred 和 succ 函数不能用于集合类型的变量。 练习: 编程读入两个字符串,然后输出如下信息: (1)出现在某一个字符串中至少一次的字母和数字; (2)同时出现在两个字符串中至少一次的字母和数字; (3)出现在一个字符串中而不出现在另一个字符串中的字母和数字; (4)不出现在任何字符串中的字母和数字。

第十章 记录与文件类型
10.1 记录类型 10.2 文件类型

10.1 记录 1.记录的定义: type 类型标识符=record 字段名 1:类型 1; 字段名 2:类型 2; ... 字段名 n:类型 n; end; 如: type studata=record num:string[6]; name:string[8]; sex:boolean; s:array[1..5] of real; end; var student:studata; students:array[1..10] of studata; 2.记录的运用: (1)对记录中和个域的引用,要写出记录名和域名,如:student.num (2)开域语句:with。 with 记录名 do 语句; 或 with 记录名 1,记录名 2,... do 语句; 注意:

1. 在 do 后面语句中使用的记录的域时,只要简单地写出域名就可以了, 域名前的记录变量和 "."均可省略。 2. 在关键字 with 后面,语句可以是一个简单语句,了可以是一个复合语句。 3. 虽然在 with 后可以有多个记录变量名,但一般在 with 后只使用一个记录变量名。 10.2 文件 文件是一种构造型的数据类型。在程序中都需要产生一些输出,也需要接受若干个输入。这些输入、输 出实际上是用文件的方法来实现的, 在 Pascal 中用标准文件“input”和“output”来实现, 它们分别 对应标准输入设备和标准输出设备(可省略不写)这也就是一些程序的程序书写如下的原因了: program ex(input,output); ... 但有时大量数据的读入和输出都是来是磁盘文件,这就要求我们必须熟练掌握对磁盘文件的操作。 对于我们来说,我们只必须掌握文本文件(或称正文文件,text)的读写即可: 1.文本文件的定义: 文本文件不是简单地由某类型的元素序列所组成,它的基本元素是字符,由它们构成行,若干行 组成一份原文。由于各行的长度可以不同,所以文本文件只能顺序地处理。文本文件的定义如下: var fp:text; 2.文本文件的读操作: (1)调用 assign 过程,把磁盘文件赋予文本文件变量; assign(fp,filename); (2)调用 reset 过程,为读操作做准备; reset(fp); (3)在需要读数据的位置调用 read 过程或 readln 过程。 readln(fp,var1,var2,...,varn); 3.文本文件的写操作: (1)调用 assign 过程,把磁盘文件赋予文本文件变量; assign(fp,filename); (2)调用 rewrite 过程,为读操作做准备; rewrite(fp); (3)在需要读数据的位置调用 write 过程或 writeln 过程。

writeln(fp,var1,var2,...,varn); 4.文本文件的关闭操作: close(fp); 5.文本文件的其他操作: (1)EOF(fp)—布尔函数,用于判断文件结束否。 (2)EOLN(fp)—布尔函数,用于判断行结束否。 例 1:下面是一个建立和使用文件的程序: program wenjian; const n=3; m=2; type student=record name:string; score:array[1..m] of 0..100; end; var st:array[1..n] of student; stfile:file of student ; sumst:array[1..n] of integer; sumsub:array[1..m] of integer; sum:integer; procedure newfile; var i,j:integer; begin assign(stfile,'score.fil'); rewrite(stfile); for i:=1 to n do begin writeln('Input student ',i,' name and ',m,' score'); readln(st[i].name) ; for j:=1 to m do read(st[i].score[j]); readln;

write(stfile,st[i]); end; close(stfile); writeln ; writeln; end; procedure jisuan; var i,j:integer; begin assign(stfile,'score.fil'); reset(stfile); for i:=1 to m do sumsub[i]:=0; for i:=1 to n do begin read(stfile,st[i]); with st[i] do begin sumst[i]:=0; for j:=1 to m do begin sumst[i]:=sumst[i]+score[j]; sumsub[j]:=sumsub[j]+score[j]; end; end; end; close(stfile); sum:=0; for i:=1 to n do sum:=sum+sumst[i]; for i:=1 to n do

begin with st[i] do begin write(name); for j:=1 to m do write(score[j]:6); end; writeln(sumst[i]:6); end; write('sum='); for i:=1 to m do write(sumsub[i]:6); writeln(sum:8); end; begin newfile; jisuan; end. 练习: 编写程序从磁盘上读取一个由 100 个实数组成的实型数据文件(indata.dat), 以此文件中所有大于平均 值的实数建立一个名为“above.dat”的文件,其余的建立一个名为“rest.dat”的文件。

第十一章 指针类型
11.1 指针 11.2 单链表 11.1 指针 指针是通过地址来访问变量的一种特殊的数据类型,属于动态的数据结构,它可以在需要时产生,用完 后则又可以取消或回收, 以减少占用的内存空间。 指针变量与其他类型的变量不同, 它占有的不是数据, 而是地址。 由于动态数据结构的变量是在程序执行过程中动态生成的, 所以不能预先予以说明, 无法预先给这 些变量起名字,访问时也无法通过名字直接输出或显示,而只能用指针得到其地址,然后间接访问。 1、定义指针类型 在 Turbo Pascal 中,指针变量用来存放某个存储单元的地址,即指针变量指向某个存储单元。一 个指针变量仅能指向某一种类型的存储单元, 这种数据类型是在指针类型的定义中确定的, 称为指针类 型的基类型。指针类型定义如下: 类型名=^基类型名; 例如:type q=^integer; var a,b,c:q; 说明:q 是一指向整型存储单元的指针类型,其中"^"为指针符。a,b,c 均定义为指针变量,分别可 以指向一个整型存储单元。 上例也可用变量说明为: var a,b,c:^integer; 指针也可以指向有结构的存储单元。 例如:type person=record name:string[10]; sex:(male,female); age:20..70 end; var pt:^person; pt 为指向记录类型 person 的指针变量。 2、动态变量 应用一个指针指向的动态存储单元即动态变量的形式如下:

指针变量名^ 例如:p^、q^、r^ 指针变量 p 和它所指向的动态变量 p^之间有如下关系:

以下语句把整数 5 存放到 p 所指向的动态变量 p^中去: p^:=5; 以下语句把 p 所指向的 p^中的值赋给整型变量 i: i:=p^; 如果指针变量 p 并未指向任何存储单元,则可用下列赋值语句: p:=nil; 其中 nil 是保留字,表示“空”,相当于 C 语言里面的 null 3、对动态变量的操作 在 Turob Pascal 程序中,动态变量不能由 var 直接定义而是通过调用标准过程 new 建立的。过程 形式为: new(指针变量名); 如果有下列变量定义语句: var p:^integer; 仅仅说明了 p 是一个指向整型变量单元的指针变量, 但这个整型单元并不存在, 在指针变量 p 中还 没有具体的地址值。在程序中必须通过过程调用语句:new(p);才在内存中分配了一个整型变量单元, 并把这个单元的地址放在变量 p 中, 一个指针变量只能存放一个地址。 在同一时间内一个指针只能指向 一个变量单元。当程序再次执行 new(p)时,又在内存中新建立了一个整型变量单元,并把新单元的地 址存放在 p 中,从而丢失了旧的变量单元的地址。 为了节省内存空间,对于一些已经不使用的现有动态变量,应该使用标准过程 dispose 予以释放。 过程形式为:dispose(指针变量名);为 new(指针变量名)的逆过程,其作用是释放由指针变量所指向 的动态变量的存储单元。 例如在用了 new(p)后在调用 dispose(p), 则指针 p 所指向的动态变量被撤销, 内存空间还给系统,这时 p 的值为 nil。 4.需要注意之处 1、P 与 P^的区别 P 是指向该动态变量的指针变量名,P^则称为动态变量或标志变量。P 的值是 P^的首地址,P^的值

为与基类型相同的一个值。 2、定义后及时分配存储单元 定义了一个指针变量后,并没有为该指针分配动态存储单元,此时的 P 的值无定义,调用 P^则会 产生运行错误。若想使该指针可用,可以对指针赋值,也可以通过 NEW()过程分配存储单元。 3、使用后及时收回存储单元 指针使用后,不会自动归还占用的存储空间,应及时使用 DISPOSE()过程来释放 P^所占用的存储 单元,以免浪费有限的存储空间. 11.2 单链表 单链表的数据类型可定义如下: type dlb=^node; node=record data:datatype; next:dlb; end; 例 1 连续输入一序列整数,组成链表 (并以动态的形式把它们记录下来) ,当输入的数为-1 时,停止输入, 然后把输入的整数按相反的顺序输出. program lianbiao; type link=^data; data=record num:integer; next:link; end; var p,q:link; i:integer; begin q:=nil; readln(i); while i<>-1 do begin

new(p); with p^ do begin num:=i; next:=q; end; q:=p; readln(i); end; while p<>nil do begin write(p^.num:6); p:=p^.next; end; readln; end. 练习:将例 1 中如果数据不按现反的顺序(按输入时的顺序)输出时,怎样建表.(程序) 上述建表方式其实就是分别从表头和表尾插入元素,下面是从表中插入元素; 例 2:输入若干整数(输入 32767 停止输入)排序(小到大)输出之。 program lianbiao; type link=^data; data=record num:integer; next:link; end; var head,p,q,r:link; i:integer; begin head:=nil; readln(i);

while i<>32767 do begin new(p); p^.num:=i; p^.next:=nil; if head=nil then begin head:=p;end else begin q:=head; if p^.num<q^.num then begin head:=p;p^.next:=q end else begin while (p^.num >=q^.num) and (q<>nil) do begin r:=q ;q:=q^.next;end; if q=nil then r^.next:=p else begin r^.next:=p;p^.next:=q end end; end; readln(i); end; p:=head; while p<>nil do begin write(p^.num:6); p:=p^.next; end; readln; end. 练习:建立一个若干整数的链表后(-1 结束) 再从链表中删除从键盘上输入一个整数的所有结点.(程序)

第十二章 程序调试
12.1 单步执行 12.2 断点法 12.1 单步执行 任何一个天才都不敢说,他编的程序是 100%正确的。几乎每一个稍微复杂一点的程序都必须经过反复 的调试,修改,最终才完成。所以说,程序的调试是编程中的一项重要技术。我们现在就来掌握一下基 本的程序调试。 我们以下的示范,是以时下比较流行的 Borland Pascal 7.0 为例子,其他的编程环境 可能略有不同,但大致上是一致的。

我们先编一个比较简单的程序,看看程序是如何调试的。 program tiaoshi; var i:integer; begin for i:=1 to 300 do begin if i mod 2 = 0 then if i mod 3 = 0 then if i mod 5 = 0 then writeln(i);

end; end. 该程序是输出 300 以内同时能被 2,3,5 整除的整数。 现在我们开始调试。 调试有多种方法, 先介绍一种,权且叫步骤法,步骤法就是模拟计算机的运算,把程序每一步执行的情况都反映出来。通 常,我们有 F8 即 STEP 这个功能来实现,如图: 不断地按 F8,计算机就会一步步地执行程序,直到执 行到最后的“end.”为止。

可能你还没有发现 F8 的威力, 我们不妨把上面的程序略微修改一下, 再配合另外的一种调试的利 器 watch,你就会发现步骤法的用处。 program tiaoshi; var i:integer; a,b,c:boolean; begin for i:=1 to 300 do begin a:=false; b:=false; c:=false; if i mod 2 = 0 then a:=true;

if i mod 3 = 0 then b:=true; if i mod 5 = 0 then c:=true; if a and b and c then writeln(i); end; end. 如图,我们单击菜单栏中 debug 选项,里面有一项叫 watch 的选项,我们单击它。

就会出现一个 watch 窗口:

watch 窗口可以让我们观察变量的变化情况,具体操作是在 watches 窗口内按 Insert 键:

这时,屏幕上弹出一个菜单,我们输入所需要观察的变量名,我们分别输入 i,a,b,c 这 4 个变量 名,于是 watches 窗口内就有如下的 4 个变量的状态:

这时,我们再次使用步骤法,我们会发现,这 4 个变量的状态随着程序的执行而不断变化,比如:

这样我们就可以方便地知道执行每一步之后,程序的各个变量的变化情况,从中我们可以知道我 们的程序是否出错,在哪里出错,方便我们及时地修改。 下一次,我们介绍另外的一种方法,断点法。 12.2 断点发 在前面我们已经学习了基本的程序调试方法——步骤法。 步骤法有一个缺点, 就是在遇到循环次数比较 多或者语句比较多的时候, 用起来比较费时, 今天我们来学习一种新的也是常用的调试方法——断点法。 所谓断点法,就是在程序执行到某一行的时候,计算机自动停止运行,并保留这时各变量的状态,

方便我们检查,校对。我们还是以前面求同时能被 2,3,5 整除的 3000 以内的自然数为例,具体操作 如下: 我们把光标移动到程序的第 14 行,按下 ctrl+F8,这时我们会发现,该行变成红色,这表明该行 已经被设置成断点行,当我们每次运行到第 14 行的时候,计算机都会自动停下来供我们调试。

我们必须学以致用,赶快运用刚学的 watch 方法,看看这家伙到底有多厉害。

请记住,计算机是执行到断点行之前的一行,断点行并没有执行,所以这时 b:=true 这一句并没有 执行。 断点行除了有以上用处之外, 还有另外一个重要用处。 它方便我们判断某个语句有没有执行或者是

不是在正确的时刻执行, 因为有时程序由于人为的疏忽, 可能在循环或者递归时出现我们无法预料的混 乱,这时候通过断点法,我们就能够判断程序是不是依照我们预期的顺序执行。

第三部 常用算法与策略
第一章 算法
1.1 什么是算法 1.2 算法的表示方法 1.3 算法分析 1.1 什么是算法 算法是程序设计的精髓,程序设计的实质就是构造解决问题的算法,将其解释为计算机语言。

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程。
在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法。前者是推理实现的算法,后 者是操作实现的算法。 一个算法应该具有以下五个重要的特征: 1. 有穷性: 一个算法必须保证执行有限步之后结束; 2. 确切性: 算法的每一步骤必须有确切的定义; 3. 输入:一个算法有 0 个或多个输入,以刻画运算对象的初始情况; 4. 输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无 意义的; 5. 可行性: 算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。 1.2 算法的表示方法 算法通常有三种表示方法:自然语言法、程序流程图法、程序法。 结构化程序设计三种程序结构的流程图(N-S 图)如下: 1.顺序结构

2.选择结构

3.循环结构

当型循环

直到型循环

例题 1:百钱买百鸡问题:

1.3 算法分析 算法的复杂性

算法的复杂性是算法效率的度量, 是评价算法优劣的重要依据。 一个算法的复杂性的高低体现在运行该
算法所需要的计算机资源的多少上面,所需的资源越多,我们就说该算法的复杂性越高;反之,所需的 资源越低,则该算法的复杂性越低。 计算机的资源,最重要的是时间和空间(即存储器)资源。因而,算法的复杂性有时间复杂性和空间复

杂性之分。
不言而喻, 对于任意给定的问题, 设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目 标;另一方面,当给定的问题已有多种算法时,选择其中复杂性最低者,是我们在选用算法适应遵循的 一个重要准则。因此,算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。 简言之,在算法学习过程中,我们必须首先学会对算法的分析,以确定或判断算法的优劣。 1.时间复杂性: 例 1:设一程序段如下(为讨论方便,每行前加一行号) (1) for i:=1 to n do (2) for j:=1 to n do (3) x:=x+1 ......

试问在程序运行中各步执行的次数各为多少? 解答: 行号 次数(频度) (1) (2) (3) n+1 n*(n+1) n*n 可见,这段程序总的执行次数是:f(n)=2n +2n+1。在这里,n 可以表示问题的规模,当 n 趋向无穷 大时,如果 f(n)的值很小,则算法优。作为初学者,我们可以用 f(n)的数量级 O 来粗略地判断算法
2 2

的时间复杂性,如上例中的时间复杂性可粗略地表示为 T(n)=O(n )。 2.空间复杂性: 例 2:将一一维数组的数据(n 个)逆序存放到原数组中,下面是实现该问题的两种算法: 算法 1:for i:=1 to n do b[i]:=a[n-i+1]; for i:=1 to n do a[i]:=b[i]; 算法 2:for i:=1 to n div 2 do begin t:=a[i];a[i]:=a[n-i-1];a[n-i-1]:=t end; 算法 1 的时间复杂度为 2n,空间复杂度为 2n 算法 2 的时间复杂度为 3*n/2,空间复杂度为 n+1 显然算法 2 比算法 1 优,这两种算法的空间复杂度可粗略地表示为 S(n)=O(n) 信息学比赛中,经常是:只要不超过内存,尽可能用空间换时间。

第二章 递归
2.1 递归的概念 2.2 如何设计递归算法 2.3 典型例题

递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写
程序能是程序变得简洁和清晰. 2.1 递归的概念

1.概念 一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数). 如: procedure a; begin . . . a; . . . end; 这种方式是直接调用. 又如: procedure begin . . . c; . b; . b; procedure c;

begin . . .

. . end; 这种方式是间接调用. 例 1 计算 n!可用递归公式如下: 1 当 n=0 时 fac(n)={n*fac(n-1) 当 n>0 时 可编写程序如下: program fac2; var n:integer; function fac(n:integer):real; begin end;

. .

if n=0 then fac:=1 else fac:=n*fac(n-1) end; begin write('n=');readln(n); writeln('fac(',n,')=',fac(n):6:0); end.

例 2 楼梯有 n 阶台阶,上楼可以一步上 1 阶,也可以一步上 2 阶,编一程序计算共有多少种不同的走法. 设 n 阶台阶的走法数为 f(n) 显然有 1 f(n)={
2 n=2

n=1

f(n-1)+f(n-2) n>2 可编程序如下: program louti; var n:integer; function f(x:integer):integer;

begin if x=1 then f:=1 else if x=2 then f:=2 else f:=f(x-1)+f(x-2); end; begin write('n=');read(n); writeln('f(',n,')=',f(n)) end. 2.2 如何设计递归算法 1.确定递归公式 2.确定边界(终了)条件 练习: 用递归的方法完成下列问题 1.求数组中的最大数 2.1+2+3+...+n 3.求 n 个整数的积 4.求 n 个整数的平均值 5.求 n 个自然数的最大公约数与最小公倍数 6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问 n 个月后共有多少对兔子? 7.已知:数列 1,1,2,4,7,13,24,44,...求数列的第 n 项. 2.3 典型例题 例 3 梵塔问题 如图:已知有三根针分别用 1,2,3 表示,在一号针中从小放 n 个盘子,现要求把所有的盘子 从 1 针全部移到 3 针,移动规则是:使用 2 针作为过度针,每次只移动一块盘子,且每根针上 不能出现大盘压小盘.找出移动次数最小的方案.

程序如下: program fanta; var n:integer;

procedure move(n,a,b,c:integer); begin if n=1 then writeln(a,'--->',c) else begin move(n-1,a,c,b); writeln(a,'--->',c); move(n-1,b,a,c); end; end; begin write('Enter n='); read(n); move(n,1,2,3); end. 例 4 快速排序 快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或 左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为 1, 处理结束. 程序如下: program kspv; const n=7; type arr=array[1..n] of integer; var a:arr; i:integer; procedure quicksort(var b:arr; s,t:integer); var i,j,x,t1:integer; begin i:=s;j:=t;x:=b[i]; repeat

while (b[j]>=x) and (j>i) do j:=j-1; if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end; while (b[i]<=x) and (i<j) do i:=i+1; if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end until i=j; b[i]:=x; i:=i+1;j:=j-1; if s<j then quicksort(b,s,j); if i<t then quicksort(b,i,t); end; begin write('input data:'); for i:=1 to n do read(a[i]); writeln; quicksort(a,1,n); write('output data:'); for i:=1 to n do write(a[i]:6); writeln; end. 练习: 1.计算 ackerman 函数值: n+1 ack(m,n)={ ack(m-1,1) m=0 m<>0 ,n=0

ack(m-1,ack(m,n-1)) m<>0,n<>0 求 ack(5,4)

第三章 回溯
3.1 回溯的设计 3.2 回溯算法的递归实现

回溯是按照某种条件往前试探搜索,若前进中遭到失败,则回过头来另择通路继续搜索.
3.1 回溯的设计 1.用栈保存好前进中的某些状态. 2.制定好约束条件 例 1 由键盘上输入任意 n 个符号;输出它的全排列. program hh; const n=4; var i,k:integer; x:array[1..n] of integer; st:string[n]; t:string[n]; procedure input; var i:integer; begin write('Enter string=');readln(st); t:=st; end; function place(k:integer):boolean; var i:integer; begin place:=true; for i:=1 to k-1 do if x[i]=x[k] then

begin place:=false; break end ; end; procedure print; var i:integer;

begin for i:=1 to n do write(t[x[i]]); writeln; end; begin input; k:=1;x[k]:=0; while k>0 do begin x[k]:=x[k]+1; while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1; if x[k]>n then k:=k-1 else if k=n then print else begin k:=k+1;x[k]:=0 end end ; end. 例 2.n 个皇后问题: program hh; const n=8; var i,j,k:integer; x:array[1..n] of integer; function place(k:integer):boolean; var i:integer; begin place:=true; for i:=1 to k-1 do if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then place:=false ; end; procedure print;

var i:integer; begin for i:=1 to n do write(x[i]:4); writeln; end; begin k:=1;x[k]:=0; while k>0 do begin x[k]:=x[k]+1; while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1; if x[k]>n then k:=k-1 else if k=n then print else begin k:=k+1;x[k]:=0 end end ; end. 回溯算法的公式如下:

3.2 回溯算法的递归实现 由于回溯算法用一栈数组实现的,用到栈一般可用递归实现。 上述例 1 的递归方法实现如下:

program hh; const n=4; var i,k:integer; x:array[1..n] of integer; st:string[n]; t:string[n]; procedure input; var i:integer; begin write('Enter string=');readln(st); t:=st; end; function place(k:integer):boolean; var i:integer; begin place:=true; for i:=1 to k-1 do if x[i]=x[k] then begin place:=false; break end ; end; procedure print; var i:integer; begin for i:=1 to n do write(t[x[i]]); writeln;readln; end; procedure try(k:integer); var i :integer; begin if k=n+1 then begin print;exit end;

for i:=1 to n do begin x[k]:=i; if place(k) then try(k+1) end end; begin input; try(1); end. 例 2:n 皇后问题的递归算法如下: 程序 1: program hh; const n=8; var i,j,k:integer; x:array[1..n] of integer; function place(k:integer):boolean; var i:integer; begin place:=true; for i:=1 to k-1 do if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then place:=false ; end; procedure print; var i:integer; begin for i:=1 to n do write(x[i]:4); writeln; end;

procedure try(k:integer); var i:integer; begin if k=n+1 then begin print; exit end; for i:= 1 to n do begin x[k]:=i; if place(k) then try(k+1); end; end ; begin try(1); end. 程序 2: 说明:当 n=8 时有 30 条对角线分别用了 l 和 r 数组控制, 用 c 数组控制列.当(i,j)点放好皇后后相应的对角线和列都为 false.递归程序如下: program nhh; const n=8; var s,i:integer; a:array[1..n] of byte; c:array[1..n] of boolean; l:array[1-n..n-1] of boolean; r:array[2..2*n] of boolean; procedure output; var i:integer; begin for i:=1 to n do write(a[i]:4); inc(s);writeln(' total=',s); end; procedure try(i:integer);

var j:integer; begin for j:=1 to n do begin if c[j] and l[i-j] and r[i+j] then begin a[i]:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false; if i<n then try(i+1) else output; c[j]:=true;l[i-j]:=true;r[i+j]:=true; end; end; end; begin for i:=1 to n do c[i]:=true; for i:=1-n to n-1 do l[i]:=true; for i:=2 to 2*n do r[i]:=true; s:=0;try(1); writeln; end.

练习: 1.找出所有从 m 个元素中选取 n(n<=m)元素的组合。 2.设有 A,B,C,D,E 5 人从事 j1,j2,j3,j4,j5 5 项工作每人只能从事一项,它们的 效益表如下: j1 j2 j3 j4 j5 A 13 11 10 4 B 13 10 10 8 C 5 9 7 7 7 5 4

D 15 12 10 11 5 E 10 11 8 8 4

求最佳安排,使效益最高. 3.N 个数中找出 M 个数(从键盘上输入正整数 N,M 后再输入 N 个正数),要求从 N 个数中 找出若干个数,使它们的和为 M,把满足条件的数组找出来,并统计组数. 4.地图着色。如下图 12 个区域用 4 种颜色着色要求相邻的区域着不同的颜色

5.将任意一正整数(1<n<100)分解成若干正整数的和. 如:4=1+1+1+1 =2+1+1 =2+2 =3+1.

第四章 排序
4.1 简单排序 4.2 快速排序 4.3 希尔排序 4.4 堆排序与二叉树排序 4.5 归并排序 4.6 线形时间排序 4.7 各种算法排序的比较

排序就是将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程。
4.1 简单排序 1.选择排序 选择排序的基本思想是: 对待排序的记录序列进行 n-1 遍的处理, 第 1 遍处理是将 L[1..n]中最小者与 L[1]交换位置, 第 2 遍处 理是将 L[2..n]中最小者与 L[2]交换位置, ......, 第 i 遍处理是将 L[i..n]中最小者与 L[i]交换位置。 这样,经过 i 遍处理之后,前 i 个记录的位置就已经按从小到大的顺序排列好了。 例 1:输入序列数据按非减顺序输出. 程序如下: program xzpx; const n=7; var a:array[1..n] of integer; i,j,k,t:integer; begin write('Enter date:'); for i:= 1 to n do read(a[i]); writeln; for i:=1 to n-1 do begin k:=i; for j:=i+1 to n do if a[j]<a[k] then k:=j;

if k<>i then begin t:=a[i];a[i]:=a[k];a[k]:=t;end; end; write('output data:'); for i:= 1 to n do write(a[i]:6); writeln; end. 2.插入排序 插入排序的基本思想:经过 i-1 遍处理后,L[1..i-1]己排好序。第 i 遍处理仅将 L[i]插入 L[1..i-1]的 适当位置 p,原来 p 后的元素一一向右移动一个位置,使得 L[1..i]又是排好序的序列。 例 2:输入序列数据按非减顺序输出. 程序 1: program crpx; const n=7; var a:array[1..n] of integer; i,j,k,t:integer; begin write('Enter date:'); for i:= 1 to n do read(a[i]); writeln; for i:=2 to n do begin k:=a[i];j:=i-1; while (k<a[j]) and (j>0) do begin a[j+1]:=a[j];j:=j-1 end; a[j+1]:=k; end; write('output data:'); for i:= 1 to n do write(a[i]:6);

writeln; end. 3.冒泡排序 冒泡排序又称交换排序其基本思想是:对待排序的记录的关键字进行两两比较,如发现两个 记录是反序的,则进行交换,直到无反序的记录为止。 例:输入序列数据按非减顺序输出。 程序 1: program mppx; const n=7; var a:array[1..n] of integer; i,j,k,t:integer; begin write('Enter date:'); for i:= 1 to n do read(a[i]); for i:=1 to n -1 do for j:=n downto i+1 do if a[j-1]<a[j] then begin t:=a[j-1];a[j-1]:=a[j];a[j]:=t end; write('output data:'); for i:= 1 to n do write(a[i]:6); writeln; end. 程序 2: program mppx; const n=7; var a:array[1..n] of integer; i,j,k,t:integer; bool:boolean; begin write('Enter date:');

for i:= 1 to n do read(a[i]); i:=1;bool:=true; while (i<n) and bool do begin bool:=false; for j:=n downto i+1 do if a[j-1]<a[j] then begin t:=a[j-1];a[j-1]:=a[j];a[j]:=t;bool:=true end; i:=i+1; end; write('output data:'); for i:= 1 to n do write(a[i]:6); writeln; end.

程序 3: program mppx; const n=7; var a:array[1..n] of integer; i,j,k,t:integer; begin write('Enter date:'); for i:= 1 to n do read(a[i]); writeln; k:=n; while k>0 do begin j:=k-1;k:=0; for i:=1 to j do if a[i]>a[i+1] then

begin t:=a[i];a[i]:=a[i+1];a[i+1]:=t;k:=i;end; end; write('output data:'); for i:= 1 to n do write(a[i]:6); writeln; end. 返回 4.2 快速排序 快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或 左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为 1, 处理结束. 例:输入一组数据小到大排序. 程序 1: program kspv; const n=7; type arr=array[1..n] of integer; var a:arr; i:integer; procedure quicksort(var b:arr; s,t:integer); var i,j,x,t1:integer; begin i:=s;j:=t;x:=b[i]; repeat while (b[j]>=x) and (j>i) do j:=j-1; if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end; while (b[i]<=x) and (i<j) do i:=i+1; if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end until i=j; b[i]:=x;

i:=i+1;j:=j-1; if s<j then quicksort(b,s,j); if i<t then quicksort(b,i,t); end; begin write('input data:'); for i:=1 to n do read(a[i]); writeln; quicksort(a,1,n); write('output data:'); for i:=1 to n do write(a[i]:6); writeln; end.

程序 2: program kspv; const n=7; type arr=array[1..n] of integer; var a:arr; i:integer; procedure quicksort(var b:arr; s,t:integer); var i,j,x:integer; begin i:=s;j:=t;x:=b[i]; repeat while (b[j]>=x) and (j>i) do j:=j-1; if j>i then begin b[i]:=b[j];i:=i+1;end; while (b[i]<=x) and (i<j) do i:=i+1;

if i<j then begin b[j]:=b[i];j:=j-1; end until i=j; b[i]:=x; i:=i+1;j:=j-1; if s<j then quicksort(b,s,j); if i<t then quicksort(b,i,t); end; begin write('input data:'); for i:=1 to n do read(a[i]); writeln; quicksort(a,1,n); write('output data:'); for i:=1 to n do write(a[i]:6); writeln; end. 返回 4.3 希尔排序 基本思想:将整个无序序列分割成若干小的子序列分别进行插入排序或冒泡排序。 序列分割方法:将相隔某个增量 h 的元素构成一个子序列。在排序过程中,逐次减小这个增量,最后当 h 减到 1 时,进行一次插入排序或冒泡排序,排序就完成。增量序列一般采用:d1=n div 2 ,di=di-1 div 2 ;i=2,3,4.....其中 n 为待排序序列的长度。 程序 1:(子序列是插入排序) program xepx; const n=7; type arr=array[1..n] of integer; var a:arr; i,j,t,d:integer;

bool:boolean; begin write('input data:'); for i:=1 to n do read(a[i]); writeln; d:=n; while d>1 do begin d:=d div 2; for j:=d+1 to n do begin t:=a[j];i:=j-d; while (i>0) and (a[i]>t) do begin a[i+d]:=a[i];i:=i-d;end; a[i+d]:=t; end; end; write('output data:'); for i:=1 to n do write(a[i]:6); writeln; end. 程序 2:(子序列是冒泡排序) program xepx; const n=7; type arr=array[1..n] of integer; var a:arr; i,temp,d:integer; bool:boolean;

begin write('input data:'); for i:=1 to n do read(a[i]); writeln; d:=n while d>1 do begin d:=d div 2; repeat bool:=true; for i:=1 to n-d do if a[i]>a[i+d] then begin temp:=a[i];a[i]:=a[i+d];a[i+d]:=temp; bool:=false end; until bool; end; write('output data:'); for i:=1 to n do write(a[i]:6); writeln; end. 返回 4.4 堆排序与二叉树排序 1.堆排序 堆:设有数据元素的集合(R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有 Ri<=R2i 和 Ri<=R2i+1(或>=) 堆的性质:堆的根结点上的元素是堆中的最小元素,且堆的每一条路径上的元素都是有序的。 堆排序的思想是: 1)建初始堆(将结点[n/2],[ n/2]-1,...3,2,1 分别调成堆) 2)当未排序完时 输出堆顶元素,删除堆顶元素,将剩余的元素重新建堆。 程序如下:

program duipx; const n=8; type arr=array[1..n] of integer; var a:arr;i:integer; procedure sift(var a:arr;l,m:integer); var i,j, t:integer; begin i:=l;j:=2*i;t:=a[i]; while j<=m do begin if (j<m) and (a[j]>a[j+1]) then j:=j+1; if t>a[j] then begin a[i]:=a[j];i:=j;j:=2*i; end else exit; a[i]:=t; end; end; begin for i:=1 to n do read(a[i]); for i:=(n div 2) downto 1 do sift(a,i,n); for i:=n downto 2 do begin write(a[1]:4); a[1]:=a[i]; sift(a,1,i-1); end; writeln(a[1]:4); end. 2.二叉树排序

排序二叉树: 每一个参加排列的数据对应二叉树的一个结点, 且任一结点如果有左 (右) 子树, 则左 (右) 子树各结点的数据必须小(大)于该结点的数据。中序遍历排序二叉树即得排序结果。程序如下: program pxtree; const a:array[1..8] of integer=(10,18,3,8,12,2,7,3); type point=^nod; nod=record w:integer; right,left:point ; end; var root,first:point;k:boolean;i:integer; procedure hyt(d:integer;var p:point); begin if p=nil then begin new(p); with p^ do begin w:=d;right:=nil;left:=nil end; if k then begin root:=p; k:=false end; end else with p^ do if d>=w then hyt(d,right) else hyt(d,left); end; procedure hyt1(p:point); begin with p^ do begin if left<>nil then hyt1(left); write(w:4); if right<>nil then hyt1(right); end end;

begin first:=nil;k:=true; for i:=1 to 8 do hyt(a[i],first); hyt1(root);writeln; end. 返回 4.5 归并排序

归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并
(merge).归并排序就是 n 长度为 1 的子序列,两两归并最后变为有序的序列。 1.二路归并 例 1:将有序表 L1=(1,5,7),L2=(2,3,4,6,8,9,10)合并一个有序表 L. program gb; const m=3;n=7; type arrl1=array[1..m] of integer; arrl2=array[1..n] of integer; arrl=array[1..m+n] of integer; var a:arrl1; b:arrl2; c:arrl; i,j,k,r:integer; begin write('Enter l1(sorted):'); for i:=1 to m do read(a[i]); write('Enter l2(sorted):'); for i:=1 to n do read(b[i]); i:=1;j:=1;k:=0; while (i<=m) and (j<=n) do begin k:=k+1; if a[i]<=b[j] then begin c[k]:=a[i];i:=i+1; end

else begin c[k]:=b[j];j:=j+1;end; end; if i<=m then for r:=i to m do c[m+r]:=a[r]; if j<=n then for r:=j to n do c[n+r]:=b[r]; writeln('Output data:'); for i:=1 to m+n do write(c[i]:5); writeln; end. 2.归并排序 program gbpx; const maxn=7; type arr=array[1..maxn] of integer; var a,b,c:arr; i:integer; procedure merge(r:arr;l,m,n:integer;var r2:arr); var i,j,k,p:integer; begin i:=l;j:=m+1;k:=l-1; while (i<=m)and (j<=n) do begin k:=k+1; if r[i]<=r[j] then begin r2[k]:=r[i];i:=i+1 end else begin r2[k]:=r[j];j:=j+1 end end; if i<=m then for p:=i to m do begin k:=k+1;r2[k]:=r[p] end; if j<=n then for p:=j to n do begin k:=k+1;r2[k]:=r[p] end; end; procedure mergesort( var r,r1:arr;s,t:integer);

var k:integer; c:arr; begin if s=t then r1[s]:=r[s] else begin k:=(s+t) div 2; mergesort(r,c,s,k); mergesort(r,c,k+1,t); merge(c,s,k,t,r1) end; end; begin write('Enter data:'); for i:= 1 to maxn do read(a[i]); mergesort(a,b,1,maxn); for i:=1 to maxn do write(b[i]:9); writeln; end. 返回 4.6 线形排序 以上我们讨论的算法均是基于比较的排序算法,在排序算法中有基于数字本身的算法:计数、桶、基数 排序。 1.计数排序 基本思想是对于序列中的每一元素 x,确定序列中小于 x 的元素的个数。 例:n 个整数序列且每个值在[1,m],排序之。 program jspx; const m=6;n=8; var i,j:integer; a,b:array[1..n] of integer;

c:array[1..m] of integer; begin writeln('Enter data:'); for i:=1 to n do read(a[i]); for i:=1 to m do c[i]:=0; for i:=1 to n do c[a[i]]:=c[a[i]]+1; for i:=2 to m do c[i]:=c[i]+c[i-1]; for i:=n downto 1 do begin b[c[a[i]]]:=a[i]; c[a[i]]:=c[a[i]]-1; end; writeln('Sorted data:'); for i:= 1 to n do write(b[i]:6); end. 2.桶排序 桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个 桶装入一个值,顺序输出各桶的值,将得到有序的序列。 例:输入 n 个 0 到 100 之间的整数,由小到大排序输出。 program tpx; const n=7; var b:array[0..100] of integer; k:0..100; i:integer; begin write('Enter date:(0-100)'); for i:=0 to 100 do b[i]:=0; for i:= 1 to n do begin

read(k); b[k]:=b[k]+1; end; writeln('Output data:'); for i:=0 to 100 do while b[i]>0 do begin write(i:6);b[i]:=b[i]-1 end; writeln; end. 3.基数排序 基本思想是对 n 个元素依次按 k,k-1,...1 位上的数字进行桶排序。 program jspx; const n=8; type link=^node; node=record data:integer; next:link; end; var i,j,l,m,k:integer; a:array[1..n] of integer; s:string; q,head:array[0..9] of link; p,p1:link; begin writeln('Enter data:'); for i:=1 to n do read(a[i]); for i:=5 downto 1 do begin for j:=0 to 9 do begin new(head[j]);

head[j]^.next:=nil; q[j]:=head[j] end; for j:=1 to n do begin str(a[j],s); for k:=1 to 5-length(s) do s:='0'+ s; m:=ord(s[i])-48; new(p); p^.data:=a[j]; p^.next:=nil; q[m]^.next:=p; q[m]:=p; end; l:=0; for j:=0 to 9 do begin p:=head[j]; while p^.next<>nil do begin l:=l+1;p1:=p;p:=p^.next;dispose(p1);a[l]:=p^.data; end; end; end; writeln('Sorted data:'); for i:= 1 to n do write(a[i]:6); end. 4.7 各种排序算法的比较

1.稳定性比较 插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的 选择排序、希尔排序、快速排序、堆排序是不稳定的 2.时间复杂性比较 插入排序、冒泡排序、选择排序的时间复杂性为 O(n ) 其它非线形排序的时间复杂性为 O(nlog2n) 线形排序的时间复杂性为 O(n); 3.辅助空间的比较 线形排序、二路归并排序的辅助空间为 O(n),其它排序的辅助空间为 O(1); 4.其它比较 插入、冒泡排序的速度较慢,但参加排序的序列局部或整体有序时,这种排序能达到较快的速度。 反而在这种情况下,快速排序反而慢了。 当 n 较小时,对稳定性不作要求时宜用选择排序,对稳定性有要求时宜用插入或冒泡排序。 若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。 当 n 较大时,关键字元素比较随机,对稳定性没要求宜用快速排序。 当 n 较大时,关键字元素可能出现本身是有序的,对稳定性有要求时,空间允许的情况下。 宜用归并排序。 当 n 较大时,关键字元素可能出现本身是有序的,对稳定性没有要求时宜用堆排序。
2

第五章 查找(检索)
5.1 顺序查找 5.2 二分查找 5.3 二叉排序树查找 5.4 哈希(Hash)表 5.5 查找第 k 小元素

查找 是在数据结构中查找指定值的结点。
5.1 顺序查找 1.顺序查找的思想是是: 将查找值顺序逐个与结点值进行比较,相等即为查找成功,否则查找失败. 程序如下: program sxcz; const n=7; type arr=array[1..n] of integer; var x1,i:integer; a:arr; b:boolean; place:integer; procedure search(r:arr;m,x:integer; var found:boolean;var p:integer); begin p:=1;found:=false; while(p<=m) and not found do if r[p]=x then found:=true else p:=p+1; end; begin write('Enter array:'); for i:=1 to n do read(a[i]); writeln; write('Enter search data:');

read(x1); search(a,n,x1,b,place); if b then begin writeln('yes');writeln('Place of',x1:5,'is:',place); end else writeln('no'); end. 5.2 二分查找 1.二分查找的基本思想:首先将结点按关键字排序,其次将查找值与中间位置的值比较,相等,查找成功; 不等,则中间数据大于或小于查找值,无论怎样查找将在一半的数据中查找。 2.例:输入序列数据查找指定值. 程序: program sxcz; const n=7; type arr=array[1..n] of integer; var x1,i:integer; a:arr; place:integer; procedure paixv(var r:arr;m:integer); var k,j,i,t:integer; begin k:=m; while k>0 do begin j:=k-1;k:=0; for i:=1 to j do if r[i]>r[i+1] then begin t:=r[i];a[i]:=r[i+1];r[i+1]:=t;k:=i;end; end; end; procedure search(r:arr;m,x:integer; var p:integer);

var low,high,mid:integer; begin p:=0;low:=1;high:=m; while low<=high do begin mid:=(low+high) div 2; if x>r[mid] then low:=mid+1 else if x<r[mid] then high:=mid-1 else begin p:=mid;exit;end; end; end; begin write('Enter array:'); for i:=1 to n do read(a[i]); writeln; write('Enter search data:'); read(x1); paixv(a,n); search(a,n,x1,place); if place<>0 then writeln('yes') else writeln('no'); end. 5.3 二叉排序树查找 因为二叉排序树的左子树若不为空则左子树的所有结点的值均小于它的根结点的值,而右子树若不为空, 则右子树的所有结点的值均不小大于它的根结点的值,根据这个性质查找算法如下: program pxtree; const a:array[1..8] of integer=(10,18,3,8,12,2,7,3); type point=^nod; nod=record w:integer;

right,left:point ; end; var root,first:point;k:boolean;i,x:integer; procedure maketr(d:integer;var p:point); begin if p=nil then begin new(p); with p^ do begin w:=d;right:=nil;left:=nil end; if k then begin root:=p; k:=false end; end else with p^ do if d>=w then maketr(d,right) else maketr(d,left); end; function searchtr(x:integer;p:point):boolean; begin if p=nil then searchtr:=false else if x=p^.w then searchtr:=true else if x<p^.w then searchtr:=searchtr(x,p^.left) else searchtr:=searchtr(x,p^.right); end; begin first:=nil;k:=true; for i:=1 to 8 do maketr(a[i],first); write('want find data x:');read(x); if searchtr(x,first) then writeln('yes') else writeln('No'); end. 5.4 哈希(Hash)表 以上讲的查找方法基于比较的,查找效率依赖比较次数,其实理想的查找希望不经比较,一次存取便能得 到所查记录,那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系 f,这样查找 k 时, 只要根据这个对应关系 f 找到给定值 k 的像 f(k)。这种对应关系 f 叫哈希(hash)函数。按这种思想

建立的表叫哈希表(也叫散列表)。哈希表存取方便但存储时容易冲突(collision):即不同的关键 字可以对应同一哈希地址。如何确定哈希函数和解决冲突是关键。 1.哈希函数的构造方法 直接定址法:H(k)=k 或 H(k)=a*k+b(线形函数) 如:人口数字统计表 地址 年龄 人数 1 1 67 2 2 3533 3 3 244 ... ... ... 100 100 4

数字分析法:取关键字的若干数位组成哈希地址 如:关键字如下:若哈希表长为 100 则可取中间两位 10 进制数作为哈希地址。 81346532 81372242 81387422 81301367 81322817 81338967 81354157 81368537

平方取中法:关键字平方后取中间几位数组成哈希地址 折叠法: 将关键数字分割成位数相同的几部分 (最后一部分的位数可以不同) 然后取几部分的叠加和 (舍 去进位)作为哈希地址。 除留余数法:取关键字被某个不大于表长 m 的数 p 除后所得的余数为哈希地址。 H(k)=k mod p p<=m 随机数法:H(k)=rondom(k)。 2.处理冲突的方法 假设地址集为 0..n-1,由关键字得到的哈希地址为 j(0<=j<=n-1)的位置已存有记录,处理冲突就是为该 关键字的记录找到另一个"空"的哈希地址。在处理中可能得到一个地址序列 Hi i=1,2,...k 0<=Hi<=n-1),即在处理冲突时若得到的另一个哈希地址 H1 仍发生冲突,再求下一地址 H2,若仍冲突,再 求 H3...。怎样得到 Hi 呢? 开放定址法:Hi=(H(k)+di) mod m (H(k)为哈希函数;m 为哈希表长;di 为增量序列) 当 di=1,2,3,... m-1 时叫线性探测再散列。 当 di=1 ,-1 ,2 ,-2 ,3 ,-3 ,...,k ,-k 时叫二次探测再散列。 当 di=random(m)时叫伪随机探测序列。 例:长度为 11 的哈希表关键字分别为 17,60,29,哈希函数为 H(k)=k mod 11,第四个记录的关键字为 38,分别按上述方法添入哈希表的地址为 8,4,3(随机数=9)。 再哈希法:Hi=RHi(key) i=1,2,...,k,其中 RHi 均为不同的哈希函数。
2 2 2 2 2 2 2 2

链地址法:这种方法很象基数排序,相同的地址的关键字值均链入对应的链表中。 建立公益区法:另设一个溢出表,不管得到的哈希地址如何,一旦发生冲突,都填入溢出表。 3.哈希表的查找 例:如下一组关键字按哈希函数 H(k)=k mod 13 和线性探测处理冲突所得的哈希表 a[0..15]: 0 1 14 2 01 3 68 4 27 5 55 6 19 7 20 8 84 9 79 10 23 11 11 12 10 13 14 15

当给定值 k=84,则首先和 a[6]比在依次和 a[7],a[8]比结果 a[8]=84 查找成功。 当给定值 k=38,则首先和 a[12]比,再和 a[13]比,由于 a[13]没有,查找不成功,表中不存在关键字等于 38 的记录。 5.5 查找第 k 小元素 查找第 k 小元素即在 n 个元素中(未排序)找到第 k 小的元素。方法同快速排序,采用递归方式。 程序如下: program kspv; const n=7; type arr=array[1..n] of integer; var b:arr; i,k:integer; function p(s,t:integer):integer; var i,j,t1,x:integer; begin i:=s;j:=t;x:=b[i]; repeat while (b[j]>=x) and (j>i) do j:=j-1; if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end; while (b[i]<=x) and (i<j) do i:=i+1; if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end until i=j;

b[i]:=x; p:=i; end; function find(s,t,k:integer):integer; var p1,q:integer; begin if s=t then find:=b[s] else begin p1:=p(s,t); q:=p1-s+1; if k<=q then find:=find(s,p1,k) else find:=find(p1+1,t,k-q); end; end; begin write('input data:'); for i:=1 to n do read(b[i]);readln; write('input k:');read(k); write('output data:'); writeln('kthsmall:=',find(1,n,k)); end.

第六章 穷举(枚举)策略
6.1 穷举策略的概念 6.2 典型例题与习题 6.1 穷举策略的概念 所谓枚举法, 指的是从可能的解的集合中一一枚举各元素, 用题目给定的检验条件判定哪些是无用的, 哪些是有用的。能使命题成立,即为其解。 有些问题可以用循环语句和条件语句直接求解,有些问题用循环求解时循环次数太多,无法编写程序, 怎么办?下面是用“千军万马过独木桥,适者存”的方式实现穷举策略的。 6.2 典型例题与习题 例 1.将 2 个 0 和 2 个 1,排成一圈。从任一个位置开始,每次按逆时针的方向以长度为 n+1 的单位进 行数二进制数。要求给出一种排法,用上面的方法产生出来的 2 个二进制数都不相同。 例如,当 n=2 时,即 2 个 0 和 2 个 1 排成如下一圈:
2 2 n+1 n n

比如,从 A 位置开始,逆时针方向取三个数 000,然后再从 B 位置上开始取三个数 001,接着从 C 开始 取三个数 010,...可以得到 000,001,010,101,011,111,110,100 共 8 个二进制数且都不相同。 程序说明: 以 n=4 为例,即有 16 个 0,16 个 1,数组 a 用以记录 32 个 0,1 的排法,数组 b 统计二进制数出现的 可能性。 程序清单 PROGRAM NOI00; VAR A B :ARRAY[1..36] OF 0..1 :ARRAY[0..31] OF INTEGER;

I,J,K,S,P:INTEGER; BEGIN FOR I:=1 TO 36 DO FOR I:=28 TO 32 DO P:=1; A[6]:=1; A[I]:=0; A[I]:=1;

WHILE (P=1) DO BEGIN J:=27 WHILE A[J]=1 DO ( A[J]:=1 ) FOR I:=J+1 TO 27 DO ( A[i]:=0 FOR I:=0 TO 31 DO B[I]:=0; FOR I:=1 TO 32 DO BEGIN ( S:=0) FOR K:=I TO I+4 DO ( B[S]:=1 ) END; S:=0; FOR I:=0 TO 31 DO S:=S+B[I]; S:=S*2+A[k]; ) J:=J-1;

IF ( S=32 ) THEN P:=0 END; FOR I:=1 TO 32 DO WRITELN END. 例 2:在 A、B 两个城市之间设有 N 个路站(如下图中的 S1,且 N<100),城市与路站之间、路站和路站 之间各有若干条路段(各路段数<=20,且每条路段上的距离均为一个整数)。 A,B 的一条通路是指:从 A 出发,可经过任一路段到达 S1,再从 S1 出发经过任一路段,?最后到 达 B。通路上路段距离之和称为通路距离(最大距离<=1000)。当所有的路段距离给出之后,求出所有不 FOR J:=I TO I+4 DO WRITE(A[J]);

同距离的通路个数(相同距离仅记一次)。 例如:下图所示是当 N=1 时的情况:

从 A 到 B 的通路条数为 6,但因其中通路 5+5=4+6,所以满足条件的不同距离的通路条数为 5。 算法说明:本题采用穷举算法。 数据结构:N:记录 A,B 间路站的个数 数组 D[I,0]记录第 I-1 个到第 I 路站间路段的个数 D[I,1],D[I,2],?记录每个路段距离 数组 G 记录可取到的距离 程序清单: PROGRAM CHU7_6; VAR I,J,N,S:INTEGER; B:ARRAY[0..100] OF INTEGER; D:ARRAY[0..100,0..20] OF INTEGER; G:ARRAY[0..1000] OF 0..1; BEGIN READLN(N); FOR I:=1 TO N+1 DO BEGIN READLN(D[I,0]); FOR J:=1 TO D[I,0] DO READ(D[I,J]); END; D[0,0]:=1; FOR I:=1 TO N+1 DO B[I]:=1; B[0]:=0; FOR I:=1 TO 1000 DO G[I]:=0; WHILE B[0]<>1 DO

BEGIN S:=0; FOR I:=1 TO N+1 DO S:= S+D[I,B[I]];

G[S]:=1;J:=N+1; WHILE B[J]:=B[J]+1; FOR I:=J+1 TO N+1 DO B[I]:=1; END; S:=0; FOR I:=1 TO 1000 DO S:=S+G[I]; WRITELN(S);READLN; END. 练习: 1。问题描述:将 n 个整数分成 k 组(k≤n,要求每组不能为空),显然这 k 个部分均可得到一个各自的和 s1,s2,??sk,定义整数 P 为: P=(S1-S2) +(S1 一 S3) +??+(S1-Sk) +(s2-s3) +??+(Sk-1-Sk)
2 2 2 2 2

B[J]=D[J,0]

DO J:=J-1;

问题求解:求出一种分法,使 P 为最小(若有多种方案仅记一种〉 程序说明: 数组:a[1],a[2],...A[N]存放原数 s[1],s[2],...,s[K]存放每个部分的和 b[1],b[2],...,b[N]穷举用临时空间 d[1],d[2],...,d[N]存放最佳方案 程序: program exp4; Var i,j,n,k : integer; a :array [1..100] of integer; b,d:array [0..100] of integer; s :array[1..30] of integer;

begin readln(n,k); for I:=1 to n do read(a[I]); for I:=0 to n do b[I]:=1; cmin:=1000000; while (b[0]=1) do begin for I:=1 to k do for I:=1 to n do ② sum:=0; for I:=1 to k-1 do for j:= ③ ①

sum:=sum+(s[I]-s[j])*(s[I]-s[j]); if ④ begin cmin:=sum; for I:=1 to n do d[I]:=b[I]; end; j:=n; while ⑤ do j:=j-1; then

b[j]:=b[j]+1; for I:=j+1 to n do end; writeln(cmin); for I:=1 to n do write(d[I]:40); writeln; end. 2.问题描述:有 n 种基本物质(n≤10),分别记为 P1,P2,??,Pn,用 n 种基本物质构造物品,这些物品使 用在 k 个不同地区(k≤20),每个地区对物品提出自己的要求,这些要求用一个 n ⑥

位的数表示:α 1α 2??α n,其中: α i =1 表示所需物质中必须有第 i 种基本物质 =-1 表示所需物质中必须不能有第 i 种基本物质 r =0 无所谓 问题求解:当 k 个不同地区要求给出之后,给出一种方案,指出哪些物质被使用,哪些物质不被使用。 程序说明:数组 b[1],b[2],...,b[nJ 表示某种物品 a[1..k,1..n]记录 k 个地区对物品的要求,其中: a[I,j]=1 表示第 i 个地区对第 j 种物品是需要的 a[i,j]=0 表示第 i 个地区对第 j 种物品是无所谓的 a[i,j]=-1 表示第 i 个地区对第 j 种物品是不需要的 程序: program gxp2; Var i, j ,k, n :integer; p:boolean; b :array [0..20] of 0..1; a :array[1..20,1..10]d integer; begin readln(n,k); for i:=1 to k do begin for j:=1 to n do read(a[i,j]); readln; end; for i:=O to n do b[i]:=0; p:=true; while begin j:=n; while b[j]=1 do j:=j-1; ② ① do

for i:=j+1 to n do b[I]:=0; ③ for i:=1 to k do for j :=1to n do if( a[i,j]=1 ) and (b[j]=0) or then p:=true; end; if ⑤ ④

then writeln('找不到!‘) else for i:=1 to n do if (b[i]=1) then writeln('物质',I,’需要') else writeln('物质',i,'不需要'); end.

第七章 贪心策略
7.1 贪心策略的定义 7.2 贪心策略特点 7.3 典型例题与习题 在众多的计算机解题策略中, 贪心策略可以算得上是最接近人们日常思维的一种解题策略, 正基于 此,贪心策略在各级各类信息学竞赛、尤其在对 NPC 类问题的求解中发挥着越来越重要的作用。 7.1 贪心策略的定义 贪心策略是: 指从问题的初始状态出发, 通过若干次的贪心选择而得出最优值(或较优解)的一种解题方 法。 其实,从“贪心策略”一词我们便可以看出,贪心策略总是做出在当前看来是最优的选择,也就是说贪 心策略并不是从整体上加以考虑, 它所做出的选择只是在某种意义上的局部最优解, 而许多问题自身的 特性决定了该题运用贪心策略可以得到最优解或较优解。 例 1:在 n 行 m 列的正整数矩阵中,要求从每一行中选一个数,使得选出的 n 个数的和最大。 本题可用贪心策略:选 n 次,每一次选相应行中的最大值即可。

例 2:在一个 N×M 的方格阵中,每一格子赋予一个数(即为权)。规定每次移动时只能向上或向右。 现试找出一条路径,使其从左下角至右上角所经过的权之和最大。 本题用贪心策略不能得到最优解,我们以 2×4 的矩阵为例。 3 1 4 2 6 10

若按贪心策略求解,所得路径为:1,3,4,6; 若按动态规划法求解,所得路径为:1,2,10,6。 例 3:设定有 n 台处理机 p1,p2,......pn,和 m 个作业 j1,j2,...jm,处理机可并行工作,作业未完成不 能中断,作业 ji 在处理机上的处理时间为 ti,求解最佳方案,使得完成 m 项工作的时间最短? 本题不能用贪心算法求解:理由是若 n=3,m=6 各作业的时间分别是 11 7 5 5 4 7

用贪心策略解(每次将作业加到最先空闲的机器上)time=15,用搜索策略最优时间应是 14,但是贪心策 略给我们提供了一个线索那就是每台处理上的时间不超过 15,给搜索提供了方便。 总之: 1. 不能保证求得的最后解是最佳的; 2. 只能用来求某些最大或最小解问题; 3. 能确定某些问题的可行解的范围,特别是给搜索算法提供了依据。 7. 2 贪心策略的特点 贪心算法有什么样的特点呢?我认为,适用于贪心算法解决的问题应具有以下 2 个特点: 1、贪心选择性质: 所谓贪心选择性质是指应用同一规则 f,将原问题变为一个相似的、但规模更小的子问题、而后的 每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择,但不依赖于未做出的选择。从全局来 看,运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质,读者可在后文给出 的贪心策略状态空间图中得到深刻地体会。 2、局部最优解: 我们通过特点 2 向大家介绍了贪心策略的数学描述。 由于运用贪心策略解题在每一次都取得了最优 解, 但能够保证局部最优解得不一定是贪心算法。 如大家所熟悉得动态规划算法就可以满足局部最优解, 但贪心策略比动态规划时间效率更高站用内存更少,编写程序更简单。 7.3 典型例题与习题 例 4:背包问题:

有一个背包,背包容量是 M=150。有 7 个物品,物品可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。 物品 重量 价值 A 35 10 B 30 40 C 60 30 D 50 50 E 40 35 F 10 40 G 25 30

分析: 目标函数: ∑pi 最大 约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150) (1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优? (2)每次挑选所占空间最小的物品装入是否能得到最优解? (3)每次选取单位容量价值最大的物品,成为解本题的策略。 程序如下: program beibao; const m=150; n=7; var xu:integer; i,j:integer; goods:array[1..n,0..2] of integer; ok:array[1..n,1..2] of real; procedure init; var i:integer; begin xu:=m; for i:=1 to n do

begin write('Enter the price and weight of the ',i,'th goods:'); goods[i,0]:=i; read(goods[i,1],goods[i,2]); readln; ok[i,1]:=0; ok[i,2]:=0; end; end; procedure make; var bi:array[1..n] of real; i,j:integer; temp1,temp2,temp0:integer; begin for i:=1 to n do bi[i]:=goods[i,1]/goods[i,2]; for i:=1 to n-1 do for j:=i+1 to n do begin if bi[i]<bi[j] then begin temp0:=goods[i,0]; temp1:=goods[i,1]; temp2:=goods[i,2]; goods[i,0]:=goods[j,0]; goods[i,1]:=goods[j,1]; goods[i,2]:=goods[j,2]; goods[j,0]:=temp0; goods[j,1]:=temp1; goods[j,2]:=temp2; end; end; end; begin init; make; for i:=1 to 7 do

begin if goods[i,2]>xu then break; ok[i,1]:=goods[i,0]; ok[i,2]:=1; xu:=xu-goods[i,2]; end; j:=i; if i<=n then begin ok[i,1]:=goods[i,0]; ok[i,2]:=xu/goods[i,2]; end; for i:=1 to j do writeln(ok[i,1]:1:0,':',ok[i,2]*goods[i,2]:2:1); end. 例 5:旅行家的预算问题: 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市,给定两个城市间的距离 d1,汽车油箱 的容量是 c,每升汽油能行驶的距离 d2,出发时每升汽油的价格是 p,沿途加油站数为 n(可为 0), 油站 i 离出发点的距离是 di,每升汽油的价格是 pi。 计算结果四舍五入保留小数点后两位,若无法到达目的地输出“No answer" 若输入: d1=275.6 d[1]=102 d[2]=220 output 26.95 本问题的贪心策略是:找下一个较便宜的油站,根据距离确定加满、不加、加到刚好到该站。 程序如下: program jiayou; const maxn=10001; zero=1e-16; c=11.9 d2=27.4 p=8 n=2

p[1]=2.9 p[2]=2.2

type jd=record value,way,over:real; end; var oil:array[1..maxn] of ^jd; n:integer; d1,c,d2,cost,maxway:real; function init:boolean; var i:integer; begin new(oil[1]); oil[1]^.way:=0; read(d1,c,d2,oil[1]^.value,n); maxway:=d2*c; for i:=2 to n+1 do begin new(oil[i]); readln(oil[i]^.way,oil[i]^.value); oil[i]^.over:=0; end; inc(n,2); new(oil[n]); oil[n]^.way:=d1; oil[n]^.value:=0; oil[n]^.over:=0; for i:=2 to n do if oil[i]^.way-oil[i-1]^.way>maxway then begin init:=false; exit

end; init:=true; end; procedure buy(i:integer;miles:real); begin cost:=cost+miles/d2*oil[i]^.value; end; procedure solve; var i,j:integer; s:real; begin i:=1;j:=i+1; repeat s:=0.0; while( s<=maxway+zero) and (j<=n-1) and (oil[i]^.value<=oil[j]^.value) do begin inc(j); s:=s+oil[j]^.way-oil[j-1]^.way end; if s<=maxway+zero then if (oil[i]^.over+zero>=oil[j]^.way-oil[i]^.way) then oil[j]^.over:=oil[i]^.over-(oil[j]^.way-oil[i]^.way) else begin buy(i,oil[j]^.way-oil[i]^.way-oil[i]^.over); oil[j]^.over:=0.0; end else begin buy(i,maxway-oil[i]^.over); j:=i+1; oil[j]^.over:=maxway-(oil[j]^.way-oil[i]^.way);

end; i:=j; until i=n; end; begin cost:=0; if init then begin solve; writeln(cost:0:2); end else writeln('No answer'); end. 例 6:n 个部件,每个部件必须经过先 A 后 B 两道工序。 以知部件 i 在 A,B 机器上的时间分别为 ai,bi。如何安排加工顺序,总加工时间最短? 输入: 5 部件 ai bi 输出: 34 1 5 4 2 3 1 3 6 2 5 2 3 8 1 4 7 4 5 10 9

本问题的贪心策略是 A 机器上加工短的应优先,B 机器上加工短的应靠后。 程序如下: program workorder; const maxn=100; type jd=record a,b,m,o:integer; end; var n,min,i:integer;

c:array[1..maxn] of jd; order:array[1..maxn] of integer; procedure init; var i:integer; begin readln(n); for i:=1 to n do read(c[i].a); readln; for i:=1 to n do read(c[i].b); readln; for i:=1 to n do begin if c[i].a<c[i].b then c[i].m:=c[i].a else c[i].m:=c[i].b; c[i].o:=i; end; end; procedure sort; var i,j,k,t:integer; temp:jd; begin for i:=1 to n-1 do begin k:=i;t:=c[i].m; for j:=i+1 to n do if c[j].m<t then begin t:=c[j].m;k:=j end ; if k<>i then begin temp:=c[i];c[i]:=c[k];c[k]:=temp end end; end;

procedure playorder; var i,s,t:integer; begin fillchar(order,sizeof(order),0); s:=1; t:=n; for i:=1 to n do if c[i].m=c[i].a then begin order[s]:=i;s:=s+1 end else begin order[t]:=i;t:=t-1;end; end; procedure calc_t; var i,t1,t2:integer; begin t1:=0;t2:=0; for i:=1 to n do begin t1:=t1+c[order[i]].a; if t2<t1 then t2:=t1; t2:=t2+c[order[i]].b; end; min:=t2; end; begin init; sort; playorder; calc_t; writeln(min); for i:=1 to n do write(c[order[i]].o,' ');

writeln; end. 习题: 1.最佳浏览路线问题: 某旅游区的街道成网格状(见图),其中东西向的街道都是旅游街,南北向的街道都是林荫道。由于游 客众多,旅游街被规定为单行道。游客在旅游街上只能从西向东走,在林荫道上既可以由南向北走,也 可以从北向南走。阿隆想到这个旅游区游玩。他的好友阿福给了他一些建议,用分值表示所有旅游街相 邻两个路口之间的道路值得浏览得程度,分值从-100到100的整数,所有林荫道不打分。所有分 值不可能全是负值。 例如下图是被打过分的某旅游区的街道图:

图6 阿隆可以从任一路口开始浏览,在任一路口结束浏览。请你写一个程序,帮助阿隆寻找一条最佳的浏览 路线,使得这条路线的所有分值总和最大。 2..删数问题 键盘输入一个高精度的正整数 N,去掉其中任意 S 个数字后剩下的数字按左右次序组成一个新的正整 数。对给定的 N 和 S,寻找一种删数规则使得剩下得数字组成的新数最小。 参考程序

第八章 分治策略
8.1 分治策略的定义 8.2 分治法解题的步骤 8.3 典型例题与习题 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。 问题的规模越小, 越容易直接 求解,解题所需的计算时间也越少。例如,对于 n 个元素的排序问题,当 n=1 时,不需任何计算。n=2 时,只要作一次比较即可排好序。n=3 时只要作 3 次比较即可,?。而当 n 较大时,问题就不那么容易 处理了。要想直接解决一个规模较大的问题,有时是相当困难的。 分治法的设计思想是, 将一个难以直接解决的大问题, 分割成一些规模较小的相同问题, 以便各个击破, 分而治之。 8.1 分治策略的定义 分治策略是:对于一个规模为 n 的问题,若该问题可以容易地解决(比如说规模 n 较小)则直接解决, 否则将其分解为 k 个规模较小的子问题, 这些子问题互相独立且与原问题形式相同, 递归地解这些子问 题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 如果原问题可分割成 k 个子问题,1<k≤n ,且这些子问题都可解,并可利用这些子问题的解求出 原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使 用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模 却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一 对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。 分治法所能解决的问题一般具有以下几个特征: 1. 该问题的规模缩小到一定的程度就可以容易地解决; 2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。 3. 利用该问题分解出的子问题的解可以合并为该问题的解; 4. 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。 上述的第一条特征是绝大多数问题都可以满足的, 因为问题的计算复杂性一般是随着问题规模的增加而 增加; 第二条特征是应用分治法的前提, 它也是大多数问题可以满足的, 此特征反映了递归思想的应用; 第三条特征是关键, 能否利用分治法完全取决于问题是否具有第三条特征, 如果具备了第一条和第二条 特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率,如 果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治 法,但一般用动态规划法较好。

8. 2 分治法解题的步骤 分治法的基本步骤 分治法在每一层递归上都有三个步骤: 1. 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题; 2. 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题; 3. 合并:将各个子问题的解合并为原问题的解。 它的一般的算法设计模式如下: Divide-and-Conquer(P) 1. 2. if |P|≤n0 then return(ADHOC(P))

3. 将 P 分解为较小的子问题 P1 ,P2 ,...,Pk 4. 5. 6. 7. for i←1 to k do yi ← Divide-and-Conquer(Pi) T ← MERGE(y1,y2,...,yk) return(T) △ 递归解决 Pi △ 合并子问题

其中|P|表示问题 P 的规模;n0 为一阈值,表示当问题 P 的规模不超过 n0 时,问题已容易直接解出,不 必再继续分解。ADH OC(P)是该分治法中的基本子算法,用于直接解小规模的问题 P。因此,当 P 的规模不超过 n0 时,直接 用算法 ADHOC(P)求解。 算法 MERGE(y1,y2,...,yk)是该分治法中的合并子算法,用于将 P 的子问题 P1 ,P2 ,...,Pk 的相应的解 y1,y2,...,yk 合并为 P 的解。 根据分治法的分割原则,原问题应该分为多少个子问题才较适宜?各个子问题的规模应该怎样才为适 当?这些问题很难予以肯定的回 答。但人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。换句话说,将 一个问题分成大小相等的 k 个子问题的处理方法是行之有效的。许多问题可以取 k=2。这种使子问题规 模大致相等的做法是出自一种平衡(balancing)子问题的思想,它几乎总是比子问题规模不等的做法要 好。 8.3 典型例题与习题 例 1:二分查找

在对线性表的操作中,经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素 x 和 线性表 L,输出为 x 在 L 中的位置或者 x 不在 L 中的信息。比较自然的想法是一个一个地扫描 L 的所有 元素,直到找到 x 为止。这种方法对于有 n 个元素的线性表在最坏情况下需要 n 次比较。一般来说,如 果没有其他的附加信息, 在有 n 个元素的线性表中查找一个元素在最坏情况下都需要 n 次比较。 下面我 们考虑一种简单的情况。假设该线性表已经排好序了,不妨设它按照主键的递增顺序排列(即由小到大 排列)。在这种情况下,我们是否有改进查找效率的可能呢? 如果线性表里只有一个元素, 则只要比较这个元素和 x 就可以确定 x 是否在线性表中。 因此这个问题满 足分治法的第一个适用条件; 同时我们注意到对于排好序的线性表 L 有以下性质: 比较 x 和 L 中任意一 个元素 L[i],若 x=L[i],则 x 在 L 中的位置就是 i;如果 x<L[i],由于 L 是递增排序的,因此假如 x 在 L 中的话,x 必然排在 L[i]的前面,所以我们只要在 L[i]的前面查找 x 即可;如果 x>L[i],同理我 们只要在 L[i]的后面查找 x 即可。无论是在 L[i]的前面还是后面查找 x,其方法都和在 L 中查找 x 一 样,只不过是线性表的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。很显然 此问题分解出的子问题相互独立,即在 L[i]的前面或后面查找 x 是独立的子问题,因此满足分治法的 第四个适用条件。 于是我们得到利用分治法在有序表中查找元素的算法。 function Binary_Search(L,a,b,x); begin if a>b then return(-1) else begin m:=(a+b) div 2; if x=L[m] then return(m) else if x>L[m] then return(Binary_Search(L,m+1,b,x)); else return(Binary_Search(L,a,m-1,x)); end; end; 在以上算法中,L 为排好序的线性表,x 为需要查找的元素,b,a 分别为 x 的位置的上下界,即如果 x 在 L 中,则 x 在 L[a..b]中。每次我们用 L 中间的元素 L[m]与 x 比较,从而确定 x 的位置范围。然后递 归地缩小 x 的范围,直到找到 x。

例 2:快速排序 快速排序的基本思想是基于分治法的。对于输入的子序列 L[p..r],如果规模足够小则直接进行排 序,否则分三步处理:
?

分解(Divide): 将输入的序列 L[p..r]划分成两个非空子序列 L[p..q]和 L[q+1..r], 使 L[p..q] 中任一元素的值不大于 L[q+1..r]中任一元素的值。

? ?

递归求解(Conquer):通过递归调用快速排序算法分别对 L[p..q]和 L[q+1..r]进行排序。 合并(Merge):由于对分解出的两个子序列的排序是就地进行的,所以在 L[p..q]和 L[q+1..r] 都排好序后不需要执行任何计算 L[p..r]就已排好序。

这个解决流程是符合分治法的基本步骤的。因此,快速排序法是分治法的经典应用实例之一。 程序代码如下: program kspv; const n=7; type arr=array[1..n] of integer; var a:arr; i:integer; procedure quicksort(var b:arr; s,t:integer); var i,j,x:integer; begin i:=s;j:=t;x:=b[i]; repeat while (b[j]>=x) and (j>i) do j:=j-1; if j>i then begin b[i]:=b[j];i:=i+1;end; while (b[i]<=x) and (i<j) do i:=i+1; if i<j then begin b[j]:=b[i];j:=j-1; end until i=j; b[i]:=x; i:=i+1;j:=j-1; if s<j then quicksort(b,s,j);

if i<t then quicksort(b,i,t); end; begin write('input data:'); for i:=1 to n do read(a[i]); writeln; quicksort(a,1,n); write('output data:'); for i:=1 to n do write(a[i]:6); writeln; end. 例 3:归并排序 归并就是将多个有序的数列合成一个有序的数列。 将两个有序序列合并为一个有序序列叫二路归并 (merge).归并排序就是 n 长度为 1 的子序列,两两归并最后变为有序的序列。 程序代码如下: program gbpx; const maxn=7; type arr=array[1..maxn] of integer; var a,b,c:arr; i:integer; procedure merge(r:arr;l,m,n:integer;var r2:arr); var i,j,k,p:integer; begin i:=l;j:=m+1;k:=l-1; while (i<=m)and (j<=n) do begin k:=k+1; if r[i]<=r[j] then begin r2[k]:=r[i];i:=i+1 end else begin r2[k]:=r[j];j:=j+1 end end;

if i<=m then for p:=i to m do begin k:=k+1;r2[k]:=r[p] end; if j<=n then for p:=j to n do begin k:=k+1;r2[k]:=r[p] end; end; procedure mergesort( var r,r1:arr;s,t:integer); var k:integer; c:arr; begin if s=t then r1[s]:=r[s] else begin k:=(s+t) div 2; mergesort(r,c,s,k); mergesort(r,c,k+1,t); merge(c,s,k,t,r1) end; end; begin write('Enter data:'); for i:= 1 to maxn do read(a[i]); mergesort(a,b,1,maxn); for i:=1 to maxn do write(b[i]:9); writeln; end. 练习: 1。写出二分查找的程序。 2。赛程问题。有 n(n=2^m)编号为 1 到 n 的运动队,参加某项运动的单循环比赛,请安排一个比赛日程? (共 n-1 天比赛,每天每队必须比赛一场)。 思考题 1:

最接近点对问题 在应用中,常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的 问题中,常需要了解其邻域中其他几何对象的信息。例如,在空中交通控制问题中,若将飞机作为空间 中移动的一个点来看待,则具有最大碰撞危险的 2 架飞机,就是这个空间中最接近的一对点。这类问题 是计算几何学中研究的基本问题之一。 下面我们着重考虑平面上的最接近点对问题。 最接近点对问题的 提法是:给定平面上 n 个点,找其中的一对点,使得在 n 个点的所有点对中,该点对的距离最小。严格 地说,最接近点对可能多于 1 对。为了简单起见,这里只限于找其中的一对。 思考题 2: 导线和开关问题 如图 1 所示,具有 3 根导线的电缆把 A 区和 B 区连接起来。在 A 区 3 根导线标以 1,2,3;在 B 区 导线 1 和 3 被连到开关 3,导线 2 连到开关 1。

图 1 一个有 3 条导线和 3 个开关的实例 一般说来,电缆含 m(1<=m<=90)根导线,在 A 区标以 1,2,...,m。在 B 区有 m 个开关,标为 1,2,..,m。 每一根导线都被严格地连到这些开关中的某一个上; 每一个开关上可以连有 0 根或多根导线。 怎样快速 测试哪根导线连在哪个开关上?

第四部 数据结构
第一章 什么是数据结构
1.1 基本概念和术语 1.2 数据的逻辑结构和物理结构 1.1 基本概念和术语 1.数据(data): 是对客观事物的符号的表示,是所有能输入到计算机中并被计算机程序处理的符号的总称。 2.数据元素(data element): 是数据的基本单位,在计算机程序中通常作为一个整体来处理。一个数据元素由多个 数据项(data item)组成,数据 项是数据不可分割的最小单位。 3.数据结构(data structure): 是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一个二元组,记为: data_structure=(D,S).其中 D 为数据元素的集合,S 是 D 上关系的集合。 数据元素相互之间的关系称为结构(structure)。根据数据元素之间关系的不同特性,通常由下列四 类基本结构: (1)集合:数据元素间的关系是同属一个集合。(图 1) (2)线性结构:数据元素间存在一对一的关系。(图 2) (3)树形结构:结构中的元素间的关系是一对多的关系。(图 3) (4)图(网)状结构:结构中的元素间的关系是多对多的关系。(图 4)

图1

图2

图3 1.2 数据的逻辑结构和物理结构

图4

逻辑结构:数据元素之间存在的关系(逻辑关系)叫数据的逻辑结构。 物理结构:数据结构在计算机中的表示(映象)叫数据的物理结构。 一种逻辑结构可映象成不同的存储结构: 顺序存储结构和非顺序存储结构 (链式存储结构和散列结构) 。

第二章 线性表
2.1 线性表的逻辑结构及基本运算 2.2 线性表的顺序存储结构 2.3 线性表的链式存储结构 2.1 线性表的逻辑结构及基本运算 1.线性表简单的定义 n 个数据元素的的有限序列其特点是除了表头和表尾外,表中的每一个元素有且仅有唯一的前驱和唯一 的后继,表头有且只有一个后继,表尾有且只有一个前驱。 2.线性表的基本运算 length(L) IsEmpty(L) 返回表 L 的长度,即元素个数。 如果表 L 为空表(长度为 0)则返回 true,否则返回 false。 这是一个函数,函数值为表 L 中位置 p 的后继位置。如果 p 是 L 中结束元素 next(L,p) 的位置,则 L.Next(p)=L.end。当 L 中没有位置 p 或 p=L.end 时,该运算无定 义。

这是一个函数,函数值为表 L 中位置 p 的前驱位置。当 L 中没有位置 p 或 p prev(L,p) 是 L 中开始元素的位置时,该运算无定义。 这是一个函数, 函数值为 L 中位置 p 处的元素。 当 p=L.end 或 L 中没有位置 p get(L,p) 时,该运算无定义。 在表 L 的位置 p 处插入元素 x, 并将原来占据位置 p 的元素及其后面的元素都 向后推移一个位置。例如,设 L 为 a1,a2,?,an,那么在执行 insert(L,x,p) insert(L,x,p) 后,表 L 变为 a1,a2,?ap-1,x,ap,?,an 。若 p 为 L.end,那么表 L 变为 a1,a2,?,an,x 。若表 L 中没有位置 p,则该运算无定义。 从表 L 中删除位置 p 处的元素。 例如, 当 L 为 a1,a2,?,an 时, 执行 delete(L,p) delete(L,p) 后,L 变为 a1,a2,?,ap-1,ap+1,?,an 。当 L 中没有位置 p 或 p=L.end 时,该运 算无定义。 这是一个函数,函数值为元素 x 在 L 中的位置。若 x 在 L 中重复出现多次, locate(L,x) 则函数值为 x 第一次出现的位置。当 x 不在 L 中时,函数值为 0 MakeEmpty(L) 这是一个将 L 变为空表的方法。

例 1 假设两个线性表 LA,LB 分别代表两个集合 A 和 B:求 A=A U B proc union(var la:linear_list;lb:linear_list); begin n:=length(la); for i:=1 to length(lb) do x:=get(lb,i); k:=locate(la,x); if k=0 then begin insert(la,n+1,x);n:=n+1 end; end 例 2 已知线性表 la,lb 中的数据元素按值非递减有序排列,现要求将 la,lb 归并为一个新的线性表 lc 且 lc 按值非递减。 proc merge(la,lb:linear_list;var lc:linear_list); begin i:=1;j:=1;k:=0; while (i<=length(la)) and (j<=length(lb)) do

if get(la,i)<=get(lb,j) then begin insert(lc,k+1,get(la,i));k:=k+1;i:=i+1 end else begin insert(lc,k+1,get(lb,j));k:=k+1;j:=j+1 end while i<=length(la) do begin insert(lc,k+1,get(la,i));k:=k+1;i:=i+1; end while j<=length(lb) do begin insert(lc,k+1,get(lb,j));k:=k+1;j:=j+1 end end; 2.2 线性表的顺序存储结构 线性表的顺序存储即用一组地址连续的存储单元依次存储线性表中的元素。 设线性表中每个元素需占用 r 个存储单元则 loc(ai+1 )=loc(ai)+r loc(ai)=loc(a1)+(i-1)*r 这时可以这样定义线性表类型 type sqlist=record data:array[1..maxlen] of datatype; last:0..maxlen end 在这种存储方式下,容易实现对表的遍历。要在表的尾部插入一个新元素,也很容易。但是要在表的中 间位置插入一个新元素,就必须先将其后面的所有元素都后移一个单元,才能腾出新元素所需的位置。 执行删除运算的情形类似。 如果被删除的元素不是表中最后一个元素, 则必须将它后面的所有元素前移 一个位置,以填补由于删除所造成的空缺。这两种运算的时间复杂度均为 O(n)n 为表的长度。 2.3 线性表的链式存储结构

1.单链表 定义: 实现表的另一种方法是用指针将存储表元素的那些单元依次串联在一起。 这种方法避免了在数组 中用连续的单元存储元素的缺点, 因而在执行插入或删除运算时, 不再需要移动元素来腾出空间或填补 空缺。然而我们为此付出的代价是,需要在每个单元中设置指针来表示表中元素之间的逻辑关系,因而 增加了额外的存储空间的开销。 为了将存储表元素的所有单元用指针串联起来, 我们让每个单元包含一个元素域和一个指针域, 其中的 指针指向表中下一个元素所在的单元。例如,如果表是 a1,a2,?,an ,那么含有元素 ai 的那个单元中的 指针应指向含有元素 ai+1 的单元(i=1,2,?,n-1)。含有 an 的那个单元中的指针是空指针 nil。此外,通

常我们还为每一个表设置一个表头单元 header,其中的指针指向开始元素中所在的单元,但表头单元 header 中不含任何元素。设置表头单元的目的是为了使表运算中的一些边界条件更容易处理。这一点 我们在后面可以看到。 如果我们愿意单独地处理诸如在表的第一个位置上进行插人与删除操作等边界情 况,也可以简单地用一个指向表的第一个单元的指针来代替表头单元。 上述这种用指针来表示表的结构通常称为单链接表,或简称为单链表或链表。单链表的逻辑结构如图 1 所示。表示空表的单链表只有一个单元,即表头单元 header,其中的指针是空指针 nil。

图 1 单链表示意图 为了便于实现表的各种运算,在单链表中位置变量的意义与用数组实现的表不同。在单链表中位置 i 是一个指针,它所指向的单元是元素 ai-1 所在的单元,而不是元素 ai 所在的单元(i=2,3,?,n)。位置 1 是指向表头单元 header 的指针。位置 End(L)是指向单链表 L 中最后一个单元的指针。这样做的目的是 为了避免在修改单链表指针时需要找一个元素的前驱元素的麻烦, 因为在单链表中只设置指向后继元素 的指针,而没有设置指向前驱元素的指针。 单链表结构的主要类型可形式地定义为: type pointer=^nodetype nodetype=record data:datatype; next:pointer; end; linklist=pointer; 基本运算的实现: 过程 Insert(x,p) 功能 在表 L 的位置 p 处插入元素 x, 并将原来占据位置 p 的元素及其后面的元素都向后推移一个位置。 例如, 设 L 为 a1,a2,?,an, 那么在执行 Insert(x,p)后, 表 L 变为 a1,a2,?ap-1,x,ap,?,an 。 若 p 为 End(L), 那么表 L 变为 a1,a2,?,an,x 。若表 L 中没有位置 p,则该运算无定义。

实现 Procedure Insert(x:datatype;p:pointer); var temp:integer; begin new(temp); temp^.data:=x; temp^.next:= p^.next p^.next:=temp; end; 上述算法中,链表指针的修改情况见图 2

图 2(a)是执行 Insert 运算之前的情况。我们要在指针 p 所指的单元之后插入一个新元素 x。图 2(b)是 执行 Insert 运算以后的结果,其中的虚线表示新的指针。 在上述 Insert 算法中,位置变量 p 指向单链表中一个合法位置,要插入的新元素 x 应紧接在 p 所指单 元的后面。指针 p 的合法性应在执行 Insert 运算之前判定。往一个单链表中插入新元素通常在表头或 表尾进行,因此 p 的合法性容易判定。Insert 运算所需的时间显然为 O(1)。 过程 Delete(p) 功能 从表 L 中删除位置 p 的下一元素。例如,当 L 为 a1,a2,?,an 时,执行 Delete(p)后,L 变为 a1,a2,?,ap-1,ap+1,?,an 。当 L 中没有位置 p 或 p=End(L)时,该运算无定义。

实现 Procedure Delete(p:pointer); var q:integer begin q:=p^.next; p^.next:=p^.next^.next; dispose(q); end; 说明 这个过程很简单,其指针的修改如图 3 所示。

若要从一个表中删除一个元素 x,但不知道它在表中的位置,则应先用 Locate(x,L)找出指示要删除的 元素的位置,然后再用 Delete 删除该位置指示的元素。Delete 过程所需的时间显然也为 O(1)。 2.静态链表 静态链表:用游标指示数组单元地址的下标值,它属整数类型数组元素是记录类型,记录中包含一个表 元素和一个作为游标的整数;具体说明如下: type jid=record data:datatype; next:integer; end; var alist=array[0..maxsize] of jid 游标就是。 我们可以用游标来模拟指针, 对于一个表 L, 我们用一个整型变量 Lhead(如 Lhead=0)作为 L 的表头游标。。这样,我们就可以用游标来模拟指针,实现单链表中的各种运算。当 i>1 时,表示第 i 个位置的位置变量 pi 的值是数组 alist 中存储表 L 的第 i-1 个元素 next 值,用 p:=alist(p).next 后移。

照此,我们虽然是用数组来存储表中的元素,但在作表的插人和删除运算时,不需要移动元素,只要修 改游标,从而保持了用指针实现表的优点。因此,有时也将这种用游标实现的表称为静态链表。 3.循环链表 我们在用指针实现表时,表中最后一个元素所在单元的指针域(next)为空指针 nil。如果将这个空指针 改为指向表头单元的指针就使整个链表形成一个环。 这种首尾相接的链表称为循环链表。 在循环链表中, 从任意一个单元出发可以找到表中其他单元。图 6 所示的是一个单链的循环链表或简称为单循环链表。

(a)非空表

(b)空表

图 6 单循环链表 在单循环链表上实现表的各种运算的算法与单链表的情形是类似的。 它们仅在循环终止条件上有所不同: 前者是 p 或 p^.next 指向表头单元;后者是 p 或 p^.next 指向空(nil)。在单链表中我们用指向表头单 元的指针表示一个表 L, 这样就可以在 O(1)时间内找到表 L 中的第一个元素。 然而要找到表 L 中最后一 个元素就要花 O(n)时间遍历整个链表。在单循环链表中,我们也可以用指向表头单元的指针表示一个 表 L。但是,如果我们用指向表尾的指针表示一个表 L 时,我们就可以在 O(1)时间内找到表上中最后一 个元素。同时通过表尾单元中指向表头单元的指针,我们也可以在 O(1)时间内找到表 L 中的第一个元 素。在许多情况下,用这种表示方法可以简化一些关于表的运算。 4.双链表 单循环链表中,虽然从任一单元出发,可以找到其前驱单元,但需要 O(n)时间。如果我们希望能快速 确定表中任一元素的前驱和后继元素所在的单元, 可以在链表的每个单元中设置两个指针, 一个指向后 继,另一个指向前驱,形成图 8 所示的双向链表或简称为双链表。

图 8 双链表 由于在双链表中可以直接确定一个单元的前驱单元和后继单元, 我们可以用一种更自然的方式表示元素 的位置,即用指向双链表中第 i 个单元而不是指向其前一个单元的指针来表示表的第 i 个位置。 双链表的单元类型定义如下。

type dupointer=^celltype celltype=record data:datatype; next,previous:dupointer; end; dulist=dupointer; 和单链的循环表类似,双链表也可以有相应的循环表。我们用一个表头单元将双链表首尾相接,即将表 头单元中的 previous 指针指向表尾, 并将表尾单元的 next 指针指向表头单元, 构成如图 9 所示的双向 循环链表。

图 9 双向循环链表 下面仅以双向循环链表为例给出三种基本运算的实现。 (1)在双向循环链表 L 的位置 p 处插入一个新元素 x 的过程 Insert 可实现如下。 procedure Insert(x:datatdata;p:pointer;var L:duList); Var q:integer begin new(q); q^.data:=x; q^.previous:=p^.previous; q^.next:=p; p^.previous^.next:=q; p^.previous:=q; end;

上述算法对链表指针的修改情况见图 10。

图 10 在双向循环链表中插入一个元素 算法 Insert 中没有检查位置 p 的合法性, 因此在调用 Insert 之前应保证位置 p 的合法性。 由于插入通 常是在表的头尾两端进行的,所以容易检查位置 p 的合法性。 (2)从双向循环链表 L 中删除位置 p 处的元素可实现如下: procedure Delete(p:integer;var L:duList); begin if (p<>nil)and(p<>L) then begin p^.previous^.next:=p^.next; p^.next^.previous:=p^.previous; dispose(p^); end; end; 上述算法对链表指针的修改情况见图 11。

图 11 从双向循环链表中删除一个元素

5.链表的应用 例 1:求 (A-B)U(B-A)其中 A,B 代表两个集合(用静态链表)

program jtlb; const maxsize=20; type jid=record data:integer; next:integer; end; jtlist=array[0..maxsize] of jid; var a:jtlist; last,i,k,pre,x,m,n:integer; begin for i:=0 to maxsize-1 do a[i].next:=i+1; a[maxsize].next:=-1; readln(m,n); for i:=1 to m do begin read(x);a[i].data:=x; end; readln; last:=m; for i:=1 to n do begin read(x); k:=1;pre:=0; while (a[k].data<>x) and (k<>a[last].next) do begin pre:=k;k:=a[k].next; end; if k=a[last].next then begin a[k].data:=x;last:=k end else begin a[pre].next:=a[k].next;if k=last then last:=pre end end; writeln;

i:=0; repeat i:=a[i].next; write(a[i].data,' '); until i=last; end. 例 2 求 p1(x)+p2(x) (两个多项式的和) program dxshi; type link=^node; node=record coef:real; exp:integer; next:link end; poly=link; var p, pa,pb:poly; procedure jl(var a:poly); var p,q:poly; co:real;ex:integer; begin p:=nil; repeat read(co,ex); new(q);q^.coef:=co;q^.exp:=ex;q^.next:=p;p:=q; until (ex=-1) and (co=-1); a:=p;readln; end; procedure add_poly(var a:poly;b:poly); var p,q,u,pre:poly; x:real;

begin p:=a^.next;q:=b^.next; pre:=a; while (p<>nil) and (q<>nil) do if p^.exp>q^.exp then begin pre:=p;p:=p^.next end else if p^.exp=q^.exp then begin x:=p^.coef+q^.coef; if x<>0 then begin p^.coef:=x;pre:=p;end else begin pre^.next:=p^.next; dispose(p) end; p:=pre^.next;u:=q;q:=q^.next;dispose(u); end else begin u:=q^.next;q^.next:=p;pre^.next:=q;pre:=q;q:=u end; if q<>nil then pre^.next:=q; dispose(b); end; begin jl(pa);jl(pb); add_poly(pa,pb); p:=pa;p:=p^.next; while p<>nil do begin writeln(p^.coef:8:2,p^.exp:5); p:=p^.next; end end. 练习题: 1.约瑟夫问题:

有 M 个猴子围成一圈,每个有一个编号,编号从 1 到 M。打算从中选出一个大王。经过协商,决定选大 王的规则如下:从第一个开始,每隔 N 个,数到的猴子出圈,最后剩下来的就是大王。 要求:从键盘输入 M,N,编程计算哪一个编号的猴子成为大王。(程序) 2.求多项式的减与乘法.(程序) 3.http://ace.delos.com/usacogate(题 1.1.2.1 珍珠项链)(程序)

第三章 栈
3.1 栈的概念(逻辑结构)及运算 3.2 栈的存储与实现 3.3 栈的应用 3.1 栈的概念及运算 栈的定义:栈是一种特殊的表这种表只在表头进行插入和删除操作。因此,表头对于栈来说具有特殊的 意义,称为栈顶。相应地,表尾称为栈底。不含任何元素的栈称为空栈。 栈的逻辑结构:假设一个栈 S 中的元素为 an,an-1,..,a1,则称 a1 为栈底元素,an 为栈顶元 素。栈中的 元素按 a1 ,a2,..,an-1,an 的次序进栈。在任何时候,出栈的元素都是栈顶元素。换句话说,栈的修改是 按后进先出的原则进行的,如图 1 所示。因此,栈又称为后进先出(Last In First Out)表,简称为 LIFO 表。所以,只要问题满足 LIFO 原则,就可以使用栈。

图1 栈的运算:为一种抽象数据类型,常用的栈运算有: 运算 含义

inistack(S) getTop(S) Pop(S) Push(S,x) Empty(S) 3.2 栈的存储与实现

使 S 成为一个空栈。 这是一个函数,函数值为 S 中的栈顶元素。 从栈 S 中删除栈顶元素,简称为抛栈。 在 S 的栈顶插入元素 x,简称为将元素 x 入栈。 这是一个函数。 当 S 为空栈时, 函数值为 true, 否则函数值为 false。

栈的数组实现:由于栈是一个特殊的表,我们可以用数组来实现栈。考虑到栈运算的特殊性,我们用一 个数组 elements[1..maxlength]来表示一个栈时, 将栈底固定在数组的底部, 即 elements[1]为最早入 栈的元素,并让栈向数组上方(下标增大的方向)扩展。同时,我们用一个游标 top 来指示当前栈顶元素 所在的单元。当 top=0 时,表示这个栈为一个空栈。在一般情况下,elements 中的元素序列 elements[top],elements[top-1],..,elements[1]就构成了一个栈。这种结构如图 2 所示。

图 2 利用上述结构,我们可以形式地定义栈类型 TStack 如下: Type TStack=Record top:integer; element:array[1..maxlength] of TElement; End; 在这种表示法下,栈的 5 种基本运算可实现如下。

procedure inistack(Var S:TStack); begin S.top:=0; end; function Empty(var S:Stack):Boolean; begin return(S.top=0); end; finction Top(var S:TStack):TElement; begin if Empty(S) then Error('The stack is empty.') else return(S.element[S.top]); end; procedure Pop(var S:TStack); begin if Empty(S) then Error('The stack is empty.') else dec(S.top); {S.top 减 1} end; procedure Push(var S:TStack;x:TElement;); begin if S.top=maxlength then Error('The stack is full.') else begin inc(S.top); {S.top 增 1} S.elements[S.top]:=x; end; end; 以上每种操作的复杂性为 O(1)。

在一些问题中,可能需要同时使用多个同类型的栈。为了使每个栈在算法运行过程中不会溢出, 要为 每个栈顶置一个较大的栈空间。这样做往往造成空间的浪费。实际上,在算法运行的过程中,各个栈一 般不会同时满,很可能有的满而有的空。因此,如果我们让多个栈共享同一个数组,动态地互相调剂, 将会提高空间的利用率,并减少发生栈上溢的可能性。 假设我们让程序中的两个栈共享一个数组 S[1..n]。利用栈底位置不变的特性,我们可以将两个栈的栈底分别设在数组 S 的两端,然后各自向中 间伸展,如图 3 所示。这两个 S 栈的栈顶初值分别为 0 和 n+1。只有当两个栈的栈顶相遇时才可能发生 上溢。由于两个栈之间可以余缺互补,因此每个栈实际可用的最大空间往往大于 n/2。

图3 3.3 栈的应用 1.表达式的求值 问题:能否设计算法,编制一个程序,让计算机扫描如下表达式,并将其值打印出来。 # 3 * ( 4 + 8 ) / 2 -5 # 注:给表达式设置#,标志扫描的开始和结束。 提示算法:设两个栈,一个是操作数栈,用来存放操作数,如 3、4、8 等,另一个是运算符栈,用 来存放运算符。 首先将标志“#”进运算符栈的栈底。 然后依次扫描,按照栈的后进先出原则进行: (1)遇到操作数,进操作数栈; (2)遇到运算符时,则需将此运算符的优先级与栈顶运算符的优先级比较, 若若高于栈顶元素则进栈,继续扫描下一符号, 否则,将运算符栈的栈顶元素退栈,形成一个操作码 Q,同时操作数栈的栈顶元素两次退栈,形成

两个操作数 a、b,让计算机对操作数与操作码完成一次运算操作,即 aQb,并将其运算结果存放在操作 数栈中?? 模拟计算机处理算术表达式过程。从键盘上输入算术表达式串(只含+、-、×、÷运算符,充许含括 号),输出算术表达式的值。设输入的表达式串是合法的。 附源程序: program exsj_1; const max=100; var number:array[0..max] of integer; symbol:array[1..max] of char; s,t:string; i,p,j,code:integer; procedure push;{算符入栈运算} begin inc(p);symbol[p]:=s[i]; end;

procedure pop;{运算符栈顶元素出栈,并取出操作数栈元素完成相应的运算} begin dec(p); case symbol[p+1] of '+':inc(number[p],number[p+1]); '-':dec(number[p],number[p+1]); '*':number[p]:=number[p]*number[p+1]; '/':number[p]:=number[p] div number[p+1]; end; end;

function can:boolean;{判断运算符的优先级别,建立标志函数}

begin can:=true; if (s[i] in ['+','-']) and (symbol[p]<>'(') then exit; if (s[i] in ['*','/']) and (symbol[p] in ['*','/']) then exit; can:=false; end;

begin write('String : '); readln(s); s:='('+s+')'; i:=1; p:=0; while i<=length(s) do begin while s[i]='(' do {左括号处理] begin push; inc(i); end; j:=i; repeat {取数入操作数栈} inc(i); until (s[i]<'0') or (s[i]>'9'); t:=copy(s,j,i-j); val(t,number[p],code); repeat if s[i]=')' then {右括号处理} begin while symbol[p]<>'(' do pop; dec(p); number[p]:=number[p+1]; end else begin {根据标志函数值作运算符入栈或出栈运算处理} while can do pop; push;

end; inc(i); until (i>length(s)) or (s[i-1]<>')'); end; write('Result=',number[0]); readln; end. 2.背包问题 问题:假设有 n 件质量分配为 w1,w2,...,wn 的物品和一个最多能装载总质量为 T 的背包,能否从这 n 件物品中选择若干件物品装入背包,使得被选物品的总质量恰好等于背包所能装载的最大质量,即 wi1+wi2+...+wik=T。若能,则背包问题有解,否则无解。 算法思想:首先将 n 件物品排成一列,依次选取;若装入某件物品后,背包内物品的总质量不超过 背包最大装载质量时,则装入(进栈);否则放弃这件物品的选择,选择下一件物品试探,直至装入的 物品总和正好是背包的最大转载质量为止。这时我们称背包装满。 若装入若干物品的背包没有满, 而且又无其他物品可以选入背包, 说明已装入背包的物品中有不合 格者,需从背包中取出最后装入的物品(退栈),然后在未装入的物品中挑选,重复此过程,直至装满 背包(有解),或无物品可选(无解)为止。 具体实现:设用数组 weight[1..N],stack[1,N]分别存放物品重量和已经装入背包(栈)的物品 序号,MaxW 表示背包的最大装载量。每进栈一个物品,就从 MaxW 中减去该物品的质量,设 i 为待选物 品序号,若 MaxW-weight[i]>=0,则该物品可选;若 MaxW-weight[i] < 0,则该物品不可选,且若 i>n, 则需退栈,若此时栈空,则说明无解。 用 Pascal 实现的参考函数: Function knapstack(n,MaxW,weight); begin top:=0; i:=1; {i 为待选物品序号} while (MaxW>0) and ( i < = n ) do begin if (MaxW-weight[i]>=0) and ( i < = n ) then begin top:=top+1; stack[top]:=i;MaxW=MaxW-weight[i] end; {第 i 件物品装入背包}

if MaxW=0 then return(true) else begin if (i=n) and (top>0) then {背包内有不合适物品} begin {取栈顶物品,恢复 MaxW 的值} i:=stack[top]; top:=top-1;MaxW=MaxW+weight[i]; if top>0 then begin i:=stack[top]; top:=top-1;MaxW=MaxW+weight[i]; end; end; i:=i+1; end; end; return(false) {问题无解} end; 练习:完整完成背包问题

第四章 队列
4.1 队列的概念(逻辑结构)及运算 4.2 队列的存储与实现 4.3 队列的应用 4.1 队列的概念及运算 队列的定义: 队列是一种特殊的线性表,对这种线性表,删除操作只在表头(称为队头)进行,插入操作只在表尾(称 为队尾)进行。队列的修改是按先进先出的原则进行的,所以队列又称为先进先出(First In First Out) 表,简称 FIFO 表。 队列的数学性质: 假设队列为 a1,a2,..,an,那么 a1 就是队头元素,an 为队尾元素。队列中的元素是按 a1,a2,..,an 的顺序 进入的, 退出队列也只能按照这个次序依次退出。 也就是说, 只有在 a1 离开队列之后, a2 才能退出队列, 只有在 a1,a2,..,an-1 都离开队列之后,an 才能退出队列。图 1 是队列的示意图。

图1 队列的运算: 为一种抽象数据类型,常用的队列运算有: 运算 Gethead(Q) 含义 这是一个函数,函数值返回队列 Q 的队头元素。

Enqueue(Q,x) 将元素 x 插入队列 Q 的队尾。此运算也常简称为将元素 x 入队。 Dlqueue(Q) Empty(Q) Clear(Q) 将 Q 的队头元素删除,简称为出队。 这是一个函数,若 Q 是一个空队列,则函数值为 true,否则为 false。 使队列 Q 成为空队列。

4.2 队列的存储与实现 队列是一种特殊的表,因此凡是可以用来实现表的数据结构都可以用来实现队列。不过,队列的中的元 素的个数通常不固定,因此常用循环数组和链表两种方法实现队列。 链队列: 用指针实现队列得到的实际上是一个单链表。 由于入队在队尾进行, 所以用一个指针来指示队尾可以使 入队操作不必从头到尾检查整个表,从而提高运算的效率。另外,指向队头的指针对于 Gethead 和 Dequeue 运算也是必要的。 为了便于表示空队列, 我们仍使用一个表头单元, 将队头指针指向表头单元。 当队头和队尾指针都指向表头单元时,表示队列为一个空队列。 用指针实现队列时,单元类型及队列类型可说明如下: type queueptr=^queuenode; queuenode=record data:elemtp;

next:queueptr; end; linkedquetp=record front,rear:queueptr; end; 其中 front 为队头指针,rear 为队尾指针。图 2 是用指针表示队列的示意图。

图2 面我们来讨论队列的 5 种基本运算。 函数 Gethead(Q) 功能 这是一个函数,函数值返回队列 Q 的队头元素。 实现 Function Gethead(var Q:linkedquetp):elemtp; begin if Empty(Q) then error('The queue is empty!') else return(Q.front^.next^.data); end; 函数 Enqueue(Q,x) 功能 将元素 x 插入队列 Q 的队尾。此运算也常简称为将元素 x 入队。 实现 Procedure Enqueue(x:elemtp;var Q:linkedquetp); begin new(Q.rear^.next); Q.rear:=Q.rear^.next; Q.rear^.data:=x;

Q.rear^.next:=nil; end; 函数 Empty(Q) 功能 这是一个函数,若 Q 是一个空队列,则函数值为 true,否则为 false。 实现 Function Empty(var Q:QueueType):Boolean; begin return(Q.front=Q.rear); end;

函数 Dequeue(Q) 功能 将 Q 的队头元素删除,简称为出队。 实现 Procedure Dequeue(var Q:linkedquetp); var p:queueptr; begin if Empty(Q) then Error('The queue is empty!') else begin p:=Q.front; Q.front:=Q.front^.next; dispose(p); end; end; 函数 Clear(Q) 功能 使队列 Q 成为空队列。 实现

Procedure clear(var Q:linkedquetp); begin Q.rear:=Q.front; while Q.front<>nil do begin Q.front:=Q.front^.next; dispose(Q.rear); Q.rear:=Q.front; end; new(Q.front); Q.front^.next:=nil; Q.rear:=Q.front; end; 循环队列: 我们可以将队列当作一般的表用数组实现,但这样做的效果并不好。尽管我们可以用一个游标 last 来 指示队尾,使得 Enqueue 运算可在 O(1)时间内完成,但是在执行 Dequeue 时,为了删除队头元素,必 须将数组中其他所有元素都向前移动一个位置。这样,当队列中有 n 个元素时,执行 Dequeue 就需要

O(n)时间。为了提高运算的效率,我们用另一种方法来表达数组中各单元的位置关系。设想数组中的单
元不是排成一行,而是围成一个圆环 ,我们将队列中从队头到队尾的元素按顺时针方向存放在循环数 组中一段连续的单元中。当需要将新元素入队时,可将队尾游标 Q.rear 按顺时针方向移一位,并在新 的队尾游标指示的单元中存入新元素。 出队操作也很简单, 只要将队头游标 Q.front 依顺时针方向移一 位即可。容易看出,用循环数组来实现队列可以在 O(1)时间内完成 Enqueue 和 Dequeue 运算。执行一 系列的入队与出队运算,将使整个队列在循环数组中按顺时针方向移动。通常,用队尾游标 Q.rear 指 向队尾元素所在的单元,用队头游标 Q.front 指向队头元素所在单元的前一个单元,并且约定只能存 放 maxsize-1 个元素如图 3 所示。

图3 此时队列的定义如下: const m=maxsize-1 type cyclicquetp=record elem:array[0..m] of elemtp; rear,front:0..m; end; var sq:cyclicquetp; 这时 当 sq.rear=sq.front 时队空 先 sq.rear=( sq.rear+1) mod maxsize 当 (sq.rear+1) mod maxsize=sq.front 时队满 后进队

先 sq.front=(sq.front+1)mod maxsize 后出队 队列中元素的个数(sq.rear-sq.front+maxsize) mod maxsize 4.3 队列的应用 例 1:一矩形阵列由数字 0 到 9 组成,数字 1 到 9 代表细胞,细胞的定义为沿细胞数字上下左右还是细胞 数字则为同一细胞,求给定矩形阵列的细胞个数。 如:阵列 0234500067 1034560500 2045600671 0000000089 有 4 个细胞。

算法步骤:

1. 从文件中读入 m*n 矩阵阵列,将其转换为 boolean 矩阵存入 bz 数组中; 2. 沿 bz 数组矩阵从上到下,从左到右,找到遇到的第一个细胞; 3. 将细胞的位置入队 h,并沿其上、下、左、右四个方向上的细胞位置入队,入队后的位置 bz 数组 置为 FLASE; 4. 将 h 队的队头出队,沿其上、下、左、右四个方向上的细胞位置入队,入队后的位置 bz 数组置为 FLASE; 5. 重复 4,直至 h 队空为止,则此时找出了一个细胞; 6. 重复 2,直至矩阵找不到细胞; 7. 输出找到的细胞数。 程序: program xibao; const dx:array[1..4] of -1..1=(-1,0,1,0); dy:array[1..4] of -1..1=(0,1,0,-1); var int:text; name,s:string; pic:array[1..50,1..79] of byte; bz:array[1..50,1..79] of boolean; m,n,i,j,num:integer; h:array[1..4000,1..2] of byte; procedure doing(p,q:integer); var i,t,w,x,y:integer; begin inc(num);bz[p,q]:=false; t:=1;w:=1;h[1,1]:=p;h[1,2]:=q;{遇到的第一个细胞入队} repeat for i:=1 to 4 do{沿细胞的上下左右四个方向搜索细胞} begin x:=h[t,1]+dx[i];y:=h[t,2]+dy[i]; if (x>0) and (x<=m) and (y>0) and (y<=n) and bz[x,y]

then begin inc(w);h[w,1]:=x;h[w,2]:=y;bz[x,y]:=false;end;{为细胞的入队} end; inc(t);{队头指针加 1} until t>w;{直至队空为止} end; begin fillchar(bz,sizeof(bz),true);num:=0; write('input file:');readln(name); assign(int,name);reset(int); readln(int,m,n); for i:=1 to m do begin readln(int,s); for j:=1 to n do begin pic[i,j]:=ord(s[j])-ord('0'); if pic[i,j]=0 then bz[i,j]:=false; end; end; close(int); for i:=1 to m do for j:=1 to n do if bz[i,j] then doing(i,j);{在矩阵中寻找细胞} writeln('NUMBER of cells=',num);readln; end. 练习: 如下图: 求图中被*围成的封闭区域的面积 (方格的个数不包括*所在的方格, 且*不在最外一层) 。

* * * * * * * * * * * * * * * * * * * * * * * * * * * * *

第五章 树和二叉树
5.1 树的概念 5.2 二叉树 5.3 二叉树的应用 5.1 树的概念 树的递归定义如下:(1)至少有一个结点(称为根)(2)其它是互不相交的子树

1.树的度——也即是宽度,简单地说,就是结点的分支数。以组成该树各结点中最大的度作 为该树的度,如上图的树,其度为 3;树中度为零的结点称为叶结点或终端结点。树中度不为零的 结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。 2.树的深度——组成该树各结点的最大层次,如上图,其深度为 4; 3.森林——指若干棵互不相交的树的集合,如上图,去掉根结点 A,其原来的二棵子树 T1、 T2、T3 的集合{T1,T2,T3}就为森林; 4.有序树——指树中同层结点从左到右有次序排列,它们之间的次序不能互换,这样的树称 为有序树,否则称为无序树。 5.树的表示 树的表示方法有许多,常用的方法是用括号:先将根结点放入一对圆括号中,然后把它的子 树由左至右的顺序放入括号中,而对子树也采用同样的方法处理;同层子树与它的根结点用圆括 号括起来,同层子树之间用逗号隔开,最后用闭括号括起来。如上图可写成如下形式: (A(B(E(K,L),F),C(G),D(H(M),I,J))) 5. 2 二叉树

1.二叉树的基本形态: 二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态:

(1)空二叉树——(a); (2)只有一个根结点的二叉树——(b); (3)右子树为空的二叉树——(c); (4)左子树为空的二叉树——(d); (5)完全二叉树——(e) 注意:尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形。 2.两个重要的概念: (1)完全二叉树——只有最下面的两层结点度小于 2, 并且最下面一层的结点都集中在该层最 左边的若干位置的二叉树; (2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。 如下图:

完全二叉树

满二叉树

3.二叉树的性质 (1) 在二叉树中,第 i 层的结点总数不超过 2^(i-1); (2) 深度为 h 的二叉树最多有 2 -1 个结点(h>=1),最少有 h 个结点; (3) 对于任意一棵二叉树,如果其叶结点数为 N0,而度数为 2 的结点总数为 N2, 则 N0=N2+1; (4) 具有 n 个结点的完全二叉树的深度为 int(log2n)+1 (5)有 N 个结点的完全二叉树各结点如果用顺序方式存储,则结

推荐相关:

信息技术竞赛辅导计划

信息技术竞赛辅导计划赖素琴 一、指导思想 信息技术学科竞赛是一项益智性的竞赛活动, 核心是考查选手的 智力和使用计算机解题的能力。同时也是提高学生信息素养,检验...


信息技术竞赛辅导

信息技术竞赛辅导_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 信息技术竞赛辅导_学科竞赛_高中教育_教育专区。信息技术竞赛辅导 目录 ? ? ?...


信息技术奥赛培训的一点体会

2、 重视程度: 信息技术奥赛要出成绩不容易,不仅仅在于比赛的难度,还在于我们的重视不够。这个重视不仅仅是在于 辅导老师和学生个人,也在于学校,学部,班主任老师...


信息技术竞赛培训教程

信息技术竞赛培训教程_其它技巧_PPT制作技巧_PPT专区。信息技术竞赛培训教程广州...以下为参考程序: const ju:array[1..8,1..8] of 0..1=( (1,0,0,0...


2015初中信息技术基本功竞赛试卷20151012试题(含参考答案)

2015初中信息技术基本功竞赛试卷20151012试题(含参考答案)_学科竞赛_初中教育_教育专区。中国教育技术协会信息技术教育专业委员会机密★考试结束前 第四届全国初中信息...


信息技术教师基本功大赛教学理论部分试题及参考答案

信息技术教师基本功大赛教学理论部分试题及参考答案_电脑基础知识_IT/计算机_专业资料。信息技术教师基本功大赛教学理论部分试题及参考答案 1、信息技术教育的主要任务和...


信息技术辅导学生计划

信息技术辅导学生计划_学科竞赛_初中教育_教育专区。信息技术辅导学生计划信息技术辅导学生计划通过上学期和现在开学仅不到两周的时间对两个班学生的了解, 最主要的是...


信息学奥赛(初赛)辅导教材

信息学奥赛(初赛)辅导教材_学科竞赛_高中教育_教育专区。信息学奥赛(初赛)辅导教材 信息学(计算机)奥林匹克竞赛辅导教程 浙江金华第一中学 《信息技术》教研组 ...


信息技术教师基本功大赛教学理论部分试题及参考答案

信息技术教师基本功大赛教学理论部分试题及参考答案_学科竞赛_小学教育_教育专区。信息技术教师基本功大赛教学理论部分试题及参考答案 1、信息技术教育的主要任务和目标...


《中小学信息技术课程指导纲要(试行)》解读

《中小学信息技术课程指导纲要(试行)》解读_学科竞赛_小学教育_教育专区。信息技术《中小学信息技术课程指导纲要(试行) 》解读中小学信息技术课程发展历程 20 世纪 ...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com