1.《数据结构》讲义.doc

《数据结构》讲义 ——师说教育集团考试教学团队编录—— 绪论 基础知识 概念和术语(黑体字部分)。 另外，注意： 1、数据元素是数据的基本单位。P4 2、数据项是数据不可分割的最小单位。P5 3、数据结构及其形式定义。P5 四种基本结构：①集合②线性结构③树形结构④图（网）状结构 4、数据结构的 逻辑结构（抽象的，与实现无关） 物理结构（存储结构） 顺序映像（顺序存储结构）位置“相邻” 非顺序映像（链式存储结构）指针表示关系P6 5、数据类型 P7 抽象数据类型（ADT）P7 ADT=（数据对象，数据关系，基本操作） ADT细分为原子类型，固定聚合，可变聚合类型。P8 6、算法的概念 P13 7、算法的五个特征 ①有穷性 ②确定性 ③可行性 ④输入（0个或多个） ⑤输出（1个或多个） 8、算法设计的要求：①正确性②可读性③健壮性④效率与低存储量 其中正确性的四个层次（通常要求达到C层）。 9、算法的时间复杂度 P15 常见有： O(1)，O(n)，O(n2)，O(log2n)，O(n log2n)，O(2n) 语句频度，用归纳法计算。 10、算法的空间复杂度 P17 算法 起泡排序。P16 另一种形式 void BubbleSort ( DataType a[], int n ) { for ( i=0; in-1; i++ ) for ( j=0; jn-i-1; j++ ) if ( a[j]a[j+1] ) a[j]—a[j+1]; } 或 void BubbleSort ( DataType a[], int n ) { for ( i=1; in; i++ ) for ( j=0; jn-i; j++ ) if( a[j]a[j+1] ) a[j]—a[j+1]; } 或 void BubbleSort ( DataType a[], int n ) { for ( i=0; in-1; i++ ) { change = fasle; for ( j=0; jn-i-1; j++ ) if ( a[j]a[j+1] ) { a[j]—a[j+1]; change = true; } if ( !change ) break; } } 说明： a) 考试中要求写算法时，可用类C，也可用C程序。 b) 尽量书写算法说明，言简意赅。 c) 技巧：用“边界值验证法”检查下标越界错误。 如上第一个： 第二个循环条件若写作jn-i，则当i=0时 a[j+1]会越界。 d) 时间复杂度为O(n2)，第3个在最好情况下（待排记录有序），时间复杂度为O(n)。 习题 1.1 编写冒泡排序算法，使结果从大到小排列。 1.2 计算下面语句段中指定语句的频度： 1) for ( i=1; i=n; i++ ) for ( j=i; j=n; j++ ) x++; // @ 2) i = 1; while ( i=n )  i = i*2; // @ 线性表 基础知识和算法 线性表及其特点 线性表是n个数据元素的有限序列。 线性结构的特点： ①“第一个” ②“最后一个” ③前驱 ④后继。 顺序表——线性表的顺序存储结构 特点 a) 逻辑上相邻的元素在物理位置上相邻。 b) 随机访问。 类型定义 简而言之，“数组+长度”。 const int MAXSIZE = 线性表最大长度; typedef struct{ DataType elem[MAXSIZE]; int length; } SqList; 注：a) SqList为类型名，可换用其他写法。 b) DataType是数据元素的类型，根据需要确定。 c) MAXSIZE根据需要确定。如 const int MAXSIZE=64; d) 课本上的SqList类型可在需要时增加存储空间，在上面这种定义下不可以。(这样做避免了动态内存分配，明显减少了算法的复杂程度，容易理解。而且，原来Pascal版本的《数据结构》（严蔚敏）就是这样做的。) e) 课本上的SqList类型定义中listsize表示已经分配的空间大小（容纳数据元素的个数）。当插入元素而遇到L.length==L.listsize时，用realloc (L.elem, L.listsize+增量) 重新分配内存，而realloc()函数在必要的时候自动复制原来的元素到新分