数据结构的基本概念

《数据结构的基本概念》由会员分享，可在线阅读，更多相关《数据结构的基本概念（10页珍藏版）》请在装配图网上搜索。

1、数据结构的基本概念数据结构是讨论计算机系统中数据的组织形式及其相互关系的一门学科,它是计算机专业的重要基础课,也是其他从事计算机软件开发工作的人需要掌握的必备知识。1、 数据结构的主要内容数据结构实际上就是研究：（1） 数据元素间的逻辑关系是什么？（2） 适宜采用什么样的存储结构（3） 有那些基本运算？怎样实现？ 也就是数据结构的三个层次：数据的逻辑结构、数据的存储结构、数据操作相关算法集合。下面举例说明：职工档案表如表7-1所示。 表7-1 职工档案表姓名性别出生年月部门职称工资婚否奖惩胡一民李 静张冬梅李清明王文明刘明伦男女女男女男01/10/6703/12/7804/12/6411/25

2、/7201/12/5412/03/76.技术科生产科生产科技术科生产科生产科.工程师助工高工工程师助工高工.165013001550165012001800.T.F.T.T.F.T.MemoMemoMemoMemoMemoMemo.这张档案表可称为一个数据结构,它是一个线性表结构,表中的每一行为一个数据元素(它是数据结构的基本单位)。（1） 表中书元素的逻辑关系是：对表中任一元素，与它相邻且在它前面的数据元素（也称为直接前驱）最多只有一个，与表中任一数据元素相邻且在它后面的数据元素（也称直接后继）也最多只有一个。表中第一个元素没有直接前驱，故称为开始 数据元素，最后一个数据元素没有直接后继，故

3、称为终点元素（例：表中李静所在元素的直接前驱为胡一民所在的数据元素；直接后继为张冬梅所在的数据元素）（2） 该表的存储方式：表中的数据元素是顺序地邻接在一片连续的单元中，而不是用指针将这些元素连接在一起。（3） 对表元素怎样进行查找、删除、插入等操作方能提高数据操作效率。2、 有关概念（1） 数据：能被计算机识别、存储和加工的客观事物的描述，称为数据。（2） 结构：是指事物间的相互关系和约束。（3） 数据元素：数据的基本单位，也称数据结点（4） 算法：是指为解决某一问题而需进行的有限操作的过程描述。3、 数据结构的具体内容（1） 数据元素逻辑关系（逻辑结构），分为两大类：A 线性结构：其逻辑特

4、征为：有且仅有一个开始元素和一个终点元素，所有数据元素最多只有一个直接前驱和 一个直接后继，线性表就是一个典型的线性结构。B 非线性结构： 其逻辑特征为：该结构中一个数据元素可能有多个直接前驱或直接后继。除最一般的图结构外， 还有树结构。图结构：对数据元素的直接前驱和直接后继的个数不作限制。 树结构：有且仅有一个根元素无直接前驱，其他元素有且仅有一个直接前驱；每个元素都可 能有多个直接后继；除根元素外， 所有的数据元素都存在一条从根元素到该元素的路径。（2） 数据元素在计算机中的存储方法（即数据的存储结构，也称物理结构），分四类：A 顺序存储方法把逻辑上相邻的数据元素存储在物理位置上相邻的存储

5、单元里，元素间的逻辑关系由存储单元的邻接关系体现，其存储表示我们称为顺序存储结构。顺序存储方法主要应用于线性的数据结构，如线性表、数组等，但非线性数据结构也可以通过某种线性化方法来实现顺序存储。B 连接存储方法并不要求逻辑上相邻的元素在物理位置上也相邻，元素的逻辑关系是由附加的指针字段表示。它要借助于程序语言的指针类型来描述元素的存储地址，每个数据元素所占存储单元分成两部分：元素数据项和指针项。C 索引存储方法在存储元素信息的同时，还建立附加的索引表。索引表的每一项成为索引项，而地址则指示存储位置。D 散列存储方法（地址转移法）根据元素的关键字，通过某一散列函数直接计算出该元素的存储地址。同一

