标签：存储变量 Chapter6 char 数组要点数据结构数据 TestResult

热身问答

程序中的变量是指什么？
- 变量是数据的容器。
- 变量中所存储的数据是可以改变的。变量的实质是按照变量所存储数据的大小被分配到的一块内存空间。
把若干个数据沿直线排列起来的数据结构叫做什么？
- 数组 array
- 使用了数组就可以高效地处理大量的数据。数组的实质是连续分配的一块特定大小的内存空间
栈和队列的区别是什么？
- 栈是先进后出FILO、队列是先进先出FIFO
- 栈中数据的存取形式是 LIFO ；队列中数据的存取形式是 FIFO。
- LIFO（Last In First Out，后进先出）表示优先读取后存入的数据； FIFO（First In First Out，先进先出）表示优先读取先存入的数据。

6.1 要点 1：了解内存和变量的关系

计算机处理的数据都存储在了被称为内存的集成电路(IC Integrated Circuit)中。在一般的个人计算机中，内存内部被分割成了若干个数据存储单元，每个单元可以存储 8 比特的数据（8 比特 = 1 字节）。为了区分各个单元，每个单元都被分配了一个编号，这个编号被称为“地址”或是“门牌号码”。如果一台个人计算机装配有 64M 字节的内存，那么就会有从 0 到 64M（M = 100 万）这么多个地址

虽然内存中有地址，但是依靠指定地址的方式编写程序依然很麻烦，所以我们通常使用变量把数据存储进内存或者读取出来。

把123存入变量a：

char a;   /* 定义变量 */
a = 123;  /* 把数据存入变量 */

为什么这样就可以把123存储进内存呢？

char代表C语言的数据类型， 用于存储1字节的整数。而这一行代码的作用就是在内存中预留了一块空间，并且给这块空间起名为“a”
- 注意：我们不需要知道变量a被存储到内存空间的哪个地址上了。是由操作系统为我们从尚未使用的内通常存空间中划分出一部分分配给变量 a 的。

6.2 要点 2：了解作为数据结构基础的数组

上面我们离散地存储了变量a，使用了一行代码。如果我们想要处理1000个数据，就要定义1000个变量吗？这有一些麻烦了。所以我们可以使用“数组”，使得我们可以同时定义出多个变量。

使用含有3个元素的数组：

char x[3];  /* 定义数组 */
x[0] = 123; /* 把数据存入数组的第 0 个元素中 */
x[1] = 124; /* 把数据存入数组的第 1 个元素中 */
x[2] = 125; /* 把数据存入数组的第 2 个元素中 */

数组实际上是为了存储多个数据而在内存上集中分配出的一块内存空间，并且为这块空间整体赋予了一个名字.

在这里就是通过定义数组，操作系统就分配出了一块用于存储 3 个数据所需的内存空间，并将这块空间整体命名为 x。其中每个元素的内存空间可以通过 x[0]、x[1]、x[2] 的方式进行访问。虽然本质上还是定义出了 x[0]、x[1]、x[2] 三个变量，但是比起单独使用 a、b、c，使用数组可以更加高效地编写出能够实现排序等算法的程序。

数组是数据结构的基础，之所以这么说是因为数组反映了内存的物理结构本身。在内存中存储数据的空间是连续分布的。

6.3 要点 3：了解数组的应用——作为典型算法的数据结构

通过数组我们可以实现各种各样的算法以及结构，下面我们利用数组实现“线性搜索”，从数组 x 所存储的 1000个数字中查找（Search）777 这个数字。

使用线性搜索算法查找数据:

for (i = 0; i < 1000; i++){
    if (x[i] == 777){
        printf(" 找到 777 了！ ");
    }
}

for语句：反复执行某种处理的功能
{}: 表示程序中的程序块

通常把像变量 i 这样的用于记录循环次数的变量称为循环计数器（Loop Counter）。数组之所以方便，就是因为可以把循环计数器的值与数组的索引对应起来使用

