计算机应用基础知识

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）是最常用并且最简单的一种数据结构。它是由n（n≥0）个数据元素（结点）a1，a2，…，an组成的有限序列。

　　① 数据元素的个数n定义为表的长度（n=0时称为空表）。

　　② 将非空的线性表（n＞0）记作：（a1，a2，…，an）

　　③ 数据元素ai（1≤i≤n）只是个抽象符号，其具体含义在不同情况下可以不同。

　　在一些比较复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，一般把数据元素称为记录，含有大量记录的线性表也称为文件。

　　例1英文字母表（A，B，…，Z）是线性表，表中每个字母是一个数据元素（结点） 例2一副扑克牌的点数（2，3，…，10，J，Q，K，A）也是一个线性表，其中数据元素是每张牌的点数

　　2.线性表的存储,　　线性表可采用顺序方式存储和链式方式存储。在各种高级语言中的一维数组就是用顺序方式存储的线性表，因此也常用一维数组来称呼顺序表。下面主要讨论的线性表对象是指顺序表。

　　3.线性表的基本操作,　　线性表是一种相当灵活的数据结构，不仅对它的数据元素可以查找访问，它的长度也可以根据需要增大或缩小，即可对线性表进行插入和删除数据元素运算。

　　常见的线性表的基本运算

　　(1) InitList（L）

　　构造一个空的线性表L，即表的初始化。

　　(2) ListLength（L）

　　求线性表L中的结点个数，即求表长。

    　(3) GetNode（L，i）

　　取线性表L中的第i个结点，这里要求1≤i≤ListLength（L）

　　(4) LocateNode（L，x）

　　在L中查找值为x 的结点，并返回该结点在L中的位置。若L中有多个结点的值和x 相同，则返回首次找到的结点位置；若L中没有结点的值为x ，则返回一个特殊值表示查找失败。

　　(5) InsertList（L，x，i）

　　在线性表L的第i个位置上插入一个值为x 的新结点，使得原编号为i，i+1，…，n的结点变为编号为i+1，i+2，…，n+1的结点。这里1≤i≤n+1，而n是原表L的长度。插入后，表L的长度加1。

    　(6) DeleteList（L，i）

　　删除线性表L的第i个结点，使得原编号为i+1，i+2，…，n的结点变成编号为i，i+1，…，n-1的结点。这里1≤i≤n，而n是原表L的长度。删除后表L的长度减1。具体程序实现可参考本书C语言相关章节。

　　1.1.4栈与队列结构

　　1.栈与队列的定义

　　栈是一种限定仅在表的一端进行插入与删除操作的线性表。允许进行插入与删除操作的这一端称为栈顶，而另一端称为栈底，不含元素的空表称为空栈，插入与删除分别称进栈与出栈。 由于插入与删除只能在同一端进行，所以较先进入栈的元素，在进行出栈操作时，要比较后才能出栈。特别是，最先进栈者，最后才能出栈，而最晚进栈者，必最先出栈。因此，栈也称作后进先出（Last In First Out）的线性表，简称LIFO表。