虚拟存储技术基本思想：利用大容量的外存来扩充内存，产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间，简称虚存。操作系统把程序当前使用的部分保留在内存，而把其他部分保存在磁盘上，并在需要时在内存与磁盘之间动态交换。支持多道程序设计技术。实现虚拟存储器需要以下的硬件支持：系统有容量足够大的内存。系统有一定容量的内存。最主要的是：硬件提供实现虚-实地址映射的机制。工作原理：当进程开始运行时，现将一部分程序转入内存，另一部分暂时留在外存但要执行的指令不在内存时，系统自动选择部分内存空间将其中原有的内容交换到磁盘扇区，并释放这些内存空间供其他进程使用。交换技术是以进程为单位进行的，进程所需内存大于当前西戎内存，那么该进程就不能在系统中运行。虚拟内存一般是以页或段为单位，所以如果一个进程所需内存大于当前系统内存，那么该进程仍然可以在系统中正常运行，因为该进程的一部分可以被还出到外存上。虚拟页式存储管理基本思想在进程开始运行之前，不是装如全部页面。而是转入一个或零个页面，之后根据进程运行的需要，动态转入其他页面，当内存空间已满，而又需要装入新的页面时，则根据某种算法置换出某个页面，易变装入新的页面。在使用虚拟页式存储管理时需要在页表中增加以下表项：页号—页面的编号。有效位—又称驻留位、存在位或中断位，表示该页是在内存还是在外存。页框号—页面在内存中时所对应的内存块号。访问位—又称引用位或 ...继续阅读 (28)

把一个逻辑地址连续的程序分散存放到几个不连续的内存区域中，并且保证程序的正确执行，即可充分利用内存空间，又可减少移动所花费的开销。基本思想该技术已广泛用于微机系统中，支持页式存储管理的硬件部件通常称为“存储管理部件”。存储管理部件首先把内存分为大小相等的许多区把每个区称为“块”，块是进行主存空间分配的物理单位。要求程序中的逻辑地址也进行分页，页的大小与块的大小一致。假定地址用m个二进制表示，其中页内地址部分占用n个二进制位，那么，每一块的长度就是2的n次方，也就是每一页有2的n次方个字节。页号部分占用了m-n位，所以，最大的程序可允许有2的（m-n）次方个页面。逻辑地址从“0”，页内地址也为“0”，当编制到2的n次方-1时，第0页的页内地址的各位均为“1”，即占满了一个页面。下一个地址是2的n次方，这时页号部分就为“1”，而页内地址部分又恢复到了“0”，表示进入了第1页。再继续顺序编址，此时页内地址0~(2のn次方-1)是属于第1页。一组顺序的逻辑地址结构将其自然地分页。存储空间的分配与回收那些块已经分配。那些块尚未进行分配。当前剩余的空闲块数。假设内存的可分配区域被分为256块，则可用字长为32位的8个字作为“位示图”，位于图中的每一位与一个内存块对应，每一一个的值可以是0或1，0表示对应的内存块为空闲，1表示已经占用。找出一些为0位，把这些位置成1，并从空闲块数中减去本次分配的 ...继续阅读 (27)

平衡二叉树介绍平衡二叉树，又称AVL树，实际上就是遵循一下两个特点的二叉树：每一子树中的左子树和右子树的深度都不超过1；二叉树的每一个子树都要求是平衡二叉树。只要是每个子树都满足左子树还有右子树的深度都不超过1即可。平衡因子每一个结点都有各自的平衡因子，表示的就是左子树深度同右子树深度的差。平衡二叉树中的各结点平衡因子取值只可能是：0、1、-1.其中 （a） 的两棵二叉树中由于各个结点的平衡因子数的绝对值都不超过 1，所以 （a） 中两棵二叉树都是平衡二叉树；而 （b） 的两棵二叉树中有结点的平衡因子数的绝对值超过 1，所以都不是平衡二叉树。二叉排序树转化为平衡二叉树为了排除动态查找表中不同的数据排列方式对算法性能的影响，需要考虑在不会破坏二叉排序树本身结构的前提下，将二叉排序树转化为平衡二叉树。例如，使用上一节的算法在对查找表{13，24，37，90，53}构建二叉排序树时，当插入 13 和 24 时，二叉排序树此时还是平衡二叉树：当继续插入 37 时，生成的二叉排序树如图 （a），平衡二叉树的结构被破坏，此时只需要对二叉排序树做“旋转”操作（如图（b）），即整棵树以结点 24 为根结点，二叉排序树的结构没有破坏，同时将该树转化为了平衡二叉树：当二叉排序树的平衡性被打破时，就如同扁担的两头出现了一头重一头轻的现象，如图（a）所示，此时只需要改变扁担的支撑点（树的树根），就能使其重 ...继续阅读 (27)

