恭贺开版--发个<数据结构电子教案>

ysfabm · 发表于 2006-4-8 13:23

第九章查找
在英汉字典中查找某个英文单词的中文解释；在新华字典中查找某个汉字的读音、含义；在对数表、平方根表中查找某个数的对数、平方根；邮递员送信件要按收件人的地址确定位置等等。可以说查找是为了得到某个信息而常常进行的工作。
计算机、计算机网络使信息查询更快捷、方便、准确。要从计算机、计算机网络中查找特定的信息，就需要在计算机中存储包含该特定信息的表。如要从计算机中查找英文单词的中文解释，就需要存储类似英汉字典这样的信息表，以及对该表进行的查找操作。本章将讨论的问题即是“信息的存储和查找”。
查找是许多程序中最消耗时间的一部分。因而，一个好的查找方法会大大提高运行速度。另外，由于计算机的特性，象对数、平方根等是通过函数求解，无需存储相应的信息表。

ysfabm · 发表于 2006-4-8 13:24

第10章排序
10.1基本概念
排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。作为排序依据的数据项称为“排序码”，也即数据元素的关键码。为了便于查找，通常希望计算机中的数据表是按关键码有序的。如有序表的折半查找，查找效率较高。还有，二叉排序树、B-树和B+树的构造过程就是一个排序过程。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可能不唯一，这是因为具有相同关键码的数据元素，这些元素在排序结果中，它们之间的的位置关系与排序前不能保持。
若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。

排序分为两类：内排序和外排序。
内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。
外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。