数据结构与算法.ppt

数据结构（DataStructure）树型结构图结构12543第38页,共54页，星期六，2024年，5月数据结构的内容逻辑结构存储结构运算集合第39页,共54页，星期六，2024年，5月1.数据的逻辑结构定义： 数据的逻辑结构是指数据元素之间逻辑关系描述。形式化描述： B=（D,R）其中D是数据元素的有限集，R是D上关系的有限集。根据数据元素之间关系的不同特性，通常分为四类基本的结构集合结构、线性结构、树型结构、图状结构。第40页,共54页，星期六，2024年，5月集合结构定义： 结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。集合例如：第41页,共54页，星期六，2024年，5月线性结构定义： 结构中的数据元素之间存在着一对一的线性关系。例如：线性表第42页,共54页，星期六，2024年，5月树型结构定义： 结构中的数据元素之间存在着一对多的层次关系。例如：树第43页,共54页，星期六，2024年，5月图状结构或网状结构定义： 结构中的数据元素之间存在着多对多的任意关系。例如：图第44页,共54页，星期六，2024年，5月综上所述，数据的逻辑结构可概括为：线性结构——线性表、栈、队、数组逻辑结构非线性结构——树、图逻辑结构第45页,共54页，星期六，2024年，5月逻辑结构的二元组表示B=（D,R）例1.5(P12)例1.6(P12)例1.7(P12)第46页,共54页，星期六，2024年，5月m*n的矩阵是一个线性数据结构Am×n=a12a12┅a1j┅a1na21a22┅a2j┅a2n┇┇ai1ai2┅aij┅ain┇┇am1am2┅amj┅amn第47页,共54页，星期六，2024年，5月Am×n=a12a12┅a1j┅a1na21a22┅a2j┅a2n┇┇ai1ai2┅aij┅ain┇┇am1am2┅amj┅amnA=（?1?2┅?j┅?n)我们可以把矩阵看成一个线性表：A=(?1?2…?j…?n)，其中?j（1≤j≤n）本身也是一个线性表，称为列向量。矩阵Am×n看成n个列向量的线性表,即?j=(a1j,a2j,…,amj)第48页,共54页，星期六，2024年，5月Am×n=a12a12…a1j…a1na21a22…a2j…a2n┇┇ai1ai2…aij…ain┇┇am1am2…amj…amnB‖?1?2┇?i┇?m我们还可以将数组Am×n看成另外一个线性表:B=(?1，,?2,，…，?m)，其中?i（1≤i≤m）本身也是一个线性表，称为行向量，即：?I=（ai1，ai2，…，aij，…，ain）。第49页,共54页，星期六，2024年，5月逻辑结构的图形表示例1.8(P13)第50页,共54页，星期六，2024年，5月2.存储结构定义： 存储结构（又称物理结构）是逻辑结构在计算机中存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。第51页,共54页