• 例2告诉我们：
解决问题方法的效率与空间的利用效率有关
• 例3告诉我们：
解决问题方法的效率与算法的巧妙程度有关
复杂问题实例
• Ex: Network Connectivity (网络连通性)
1. 如何存储和表示 网络的结构？
2. 如何确认两个节
点的连通性，最 短路径是什么？ 3. ……
A
B
1.2 什么是数据结构
int i ; double p = a[0]; for ( i = 1; i <= n; i++) p += a[i] * pow(x, i); return p;
}
f(x) = a0 + a1x + … + an-1xn-1 + anxn
f(x) = a0 + x*(a1 + x*(… ( an-1 + x*(an))…))

新进一本《三体》……
需要移动大量图书 ，才能腾出空的位 置！

操作2：如何查找指定的图书？

二分查找！
可行！
例1：图书摆放问题 方法3：在书架中划分区域，各分区指定摆放 某类图书；并且，在每个分区内，按照书名的 首字母拼音顺序摆放。

操作1：新书如何插入？

可行！
先定类别，二分查找位置，再移出空位，插入新书
void main() { int N; cin>> N; PrintN(N); } 递归实现
循环实现
N = 100
N = 100000
启示
• 例1告诉我们：
解决问题方法的效率与数据的组织方式有关
• 例2告诉我们：
解决问题方法的效率与空间的利用效率有关
例3：多项式求值
方法1：double f1 ( int n, double a[], double x) {
平时成绩：出勤、课堂表现、作业情况、实
验情况及实验报告等
上机实验
实验一
线性表的基本运算及多项式的算术运算
实验二
二叉树的基本操作及哈夫曼编码和译码系统的实现
实验三
图的基本运算及飞机换乘次数最少问题
实验四
基本内排序算法的验证和性能比较、改进快速排序算法
教材及主要参考书 1、教材 《数据结构——使用C++语言描述》（第2版），陈慧 南，人民邮电出版社，2008年

操作2：如何查找指定的图书？

先确定类别，再二分查找！
可行！
• 问题：分区空间大小如何分配？分区粒度多细？
启示
• 例1告诉我们：
解决问题方法的效率与数据的组织方式有关
例2：顺序打印1到N之间的全部正整数
• 循环实现
void PrintN ( int N )d PrintN ( int N )
(4) 更新操作——修改数据结构中某个指定元素的值； (5) 搜索操作——在数据结构中搜索满足一定条件的元素； (6) 遍历操作——按照某种次序，系统的访问数据结构的各 个元素，使得每个元素恰好被访问一次。
……
1.3 抽象数据类型 (Abstract Data Type)
•
1.2.4 数据结构的运算 数据类型
2、主要 参考书
（1）《数据结构(用面向对象方法及C++描述)》，殷 人昆等，清华大学出版社 （2）Data Structures,Algorithms andApplications in C++, Sartaj Sahni, 机械工业出版社 （3）Data Structures with C++, Wlliam Ford, 清华大 学出版社
• 数据对象在计算机中的组织方式

逻辑结构
物理存储结构

• 数据对象必定与一系列加在其上的操作相关联
• 完成这些操作所用的方法即为算法
1.2 什么是数据结构
四种基本逻辑结构
(a) 集合结构
(b) 线性结构
(c) 树形结构
(d) 图状结构
1.2 什么是数据结构
数据的存储结构
Ex：四个连续的元素（ a0, a1, a2, a3 ）的数据结构
优效率的算法。
-------- 中文维基百科
1.1 算法和数据结构
数据结构和算法是计算机学科的基础之一，更是 软件技术的基础。
“Algorithms + Data Structures = Programs ” ─ Niklaus Wirth • 1984 Turning Award • Pascal 之父
数据结构A
南京邮电大学计算机学院
计算机科学与技术系 戴华 daihua@ 2016/7/24
课程的主要内容、考核方式
主要内容：讨论线性表、栈和队列、数组和字符串、
二叉树和树、搜索树、散列表、图和文件等常见的数 据结构.
考核方式：

闭卷考试 期末占70%+平时占30%
逻辑结构：
a0 → a1 →a2 →a3
存储结构
顺序表： 链接表：
a0
a1
a2
a3
1.2 什么是数据结构
数据结构的操作
逻辑结构描述了数据的静态性，操作给出了数据被使用的 方式，即数据的动态性。常见的操作有： (1) 创建操作——创建一个数据结构； (2) 插入操作——在数据结构中插入一个新元素；
(3) 删除操作——将数据结构中的某个指定元素的删除；
MAXN

i 0
i ( x)
i
f (1.1) i (1.1)i
i 0
10
clock_tbegin, end; doubleduration; #defineMAXN 120000 //多项式最大项数 int main() { int i; doublea[MAXN]; //存储多项式的系数 for (i = 0; i < MAXN; i++) a[i] = (double) i; begin = clock(); f1(MAXN - 1, a, 1.1); end = clock(); printf("ticks1 = %f\n", (double) (end - begin));
例1：图书摆放问题
图书摆放问题中的2个常用操作：

操作1：新书如何插入？

操作2：如何找到指定的图书？
例1：图书摆放问题 方法1：随意摆放

操作1：新书如何插入？

Easy!
哪里有空位就放哪里，一步到位。

操作2：如何找到制指定的图书？
例1：图书摆放问题 方法2：按书名的拼音首字母顺序摆放

操作1：新书如何插入？
{ if ( N ) { PrintN ( N – 1 ); cout<< N<<endl; } return ; }
for ( i = 1; i < N; i ++) {
cout<< i<<endl; } return ; }
N = 100, 1000, 10000, 100000, …
例2：顺序打印1到N之间的全部正整数

