C语言入门教程全第9章.ppt

《C语言入门教程全第9章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章数据结构与算法基础9.1数据结构与算法概述9.2线性表9.3栈和队列9.4树和二叉树9.5图9.6排序9.7查找本章小结习题九9.1数据结构与算法概述9.1.1数据结构的相关概念实践证明，要想更有效地使用计算机，仅仅掌握计算机语言而缺乏数据结构和算法的有关知识，是难以处理诸多复杂应用问题的。早期的计算机主要解决纯数值计算的问题，以此为加工对象的程序设计称为数值型程序设计。其涉及的操作对象比较简单，其一般为整型、实型数据等。后来，随着计算机应用领域的不断拓宽，解决非数值计算的问题越来越引起人们的关注。例如，金融管理、文献检索、

2、计算机辅助设计等。这些问题主要集中于对数据集合中的各元素以各种方式进行运算，如插入、更新、删除、查找等。在此涉及的数据类型比较复杂，而且数据元素之间具有各种特定的联系，所以，如果了解了数据集合中元素之间的关系以及如何组织和表示这些数据，就能大大提高计算机处理问题的效率。数据结构是一门研究非数值运算的程序设计问题的学科，它包含以下3个方面的内容：（1）数据集合中各数据元素之间的逻辑结构。（2）对数据进行处理时，各数据元素在计算机中的存储（物理）结构。（3）对数据的抽象运算。1．数据（data）数据是反映客观事物信息符号的集合，也是计

3、算机程序要加工的对象。这个集合中包括客观事物的数值、字符以及能够输入到计算机中并被计算机程序处理的符号。计算机发展初期，由于计算机主要用于数值计算，数据指的就是数值。随后由于计算机应用的普及，数据的含义也比原来变得更加广泛。如文字、表格、声音、图形、图像等都属于数据的范畴。2．数据元素（dataelement）数据元素是数据集合中的客体（个体），是数据的基本单位，有时也称为节点或记录。例如数据集合N={1，2，3，4，5}中整数1～5都是数据元素。每个数据元素的表现形式是由一个或多个数据项组成的。数据项是具有独立含义的最小标识单位

4、，例如，在老师档案信息管理中的每一位老师就是一个数据元素，组成它的数据项可以是姓名、性别、年龄等。3．数据对象（dataobject）数据对象是具有相同特性的数据元素的集合，是数据的一个子集。例如，一周中的7天就是一个数据对象，可表示为集合W={Mon，Tue，Wed，Thu，Fri，Sat，Sun}；再如，字母数据对象可表示为集合C={‘A’，‘B’，…，‘Z’}。4．数据类型（datatype）数据类型是一个值的集合和定义在该值集上的一组操作的总称。程序中出现的每一个变量必须与一个而且只能与一个数据类型相联系，它不仅规定了该变

5、量可以设定的值的集合，还规定了该集合上的运算。各种语言规定了它所允许的数据类型。在C语言中，基本数据类型包括整型、实型等，这些变量的值是不可再分的；而构造类型包括数组、结构体等，这些变量的值是可以再分的，也可以说它们是带结构的数据，它们的成分可以是基本数据类型，也可以是构造数据类型等。5．数据结构（datastructure）数据结构指的是数据之间的相互关系，即数据的组织形式。可以用集合论的方法定义数据结构如下：S=(D,R)D={ai

6、ai∈ElemSet,i=0,1,2,3,…,n,n≥0}R={

7、ai-1,

8、ai∈D,2≤i≤n}数据结构S是一个二元组，其中D是一个数据元素的有限集合，R是定义在关系D上的有限集合，即R是由有限个关系所构成的集合。若n=0时，则D是一个空集。数据结构分为逻辑结构与物理结构两种。（1）数据的逻辑结构。数据的逻辑结构就是数据元素间的逻辑关系，它研究的是数据元素及其关系的数学特性，与数据的存储无关，是独立于计算机的。数据的逻辑结构可概括地分为线性结构和非线性结构两种，如图9.1.1所示。图9.1.1数据的逻辑结构线性结构的逻辑特性是有且仅有一个开始元素和一个终结元素，除第一个元素以外，其他元素有且仅有一个直接

9、前驱；除最后一个元素外，其他元素都有且仅有一个直接后继。非线性结构的逻辑特性是一个元素可能有多个直接前驱和直接后继。线性结构主要有线性表、栈和队列等，而非线性结构分为树型结构和图型结构等。（2）数据的物理结构。数据的物理结构又称存储结构，是数据及其关系在计算机中的存放形式，是逻辑结构在计算机存储器中的映像，也就是它的具体实现，通常用高级语言中各种数据类型来描述。在进行实际的数据处理时，被处理的数据都是存放在计算机的存储空间中，而且，各数据在计算机存储空间的位置关系与它们的逻辑关系通常是不同的。因此，为了能表示出存放在计算机存储空间

10、的各个节点之间的逻辑关系，在数据的存储结构中，不但要存放各个节点的信息，还要存放各个节点之间逻辑关系的信息。下面介绍4种常见的存储结构：1）顺序存储结构。顺序存储结构主要用于线性的数据结构。它是把逻辑上相邻的数据元素节点存储在物理上相邻的存储单元中