这是一个讲究效率的世界。在同样的条件下，事物的效率和自身的竞争力、受欢迎程度是成正比的。
计算机科学是一门研究信息的表示和处理的科学。而信息的表示和组织又直接关系到信息处理程序的效率。假如，需要在很多写有姓名的纸张中找出"李某人"，一种笨方法就是一个个筛选对比，这样的效率可想而知。那把这些姓名（数据）制作成带有“A、B、C...”目录的花名册，在根据目录去查找，就能省去很多运算，从而提升效率。
数据结构分为数据的逻辑结构、数据的物理存储结构、对数据的操作（或运算）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。
数据的逻辑结构：数据之间的逻辑关系。其中的逻辑关系是指数据元素之间的前后间关系，而与它们在计算机中的存储位置无关。
数据的物理结构：指数据的逻辑结构在计算机存储空间的表示（映像），分数据元素的机内表示和关系的机内表示。
数据的逻辑结构
根据数据元素之间的关系的不同特性，有4类基本逻辑结构： 集合、线性结构、树型结构、图型结构。
1.集合：数据结构中的元素之间除了“同属一个集合”的相互关系之外，别无其他关系。
集合
2.线性结构：数据结构中的元素之间存在一对一的相互关系。
线性结构
可以用B=(D,R)来表示数据结构。其中B代表一种数据结构，D代表数据，R代表数据之间的关系。上方线性图可以这么写：
L=(D,R)
D={1,2,3,4,5} (这里的顺序不影响数据之间的关系)
R={r}
r={<5,2>,<2,1>,<1,3>,<3,4>} 序偶<x,y>表示数据之间的关系，x是y的前驱，y为x的后继。
线性数据结构的特点是数据之间的一对一的联系。
3.树型结构：数据结构中的元素之间存在一对多的相互关系。
树型结构
T=(D,R)
D={1,2,3,4,5,6,7,8}
R={r}
r={<1,2>,<1,3>,<1,4>,<2,5>,<2,6>,<4,7>,<4,8>}
树型数据结构的特点是数据之间的一对多的联系。
4.图型结构：数据结构中的元素之间存在多对多的相互关系。
图型结构(我觉得还蛮好看的)
G={D,R}
D={1,2,3,4,5,6,7}
R={r}
r={<1,3>,<3,1>,<3,4>,<4,3>,<3,7>,<7,3>,<4,6>,<6,4>,<6,7>,<7,6>,<6,2>,<2,6>,<7,5>,<5,7>,<5,2>,<2,5>,<2,1>,<1,2>}
图型数据结构的特点是数据之间多对多的联系。
数据的物理结构
数据结构在计算机中的表示（映像）称为数据的物理结构，又称为存储结构，它包含数据的机内表示和关系的机内表示。
1.数据的机内表示
用二进制位（bit）的位串来表示数据元素，通常称这个位串为结点。
2.关系的机内表示
数据元素之间关系的机内表示可以分为顺序映像和非顺序映像，常用的两种存储结构：顺序存储结构和链式存储结构。顺序映像借助元素在存储器中的相对位置来表示数据之间的逻辑关系。非顺序映像借助指示元素存储位置的指针来表示数据元素之间的逻辑关系。
顺序存储结构：
顺序存储
数据(1,2,55,64,7)以顺序存储结构存储，首元素1存放在地址为0100的单元中（假设数据占两个字节），第二个元素存放在地址为0102中，以此类推。这种存储方式很容易确定序列中任意一个元素的位置，第n个数据地址可以用0100+（n-1）*2来得出。
链式存储结构：
链式存储
同样的数据(1,2,55,64,7)以链式存储结构存储，其中首元素1存放在地址0108中，第二个元素2的存储位置由首元素的指针域指示出来，地址是0100；第三个元素55的存储位置由第二个元素的指针域指示出来，地址是0104,以此类推。
网友评论