6、种逻辑结构采用不同的存储方法，可得到不同的存储结构，采用何种存储方法来表示相应的逻辑结构，主要是根据算法具体确定。例如：线性表是一种逻辑结构，采用顺序方法的存储表示，该结构为顺序表；若采用链接方法的存储表示，该结构为链表；若采用散列方法的存储表示，该结构为散列表。（3） 数据处理与运算对一个数据结构，一般有如下的一些基本运算：A 遍历：在数据结构里的各元素间移动，或查看所有的数据元素。B 插入：往数据结构中添加新元素。C 更新：修改数据元素的数据项（又称为字段）的值D 删除：把指定的数据元素从数据结构中去掉。E 查找：在数据接中查找满足一定条件的数据元素F 排序：在保持数据元素个数不变的前提下

7、，将数据元素按指定顺序重新排列（一般针对线性逻辑结构）由于数据运算是数据结构不可分割的部分，对于同一个数据结构，同一个基本运算，当选择的存储结构不同时,其运算的实现也会完全不同。例如，对一个线性表结构，同样进行插入操作，采用顺序存储时的算法就与采用链式存储时迥然不同。同样地，已给定了数据的逻辑结构和存储结构，若定义的运算不同，也可能导致完全不同的数据结构。例如，对线性表上的插入、删除运算仅在表的一端进行，则该线性表称之为栈；而插入限制在表的一端进行，删除限制在表的另一端进行的线性表称为队列。若线性表采用顺序表示和链表作为存储结构，则对插入和删除运算在做了上述限制之后可分别得到顺序栈和链栈、顺序

8、队列和链队列。常用的数据结构 一、线性结构线性结构是数据结构中最简单且最常用的一种数据结构。其基本特点是：数据元素有序并有限。线性结构的数据元素可排成一个线性队列： a1,a2,a3,a4an其中：a1为起始元素，an为终点元素，ai为索引号为I的数据元素。 在线性表中，除首元素外，每个元素有且仅有一个前驱；除尾元素外，每个元素有且仅有一个后继。线性结构有各种类型，如线性表、堆栈、队列、数组、串等。线性表的主要基本操作有以下几种：（1） initiate(L) 初始化 设定一个空的线性表L。（2） length(L) 求表长 返回线性表中数据元素的个数。（3） get(L,I) 取元素 返回线

9、性表中第I个数据元素。（4） locate(L,x) 定位 返回值等于x的数据元素在线性表中的序号，若不存在这样的元素，则返回0。1顺序表当线性表采用顺序存储结构时，我们称之为顺序表。在顺序表中，数据元素按逻辑次序依次放在一组地址连续的存储单元里。由于逻辑上相邻的元素存放在内存的相邻单元里，所以顺序表的逻辑关系蕴含在存储单元的邻接关系中。设顺序表中的每个元素占用K个存储单元，索引号为1的数据元素a1的内存地址为loc(a1)，则索引号为I的数据元素ai的内存地址为：loc(ai)=loc(al)+(I-l)*k显然，顺序表中每个元素的存储地址是该元素在表中索引号的线性函数。只要知道某元素在顺序

10、表中的索引号，就可以确定其在内存中的存储位置。所以说，顺序表的存储结构是一种随机存取结构。顺序表的特点： 物理上相邻的元素在逻辑上也相邻。 可随机存取。 存储密度大，空间利用率高。 对顺序可进行插入、删除等操作，但运算效率低，需要大量的数据元素移位。【例72】 在下面的顺序表中，在数据元素c、d之间插入h ,则歩骤为： abcdef 先将f、e、d按次序向后移动一个位置。 将h放入元素移动后空出的位置上。 元素总数加1。元素个数为n 时，要在第I个元素前插入新元素，需移动n-i+1个元素。在等概率情况下，插入一个新元素平均需移动(n+1)/2个元素。【例73】 在下面的顺序表中，删除元素c，则

