第一章 计算机基础知识

大家好，欢迎来到IT知识分享网。

第一章 计算机基础知识

1.1 计算机历史

1.1.1计算机发展史

• 第一代 ：电子管计算机 （1946-1957）

​ 特点：体积大、耗电多、可靠性差、价格昂贵

​ 应用：科学和工程计算

​ 1946年 美国 ENIAC计算机 是世界上第一台计算机

• 第二代：晶体管计算机 （1958-1964）

​ 特点：相对于第一代，体积缩小、耗电减少、可靠性提高、性能提高

​ 应用：数据处理

• 第三代：中小规模集成电路 （1965-1970）

​ 特点：相对于第二代，体积更小、耗电更少、可靠性更好、性能提高

​ 应用：科学计算、数据处理、工业控制

• 第四代：大规模集成电路 （1971年至今）

​ 特点：微型化、耗电极少、可靠性很高

​ 应用：各行各业

1.1.2 计算机领域代表人物

• 艾伦·图灵

  英国计算机科学家，被誉为“计算机科学与人工智能之父”，以他的名字命名的“图灵奖”是计算机领域的最高奖项

• 冯·诺依曼

​ 是理论计算机科学和博弈论的奠基者，被誉为“现代计算机之父”，提出了存储程序的计算机工作原理、二进制编码思想

• 丹尼斯·里奇 和 肯·汤普森

​ 都是美国计算机软件工程师，共同创建了UNIX操作系统和C语言，1983年获得图灵奖

1.2 计算机系统

1.2.1计算机硬件：运算器、控制器、存储器、输入输出设备

• 运算器：是计算机执行各种算术运算和逻辑运算操作的部件。包含若干寄存器，用来暂时存放操作数和中间结果
• 控制器：是指挥控制计算机各个部件按照指令的功能和要求协调工作的部件，是计算机的“神经中枢”和“指挥中心”
• 存储器：是计算机系统中的记忆设备，用来存放程序和数据。存储器包括主存储器、外存储器以及CPU内部的高速缓冲存储器（Cache）
  • 数据存取速度：Cache > 主存储器 > 外部存储器
  • Cache：将CPU频繁用到的程序和数据从主存储器送到Cache,这样CPU就可以直接从内部获得指令和数据，达到加速运行的效果
  • 主存储器：又称内存，核心在于地址和内容
  • 外部存储器：又称为辅助存储器，作为主存储器的辅助存储部件，外部存储器大大扩大了存储器容量

    U盘，硬盘，光盘

• 输入输出设备

1.2.2 计算机软件系统：系统软件、应用软件

• 系统软件：
  • 操作系统：Windows、UNIX、Linux、MacOS
  • 语言处理系统：Visual C++、Java、Pycharm
  • 数据库管理系统：MySQL
  • 服务程序：磁盘分区
• 应用软件：……

1.3数据表示与计算

1.3.1进制转换

• 二进制：范围是0-1,”逢2进1“，以字母B表示二进制
• 八进制：范围是0-7,”逢8进1“，以字母O表示八进制
• 十进制：范围0-9，”逢10进1“，以字母D表示十进制
• 十六进制：范围0-15，”逢16进1“，以字母H表示十六进制，有0-9和ABCDEF表示10-15

常用进制的书写方式

• 字母表示：11B (二进制)、11O(八进制)
• 下标表示：$(11{)}_8$ (八进制) 、$(11{)}_{10}$（十进制）

1.3.2不同进制之间的转换

• 非十进制转化为十进制
  • 将非十进制按位权展开，求出各个数字之和，就可以得到相应十进制数
  • $（1011.01{）}_2=1\ast 2^0+1\ast 2^1+0\ast 2^2+1\ast 2^3+0\ast 2^{-1}+1\ast 2^{-2}=11.25$
• 十进制转化为非十进制（R）
  • 将十进制整数部分和小数部分分别转化成R进制数，再将结果结合起来。其中十进制的整部分采用“除基取余法”进行转换，小数部分采用“乘基取整法”
  • 除基取余法：

• 乘取整法

• 二、八、十六进制的相互转换
  • 二进制和八进制之间的转换

• 二进制与十六进制之间的转换

$(.10101{)}_2=0110/0110./1010/1000=66.A8$

• 八进制和十六进制

$(57.16{)}_8$=5/101 7/111 . 1/001 6/110=101 111 . 001 110

0010/2 1111/F .0011/3 1000/8 = 2F.38

