数据结构(C++语言描述)教学演示文稿现实世界中的实际问题必须经过抽象,得出反映实际事物本质的数据表示后,才能被计算机处理。如何用计算机所能接受的形式来描述这些数据,如何将这些数据以及它们之间的关系存储在计算机中,以及如何用有效的方法去处理这些数据,是数据结构课程要研究的主要内容。2.12.1.1数据、数据元素、数据对象2.1.2数据结构2.1.1数据、数据元素、数据对象数据(data)是对客观事物的符号表示,是对现实世界的事物采用计算机能够识别、存储和处理的形式进行描述的符号的集合。例如:科学计算软件处理的是数值数据;文字处理软件处理的是字符数据;多媒体软件处理的是图象、声音等多媒体数据。数据元素(dataelement)是数据的基本单位,也称结点,在一个计算机程序中通常作为一个整体进行考虑和处理。数据元素也称结点。2.1.1一个数据元素可以由若干个数据项(dataitem)组成。数据项包括两种:初等项(是数据不可分割的最小单位)、组合项(由若干个数据项组成)。在数据库语言中,数据项称为"字段",而数据元素称为"记录"。数据对象(dataobject)是性质相同的数据元素的集合,是数据的一个子集。例如整数对象、实数对象、字符对象等。姓名性别年龄籍贯班别成绩数学物理化学外语张三女18北京600380907075李四男20上海600175809080王五男19长沙600285807590...........................表2-1学生情况表一个数据元素一个初等数据项一个组合数据项整张表就??一个数据对象,其中每个学生的情况是其中的一个数据元素。2.1.2从数学意义上讲,数据结构是指数据的组织形式,由数据对象及该对象中数据元素之间的关系组成。数据结构可描述为一个二元组Data-Structure=(D,R)其中:D是数据对象,为数据元素的有限集;R是该对象中数据元素之间关系的有限集。这种意义上的数据结构称为数据的逻辑结构。除此之外,要将数据放在计算机内进行处理,还将涉及数据的存储结构。2.1.2涉及到计算机的数据结构概念,至今尚未有一个公认的标准定义,但一般认为应包括以下三个方面:(1)数据元素与数据元素之间的逻辑关系,也称为数据的逻辑结构,它独立于计算机;(2)数据元素与数据元素之间的关系在计算机中的存储表示,也称为数据的存储结构或物理结构,它依赖于计算机;(3)??据的运算,即对数据施加的操作。2.2如果一个数据结构中的两个结点k、k'之间存在的关系可用有序对表示,则称k'是k的后继,k是k'的前驱,k和k'互为相邻结点。如果k没有后继,则k称为终端结点。如果k没有前驱,则称k为开始结点。如果k既不是终端结点,也不是开始结点,则称k为内部结点。数据的逻辑结构分为线性结构和非线性结构两大类。非线性结构又分为树型结构和图状结构。线性结构线性结构有且仅有一个开始结点和一个终端结点,并且所有的结点最多只有一个前驱和一个后继。线性表是典型的线性结构。线性表一个学校所有学生的各种特征可用以下表格来记录:学号姓名性别出生年月系班级...030401张三男1985.1计算机0304...030402李四女1984.12计算机0304...030403王五男1984.6计算机0304...030404赵六男1985.4计算机0304........................该表为一个数据结构,其中列称为"字段",行称为"记录",记录之间有一对一的线性关系,称为"线性结构"。树状结构树状结构中,一个结点最多只有一个前驱,而可以有多个后继。它是最重要的非线性结构。一个学校的组织机构可用以下数据结构来表示:该数据结构的"结点"具有一对多的逻辑关系,就象一棵倒挂的树,故称为"树状结构"。学校保险系金融系会计系计算机系基础教研室电子商务教研室教师甲教师乙教师丙.....................图状结构图状结构中,对结点的前驱和后继的个数没有限制,结点之间的关系是任意的。它是最一般的非线性结构。在n个城市间建立通信网络,要求在任意两个城市之间都有直接或间接的通信线路,该通信线路可用以下图形来表示:如果每个城市为一个结点,则结点之间的逻辑结构称为"图状结构",它是一种多对多的数据结构。ABCDEFG2.2数据的存储结构(又称物理结构)取决于四种基本的存储方法:顺序存储、链接存储、索引存储、散列存储。顺序存储是把逻辑上相邻的结点存储在物理位置相邻的存储单元里。结点之间的逻辑关系用存储单元的邻接关系来体现。链接存储对逻辑上相邻的结点不要求在存储的物理位置上相邻,结点之间的逻辑关系由附加的指针来表示。索引存储是在存储结点数据的同时,还建立附加的索引表。索引表的每一项称为索