冒泡排序可以将存储在数组中的1000个数字按降序排列，在冒泡排序算法中，需要从头到尾地比较数组中每对儿相邻的元素的数值，然后反复交换较大的数值和较小的数值的位置。

通过冒泡排序算法排列数据：

for (i = 999; i > 0; i--){
    for (j = 0; j < i; j++){
        if (x[i] > x[j]){
            tmp = x[i];
            x[i] = x[j];
            x[j] = tmp;
        }
    }
}

6.4 要点 4：了解并掌握典型数据结构的类型和概念

数组是一种直接利用内存物理结构（计算机的特性）的最基本的数据结构, 所以我们只需要使用for语句，就可以连续地处理数组中所存储的数据，然后实现各种各样的算法。

但是我们还有更多不一样的需求，有时候我们想把数据堆积像小山一样，或者排成一队，甚至分成两路排列, 这个时候我们就需要通过程序从逻辑上改变内存的物理结构，也就是数据在内存上呈现出的连续分布状态去实现如下这些数据结构。（通过数组去实现更多数据结构）

栈/Stack： LIFO（Last In First Out，后进先出），即最后被存入的数据是最先被处理的
队列/Queue：是等待做某事而排成的队。队列与栈正相反，属于FIFO（First In First Out，先进先出），即最先被存入的数据也是最先被处理的。
链表/LinkedList：就相当于几个人手拉着手排成一排。某个人只要松开拉住的那只手，再去拉住另一只手，这一排人（相当于数据）的排列顺序就改变了[删除操作]。而只要先松开拉住的手，再让一个新人加入进来并拉住他的手，就相当于完成了数据的插入操作。
二叉树/Binary Tree: 二叉树从树干开始分杈，树枝上又有分杈，但每次都只会分为两杈，在每个分杈点上有一片叶子（相当于数据）。二叉树其实是链表的特殊形态。

6.5 要点 5：了解栈和队列的实现方法

栈和队列的相似点在于，它们都可以把不能立刻处理的数据暂时存储起来；不同点在于，栈对所存储数据的存取方式是 LIFO 的，而队列对所存储数据的存取方式是 FIFO 的。

那么，如何实现这两种数据结构呢？利用数组。

实现栈：

使用数组、栈顶指针、入栈函数和出栈函数实现栈:

Push：用于把数据存入到栈中，也叫作压入到栈中
Pop：用于从栈中把数据取出来，也叫作从栈中弹出来。

char Stack[100];        /* 作为栈本质的数组 */ //此数组中所包含的元素个数就是栈的大小（栈中最多能存放多少个数据）
char StackPointer = 0;  /* 栈顶指针 指向存储在栈中最顶端的数据 */
/* 入栈函数 */
void Push(char Data){
    /* 把数据存储到栈顶指针所指的位置上 */
    Stack[StackPointer] = Data;
    /* 更新栈顶指针的值 */
    StackPointer++;
}
/* 出栈函数 */
char Pop(){
    /* 更新栈顶指针的值 */
    StackPointer--;
    /* 把数据从栈顶指针所指的位置中取出来 */
    return Stack[StackPointer];
}

实现队列：

一个任意大小的数组
一个用于存放排在队头的数据对应的索引的变量
一个用于存放排在队尾的数据对应的索引的变量
一对函数，分别用于把数据存入到队列中和从队列中把数据取出来。如果数据一直存放到了数组的末尾，那么下一个存储位置就会折回到数组的开头。这样就相当于数组的末尾就和它的开头连接上了，于是虽然数组的物理结构是“直线”，但是其逻辑结构已经变成“圆环”了

使用一个数组、两个变量和两个函数实现队列:

