《数据结构笔记》由会员分享，可在线阅读，更多相关《数据结构笔记（20页珍藏版）》请在金锄头文库上搜索。
1、数据结构笔记基础：数据结构与算法（一）数据结构基本概念数据（data）:是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被 计算机程序处理的符号总称数据元素（data element）:是数据的基本单位，在计算机中通常被当做一个整体进行考虑 和处理数据对象（data object）:性质相同的数据元素的集合，是数据的一个子集数据结构（data structure）:相互之间存在一种或多种特定关系的数据元素的集合4类基本结构：集合、线性结构、树形结构、图形（网状）结构数据结构的形式定义为数据结构是一个二元组Data Structure =（D,S），其中D是数据元素 的有限集，S
2、是D上关系的有限集数据结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构 数据结构在计算机中的表示（映像）称为物理结构（存储结构）计算机中表示信息的最小单位是二进制中的一位，叫做位（bit），一到若干位组成一个位 串表示一个数据元素，这个位串称为元素或结点数据结构之间关系在计算机中的表示有两种：顺序映像、非顺序映像，并由此得到两种存储 结构：顺序存储、链式存储，前者运用相对位置表示数据元素间的逻辑结构，后者借助指针 任何一个算法的设计取决于数据（逻辑）结构，而实现依赖于存储结构数据类型是一个值的集合和定义在这个值集上的一组操作的总称数据类型分两种：原子类型、结构类型，
3、前者不可分解（例如int、char、float、void），后者结构类型由若干成分按某种结构组成，可分解，成分既可以是非结构的也可以是结构的 （例：数组）抽象数据类型（Abstract Data Type）:是指一个数学模型及定义在该模型上的一组操作（P8） 抽象数据类型格式如下：ADT抽象数据类型名数据对象： 数据对象的定义数据关系： 数据关系的定义数据操作： 数据操作的定义ADT抽象数据类型名基本操作格式如下：基本操作名（参数表）初始条件： 初始条件描述操作结果： 操作结果描述多形数据类型（polymorphic data type）：是指其值得成分不确定的数据类型（P9）抽象数据类型可由
4、固有数据类型来表示和实现（二）算法（概念）和算法分析（时、空性能）算法（algorithm）:对特定问题求解步骤的一种描述算法5特性：有穷、确定、可行、输入、输出1、有穷性：算法必须在可接受的时间内执行有穷步后结束2、确定性：每条指令必须要有确切含义，无二义性，并且只有唯一执行路径，即对相同的 输入只能得相同输出3、可行性：算法中的操作都可通过已实现的基本运算执行有限次来完成4、输入：一个算法有一到多个输入，并取自某个特定对象合集5、输出：一个算法有一到多个输出，这些输出与输入有着某些特定关系的量算法设计要求（好算法）：正确性、可读性、健壮性、效率与低存储需求健壮性是指对于规范要求以外的输入能
5、够判断出这个输入不符合规范要求，并能有合理的处 理方式。算法效率的度量：（1）事后统计：程序运行结束后借助计算机内部计时功能，缺点一是必须先运行依据算法 编制的程序，二是受限于计算机软硬件，导致掩盖了算法本身的优劣（2）事前分析估计：消耗时间影响因素：算法策略、问题规模、编程语言、编译程序产生的机器码质量、 机器执行指令的速度撇开各种影响因素只考虑问题的规模（通常用整数量n表示），记为问题规模的函数 算法时间取决于控制结构（顺序，分支，循环）和固有数据类型操作的综合效果 书写格式：T（n）= O（f（n） f（n）为n的某个函数时间复杂度：算法的渐近时间复杂度（asymptotic time
6、complexity），它表示随问题规模的增大，算法执行时间的增长率和f（n）的增长率相同以循环最深层原操作为度量基准频度：该语句重复执行的次数算法的存储空间需求：空间复杂度（space complexity）:算法所需存储空间度量，记作S（n）= O（f（n）， 其中n为问题规模的大小排序方法时间复杂度零间复余 皮稳;t性夏杂牲平均情况彘坏情况最好情 况直搓插入持O(n2)O(n)OC0简单希尔排序(nlog2ii)0(1)不稳定兹复杂冒泡排序O(n2)O(i)Bn)OC0趋定简单快速耕序不摧定疫复杂直接逸择排 序O(ii2)0(1/)0(1/)Ofl)不稳定却排序0(U10g21l)W1J
7、不荏定技更杂归井排序Ofnlogju)Ofiilo gan)0(1110211)0(10稳宅较复杂旺夏杂 mAvhuslei基楚排序l(：u-i)( 记录- 文件，例如每个学生情况为一个记录，它由学号、性 别.数据项组成，多个学生记录组成一个文件在形如（a1，.，ai-1，ai，ai+1，.，an）中，ai-1 领先于 ai，ai 领先于 ai+1，且形成直接前驱元素，直接后继元素关系元素个数n定义为线性表长度，n=0为空表相关操作算法见书（P20）（二）线性表顺序存储结构和链式存储结构（1）线性表顺序表示和实现线性表顺序存储在一组连续的存储单元中，链式存储则不要求；顺序结构可以随机访问，链
8、式结构可以无限扩容确定存储位置（计算公式）：第i个元素：LOC（ai）= LOC（a1）+（i-1）*LL是偏移量，即每个元素占用存储单元第ai+1个元素：LOC（ai+1）= LOC（ai）+L a1 （起始地址或基地址）C语言下标从“0”开始，则表中第i个元素是L.elem i-1当对线性表进行操作时，被操作元素后面的元素角标会相应变化（前移、后移），算法（P24）（2）线性表链式表示和实现特点：用一组任意的存储单元存储线性表的数据元素（存储单元不一定连续）结点存储数据元素及直接后继的存储位置信息，两个域：数据域和指针域，指针域中存储的 信息称为指针或链，仅含有一个指针域故又称线性链表或单
9、链表链表的插入：先增加一条指针再修改原指针头指针指向第一个数据元素的存储位置，最后一个结点的指针为空（NULL）链表表示方法及算法（P28）单链表第一个结点前加一个头结点Head，其数据域可为空也可存储一些附加信息（链长等） 假设p是指向线性表中i个元素（ai）的指针，则p-next是指向i+1个数据元素 在单链表中，取得第i个元素必须从头指针开始寻找，因此单链表是非随机的存储结构 线性表指逻辑结构，从抽象数据层面来说顺序表和链表指物理存储结构逻辑结构：离散、线性、层次、网状 应用见书算法二、栈和队列（一）栈的基本概念栈（stack）是限定仅在表尾进行插入或删除操作的线性表表尾为栈顶，表头为栈
10、底，遵循后进先出原理（last in first on，LIFO），不含元素则 为空栈操作：在栈顶插入（入栈）和删除（出栈），栈初始化、判空、取栈顶元素（算法P45）（二）栈的顺序存储和链式存储顺序栈，即栈的顺序存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元 素，同时附设指针top指示栈顶元素在顺序栈中的位置初始栈时不应限定栈的最大容量，基本做法是先为栈分配一个基本容量，然后在应用过程 中，不够用再逐段扩大（算法P46）（三）递归栈与递归的实现：一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称 为递归函数阶乘函数、2阶Fibonacci数列、Ackerman函数、3
11、阶Hanoi问题（多阶呢？）（P54）函数调用函数执行过程笔记（P56）（四）队列队列先进先出（first in first out，FIFO），队尾一端插入，队首一端删除元素（日常排队）队列与栈均有八种基本操作（P59），队列一般用链表实现，栈用顺序表实现双端队列（限定操作的队列）（P60）（五）栈和队列的应用链队列、循环队列（P60），离散事件模拟（银行接待工作（P65）（六）特殊矩阵的压缩存储如何存储矩阵的元，使矩阵的运算有效进行。高级语言常用二维数组存储阵元面对如高阶矩阵，多值相同矩阵和多零元素矩阵进行压缩存储节省空间压缩存储：为多个值相同的元只分配一个空间，对零元不分配值相同元素或零
12、元素具有分布规律则称为特殊矩阵，反之为稀疏矩阵具体应用与算法（P95）三、树与二叉树（一）树的基本概念树是非线性数据结构，以分支关系定义的层次结构树是n（n=0）个结点的有限集详见（P118），基本术语（P120）（二）二叉树1. 二叉树的定义及其主要特征：二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree） 和“右子树”（right subtree）。性质：1.2.3.满二叉树：完全二叉树：4.5.2. 二叉树的顺序存储结构和链式存储结构顺序存储，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结 点元素，即将完全二叉树上编号为i的结点
13、依次存储在如上定义的一位数组下标为i-1的 分量中。123456789链式存储，每个结点中至少包含三个域，左指针，数据，右指针，称作“二叉链表” 增加一个双亲指针域，则称作“三叉链表”详见P126-1273. 二叉树的遍历遍历二叉树，每个结点均被访问一次，且仅有一次。在限定先左后右的访问序列后，有三 种遍历方式：先序（DLR），中序（LDR），后续（LRD）P129算法6.1 （波兰式）层次遍历，无论那种遍历方式，对含n个结点的二叉树，时间复杂度都为O（n），空间 复杂度也为O（n）。4. 线索二叉树的基本概念和构造摘要：对于n个结点的二叉树，在二叉链存储结构中有n+1（2n-（n-1）个空链
14、域，利 用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为 线索 概念：加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树（ThreadedBinaryTree）。构造方法：（三）树与森林1. 树的存储结构链表结构：1.双亲表示法2.孩子表示法3.孩子兄弟表示法详见P1352. 森林与二叉树转换-左孩子右兄弟3. 树与森林的遍历先序、中序遍历，详见P139当以二叉链表做树的存储结构时，树的先序=二叉树先序、树的后序=二叉树中序（四）树与二叉树的应用1. 二叉排序树二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。定义：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；（4）没有键值相等的节点。步骤：若根结点的关