1.3.3 原码、反码、补码

• 原码：符号位+真值的绝对值，最高位用符号表示(0代表正，1代表负)，其余位表示真值的绝对值
  • 8位二进制数 [+1]=[00000001] [-1]=[]
• 反码：正数的反码就是原码，负数的反码是在原码的基础上符号位不变，其余各位取反。

[+1]=$[00000001{]}_{原}$=$[00000001{]}_{反}$

[-1]=$[{]}_{原}$=$[{]}_{反}$

• 补码：正数的补码就是原码，负数的补码是在原码基础上符号位不变，其余各位取反，最后+1，也就是在反码基础上+1

1.4 信息编码

1.4.1 ASCII码

• ASCII码全称是美国信息交换标准代码，是一种7位二进制编码，能表示$2^7=128$种字符
• ASCII码包括以下2类最常用的字符
  • 数字0-9 二进制：011000B~0B 十六进制：30H~39H 十进制:80-89
  • 26个英文字母：A~Z：65 ~ 90 a~z: 97~122

1.4.2 汉字信息编码

• 区位码和国标码：
  • 区位码把常用的汉字、数字、符号分类编在一个方阵里，方阵的每一行称为区，每一列称为位，区码和位码均采用01~94的十进制表示，方阵的每个字符用4位十进制表示，前两位是区码，后两位是位码。
  • 国标码：GB/T2313-1980为标准，采用21H-73H表示
  • 区位码与国标码之间的换算关系：区码和位码分别加上十进制数32=国标码

1.5网络基础

1.5.1网络体系结构

• 计算机网络：连接多台计算机，解决计算机之间相互传输数据的问题
• 因特网：局域网（LAN）、广域网（WAN）
• TCP/IP协议：TCP协议（传输协议），IP协议（网络互联协议），FTP（文件传输协议），Telnet(远程登录协议)，SMTP、POP3、IMAP（电子邮件协议）
• IP地址：是因特网中的每个网络和每台计算机的地址（192.168.31.119）
• IPv4与IPv6：IPv4,255.255.255.255,一共有32位，可以提供$2^{32}$个地址（约20亿），IPv6,一共有128位，最多有$2^{128}$个地址

1.5.2域名

• 域名是IP地址的名称
• 域名的构成：每个部分由.隔开，末尾的部分叫顶级域名com、gov、edu；cn,us,uk,jp,fr,kr
• 域名解析：是指把网络的域名和IP地址建立连续，由域名系统完成（DNS）

1.6计算机语言

1.6.1机器语言

• 是计算机可以直接识别并运行的语言（0101）

1.6.2汇编语言

• 是机器语言的另一种形式，用英文字母或单词缩写作为指令，例如0100 0001 0010 汇编语言可以写成ADD R1 R2，需要通过编译器将汇编程序转化为可执行程序

1.6.3 高级语言

• 是多种编程语言的统称
• 编译型语言与解释型语言

• 面向过程语言与面向对象语言

第二章 语法基础

2.1 存储单位

2.1.1 常见的内存存储单位有:

• bit(位) :称为位，是计算机内存的最小单位，1位的存储内容是 0或1
• byte:称为字节，是计算机存储的基本单位。1字节由8位组成
• KB:1KB = 1024byte = $2^{10}$byte
• MB:1MB = 1024KB = $2^{10}$KB
• GB: 1GB = 1024MB = $2^{10}$MB
• TB:1TB = 1024GB = $2^{10}$GB

2.2 数据类型

2.3 变量名

• 变量名只能以字母或下划线开头，后面的字符可以用字母、下划线或者数字
• C++定义一个变量的格式 类型标识 变量名；

2.3.1 常量

• C++ 定义一个常量的格式为 const 类型标识 变量名；

2.4 运算符

• 运算符优先级口诀：

单、算、移、关、与，异、或、逻、条、赋

2.4.1 位运算符

2.5 数据输入输出

2.5.1字符输入输出

输入单个自符：

• char c;
  c = getchar();
  

输出单个字符：

• char c = '*';
  putchar(c);
  

2.5.2标准输入输出流

cin >> 变量1 >> 变量2 >>....;
cot << 变量1 << 变量2 >>....;

2.5.3格式化输入输出

scanf(“格式控制符”，地址);
printf(“格式控制符”，输出);

2.6 选择结构

2.6.1条件运算符

表达式1 ? 表达式2 : 表达式3
c = (a>b) ? a : b; 

