课程内容：
计算机软件的基础知识 ——— 数据结构课时安排：
数据结构 —— 32学时
上机 —— 12学时
16,17,18周，周一晚（ 5,00~9,00）
信息学院软件中心（计算机系二楼）
教材：
数据结构基础 曹桂琴 大工参考书：
数据结构 严蔚敏 清华第一章 绪言
§ 1.1 什么是数据结构程序 =数据结构 +算法
例 1 书目自动检索系统登录号：
书名：
作者名：
分类号：
出版单位：
出版时间：
价格：
书目卡片
0 0 1 高等数学 樊映川 S 0 1
0 0 2 理论力学 罗远祥 L 0 1
0 0 3 高等数学 华罗庚 S 0 1
0 0 4 线性代数 栾汝书 S 0 2
…… …… …… ……
书目文件按书名 按作者名 按分类号高等数学 001,003 ……
理论力学 002,……,.
线性代数 004,……
…… ……,.
樊映川 001,…
华罗庚 002,…,
栾汝书,…,
……,……,
L 002,…
S 0 0 1,0 0 3,
…… ……
索引表线性表
例 2 人机对奕问题 树
……..……..
…..,…..,…..,…...
多叉路口交通灯管理问题
C
E
D
A
B
AB AC AD
BA BC BD
DA DB DC
EA EB EC ED
图
数据结构定义,是一门研究 非数值计算 的程序设计问题中计算机的 操作对象 以及它们之间的 关系和 操作 等等的学科
§ 1.2 基本概念和术语
数据（ data)— 所有能输入到计算机中去的 描述客观事物的符号
数据元素（ data element） — 数据的 基本单位,
也称节点（ node） 或记录（ record）
数据项（ data item） — 有独立含义的数据 最小单位,也称域 (field)
数据结构（ data structure)— 数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据结构
（集合） —— 数据元素间除“同属于一个集合”外，无其它关系线性结构 —— 一个对一个，如线性表、栈、队列树形结构 —— 一个对多个，如树图状结构 —— 多个对多个，如图
数据的逻辑结构 — 只抽象反映数据元素的 逻辑关系
数据的存储（物理）结构 — 数据的逻辑结构在计算机 存储器中的实现数据的逻辑结构与存储结构密切相关算法设计 逻辑结构算法实现 存储结构存储结构分为：
顺序 存储结构 —— 借助元素在存储器中的 相对位置 来表示数据元素间的逻辑关系链式 存储结构 —— 借助指示元素存储地址的 指针 表示数据元素间的逻辑关系元素 n
……..
元素 i
……..
元素 2
元素 1L
o
Lo+m
Lo+(i-1)*m
Lo+（ n-1)*m
存储地址 存储内容
Loc(元素 i)=Lo+（ i-1)*m
顺序存储
1536元素 21400元素 1 1346元素 3 ∧元素 4
1345
h
存储地址 存储内容 指针
1345 元素 1 1400
1346 元素 4 ∧
……,……,,……,
1400 元素 2 1536
……,……,,……,
1536 元素 3 1346
链式存储
h
数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：
数据类型 — 高级语言中指数据的 取值范围 及其上可进行的 操作 的总称例 C语言中，提供 int,char,float,double等基本数据类型,数组、结构体、共用体、枚举等 构造数据类型,还有指针、空 (void)类型等。用户也可用 typedef 自己定义数据类型
typedef struct
{ int num;
char name[20];
float score;
}STUDENT;
STUDENT stu1,stu2,*p;
§ 1.3 算法的描述和算法分析简介
算法（ algorithm） — 解决某一特定问题的 具体步骤的描述,是指令的有限序列
算法特性 —
输出一个算法有零个或多个—输出输入一个算法有零个或多个—输入算法是能行的—可行性义性切定义的，不能产生二算法的每一步必须是确确定性限步骤之后结束一个算法必须在执行有有穷性
—
—
算法的描述 — 采用 C语言
算法的评价 — 衡量算法优劣的标准
正确性 (correctness)
可读性 (readability)
健壮性 (robustness)
效率与低存储量算法效率 —— 用依据该算法编制的程序在计算机上执行所 消耗的时间 来度量
1.事后统计 —— 利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分缺点,?必须先运行依据算法编制的程序
所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣
2.事前分析估计 —— 一个高级语言程序在计算机上运行所消耗的时间取决于：
依据的算法选用何种策略
问题的规模
程序语言
编译程序产生机器代码质量
机器执行指令速度同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，
效率均不同,——— 所以使用 绝对时间单位 衡量算法效率 不合适
时间复杂度：基本操作重复执行的次数的阶数
T(n)=o(f(n))
空间复杂度,s(n)=o(f(n))
例 1,NXN矩阵相乘
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{c[i][j]=0;
for(k=1;k<=n;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
}
3
3)(
nOnT
nnf