11、步骤为：abcde 将b、e按次序向左移动一个位置。 元素个数减1。元素个数为n 时，要删除第I个元素，需移盍n-I+1个元素。在等概率情况下，删除一个元素平均需移动n/2个元素。2线性链表采用顺序表的运算效率较低，需要大量的数据元素的移位，而采用链式存储结构的链表是用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零星分布在内存中的任何位置上，从而可以大大提高存储器的使用效率。在线性链表中每个元素结除存储自身信息外要额外存储一个指向直接后继的信息（即后继的存储位置：地址）。对链表的访问总是从链表的头部开始，根据每个结点中存储的后继结点的地址信

12、息顺链进行的。信息地址数据域 指针域 优点：插入、删除操作时移动的元素少。 缺点：所有的操作都必须顺链操作，访问不方便。 将顺序表与链表作一比较，可以看出： 顺序存储的访问是随机访问，而链式存储的访问是顺链进行的顺序访问。顺序存储下插入、删除平均移动一半元素，效率不高，而链式存储下插入、删除效率高。（3）顺序存储空间利用效率高，链式存储需额外增加地址指针的存储，增加空间耗费。3栈与队列栈与队列是两种特殊的线性表。即它们的逻辑结构与线性表相同，只是其插入、删除运算仅限制在线性表的一端或两端进行。（1） 栈 栈是限制仅在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶，另一端为栈

13、底，当表中没有元素时称为空栈，一摞盘子的情形就是栈的生动形态。栈的特点是：后进先出（LIFOLast In,First Out）栈的基本运算有五种： SETNULL（S）（置空栈）：将栈S置成空栈。 EMPTY（S） （判空栈：这是一个布尔函数，若栈S为空栈，返回值为“真”；否则，返回值为“假”。） PUSH（S，X）（进栈，又称压栈）：在栈S的顶部插入（亦称压入）元素X。 POP（S） （出栈）：若栈S不空，则删除（亦称弹出）顶部元素X。 TOP（S） （取栈顶）：取栈顶元素，并不改变栈中内容。由于栈是运算受限的线性表，因此线性表的存储结构对栈适用。所以，栈也可以分成采用顺序结构的顺序栈和采

14、用链结构的链栈。顺序存储的顺序栈：顺序栈是利用一组地址连续的存储单元的从栈底到栈顶依次存放数据的元素。链式存储的链栈：链栈是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行。链栈中每个数据元素用一个节点表示，栈顶指针作为链栈的头指针。（2） 队列 队列是一种操作受限的线性表，它只允许在线性表的一端进行数据元素的插入操作，而在另一端才能进行数据元素的删除操作。其中，允许插入的一端称为队尾，允许删除的另一端称为队头。日常生活中的排队就是队列的实例。特点：先进先出（FIFOFirst In,First Out）。同栈的操作类似，队列的基本操作也有五种：SETNULL(Q) ( 置空队列)：将

15、队列Q初始化为空。EMPTY(Q)(队列为空)：若队列Q为空队列，返回“真”；否则返回“假”. ENTER(Q) (若队列)：若队列 Q未满，在原队尾后加入数据元素x，使x成为新的队尾元素。DELETE(Q) （出队列）：若队列Q不空，则将队列的队头元素删除。 GETHEAD(Q) （取队头元素）：若队列Q不空，则返回队头元素，但不改变队列中的内容。 队列也可以分成采用顺序结构的顺序队列和采用链队列。 队列的顺序存储结构：它同栈一样，可以用一组地址连续的窨空间存放队列中的元素。 队列的链式存储结构：利用带头结点的单链表可以作为队列的链式存储结构。此时，一个队列需要指向队头和队尾的两个指针才能惟

16、一确定。 二非线性结构 非线性结构的逻辑特征是一个结点元素可能有多个直接前趋和多个直接后继。最主要的非线性数据结构是：树结构、二叉树和图结构。 1、树结构 树结构是结点之间有分支、层次关系的结构，类似于自然界中的树，也有树根、树叶及联系它们的支干，不过是一种倒生树。树一般用递归的方式定义。 树是一个或多个结点元素组成的有限集合T，对任意一个非空树，它都满足如下条件： （1）有且仅有一个特定的称为根(Root)的结点。 （2）其余结点可分为m(m0)个互不相交的有限集合T1，T2，.，Tm。其中每个集合又是一棵树，被称为 根的子树。图7-1是一个树的示意图。 图7-1 树 在树中，一个结点元素常

