高等学校计算机专业教材 数据结构 袁平波 2018.9 课程主页：http://staff.ustc.edu.cn/~ypb

课程情况 60理论课时 30实验课时 课程考核 课堂要求 作业一章提交一次 10次，西区信院机房（电一楼） 周四（8.9.10），第5周开始 考试60-70%，平时（作业，出勤）10%，实验30-20% 6个实验，提交1-2份实验报告，其他实验随堂检查 课堂要求 请假在上课前完成

参考教材 实验指导教材

第二章 数据结构导论 2.2.1基本概念和术语 2.2.3数据类型和抽象数据类型 2.1《数据结构》讨论范畴 2.2《数据结构》相关概念 2.2.2数据结构 2.2.3数据类型和抽象数据类型 2.3算法及其描述和算法分析

2.1《数据结构》研究什么 数据结构的历史 数据结构正是讨论非数值类问题的对象描述、信息组织方法及其相应的操作 1968 美国唐·欧·克努特 设立《数据结构》课程 1976 瑞士 Niklaus Wirth 提出算法+数据结构=程序设计 数据结构正是讨论非数值类问题的对象描述、信息组织方法及其相应的操作 (1) 加工对象逻辑组织（2）存储到计算机 (3)数据运算 [例]、设有一个电话号码薄，有N个人的姓名和电话号码。要求设计一个程序，按人名查找号码，若不存在则给出查找失败的信息。

[例] 下棋 井子棋 非线性数据结构-树

[例] 交叉口交通灯设置（顶点着色问题） 非线性——图

2.2数据结构相关概念 2.2.1基本概念和术语 集合和关系 数据和信息 集合是若干具有共同可辨特征的事物的“聚合”，每个事物称该集合的元素或成员。 集合元素之间一般都具有某种“关系”。 数据和信息 数据是指描述客观事物且能由计算机处理的数值、字符符号的总称 信息是包含在数据中符号的含义。数据是信息的符号表示形式。

数据元素 是数据的基本单位，有时称记录、结点、顶点。其包括数据项（Data Item），数据项可以是原子项（性别）或组合项（出生日期） 数据对象 是性质相同的数据元素的集合，是数据的一个子集 。 关键码（key） 数据元素中起识别作用的数据项。有主次之分，能唯一识别的称主码，否则称次码。

2.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>}

数据的操作：检索、排序、插入、删除、修改等 数据结构的三个方面： 线性表 栈 队列 线性结构 串及数组 数据的逻辑结构 树形结构 非线性结构 图形结构 顺序存储 数据的存储结构 链式存储 数据的操作：检索、排序、插入、删除、修改等

2.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);

2. 3 算法及其描述和算法分析 1、算法:对问题求解的描述，为解决问题给出的一个确定的、有限长的操作序列。 1）正确性 2）具体性 3）确定性 4）有限性 5）可终止性 2、算法效率衡量方法与准则 : 时间复杂度：T（n）=O（f(n)） 空间复杂度：S（n）=O（g(n)）

3、算法的描述:类C语言 预定义常量和类型 内存的动态分配与释放 输入输出 赋值语句 串连、成组、条件赋值 const TRUE=1;typedef int status； 内存的动态分配与释放 new 、Delete 取代malloc和free 输入输出 cin、cout 取代 scanf和printf 赋值语句 串连、成组、条件赋值 变量1=变量2=…=变量n=表达式 (变量1，变量2…变量n)=（表达式1，表达式2,…表达式n） 结构变量={值1，值2,…,值n} 数组变量1[起始下标..截止下标]=数组变量2[起始下标..截止下标]

“O” 的形式定义 若f(n)是正整数n的一个函数，则xn＝O(f(n))表示存在一个正的常数M，使得当nn0时都满足|xn|M|f(n)|； 换句话就是说这当整型自变量n趋向于无穷大时， xn和f(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） 、f(n)=2n3+5n2+7n+c;（c为某一常数），则 T（n）=O（n3）。

可变 时间复杂度 （输入有关）最坏，最好，平均 [例] 起泡排序 void bubble_sort(int a[], int n){ for (i=n-1, change=TRUE; i>0 && 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) 可变 时间复杂度 （输入有关）最坏，最好，平均

常见函数的增长率