2.6.2 switch语句

i=20
switch(i/10):
{
    case 常量1 : 语句;break;
    case 常量2 : 语句;break;
    ……
    case 常量n : 语句;break;
    default :  语句;break;
}

2.7字符串

2.7.1字符数组

char s[10] = "hello";

这里定义了一个大小为10的char类型数组s，并将s[0]~s[5]分别赋值为‘h’,‘e’,‘l’,‘l’,‘o’,‘\0’,其余位置自动补0.其中，\0是一个自动添加的转义字符，作为字符串结束的标志。

2.7.3字符串函数

字符串函数头文件 #include <cstring> ，以下是常见字符串函数

• strlen(s):获取字符串长度，字符串s的实际长度，而不是实际占用空间
• strcpy(s,t):函数会将字符串t的内容复制到字符串s
• strncpy(s,t,n):会将字符串t中的前n个字符复制到s的前n个位置，即s[0],s[1],……,s[n-1],需要注意的是，该操作不会修改s[n]及后面的内容
• strcmp(s,t):字典序比较，返回一个整数，表示字符串s和t比较的结果
• strcat(s,t):字符串拼接，会将字符串t拼接到s的末尾

2.9结构体

在C++中，保存单个数据可以使用基础的数据类型，保存多个相同类型的数据可以使用数组，如果保存多个不同类型的数据，就需要用到C++中的结构体

2.9.1 结构体的声明

struct xxx(结构体的名字)
{
    成员变量1;
    成员变量2;
    成员变量3;
    ……
    成员变量n;
};

struct Student
{
	string name;
    int age;
    float height;
};

2.9.2结构体变量的定义

Student cy,amy;
Student stus[10]

声明同时定义
struct Student
{
	string name;
    int age;
    float height;
}cy,amy;

2.9.3结构体变量的赋值

一般格式：结构体变量名.成员变量名

cy.name = "chenyi";
cy.height = 142.5;
输出
printf("%f",cy.height);
cout<<cy.height<<endl;

也可以使用大括号加参数列表的形式对结构体变量赋值(统一赋值)：

cy = {"chenyi",11,142.5}

2.10 递归函数

递归函数计算n的阶乘。对于一个整数n，定义n的阶乘从1到n所有整数的乘积，表示为n！

定义一个函数f(int n)来计算n的阶乘

• 当 n=1时，f(n)=1
• 当n>1时，f(n)=n*f(n-1) 当前项f(n)和后项f(n-1)的关系

int f(int n)
{
	if(n==1)
	return 1;
	return n*f(n-1);
}
ci'shin=5

第三章 数据结构

3.1 线性表

• 线性表是由n个元素节点组成的有限序列，n为线性表长度，当表中没有长度时为空表
• 线性表的特点：存在一个没有前驱的节点的数据元素（开头元素），存在一个没有后继节点的数据元素（结尾元素）
• 线性表：
  • 顺序表
  • 链表
    • 单向链表
    • 双向链表
    • 循环链表

3.1.1 顺序表

• 顺序表是在计算机内存中用一组地址连续的存储单元依次存储数据元素的线性表
  

  数据元素在线性表中的位序	存储地址	内存状态
  1	b	a1
  2	b+c	a2
  i	b+(i-1)*c	ai
  n	b+(n-1)*c	an

  只要确定了存储线性表的起始位置和数据元素在线性表中的位序，就可以知道元素的存储地址，这个特点被称为随机存储

3.1.2 链表

• 单向链表是非连续存储的线性表，链表的每一个元素保存指向下一个元素的指针，由于链表不要求逻辑上相邻的元素在物理位置上也相邻，因此链表不具备随机存储的特点，但是链表在插入和删除元素时不需要移动元素的位置
• 
• 双向链表的每个元素都有两个指针，分别指向元素的直接后继和直接前驱，因此从双向链表的任意一个元素开始，都可以访问它的前驱元素和后继元素

• 循环链表的最后一个元素指向第一个元素，形成一个环。因此，从循环链表中的任意一个元素出发都能访问到其他元素

3.2 树

• 根节点：树有唯一的根节点，它没有前驱节点
• 度：一个节点的子树的个数，度为0的节点，叫叶子节点，树中各节点的度的最大值称为这棵树的度
• 子节点：节点子树的根，称为该节点的子节点
• 深度：一棵树中所有节点的层次的最大值称为树的深度
• 森林：森林是若干棵互不相交的树的合集

