数据结构与算法_数据结构 .pptxVIP

数据结构与算法目数据结构的概念内存的存储结构数据结构的分类顺序表存储方式顺序表的实现和扩充顺序表增加与删除元素录Contents 知道什么是数据结构 知道数据结构和算法的关系目标TARGET1.1 数据结构的作用数据结构是存储、组织数据的方式 . 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率 , 数据结构往往同高效的算法有关举个栗子:我们希望存贮一个 班级的学员信息1. 数据结构的概念1.1 数据结构的作用存储方式2:字典存储方式1:列表查找学员钢铁侠:查找学员钢铁侠:时间复杂度 : O(1)时间复杂度 : O(n)由此我们可以看出 , 相同的数据用不同的方式也就不同的数据结构存储 那么带来的运行或者存储效率是不同的1. 数据结构的概念1.2 算法与数据结构的区别数据结构和算法都是为了提高程序的运行效率 , 他们的区别是什么?数据结构只是静态的描述了数据元素之间的关系高效的程序需要在数据结构的基础上设计和选择算法算法是为了解决实际问题而设计的，数据结构是算法需要处理问题的载体1. 数据结构的概念1.2 算法与数据结构的区别业务存储数据业务目的最优数据结构最优算法数据数据结构 + 算法 = 程序1. 数据结构的概念数据结构是存储、组织数据的方式 .精心选择的数据结构可以带来更高的运行或者存储效率算法是为了解决实际问题而设计的，数据结构是算法需要处理问题的载体总结总结目数据结构的概念内存的存储结构数据结构的分类顺序表存储方式顺序表的实现和扩充顺序表增加与删除元素录Contents目标 知道内存怎么存储数据TARGET2.1 内存存储结构内存是以字节为基本存储单位的(1024b = 1kb) , 每个基本存储空间都有自己的地址0x110x120x130x14整形(int) : 4个字节字符(char): 1个字节 . 单个字符“a”占1个字节, 字符串“abc”占3个字节num = 100x11name1 = “a”name2 = “b”name3 = “c”0x11a100x12b0x13c2. 内存的存储结构内存是以字节为基本存储单位的(1024b = 1kb) , 每个基本存储空间都有自己的地址 , 内存地址是连续的整形(int) : 4个字节字符(char): 1个字节总结总结目数据结构的概念内存的存储结构数据结构的分类顺序表存储方式顺序表的实现和扩充顺序表增加与删除元素录Contents目标 知道数据结构有哪些类型TARGET3.1 线性结构数据结构的分类:①线性结构②非线性结构线性结构:简单地说，线性结构就是表中各个结点具有线性关系线性结构的特点:①线性结构是非空集②线性结构所有结点都最多只有一个直接前驱结点和一个直接后继结点开始123结束典型的线性结构 : 栈、队列等3. 数据结构的分类3.2 非线性结构非线性结构:简单地说，非线性结构就是表中各个结点之间具有多个对应关系非线性结构的特点:①非线性结构是非空集②非线性结构的一个结点可能有多个直接前驱结点和多个直接后继结点3800129033典型的非线性结构 : 树结构和图结构等3. 数据结构的分类数据结构的分类:①线性结构②非线性结构线性结构:线性结构就是表中各个结点具有线性关系非线性结构:非线性结构就是表中各个结点之间具有多个对应关系总结总结目数据结构的概念内存的存储结构数据结构的分类顺序表存储方式顺序表的实现和扩充顺序表增加与删除元素录Contents目标 知道什么是顺序表TARGET4.1 线性结构存储方式的分类线性结构的实际存储方式，分为两种实现模型：①顺序表 : 将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示②链表 : 将元素存放在通过链接构造起来的一系列存储块中 , 存储区是非连续的顺序表和链表都是线性的存储结构, 我们称之为线性表链表: 非连续的存储顺序表: 连续的存储 1010202030304. 顺序表存储方式4.2 顺序表顺序表存储数据的两种情况:①一体式结构②分离式结构0x11num会记录列表的首元素地址0x11由于列表所有的数据都是整形,大小都为4个字节,偏移量为4第一个元素10 : 通过0x11偏移4*0个字节可以找到第二个元素20 : 通过0x11偏移4*1个字节可以找到第三个元素30 : 通过0x11偏移4*2个字节可以找到查找数据的公示 : 0x11 偏移 4 * (n-1) 个字节 num = [ 10 , 20 , 30]0x11第一10第二20第三304. 顺序表存储方式4.3 顺序表0x11num = [ 10 , “A”, “ABC”]0x11第一10第二A第三ABCnum会记录列表的首元素地址0x11由于列表中数据大小