计算机二级C语言：公共基础知识part1

计算机二级c语言书籍知识框架，公共基础部分第一二章，后续会继续更新。

计算机二级C语言——公共基础知识Part1

一、计算机系统

1.1 .概述

第一台电子数字计算机：ENIAC

存储程序控制计算机：EDVAC（也称冯_诺依曼机）

冯_诺依曼：现代电子计算机之父

（1）程序和数据采用二进制数表示

（2）采用程序存储概念，程序和数据存放在存储器中

（3）硬件为五大基本部件：运算器、控制器、存储器、输入设备、输出设备组成

计算机发展分为4个阶段

（1）电子管

（2）晶体管

（3）中小规模集成电路

（4）大规模和超大规模集成电路

计算机系统基本组成

硬件系统·

主机

中央处理器

运算器

控制器

主存储器

外部设备

辅助储存器

输入设备

输出设备

软件系统

系统软件

操作系统

语言处理系统

数据库管理系统

系统辅助处理程序

应用软件

各种程序包

1.2 硬件系统

2.1 中央处理器（CPU）

计算机运算和控制核心包含运算器和控制器

运算器：负责对数据进行加工处理，算术运算和逻辑运算

控制器：负责对指令进行分析、控制并协调输入、输出操作或对主存储器访问

技术指标

字长：CPU一次能处理的二进制数据位数。 工作频率不变和CPU体系结构相似前提下，字长越长，CPU数据处理速度越快

主频：CPU时钟频率。主频越快，CPU运算速度越快

运算速度：CPU每秒所能执行的加法指令数目。更直观反映计算机速度

2.2 存储器

主存储器

RAM（随机存储器）

特点

1）可读写性，写入时，原数据被擦除

2）易失性，断电后数据消失，且无法恢复

分类

静态RAM：集成度低，价格高，存储速度快，不需要刷新

动态RAM：集成度高，价格低，存储速度慢，需要刷新

ROM（只读存储器）

信息只能读出，不能写入，具有内容永久性，断电后信息不会丢失

高速缓冲存储器

介于CPU和内存之间的一种小容量、可高速存取信息的芯片

用途；解决CPU和内存之间速度不匹配问题

辅助存储器

容量大。其中数据被读入内存后，才能被CPU读取，即CPU不能直接访问辅助存储器

2.3 外部设备

除主机外的各种硬件装置

分类

（1）输入/输出设备

（2）辅助存储器

硬盘

（3）终端设备

I/O接口

用于主机和外设之间的通信

2.4 总线

一组能够被多个部件“分时共享”的公共信息传输线路

分时：同一时刻，总线上只能传输一个部件发输的信息

共享：总线上可以“挂接”多个部件，各部件间信息交换通过总线传输

分类

片内总线：芯片内部的总线

系统总线：计算机系统内各功能部件间相互连接的总线，也称“内部总线”

通信总线：计算机设备之间或计算机与其他设备间的信息传输总线，也称“外部总线”

分为串行通信总线和并行通信总线

结构

单总线结构

仅一条系统总线，CPU、内存、I/O设备都挂在该总线上，允许两两之间信息交换

双总线结构

低速I/O设备从单总线上分离，实现内存总线与I/O总线分析

三总线结构

各部件间采用3条各自独立的总线

性能指标

总线周期：一次总线操作所需时间。通常由若干总线时钟周期构成

总线时钟周期：计算机的时钟周期

总线的工作频率：总线周期的倒数

总线宽度：通常指数据总线根数，用位表示，如数据总线有32根，则称该总线为32位总线

总线带宽：可理解为总线数据传输率，即单位时间内总线上传输数据的位数

时钟同步/异步：数据与时钟同步工作的总线称为同步总线 数据与时钟不同步工作的总线称为异步总线

总线复用：一种总线在不同的时间传输输不同的信息

信号线数：地址总线、数据总线以及控制总线3中总线的总和

2.5 计算机工作原理

步骤

1）将要执行的相关程序和数据先放入内存中

2）执行时，CPU根据当前程序指针寄存器的内容取出指令并执行

