2021计算机应用基础知识.docx

本文格式为Word版，下载可任意编辑2021计算机应用基础学问 2021计算机应用基础学问 1.1数据结构与算法 借助于计算机解决问题，首先需要了解所处理对象的性质和特点即所操作对象的数据结构，然后再设计解决问题的方法和步骤即设计一个合理的算法，即通常所说的“程序=数据结构+算法”。 1.1.1算法的基本概念 “算法”Algorithm一词最早来自公元9世纪波斯数学家比阿勒霍瓦里松的一本影响深远的著作代数对话录。20世纪的英国数学家图灵提出了出名的图灵论点，并抽象出了一台机器，这台机器被我们称之为图灵机。图灵的思想对算法的进展起到了重要的作用。一般来说，算法是指完成一个任务或解决一个问题所需要的具体步骤和方法的描述。在这里我们说的算法是指计算机能执行的算法。 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 线性表结构 1.线性表的定义 线性表Linear List是最常用并且最简洁的一种数据结构。它是由nn0个数据元素结点a1，a2，an组成的有限序列。 数据元素的个数n定义为表的长度n=0时称为空表。 将非空的线性表n0记作：a1，a2，an 数据元素ai1in只是个抽象符号，其具体含义在不怜悯况下可以不同。 在一些比较冗杂的线性表中，一个数据元素可以由若干个数据项组成。在这种状况下，一般把数据元素称为记录，含有大量记录的线性表也称为文件。 例1英文字母表A，B，Z是线性表，表中每个字母是一个数据元素结点 例2一副扑克牌的点数2，3，10，J，Q，K，A也是一个线性表，其中数据元素是每张牌的点数 2.线性表的存储 线性表可接受挨次方式存储和链式方式存储。在各种高级语言中的一维数组就是用挨次方式存储的线性表，因此也常用一维数组来称呼挨次表。下面主要协商的线性表对象是指挨次表。 3.线性表的基本操作 线性表是一种相当灵敏的数据结构，不仅对它的数据元素可以查找访问，它的长度也可以依据需要增大或缩小，即可对线性表进行插入和删除数据元素运算。 常见的线性表的基本运算 (1) InitListL 构造一个空的线性表L，即表的初始化。 (2) ListLengthL 求线性表L中的结点个数，即求表长。 (3) GetNodeL，i 取线性表L中的第i个结点，这里要求1iListLengthL (4) LocateNodeL，x 在L中查找值为x 的结点，并返回该结点在L中的位置。若L中有多个结点的值和x 相同，则返回首次找到的结点位置；若L中没有结点的值为x ，则返回一个特殊值表示查找失败。 (5) InsertListL，x，i 在线性表L的第i个位置上插入一个值为x 的新结点，使得原编号为i，i+1，n的结点变为编号为i+1，i+2，n+1的结点。这里1in+1，而n是原表L的长度。插入后，表L的长度加1。 (6) DeleteListL，i 删除线性表L的第i个结点，使得原编号为i+1，i+2，n的结点变成编号为i，i+1，n-1的结点。这里1in，而n是原表L的长度。删除后表L的长度减1。具体程序实现可参考本书C语言相关章节。 1.1.4栈与队列结构 1.栈与队列的定义 栈是一种限定仅在表的一端进行插入与删除操作的线性表。允许进行插入与删除操作的这一端称为栈顶，而另一端称为栈底，不含元素的空表称为空栈，插入与删除分别称进栈与出栈。 由于插入与删除只能在同一端进行，所以较先进入栈的元素，在进行出栈操作时，要比较后才能出栈。特殊是，最先进栈者，最终才能出栈，而最晚进栈者，必最先出栈。因此，栈也称作后进先出Last In First Out的线性表，简称LIFO表。 第 5 页 共 5 页