文档介绍：课程简介:
计算机软件的基础知识———数据结构
课时安排:
数据结构——52学时
上机——12学时
课程设计——18周(1周时间)
教材:
数据结构C语言版严蔚敏吴伟民(清华)
参考书:
数据结构及应用算法教程严蔚敏(清华大学出版社)
数据结构尹人昆(清华大学出版社)
课程介绍
数据结构在课程体系中的地位
程序设计基础
高级程序设计
离散数学
Data Structure
数据库原理
操作系统
软件工程
……
第一章绪论
什么是数据结构
记住一个公式:程序=数据结构+算法
第一章绪论
书目文件
按书名
按作者名
按分类号
索引表
线性表
树
●
●
●
●
●
●
●
●
●
●
●
●
第一章绪论
图
A
B
C
D
E
F
G
H
I
居民区示意图
A
B
C
D
E
F
G
H
I
铺设煤气管道设计图
第一章绪论
多叉路口交通灯管理问题
C
E
D
A
B
AB
AC
AD
BA
BC
BD
DA
DB
DC
EA
EB
EC
ED
图
算法(algorithm)—解决某一特定问题的具体步骤的描述,是指令的有限序列;
算法的描述(伪代码)
算法设计的要求
正确性(correctness):功能必须正确
可读性(readability):通过注释、分块等完成
健壮性(robustness):能经受非法操作的检验
高效:高速度、低存储
第一章绪论
算法和算法分析
算法效率:依据算法编制的程序在计算机上执行所消耗的时间
算法转化成的程序在计算机上运行所消耗的时间取决于:
硬件的速度
书写程序的语言
问题的规模
编译程序产生机器代码质量
机器执行指令速度
同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行,效率均不同,———所以使用绝对时间单位衡量算法效率不合适,采用时间复杂度比较合适
第一章绪论
算法和算法分析
时间复杂度:基本操作(元操作)重复执行的次数的阶数 T(n)=o(f(n))
例1:N*N矩阵相乘
void mult_matrix(int c[][],int a[][],int b[][],int n)
{//a、b、c均为n阶方阵,c为a和b的乘积
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{ c[i][j]=0;
for(k=1;k<=n;k++)
s=s+a[i][k]*b[k][j];
}//mult_matrix
第一章绪论
算法和算法分析