3）在取出下条指令并执行，如此循环直到程序结束时才停止执行

指令

计算机指令格式

一条计算机指令用一串二进制代码表示，包括操作码和操作数（地址码），若二者加起来为n字节，则称该指令为n字节指令

操作码;：指指令要完成操作的性质和功能，进行什么操作。操作码的二进制位数决定了该类型计算机最多能具有的指令条数

操作数：操作码执行的对象。可以是数据本身，也可以是存放数据的内存单元地址或寄存器名称。

计算机指令寻址方式

指令寻址：找到下一条要执行指令的地址

数据寻址：找到当前站在执行指令的数据地址

计算机指令系统

一台计算机所能执行的全部指令集合

其中“处理器控制和调试指令”用来实现计算机的硬件管理

执行过程：<1>取指令——<2>分析指令——<执行指令>

1.3 操作系统

对硬件的首次扩充，计算机硬件上的第一层软件，其功能有5个方面

1）处理器（CPU）管理

2）存储器管理

3）设备管理

4）文件管理

5）提供用户接口

进程管理

程序只有经过运行才能得到结果，其执行分为

顺序执行：一个具有独立功能的程序独占处理器直至执行结束

特点：顺序性、封闭性及可再现性等

并发执行：系统中引入多道程序技术，是程序或程序段间能并发执行

特点：失去了封闭性，不可再现性，间断性（即程序间可相互制约）

并发程序还具有并行性和共享性

进程：具有一定独立功能的程序关于某个数据集合的一次运行活动，简单说是指可以并发执行的程序的执行过程

包含程序和数据

一个程序可能对应多个进程

一个进程可以包含多个程序

进程状态及转换

1）运行状态

2）就绪状态

3）等待状态

4）创建状态

5）终止状态

进程组织

1）线性方式：适合进程数目不多的系统

2）链接方式

3）索引方式

进程调度（也可称为处理器调度或低级调度）

按一定策略动态地把CPU分配给处于就绪队列中的某一进程并使之执行的过程

仅负责对CPU进行分配

方式

抢占方式：把CPU分配给高优先级进程，并保存被抢占进程的信息，便于以后恢复

非抢占方式：一旦CPU分给了某进程，高优先级进程无法抢占现行进程的CPU

其他

线程：毕进程更小的可独立运行的基本单位

死锁：各进程互相独立动态获得，不断申请和释放系统中的软硬件资源，这可能使系统中若干个进程均因互相“无知地”等待对方所占有的资源而无线等待。

存储管理

主要对象：内存

功能

1）地址变换

2）内存分配

3）存储共享与保护

4）存储器扩充

地址重定位

1）地址变换：当用户程序进入内存执行时，吧用户程序中所有相对地址（逻辑地址）转换成内存中的实际地址（物理地址）

2）地址重定位：地址转换时，必须修改程序中所有与地址有关的项，即对程序中指令地址和指令中有关地址的部分（有效地址）进行调整

实现方式

静态地址重定位

程序执行前由操作系统重定位将其装入内存完成。

程序必须占用连续的内存空间，且一旦装入程序不便于移动

动态地址重定位

在程序运行期间进行，由专门硬件机构来完成

不要求程序装入固定的内存空间，在内存中允许再次移动位置，且可部分装入程序运行，同时也便于多个作业共享同一程序的副本。

文件管理

文件组织结构

逻辑结构

用户可见结构

根据有无逻辑结构分类

记录式文件：每个记录都用于描述实体集中的一个实体

流式文件：数据不组成记录，只是一串有顺序的信息集合（有序字符流）

物理结构

二、数据结构与算法

2.1 算法

基本特征

在特定环境中执行，并保证每一个一个步骤能够实现，结果能达到预期目的：可行性（1）

算法中每一步描述都是明确的，无论执行多少遍，所得结果应该相同：确定性（2）

算法能够在有限时间内完成，即执行有限步骤后能够终止：有穷性（3）

即算法需要足够的输入信息和初始化信息才是有效的：拥有足够的情报（4）

两种基本要素

数据对象的运算和操作（1）

