[数据结构与算法]《算法笔记知识点记录》第二章——快速入门2[选择结构、循环结构和数组]

?前言?

今天是我开坑的第二天，也不知道这个系列会不会火呢？
今天依旧会介绍很多基础知识，但是更注重逻辑，如果我有哪些没有讲清楚的，欢迎大家联系我，你提出的问题是我修改完善的基础，万分感谢。

• 欢迎大家加入我的打卡队列，如果你刷完了对你有帮助请你评论一个打卡。
• 如果你觉得这本书有用的话还希望多多支持作者。

如果觉得这个文章有用还希望大家交出素质三连呀。

🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
?联系方式：2201891280(QQ)
📔源码地址：https://gitee.com/xingleigao/algorithm-notes
?全文大约阅读时间： 80min

🍭1.基础知识点

有了上次课的亿点点基础，我们就可以开始学习一些稍微复杂一点的结构了。上节课的内容非常重要，需要我们去反复推敲打磨，没事了都要回头看一看呢。
那我们废话不多说，开始今天的学习吧。

🐌1.1选择结构

c语言的选择结构主要是两个，其中一个就是if－else结构，另外一个就是switch - case结构，我们今天来分别了解一下吧。

🐰1.1.1if语句及其嵌套

if语句

if语句的基本用法如下：

if(条件A){
	...
}
else{
	...
}

就是根据条件来跳转到不同的语句执行，可以用下面的流程图来表示这一个结果。

举个栗子🌰

#include<cstido>
int main(){
	int n = 2;
	if(n > 3){
		n = 9;
		printf("%d\n",n);
	}
	else{
		printf("%d\n"n);
	}
	return 0;
}

输出结果：2
需要注意的点有三个：

1. 一般只有在明确不出错的情况下才不加括号。(加上不会错就完了)
2. 分支结果注意打缩进，新手不打缩进差错看的很费劲，提升下代码可读性吧，求求了😂
3. !=0可以省略，==0可以用!替换。eg.a==0与!a是一样的。

if语句的嵌套

基本嵌套结构如下：

if(条件A){
		if(条件B){
			...
		}
		else{
			...
		}
	}
else{
	..
}

其实就是套娃，相信都还是可以看得懂的。再次强调，缩进、缩进、缩进（重要的事说三遍）。

---

一点补充：(嵌套的另外一种写法)

if(条件A){
	..	
}
else if(条件 B){
	...
}
else{
	...
}

🐮1.1.2switch-case结构

sitch-case主要用于多分支的结构，在分支较少的时候并不常用。基本语法如下：

switch(表达式){
	case 常量表达式1:
		...
		break;
	case 常量表达式2:
		...
		break;
	default:
		...
}

它的执行过程可以看成下图：

需要注意点：

1. 每个case后面一定要加break，不然就会顺序执行所有的之后的函数，可以看流程图。
2. 适用于情况较多的时候，平时使用不常见。

🐟1.2 循环结构

循环结构主要包含三种，即while、for、do--while，需要注意循环体的控制语句有两个break、continue。

🐬1.2.1 while语句

假设需要计算1+2+…+n那么应该怎么计算呢？
while就用于这样的问题，当条件满足时不断执行,基本结构如下：

while(条件A){
	...
}

基本的执行逻辑就是如下图：

上面那个题目的代码就可以如下所示：

#include<csdtio>
int main(){
	int n = 100, sum = 0;
	while(n){
		sum += n;
		n--;
	}
	printf("%d\n",sum);
	return 0;
}

其中while的判断和if一样可以省略是否==0，所以这里我算的是100+99+…+1

🐳1.2.2 do…while语句

do...while语句和while语句很类似，但是他们格式是颠倒的。

do{
	...
}while(条件A)

执行的顺序如图所示：
do…while会先执行循环体一次，然后才去判断循环条件是否满足，这就使得do…while的语句适用性远远不如while。 建议不用233

🐋1.2.3 for循环

for语句的使用频率是三种循环中最高的，常见格式如下：

for(初始值表达式;判断条件;循环执行表达式){
	...
}

常见的执行流程如下

举个栗子🌰

#include<cstdio>
int main(){
	int sum = 0;
	for(int i = 1 ; i <= 100 ; i++)
		sum += i;
	printf("%d\n",sum);
	return 0;
}