覆盖技术覆盖技术是指一个程序的若干程序段和几个程序的某些部分共享一个存储空间。覆盖技术的实现是把程序分为若干个功能上相对独立的程序，按照其自身的逻辑结构使那些不会同时执行的程序段共享同一块内存区域。未执行的程序段先保存在磁盘上，当有关程序段的前一部分执行结束后，把后续程序段调入内存，覆盖前面的程序段。覆盖技术是用户程序自己附加的控制。要把一个程序划分成不同的程序段，并规定好他们的执行和覆盖顺序。操作系统则根据程序员提供的覆盖结构，完成程序段之间的覆盖。该程序正文段所需要的内存空间是A（20KB）+B（50KB）+F（30KB）+C（30KB）+D（20KB）+E（40KB）=190KB，但是在采用了覆盖技术后只需要A（20KB）+B（50KB）+E（40KB）=110KB占用空间。覆盖技术主要用于系统程序的内存管理上，MS-DOS系统分为两个部分。操作系统中经常要用到的基本部分，它们常驻在内存且占用固定区域。不太经常使用的部分，它们存放在磁盘上，当调用它们时才被调入内存覆盖区。交换技术交换技术：在分时系统中，用户的进程比内存能容纳的数量要多，这就需要在磁盘上保存那些内存放不下的进程。在需要运行这些进程时，再将它们装入内存。进程从内存移到磁盘并再移动回内存称为交换。交换技术是进程在内存与外存之间的动态调度，是由操作系统控制的。后备存储区（又称盘交换区）。目的：尽可能达到”足够快的交换 ...继续阅读 (22)

基本思想：是把内存划分成若干个连续的区域，称为分区，每个分区装入一个运行程序。固定分区基本思想固定分区是指系统先把内存划分为若干个大小固定的分区，一旦分配好，在系统运行期间便不再重新划分。程序运行时必须提供对内存资源的最大申请量。内存分配表与分区的分配、回收用于固定分区管理的内存分配表是一张分区说明表，按顺序每个分区说明表中对应一个表目。表目内容包括分区序号、分区大小、分区起始地址以及使用状态（空闲或占用）。一个程序在运行时，想要根据其对内存的需求量，按一定的分配策略在分区说明表中查找空闲分区。若找到合乎需要的分区，就将该分区分配给程序，并将该分区置为占用状态。当程序完成时释放这块分区内存，由系统回收，并在分区说明表中间回收的分区重新置为空闲状态。固定分区方案灵活性差，可接纳程序的大小受到了分区大小的严格限制。可变分区基本思想可变分区是指系统不预先划分固定分区，而是在装入程序时划分内存分区，使为程序分配的分区的大小正好等于该程序的需求量，且分区的个数是可变的。可变分区有较大的灵活性，较之固定分区能更好的内存利用率。系统初次启动后，在内存中出操作系统区之外，其余空间为一个完整的大空闲区，当有程序要求装入内存运行时，系统从该空闲区中划分出一块与程序大小相同的区域进行分配。当系统运行一段时间后，随一系列的内存分配与回收，原来的一整块大空闲区形成了若干占用区和空闲区相间的布局，若有上下相邻 ...继续阅读 (28)

进程（线程）间相互作用相关进程与无关进程相关进程：在逻辑上具有某种联系的进程。无关进程：在逻辑上没有任何联系的进程。如果一个进程的执行不影响其他进程的执行，且与其他进程的进展情况无关，即它们是各自独立的，则说这些并发进程的相互之间是无关的。无关的并发进程一定没有共享的变量。如果一个进程的执行依赖其他进程的进展情况，或者说，一个进程的执行可能影响其他进程的执行结果，则说这些并发进程是相关的。与时间有关的错误京城执行的速度是不能由进程自身控制的。对于相关进程来说，可能有若干并发进程同时使用共享资源，即一个进程一次使用未结束，另一个进程也开始使用，形成交替使用共享资源。进程同步：值多个进程中发生的事件存在某种时序关系，必须协同动作，相互配合，以共同完成一个任务。进程互斥：指由于共享资源所要求的排他性，进程间要相互竞争以使用这些互斥资源。进程互斥解决进程互斥的两种方法：由竞争各方平等协商。引入进程管理者，有管理者来协调竞争各方对互斥资源的使用。临界资源：计算机系统中的需要互斥使用的硬件或软件资源，如外设、共享代码块、共享数据结构等。对各进程在对临界资源进程进行访问时，特别是进行写入或修改操作时，必须互斥的运行。计算机系统中资源共享的程度分为三个层次：互斥、死锁和饥饿。互斥：保证资源的互斥使用是指多个进程不能同时使用同一个资源，这是正确使用资源的最基本要求。死锁：避免死锁是指多个进程互不相让 ...继续阅读 (31)

计算机系统中的存储器可以分为两类：内存储器（简称内存）和外存储器（简称外存）。处理器可以直接访问内存，但不能直接访问内存。CPU要通过启动相应的输入/输出设备后才能使内存和外存交换信息。内存管理是操作系统中重要功能之一。基本概念存储体系存储设备的速度仍然明显慢于同一级别的中央处理器的速度。任何一种存储设备都无法在速度与容量两个方面同时满足用户的需求。少量的、非常快速、昂贵、内存易变的高速缓冲器Cache，通常是有KB的数量级。若干兆字节、中等速度、中等价格、内容易变的内存RAM，通常是千MB的数量级。低速、廉价、内容不一边的外存（磁盘），通常是百至千GB的数量级。存储管理的任务任何程序和数据以及各种控制用的数据结构都必须占用一定的存储空间，因此，存储空间直接影响系统性能。内存空间：由存储单元（子节或字）组成的一维连续的地址空间，内存空间用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的亦即程序计数器所指的存储空间。系统区：用以存放操作系统常驻内存的部分，用户不能占用这部分空间。用户区：分配给用户使用，用于装入并存放用户程序和数据，信息随时都会发生变化，存储管理的实质就是管理供用户使用的那部分空间。内存管理问题的主要包括：内存管理方法、内存的分配和释放算法、虚拟存储器的管理、控制内存和外存之间的数据流动方法、地址交换技术和内存数据保护与共享技术等。单道、单用户：在一个区 ...继续阅读 (19)

线程模型线程：能够独立运行的基本单位，试图用它来提高系统内程序并发执行的程度。线程的引入基本属性：进程是一个可拥有资源的独立单位，又是一个可以独立调度和分派的基本单位。创建进程：必须为其分配所有资源（除CPU外），包括内存空间、I/O设备以及建立相应的数据结构PCB。撤销进程：必须先对这些资源进行回收操作，然后在撤销PCB。进程切换：由于要保留当前进程的CPU环境和设置新选中进程的CPU环境，为此需要花费不少的CPU时间。进程是一个资源拥有者，因而在进程的创建、撤销和切换中，系统必须为之付出较大的时空开销。创建背景：如果将作为调度和分派的经本单位不同时作为独立分配资源的单位，以使轻快运行；而对拥有资源的基本单位，又不频繁地对之进行切换。线程的基本概念线程是进程中的一个实体，是CPU调度和分派的基本单位。一个线程可以创建和撤销另一个线程；同一个进程中的多个线程之间可以并发执行。线程也同样有就绪、等待和运行三种基本状态。线程的属性每一个线程有一个唯一的标识符和一张线程描述表，记录了线程执行的寄存器和栈等现场状态。不同的线程可以执行相同的程序，同一个服务程序被不同用户调用时操作系统为它创建不同的线程。同一个进程中的各个线程共享进程的内存地址空间。线程是处理器的独立调度单位，多个线程是可以并发执行的，在单个CPU的计算机系统中，各个线程可交替的占用CPU；在多个CPU计算机系统中，各个线程 ...继续阅读 (11)

调度是分层次的，在操作系统中，一般将调度分为高级调度、中级调度和低级调度。 高级调度也称作业调度，其主要任务是按一定的原则，对磁盘中的处于后备状态的作业进行选择并创建为进程。 中级调度的主要任务是按照给定的原则和策略，将处在磁盘对换区中切具备运行条件的就绪进程调入内存，或将处于内存就绪状态或内存阻塞状态的进程交换到对换区。低级调度即进程（线程）调度，是决定就绪队列中哪个进程将获得处理机，并使即将处理及分配给该进程的操作。进程（线程）调度即处理机调度。任务是控制、协调进程（线程）对CPU的竞争，按照一定的调度算法，使某一就绪进程获得CPU的控制权，转换成运行状态。概述进程（线程）调度的主要功能记录系统中所有进程（线程）的执行状况，根据一定的调度算法，从就绪队列中选出一个进程（线程）来，准备把CPU分配给它，把CPU分配给进程（线程），即把选中进程（线程）的进程（线程）控制块内有关的现场信息，让它占用CPU运行。进程（线程）调度的时机正在执行的进程（线程）运行完毕。调用阻塞原语将自己阻塞起来进入等待状态。调用阻塞原语操作，并且因为资源不足而被阻塞；或调用唤醒原语操作激活了等待资源的进程（线程）。时间片用完。就绪队列中的某个就绪队列中一旦有优先级高于当前运行进程（线程）优先级时，引发进程（线程）调度。抢占方式：就绪队列中一旦由优先级高于当前运行进程（线程）优先级的进程（线程）存在时，便立 ...继续阅读 (18)

进程控制块PCB在操作系统中，为进程定义了一个专门的数据结构，称为进程控制块PCB。PCB内容PCB内容可以分为调度信息和现场信息两大部分。调度信息供进程使用时使用，描述了进程当前所处的状况，他包括进程名、存储信息、进程号、优先级、当前状态、资源清单、“家族”关系、消息队列指针、进程队列指针和当前打开的文件等。现场信息刻画了进程的运行情况，由于每个进程都有自己专用的工作存储区，其他进程运行时不会改变它的内容。进程的组成PCB组织线性方式：将所有的PCB部分状态组织在一个连续表（称为PCB表）中。优点：简单，且不需要额外的开销，适用于进程数且不多的系统。缺点：需要扫描整个PCB表。索引方式：对于具有相同状态的进程，分别设置各自的PCB索引表，表目为PCB在PCB表（线性表）中的地址。就构成了就绪索引表和等待索引表。链接方式：对于具有相同状态的进程PCB，通过PCB中的链接字构成一个队列。按“先进先出”的原则出对，若队列指针为0，表示该队列为空。进程的队列就绪队列：进程入队和出队的次序与处理机调度算法有关。等待队列：每一个等待事件一个队列。运行队列：在单CPU系统中整个系统有一个运行队列。进程控制作用：就是对进程在这个生命周期中各种状态之间的转换进行有效的控制。原语：通常由若干的指令组成，用来实现某个指定的操作。通过一段不可分割的或不可中断的程序实现其功能。原语的执行过程必须是连续的， ...继续阅读 (18)

缓存浏览器的一次请求需要从服务器获得许多css、img、js等相关的文件，如果每次请求都把相关资源文件加载一次，对带宽、服务器资源、用户等待时间都有严重的损耗，浏览器有做优化处理，就是把css、img、js等文件在第一次请求成功后就在本地保留一个缓存备份，后续的每次请辞u就在本身获得相关的缓存资源文件就可以了，可以明显地加快用户的访问速度。css、img、js等文件可以缓存，但是动态程序文件例如PHP文件不能进行缓存，即使缓存我们也不要其缓存效果。浏览器对动态程序文件缓存的处理解决：给请求的地址设置随机数【推荐】；给动态程序设置header头信息，禁止浏览器对其缓存。给请求的地址设置随机数12345678910111213141516171819DOCTYPE htmlAjax对缓存的处理functionf1(){varxhr=newXMLHttpRequest();xhr.open('get','./server.php?'+Math.random());xhr.send(null);}Ajax对缓存的处理给动态程序设置header头信息123456//设置header头禁止浏览器缓存当前页面header("Cache-Control:no-cache");header("Pragma:no-cache");header("Expires:-1");$fp=fopen("test ...继续阅读 (22)

计算机网络技术的形成与发展主要知识点记录“三网融合” ：计算机网络、电信网与电视网之间的融合。UNIX操作系统集中式、分时、多用户的系统架构制订了基于Unix的易移植操作系统环境（POSIX）标准Linux操作系统常见的发行版本：Rad Hat、Mandrake、Slackware、SUSE、TurbpLinux、Debian、Caldera、Ubuntu，国内的有蓝点、红旗等。计算机网络的基本概念计算机网络的定义计算机网络用相互共享资源的方式互联起来的自治计算机系统的集合。特征：主要目的是资源的共享互联的计算机是分布在不同地理位置的多台独立的“自治计算机”联网计算机之间的通讯需要遵循共同的网络协议。常见计算机名词区分：术语英文名称含义计算机网络computer network用相互共享资源的方式互联起来的自治计算机系统的集合网络互联internet将多个计算机网络互联成大型网络系统的技术互联网Internet指目前广泛应用、覆盖了全世界的大型网络系统内部的专用网络系统Intranet将分布在不同地理位置的部门局域网连接起来的企业内部专用网络。计算机网络的分类按照覆盖的地理范围划分为：广域网、城域网、局域网、个人区域网。广域网技术WAN又称为远程网，覆盖的地理位置从几十千米到几千千米。城域网技术IEEE802协会对其的定义与特征表述：以光纤为传输介质，能够提供45-150Mbps的 ...继续阅读 (26)

树树的定义专业定义：有且只有一个根的节点有若干的互不相交的子树，这些子树本身也是一棵树通俗的定义：树是由节点和边组成每个节点只有一个父节点，但可以有多个子结点但有一个节点例外，该节点没有父节点，此节点为根节点。专业术语：节点 父节点 子节点 子孙 祖先 堂兄弟深度：从根节点到最底层节点的层数。（根节点是第一层）叶子节点：没有子节点的节点非终端节点：实际就是非叶子节点度:子结点的个数树的分类一般树任意一个节点的子节点的个数都不受限制二叉树任意一个节点的子节点的个数最多为两个，且子节点的位置不可变更分类：一般二叉树满二叉树 在不增加树的层数的前提下，无法再多添加一个节点的二叉树。完全二叉树 如果只是删除了满二叉树最底层最右边的连续若干个节点。森林n 个互不相交的树的集合树的存储二叉树的存储连续存储[完全二叉树]优点： 查找某个节点的父节点和子结点速度(也包括有没有子结点)很快.缺点： 耗用的内存空间比较大.链式存储一般树的存储双亲表示法求父节点方便。孩子表示法求子节点方便。双亲孩子表示法求父节点和子结点都很方便。二叉树表示法把一个普通的树转换成二叉树来存储。具体转换方法:设法保证任意一个节点的左指针指向它的第一个孩子，右指针指向它的堂兄弟。只要能满足此条件，就可以把一个普通的树转换成为二叉树。一个普通树转换成的二叉树一定没有右子树。森林的存储先把森林转化成二叉树，再存储二叉树树的操作遍 ...继续阅读 (27)

算法思想在使用查找表中有n个关键字，表中的每个关键字被查找的概率都是1/n。在等概率的情况下，使用折半查找算法最优。然而在某些情况下，查找表中的个关键字被查找的概率都是不同的。例如在UI设计师设计图片的时候，不同的设计师和不同的项目经理需求不同，有些项目经理喜欢暖色调，那么暖色调就会应用的多一些，有的项目经理比较喜欢冷色调，之后你的设计采用冷色调的概率也是比较大的。在查找表中的关键字不同的情况下，对应于折半查找算法，按照上面的情况并不是最优的查找算法。静态最优查找二叉树 若在考虑查找成功的情况下，描述查找过程的判定树其带权路径之和（用PH表示）最小时，查找性能最优。算法思想例子在查找表中各关键字查找概率不相同的情况下，对于使用折半查找算法，按照之前的方式进行，其查找的效率并不一定是最优的。例如，某查找表中有 5 个关键字，各关键字被查找到的概率分别为：0.1，0.2，0.1，0.4，0.2（全部关键字被查找概率和为 1 ），则根据之前介绍的折半查找算法，建立相应的判定树为（树中各关键字用概率表示）：折半查找查找成功的平均查找长度计算方式：ASL = 判定树中的各节点的查找概率 * 所在层次相对的平均查找长度为：ASL=0.41 + 0.22 + 0.22 + 0.13 + 0.1*3=1.8带权路径之和的计算公式：PH = 所有结点所在的层次数 * 每个结点对应的概率值。但是由于构 ...继续阅读 (23)

定义键树查找法又称数字查找树（根节点子树>=2个），键树节点存储的不是某个关键字，而是组成关键字的单个符号。如果关键字本身是字符串，则键树中的一个结点只包含有一个字符；如果关键字本身是数字，则键树中的一个结点只包含一个数位。每个关键字都是从键树的根结点到叶子结点中经过的所有结点中存储的组合。例如，当使用键树表示查找表1{CAI，CAO，CHEN，LI，LAN，ZHAO}时，为了查找方便，首先对该查找表中关键字按照首字符进行分类（相同的在一起）：1{{CAI,CAO,CHEN},{LI,LAN},{ZHAO}}然后继续分割，按照第二个字符、第三个字符、…，最终得到的查找表为：1{{CAI,CAO},{CHEN},{LI,LAN},{ZHAO}}然后使用键树结构表示该查找表，如下图所示：注意 ：键树中叶子结点的特殊符号 $ 为结束符，表示字符串的结束。使用键树表示查找表时，为了方便后期的查找和插入操作，约定键树是有序树（兄弟结点之间自左至右有序），同时约定结束符 ‘$’ 小于任何字符。键树的存储结构键树的存储结构有两种，分别是：双链树 ：通过使用树的孩子兄弟表示法来表示键树。字典树 ：以树的多重链表表示键树。双链树当使用孩子兄弟表示法表示键树时，树的节点构成以下3部分：symobl域：存储关键字的一个字符。first域：存储指向孩子节点的指针。next域：存储指向兄弟节点的指针。注意： ...继续阅读 (24)

与哈夫曼树相关名词路径：在一棵树中，一个节点到另一个节点之间的通路。路径长度：在一条路径中，每经过一个节点，路径都要加1.节点的权：给每一个节点赋予一个新的数值。节点的带全路径长度：从根节点到该节点之间的路径长度与该节点的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。此树的带全路径长度为：WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3哈夫曼树当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。遵循一个原则，那就是：权重越大的结点离树根越近。构建哈夫曼树对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。（A）给定了四个结点a，b，c，d，权值分别为7，5，2，4；第一步如（B）所示，找出现有权值中最小的两个，2 和 4 ，相应的结点 c 和 d 构建一个新的二叉树，树根的权值为 2 + 4 = 6，同时将 ...继续阅读 (21)

算法定义分块查找，也叫索引顺序查找，算法实现除了需要查找表本身之外，还需要根据查找表建立一个索引表。建立的索引表要求按照关键字进行升序排序，查找表要么整体有序，要么分块有序。分块有序：指的是第二个子表中所有关键字都要大于第一个子表中的最大关键字，第三个子表的所有关键字都要大于第二个子表中的最大关键字，依次类推。块（子表）中各关键字的具体顺序，根据各自可能会被查找到的概率而定。如果各关键字被查找到的概率是相等的，那么可以随机存放；否则可按照被查找概率进行降序排序，以提高算法运行效率。算法原理所有前期准备工作完成后，开始在此基础上进行分块查找。分块查找的过程分为两步进行：确定要查找的关键字可能存在的具体块（子表）；在具体的块中进行顺序查找。方法描述将n个数据元素”按块有序”划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须”按块有序”；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……。算法实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include#includestructindex{//定义块的结构intkey;intstart;}newI ...继续阅读 (26)

插入排序算法介绍插入排序算法是所有排序方法中最简单的一种算法，其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中，最终得到的序列就是已经排序好的数据。直接插入排序是插入排序算法中的一种，采用的方法是：在添加新的记录时，使用顺序查找的方式找到其要插入的位置，然后将新记录插入。例如采用直接插入排序算法将无序表1{3,1,7,5,2,4,9,6}进行升序排序的过程为：首先考虑记录 3 ，由于插入排序刚开始，有序表中没有任何记录，所以 3 可以直接添加到有序表中；向有序表中插入记录 1 时，同有序表中记录 3 进行比较，1<3，所以插入到记录 3 的左侧；向有序表插入记录 7 时，同有序表中记录 3 进行比较，3<7，所以插入到记录 3 的右侧；向有序表中插入记录 5 时，同有序表中记录 7 进行比较，5<7，同时 5>3，所以插入到 3 和 7 中间；向有序表插入记录 2 时，同有序表中记录 7进行比较，2<7，再同 5，3，1分别进行比较，最终确定 2 位于 1 和 3 中间；照此规律，依次将无序表中的记录 4，9 和 6插入到有序表中。代码实现1234567891011121314151617181920212223242526272829303132#include//自定义的输出函数voidprint(inta[],intn,inti){printf("%d:",i ...继续阅读 (25)

定义二叉排序树要么是空二叉树，要么具有如下特点：二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；二叉排序树的左右子树也要求都是二叉排序树；例如，下图就是一个二叉排序树：二叉排序树关键字的操作使用二叉排序树查找关键字二叉排序树中查找某关键字时，查找过程类似于次优二叉树，在二叉排序树不为空树的前提下，首先将被查找值同树的根结点进行比较，会有 3 种不同的结果：如果相等，查找成功；如果比较结果为根结点的关键字值较大，则说明该关键字可能存在其左子树中；如果比较结果为根结点的关键字值较小，则说明该关键字可能存在其右子树中；实现函数为：（运用递归的方法）123456789101112BiTreeSearchBST(BiTreeT,KeyTypekey){//如果递归过程中 T 为空，则查找结果，返回NULL；或者查找成功，返回指向该关键字的指针if(!T||key==T->data){returnT;}elseif(keydata){//递归遍历其左孩子returnSearchBST(T->lchild,key);}else{//递归遍历其右孩子returnSearchBST(T->rchild,key);}}二叉排序树本身是动态查找表的一种表示形式，有时会在查找过程中插入或者删除表中元 ...继续阅读 (25)

B+树定义一颗 m 阶的 B+树和 m 阶的 B-树的差异在于：有 n 棵子树的结点中含有 n 个关键字；在上一节中，在 B-树中的每个结点关键字个数 n 的取值范围为⌈m/2⌉ -1≤n≤m-1，而在 B+树中每个结点中关键字个数 n 的取值范围为：⌈m/2⌉≤n≤m。所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。所有的非终端结点（非叶子结点）可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。例如，下图中所示的就是一棵深度为 4 的 3 阶 B+树：如上图所示，B+树中含有两个头指针，一个指向整棵树的根结点，另一个指向关键字最小的叶子结点。同时所有的叶子结点依据其关键字的大小自小而大顺序链接，所有的叶子结点构成了一个 sqt 指针为头指针的链表。所有，B+树可以进行两种查找运算：一种是利用 sqt 链表做顺序查找，另一种是从树的根结点开始，进行类似于二分查找的查找方式。在 B+树中，所有非终端结点都相当于是终端结点的索引，而所有的关键字都存放在终端结点中，所有在从根结点出发做查找操作时，如果非终端结点上的关键字恰好等于给定值，此时并不算查找完成，而是要继续向下直到叶子结点。B+树的查找操作，无论查找成功与否，每次查找操作都是走了一条从根结点到叶子结点的路径。B+树中插入关键字在B+树中插 ...继续阅读 (29)

B-树定义B-树，有时又写为B_树（其中的“-”或者“-_只是连字符，并不读作“B减树”），一颗 m 阶的 B-树，或者本身是空树，否则必须满足以下特性：树中每个结点至多有 m 棵子树;若根结点不是叶子结点，则至少有两棵子树；除根之外的所有非终端结点至少有棵子树；所有的非终端结点中包含下列信息数据：（n，A0，K1，A1，K2，A2，…，Kn，An）；n 表示结点中包含的关键字的个数，取值范围是：⌈m/2⌉-1≤ n ≤m-1。Ki （i 从 1 到 n）为关键字，且 Ki < Ki+1 ；Ai 代表指向子树根结点的指针，且指针 Ai-1 所指的子树中所有结点的关键字都小于 Ki，An 所指子树中所有的结点的关键字都大于 Kn。如图所示，当前结点中有 4 个关键字，之间的关系为：K1< 47 ，所以如果 47 存在于这棵树中，肯定位于 A1 指针指向的右子树中；然后顺着指针找到存有关键字 43 和 78 的结点，由于 43 < 47 < 78，所以如果 47 存在，肯定位于 A1 所指的子树中；然后找到存有 47、53 和 64 三个关键字的结点，最终找到 47 ，查找操作结束；以上图中的 B-树为例，若查找到深度为 3 的结点还没结束，则会进入叶子结点，但是由于叶子结点本身不存储任何信息，全部为 NULL，所以查找失败。B-树插入关键字B-树也是从空树开始，通过不断地插入新的数据 ...继续阅读 (26)

中央处理器CPU单机系统：一个计算机系统只有一个处理器。多处理器系统：一个计算机系统有多个处理器。CPU的构成与基本工作方式处理器一般由运算器、控制器、寄存器以及高速缓存构成。运算器实现任何指令中的算术和逻辑运算，是计算机的核心;控制器负责控制程序运行的流程，包括取指令、维护CPU状态、CPU与内存的交互等;寄存器是指令在CPU内部做处理的过程中能够张村数据、地址以及指令信息的存储设备;高速缓存处于CPU和物理内存之间，一般由控制器中的内存管理单元MMU管理;处理器中的寄存器用户可见存储器：对于高级语言来说，编译器通过一定的算法分配并使用这些寄存器，以最大限度地减少程序运行过程中的访问存储器的次数，这对程序运行速度的影响很大。 控制和状态存储器：用于控制处理器的操作。数据寄存器：又称为通用寄存器，主要用于各种算术逻辑指令和访存指令，对具有浮点能力和多媒体能力处理能力的处理器来说，浮点处理过程的数据寄存器和整数处理时的数据寄存器一般是分离的。地址寄存器：用于存储数据及指令的物理地址、线性地址、有效地址。条形码寄存器：保存CPU操作结果的各种标记位。作用：控制处理器的操作。控制和状态寄存器包括了程序计数器、指令寄存器和程序状态字。程序计数器（PC）：记录了将要取出的指令的地址。指令寄存器（IR）：包含了最近取出的指令。程序状态字（PSW）：记录了处理器的运行模式信息。指令执行的基本过程 ...继续阅读 (29)

算法原理先确定待查记录所在的范围（区间），然后逐步缩小范围指导找到或找不到该记录为止。算法性能时间复杂度： log 2 n + 1 平均查找长度： log 2 n + 1 – 1注意事项折半查找法必须为有序数列。可以是逆序的，但是必须得提前定义遍历对比对象。算法实现12345678910111213141516171819202122232425262728293031323334353637383940414243include"stdio.h"//折半查找函数intbinarySearch(inta[],intn,intkey){//定义数组的第一个数intlow=0;//定义数组的最后一个数inthigh=n-1;//定义中间的数值intmid;//存放中间的数值的变量intmidVal;//当左边的值小于等于右边的值的时候while(low<=high){mid=(low+high)/2;midVal=a[mid];//如果中间值小于用户查找到的数值，最低的数字到中间数值+1位置上if(midValkey){//如果中间值大于用户查找到的数值，最高的数字到中间数值-1位置上high=mid-1;}elsereturnmid;}return-1;}intmain(){inti,val,ret;inta[10]={1,2,3,4,5,6,7,8,9,10};//打印数组for( ...继续阅读 (20)

操作系统的概念计算机系统计算机系统包括硬件子系统及软件子系统。 各种程序和数据组成了计算机的软件系统。 操作系统：在计算机系统中，集中了资源管理功能和控制程序执行功能的一种软件。操作系统的定义“有效”是指根据用户的不同的要求，在管理计算机资源时考虑到系统运行的效率及资源的利用率。“合理”是指操作系统要“公平对待”不同的用户程序，保证系统不发生“死锁”及“饥饿”现象。操作系统的特征并发性 是指在计算机系统中同时存在若干个运行的程序。计算机的并发行体现在下面两个方面：用户程序与用户程序之间并发执行用户程序与操作系统之间并发执行共享性随机性研究操作系统的观点软件的观点 操作系统就是一种大型的软件系统，它是多种功能程序的集合。外在特性操作系统是一种软件，它的外部表现形式，即它的操作命令定义集和它的界面，完全确定了炒作系统这个软件的使用方式。内在特性 操作系统既然是臃肿软件，他就具有一般软件的结构特点。资源管理的观点操作系统就是负责记录谁在使用什么样的资源。 操作系统要提供一些机制去协调程序间的竞争与同步，提供机制对资源进行合理使用，对其保护，一机采取虚拟技术来“扩充”资源等。进程的观点 操作系统就死看作是由多个可以独立运行的程序和一个对这些程序进行协调的核心所组成的。虚拟机的观点服务提供者的观点操作系统的功能进程管理 对中央处理器进行管理。 进程管理分为一下几个方面：进程控制进程控制的主要 ...继续阅读 (19)

安装 Sublime text3 软件官方网址：https://www.sublimetext.com/3选择Windows - also available as a portable version一项，点击下载安装。安装 packagecontrol 插件官方网址：https://packagecontrol.io/选择 Installation 项选择 SUBLIME TEXT3 代码进行复制打开 sublime text3 软件，选择View->Show Console选项（或者按Ctrl+~组合键），调出命令行，将代码粘贴至命令行，回车，进行安装 packagecontrol 插件；安装好之后在菜单栏Preferences栏目中会有packagecontrol选项，即安装成功。安装汉化插件 ChineseLocalization安装 sublime 汉化插件 ChineseLocalization在弹出的框中，由于网速原因，请耐心等待…… 输入插件名称ChineseLocalization，回车[enter]进行安装各类插件安装推荐其他插件均和 ChineseLocalization 插件安装过程一样，在此不再重复操作，只推荐几款插件。必备的插件安装 (初学者推荐安装)EmmetEmmet 的前身是大名鼎鼎的 Zen coding，如果你从事Web前端开发的话，对该插件 ...继续阅读 (25)

我的阅读清单2023状态书籍类别笔记推荐指数⏳《富爸爸穷爸爸》理财🌟🌟🌟🌟🌟2022状态书籍类别笔记推荐指数✅《Effective Go 中英双语版》技术🌟🌟🌟🌟✅《一往无前》公司🌟🌟🌟🌟🌟✅《黄金时代》小说🌟🌟🌟🌟✅《乖，摸摸头》散文🌟🌟🌟🌟🌟✅《图解 HTTP》技术🌟🌟🌟🌟✅《分布式缓存：原理、架构及Go语言实现》技术🌟🌟🌟🌟✅《深入理解Java虚拟机JVM高级特性与最佳实践》技术🌟🌟🌟🌟🌟✅《深入设计模式》技术🌟🌟🌟🌟⏳《保重》散文🌟🌟🌟🌟🌟2021状态书籍类别笔记推荐指数✅《MySQL 实战 45 讲》技术🌟🌟🌟🌟🌟✅《Redis 设计与实现》技术🌟🌟🌟🌟🌟 ...继续阅读 (20)

申请友链评论区留言申请～1234-title:Debug客栈image:https://cdn.jsdelivr.net/gh/debuginn/image@main/img/202302182238057.JPGwebsite:https://debuginn.comdescription:做一个爱分享的程序猿友情提示如果您想交换链接，请按上述格式留言。(仅限个人非商业性博客网站)；网站出现故障、停止维护和不当内容可能会被取消链接！那些不尊重他人劳动成果、无源转载、恶意行为的网站，请不要前来交流。 ...继续阅读 (46)