高等学校计算机专业教材 数据结构 袁平波 2007.9
第一章 绪论 1.1《数据结构》讨论范畴 1.2《数据结构》相关概念 1.3算法及其描述和算法分析 1.2.1基本概念和术语 1.2.2数据结构 1.2.3数据类型和抽象数据类型 1.3算法及其描述和算法分析
1.1《数据结构》研究什么 (1) 要对所加工的对象进行逻辑组织 (2) 如何把加工对象存储到计算机中去？ (3) 数据运算 数据结构正是讨论非数值类问题的对象描述、信息组织方法及其相应的操作 [例]、设有一个电话号码薄，有N个人的姓名和电话号 码。要求设计一个程序，按人名查找号码，若不存在则给出不存在的信息。
1.2数据结构相关概念 1.2.1基本概念和术语 数据元素、结点、数据项、关键字或主关键字、 次关键字、数据对象、数据结构 1.2.2数据结构 特性相同的数据元素构成的集合中，如果在数据元素之间存在一种或多种特定的关系，则称之为数据结构 。 Data-Structure=(D,S)
[例] linear=(D,R) D={1,2,3,4,5,6,7,8,9,10} R={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>,<6,7>, <7,8>,<8,9>,<9,10>}
[例]tree=（D,R） D={a, b, c, d, e, f, g, h, i, j, k, l} R={<a,b>,<a,c>,<a,d>,<b,e>,<b,f>,<b,g>,<c,h>,<c,i>,<c,j>, <d,k>,<d,l>}
[例] graph=(D,R) D={1, 2, 3, 4, 5, 6, 7, 8, 9} R={<1,2>,<1,3>,<2,4>,<2,5>,<2,6>,<2,8>,<3,2>,<3,4>, <4,5>,<5,7>,<6,7>,<6,9>,<7,9>,<8,9>}
1.2.3数据类型和抽象数据类型 操作结果：〈操作结果描述〉 ADT=（D，S，P） 其中：D是数据对象，用结点的有限集合表示； S是D上的关系的集合，用结点间的序偶的集合来表示； P是对D的基本操作的集合。基本操作的 定义格式为： 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉
操作中的参数有两种 1）赋值参数 void add (int a, int b, int * c){ *c=a +b;} add(2,3,&c); 2）引用参数 void add (int a, int b, int &c){ c=a +b } add(2,3,c);
1. 3 算法及其描述和算法分析 1、算法:对问题求解的描述，为解决问题给出的一个确定的、有限长的操作序列。 1）输入 2）输出 3）有穷性 4）可行性 5）确定性 2、算法的描述:类C语言 3、算法效率衡量方法与准则 : 时间复杂度：T（n）=O（f(n)） 空间复杂度：S（n）=O（g(n)）
“O” 的形式定义 若f(n)是正整数n的一个函数，则xn＝O(f(n))表示存在一个正的常数M，使得当nn0时都满足|xn|M|f(n)|； 换句话就是说这当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。
②、for (i=1;i<=n;i++) {x++;s+=x;} O（n） ③、for( i=1;i<=n;i++) 分析下列三个程序段： ①、x++;s=0; O（1） ②、for (i=1;i<=n;i++) {x++;s+=x;} O（n） ③、for( i=1;i<=n;i++) for (j=1;j<=n; j++) {x++; s+=x;} O（n2） 、T(n)=2n3+5n2+7n+c;（c为某一常数），则 T（n）=O（n3）。
[例] 起泡排序 算法 1.3 void bubble_sort(int a[], int n){ [例] 起泡排序 算法 1.3 void bubble_sort(int a[], int n){ for (i=n-1, change=TRUE; i>1 && change; --i) { change = FALSE; for (j=0; j<i; ++j) if (a[j] > a[j+1]) { w = a[j]; a[j]= a[j+1]; a[j+1]= w; change = TRUE } } } // bubble_sort 时间复杂度O(n2)
常见函数的增长率