数据结构知识.docVIP

数据结构的概述 定义：我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器中，以及在此基础上为实现某个功能（比如查找某个元素和删除某个元素，对所有元素进行排序）而执行的相应的操作，这个相应的操作也叫算法 。 数据结构 = 个体 + 个体的关系 算法 = 对存储数据的操作 数据结构 狭义： 数据结构是专门研究数据存储的问题 数据的存储包含两方面：个体的存储 + 个体关系的存储 广义： 数据结构既包含数据的存储也包含数据的操作 对存储数据的操作就是算法 算法： 狭义 算法是和数据结构的存储方式密切相关 广义 算法和数据的存储方式无关 这就是泛型思想 数据的存储结构有几种 线性 连续存储【数组】 优点：存取速度很快 缺点：事先必须知道数组的长度 插入删除元素很慢 空间通常是有限制的 需要大块连续的内存块 离散存储【链表】 优点：空间没有限制 插入删除元素很快 缺点：存取速度很慢 线性结构的应用 -- 栈 线性结构的应用 -- 队列 非线性 算法： 解题方法和步骤 衡量算法的标准 时间复杂度 大概程序要执行的次数，而非执行的时间 空间复杂度 算法执行过程中大概所占用的最大内存 难易程度 健壮性 数据结构的地位 数据结构是软件中最核心的课程 程序 = 数据的存储 + 数据的操作 + 可以被计算机执行的语言 预备知识 指针 指针是C语言的灵魂 定义 地址 地址就是内存单元的编号 从0开始的非负数 范围：0—FFFFFFFF【0 – (4G-1)】 指针： 指针就是地址，地址就是指针 指针变量是存放内存单元地址的变量 指针的本质是一个操作受限制的非负数 分类： 1.基本类型的指针 2.指针和数组的关系 结构体 为什么会出现结构体 为了表示一些复杂的数据，而普通的基本类型变量无法满足要求 如何让使用结构体 结构体是用户根据实际需要自己定义的符合数据类型 两种方式： Struct Student st = {1000,”zhangsan”,20}; Struct Student * pst = st; 1.：St.sid 2.：Pst-sid pst所指向的结构体变量中的sid这个成员 注意事项： 结构体变量不能加减乘除，但可以相互赋值 普通结构体变量和结构体指针变量作为函数传参的问题 动态内存的分配和释放 模块一：线性结构【把所有的结点用一根直线穿起来】 连续存储【数组】 1.什么叫数组 元素类型形同，大小相等 2.数组的优缺点： 离散存储【链表】 定义： n个节点离散分配 彼此通过指针相连 每个节点只有一个前驱节点，每个节点只有一个后续节点 首节点没有前驱节点，尾节点没有后续节点 专业术语： 首节点：第一个有效的节点 尾节点：最后一个有效的节点 头结点：头结点的数据类型和首节点的类型一样 第一个有效节点之前的节点 头结点并不存放有效数据 加头结点的目的是为了方便对链表的操作 头指针：指向头结点的指针变量（第一个节点的地址） 尾指针：指向尾节点的指针变量 如果希望通过一个函数来对链表进行处理，我们至少需要接受链表的哪些参数 只需要一个参数：头指针 因为我们通过头指针可以推算出链表的其他所有信息