苏州营销网站建设,如何搭建一个网站,网络推广阶段策划,搜狐快站做的手机网站系列综述#xff1a; #x1f49e;目的#xff1a;本系列是个人整理为了数据结构复习用的#xff0c;由于牛客刷题发现数据结构方面和王道数据结构的题目非常像#xff0c;甚至很多都是王道中的#xff0c;所以将基础知识进行了整理#xff0c;后续会将牛客刷题的错题一… 系列综述 目的本系列是个人整理为了数据结构复习用的由于牛客刷题发现数据结构方面和王道数据结构的题目非常像甚至很多都是王道中的所以将基础知识进行了整理后续会将牛客刷题的错题一并整理到该文章中可以考试复习或者找工作复习使用。 来源材料主要源于《王道数据结构考研复习指导》进行的每个知识点再考研中及复习至少思考过三遍比较可靠。 结语如果有帮到你的地方就点个赞和关注一下呗谢谢 文章目录数据结构一、绪论基本概念数据结构三要素算法二、线性表三、栈和队列栈队列四、串串的定义和实现串的存储结构五、树与二叉树树二叉树树与森林二叉排序树平衡二叉树六、图基本概念图的存储图的遍历图的应用七、查找基本概念静态查找动态查找八、排序插入排序交换排序选择排序特殊排序内部排序算法比较参考博客点此到文末惊喜↩︎ 相关思维导图https://wwb.lanzouy.com/iAZyi0d3qbyd 数据结构
一、绪论
基本概念
数据对象⊃数据元素⊃数据项数据对象 \supset 数据元素 \supset 数据项数据对象⊃数据元素⊃数据项 数据对象是具有相同性质的数据元素的集合数据元素是数据的基本单位由若干数据项组成据项是构成数据元素不可分割最小单位 数据类型是一个值的集合和定义在该集合上的一组操作 原子类型值不可再分结构类型值可以再分 数据结构 定义数据元素 相互关系数据的运算实质就是算法的执行由逻辑结构定义由存储结构实现。不能过于考虑逻辑结构而忽略存储结构是否容易实现逻辑结构和存储结构都影响着算法的好坏。
数据结构三要素
逻辑结构 集合数据元素同属于一个集合其他无任何关系线性结构数据元素之间只存在一对一的关系如栈、队列、串、数组、其他线性表树状结构数据元素间存在一对多的关系图状结构数据元素间存在多对多的关系 存储结构 顺序存储逻辑相邻的数据元素存储在物理上相邻的位置。 优点可以实现随机存取占用空间小缺点可能产生空间碎片 链式存储不同节点只要求逻辑上相邻但是节点内要求物理连续 优点无碎片现象元素的增删容易缺点指针占用额外的空间只能顺序存取 索引存储存储元素的同时建立索引表 优点查找速度快缺点索引表占用额外的空间增删数据需要花费时间修改索引表 散列存储哈希存储将数据元素的值映射成存储地址 优点增删改查都很快缺点出现哈希冲突会增大时空开销
算法
算法的特性 输入有零个或多个输入有穷性每一步均可在有穷时间内完成确定性相同的输入只能获得相同的输出可行性算法可以通过计算机基本指令实现输出至少一个输出 好的算法 正确性正确解决问题健壮性及时处理非法数据可读性易于人们理解时空开销小 算法效率的度量 时间复杂度最深层嵌套语句运算次数的数量级空间复杂度算法耗费的存储空间原地存储指O(1)O(1)O(log2n)O(n)O(nlog2n)O(n2)O(2n)O(n!)O(nn)O(1)O(log_{2}n)O(n)O(nlog_{2}n)O(n^2)O(2^n)O(n!)O(n^n)O(1)O(log2n)O(n)O(nlog2n)O(n2)O(2n)O(n!)O(nn) 二、线性表
线性表具有相同数据类型数据元素的有限序列 逻辑和物理的关系是一种逻辑结构表示数据元素一对一的相邻关系即除表头元素其他元素只有一个直接前驱除表尾元素其他元素只有一个直接后继存储空间上每个元素占用相同大小的存储空间 顺序表线性表的顺序存储逻辑结构和存储结构的结合 逻辑和物理的关系表中逻辑顺序和物理顺序相同存储空间上每个节点只存储数据元素不需要浪费额外空间增删改查插入和删除需要移动大量元素但是可以随机存取静态分配数组大小在编译阶段确定执行时一旦超过可能发生溢出动态分配在程序执行时分配一旦超过原空间需要开辟更大的空间进行存储 单链表线性表的链式存储 逻辑和物理的关系表中逻辑顺序和物理顺序一般不相同存储空间上每个节点只存储数据元素需要额外存储指针增删改查查找需要进行遍历但是增删容易头插法链表元素的读入顺序和生成顺序时相反的尾插法链表元素的读入顺序和生成顺序时相同的 双链表每个节点有两个指针prior和next可以逆序遍历循环单链表尾指针指向头节点的链表判空条件是头节点指针是否指向自己循环双链表判空条件是头节点的prior和next都等于头节点静态链表使用数组描述线性表的链式存储 节点具有数据域和指针域指针域存放的是数组下标结束标志是next -1静态链表的插入和删除只需要修改指针不需要移动元素可用于不支持指针的高级语言Basic 三、栈和队列
栈
栈的基本概念 栈只允许在一端进行插入和删除操作的线性表即后进先出栈顶Top线性表允许进行插入删除的那一端栈底Bottom线性表不允许插入和删除的那一端空栈不含任何元素的空线性表n个不同元素进栈出栈元素不同排列的个数为1n1C2nn\frac{1}{n1}C_{2n}^{n}n11C2nn - 最后一个元素第一个出栈则输出序列一定是逆序
- 判断出栈顺序是否正确按序进栈并在栈中相邻的元素出栈一定是逆序的顺序栈采用顺序存储的栈逻辑和物理存储顺序一致//数组 栈顶指针top
#define MaxSize 50
typedef struct {Elemtype data[MaxSize];// 存放栈中元素数组栈存在上溢的问题int top;// 栈顶指针
}SqStack;栈顶指针初始化时通常设置S.top -1栈顶元素S.data[S.top]进栈操作栈不满时栈顶指针先加1再送值到栈顶元素出栈操作栈非空时先取栈顶元素值再将栈顶指针减1栈空条件S.top -1栈满条件S.top MaxSize-1栈长S.top1 共享栈 定义栈底在共享数组两端栈顶向共享空间中间延伸栈空条件top0 -1时0号栈为空top1MaxSize时1号栈为空栈满条件仅当两个栈顶指针相邻即top1 - top0 1 链栈typedef struct Linknode{Elemtype data;struct Linknode *next;
}* LiStack;定义采用链式存储的栈优点不会栈满上溢便于节点的插入和删除但是需要前一个节点的辅助
队列
队列的基本概念 定义只允许在线性表的一端进行插入而在另一端进行删除的线性表即先进先出出队在队头删除元素入队在队尾加入元素空队列不含任何元素的线性表栈和队列都是操作受限的线性表不可以随便读取栈或队列中间的某个数据 队列的顺序存储#define MaxSize 50
typedef struct {Elemtype data[MaxSize];// 存放栈中元素数组栈存在上溢的问题int front,rear;
}SqQueue;定义分配一块连续的存储单元存放队列中的元素队头指针front指向对头元素队尾指针rear指向队尾元素的下一个位置队空条件Q.front Q.rear0进队操作队不满时先送至到队尾元素再将队尾指针加1出队操作队不空时先取队头元素值再将队头指针加1假溢出存在连续出队导致分配使用的内存不足使用循环队列进行解决 循环队列 定义将存储队列元素的表在逻辑上视为一个环出队Q.front Q.rear 0入队Q.rear (Q.rear1) % MaxSize队列长度Q.rear-Q.frontMaxSize% MaxSize将队尾指针指向队尾的下一个元素牺牲了队尾指针指向的单元。将队头指针在队尾指针的下一位置作为队满的标志队满条件(Q.rear1) % MaxSize Q.front队空条件Q.front Q.rear 链队列typedef struct {ElemType data;struct LinkNode *next;
}LinkNode;
typedef struct{LinkNode *front,*rear;
}LinkQueue;定义队列的链式表示头指针指向队头节点尾指针指向队尾节点的单链表判空条件Q.front NULL Q.rear NULL设计通常将链式队列设计成带头节点的单链表统一插入和删除操作优点有利于元素数据变动无溢出问题 双端队列 定义允许前端和后端均可出入队操作的队列输出受限的双端队列允许在一端进行插入和删除在另一端只允许插入的双端队列输入受限的双端队列允许在一段进行插入和删除在另一端只允许删除的双端队列 特殊矩阵的压缩存储 压缩矩阵为多个值相同的元素值分配一个存储空间对零元素不分配存储空间特殊矩阵分布具有规律性的矩阵例如上三角矩阵、对角矩阵、对称矩阵稀疏矩阵矩阵中非零元素相对于矩阵整体元素个数来说比较少通常使用三元组存储 四、串
串的定义和实现
定义由零个或多个字符组成有限序列子串串中任意个连续的字符组成的子序列主串包含子串的串串的主要操作是以子串为对象进行的空格串由一个或多个空格组成的串串相等串的长度和每个位置对应的字符都相等
串的存储结构 定长顺序存储 #define MAXLEN 255
typedef struct{char ch[MAXLEN];// 字符串的最后一位是‘\0’int length;
}SString;堆分配存储表示 typedef struct{char *ch; // 按照串长分配存储区ch指向串的基地址int length;
}HString;串长的两种表示方式 length变量存储结束标记法 五、树与二叉树
树
定义树是n个节点的有限集合当n0时称为空树树的定义是递归的具有以下特点 树的根节点没有前驱除根节点外的所有结点都有且只有一个前驱树中所有节点可以有零个或多个后继树适合表示有层次结构的数据在n个节点的树中有n-1条边 基本概念 祖先根A到节点K的唯一路径上的任何节点称为节点K的祖先子孙如果节点B是节点K的祖先则节点K是节点B的子孙兄弟节点具有相同的父节点根A是树中唯一没有双亲的结点节点的度某个节点的孩子的个数树的度树中节点的最大度数分支节点度大于0的节点叶子节点度为0的节点节点的深度从根节点开始自顶向下逐层累加的节点的高度从该节点分支的叶节点开始自底向上逐层累加的树的高度深度树中节点的最大的层数有序树树中节点的各字数从左到右是有序的不能互换路径自顶向下两个节点所经过的结点序列构成的路径长度路径上所经过的边的个数同一个双亲之间的孩子不存在路径森林m棵互不相交的树的集合 一棵度为m的树 总节点数n0n1n2⋅⋅⋅总节点数 n_0 n_1n_2···总节点数n0n1n2⋅⋅⋅ 总度数/总分支数1∗n12∗n23∗n3⋅⋅⋅总度数/总分支数 1*n_12*n_23*n_3···总度数/总分支数1∗n12∗n23∗n3⋅⋅⋅ 总节点数总度数1总节点数 总度数 1总节点数总度数1度为m的树中第i层上至多有mi−1m^{i-1}mi−1个节点高度为h个m叉树至多有(mh−1)/(m−1)(m^h-1)/(m-1)(mh−1)/(m−1)个节点
二叉树
特点 每个节点至多有两颗子树二叉树是有序树左右子树顺序不能颠倒二叉树以递归形式定义 二叉树和度为2的有序树的区别 度为2的树至少有3个节点而二叉树可以为空度为2的树若某个节点只有一个孩子则该孩子无须区分左右次序。有序树孩子左右次序是固定的 特殊的二叉树 满二叉树一个高度为h且含有2h−12^h-12h−1个节点的二叉树称为满二叉树即树中每层都含有最多的节点。完全二叉树最后一层自左向右排列不满其余均满。即度为1的节点只有左孩子。二叉排序树左子树上所有节点的关键字均小于根节点的关键字右子树上的所有结点均大于根节点。左子树和右子树又各是一颗二叉排序树平衡二叉树书上的任一结点的左子树和右子树的深度之差不超过1 二叉树的性质 非空二叉树的叶子结点等于度为2的结点数加1n0n21n_0 n_21n0n21结点数量为n则边的数量为n-1非空二叉树的第k层至多有2k−12^{k-1}2k−1个结点高度为h的树至多有2h−12^h-12h−1个结点完全二叉树和满二叉树可以自顶向下自左向右进行顺序编号 顺序存储 定义二叉树的顺序存储是指用一组地址连续的存储单元一次自上而下、自左向右存储完全二叉树上的结点满二叉树和完全二叉树适合采用顺序存储优点 节省存储空间利用数组元素下标可以确定结点在二叉树中的位置 忽略数组第0个元素从数组下标1开始存储的性质 当i为偶数时其双亲的编号为i/2是左孩子。 当i为奇数时其双亲的编号为(i-1)/2是右孩子。结点i的左孩子编号为2i否则无左孩子 结点i的右孩子编号为2i1否则无右孩子 链式存储结构typedef struct BiNode{ElemType data; // 数据域struct BiTNode *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;在n个结点的二叉链表中含有n1个空链域 二叉树的遍历 定义某条搜索路径访问树中的每个结点使得每个结点均被访问一次由遍历序列构造二叉树 由二叉树的先序和中序序列可以唯一确定一颗二叉树由二叉树的中序和后序序列可以唯一确定一颗二叉树 有五种遍历方式空间复杂度和时间复杂度均为O(n) // 先序遍历根左右void preOrder(BiTree T){if(T ! NULL) {visit(T); // 遍历根结点preOrder(T-lchild); // 遍历左子树preOrder(T-rchild); // 遍历右子树}}// 中序遍历左根右void preOrder(BiTree T){if(T ! NULL) {preOrder(T-lchild); // 遍历左子树visit(T); // 遍历根结点preOrder(T-rchild); // 遍历右子树}}// 后序遍历左右根void preOrder(BiTree T){if(T ! NULL) {preOrder(T-lchild); // 遍历左子树preOrder(T-rchild); // 遍历右子树visit(T); // 遍历根结点}}// 层次遍历/广度优先遍历void levelOrder(BiTree T) {initQueue(Q); // 初始化辅助队列BiTree p;EnQueue(Q, T); // 将根节点入队while (!IsEmpty(Q)) { // 队列不空则循环DeQueue(Q, p); // 队头结点出队visit(p); // 访问队头结点if (p-lchile ! NULL) EnQueue(Q, p-lchild); // 左子树不空则左子树根节点入队if (p-rchild ! NULL)EnQueue(Q, p-rchild); // 右子树不空则右子树根节点入队}}线索二叉树 目的充分利用空指针域加快查找结点前驱和后继的速度方式 若无左子树令lchile指向其前驱结点 若无右子树令rchild指向其后继结点 typedef struct ThreadNode{ElemType data; // 数据元素struct ThreadNode *lchildl, *rchild; // 左右孩子指针int ltag, rtag; // 左表示前驱右表示后继1表示前后0表示孩子
}ThreadNode, *TheadTree;// 中序线索二叉树的建立
void InThread(ThreadTree T){if(T ! NULL) {InThread(T-lchild);visit(T);InThread(T-rchild);}
}
void visit(ThreadNode *q){if(q-lchild NULL){q-lchild pre;q-ltag 1;} if(pre ! NULL pre-rchild NULL){pre-rchild q;pre-rtag 1;}pre q;S
}树与森林
树的存储结构 双亲优先法 #define MAX_TREE_SIZE 100 // 树中最多的结点数
typedef struct {ElemType data; // 数据元素int parent; // 双亲数组下标
}PTNode;
typedef struct { // 树的类型定义PTNode nodes[MAX_TREE_SIZE]; // 双亲定义int n; // 结点数
}PTree;采用顺序存储第一个是根节点其双亲为-1可很快得到双亲结点但是求结点的孩子需要遍历整个结构 孩子优先法 typedef struct SNode{ElemType data;SNode *child;
}SNode;SNode T[MAX_SIZE];// 双亲结点数组使用邻接链表数组存储存储所有结点表示双亲链表元素表示双亲节点的孩子寻找孩子结点非常直接寻找双亲需要完整遍历 孩子兄弟表示法 typedef struct CSNode{ElemType data;struct CSNode *firstchild, *nextsibling; // 左指针为第一个孩子右指针为孩子的兄弟
}CSNode, * CSTree;易于查找孩子但是难以查找双亲 树转化为二叉树 每个结点的左指针指向它的第一个孩子右指针指向它在树中的相邻右兄弟 树的遍历 先根遍历先根后顺序遍历相应子树遍历序列和对应二叉树的先序序列相同后根遍历先顺序遍历子树后访问根遍历序列和该树对应二叉树的中序序列相同层次遍历按每层结点顺序访问
二叉排序树
BST的特性 左子树非空则左子树所有结点的值均小于根节点的值右子树非空则右子树所有结点的值均大于根节点的值左右子树分别各是一颗二叉排序树 重要对二叉排序树结点中序遍历可以得到一个递增的有序序列BST的非递归查找算法BSTNode *BST_Search(BiTree T, ElemType key){while (T ! NULL key ! T-data){if(key T-data)T T-lchild;elseT T-rchild;}return T;
}BST的插入和构造int BST_Insert(BiTree T, KeyType k) {if (T NULL){T (BiTree)malloc(sizeof(BSTNode));T-key k;T-lchild T-rchild NULL;return l;}else if(k T-key)return 0;else if(k T-key)return BST_Insert(T-lchlde, k);elsereturn BST_Insert(T-lchild, k);
}
// 二叉排序树的构造
void Creat_BST(BiTree T, keyType str[], int n){T NULL;int i 0;while (i n) {BST_Insert(T, str[i]);i;}
}二叉排序树的删除 若被删结点为叶结点则直接删除若被删结点只有一颗子树则让该节点的子树成为其父亲结点的子树若被删结点有左右子树则从左子树中最大结点代替被删结点从右子树中找最小结点代替被删结点 二叉排序树的查找效率 最好情况二叉排序树是一个平衡二叉树平均查找长度为O(log2n)O(log_2n)O(log2n)最坏情况输入序列是有序的则形成一颗单支树平均查找长度为O(log2n)O(log_2n)O(log2n) 二分查找的对象是有序顺序表 当有序表是静态查找表时宜用顺序表作为存储结构当有序表是动态查找表时宜用二叉排序树作为逻辑结构
平衡二叉树
定义任意结点的左右子树的高度差的绝对值不超过1目的为了避免树的高度增长过快降低二叉排序树的性能插入 调整对象最小不平衡子树四种平衡操作 平衡二叉最大深度和平均查找长度均为O(log2n)O(log_2n)O(log2n)哈夫曼树的基本概念 带权路径长度根到任意结点的路径长度经历的边的数量与该节点权值的乘积树的带权路径长度所有叶结点的带权路径长度之和哈夫曼树带权路径长度最小的二叉树 哈夫曼树的构造 给定n个带权结点序列每次取出两颗权值最小的结点构成一颗二叉树树的根节点为左右子树的结点之和并将根节点加入到序列中 哈夫曼树的特点 每个初始结点都最终成为叶结点权值越小的结点到根节点的路径长度越大初始结点数量为n个则哈夫曼树的结点总数2n-1哈夫曼树中不存在度为1的结点相同的序列可能构造不同的哈夫曼树但是带权路径长度WPL相同且为最优 哈夫曼编码 固定长度编码对每个字符用相等长度的二进制位表示可变长度编码允许对不同字符使用不等长的二进制位表示哈夫曼树通常使用可变长度编码对频率高的字符赋予更短的编码启到压缩数据的目的前缀编码没有一个编码是这个编码的前缀 由哈夫曼树构建哈夫曼编码 初始结点的权值为该节点的频率在哈夫曼树中对每个结点进行左0右1的标记每个叶子结点从根节点开始形成的01序列即为编码 六、图
基本概念
图由顶点集和边集组成顶点的个数称为图的阶 线性表可以是空表树可以是空树但是图不可以是空图顶点咋集一定非空 有向图由顶点集和有向边集也称为弧组成有向边使用vu 序列表示可以双向无向图 由顶点集和无向边集组成简单图不存在重复边和顶点到自身的边多重图允许两顶点间边数多于一条或顶点通过一条边和自己关联完全图顶点集合具有n个的无向图具有n(n-1)/2条边有向完全图顶点集合具有n个的有向图具有n(n-1)条边。在有向完全图中任意两个顶点之间都存在方向相反的两条弧G’是G的子图G V,E和G’V’ ,E’若V’是V的子集且E是E’的子集其中E’的顶点必须在V’内生成子图与主图顶点集相同的子图连通图图中任意两个顶点都有路径存在边数小于n-1的必是非连通图 极大连通子图包含主图所有边的连通子图再加入一个顶点都会使其不连通极小连通子图保持图连通并使边数最少的子图连通图的生成树包含图中所有顶点的一个极小连通子图边数必为n-1 强连通图图中的每一对顶点都有双向的路径顶点的度 无向图该顶点边的条数。无向图全部顶点的度的和等于边数的两倍有向图 入度以顶点v为终点的有向边的数目出度以顶点v为起点的有向边的数目有向图的全部顶点的入度之和与出度之和相等且等于边数 带权图/网边上带有权值的图稀疏图、稠密图使用边数的多少进行划分一般∣E∣∣V∣log∣V∣|E||V|log|V|∣E∣∣V∣log∣V∣认为是稀疏图路径由边关联的相邻顶点组成的序列 路径长度路径上边的数目回路/环第一个顶点和最后一个顶点相同的路径简单路径顶点不重复出现的路径简单回路除了第一个顶点和最后一个顶点外其余顶点不重复出现的回路距离两个顶点之间最短的路径 有向树一个顶点的入度为0其余顶点的入度均为1的有向图
图的存储
邻接矩阵 定义存储顶点之间邻接关系二维数组带权图中邻接矩阵存放着该边对应的权值有向图和无向图的矩阵n个节点生成n×n的矩阵某行某列不为零表示行序号的节点到列序号的节点有边带权图某行某列为其权值结构体#define MaxVertexNum 100 // 顶点数目的最大值
typedef char VertexType; // 顶点的数据类型
typedef int EdgeType; // 带权图中边上给权值的数据类型
typedef struct{VertexType Vex[MaxVertexNum]; // 顶点表EdgeType Edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵、边表int vexnum, arnum; // 图的当前顶点数和弧数
}MGraph;特点 无向图的邻接矩阵是对称矩阵可以进行压缩操作只存储半三角邻接矩阵表示法的空间复杂度为O(n2)O(n^2)O(n2)其中n为图的顶点数量|V|无向图的邻接矩阵的第i行或第i列非零元素或非无穷元素的个数正好是第i个顶点的度数有向图第i行全部的有值元素之和为顶点i的出度第i列全部的有值元素之和为顶点i的入度邻接矩阵容易确定顶点之间是否有边相连但确定边数花费时间比较大稠密图适合使用邻接矩阵存储 邻接表法 定义顶点表使用顺序存储边表使用链式存储结构体#define MaxVertexNum 100 // 图中顶点的最大数量
// 边表节点
typedef struct ArcNode{int adjvex; // 该弧所指向的顶点位置struct ArcNode *next; // 指向下一条弧的指针//InfoType info; // 网的边权值
}ArcNode;
// 顶点表节点
typedef struct VNode{VertexType data; // 顶点数据ArcNode *first; // 指向第一条依附该顶点的弧线的指针
}VNode,AdjList[MaxVertexNum];
// 邻接表
typedef struct{AdjList vertices; // 图的顶点数和弧数int vexnum, arcnum; // AlGraph是邻接表存储的图
}ALGraph;特点 G为无向图则所需的存储空间为O(∣V∣2∣E∣)O(|V|2|E|)O(∣V∣2∣E∣)。G为有向图则所需的存储空间为O(∣V∣∣E∣)O(|V||E|)O(∣V∣∣E∣)。邻接链表适合存储稀疏图给定顶点通过邻接链表可以很容易的找到它的所有邻边和顶点有向图的邻接链表容易计算某个顶点的出度但是不容易计算入度需要遍历全部邻接链表图的邻接链表不是唯一的各边节点的连接次序可以任意的 十字链表 定义有向图的一种链式存储结构由顶点结构体和边结构体组成常用于存储稀疏图容易求得顶点的出度和入度 邻接多重表 定义无向图的一种链式存储由顶点结构体和边结构体组成相比于邻接表同一条边需要两个节点表示在邻接多重表中只使用一个节点
图的遍历
定义从图中某一个顶点出发对图中所有顶点访问一次且仅访问一次广度优先搜索BFS
bool visited[MAX_VERTEX_NUM];
// 遍历所有节点
void BFSTraverse(Graph G){fori 0; i G.vexnum; ivisited[i] FALSE;InitQueue(Q);for(i0; iG.vexnum; i)if(!visited[i])BFS(G, i);}
// 遍历输入节点的所有子节点
void BFS (Graph G, int v){visit(v);visited[v] TRUE;Enqueue(Q, v);while(!isEmpty(Q)){DeQueue(Q,v);for (wFirstNeighbor(G,v); w0; wNextNeighbor(G, v, w))if(!visited[w]){visit(w);visited[w] TRUE;EnQueue(Q, w);}}
}算法时间复杂度 邻接表存储为O(∣V∣∣E∣)O(|V||E|)O(∣V∣∣E∣)邻接矩阵存储为O(∣V2∣)O(|V^2|)O(∣V2∣) 广度优先遍历过程可以得到一颗广度优先生成树广度优先生成树的唯一性和邻接矩阵存储表示的唯一性一致 深度优先搜索DFSbool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G){for(v0; vG.vexnum; v)visited[v]FALSE;for(v0; vG.vexnum; v)if(!visited[v])DFS(G,v);
}void DFS(Graph G, int v){visit(v);visited[v] TRUE;for(w FirstNeighbor(G, v); w0; wNextNeighor(G,v,w))if(!visited[w]){DFS(G,w);}
}DFS是一个递归算法空间复杂度为O(∣V∣)O(|V|)O(∣V∣)时间复杂度 邻接表存储为O(∣V∣∣E∣)O(|V||E|)O(∣V∣∣E∣)邻接矩阵存储为O(∣V2∣)O(|V^2|)O(∣V2∣)
图的应用
最小生成树 定义包含连通图的所有顶点 只含尽可能少的边的生成树 边的权值之和最小性质 不一定唯一图中的各边权互不相等时G的最小生成树是唯一的无向连通图G的边数比顶点数小1即G本身是一颗树时则G的最小生成树就是它本身最小生成树的边的权值之和总是唯一的且是最小的最小生成树的边数为顶点数减1 生成算法1: Prim算法 过程开始从图中任取一顶点加入树T中之后选择一个与当前T中顶点集合距离最近且加入后不生成环的顶点加入集合再重复以上过程。特点时间复杂度为O(∣V∣2)O(|V|^2)O(∣V∣2)适用于求解边稠密图的最小生成树 生成算法2: Kruskal算法 过程将边的权值由小到大进行排序不断选取当前未被选取的权值最小的边且加入后不会构成环特点主要由排序时间决定适合顶点多的图 最短路径 定义带权图中两顶点长度最短的那条路径最短路径问题分类 Dijkstra算法单源最短路径问题即求图中某一个顶点到其他各顶点的最短路径 特点1.基于贪心策略的 2.时间复杂度均为O(∣V∣2)O(|V|^2)O(∣V∣2) 3.不适用边上有负权值的Floyd算法求顶点对之间的最短路径 特点1.时间复杂度为O(∣V∣3)O(|V|^3)O(∣V∣3) 2. 不允许带有负权值边组成的回路 有向无环图不存在环的有向图简称DAG图 用于描述含有公共子式的共享从而节省存储空间 拓扑排序 AOV网使用顶点表示前后关系的有向无环图定义有一个有向无环图组成的序列且满足以下关系 每个顶点出现且只出现一次在序列中靠后的顶点不存在到前面顶点的路径每个AOV网中存在一个到多个拓扑排序序列 对AOV网进行拓扑排序 从AOV网中选择入度为0的顶点并输出从网中删除该顶点和所有以它为起点的有向边重复前两步知道当前AOV网络为空或网中不存在无前驱的顶点 特点 时间复杂度为O(∣V∣∣E∣)O(|V||E|)O(∣V∣∣E∣)有向无环图的拓扑序列唯一不能唯一确定该图若不存在拓扑序列则图中必有回路 关键路径 AOE网在带权有向图中以顶点表示事件以有向边表示活动边上的权值表示完成活动的开销概念 开始顶点源点 AOE网中仅有的一个入度为0的顶点表示整个工程的开始结束顶点汇点网中仅有的一个出度为0的顶点表示整个工程的结束关键路径从源点到汇点的所有路径中具有最大路径长度的路径。这个路径决定了工程最短结束事件 性质 只有在某顶点所代表的事件发生后从该顶点出发的各有向边所代表的活动才能开始只有在进入某个顶点的各有向边所代表的活动都结束该顶点所代表的事件才能发生网络中的关键路径可能不唯一且关键路径上的所有活动都是关键活动缩短所有关键路径上共有的任意一个关键活动 七、查找
基本概念
查找在数据集合查找表中寻找满足某种条件的数据元素分类 静态查找顺序查找、折半查找、散列查找动态查找散列查找、二叉平衡树查找、B树查找 关键字数据元素中唯一表示该元素的某个数据项的值平均查找长度所有查找过程中进行关键字的比较次数的平均值增加查找效率的数据结构都是对于查找表进行规则约束而形成的
静态查找
顺序查找 定义在线性表中遍历查找平均查找长度 ASL成功(n1)/2ASL_{成功} (n1)/2ASL成功(n1)/2ASL失败n1ASL_{失败} n1ASL失败n1 特点 当n平均查找长度较大效率低对数据元素的存储和有序性没有要求 折半查找 适用范围二分查找适用于有序顺序表存储结构必须支持随机查找时间复杂度O(log2n)O(log_2n)O(log2n) 分块查找 特点 块内元素无序块之间元素有序第一个块中的最大关键小于第二个块中的所有记录的关键字索引表中的每个元素中含有各块中的最大关键字和各块中的第一个元素的地址 理想块长度查找表长度理想块长度 \sqrt{查找表长度}理想块长度查找表长度
动态查找
B树 定义是一颗多路平衡查找树m叉的B树有以下特性 绝对平衡任一层的所有子树均高度相同根节点子树数量[2,m]关键字数[1,m-1]其他节点子树[m/2,m]关键字数[(m/2)-1,m-1]每个节点内的关键字有序左小右大叶子节点均在最后一层节点中孩子个数等于该节点中关键字个数加1B树叶子节点中对应查找失败的情况n个关键字中有n1中失败的可能性 B树的高度和磁盘存取顺序成正比不包括没有信息的叶节点那层基本操作 在B树中找节点通常存储在磁盘中在节点内找关键字通常存储在内存中 插入操作 插入后节点的关键字个数小于m可以直接插入插入后检查被插入节点内的关键字个数当插入后的节点关键字个数大于m-1时必须对节点进行分裂左部分放在原节点中中间位置元素插入到原节点的父节点右部分放到新节点中 删除操作 直接删除所在节点的关键字个数大于等于m/2兄弟够借被删除节点由父顶点代替父顶点由被借顶点代替兄弟不够借父亲顶点下来与兄弟合并 B树 具有n个关键字的节点只含有n棵子树即每个关键字对应一颗子树内部节点关键字个数n的范围是m/2≤n≤mm/2\le n \le mm/2≤n≤m根节点为1≤n≤m1\le n \le m1≤n≤m只有叶子节点包含信息全部节点非叶节点只是索引作用存盘存储块小读入内存快查找过程无论成功与否每次查找都是一条从根节点到叶子节点的路径 散列表哈希表 散列函数将查找表中关键字映射成对应地址的函数但是可能将多个关键字映射到同一个地址发生冲突哈希表建立关键字和存储地址直接的直接映射关系常用散列函数 直接定址法简单算数运算进行映射简单不会产生冲突只适合关键字分布基本连续的情况空位较多会造成存储空间的浪费除留余数法选取小于等于元素个数的最大质数进行取余运算。冲突主要取决于选取的余数数字分析法选取数码分布较为均匀的其中几位作为散列地址手机号平方取中法取关键字平方值的中间几位作为散列地址 开放定址法处理冲突的方式 定义存放新表项的空闲地址既向它的同义词表项开放又向它的非同词表项开放 缺点开放定址法不能随便删除元素可以给要删除的元素做一个标记进行逻辑删除防止中断查找路径 线性探测法冲突发生时顺序查看下一个表中的单元直到找到一个空闲单元。但是可能造成相邻散列地址的堆积导致查找效率下降平方探测法每次查找的步数呈指数增长不能探测所有单元但是可以探测一半再散列法使用两个散列函数当通过第一个散列函数得到的地址发生冲突时再利用第二个散列函数伪随机序列法出现碰撞时使用生成的伪随机序列作为增量 拉链法 顺序数组作为散列后的地址数组中的每个数据元素指向发生冲突的同义词链表 八、排序
算法的稳定性关键字相同的两个元素在排序后顺序不变
插入排序
直接插入排序 基本思想 对于n个元素的序列分为有序表和无序表每次从后部的无序表中选择第一个元素和有序表中的元素从后向前进入比较若有序表中选择元素比无序表中选择元素大则有序表元素后移直到找到无序表中选择元素要插入的位置哨兵的作用在进行大量数据进行比较时在数据边界放置特别的元素标注避免每次比较是否越界而浪费时间空间复杂度O(1) 时间复杂度O(n2)O(n^2)O(n2) 折半插入排序 基本思想 适合整体有序的顺序表使用折半查找确定插入位置从而统一移动元素时间复杂度仍然为O(n2)O(n^2)O(n2)但是对于数据量不大的排序表往往可以表现出较好的性能 希尔排序缩小增量排序 基本思想 取一个小于n的步长d把表中的全部记录分成d组将待排序表中d的倍数的数据元素放在同一组在组内进行直接插入排序。再取更小的步长进行排序直到所有记录放在同一组中。空间复杂度O(1) 时间复杂度O(n1.3)O(n^{1.3})O(n1.3)但仅适用顺序存储
交换排序
冒泡排序 基本思想按逆序或顺序两两比较相邻的元素按升序或降序进行交换 产生的子序列是全局有序的即每一次排序会产生一个最终结果元素空间复杂度O(1) 时间复杂度O(n2)O(n^2)O(n2) 快速排序 基本思想 选择基准在待排序列中按照某种方式挑出一个元素作为 “基准”pivot分割操作以该基准在序列中的实际位置把序列分成两个子序列。此时在基准左边的元素都比该基准小在基准右边的元素都比基准大递归地对两个序列进行快速排序直到序列为空或者只有一个元素。 特点 不产生有序子序列但每次排序后会将基准元素放到最终位置上每次排序划分子区间越相近越能发挥快排优势 空间复杂度O(log2n)O(log_2n)O(log2n) 时间复杂度O(nlogn)O(nlogn)O(nlogn)
选择排序
简单选择排序 基本思想分成有序区和无序区每次从无序区中找一个最小的放到有序区的最后一个空间复杂度O(1) 时间复杂度O(n2)O(n^2)O(n2) 堆排序 堆分类 大根堆在完全二叉树中所有根均大于左右子树的值小根堆在完全二叉树中所有根均小于左右子树的值 堆的建立 检查所有非终端节点顺序存储前ii≤n/2i \le n/2i≤n/2从最大分支节点第i个开始与其顺序表中左孩子2i和右孩子2i1进行比较交换最大值使该分支节点满足大根堆指针前移指向下一个分支节点重复上述过程时间复杂度为O(n) 堆的插入 先将新节点放在堆末端再对这个新节点执行调整操作与父节点不断比较向上调整到最后位置堆的删除 用堆底部元素进行填充然后该元素进行下坠比较堆的应用 可以用堆实现优先队列 算法性能 空间复杂度O(1)O(1)O(1) 时间复杂度O(nlog2n)O(nlog_2n)O(nlog2n)
特殊排序
归并排序 定义将n个有序表组合在一起形成新的有序表通常n为2称为2路归并算法算法性能 空间复杂度O(n)O(n)O(n) 时间复杂度O(nlog2n)O(nlog_2n)O(nlog2n) 基数排序 不基于比较和移动而是基于关键字各位的大小进行排序算法性能 空间复杂度O(r)O(r)O(r) r表示辅助队列个数时间复杂度O(d(nr))O(d(nr))O(d(nr))共接进行d躺分配和收集一趟分配需要O(n)一趟收集需要O®
内部排序算法比较
直冒简希快堆二基
算法种类最好情况平均情况最坏情况空间复杂度是否稳定直接插入排序O(n)O(n)O(n)O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(1)O(1)O(1)是冒泡排序O(n)O(n)O(n)O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(1)O(1)O(1)是简单选择排序O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(1)O(1)O(1)否希尔排序适合大规模数据O(n1.3)O(n^{1.3})O(n1.3)O(n2)O(n^2)O(n2)O(1)O(1)O(1)否快速排序O(nlog2n)O(nlog_2n)O(nlog2n)O(nlog2n)O(nlog_2n)O(nlog2n)O(n2)O(n^2)O(n2)O(log2n)O(log_2n)O(log2n)否堆排序O(nlog2n)O(nlog_2n)O(nlog2n)O(nlog2n)O(nlog_2n)O(nlog2n)O(nlog2n)O(nlog_2n)O(nlog2n)O(1)否2路归并排序O(nlog2n)O(nlog_2n)O(nlog2n)O(nlog2n)O(nlog_2n)O(nlog2n)O(nlog2n)O(nlog_2n)O(nlog2n)O(n)O(n)O(n)是基数排序O(d(nr))O(d(nr))O(d(nr))O(d(nr))O(d(nr))O(d(nr))O(d(nr))O(d(nr))O(d(nr))O(r)O(r)O(r)是
当n比较小或关键字基本有序的时候使用直接插入排序。当n比较大使用O(nlog2n)O(nlog_2n)O(nlog2n)的排序算法 快速排序排序关键字随机分布时性能表现最好堆排序辅助空间少不会出现最坏情况归并排序排序稳定不交换相等数据元素 数据元素本身信息量比较大可以使用简单选择排序减少数据元素的移动次数。或者使用链表作为存储结构。n很大且关键字位数少可以分解可以采用基数排序 少年我观你骨骼清奇颖悟绝伦必成人中龙凤。 不如点赞·收藏·关注一波 点此跳转到首行↩︎
参考博客
王道考研数据结构
