我们都知道,数据结构和算法本身解决的是 “快” 和 “省” 的问题,即如何让代码运行得更快,如何让代码更省存储空间。所以,执行效率是算法一个非常重要的考量指标。那如何来衡量你编写的算法代码的执行效率呢?这里就要用到本章要讲的内容:时间、空间复杂度分析。
1. 大O表示法时间复杂度指的就是算法的执行效率,粗略地讲,就是算法代码执行的时间,用时越短效率越高。但是,如何在不运行代码的情况下,用“肉眼”得到一段代码的执行时间呢?
先看一段简单的代码:
123456789void func(int n) { int sum = 0; for (int i=1; i <= n; ++i) { sum = sum + i; } printf("sum = %d\n", sum); }
从 CPU 的角度来看,执行每行代码的操作都类似,虽然执行时间不尽相同,但是可以假设 CPU 执行每行代码的时间都是一个指令周期,这样就可以轻松算出上面代码的执行时间了:
第 3、8 行,分别需 ...
1. 概述1.1 概念数据结构和算法是计算机科学中的一组重要概念。先看一下官方对这两个概念的定义:
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
算法:是指解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个步骤。
为了方便理解,上述概念可以再说的直白一些:
数据结构就是指一组数据的存储方式
算法就是操作数据的一组方法
1.2 为什么要学习数据结构和算法为什么要学习数据结构和算法呢?
想要通关大厂面试,千万别让数据结构和算法拖了后腿
业务开发工程师,不能做一辈子 CRUD(增删改查)
基础架构研发工程师,写出达到开源水平的框架才是目标
对编程还有追求?不想被行业淘汰?那就不要只会写凑合能用的代码
学习数据结构具有多重好处:
提高问题解决能力: 数据结构是组织和存储数据的方式,学习数据结构可以帮助你更好地理解问题的本质,并能够有效地设计和实现解决方案。
提升编程能力: 数据结构是编程的基础,掌握了数据结构可以让你写出更高效、更健壮的代码,提升编程技能和代码质量。
优化算法效率: 数据结构和算法是紧密相关的,选择合适的数据 ...
1. Protobuf 概述protobuf也叫protocol buffer是google 的一种数据交换的格式,它独立于语言,独立于平台。google 提供了多种语言的实现:java、c#、c++、go 和 python 等,每一种实现都包含了相应语言的编译器以及库文件。
由于它是一种二进制的格式,比使用 xml 、json进行数据交换快许多。可以把它用于分布式应用之间的数据通信或者异构环境下的数据交换。作为一种效率和兼容性都很优秀的二进制数据传输格式,可以用于诸如网络传输、配置文件、数据存储等诸多领域。
1.1 源码安装github源代码下载地址:
1https://github.com/protocolbuffers/protobuf/releases
本篇文章中只介绍如何基于Linux完成protbuf的源码安装,基于提供的官方地址大家可以把自己的心仪的源码包下载到本地。接下来介绍安装步骤:
温馨提示:以下按照步骤只适用于 3.21.12 及以下版本,高于该版本的安装方式就不一样了。
123456789# 以 protobuf 3.21.12 为例# 自行下载源码包, ...
1. 文件概述1.1 什么是文件I/O文件 I/O(Input/Output)指的是程序与外部文件之间的数据传输操作。在许多编程语言中,包括C、C++、Python等,都提供了用于进行文件 I/O 操作的内置函数或库。
文件 I/O 操作主要涉及两个方面:读取文件和写入文件。
读取文件:
打开文件:使用文件打开函数(如fopen)打开待读取的文件,指定文件名和打开模式(如只读、读写等)。
读取文件内容:使用文件读取函数(如fread、fgets等)从打开的文件中读取内容,将内容保存到程序中的变量中进行处理。
关闭文件:使用文件关闭函数(如fclose)关闭已打开的文件,释放系统资源。
写入文件:
打开文件:使用文件打开函数(如fopen)打开待写入的文件,指定文件名和打开模式(如只写、追加等)。
写入文件内容:使用文件写入函数(如fwrite、fprintf等)将程序中的数据写入到打开的文件中。
关闭文件:使用文件关闭函数(如fclose)关闭已打开的文件,释放系统资源。
在计算机中,我们最常见的就是磁盘文件,磁盘文件由文件系统 ...
1. 联合体在 C 语言中,联合体又叫共用体(Union)是一种特殊的数据类型,定义联合体的语法如下:
123456union 联合体名 { 成员类型 成员名1; 成员类型 成员名2; ... };
定义联合体变量的语法如下:
1union 联合体名 变量名;
从语法上来看联合体和结构体非常的类似只是将关键字struct替换成了union,但是,二者在使用的时候有很大区别,其特点如下:
联合体的不同成员共享同一块内存,它们的值互相覆盖。
联合体的大小由最大成员的大小确定。
下面是一个示例,展示如何定义联合体并使用联合体变量:
123456789101112131415161718192021222324252627282930313233343536373839404142// 定义一个联合体类型union Data { unsigned char c; unsigned int i; unsigned short s; char str[20];};int main() { ...
1. 结构体的定义和使用在前面的章节中学习了数组,它描述的是一组具有相同类型数据的有序集合,用于处理大量相同类型的数据运算。
有时我们需要将不同类型的数据组合成一个有机的整体,如:一个学生有学号/姓名/性别/年龄/地址等属性。显然单独定义以上变量比较繁琐,数据不便于管理。
C语言中给出了另一种构造数据类型——结构体。
1.1 定义和初始化声明一个结构体类型的语法是:
123456struct 结构体名 { 成员类型 成员名1; 成员类型 成员名2; ... };
结构体类型是一种复合类型,说得更直白一些就是自定义类型,通过上面的语法将结构体类型定义出来之后,就可以基于这种类型定义变量了。
定义结构体变量的语法为:
1struct 结构体名 变量名;
在一个结构体变量内部有若干个成员,访问结构体成员的语法为:
1结构体变量名.成员名
其实,定义结构体变量有三种方式,如下图:
先声明结构体类型,再定义相应的变量
在声明类型的同时定义变量
直接定义结构体类型变量(无类型名)
结构体类型和结构体变量关系:
结构体类型:指定了 ...
1. 内存分区C代码经过预处理、编译、汇编、链接4步后生成一个二进制可执行程序。
在 Linux 下,可以在命令行中通过size命令查看二进制文件(可执行文件、静态库、动态库等)的大小和节(section)信息。
size 命令的基本语法是:
1size [选项] [文件名]
示例使用:
1$ size my_program
上述名为 my_program 的可执行文件的大小信息输出如下:
12text data bss dec hex filename10024 464 24 10512 2900 my_program
text:代码段(可执行文件)或只读数据段(库文件)的大小。
data:已初始化数据段的大小。
bss:未初始化数据段(bss)的大小。
dec:代码段、数据段和bss段的总大小。
hex:十六进制表示的 dec 的大小。
filename:文件的名称。
通过命令输出的信息可以得知,在没有运行程序前,也就是说程序没有加载到内存前,可执行程序内部已经分好3段信息,分别为代码区(text)、数据区(dat ...
1. 变量作用域C 语言中,作用域(Scope)是指程序中变量、函数的可见性和生命周期的范围。作用域规定了在程序中的哪些地方可以访问变量、函数。
C 语言中主要有以下几种作用域:
文件作用域(File Scope):函数之外定义的变量具有文件作用域,也称为全局作用域。在文件的任何地方都可以访问这些变量,直到文件结束。
块作用域(Block Scope):在函数中、循环或复合语句块内部定义的变量具有块作用域,也称为局部作用域。只能在定义它们的块({}之间的一段代码)内部访问。
函数原型作用域(Function Prototype Scope):函数原型中声明的形式参数具有函数原型作用域。它们只在函数原型内部可见,用于声明函数的参数类型。
函数作用域(Function Scope):在早期版本的 C 语言中(如 C89),函数内部定义的变量具有函数作用域。它们只能在定义它们的函数内部访问。但是在较新的 C 语言标准中,函数内部定义的变量具有块作用域。
变量的作用域可以通过声明位置和跨越的区域来确定。一般来说,变量的作用域从声明点开始,直到其所在的块(或函数) ...
1. 字符指针1.1 处理字符串字符指针是指向字符(char)数据类型的指针变量。它们可以用于处理字符串(以 NULL结尾的字符数组)和字符数组,并对其中的字符进行读取、修改和操作。以下是一个示例,展示了字符指针的使用:
123456789101112131415161718192021#include <stdio.h>int main() { char str[] = "Hello, World!"; // 字符数组 char* p = str; // 字符指针指向字符数组的首地址 *p = 'h'; p++; *p = 'a'; // 通过字符指针访问字符数组中的字符 char* ptr = str; while (*ptr != '\0') { printf("%c", *ptr); ptr++; // 指针后移一个位置 } printf ...
函数和指针在 C/C++ 中常常一起使用,指针可以用于传递函数参数、返回函数结果或者作为函数的返回值。这样做可以实现更灵活和高效的程序设计。
下面是一些常见的函数和指针的使用方式:
1. 指针做函数参数1.1 参数为变量可以将指针作为函数的参数,从而在函数内部直接访问并修改指针所指向的变量。这样可以避免在函数调用时进行变量的拷贝,提高程序的运行效率。
需求:编写一个函数实现两个变量之间的值的交换
123456789101112131415161718192021222324252627282930313233#include <stdio.h>void swap1(int x, int y){ int tmp; tmp = x; x = y; y = tmp; printf("x = %d, y = %d\n", x, y);}void swap2(int* x, int* y){ int tmp; tmp = *x; *x = *y; *y = tmp;& ...