文档介绍：七夕，古今诗人惯咏星月与悲情。吾生虽晚，世态炎凉却已看透矣。情也成空，且
作“挥手袖底风”罢。是夜，窗外风雨如晦，吾独坐陋室，听一曲《尘缘》，合成
诗韵一首，觉放诸古今，亦独有风韵也。乃书于纸上。毕而卧。凄然入梦。乙 酉年
七月初七。是两指针：左指针
（ Llink ） 指向前件结点，右指针（ Rlink 〉指向后件结点。
线性链表的基本运算：查找、插入、删除。
6树与二叉树
树是一种简单的非线性结构，所有元素之间具有明显的层次特性。
在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为 树
的根结点， 简称树的根。 每一个结点可以有多个后件， 称为该结点的子结点。 没有后件的 结点称
为叶子结点。
在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为 树 的度。树的最大层次称为树的深度。
二叉树的特点： （ 1） 非空二叉树只有一个根结点： （ 2） 每一个结点最多有两棵子树， 且 分 别称为该结点的左子树与右子树。
二叉树的基本性质：
在二叉树的第 k 层上，最多有2k-l （ ?l ） 个结点：
深度为 m 的二叉树最多有2m-1 个结点：
度为 0 的结点（即叶子结点）总是比度为 2 的结点多一个：
具有 n 个结点的二叉树，其深度至少为 [ log2n] +hH 中 [ log2n] 表示取 log2n 的 整数 部分；
具有 n 个结点的完全二叉树的深度为 [ log2n ] +l ；
设完全二叉树共有n 个结点。如果从根结点开始，按层序（每一层从左到右）用 自
然数 1, 2, 11 给结点进行编号有以下结论：
若 k=l, 则该结点为根结点， 它没有父结点； 若 k>l, 则该结点的父结点编号为 INT （ k/2）：
若 2 匕，则编号为 k 的结点的左子结点编号为 2k ： 否则该结点无左子结点（也无右 子 结点）；
若 2k+lSi, 则编号为 k 的结点的右子结点编号为 2k+l ； 否则该结点无右子结点。
满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则 k 层上有 2k-l 个 结点
深度为 m 的满二叉树有2m-1 个结点。
完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少 右 边的若干结点。
二叉树存储结构采用链式存储结构， 对于满二叉树与完全二叉树可以按层序进行顺序存储。
二叉树的遍历：
前序遍历（ DLR ） ,首先访问根结点，然后遍历左子树，最后遍历右子树；
中序遍历（ LDR ） ,首先遍历左子树，然后访问根结点，最后遍历右子树；
后序遍历（ LRD ） 首先遍历左子树，然后访问遍历右子树，最后访问根结点。
7查找技术
顺序查找的使用情况：
线性表为无序表：
表采用链式存储结构。
二分法查找只适用于顺序存储的有序表，对于长度为 n 的有序线性表，最坏情况只需比 较 log2n 次。
8排序技术
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
交换类排序法： （ 1） 冒泡排序法，需要比较的次数为 n（ n-l ） /2：（2） 快速排序法。
插入类排序法： （ 1） 简单插入排序法，最坏情况需要 n（n-l） /2 次比较： （2） 希尔排序
法 , 最坏情况需要0（ ） 次比较。
选择类排序法： （ 1） 简单选择排序法，
最坏情况需要n（n-l） /2 次比较； （2） 堆排序法，最坏情况需要O （nlog2n） 次比较。
第二章程序设计基础
1 程序设计设计方法和风格
如何形成良好的程序设计风格
1、源程序文档化： 2、数据说明的方法；
3、语句的结构：4、输入和输出。
注释分序言性注释和功能性注释，语句结构清晰第一、效率第二。
2结构化程序设计
结构化程序设计方法的四条原则是： ： ；3?模块化：4?限制使用
goto 语句。
结构化程序的基本结构和特点：
顺序结构：一种简单的程序设计，最基本、最常用的结构：
选择结构：又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断
应该选择哪一条分支来执行相应的语句序列：
重复结构：又称循环结构，可根据给左条件，判断是否需要重复执行某一相同程
序段。
3面向对象的程序设计
面向对象的程序设计：以 60 年代末挪威奥斯陆大学和挪威讣算机中心研制的 SIMULA 语 言为标志。
而向对象方法的优点：
与人类****惯的思维方法一致：
稳定性好；
可重用性好：
易于开发大型软件产品：
可维护性好。
对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体