计算机二级C语言 公共基础知识教程

计算机二级C语言 公共基础知识教程

`

第1章 数据结构与算法

§1.1 算法的复杂度

1. 算法的基本概念

①.算法：即解题方案的准确而完整的描述【注意：算法不等于程序，也不等于计算方法，通常，程序的编制不可能优于算法的设计】

②.利用计算机算法为计算机解题的过程实际上是在实施某种算法。

（1）算法的基本特征

算法一般具有4个基本特征：可行性、确定性、有穷性（包括精度要求确定的计算过程和合理的执行时间的含义）、拥有足够的情报。

（2）算法的基本要素

①.对数据对象的运算和操作

计算机算法就是计算机能处理的操作所组成的指令序列。通常，计算机可以执行的基本操作是以指令的形式描述的，一个计算机系统能执行的所有指令的集合称为该计算机系统的指令系统。其中基本的运算和操作包括：算术运算、逻辑运算、关系运算、数据传输（赋值、输入、输出等）。

②.控制结构：算法中各操作之间的执行顺序称为算法的控制结构。

ⅰ.描述算法的工具通常有：传统流程图、N—S结构化流程图、算法描述语言。

ⅱ.一个算法的3种基本控制结构：顺序结构、选择结构、循环结构。

（3）算法基本设计方法

算法基本设计方法：列举法、归纳法、递推（逐成分解）、递归、减半递推技术、回溯法。

2. 算法复杂度

算法复杂度包括时间复杂度和空间复杂度。注意两者的区别，不要混淆，见表1-1

§1.2 数据结构

1.2.1 逻辑结构和存储结构

1. 数据结构的基本概念

（1）数据结构：指相互有关联的数据元素的集合。

（2）数据处理：指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算、也包括对数据元素进行分析。

（3）数据结构研究的3个方面

①.数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构;

②.在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构;

③.对各种数据结构进行的运算。

2. 数据的逻辑结构

数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构可以表示成：B=(D,R)

其中，B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。在数据处理领域中，通常把数据元素之间的这种固有的关系简单地用前后件关系（或直接前驱或直接后继关系）来描述。例如，假设a与b是D中的；两个数据，则二元组（a，b）表示a是b的前件，b是a的后件

例如，如果把一年四季看作一个数据结构，则可表示成：B =(D,R)

D ={春季,夏季,秋季,冬季}

R ={(春季,夏季),(夏季,秋季),(秋季,冬季)}

计算机二级C语言 公共基础知识教程

3. 数据的存储结构

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。

由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。

一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。 顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。

链式存储结构就是在每个结点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系。

1.2.2 数据结构的图形表示

一个数据结构除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后向结点。

例如，一年四季的数据结构可以用如图的图形表示

又如，反映家庭成员间辈分关系的数据结构可以用如图的图形表示

在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（也称叶子结点）。例如，在数据结构一年四季中，―春‖所在的结点（简称为结点―春‖，下同）为根结点，结点―冬‖为终端结点。通常，一个数据结构中的元素结点可能是在动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（称为插入运算），也可以删除数据结构中某个结点（称为删除运算）插入与删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等等。

1.2.3 线性结构和非线性结构

根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。

（1）如果一个非空的数据结构满足下列两个条件：

①.有且只有一个根结点；

②.每一个结点最多有一个前件，也最多有一个后件。

则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都为线性结构。

如果一个数据结构不是线性结构，则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。

（2）线性表的顺序存储（也称顺序分配）结构具有以下两个基本特点：

①.线性表中所有元素所占的存储空间是连续的；

②.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

元素ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。

（3）顺序表的运算有查找、插入、删除3种。

计算机二级C语言 公共基础知识教程

§1.3 栈 （zhàn）

1. 栈的基本概念

栈（stack）是一种特殊的线性表，是限定只在一端进行插入与删除的线性表。

在栈中，一端是封闭的，既不允许进行插入元素，也不允许删除元素；另一端是开口的，允许插入和删除元素。通常称插入、删除的这一端为栈顶，另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。 栈是按照―先进后出‖或―后进先出‖的原则组织数据的。

因此，栈也被称为―先进后出‖表或―后进先出‖表。由此可 以看出，栈具有记忆作用

通常用指针top来表示栈顶的位置，用指针botton指向栈

底。往栈中插入一个元素称为入栈运算，从栈中删除一个元素

（即删除栈顶元素）称为退栈运算。栈顶指针top动态反应了

栈中的元素变化情况。（如右图所示）

栈这种数据结构在日常生活中也是常见的。例如，枪械的子弹匣就可以用来形象的表

示栈结构。子弹匣的一端是完全封闭的，最后被压入弹匣的子弹总是最先被弹出，而

最先被压入的子弹最后才能被弹出。

2. 栈的顺序存储及其运算

栈的 …… 此处隐藏：16366字，全部文档内容请下载后查看。喜欢就下载吧 ……