存储结构不同于逻辑结构，与计算机 的程序设计语言有关系。
第6页
第1章绪论
数据的存储结构有4种基本的存储表 示方法：
.1 顺序存储方法 .2 链式存储方法 .3 索引存储方法 .4 散列存储方法
第7页
第1章绪论
.1 顺序存储方法
该方法是将相邻的结点用一组连续的 位串来表示，该位串称为结点。结点之 间的逻辑关系由存储单元的邻接关系来 表示，这种存储表示称为顺序存储。
第1章绪论
第17页
第1章绪论
1.7 算法的描述
算法是对特定问题求解的方法和步骤的描
述。
算法的5个重要特性：
1.输入
2.输出
3.有
4.确定性
5.可行性
第18页
第1章绪论
算法的定义： 算法是在有限的时间内，解决某一格问题
的一系列逻辑步骤。
第19页
第1章绪论
第二章 算法分析 对于同一个问题可以构造不同的算法。 因此，选取一个合适的算法就涉及到 如何评价算法好坏的问题。
for( j=1;j<=n;++j) /* n *2 / c[i][j]=0; /* n2 */ 当n充分大时，该两重循环算法时间复杂
度为：T(n)=O(n2)
第26页
例4.一个矩阵相乘 c=a*b
void mult(int a[],int b[],int& c[]) {
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]+=a[i,k]*b[k,j];}
算法效率的衡量方法通常有两种方法: .事后统计法 缺点：1．必须执行程序
2．其它因素掩盖算法本质 .事前分析估算法 本教材涉及的仅是事前分析估算法。第23页
第1章绪论
算法中实现基本操作的语句(基本语句)重 复执行的次数，称为算法的时间复杂度。
记作：T(n)=O(f(n)) 随问题规模n的增大，算法的频度T(n)和 f(n)的增长率同阶。算法执行时间的增长率 和f(n)的增长率相同。
第20页
第1章绪论
一个好的算法具有以下5个特征： (1) 算法是正确的 (2) 执行算法所耗费的时间少，效率问题。 (3) 执行算法所耗费的空间少。 (4) 算法易于理解，具有可读性，易于编码，
易于调试。 (5) 健壮性，对非法或错误数据作出适当的
反应。
第21页
第1章绪论
我们主要讨论算法的时间特性，既算法的 执行效率问题。
算法的时间特性用时间复杂度来表示。 算法消耗的计算机时间是该算法的所有语 句执行时间之和，而每条语句的执行时间是 该语句的执行次数和执行一次所需时间的乘 积。 算法分析是学习数据结构的重要基本功。
第22页
第1章绪论
任何算法所花费的运行时间总是取决于 它所处理的数据量。
一个算法的运行时间是数据输入量的一 个函数。
第9页
第1章绪论
例1-2 有一个数据结构如下： A=（D，S） D={a,b,c,d,e} S={<a,b>,<b,c>,<c,d>,<d,e>} 设第一个结点的存储单元地址为1000， 每个结点占用的存储单元个数为1，其存储 结构如下：
存储单元 a b c d e
地址 1000 1001 1002 1003 1004
第24页
第1章绪论
例1： x+=5; 单个语句的频度为1，则程序段的时间复 杂度为T(n)=O(1)。 例2： for(i=0;i<=n;i++)
j=j+i; 单循环语句的频度为n，则程序段的时间 复杂度为T(n)=O(n)。
第25页
第1章绪论
例3 for(i=1;i<=n;++i) /* n */
解：上述表达式可用图形表示为：线 性结构:
bc a e
fd
第4页
例3：S=(D, R) D={di | 1≤i≤5} R={(di , dj ), i<j}
解：上述表达式可用图形表示为：
第1章绪论
d2
d1 d4
d3
非线性结构
d5
第5页
第1章绪论
1.5 数据的存储结构
数据的存储结构是数据的逻辑结构在 计算机内部的表示或实现，又称为数据 的物理结构。它包括数据元素的表示和 关系的表示。
时间复杂度:T(n)=O(n )2
第28页
第1章绪论
从算法中选取一种对于所研究的问题 来说是基本操作的原操作，以该基本操 作在算法中重复执行的次数作为算法运 行时间的衡量准则。
算法的时间复杂度由嵌套最深层语句 的频度决定
第29页
第1章绪论
时间复杂度T(n)按数量级按递增顺为： 常数阶O(C)﹤对数阶O(log n)﹤线性
第15页
第1章绪论
1.6 数据的运算
数据的运算式定义在数据的逻辑结构上的， 每种数据的逻辑结构都有一个运算的集合。 是施加在该数据元素的一系列抽象的操作。
抽象的操作是指只知道这些操作要“做什 么”，而无需考虑“如何做”，只有在确定 了数据结构之后，才考虑如何去实现这些操 作。
第16页
数据的运算式主要包括： (1)查找 (2)插入 (3)删除 (4)修改 (5)排序
{ change = FALSE; /*change 为元素进行交换标志*/
for ( j=0;j<i;++j)
if (a[j]>a[j+1])
{ a[j]←→a[j+1];change=TRUE ;}
}
}
基本操作: 交换赋值操作
最好的情况:交换0次.
最坏的情况:交换(n-1)+(n-2)+…+1=n(n-1)/2次
>} 地址 数据 指针
链1式000 存45储存1030储结构如下：
100 63 100 97 67 63 45 14∧
1
0
100 67 100
2
1
(b) 逻辑结构
1(0a0) 存1储4 结构∧
3
第13页
第1章绪论
.3 索引存储方法 除了有基本表之外，还需要建立索引 表。
第14页
第1章绪论
.4 散列存储方法 根据结点中关键字的值，直接计算出 其物理存储地址。
2
阶O(n)﹤线性对数阶O(nlog n)﹤ 2
平方阶O(n )2 ﹤立方阶O(n )3﹤ 指数阶O(2 )n。
第30页
它主要用于线性的数据结构，而非线 性的数据结构必须通过某种线性化的过 程后，采用顺序存储。
第8页
第1章绪论
顺序存储结构的主要特点： (1)结点中只有自身信息，没有链接信息。
存储空间利用率高。 (2)可以用过计算直接确定数据结构中的任
意结点i的存储地址。 Li=L0+(i-1)*m 其中： L0为第一个结点的存储位置； m为每个结点所占用的存储单元个数。 (3)插入和删除都会引起大量的结点移动。
第1章绪论
1.4 数据的逻辑结构 1.数据结构形式定义
数据结构在形式上可以定义为一个二 元组: Data_Structures=(D,S) 其中: D 是数据元素的有限集，
S 是D上关系的有限集。 数据结构由两部分组成: (1) 数据元素的集合D (2) 数据元素之间关系的集合S。
第1页
第1章绪论
的指针。
第11页
第1章绪论
链式存储结构的主要特点： (1)结点中有自身信息，还有辑上相邻的结点，物理存储地址
不必相邻。 (3)插入和删除结点,方便灵活。
第12页
例1-2 有一个数据结构如下： A=（D，S） D={45,63,67,14,97}
第1章绪论
S={<97,67>,<67,63>,<63,45>,<45,14
S21，S23，S31，S32，S41，S42}
第2页
第1章绪论
R表示小组成员(教授、研究生和本科生) 它们的关系有两种：R={R1,R2}. R1={<T，Gi)|1≦i≦n,1≦n≦4} R2={<Gi,Sij>)|1≦i≦n,1≦j≦m,
1≦n≦4, 1≦m≦2}
第3页
第1章绪论
例2:用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。 S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a),(e,f), (f,d)}
例1：设计一个事物管理的程序：每个课 题由一个教授、1~4名研究生和1~8名本科 生组成，一个教授指导1---4名研究生，每 位研究生指导1---8名本科生，我们得到一 个数据结构：
Group=(P,R)
其中：P表示数据元素，教授、研究生和 本科生；
即P={T，G1，G2，G3，G4，S11，S12，
第10页
第1章绪论
.2 链式存储方法
该方法是不要求逻辑上相邻的结点在物理
存储位置上也相邻。结点之间的逻辑关系由
结点中的附加信息—指针来表示，指针指向
节点的相邻结点。该种存储方法称为链式存
储结构。
该存储方法中的结点由两部分组成：
一部分存储结点本身的值，成为数据域；
另一部分存储该结点的直接前驱或直接后继
}
基本操作: 乘法操作. 时间复杂度: O(n )3
第1章绪论
第27页
例5. 冒泡排序
第1章绪论
void bubble_sort(int& a[], int n)
/* 将a中整数序列重新排列成自小至大有序的整数序列。*/