c语言算法与数据结构全套ppt课件教案

《c语言算法与数据结构全套ppt课件教案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法与数据结构刘建圻粤嵌教育第一章概论基础知识时间复杂度空间复杂度数据(Data)：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement)：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。一个数据元素可由若干个数据项(DataItem)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。数据对象(DataObject)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C={‘A’,’B’,

2、’C,…}。1.1基本概念和术语数据结构(DataStructure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型，如图1-3所示。①集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。②线性结构：结构中的数据元素之间存在一对一的关系。③树型结构：结构中的数据元素之间存在一对多的关系。④图状结构或网状结构：结构中的数据元素之间存在多对多的关系。数据结构的形式定义是一个二元组：Data-Structure=(D，

3、S)其中：D是数据元素的有限集，S是D上关系的有限集。例2：设数据逻辑结构B=（K，R）K={k1,k2,…,k9}R={，，，，，，，，，，}画出这逻辑结构的图示，并确定那些是起点，那些是终点1.1.3数据结构的形式定义图1-3四类基本结构图1.1.4数据结构的存储方式数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的

4、关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer)，用该指针来表示数据元素之间的逻辑结构(关系)。例：设有数据集合A={3

5、.0,2.3,5.0,-8.5,11.0}，两种不同的存储结构。顺序结构：数据元素存放的地址是连续的；链式结构：数据元素存放的地址是否连续没有要求。数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。数据结构的三个组成部分：逻辑结构：数据元素之间逻辑关系的描述D_S=（D，S）存储结构：数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。数据操作：对数据要

6、进行的运算。本课程中将要讨论的三种逻辑结构及其采用的存储结构如图1-4所示。数据的逻辑结构非线性结构集合图状结构有向图无向图树形结构一般树二叉树线性结构一般线性表线性表推广广义表数组串受限线性表栈和队列图1-5数据逻辑结构层次关系图图1-4逻辑结构与所采用的存储结构线性表树图顺序存储结构链式存储结构复合存储结构逻辑结构物理结构数据类型(DataType)：指的是一个值的集合和定义在该值集上的一组操作的总称。数据类型是和数据结构密切相关的一个概念。在C语言中数据类型有：基本类型和构造类型。数据结构不同于数据类型，

7、也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。1.1.5数据类型数据结构的主要运算包括：⑴建立(Create)一个数据结构；⑵消除(Destroy)一个数据结构；⑶从一个数据结构中删除(Delete)一个数据元素；⑷把一个数据元素插入(Insert)到一个数据结构中；⑸对一个数据结构进行访问(Access)；⑹对一个数据结构(中的数据元素)进行修改(Modify)；⑺对一个数据结构进行排序(Sort)；⑻对一个数据结构进行查找(Search)。1.1.6数据结构的运算

8、抽象数据类型(AbstractDataType，简称ADT)：是指一个数学模型以及定义在该模型上的一组操作。ADT的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。ADT的形式化定义是三元组：ADT=(D，S，P)其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。1.2抽象数据类型ADT的一