其中i的初始值是1，i小于等于100不断循环，循环结束后i的值会加1。
最终的结果肯定就是1+2+…+100 啦
for需要注意的点：

1. 每个表达式都可以省略 第二个表达式省略代表死循环
2. for第一个表达式定义的变量只在循环体内有效，循环执行结束变量就会被回收。

🦈break和contin语句

break和continue都是对循环体的控制。

• 在switch的时候看到过break，看那张图break就是跳出循环体执行下一条语句。
• 而continue是结束本次循环开启下一轮循环

看不懂没关系 来看图0.0

主要区别就是控制跳出之后进行什么操作。
举两个栗子🌰作为结束吧

#include<cstdio>
int main(){
	int sum = 0;
	for(int i = 1; i <= 100; i ++){
		if(i % 2 == 1)	continue;
		sum += i;
		if(sum > 2000)	break;
	}
	printf("sum = %d\n",sum);
	return 0;
}

上面程序实现的功能就是计算从1到100内来连续奇数和不大于2000的最大值。

??1.3 数组

🗡1.3.1 一维数组

数组就是把相同数据类型组合在一起而产生的数据集合。 数组就是从某个地址开始的连续若干位置行程的元素集合。
数据类型 数组名[数组大小]
常见的一维数组举例:

int a[10];
double db[233];
char str[1000000];
bool HashTable[10000000];

访问元素的方法数组名称[下标]
定义了长度为size的数组之后，只能访问下标为0~(size-1)的元素！！

数组的初始赋值

int a[10] = {1, 2 ,3 };

可以只给出部分元素，后面的部分元素会置为0。
如果希望初始化所有元素为0可以int a[10] = {0};或者int a[10] = {};
需要注意的点：

1. 括号的意思是取元素a[2]和*(a+2)的作用是等价的。(知道你们看不懂，指针学了回来看0.0)
2. 数组首地址是个常量也就是a是个常量 不可更改！！

一个栗子🌰结束吧

#include<stdio.h>
int main(){
	int a[10];
	scanf("%d", & a[0]);
	for(int i = 1; i < 10; ++i)
		a[i] = a[i - 1] * 2;
	for(int i = 1; i < 10; ++i)
		printf("a[%d] = %d\n",i , a[i]);
	return 0;
}

读入第一个元素 然后从前往后顺推每一个元素的值为前一个两倍，输出就好了。

🛡1.3.2冒泡排序

排序：将一个无序序列按照某种规则进行有序排列
冒泡排序是基于交换的排序方式，是其中最简单的一种排序方式。

---

首先介绍一下交换的实现方式

int temp = a;
a = b;
b = temp;

上面这样就完成了两个元素的交换。

---

冒泡排序的思想是从前往后扫描变量，如果前面的元素比后面的元素大就交换元素，否则不动。
这就像冒泡一样，每次都将最大的元素放在最后面，完成n－1轮就完成了对整个数组的排序。看下图

具体实现代码：

#include<stdio.h>
int main(){
	int a[10] = { 3, 1, 4, 5, 2};
	for(int i = 0; i <= 4; ++i){	//进行n－1躺排序
		for(int j = 0; j < 5 - i; ++j){
			bool flag = true;
			if(a[j] > a[j + 1]){	//判断是否交换
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
				flag = false;
			}
			if(flag)	break;	//没有交换可以直接返回
		}
	}
	for(int i = 0; i < 5; i++)	printf("%d ", a[i]);
	return 0;
}

注意：冒泡排序可以根据交换与否提前跳出，如果基本有序执行很快。

🔧1.3.3 二维数组

二维数组其实是一维数组的延伸和扩展
基本结构：数据类型 数组名[第一维大小][第二维大小]
对数据的访问类似于一维数组：数组名 [下标1][下标2]
二维数组的存储结构如图所示：

特别注意序号是从0开始的，并且达不到size！！！！
初始化的方式:

int a[5][5] = {{1 ,2 , 3, 4, 5}, {1 ,2 , 3, 4, 5}, {1 ,2 , 3, 4, 5}, {1 ,2 , 3, 4, 5}};

人类的本质就是套娃，多维数组也是一样0.0
举个栗子🌰

