2023拉
DataStructures and AlgorithmAnalysis in C (一)
上一篇 /
下一篇 2012-07-03 11:01:03
/ 个人分类:数据结构与算法分析
数据结构概念:数据结构是
数据对象,以及存在于该对象的
实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的
函数来给出。”他将
数据对象(data object)定义为“一个数据对象是
实例或
值的集合”。
基本概念:
数据:信息的载体。
数据元素:是数据的基本单位,又称记录。
数据类型:取值范围与运算限定(类似int,char等)
数据对象:用若干数据元素组成(是性质相同的数据元素的集合,是数据的一个
子集。数据对象可以是有限的,也可以是无限的)
数据元素基础特征:
集合:同属于一个集合外
数据元素相互之间的关系称为结构。有四类基本结构:集合、
线性结构、
树形结构、图状结构(网状结构)
数据结构的特征: 一: 逻辑结构:
a:线性结构(线性表,栈,队列) b:非线性结构(树形,图,堆,堆)
队列:一种特殊的
线性表,它只允许在表的
前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。
数据结构中,逻辑上(逻辑结构:数据元素之间的逻辑关系)可以把数据结构分成线性结构和非线性结构。 线性结构的顺序存储结构是一种随机存取的存储结构,线性表的链式存储结构是一种顺序存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。 栈:是只能在某一端插入和删除的特殊
线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
树形:是包含n(n>0)个结点的有穷集合K,且在K中定义了一个关系N,N满足 以下条件:
(1)有且仅有一个结点 k0,他对于关系N来说没有前驱,称K0为树的根结点。简称为根(root)。 (2)除K0外,k中的每个结点,对于关系N来说有且仅有一个前驱。
(3)K中各结点,对关系N来说可以有m个后继(m>=0)。
图: 图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以
区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。
堆:在计算机科学中,堆是一种特殊的树形数据结构,每个结点都有一个值。通常我们所说的堆的数据结构,是指二叉堆。堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆
链表:是一种物理存储单元上非连续、非顺序的存储结构,数据元素的
逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时
动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
二:(物理)存储结构:
a:顺序存储(理想情况下数组是连续顺序存储) b:链式存储(通过地址,指针建立联系,内存区域,不同的位量)
数据结构在计算机中的表示(映像)称为数据的物理(存储)结构。它包括数据元素的表示和关系的表示。 数据元素之间的关系有两种不同的表示方法:顺序映象和非顺序映象,并由此得到两种不同的存储结构:顺序存储结构和链式存储结构。 顺序存储方法:它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现,由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法,通常借助于程序设计语言中的数组来实现。 链接存储方法:它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构,链式存储结构通常借助于程序设计语言中的指针类型来实现。索引存储方法:除建立存储结点信息外,还建立附加的索引表来标识结点的地址。散列存储方法:就是根据结点的关键字直接计算出该结点的存储地址。 三: 数据运算(处理):
进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程
收藏
举报
TAG: