IM电竞计算机软件基础知识doc

　　计算机软件基础知识1.1数据结构与算法借助于计算机解决问题，首先需要了解所处理对象的性质和特点即所操作对象的数据结构，然后再设计解决问题的方法和步骤即设计一个合理的算法，即通常所说的“程序=数据结构+算法”。1.1.1算法的基本概念“算法”（Algorithm）一词最早来自公元9世纪波斯数学家比阿勒霍瓦里松的一本影响深远的著作《代数对线世纪的英国数学家图灵提出了著名的图灵IM电竞网站论点，并抽象出了一台机器，这台机器被我们称之为图灵机。图灵的思想对算法的发展起到了重要的作用。一般来说，算法是指完成一个任务或解决一个问题所需要的具体步骤和方法的描述。在这里我们说的算法是指计算机能执行的算法。1.算法分类计算机算法可分为两大类，一类是数值运算算法，另一类是非数值运算算法。数值运算算法主要是求数值解，如求方程的解、求函数的定积分等，非数值运算的范围则非常广泛，如人事管理、图书检索等。2.算法特征一个科学的算法必须具备以下特征：(1)有穷性：一个算法必须保证执行有限步之后结束，而不能是无限的。这是显而易见的。更进一步说，有穷性是指在合理的范围内结束运算，如果一个算法需计算机执行几百年或更长时间才结束，这显然是不合理的。(2)确定性：算法的每一步骤必须有确切的定义而不能模棱两可，算法中不能出现诸如“一个比较大的数”等模糊描述。(3)有零个或多个输入(4)有一个或多个输出。算法的目的是为了解决问题,一个没有输出的算法是不能解决任何问题因而它是没有意义的.(5)有效性。算法中的每一个步骤都都应当能有效地执行，并得到确定的结果。例如，若n=0则执行m/n是无法有效执行的。3.算法表示一个计算机算法可以用自然语言、流程图、N-S图等来表示。4.算法分析算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论各种复杂度，以探讨某种具体算法适用于哪类问题，或某类问题宜采用哪种算法。算法的复杂度分时间复杂度和空间复杂度。．时间复杂度：在运行算法时所耗费的时间为f(n)(即n的函数)。．空间复杂度：实现算法所占用的空间为g(n)（也为n的函数）。称O(f(n))和O(g(n))为该算法的复杂度。1.1.2数据结构的定义数据结构是计算机科学与技术领域上广泛被使用的术语。尽管它至今还未有一个被一致公认的定义，但其内容是大家一致公认的。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。一般数据结构可采用下面两类主要的存储方式，大多数数据结构的存储表示都采用其中的一类方式，或两类方式的结合。1.顺序存储结构这种存储方式的主要用于线性数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元内，结点之间的关系由存储单元的邻接关系来实现。顺序存储结构的主要特点是：（1）结点中只有自身信息域，没有连接信息域，因此存储密度大，存储空间利用率高；（2）可以通过计算直接确定数据结构中第i个结点的存储地址Li，计算公式为Li=L0+(i-1)*m，其中L0为第一个结点的存储地址，m为每个结点所占用的存储单元个数；（3）插入、删除运算不便，会引起大量结点的移动。2.链式存储结构链式存储结构就是在每个结点中至少包括一个指针域，用指针来体现数据元素之间逻辑上的联系。这种存储结构可把逻辑上相邻的两个元素存放在物理上不相邻的存储单元中；还可以在线性编址的计算机存储器中表示结点之间的非线性联系。链式存储结构的主要特点是：（1）结点中除自身外，还有表示连接信息的指针域，因此比顺序结构的存储密度小，存储空间利用率低；（2）逻辑上相邻的结点物理上不必邻接，可用于线性表、树、图等多种逻辑结构的存储表示；（3）插入、删除操作灵活方便，不必移动结点，只要改变结点中的指针即可。除上述两种主要存储方式外，散列法也是在线性表和集合的存储表示中常用的一种存储方式。1.1.3线.线性表的定义线性表（LinearList）是最常用并且最简单的一种数据结构。它是由n（n0）个数据元素（结点）a1，a2，„，an组成的有限序列。数据元素ai（1in）只是个抽象符号，其具体含义在不同情况下可以不在一些比较复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，一般把数据元素称为记录，含有大量记录的线英文字母表（A，B，„，Z）是线性表，表中每个字母是一个数据元素（结点）例2一副扑克牌的点数（2，3，„，10，A）也是一个线性表，其中数据元素是每张牌的点数2.线性表的存储线性表可采用顺序方式存储和链式方式存储。在各种高级语言中的一维数组就是用顺序方式存储的线性表，因此也常用一维数组来称呼顺序表。下面主要讨论的线.线性表的基本操作线性表是一种相当灵活的数据结构，不仅对它的数据元素可以查找访问，它的长度也可以根据需要增大或缩小，即可对线性表进行插入和删除数据元素运算。常见的线)InitList（L）构造一个空的线性表L，即表的初始化。(2)ListLength（L）求线性表L中的结点个数，即求表长。(3)GetNode（L取线性表L中的第i个结点，这里要求1iListLength（L）(4)LocateNode（L，x）在L中查找值为x的结点，并返回该结点在L中的位置。若L中有多个结点的值和x相同，则返回首次找到的结点位置；若L中没有结点的值为x，则返回一个特殊值表示查找失败。(5)InsertList（L在线性表L的第i个位置上插入一个值为x的新结点，使得原编号为i，i+1，„，n的结点变为编号为i+1，i+2，„，n+1的结点。这里1in+1，而n是原表L的长度。插入后，表L的长度加1。(6)DeleteList（L，i）删除线性表L的第i个结点，使得原编号为i+1，i+2，„，n的结点变成编号为i，i+1，„，n-1的结点。这里1in，而n是原表L的长度。删除后表L的长度减1。具体程序实现可参考本书C语言相关章节。1.1.4栈与队列结构1.栈与队列的定义栈是一种限定仅在表的一端进行插入与删除操作的线性表。允许进行插入与删除操作的这一端称为栈顶，而另一端称为栈底，不含元素的空表称为空栈，插入与删除分别称进栈与出栈。由于插入与删除只能在同一端进行，所以较先进入栈的元素，在进行出栈操作时，要比较后才能出栈。特别是，最先进栈者，最后才能出栈，而最晚进栈者，必最先出栈。因此，栈也称作后进先出（LastInFirstOut）的线性表，简称LIFO表。其示意图如图1-1所示：图1-1栈结构队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端进行删除元素。 允许插入的一端称队尾，允许删除的一端称队头。插入与删除分别称为入队与出队。队列示 意图如图1-2： Top栈顶Bottom栈底 图1-2队列2．栈与队列的存储 栈的存储结构 栈既然是一种线性表，所以线性表的顺序存储和链接存储结构同样适用于栈。 (1)栈的顺序存储结构 栈的顺序存储结构同样需要使用一个数组和一个整型变量来实现，利用数组来顺序存储 栈中的所有元素，利用整型变量来存储栈顶元素的下标位置。假定栈数组用 stack[StackMaxSize]表示，指示栈顶位置的整型变量用top表示，则元素类型为ElemType的 栈的顺序存储类型可定义为： ElemTypestack[StackMaxSize]; inttop; 其中，StackMaxSize为一个整型全局常量，需事先通过const语句定义，由它确定顺序 栈（即顺序存储的栈）的最大深度，又称为长度，即栈最多能够存储的元素个数；由于top用 来指示栈顶元素的位置，所以把它称为栈顶指针。 栈的顺序存储结构同样可以定义在一个记录类型中，假定该记录类型用Stack表示，则定 structStack{ElemTypestack[StackMaxSize]; inttop; 如图1-3所示：在顺序存储的栈中，top的值为-1表示栈空，每次向栈中压入一个元素时，首先使top增1，用以指示新的栈顶位置，然后再把元素赋值到这个位置上，每次从栈中弹出 一个元素时，首先取出栈顶元素，然后使top减1，指示前一个元素成为新的栈顶元素。由此 可知，对顺序栈的插入和删除运算相当于是在顺序表（即顺序存储的线性表）的表尾进行的， 其时间复杂度为O(1)。 图1-3栈的存储结构 栈也可以采用链式方式存储。 （2）队列的存储结构 队列的存储结构同线性表和栈一样，既可以采用顺序结构，也可以采用链接结构。 (1)队列的顺序存储结构 队列的顺序存储结构需要使用一个数组和两个整型变量来实现，利用数组来顺序存储队 列中的所有元素，利用两个整型变量来分别存储队首元素和队尾元素的下标位置，分别称它 们为队首指针和队尾指针。假定存储队列的数组用queue[QueueMaxSize]表示，队首和队尾指 针分别用front和rear表示，则元素类型为ElemType的队列的顺序存储类型可定义为： ElemTypequeue[QueueMaxSize]; intfront,rear; 其中QueueMaxSiIM电竞网站ze为一个整型全局常量，需事先通过const语句定义，由它确定顺序队 列（即顺序存储的队列）的最大长度，即最多能够存储的元素个数。当然，队列的顺序存储 空间也可以采用动态分配，此时用于决定最大长度的量可以为全局常量，也可以为全局或局 部变量。如在一个函数的函数体中使用下面语句能够为一个队列分配长度为n的数组空间， 该数组名仍用queue表示。 ElemType*queue=newElemType[n]; 队列的顺序存储类型同样可以用一个记录类型来表示，假定记录类型名为Queue，则该 类型定义为: structQueue{ ElemTypequeue[QueueMaxSize]; intfront,rear; 假定一个队列的当前状态如图1-4(a)所示，此时已经有a,b,c三个元素相继出栈（为了同队列中的元素相区别，把它们分别括了起来），队首指针front的值为3，指向的队首元素为 d，队尾指针的值为7，指向的队尾元素为h；若接着插入一个新元素i，则队列的当前状态如 图1-4(b)所示；若再接着删除一个元素，则变为图1-4(c)所示。 图1-4顺序存储队列的插入与删除 每次向队列插入一个元素，需要首先使队首指针后移一个位置，然后再向这个位置写入新元素。 当队尾指针指向数组空间的最后一个位置QueueMaxSize-1时，若队首元素的前面仍存在空闲 的位置，则表明队列未占满整个数组空间，下一个存储位置应是下标为0的空闲位置，因此，首 先要使队尾指针指向下标为0 的位置，然后再向该位置写入新元素。通过语句 rear=(rear+1)%QueueMaxSize可使存储队列的整个数组空间变为首尾相接的一个环（称此 为循环队列），当rear指向最后一个存储位置时，下一个所求的位置自动为数组空间的开始 位置（即下标为0的位置）。 同对线性表和栈的插入一样，每次在进行队列插入前，也要判断队列是否已满（即数组空