char Queue[100];        /* 作为队列本质的数组 */
char SetIndex = 0;      /* 标识数据存储位置的索引 */
char GetIndex = 0;      /* 标识数据读取位置的索引 */
/* 存储数据的函数 */
void Set(char Data){
    /* 存入数据 */
    Queue[SetIndex] = Data;
    /* 更新标识数据存储位置的索引 */
    SetIndex++;
    /* 如果已到达数组的末尾则折回到开头 */
    if (SetIndex >= 100){
        SetIndex = 0;
    }
}
/* 读取数据的函数 */
char Get(){
    char Data;
    /* 读出数据 */
    Data = Queue[GetIndex];
    /* 更新标识数据读取位置的索引 */
    GetIndex++;
    /* 如果已到达数组的末尾则折回到开头 */
    if (GetIndex >= 100){
        GetIndex = 0;
    }
    /* 返回读出的数据 */
    return Data;
}

6.6 要点 6：了解结构体的组成

在C语言中实现链表和二叉树之前，我们需要先了解结构体。

结构体，就是把若干个数据项汇集到一处并赋予其名字后所形成的一个整体。例如，可以把学生的语文、数学、英语的考试成绩汇集起来，做成一个叫作 TestResult 的结构体，如下

结构体汇集了若干个数据项:

struct TestResult{//定义了一个叫作 TestResult 的结构体
    char Chinese;   /* 语文成绩 */
    char Math;      /* 数学成绩 */
    char English;   /* 英语成绩 */
};

struct: 结构体的标签

一旦定义完结构体，就可以把结构体当作是一种数据类型，用它来定义变量。

如果把结构体 TestResult 用作数据类型并定义出了一个名为 xiaoming 的变量（代表小明的成绩），那么在内存上就相应地分配出了一块空间，这块空间由用于存储 Chinese、Math、English 这三个成员（Member）数据所需的空间汇集而来。被汇集到结构体中的每个数据项都被称作“结构体的成员”。在为结构体的成员赋值或是读取成员的值时，可以使用形如 xiaoming.Chinese（表示小明的语文成绩）的表达式，即以“.”分割变量和结构体的成员

struct TestResult xiaoming;  /* 把结构体作为数据类型定义变量 */
xiaoming.Chinese = 80;       /* 为成员数据 Chinese 赋值 */
xiaoming.Math = 90;          /* 为成员数据 Math 赋值 */
xiaoming.English = 100;      /* 为成员数据 English 赋值 */

6.7 要点 7：了解链表和二叉树的实现方法

这里我们需要使用结构体的数组实现链表和二叉树。

实现链表：

因为前面说过，链表中的每个元素都是手拉手的，所以我们为了实现这个不同，新添了一个元素“struct TestResult* Ptr;”
这个Ptr存储了数组中另一个元素的地址，是一个指针。在 C 语言中，把存储着地址的变量称为“指针”。这里的“*”（星号）就是指针的标志。
这种特殊的结构体可以称为“自我引用的结构体”。之所以叫这个名字，是因为在结构体 TestResult 的成员中，含有以 TestResult 的指针为数据类型的成员，这就相当于 TestResult 引用了与自身相同的数据类型。

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

因为 Ptr 中存储的是与下一个数组元素的连接信息，所以只要替换了 Ptr 的值，就可以对数组中的元素排序，使元素的排列顺序不同于其在内存上的物理排列顺序。

首先，我们来试着把数组中元素 A 的 Ptr 的值改为元素 C 的地址，然后把元素 C 的 Ptr 的值改为元素 B 的地址。通过这样一改，原有的顺序A → B → C 就变成了 A → C → B。

实现二叉树：

实现二叉树也是用自我引用的结构体，并且只要改为要带有两个连接信息的成员的自我引用结构体就可以实现。

带有 2 个链表连接信息的自我引用结构体:

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

二叉树多用于实现那些用于搜索数据的算法，比如“二分查找法”。比起只使用链表，使用二叉树能够更快地找到数据。因为搜索数据时并不是像在简单数组中那样沿一条线搜索，而是寻着二叉树不断生长出来的两根树杈中的某一枝搜索，这样就能更快地找到目标数据了。

标签：存储,变量,Chapter6,char,数组,要点,数据结构,数据,TestResult
From： https://www.cnblogs.com/Natsumeno/p/16967998.html

Chapter6_与数据结构称为好朋友的七个要点