文档介绍：蒆基本概念肃数据袁数据是信息的载体,在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。肈数据元素薆数据元素也称为结点,是表示数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。蒄数据项艿数据项是构成数据元素的不可分割的最小单位。袇数据对象薆数据对象是具有相同性质的数据元素的集合,是数据的子集。袅注意:在不产生混淆的情况下,将数据对象简称为数据。羁数据结构袀数据结构是指相互之间存在一定关系的数据元素的集合,即数据结构是一个二元组DataStructure=(D,R),其中D是数据元素的集合,R是D上关系的集合。按照视点的不同,数据结构分为逻辑结构和存储结构。蚆数据的逻辑结构羂数据的逻辑结构是指数据元素之间逻辑关系的整体。根据数据元素之间逻辑关系的不同,数据结构分为四类:蚃⑴集合:数据元素之间就是“属于同一个集合”,除此之外,没有任何关系;虿⑵线性结构:数据元素之间存在着一对一的线性关系;螆⑶树结构:数据元素之间存在着一对多的层次关系;莃⑷图结构:数据元素之间存在着多对多的任意关系。膀注意:数据结构分为两类:线性结构和非线性结构。蒇数据的存储结构袆数据的存储结构又称为物理结构,是数据及其逻辑结构在计算机中的表示。通常有两种存储结构:顺序存储结构和链接存储结构。螃顺序存储结构的基本思想是:用一组连续的存储单元依次存储数据元素,数据元素之间的逻辑关系是由元素的存储位置来表示的。袂链接存储结构的基本思想是:用一组任意的存储单元存储数据元素,数据元素之间的逻辑关系是用指针来表示的。膆注意:存储结构除了存储数据元素之外,必须存储数据元素之间的逻辑关系。羆抽象数据类型膄抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。抽象数据类型提供了使用和实现两个不同的视图,实现了封装和信息隐藏。莀算法的定义艿通俗地讲,算法是解决问题的方法,严格地说,算法是对特定问题求解步骤的一种描述,是指令的有限序列。肆算法的特性莁⑴输入:一个算法有零个或多个输入(即算法可以没有输入),这些输入通常取自于某个特定的对象集合。肂⑵输出:一个算法有一个或多个输出(即算法必须要有输出),通常输出与输入之间有着某种特定的关系。肈⑶有穷性:一个算法必须总是(对任何合法的输入)在执行有穷步之后结束,且每一步都在有穷时间内完成。膅⑷确定性:算法中的每一条指令必须有确切的含义,不存在二义性。并且,在任何条件下,对于相同的输入只能得到相同的输出。螂⑸可行性:算法描述的操作可以通过已经实现的基本操作执行有限次来实现。蒀线性表的定义螇线性表简称表,是零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长度,长度等于零时称为空表。膅线性表的逻辑关系膃在一个非空表L=(a1,a2,……,an)中,任意一对相邻的数据元素ai-1和ai之间(1<i≤n)存在序偶关系(ai-1,ai),且ai-1称为ai的前驱,ai称为ai-1的后继。在这个序列中,a1无前驱,an无后继,其它每个元素有且仅有一个前驱和一个后继。节顺序表的存储结构定义袀用MaxSize表示数组的长度,顺序表的存储结构定义如下:芅#defineMaxSize100薄typedefstruct蚀{蕿ElemTypedata[MaxSize];//ElemType表示不确定的数据类型莅intlength;//length表示线性表的长度羅}SeqList;莂顺序表是随机存取结构莈设顺序表的每个元素占用c个存储单元,则第i个元素的存储地址为:蒅LOC(ai)=LOC(a1)+(i-1)×c肂顺序表的优缺点衿顺序表利用了数组元素在物理位置上的邻接关系来表示线性表中数据元素之间的逻辑关系,这使得顺序表具有下列优点:膆⑴无需为表示表中元素之间的逻辑关系而增加额外的存储空间;薅⑵可以快速地存取表中任一位置的元素(即随机存取)。蒂同时,顺序表也具有下列缺点:薁⑴插入和删除操作需移动大量元素。在顺序表上做插入和删除操作,等概率情况下,平均要移动表中一半的元素。腿⑵表的容量难以确定。由于数组的长度必须事先确定,因此,当线性表的长度变化较大时,难以确定合适的存储规模。蚅⑶造成存储空间的“碎片”。数组要求占用连续的存储空间,即使存储单元数超过所需的数目,如果不连续也不能使用,造成存储空间的“碎片”现象。袃单链表的存储结构定义聿单链表的存储结构定义如下:羈StructNode螅{ElemTypedata;//ElemType表示不确定的数据类型芄structNode*next;螁}*first;//first为单链表的头指针蚇双链表的存储结构定义螄双链表存储结构定义如下:蚅structDulNode腿{螀ElemTypedata;//ElemType表示不确定的数据类型袄structDulNode