数据结构实用教程（c语言版）上ppt

《数据结构实用教程（c语言版）上ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实用教程（C语言版）上第一章绪论第二章线性表第三章栈和队列第四章多维数组和广义表第一章绪论1．1基本术语1．2数据结构的定义及研究的内容1．2．1数据的逻辑结构1．2．2数据的存储结构1．2．3数据的运算1．3算法1．3．1算法的概念及特性1．3．2算法的描述1．3．3算法的评价1．4学习数据结构的意义和目的1．1基本术语数据（Data）是人们约定的符号，用它来表示客观事物及其活动，是信息的载体。数据是计算机程序加工处理的对象。数据元素（DataElement）是数据的基本单位，在计算机程序中通

2、常作为一个整体进行考虑和处理，在不同的情况下，又可以称为元素、结点、顶点或记录。数据是由数据元素构成的。数据项（DataItem）是构成数据元素不可分割的具有独立含义的最小标识单位。若数据元素可再分，则数据元素是由若干个数据项组成；如数据元素不可再分，数据元素和数据项是同一概念，如整型数据就是不可再分的。数据类型（DataType）是一个值的集合和定义在这个值集上一组操作的总称。按值的不同特性，高级程序设计语言中的数据类型可分为原子类型和结构类型两类。第一章绪论1．2数据结构的定义及研究的内容数据结构的定义及

3、研究的内容数据结构（DataStructure）：按照某种逻辑关系组织起来的一批数据，用一定的存储方式存储在计算机的存储器中，并在这些数据上定义一个运算的集合，就称为一个数据结构（DataStructure）。数据结构重点研究的内容：（1）数据的逻辑结构：即数据之间的逻辑关系。（2）数据的存储结构：即数据及数据之间的关系在计算机存储器中的表示。（3）数据的运算：即对数据施加的各种操作。数据的逻辑结构数据的逻辑结构（LogicalStructure：的是数据元素之间的逻辑关系。它是人们根据实际问题的需要和问题本

4、身所含数据之间的内在联系而抽象出来的数学模型，与如何利用计算机存储和处理无关，所以被称为数据的逻辑结构。由于数据的逻辑结构是数学模型，可以借助数学方法来表示，具体的可以用离散数学中关系代数的二元组表示：Data_Structure=（D，S）通常取S中的一个关系rj来进行讨论，rj可以表示为数据元素的序偶的集合。如果集合中有序偶，表示数据元素di和dj之间有rj这种关系。用二元组表示的数据的逻辑结构，有如下的常用术语（1）前趋结点、后继结点、相邻结点（2）开始结点、终端结点、内部结

5、点数据的逻辑结构还能够利用更形象的图形表示数据的逻辑结构有两大类：（1）线性结构：经典的线性结构是线性表。线性结构的逻辑特征是：有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋结点和一个后继结点，也就是说结构中的数据元素间存在着一对一的相互关系。（2）非线性结构：经典的非线性结构有树形结构和图形结构。树形结构的逻辑特征是：有且仅有一个开始结点，可有若干个终端结点，其余的内部结点都有且仅有一个前趋结点，可以有若干个后继结点，也就是说结构中的数据元素间存在着一对多的层次关系。图形结构的逻辑特征

6、是：可有若干个开始结点和终端结点，其余的内部结点可以有若干个前趋结点和若干个后继结点，也就是说结构中的数据元素间存在着多对多的网状关系。表1.1某校围棋社团学生简表学号姓名性别出生日期职务01黄家正男1982-08-05团长02赵芳女1981-08-15组长03王明女1983-04-01组长04王红女1982-06-28组员05张小才男1984-03-17组员06马立伟男1983-10-12组员07孙刚男1982-07-05组员08刘永男1982-12-09组员例1.1在表1.1中，八名学生按学号从小到大排列

7、，形成一个线性结构。假设表示这种逻辑结构的关系为r1，则r1可以定义为学生按学号顺序递增排列的关系，该线性结构的逻辑结构可用二元组表示为：L=（D，S），r1∈SD=｛01，02，03，04，05，06，07，08｝r1=｛<01，02>，<02，03>，<03，04>，<04，05>，<05，06>，<06，07>，<07，08>｝图1.1线性结构的图示例1.2在表1.1中，学生之间还存在着领导与被领导关系，其中01号学生为团长，直接领导02和03号学生，他们分别是组长，02号学生直接领导04和05号学生，

8、03号学生直接领导06、07和08号学生，假设表示这种逻辑结构的关系为r2，则r2可以定义为学生之间的领导与被领导关系，该数据结构的逻辑结构可用二元组表示为：T=（D，S），r2∈SD=｛01，02，03，04，05，06，07，08｝r2=｛<01，02>，<01，03>，<02，04>，<02，05>，<03，06>，<03，07>，<03，08>｝图1.2树形结构的图示例1.3在表1.1中，学