四种基本运算和操作

算数运算（1

逻辑运算（2

关系运算（3

数据传输（4

算法的结构控制，即运算或操作顺序（2）

顺序结构

选择结构（或分支结构）

循环结构

设计的基本方法

针对待解决的问题，列举所有可能的情况：列举法（1）

通过分析少量特殊情况，从而找出一般关系：归纳法（2）

本质上也属于归纳法，不过递推法是从已知的初始条件出发，：递推法（3） 逐条退出所要求的个中间结果和最后结果，就是一步一步归纳

“减半”是指在不改变问题性质前提下，将问题规模减半：减半递推法（4） “递推”则是不断重复减半的过程

将一个复杂问题逐层分解成若干个简单的问题，解决这些简单问题后，：递归法（5） 再按原来分解的层次逐层向上，把简单问题综合以解决复杂的问题

把一个问题逐层分析，从上到下逐步去“试”，若成功，则得到问题的解；：回溯法（6） 若失败，就逐步退回，换个路线再行试探，直到彻底解决问题

算法的复杂度

所需资源越高，算法复杂度越高

分类

执行算法所需要的计算工作量：时间复杂度

算法程序执行具体时间和算法的时间复杂度不一致，具体时间受到计算机、程序设计语言以及算法实现过程中许多细节所影响。而算法的时间复杂度与这些因素无关。

算法计算工作量是用算法所执行的基本运算次数来度量

指执行算法所需要的内存空间：空间复杂度

和时间复杂度为两个相互独立概念，二者没有直接或间接关系

储存空间包括3个部分

输入数据所占的存储空间（1）

程序本身所占的存储空间（2）

算法执行过程中所需要的额外空间（3）

包括算法程序执行过程中的工作单元，以及某种数据结构所需的附加存储空间

降低算法空间复杂度

主要应减少输入数据所占的存储空间以及额外空间，通常采用压缩存储技术

2.2 数据结构基本概念

数据结构

互有关联的数据元素集合

数据处理领域中，通常把两两数据元素之间的关系用前后件关系来描述 （或直接前驱或直接后继关系）

例如“早餐”是“午餐”的前件，“午餐”是“早餐”的后件

前后件关系是数据元素之间最基本的关系，一般来说，数据元素之间任何关系都可以用前后件关系来描述

一个数据结构中没有数据元素，则称该数据结构为“空的数据结构”

2个要素

需要处理的数据元素集合，一般来说，这些数据元素具有某个共同特征：数据

结构

重要

线性结构

树形结构

网状结构

集合

数据逻辑结构

即反映数据元素之间逻辑关系（即前后件关系）的数据结构

2个要素

数据元素集合，通常记为D（1）

D上的关系，反映D中各数据元素之间前后件关系，通常记为R（2）

即一个数据结构可表示为，其中B表示数据结构

数据存储结构

数据的存储结构，又称为数据的物理结构，是数据的逻辑结构在计算机存储空间中的存放方式

一般来说，一种数据逻辑结构可以表示成多种存储结构； 采用不同存储结构，数据处理效率不同，因此进行数据处理时，要选择合适的存储结构很重要

图形表示

结点

根据前后件关系的复杂程度，分为2大类型

线性结构

非线性结构

注：一个空的数据结构需要根据具体情况确定；如果对该数据结构算法按线性结构规则处理，则属于线性结构；否则属于非线性结构

2.3 线性表及其顺序储存结构

基本理论

线性表是最简单也是最常用的一种数据结构

:定义为表的长度，n=0时称为空表，记作（）或？

非空线性表特征

有且只有一个根结点，它无前件

有且只有一个终端结点，它无后件

除根结点与终端结点外，其他结点有且只有一个前件、后件

结点个数n称为线性表的长度，n=0时称为空表

线性表相邻元素存在前后顺序关系，第一个元素无前驱，最后一个无后继， 其他元素有且仅有一个直接前驱和一个直接后继，因此线性表是一种线性结构

矩阵是一中比较复杂的线性表

矩阵中每一行看成一个元素，也可以把每一列看成一个数据元素。其中每一个数据元素实际上又是一个简单的线性表

