《计算机是怎么跑起来的》第六章读后小结

《计算机是怎么跑起来的》第六章读后小结

数据结构

这章讲的是 数据结构

计算机处理的数据都存储在 内存 的集成电路中,内存有多个数据存储单元,每个单元存8比特(8比特 = 1字节),并且每个单元都有唯一的编号,就叫做 地址,相信对指针了解的不会对地址陌生

依靠直接指定内存地址来进行编程太过麻烦,所以几乎所有的编程语言中,都有变量这个概念,它可以用来代替内存地址的名字,看起来更加直观

char a
a = 123

当程序运行时,由操作系统为我们分配没有使用的内存空间给变量,所以变量可以直接读取到地址,并且能使用数据

如果不了解数据结构,那么编程时就只能一个挨一个地定义若干个单独的变量

为什么需要数据结构

举例:把三个数据进行降序

char a, b, c, tmp; 
a = 123; 
b = 124; 
c = 125; 
if (b > a) { 
 tmp = b; 
 b = a;
 a = tmp; 
} 
if (c > a) { 
 tmp = c; 
 c = a; 
 a = tmp; 
} 
if (c > b) { 
 tmp = c; 
 c = b; 
 b = tmp; 
}

这样也能实现,但是,如果数据有一万个呢?那就真的很麻烦了

那么我们就来了解一下 数据结构

数据结构,本质上就是 “把数据怎么摆放、怎么组织、怎么取用” 的方法

可以想一下中药店里的中药柜,每个柜子里都对应一个中药,如果所有中药混在一起,不仅不好找,而且还容易找错

常见的数据结构包含 数组、栈、队列、链表、树、图

数组

数组 是数据结构的基础,像 顺序查找,冒泡排序等等,都是需要数组的

那么什么是数组?可以把他想象成一个排列整齐的电影院的座椅, 优点是找座位非常快,缺点就是如果想在中间塞一把椅子进去,会很麻烦

链表

这时就有了 链表

看链表怎么写

struct TestResult { 
char Chinese;      /* 语文成绩 */ 
char Math;        /* 数学成绩 */ 
char English;      /* 英语成绩 */ 
struct TestResult *Ptr; /* 指向其他元素的指针 */ 
};

不太好理解,看图

在这里,如果我们想要在中间插入元素进去的话,只需要把原本的连接关系改成指向元素 x(也就是你想插入的元素)就可以了 缺点就是查找慢,因为它必须顺着开始元素一个个找下去

栈

接下来是 栈，栈对于数据的存取方式是LIFO（Last In， First Out）先进后出，就像洗盘子，你洗完盘子，一个个往上堆，但你用盘子的时候，肯定不是从下面去抽，而是从上面去拿，

char Stack[100];     /* 作为栈基础的数组 */
char StackPointer = 0;  /* 栈顶指针 */

/* 入栈函数 */
void Push(char Data) {
 /* 把数据存入栈顶指针所指的位置 */
 Stack[StackPointer] = Data;
 /* 更新栈顶指针的值 */
 StackPointer++;
}

/* 出栈函数 */
char Pop() {
 /* 更新栈顶指针的值 */
 StackPointer--;
 /* 把数据从栈顶指针所指的位置取出来 */
 return Stack[StackPointer];
}

它适合做什么呢，像浏览器的撤回、Ctrl+Z、游戏中死了之后读取最后一次的存档

队列

队列，顾名思义，队列对于数据的存取方式是FIFO（First In， First Out），就像排队打饭一样，先到的人先吃

那它适合做什么,像排号系统、打印任务排队这些

树

接下来是 树，树可以分叉，就有了二叉树、三叉树。很简单,理解了链表的话就直接看代码就懂了

struct TestResult { 
char Chinese;      /* 语文成绩 */ 
char Math;        /* 数学成绩 */ 
char English;      /* 英语成绩 */ 
struct TestResult *Ptr1; /* 指向其他元素的指针 */ 
struct TestResult *Ptr2; /* 指向其他元素的指针 */ 

};

那么树适合做什么?像文件夹结构、公司组织图等等,它们都不是随便乱连,而是一层包一层

图

接下来是 图,可以想象一下城市地铁图 (随便截的,将就看一下)

图的核心本质为,我不关注谁是源头,我只关注谁和谁之间有连接关系

为什么数据结构重要

这一章读下来,我感觉数据结构的重要性就在于:它不是单纯在讲“数据有哪些名字”,而是在讲数据应该怎么组织,程序才能更方便地处理它们。如果数据组织得好,查找、插入、删除、排序这些操作都会更顺;如果组织得不好,程序就会越写越麻烦。

从数组、链表、栈、队列,再到树和图,它们其实都在回答同一个问题:面对不同类型的数据和不同的使用场景,我们到底该用什么方式来存放和操作这些数据。

本章小结

这一章让我开始明白,数据结构并不只是几个要背下来的名词,而是编程时组织数据的方法。数组适合快速按位置访问,链表适合插入和调整连接关系,栈和队列强调的是“怎么进、怎么出”,树和图则更适合表示层级关系和连接关系。

如果说前面几章让我知道程序是怎么执行的,那么这一章更像是在告诉我:程序不只是“会跑”就够了,还得考虑数据怎么放,后面才更好处理。这也让我意识到,写程序时不仅要会写语法,还要学会选择合适的数据结构。