683-7.3 数据结构基础.ppt

  1. 1、本文档共54页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
7.3.1 数据结构的基本概念 1.数据 3.数据对象 5.逻辑结构与物理结构 6.数据类型 7.数据的运算 8.线性结构与非线性结构 1.线性表的定义和运算 2.顺序存储线性表 3.线性链表 例 题 例 题 1.栈的定义 2.栈的基本运算 例 题 1.队列的定义 2.队列的基本运算 3.循环队列 小 结 为了高效地解决复杂的应用课题,必须要掌握数据结构和算法的有关知识。数据结构主要研究和讨论各数据之间所固有的逻辑关系、各数据在计算机中的存储关系、对各种数据结构进行的运算,主要目的是提高数据处理的效率。线性表、栈、队列是基本的数据结构,研究它们的存储结构及其基本运算具有十分重要的意义,通过对本章的学习,要求同学们熟悉数据结构的基本概念、线性表、栈、队列这三本数据结构的存储结构及其基本运算,为 作 业 7.3.2 线性表 链式存储结构不需要一组连续的存储单元,它的数据元素可以分散存放在存储空间中。为保持线性表的逻辑上连续,必须在每个元素中存放其后继元素的地址。由n个节点组成的序列便构成一个链表,称为线性表的链式存储结构。 (1)链式存储结构 链式存储结构 节点中用于存放数据元素信息称为数据域,用于存放其后继节点地址的称为指针域。节点组成如图7-5所示。 数据域 指针域 图7-5 链式存储结构 线性链表 为了在线性链表中插入一个新元素,首先要给该元素分配一个新节点,以便用于存储该元素的值,新节点可以从可利用栈中取得,然后将存放新元素值的节点链接到线性链表中指定的位置。 (2)线性链表的基本运算 ① 线性链表的插入: 【例7.2】设p指向单链表中某节点,s指向待插入的值为x的新节点,将s插入到p的后面如图7-6所示。 x s 图7-6 将s插入到p的后面 p 线性链表的基本运算 指在线性链表中删除包含指定元素的节点,首先要在线性链表中找到该节点,然后将要删除的节点放回可利用栈。 ①线性链表的删除: 【例7.3】设p指向单链表中某节点,删除*p。要实现对节点*p的删除,首先要找到*p的前驱节点*q,然后完成指针的操作即可,如图7-7所示。 p q 图7-7 删除*p 线性链表的基本运算 在线性链表的插入删除操作中,不需移动元素,只需改变相应节点的指针域即可。 注意! 线性链表 所谓循环链表是指链表的最后一个节点的指针值指向第一个节点,整个链表形成一个环。对于循环链表而言,只要给定表中任何一个节点的地址,通过它就可以访问表中所有的其他节点,而不像单向链表那样一定要指出第一个节点的地址,才能访问其后的节点。循环链表如图7-8所示。 (3)循环链表 循环链表 图7-8 循环链表 非空表(a) 空表(b) 7.3.3 栈 栈是一种特殊的线性表,在栈中的插入与删除都只在线性表的一端进行,插入与删除也不需要移动表中的其他元素,这种线性表称为栈。 (1)线性表定义 栈的定义 在栈中,允许插入与删除的一端称为栈顶,通常用指针TOP来指向栈顶的位置,不允许插入与删除的一端称为栈底。 栈顶和栈底 栈顶元素总是最后插入的元素,从而也是最先能被删除的元素,即栈是按照“先进后出”(FILO)或“后进先出”(LIFO)的原则组织数据。 插入删除原则 7.3.3 栈 栈的基本运算有入栈、退栈、读栈顶元素3种。 (1)入栈运算: 入栈运算是指在栈顶位置插入一个新元素,它首先将栈顶指针进一,然后将新元素插入到指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,不可能再进行入栈操作,这种 情况称为“上溢”。 栈的基本运算 (2)退栈运算: 退栈运算是取出栈顶元素给一个指定的变量,它首先将栈顶元素赋给一个指定的变量,然后将栈顶指针退一。当栈顶指针与栈底指针重合时,不可能进行退栈操作,这种情况称为“下溢”。 栈的基本运算 (3)读栈顶元素 : 读栈顶元素是指将栈顶元素赋给一个指定的变量,但这个运算不删除栈顶元素,栈顶指针也不会动。 【例7.4】如图7-9所示栈中有3个元素,进栈的顺序是a1、a2、a3,当需要出栈时其顺序为a3、a2、a1。 图7-9 栈 7.3.4 队列 队列也是一种特殊的线性表,队列是一种“先进先出”(FIFO)的线性表,它只允许在表的一端插入元素,而在表的另一端删除元素。在队列中,允许插入的一端称为队尾,允许删除的一端称为队头。 队列的定义 如图7-10所示是一个有5个元素的队列。入队的顺序依次为a1、a2、a3、a4、a5,出队时的顺序将依然是a1、a2、a3、a4、a5 。 入队 出队 a1 a2 a3 a4 a5 图7-10 队列 7.3.4 队列 每进行一次入队运算,队尾指针进一,然后将新元素插入到队尾指针所指的位置。如不能入队,说明队列

文档评论(0)

小玉儿 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档