复杂线性表中，一个数据元素由若干数据项组成，此时，把数据元素称为记录(record) 由多个记录构成的线性表又称为文件（file）

顺序存储结构（也称为顺序分配）

特征

所有元素所占空间连续（1）

各数据元素在存储空间中是按照逻辑顺序依次存放（2）

这样可以看出，它是用计算机内物理位置上的相邻关系来表示元素之间逻辑上的相邻关系。只要确定了首地址，线性表内任意元素的地址都可以方便地计算出来。

插入运算

一般线性表会开辟一个大于线性表长度的存储空间，若存储空间已满，仍继续插入会导致错误，这类错误称为“上溢”

2.4 栈和队列

栈和队列属于两种特殊的线性表

他们逻辑结构和线性表相同，只是其运算规则较线性表有一些限制，故又称为运算受限的线性表

栈及其基本运算

栈（Stack）

定义

一种特殊的线性表，其插入与删除都限定在线性表的同一端进行

栈的一端封闭，既不允许插入，也不允许删除；仅可以从另一端进行操作

术语

允许插入与删除的一端，通常用指针top指示栈顶位置：栈顶

不允许插入与删除的另一端，通常用指针bottom来指向栈底：栈底

没有任何元素的栈：空栈

插入、删除方式

栈的修改原则是“后进先出”或“先进后出”，因此栈也称为“后进先出”表或“先进后出”表

类似弹夹装子弹，最后压入的子弹总是第一个被射出，第一个压入的子弹最后被射出

特点

栈顶元素总是最后被插入的元素，也是最早被删除的元素(1)

栈底元素总是最早被插入的元素，也是最晚被删除的元素（2）

栈具有记忆作用（3）

在顺序存储结构下，栈的插入和删除运算都不需要移动表中其他元素（4）

栈顶指针top动态反映了栈中元素的变化情况（5）

3种栈的顺序存储结构基本运算

入栈（1）

栈的插入，在栈顶插入一个新元素

退栈（2）

栈的删除，取出栈顶元素赋予指定变量

读栈顶元素（3）

将栈顶元素（即栈顶指针top指向的元素）的值赋给一个指定变量

队列及其基本运算

队列（Queue）

定义

指允许在一段进行插入，另一端进行删除的线性表

术语

允许插入的一端，通常用一个成为尾指针（rear）的指针指向队尾元素：队尾

允许删除的一端，通常用一个成为头指针（front）的指针指向头元素的前一个位置：队头（或排头）

插入、删除方式

队列为“先进先出”或“后进后出”，队尾指针和头指针共同反映队列中元素动态变化的情况

2种运算

入队运算（1）

往队列队尾插入一个元素

退队运算（2）

从队列排头删除一个元素

循环队列及其运算

循环队列

队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间

队列的顺序存储结构一般采用循环队列的形式，当存储空间最后一个位置被使用，但还需要入队运算时，只要存储空间第一个位置空闲，便可将元素加入到第一个位置，即将存储空间第一个位置作为队尾

方式

用队尾指针rear指向队列中队尾元素，用排头指针指向排头元素的前一个位置

3种益处现象

下溢（1）

队列为空时，继续做出队运算产生的溢出现象； 下溢是正常现象，常用作程序控制转移的条件

真上溢（2）

队列满时，继续做进栈运算； 真上溢是一种出错状态，应设法避免

假上溢（3）

入队和出队时，头尾指针只增不减，使被删除的元素空间永远无法重新利用。当队列中实际元素个数远远小于向量空间规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作

2.5 线性链表

基本概念

顺序存储线性表缺点

为保证插入值两侧数据存储仍顺序存储，需要移动大量数据元素（1）

线性表以分配空间且存储空间已满，仍插入新元素时，会发生“上溢”错误（2）

线性表顺序存储结构不便于对存储空间的动态分配（3）

线性链表(即链式存储结构的线性表)简称链表

这种链表每个结点只有一个指针域，故称为单链表

2.6 树与二叉树

2.7 查找和排序顺序