数据结构 教学课件 ppt 作者 江家宝 程勇 数据结构-江家宝
155页1、数据结构,学习方式, 听课 (启发式、讨论式) 读书 (预习、复习) 报告 (综合练习),考试成绩,平时成绩 (书面作业、上机练习、综合练习) 上机考试 期末笔试,内容安排,第一章 数据结构的基础知识 第二章 线性表 第三章 栈与队列 第四章 串 第五章 数组与广义表 第六章 树,内容安排,第七章 图 第八章 查找 第九章 内部排序,数据结构 第一章 数据结构的基础知识,基本概念和相关术语,数据 所有能输入到计算机之中,并能被计算机程序所处理的符号 的总称。如数字,字母,标点符号、图形图像 、声音等。 数据元素 描述数据的基本单位(数据项) 数据对象 性质相同的一类数据元素的集合 数据逻辑结构 数据元素之间的组织形式:集合、 线性结构、树形结构 网状结构。,基本概念和相关术语,物理结构 数据在计算机内部的实际存储结构 结点 存储在内存中的数据元素 域 数据元素中的每个数据项 线性存储结构 用物理地址相邻来表示数据元素在逻辑上的相邻关系。 链式存储结构 元素之间逻辑上的相邻关系物理地址上不一定相邻,而是通过指针来描述,抽象数据类型,数据类型是和数据结构密切相关的一 个概念。不同的数据类型
2、拥有不同的取值 范围和允许的操作。从硬件的角度来看, 数据类型涉及具体存储单位。如int型占用 两个字节的存储空间,float型占用4个字节 的存储空间,可以帮助程序开发人员了解 内存的使用情况。,抽象数据类型,抽象数据类型(Abstract Data Type,ADT) 原子类型 固定聚合类型 可变聚合类型 抽象数据类型的组成(三元组 D S P) D表示数据对象 S是D上的数据关系 P表示D的基本操作,算法分析,算法 对特定问题求解步骤的一种描述,然后再依据算法编制程序完成 要求。 特性 有穷性 确定性 可行性 输入 输出 好的算法特性 正确性 可读性 健壮性 高效率 低存储,算法的时间复杂度分析,事后统计法 直接比较运行时间 事先分析法 用数学方法直接对算法的效率进行分析 指令的执行次数 抛弃特定的软硬件配置有关的因素,直接求出算法中 加法和乘法的执行次数。,下课了。,追求,休息一会儿。,数据结构 第二章 线性表,线性表,定义 具有相同类型的n个数据元素的有限序列。元素之间存在着线性的逻辑关系。,前驱结点和后继结点,以ai为例, ai+1是它的直接后继元素, ai-1是它的直接前
3、驱元素。,线性表顺序存储结构,定义 把线性表存储在一串连续的内存地址的结构叫做线性 表的顺序存储结构。 优点 只要知道第一个数据元素的位置,就可以很快地找到 表中任何一个元素。 基本操作 插入、删除、查询,线性表的链式存储结构,链表 一种动态存储结构,在需要插入一个结点时,按结 点的类型向系统申请一个结点的存储空间;当删除一 个结点时,就将这个结点的存储空间释放,它比顺序 存储方式更加灵活、高效。 结点 表示数据元素内容的部分称为数据域,表示直接后 继元素或直接前驱元素位置的部分称为指针。,单链表,单链表结点由两部分组成:一部分是该结点的数值, 另一部分是指向直接后继结点的指针。,可以将链表画成如下的形式,h是头指针,它指向单链表的第一个结点,是单链表的入口地 址访问单链表的任何结点必须由头指针出发。,单链表的基本操作,链表的建立 计算表长 查询元素 插入结点 删除结点,循环链表,将单链表的最后一个结点的指针域指向头结点,从而 形成一个环状,由此,从表中任意一结点出发都可以访 问到表中其他的结点。,循环链表,需要在第一个结点之前附加一个头结点作为标记,头 结点的数据域存储任何信息,指针
4、域指向第一个结点。,循环链表的基本操作,循环链表的操作与单链表基本一致,如插入、删除、 查找、输出等。区别仅仅在于尾结点的判定条件不同。,双向链表,在需要同时频繁访问前驱和后继结点的时候,定义一 种新型的存储结构双向链表。每个结点包含两个指 针域:一个指向前驱结点,另一个指向后继结点。,双向链表,双链表为当前结点与它们的前后继结点都建立明 确的逻辑关系,这样就解决了链表反方向访问结点的 问题。,可以方便地向前访问结点,既不需要像单链表那样重新遍历结点,也不需要像循环链表那样从尾结点“跳回”到头结点 。,双链表的基本操作,双链表的建立 插入 删除,循环双链表,一种变化的双链表形式。它借鉴了循环链表的思 想,将双链表的最后一个结点的后继指针指向头结点, 头结点的前驱指针指向最后一个结点。,循环双链表实质上是两个单循环链表的合成,结点类型和基 本操作与双链表完全一样,直接采用双链表结点的定义。,循环双链表的基本操作,循环双链表的构造 循环双链表的遍历 插入 删除 查找,下课了。,追求,休息一会儿。,数据结构 第三章 栈与队列,栈和队列,定义 栈和队列是两种特殊的线性表。插入和删除操作均在 对
《数据结构 教学课件 ppt 作者 江家宝 程勇 数据结构-江家宝》由会员E****分享,可在线阅读,更多相关《数据结构 教学课件 ppt 作者 江家宝 程勇 数据结构-江家宝》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页