Matrix Create(int M, int N): 返回一个M*N的空矩阵； int GetMaxRow(Matrix A)：返回矩阵A的总行数； int GetMaxCol(Matrix A)：返回矩阵A的总列数；
ElementType GetEntry(Matrix A, int i, int j)：返回矩阵A第i行、第j列元素；
1.5 算法分析的基本方法
算法的时间复杂度：程序运行从开始到结束所需的时间
手柄转动
的次数！
1.5 算法分析的基本方法
1.5.2 算法的时间复杂度 如何度量算法的时间复杂度？ 程序步：
一个程序步是指在语法上或语义上有意义
的程序段，该程序段的执行时间与具体执行环 境无关。
1.5 算法分析的基本方法
1.5.2 算法的时间复杂度
Ex: 程序1.3 求一个数组元素的累加之和 float sum(float list[],const int n) { float tempsum=0.0; for(int i=0;i<n;i++) tempsum+=list[i]; return tempsum; } 程序语句
一次执行所需 执行频度 程序步数 程序步数 float tempsum=0.0; 1 1 1 for(int i=0;i<n;i++) 1 n+1 n+1 tempsum+=list[i]; 1 n n return tempsum; 1 1 1 2n+3 总程序步数
1.1 算法和数据结构
数据结构（Data Structures）是一门研究非数值计算的 程序设计问题中的操作对象，以及它们之间的关系和操作等 相关问题的学科。 算法（Algorithms）是解决特定问题求解步骤的描述，在 计算机中表现为指令的有限序列，并且每条指令表示一个或
多个操作。
例1：图书摆放问题
1.5.1 算法及其性能标准
算法(Algorithm)：是解决特定问题求解步骤的描述，在计算机中 表现为指令的有限序列，并且每条指令表示一个或多个操作。
算法的五个特征：
(1)输入 (2)输出 有零个或多个输入 至少产生一个输出
(3)确定性 每一条指令都有确切的定义，没有二义性 (4)可行性 可以通过已经实现的基本运算执行有限次来实现 (5)有穷性 算法必须总能在执行有限步之后终止
准备：复习C++的相关内容，如指针、模板等。