3.2.1二叉树

• 概念：它的度为2，即二叉树的每个节点最多有两个子节点，每个节点的子节点分别被称为左孩子、右孩子。它的两颗子树分别被称为左子树和右子树
• 特点：
  • 二叉树的第i层，最多有$2^{i-1}$个节点
  • 深度为k的二叉树至多有$2^k-1$个节点
  • 一棵深度为k，且有$2^k-1$个节点的二叉树被称为满二叉树，这种树的特点是每层上的节点数都是最大节点数 完全二叉树（略）
  • 对任意一棵，如果其叶子节点的数为$n_0$,度为2的节点数为$n_2$,则一定满足$n_0=n_2+1$
  • 具有n个节点的完全二叉树深度为$[lo{g}_2^n]+1$

3.2.2 二叉树的遍历

• 先序遍历：根，左，右 （左点）
• 后序遍历：左，右，根 （右点）
• 中序遍历：左，根，右 （下点）

3.2.3 二叉树的应用

• 前缀表达式：先序遍历
• 中缀表达式：中序遍历
• 后缀表达式：后序遍历
• 说明:第一步先把表达式拆分成二叉树，运算符作为根节点和子节点，用前中后序遍历写出前中后表达式

3.2.4 哈夫曼编码

• 特点：出现频率较高的数据采用较短的编码，频率较低的采用较长的编码。在进行哈夫曼编码时，选择频率最小的两个数据作为左子树和右子树，频率之和作为子树的根节点，然后将这两个数据从待编码的数据中删除，并将根节点作为新数据加入到待编码的数据中，重复上面的过程，直到所有的数据都被挑选出来。
• 例子，现有字符a,b,c,d,e，每种字符出现的频率是10%，12%，33%，20%，25%

3.3 图

3.3.1 定义

• 图是由顶点集合和边集合构成的数据结构，记为Graph=(V,E)。V表示顶点的集合，E表示边的集合。边有方向的图为有向图，没有方向的图为无向图

3.3.2 基本元素概念

• 入度: 以某个顶点为终点的有向边的数目
• 出度：以某个顶点为起点的有向边的数目
• 度：在无向图中，与顶点相连的边的数目称为顶点的度；在有向图中，顶点的入度和出度之和，称为顶点的度
• 连通：如果图中顶点U和V之间存在一条从U出发，通过若干条边、顶点到达V的通路，则称UV是连通的
• 权值：从一个顶点到另一个顶点的代价或距离，也可以形象的理解为长度
• 回路：起点和终点相同的路径，称为回路
• 完全图：无向完全图是指每个顶点都与其他顶点恰好有一条边相连，因此有n个顶点的无向完全图有$n(n-1)/2$条边；有向完全图是指每个顶点恰好有两条方向相反的边相连，因此有n个顶点的有向完全图含有$n(n-1)$条边。

3.3.3 拓扑排序

• 拓扑排序是对有向无环图的一种排序方法，具体排序规则是：找到一个入度为0的顶点，输出这个顶点，然后删除所有与该顶点相连的边，循环这个操作直到输出所有顶点。
  图是由顶点集合和边集合构成的数据结构，记为Graph=(V,E)。V表示顶点的集合，E表示边的集合。边有方向的图为有向图，没有方向的图为无向图
  

3.3.2 基本元素概念

• 入度: 以某个顶点为终点的有向边的数目
• 出度：以某个顶点为起点的有向边的数目
• 度：在无向图中，与顶点相连的边的数目称为顶点的度；在有向图中，顶点的入度和出度之和，称为顶点的度
• 连通：如果图中顶点U和V之间存在一条从U出发，通过若干条边、顶点到达V的通路，则称UV是连通的
• 权值：从一个顶点到另一个顶点的代价或距离，也可以形象的理解为长度
• 回路：起点和终点相同的路径，称为回路
• 完全图：无向完全图是指每个顶点都与其他顶点恰好有一条边相连，因此有n个顶点的无向完全图有$n(n-1)/2$条边；有向完全图是指每个顶点恰好有两条方向相反的边相连，因此有n个顶点的有向完全图含有$n(n-1)$条边。

3.3.3 拓扑排序

• 拓扑排序是对有向无环图的一种排序方法，具体排序规则是：找到一个入度为0的顶点，输出这个顶点，然后删除所有与该顶点相连的边，循环这个操作直到输出所有顶点。