#include<stdio.h>
int a[10000][10000];
int main(){
	for(int i = 0;i < 10000;i++)
		for(int j = 0;j < 10000;j++)
			scanf("%d",&a[i][j]);
	for(int i = 0;i < 10000;i++)
		for(int j = 0;j < 10000;j++)
			printf("%d\n",a[i][j]);
	return 0;
}

结果就是读入一堆数字然后再把它打印出来。
特别注意，上面的🌰中将数组定义在函数外其实是定义在了堆内存上，放置栈溢出。(又突然听不懂了是不是？没关系，记住数组大于10⁶就定义在函数体外就好了，剩余的回头再学)

?1.3.4memset函数

如果需要对一个数组中每个元素进行赋值，可以使用memset函数；
基本格式：memset(数组名, 值, sizeof(数组名));
其中sizeof返回的事对应的数组的大小。单位是字节。
注意：

1. 此函数只适用于赋全0或者全1，因为传入参数字节，这个函数按照字节赋值的，如果int是长度是4，赋值2就会出问题！！！！
2. 使用此函数务必包含string.h函数！！！

举个栗子

#include<cstdio>
#include<cstring>//cpp里cstring 和 string.h一样
int main(){
	int a[5] = { 1, 2, 3, 4, 5};
	memset(a, 0, sizeof(a));
	for(int i = 0; i < 5; i++)	printf("%d ", a[i]);
	printf("\n");
	memset(a, -1, sizeof(a));
	for(int i = 0; i < 5; i++)	printf("%d ", a[i]);
	printf("\n");
	return 0;
}

🔨1.3.5 字符数组

其实字符本质上也是数字0.0，你说你不信？我给你康康！
看法很简单就是从上到下依次增加，一共127个数字。对应1比特的6个1，也就是char的正数部分。
没事可以翻回来看看这个表，需要记住的昨天说了，就是小写比大写大32。

1.字符数组的初始化

字符数组的初始化有两种方式:

char s[6] = {'a', 'e', 'i', 'o', 'u'};
char s[6] = "aeiou";

其中第二种方式只用于初始化，在程序执行过程中如果这么干会直接报错！！
注意字符串末尾有一个'\0‘作为结束标志，所以开数组要大一个位置！

2.字符数组的输入输出

scanf和printf这个昨天说过了，今天不提了 主要就是利用%s
但是注意scanf读取字符串是以空格和回车作为结束的，这两个元素不可能读入到字符串内

---

getchar 和 putchar昨天也说过了。这里需要注意的是:
getchar不会给字符串加结束符，需要手动加，并且getchar能读到回车

---

gets()和puts()
gets用于读入一整行的数据。但是这个在C11中弃用了。。。因为安全问题
有些OJ还能使用，用法就是gets(s)。
需要注意的是：
scanf读入数据后会把相应的结束标志留在标准输入输出上，所以使用gets之前如果使用了scanf需要用一个getchar吸收掉回车！！！

---

puts()相比较而言就简单很多。
作用就是把字符串打印到屏幕上并加上一个换行符。
一个常用的方式是puts("")可以打印一个换行，是不是很方便？

---

gets_s()
因为刚才说到的原因gets弃用了。。。多说个函数就是gets_s
用法gets_s(str,strlen);
参数就多了一个就是strlen ，这个函数读到长度后就不会再读，防止读爆字符串产生安全问题0.0

---

但是ges_s()这个东西在c++里没有 所以我们要引入另外一个神器
cin.getline(str,strlen);，用法和gets_s一样 但是别忘了 #include<iostream>和using namespace std;

🔩1.3.6 string.h头文件

之前介绍了memset，我们再来扒一扒这个头文件有什么好用的函数。

最后的sscanf和sprintf是不是有亿点点熟悉？其实我们平常用到的scanf和printf都是这两个的变体!!

知识点到这里就结束了，大家要好好做题巩固呀，有什么问题大家评论区见0.0
让我们相约明天

🐳课后习题

今天的题目难度也不高，就是有点多，我写完会放题解，大家写完了可以在评论区打卡哟！我觉得，题解我放评论区吧，这样不用修改文章。

题解：评论区见，置顶没有就是我没写完0.0，大佬们刷完打个卡呀