文档介绍：算法与数据结构
Alita Chang
编写解决实际问题的程序的一般过程:
如何用数据形式描述问题?—即由问题抽象出一个适当的数学模型;
问题所涉及的数据量大小及数据之间的关系;
如何在计算机中存储数据及体现数据之间的关系?
处理问题时需要对数据作何种运算?
所编写的程序的性能是否良好?
计算机求解问题的一般步骤
数据结构的例子
姓名
电话号码
陈海
**********
李四锋
**********
。。。
。。。
例1:电话号码查询系统
设有一个电话号码薄,它记录了N个人的名字和其相应的电话号码,假定按如下形式安排:(a1, b1),(a2, b2),…(an, bn),其中ai, bi(i=1,2…n) 分别表示某人的名字和电话号码。本问题是一种典型的表格问题。如表1-1,数据与数据成简单的一对一的线性关系。
表1-1 线性表结构
例2:磁盘目录文件系统
磁盘根目录下有很多子目录及文件,每个子目录里又可以包含多个子目录及文件,但每个子目录只有一个父目录,依此类推:
本问题是一种典型的树型结构问题,如图1-1 ,数据与数据成一对多的关系,是一种典型的非线性关系结构—树形结构。
图1-1 树形结构
例3:交通网络图
从一个地方到另外一个地方可以有多条路径。本问题是一种典型的网状结构问题,数据与数据成多对多的关系,是一种非线性关系结构。
佛山
惠州
广州
中山
东莞
深圳
珠海
图1-2 网状结构
数据(Data) :是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素(Data Element) :是数据的基本单位,在程序中通常作为一个整体来进行考虑和处理。
一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。
数据对象(Data Object):是性质相同的数据元素的集合,是数据的一个子集。如字符集合C={‘A’,’B’,’C,…} 。
基本概念和术语
数据结构(Data Structure):是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型,如图1-3所示。
①集合:结构中的数据元素除了“同属于一个集合”外,没有其它关系。
②线性结构:结构中的数据元素之间存在一对一的关系。
③树型结构:结构中的数据元素之间存在一对多的关系。
④图状结构或网状结构:结构中的数据元素之间存在多对多的关系。
数据结构的形式定义是一个二元组:
Data-Structure=(D,S)
其中:D是数据元素的有限集,S是D上关系的有限集。
例2:设数据逻辑结构B=(K,R)
K={k1, k2, …, k9}
R={ <k1, k3>,<k1, k8>,<k2, k3>,<k2, k4>,<k2, k5>,<k3, k9>,<k5, k6>,<k8, k9>,<k9, k7>,<k4, k7>,<k4, k6> }
画出这逻辑结构的图示,并确定那些是起点,那些是终点
数据结构的形式定义
图1-3 四类基本结构图
数据结构的存储方式
数据元素之间的关系可以是元素之间代表某种含义的自然关系,也可以是为处理问题方便而人为定义的关系,这种自然或人为定义的“关系”称为数据元素之间的逻辑关系,相应的结构称为逻辑结构。
数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。
元素之间的关系在计算机中有两种不同的表示方法:顺序表示和非顺序表示。由此得出两种不同的存储结构:顺序存储结构和链式存储结构。
顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。