夜深人静码代码-CSDN博客

原创插入排序超详解释，一看就懂

一、插入排序的相关概念1、基本思想每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。即边插入边排序，保证子序列中随时都是排好序的。就像玩扑克牌抓牌的时候。2、基本操作:有序插入■在有序序列中插入一个元素，保持序列有序，有序长度不断增加。■起初，a[0]是长度为1的子序列。然后，逐一将a[1]至a[n-1 ]插入到有序子序列中。二、插入排序的种类三、直接插入排序1、直接插入排序的过程：顺序查找法查找插入位置

2023-06-16 09:56:34 3244

原创交换排序——冒泡排序和快速排序

一、交换排序的基本思想1、两两比较，如果发生逆序则交换，直到所有记录都排好序为止。2、常见的交换排序方法：冒泡排序和快速排序二、冒泡排序1、冒泡排序基本思想：每趟不断将记录两两比较，并按“前小后大”规则交换。2、冒泡排序总结：■n个记录，总共需要n-1趟■第m趟需要比较n-m次3、算法描述void bubble_sort(SqList &L){ //冒泡排序算法int m,i,j; RedType x;

2023-06-14 14:34:18 670

原创选择排序——堆排序

一、堆排序的相关概念1、堆的定义从堆的定义可以看出，堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于(大于)它的孩子结点。2、堆排序的定义若在输出堆顶的最小值(最大值)后，使得剩余n- 1个元素的序列重又建成一个堆，则得到n个元素的次小值(次大值) ... .如此反复，便能得到一个有序序列，这个过程称之为堆排序。二、堆的调整1、如何在输出堆顶元素后，调整剩余元素为一个新的堆?以小根堆为例：①输出堆顶元素之后，以堆中最后一个元素替代之 ;②然后将根结点值与

2023-06-09 11:06:52 499

原创线索二叉树

一、线索二叉树的相关概念1、由于二叉树链表中空指针域的数量较多：具有n个结点的二叉链表中，一共有2n个指针域;因为n个结点中有n-1个孩子，即2n个指针域中，有n-1个用来指示结点的左右孩子，其余n+1个指针域为空。2、线索二叉树的定义：如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱;如果某结点的右孩子为空，则将空的右孩子指针域改为指向其后继——这种改变指向的指针称为 “线索"。加上了线索的二叉树称为线索二叉树，对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化。3、研究线索二

2022-10-07 20:49:04 806

原创广义表的相关概念及其性质

一、广义表的相关概念1、广义表的定义：广义表(又称列表Lists)是n>=0个元素a0,a1, ... ,an的有限序列，其中每一个ai或者是原子，或者是一个广义表。这种拓宽了的线性表就是广义表。2、广义表通常记作: LS=(a1, a2,...,an)其中: LS为表名，n为表的长度，每一个ai为表的元素。习惯上,一般用大写字母表示广义表，小写字母表示原子。3、表头:若LS非空(n≥1 ),则其第一个元素a1就是表头。记作head(LS) = a1。 ...

2022-09-25 19:54:04 1712

原创虚拟机网络连接方式

通过桥接模式网络连接，虚拟机中的虚拟网络适配器可连接到主机系统中的物理网络适配器，在桥接模式下，虚拟机ip。在默认配置中，虚拟机会在此专用网络中通过DHCP。虚拟机和主机系统共享一个网络标识，此标识在外部网络中不可见。但是桥接模式有个问题就是当你转变办公的地方时（外部网络改变了），虚拟机的IP。模式将虚拟机与外网隔开，使得虚拟机成为一个独立的系统，只与主机相互通讯。地址需要与主机在同一个网段，如果需要联网，则网关与DNS。模式网络时，虚拟机在外部网络中不必具有自己的。模式中，主机网卡直接与虚拟。...

2022-07-19 17:05:03 15134 4

原创二叉树遍历算法的应用

一、二叉树遍历算法的应用——二叉树的创建1、按先序遍历序列建立二叉树的二叉链表例如：已知先序序列为：ABCDEGF，按照二叉树先序方式建立可能会建立出两种不同的二叉树，如下图所示：因此为了避免这种情况，我们可以补充一些空结点，补充空结点过后这两棵树接完全不一样了，因为补充的空结点的位置不一样。可用#号表示空结点。2、对下图所示二叉树按下列顺序读入字符：ABC##DE#G##F### 算法描述：Status CreateBiTree(BiTree &am......

2022-07-19 10:06:52 2520

原创遍历二叉树的非递归算法

一、二叉树中序遍历的非递归算法的关键和思路1、二叉树中序遍历的非递归算法的关键:在中序遍历过某结点的整个左子树后，如何找到该结点的根以及右子树。2、基本思路：基本思路:(1)建立一个栈(2)根结点进栈，遍历左子树(3)根结点出栈，输出根结点，遍历右子树。3、算法描述Status InOrderTraverse (BiTree T){BiTree p;InitStack(S);p=T;while(p || !StackEmpty(S)){if(p) {Push(S,p); p

2022-07-19 10:02:51 631

原创数组和特殊矩阵的压缩存储

一、数组的相关概念1、声明格式：数据类型变量名称[行数] [列数]例:int num[5] [8]在C语言中，一个二维数组类型也可以定义为一维数组类型(其分量类型为一维数组类型)。2、三维数组:若二维数组中的元素又是一个一维数组，则称作三维数组。n维数组:若n-1维数组中的元素又是一个一维数组结构，则称作n维数组。3、结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。4、数组特点:结构固定——定义后，维数和维界不再改变。二、数组的抽象数据类型定义1、

2022-07-17 16:20:49 595

原创串的初步认识

一、串的相关概念1、串的定义：零个或多个任意字符组成的有限序列。2、空串一般用∅表示。3、串相等:当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的。所有空串是相等的。4、......

2022-07-14 14:31:19 247

原创我与CSDN的一年时光及大学经验分享

最后送大家几句我喜欢的座右铭：熬过无人问津的日子，才配拥有诗和远方，生活不是为了“赶路”，而是为了“感路”。种一棵树最好的时间是十年前，其次是现在。人是不能太闲的，闲久了，努力一下就以为是拼命。你远道而来这世间，想必也是因为热爱吧，热爱可抵岁月漫长。......

2022-06-21 18:36:08 2077 8

原创散列表(哈希表）的超详解释，一看就懂

一、散列函数1、散列存储选取某个函数，依该函数按关键字计算元素的存储位置Loc(i)=H(keyi)冲突：不同的关键码映射到同一个散列地址key1≠key2,但是H(key1) = H(key2)在散列查找方法中，冲突是不可能避免的，只能尽可能。二、散列函数的构造方法1、构造要求要求一: n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。要求二:无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。2、常用的方法：直接定址法

2022-05-05 20:30:50 848

原创树表的查找——平衡二叉树

一、平衡二叉树的相关概念1、为了提高形态不均衡的二叉排序树的查找效率，应做“平衡化”处理，将二叉树变成平衡二叉树。2、平衡二叉树的定义平衡二叉树又称AVL树。一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树:①左子树与右子树的高度之差的绝对值小于等于1;②左子树和右子树也是平衡二叉排序树。3、为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子(BF) 。平衡因子=结点左子树的...

2022-05-05 17:25:18 951

原创图的常用遍历——广度优先遍历和深度优先遍历

一、遍历图可能遇到的问题图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。怎样避免重复访问?解决思路:设置辅助数组visited[n]，用来标记每个被访问过的顶点。初始状态visited [i]为0顶点i被访问，改visited [i]为1，防止被多次访问。二、图的常用遍历1、深度优先搜索（DFS）2、广度优先搜索（BFS）三、深度优先遍历（DFS）1、遍历的方法■在访问图中某一起始顶点V后.

2022-05-05 16:37:06 6584

原创遍历二叉树的递归算法

目录一、遍历二叉树的相关概念二、四种遍历二叉树的方式三、遍历二叉树的算法四、遍历算法的分析一、遍历二叉树的相关概念1、遍历定义:顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次(又称周游)。“访问”的含义很广，可以是对结点作各种处理，如:输出结点的信息、修改结点的数据值等，但要求这种访问不破坏原来的数据结构。2、遍历目的:得到树中所有结点的一个线性排列。3、遍历用途:它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树...

2022-05-04 09:35:31 1489

原创二叉树的相关概念以及存储结构

目录一、二叉树的相关概念二、满二叉树三、完全二叉树四、二叉树的顺序存储结构五、二叉树的链式存储结构一、二叉树的相关概念1、二叉树的定义：二叉树是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。2、二叉树的特点：①每个结点最多有俩孩子(二叉树中不存在度大于2的结点)。②子树有左右之分，其次序不能颠倒。③二叉树可以是空集合，根可以有空的左子树或空的右子树。3、二叉树的5种基本形

2022-05-03 09:03:06 676

原创哈夫曼树以及哈夫曼算法

一、哈夫曼树的定义1、哈夫曼树:最优树即带权路径长度(WPL)最短的树“带权路径长度最短”是在"度相同”的树中比较而得的结果，因此有最优二叉树、最优三叉树之称等等。2、哈夫曼树:最优二叉树即带权路径长度(WPL)最短的二叉树因为构造这种树的算法是由哈夫曼教授于1952年提出的，所以被称为哈夫曼树，相应的算法称为哈夫曼算法。二、哈夫曼树的特点1、满二叉树不一定是哈夫曼树2、哈夫曼树中权越大的叶子离根越近3、具有相同带权结点的哈夫曼树不唯一三、哈夫曼算法(构造哈夫曼树的方法)

2022-05-01 19:45:22 5619

原创最小生成树

一、生成树1、生成树:所有顶点均由边连接在一起，但不存在回路的图。如下图所示：2、由上图可知：①一个图可以有许多棵不同的生成树②所有生成树具有以下共同特点：■生成树的顶点个数与图的顶点个数相同;■生成树是图的极小连通子图，去掉一条边则非连通;■一个有n个顶点的连通图的生成树有n-1条边;■在生成树中再加一条边必然形成回路；■生成树中任意两个顶点间的路径是唯一的;二、图的遍历和生成树之间的关系如下图所示：三、最小生成树1、定义：最小生成树:给定

2022-04-30 20:50:10 494

原创哈夫曼编码

一、哈夫曼编码的由来1、在远程通讯中，要将待传字符转换成由二进制的字符串如下图所示:如上图所示若将每个字符都用同样位数的二进制数来表示的话会产生浪费。但如果将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。如下图所示：而哈夫曼编码刚好满足前缀编码的要求，并却能够使电文的总长度最短。二、构造哈夫曼编码的方法1、统计字符集中每个字符在电文中出现的平均概率(概率越大，要求编码越短)。2、利用哈夫曼树的..

2022-04-30 19:42:18 22456

原创串的子串（模式串）匹配算法

一、串的模式匹配算法1、算法目的:确定主串中所含子串(模式串)第一次出现的位置(定位)。2、算法应用:搜索引擎、拼写检查、语言翻译、数据压缩3、算法种类:●BF算法(Brute-Force, 又称古典的、经典的、朴素的、穷举的)●KMP算法(特点:速度快)二、BF算法1、Brute-Froce简称为BF算法，亦称简单匹配算法。采用穷举法的思路。如下图所示：算法的思路是从S的每一个字符开始依次与T的字符进行匹配。2、算法描述int Index BF(SS.

2022-04-30 15:59:59 1947

原创图的存储结构——邻接表（链式存储结构）

一、邻接矩阵表示法的缺点1、不便于增加和删除顶点2、浪费空间：存稀疏图(点很多而边很少)有大量无效元素，对稠密图(特别是完全图)还是很合算的3、浪费时间：统计稀疏图中一共有多少条边...

2022-04-24 20:47:58 3139

原创链队的算法

一、链队的相关概念1、若用户无法估计所用队列的长度，则宜采用链队列。2、链队列的存储方式如下图所示3、链队列的类型定义#define MAXQSIZE 100 //最大队列长度typedef struct Qnode {QElemType data;stuct Qnode *next;}QNode, *QueuePtr;typedef struct {QueuePtr front; //队头指针QueuePtr rea

2022-04-24 09:34:56 793

原创循环队列的算法

一、循环队列的初始化

2022-04-23 13:44:27 1422

原创队列的存储和循环队列

一、队列的存储结构1、队列的物理存储可以用顺序存储结构，也可用链式存储结构。相应队列的存储方式也分为两种，即顺序队列和链式队列。2、顺序队列可以用一维数组表示如下：#define MAXQSIZE 100 //最大队列长度Typedef struct {QElemType *base; //初始化的动态分配存储空间int front; //头指针int rear； //尾指针}SqQueue;二、循环队列的基本操作语句1、队列的初始：front=rear=0;2、

2022-04-22 20:36:14 2440

原创栈和队列的初步认识

一、栈的定义和特点1、定义：栈(stack) 是一个特殊的线性表，是限定仅在一端(通常是表尾)进行插入和删除操作的线性表。又称为后进先出的线性表，简称LIFO结构。2、栈的相关概念：①栈是仅在表尾进行插入、删除操作的线性表②表尾称为栈顶Top，表头称为栈底Base。③插入元素到栈顶(即表尾)的操作，称为入栈。④从栈顶(即表尾)删除最后个元素的操作，称为出栈。3、栈的常见应用：由于栈的操作具有后进先出的固有特性，使得栈成为程序设计中的有用工具。另外，如果问题求解的过程具有"后进先

2022-04-21 10:25:48 279

原创链栈的算法

一、链栈的相关概念1、定义：链栈是运算受限的单链表，只能在链表头部进行操作。2、特点：●链表的头指针就是栈顶●不需要头结点●基本不存在栈满的情况●空栈相当于头指针指向空●插入和删除仅在栈顶处执行●链栈中的指针方向是由栈顶依次指向栈底，如下图所示：二、定义链栈的数据类型typedef struct StackNode{ElemType data;struct StackNode *next;}StackNode ,*LinkStack;...

2022-04-20 20:59:21 499

原创顺序栈的算法

一、顺序栈的存储方式和相关概念1、存储方式：同一般线性表的顺序存储结构完全相同，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，栈底一般在低地址端。2、相关概念①附设top指针，指向栈顶元素在顺序栈中的位置。为了方便操作，通常top指示真正的栈顶元素之上的下标地址。②另设base指针，指向栈底元素在顺序栈中的位置。③另外，用stacksize表示栈可使用的最大容量。结构图如下图所示：3、空栈和栈满的条件①空栈：base==top是栈空标志。②栈满：top-

2022-04-19 19:26:27 1829

原创顺序表的算法

一、顺序表的初始化1、顺序表的初始化操作就是构造一个空的顺序表。初始化也就是为顺序表分配地址空间。2、算法步骤：①为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段地址空间的基地址。②将表的当前长度设为0。3、算法描述Status InitList(SqList &L){//构造一个空的顺序表LL.elem=new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间if(！L.elem) exit(OVERFLOW)

2022-04-18 19:47:03 3725

原创递归的详细解释

一、递归的定义1、若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的。2、若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。二、使用递归必备的条件1、递归问题——用分治法求解分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解。2、必备的三个条件①能将一一个问题转变成一个新问题,而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的。②可以通过上述的分治法而使问题简化。④必须

2022-04-11 20:32:41 681

原创树的初步认识

一、树的定义1、树(Tree)是n (n≥0)个结点的有限集。①若n= 0,称为空树;②若n> 0,则它满足如下两个条件:(1)有且仅有一个特定的称为根(Root)的结点;(2)其余结点可分为m (m≥0)个互不相交的有限集T1, T2, T3,...,Tm,其中每一个集合本身又是一棵树，并称为根的子树(SubTree)。二、树的基本术语1、相关术语如下图所示：2、森林:是m(m≥0)棵互不相交的树的集合。把根结点删除树就变成了森林。一棵树可以看成是一个

2022-04-10 14:49:12 750

原创线性表的三个常见应用

一、线性表的合并假设利用两个线性表La和Lb分别表示两个集合A和B，现要求一个新的集合A=A∪BLa=(7.5, 3,11) Lb=(2.6.3) La=(7,5, 3,11,2, 6)依次取出Lb中的每个元素，执行以下操作:在La中查找该元素2.如果找不到，则将其插入La的最后...

2022-04-06 21:05:00 1162

原创特殊的链表——双向链表

一、双向链表的概述1、双向链表的定义：在单链表的每个结点里再增加一个指向其直接前驱的指针域prior，这样链表中就形成了有两个方向不同的链，故称为双向链表。2、优点：双向链表可以克服单链表查找链表中某结点不方便的缺点。3、双向循环链表：和单链的循环表类似，双向链表也可以有循环表。让头结点的前驱指针指向链表的最后一个结点，让最后一个结点的后继指针指向头结点。二、双向链表的特点与算法操作1、双向链表结构的对称性：设指针P指向某一结点，侧有：p->next->prior=p=p

2022-04-05 09:21:13 4020

原创特殊的链表——循环链表

一、循环链表的概述1、循环链表( Circular LinkedList)是另一种形式的链式存储结构。其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。2、由此，从表中任一结点出发均可找到表中其他结点。3、优点：从表中任意结点出发均可找到表中其他结点。二、循环链表与单链表的区别1、循环链表的操作和单链表基本一致。2、差别仅在于：当遍历链表时，判别当前指针P是否指向表尾结点的终止条件不同。3、由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像单链

2022-04-04 10:53:44 2120

原创单链表的常用算法

一、判断链表是否为空1、空表：链表中无元素，称为空链表，但头指针和头节点仍然存在。2、算法思路：判断头结点的指针域是否为空。int ListEmpty(LinkList L){ //若L为空表，则返回1，否则返回0if(L->next) //非空return 0;elsereturn 1;}...

2022-03-30 15:23:02 5062

原创线性表的抽象数据类型

一、线性表的抽象数据类型定义ADT List{数据对象：D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}基本操作：InitList(&L)操作结果:构造一个空的线性表L。DestroyList(&L)初始条件:线性表L已经存在。操作结果:销毁线性表L。ClearList(&L)初始条件:线性表L已经存在。操作结果:将线性表L重置为空

2022-03-29 19:28:22 3854 1

原创数据结构与算法的初步认识（包括抽象数据类型）

一、数据结构与算法的由来二、数据结构的逻辑结构1、逻辑结构：描述数据元素之间的逻辑关系，与数据的存储无关，独立于计算机，是从具体问题抽象出来的数学模型。2、逻辑结构分为：集合结构、线状结构、树结构、图结构。①集合结构：数据元素之间除了属于同一集合之外，别无其他关系。②线状结构：数据元素之间存在一对一的关系。只有一个开始和一个终端结点且所有结点最多只有一个直接前趋和一个后继。③树结构：数据元素之间存在一对多的关系。④图结构：数据元素之间存在多对多的关系。3、几种逻辑结构层.

2022-03-28 11:19:54 731

原创 WLAN工作过程——后三阶段

一、第二阶段：WLAN业务配置下发AC向AP发送Configuration Update Request请求消息，AP回应Configuration Update Response消息，AC再将AP的业务配置信息下发给AP,如图16- 19所示。AP上线后，会主动向AC发送Confguration Starus Request报文，该信息中包含了现有AP的配置，为了做AP的现有配置和AC设定配置的匹配检查。当AP的当前配置与AC要求不符合时，AC会通过Confiouration Status

2022-03-23 21:48:43 1223

原创 WLAN工作过程——第一阶段AP上线

一、WLAN工作流程AC+FIT AP组网架构中，是通过AC对AP进行统一的管理，因此所有的配置都是在AC上进行的。WLAN的工作流程分为四个阶段，如图16-16所示:1.AP上线，AP获取IP地址并发现AC,与AC建立连接。2. AC 将WLAN业务配置下发到AP生效。3. STA 搜索到AP发送的SSID并连接，上线接入网络。4.WLAN网络开始转发业务数据。二、第一阶段：AP上线...

2022-03-22 19:59:36 7746

原创 BSS/SSID/BSSID、VAP和ESS

一、BSS（基本服务集）BSS是一个AP覆盖的范围，是无线网络的基本服务单元，通常由一个AP和若干STA组成，BSS 是802.11网络的基本结构，如下图所示。由于无线介质共享性，BSS 中报文收发需携带BSSID (MAC地址)。■终端要发现和找到AP，需要通过AP的一个身份标识，这个身份标识就是BSSID (Basic ServiceSet ldentifier,基本服务集标识符)。BSSID是AP上的数据链路层MAC地址。为了区分BSS，要求每个BSS都有唯一的BSSID，因此使用AP的.

2022-03-21 14:27:57 5455