17、简称为结点，下面介绍一些有关树结构的常用术语与概念。 （1）结点的度 一个结点的子树的个数称为该结点的度。如图7-12中结点D的度为2。 （2）叶子 度为0的结点称为叶子或终端结点。如图7-12中的结点H、I、J、K、L、M、N、O、P、Q （3）分支结点 度不为0的结点称为分支结点或非终端结点。 （4）树的度 树中各结点的度的最大值，用来表征一个树的茂密程度。图7-12中树的度为2。 （5）双亲和孩子 结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。例如， 图7-12 中B是A的孩子，而A是B的双亲。 （6）兄弟 具有相同双亲的结点互为兄弟。如图7-12中结点B和C互为兄弟。

18、（7）结点的层次 根结点的层次为1，其余任一结点的层次等于它的父结点的层次加1。 （8）树的深度 树中结点的最大层次称为树的深度或高度。如图7-12所示的树的深度为4。 （9）有序树和无序树 如果将树中结点的各子树看成从左至右是有次序的，即若交换了某结点 各子树的相对位置，则构成了不同的树，称这棵树为有序树；否则称为无序树。 （10）森林 森林是n(n0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林 （11）路径 若树中存在序列k1k2kj，使ki是ki+1的双亲(1ij)，则称该结点序列为从k1到kj 的一条路径。路径的长度等于j-1，它是该路径所经过的边(即连接两个结点的

19、有序对)的数目。 二叉树是既简单又重要的树结构。它的每个结点最多有两棵子树，且严格区分为左子树和右子树。 二叉树是有限个结点的集合，它或为空集(此时称为空二叉树)，或是由一个根结点和两棵互不相交的且分别称为这个根的左子树和右子树的二叉树组成。 这是二叉树的递归定义，即在二叉树的定义中又用到了二叉树的概念。这个递归定义表明二叉树有五种基本形态：或为空(图7-2(a)，或只有一个根结点(图7-2(b)，或只有左子树没有右子树图7-2(c)，或只有右子树没有左子树图7-2(d)，或左、右子树均非空 图7-2 二叉树的五种基本形态 需要特别注意的是，二叉树并不是树的特殊形式，虽然树与二叉树的概念有许多

20、关系，但它们是两个概念。其主要区别是：树至少应有一个结点，而二叉树可以为空；其次，二叉树的结点的子树要区分左子树和右子树，即使某结点只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树。例如，图7-2中的(c)和(d)是两棵不同的二叉树。而作为树，它们就是相同的了。二叉树不是树的特殊情况。 二叉树具有如下重要性质： 二叉树第i层上的结点数目最多为2i-1(i1)。 深度为k的二叉树至多有2k-1个结点(k1)。 在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点的个数为n2，则n0= n2+1。 下面我们介绍几种特殊的二叉树： （1）满二叉树 图7-3 在一棵二叉树中，如果所有分支

21、结点都存在左子树和右子树，并且所有叶结点都在同一层上，这样的二叉树称作满二叉树，如图7-3所示。图中结点内的字符代表该结点本身的数据信息，结点下面的数字为该结点的顺序编号。 （2）完全二叉树 若一棵二叉树至多只有最下面两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树，如图7-4所示。实际上，完全二叉树是在满二叉树上减少一些结点，减少的结点只能是最后一层且从右边开始减少，不满足该条件的都是非完全二叉树，如图7-5所示。 显然，一个具有n个结点的二叉树，其所有结点的编号和一个满二叉树1到n个结点的编号完 全一致，则它肯定是完全二叉树。2、 图

22、结构 图是另一种重要的、比树更复杂的非线性数据结构。在树中，每个结点只与上一层的一个结点（即父结点）有联系，并可与其下层的多个子结点有联系，而同一层的结点之间没有任何横向联系。但在图中，结点之间的联系是任意的，每个结点都可能与其它结点相关。 一个图G由两个集合V和E组成，记为G（V、E）。其中V是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集。通常也将图G的顶点集和边集分别记为V（G）和E（G）。E（G）可以是空集，若E（G）为空集，则图G只有顶点而没有边。 如果图G中每一条边顶点的偶对都是有序的，则称G为有向图。在有向图中，一条有向边是由两个顶点组成的有序对，通常用表示一条有向边。V

23、i称为边的始点或弧尾，Vj称为边的终点或弧头。和 这两个偶对代表不同的边。 图7-6 图的表示 如果图G的每一条边顶点的偶对都是无序的，则称G为无向图。通常用（Vi，Vj）表示一条无向边。在 无向图中，（Vi，Vj）和（Vj，Vi）这两个偶对代表同一条边。 图6-19所示的是有关图的两个例子G1和G2。G1为无向图，G2为有向图，集合的表示形式： G1=（V，E） V(G1)=1，2，3，4，5 E(G1)=(1，2)，(1，3)，(1，4)，(2，3)，(3，4)，(4，5) G2=(V，E) V(G2)=1，2，3，4，5 E(G2)=， 在有向图中，用箭头表示边的方向，箭头从始点指向终点

24、。 几个概念：（1） 邻接点：有边相连的点。（2） 顶点的度：与每个顶点相连的边数（3） 路径：某一顶点到达另一顶点所经过的顶点序列。两个顶点之间可以有多条路径。路径上的边的数目称为路径的长度。常见算法 一、线性表的查找 线性表的查找常用的算法有2种：顺序查找、折半查找、分块查找。 顺序查找 顺序查找的过程是从表中第一个记录开始，逐个进行记录关键字和给定值的比较，若某个记录的关键字结和给定的值相等，则查找成功，找到所查的记录；否则，直到最后一个记录，其关键字和给定的值都不相等，则表中没有所查的记录，查找不成功。其查找的平均时间长度为：（N+1）/2，顺序查找和将要讨论的其它查找算法相比，其缺点

25、是平均查找时间长，特别是当N特别大时，查找效率较低。然而，它有很大的优点：算法简单且适用的范围广，它对表的结构无任何要求，无论是记录是否按关键字排序均可适用。例：在如下的线性表中查找：23、78、16、34、54、12、98、64、30A 找：54？成功，查找长度为5。B 找：19？失败，查找长度为9。 折半查找（二分法查找） 折半查找又称为二分法查找，折半查找的前提是线性表已经按关键字排好序，其基本思想是：由于待查找的表已经事先按某种顺序排好序（设为升序），则查找时不必像顺序查找一样按顺序逐个比较，而是先与中间的关键字进行比较，若相等，则查找成功，若不相等，则把查找值和中间的关键字进行比较，

26、若比中间的关键字还小，则在前半部分继续进行折半查找（因为已经排好序），否则在后半部分继续进行折半查找，这样，每进行一次比较，就将查找的区间缩短为原来的一半，这也是二分法名称的来源之所在，折半查找算法的查找平均查找时间为：Log2N-1虽然折半查找的平均时间小于顺序查找，但是折半查找只能适用于有序表，且局限与顺序存储结构，对线性表无法进行折半查找。 例如：有数列1 5 7 23 56 89 120 210 序号： 1 2 3 4 5 6 7 8若要查找的数为23：次数 1 查找区间18 状态：成功若查找的数为3：次数 查找区 状态1 182 133 12 查找成功 分块查找分块查找是介于顺序查找

27、与二分法查找之间的一种查找方法，又称索引顺序查找。它的基本思想是： （1）分块：将数据划分为若干数据块，数据在块内无序，但块间有序。也就是说，第一块内的最大数据比后继所有块内的所有数据都小（假设按数据递增有序），后面的每一块内的所有数据都大于它前面的所有块的最大数据，同时又小于后继所有块内的所有数据。（2） 查找：分两步进行。块间：建立一个各块最大关键字值表，将待查数据在该表中按二分法或顺序查找进行，通过块间查找确定数据所在块。用二分法可以提高块间查找的效率。块内：在块内按书许查找方式直接查找元素。由于块间查找用了二分法，所以整个算法的效率要比顺序查找高，但事先要将数据进行分块，这在一定程度上

28、增加了时间开销。例：分块查找。待查序列为：22 13 30 54 65 58 73 69 86 查找关键字值为50的元素。（1）先将该序列等分为三块：22 13 30 54 65 50 73 69 86（2）建立一个顺序的各块最大关键字值表：30 65 86（3）根据待查的关键字在各块最大关键字值表中进行查找，确定数据可能在的块。在30 65 86中查找50，由于305065，确定数据在第二块中。（4）在第二块中顺序查找关键字为50的元素，找到了。二、内排序排序：又称为分类，它是数据处理中经常使用的一种运算，它是将一组数据元素（记录）按排序码进行递增或递减的运算操作。排序分内排序和外排序。内排

29、序，就是整个排序运算在内存中进行；外排序，则是对外存储器中的数据进行排序操作。1、插入法排序 把N个数据元素的序列分成两部分，一个是已排好序的有序部分，另一个是未排好序的未排序部分；把未排好序的元素逐个与已排好序的元素比较，并插入到有序部分的合适位置，最后得到一个新的有序序列。例：插入法排序。（线性表长度 n=8） 初始序列 49 38 65 97 76 13 27 49（1） 38 49 65 97 76 13 27 49（2）38 49 65 97 76 13 27 49（3）38 49 65 97 76 13 27 49（4）38 49 65 76 97 13 27 49（5）13 38

30、 49 65 76 97 27 49（6）13 27 38 49 65 76 97 49（7）13 27 38 49 49 65 76 97 2、选择排序 每一趟排序中，将第I个元素与从序列第I+1到n的n-I+1(I=1,2,3n-1)个元素中选出的、值最小的一个元素进行比较，若该最小元素比第I个元素小，则将两者交换。I从1开始，重复此过程，直到I=n-1. 简洁地说，通过交换位置，选最小的放在第一，次小的放在第二，依次类推，直到元素序列的最后为止。 例：选择排序。（线性表长度n=8） 初始序列：49 38 65 97 76 13 27 49（1） 13 38 65 97 76 49 27

31、49（2） 13 27 65 97 76 49 38 49（3） 13 27 38 97 76 49 65 49（4） 13 27 38 49 76 97 65 49（5） 13 27 38 49 49 97 65 76（6） 13 27 38 49 49 65 97 76（7） 13 27 38 49 49 65 76 97 以第一、二步为例：49与13比较后互换，38与27比较后互换以后各步依此类推。 选择排序是一种不稳定的排序方法。 3、冒泡排序 冒泡法排序需要进行n-1趟排序过程。 例：冒泡排序过程。（线性表长度n=7） 初始状态： 65 97 76 13 27 49 58 第一趟（I

32、=16） 65 76 13 27 49 58 97 第二趟（I=15） 65 13 27 49 58 76 97 第三趟（I=14） 13 27 49 58 65 76 97 第四趟（I=13） 13 27 49 58 65 76 97 第五趟（I=12） 13 27 49 58 65 76 97 第六趟（I=1） 13 27 49 58 65 76 97 4、归并排序 将两个或两个以上的有序表组合成一个新的有序表。 将每个元素看成一个长度为1的子序列，把相邻子序列两两合并，得到一个新的子序列，如此重复，最后得到长度为n的一个新的有序序列。 例：归并排序过程。（线性表长度n=7） 初始序列：25 57 48 37 12 92 86 （1） 25 57 37 48 12 92 86 （两两合并） （2） 25 37 48 57 12 86 92 （两两合并） （3） 12 25 37 48 57 86 92 （两两合并） 几种排序比较： （1）稳定性比较：稳定的排序方法有：插入，归并，冒泡排序； 不稳定的排序方法有：选择排序。 （2）平均综合情况：归并排序速度较快，插入、冒泡排序速度较慢。 总之，各种排序法各有其优缺点。其选用依据是： 其数据规模n大，内存允许，要求稳定，选归并排序。 其数据规模n较小，有稳定要求，选插入排序。 其数据规模n较小，对稳定不要求，用选择排序。