数据结构_绪论.pptVIP

姜斌 whkunyushan@163.com 答疑时间：每周四下午1、2节 Why? What is DS? How? #includeiostream.h//输入三个数，按从小到大顺序排出 void main() { float a,b,c,t; cinabc; if(ab) {t=a;a=b;b=t;} if(ac) {t=a;a=c;c=t;} if(bc) {t=b;b=c;c=t;} couta\nb\nc\n; } 第1章 绪论 计算机，顾名思义，无非就是进行计算的机器。而计算则离不开数据，所以研究数据的组织、存储和传送就成为计算机科学中最重要的内容之一，也就是我们数据结构课程要讨论的中心问题。 1.1 什么是数据结构 一般来说，用计算机解决一个具体问题时，大致需要经过下列几个步骤： 首先要从具体问题出发，抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序，对程序进行调试，直至得到问题的解。 例1-2 计算机和人对弈问题。 1.2 基本概念和术语 简单来说，数据结构可以认为是数据之间的相互关系。在计算机处理数据的过程中，大批量的数据并不是彼此孤立，杂乱无章的，它们之间有内在的联系。只有利用这些客观存在的关系，把各数据元素有机地组织起来，才有可能对这些数据进行处理，或者说才有可能对这些数据进行有效地处理。下面我们对涉及到数据的有关概念给出准确的定义或说明。 例1-4 如表1-1所示是一个图书目录表，是一个需要用计算机进行处理的数据实体。 例1-5 在计算机科学中，复数可取如下定义：复数是一种数据结构 1.3 数据的逻辑结构和存储结构 (1) 顺序存储方式 (2) 链接存储方式 (3) 索引存储方式 (4) 散列存储方式 1.4 抽象数据类型的表示与实现 (1) 原子类型(Automic Data Type) (2) 固定聚合类型(Fixed-aggregate Data Type) (3) 可变聚合类型(Variable-aggregate Data Type) 例1-6 复数的抽象数据类型定义。 1.5 算法和算法分析 1. 时间复杂度(Time Complexity) 例1-7 累加求和。 例1-8 矩阵相加。 2. 空间复杂度(Space Complexity) 习题 1.8 1.11 1.13 void MatrixAdd(int a[N][N],int b[N][N],int c[N][N],int n) //实现矩阵a[n][n]和b[n][n]的加法，其和存入c[n][n]中 { int i,j; for(i=0;in;i++) for(j=0;jn;j++) c[i][j]=a[i][j]+b[i][j]; } 第1句是说明语句，运行时不做任何操作。第2句是一个两重循环 为了简化图的表示，我们将x,y和y,x这两个对称序偶用一个无序对(x,y)或(y,x)来代替。这样就可以把x结点和y结点之间两条相反的有向边用一条无向边来代替，如图1.7所示。这样，关系可以改写为 r={(1,2),(1,4),(2,3),(2,6),(2,7), (3,7),(4,6),(5,7)} 从图形结构、树形结构和线性结构的关系可以看出，树形结构是图形结构的特殊情况，线性结构是树形结构的特殊情况。为了区别于线性结构，我们把树形结构和图形结构统称为非线性结构。 前面都是从逻辑上观察分析数据元素之间的关系。但数据结构需要用计算机处理，必须把数据结构存入计算机的存储单元中。数据结构在计算机中的表示（又称映象），称为数据的存储结构或物理结构，它包括数据元素的表示和关系的表示。 怎样既能合理的利用有限的存储空间，又能对数据结构进行有效地处理，这就是存储结构要讨论的问题。计算机的存储器是由很多存储单元（byte或word）组成的，每个存储单元都有唯一的地址。各存储单元的地址编码是线性连续的，即每一个存储单元有唯一的前驱单元和后继单元。我们把两个互为前驱和后继的存储单元成为相邻存储单元，把一片相邻的存储单元称为存储区域。 一般情况下，一个结点所占用的空间并不止一个存储单元，不同类型的结点所占用的存储单元数量也各不相同。除了要保存结点的值以外，还必须保存结点之间的相互关系。为了体现结点之间的关系，通常有以下四种常用的存储表示方法： 顺序存储方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。通常顺序存储结构是借助于程序设计语言的向量来表示的。 顺