计算机软件技术基础 第二章：数据结构ppt课件.ppt

《计算机软件技术基础 第二章：数据结构ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机软件技术基础第二章数据结构计算机早期运算:原始数据和结果数据不多,重点是算法。计算机应用的发展:对数据进行非数值型的加工处理为主数据结构为研究和解决诸如数据的分类与查找、情报检索、数据库、企业管理、系统工程、图形识别、人工智能以及日常生活等各领域的非数值问题而提出的理论与方法。目的是合理的组织数据，以提高算法的效率。特点:数据量大,而计算的工作量可能很小。数据结构概述数据：描述客观事物的信息（数，字符，符号等）的集合，是程序处理的对象。数据元素：是数据集合中的个体，是构成数据对象的基本单位，一个数据元素可由若干个数据项组成。数据项

2、：是数据的最小单位。一组数据元素具有某种结构形式。数据结构：数据结构描述了一组性质相同的数据元素及元素间的相互关系。用集合论给出的数据结构的定义为:数据结构S是一个二元组：S=(D,R)。其中:D是一个数据元素的非空的有限集合。R是定义在D上的关系的非空的有限集合概念数据结构概念的三个方面数据元素之间的逻辑关系数据元素在计算机中的存储方式在这些数据元素上定义的运算的集合。数据的逻辑结构数据的逻辑结构有时可直接称为数据结构。数据的逻辑结构的三种基本类型：线性表、树和图。逻辑结构分类两大类：(一)线性结构（线性表）数据元素之间的逻辑关系可以

3、用一个线性序列简单地表示出来。线性表是典型的线性结构，它的数据元素只按先后次序联接。有栈、队列、字串、数组和文件等方式。(二）非线性结构（树，图）不满足线性结构特点的数据结构称为非线性结构。树、图等是非线性结构。树中的数据元素是分层次的纵向联接。图中的数据元素则有各种各样复杂联接。其它种类的数据结构由这三种基本结构派生的。定义：数据的逻辑结构在计算机存储设备中的映象称为数据的存储结构(亦称为物理结构)。同一个逻辑结构可以有不同的存储结构。最常用的二种方式是：顺序存储结构链式存储结构。大多数据结构的存储表示都采用其中的一种方式或两种方式的

4、结合。物理结构数据逻辑结构中的数据元素按某种顺序存放在存储器的连续单元中。将逻辑上相邻的数据元素存储在物理上相邻的存储单元中，而数据元素之间的关系由存储单元的邻接关系唯一确定。例如数组主要特点：结点中只有自身信息域，没有连接信息域。因此存储密度大，存储空间利用率高；可以通过计算直接确定数据结构中第i个结点的存储地址。即可以对记录直接进行存取；插入、删除运算会引起大量结点的移动；要求存储在一片连续的地址中。这种存储方式主要用于线性的数据结构。顺序存储结构存储数据结构的存储空间可以不连续，数据元素之间的关系由指针来确定。主要特点是：结点由两

5、类域组成：数据域和指针域。逻辑上相邻的结点物理上不必邻接，既可实现线性数据结构，又可用于表示非线性数据结构。插入，删除操作灵活方便，不必移动结点，只要改变结点中的指针值即可。链式存储结构插入:在数据结构中的指定位置上插入新的数据元素；删除:根据一定的条件,将某个结点从数据结构中删除；更新:更新数据结构中某个指定结点的值；检索:在给定的数据结构中,找出满足一定条件的结点来，条件可以是某个或几个数据项的值；排序:根据某一给定的条件，将数据结构中所有的结点重新排列顺序等。数据结构运算数据结构运算操作分类加工型操作：操作改变了存储结构的值（如插

6、入、删除、更新等)引用操作：操作只是查询或求得结点的值（如检索等）。评价算法正确性运算时间存储空间线性表表中的每个元素呈线性关系，除第一个外，都有一个直接前趋(predecessor)，除最后一个元素外，都仅有一个后继(successor)。1.线性表的逻辑结构线性表L用符号表示为：L=(a1，a2，a3，..ai...，an)线性表也可以正式定义为：若数据结构L=（D，R）是一个线性表，则：D是包括a1,a2,a3.....an等元素的集合。R中只包含一个关系，即R={

7、ai-1，ai∈D，2≤i≤n}。关系

8、1,ai>给出了元素的一种先后次序。a1称为表的线性起始结点，an为表的终结点。线性表——最简单，最常用的数据结构2.线性表的存储结构存储结构:顺序存储结构和链接存储结构。具有顺序存储结构的线性表称为顺序表用一组地址连续的存储单元依次存储线性表中的每个数据元素。具有链接存储结构的线性表称为线性链表。用一组任意的存储单元来存储线性表中数据元素的，这组存储单元可以是连续的，也可以是不连续的。通常亦称为链表。常用的链表有单链表、循环链表和双向链表。3.线性表的基本运算常用的操作有插入、删除、修改、读值、检索和排序等。线性表还可以进行一些更为复

9、杂的操作。将两个或两个以上的具有相同数据对象的线性表合并成一个线性表，将一个线性表拆成若干个线性表，复制一个线性表等等。C++编写类程序的回顾建立win32Console工程建立类的说明—类的头文件:在工程