Gauss Zhou

Appearance

第六章 与数据结构成为好朋友 ​

栈和队列的区别是什么

栈中数据的存取是 LIFO 后进先出；队列中数据的存取方式是 FIFO 先进先出；

程序员有必要把算法（处理问题的步骤）和数据结构（作为处理对象的数据的排列方式）两者放到一起考虑。

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

计算机所处理的数据都存储在被称为内存的集成电路中。在一般的个人计算机中，内存内部被分为若干个数据存储单元，每个单元可以存储 8 比特数据，每个单元都又被分配一个编号，这个编号被称为“地址”。

因为依靠指定地址的方式编写程序很麻烦，所以在几乎所有的编程语言中，都是使用变量把数据存储进内存，或从内存中把数据读出来的，不需要知道数据具体被存储在那个地址上。

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

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

数组是数据结构的基础，之所以这么说是因为数组反应了内存的物理结构本身。在内存中存储数据的空间是连续分布的。而在程序中往往要从内存整体中分配出一块连续的空间以供使用。

6.3 要点 3：了解数组的应用 ​

数组是数据结构的基础，只要数组就能通过程序实现各种各样的算法以处理大量的数据。

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

数组是一种直接利用内存物理结构的最基本的数据结构。但是在现实世界中一些数据结构，仅凭借数组是无法实现的。比如有的数据可以堆积的像小山一样，有的数据结构可以把数据排成一队，有的数据结构可以任意的改变数据的排列顺序等。

“栈”的本意是干草堆。在牧场中，把喂家畜吃的干草堆积在地上就会形成一座小山。而在给家畜喂食的时候，则要按照从上往下的顺序堆积起来的干草取下来。

“队列”就是等待某事而排成的队。比如地铁排队队列，队列与栈正相反，排在队头的乘客可以最先买到车票。

“链表”的概念就相当于几个人手拉着手排成一排。某个人只要松开拉住的那只手，再去拉住另一只手，这一排人的排列顺序就改变了。

“二叉树”的改变正如其名，就相当于一棵树。不过这棵树与自然界中的树稍有些不同，二叉树从树干开始分叉，树杈上又有分叉，但每次都只会分为两杈。

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

c
/* 作为栈本质的数组 */
char Stack[100];
/* 栈顶指针 */
char StackPointer = 0;
/* 入栈函数 */
void Push(char Data){
  /* 把数据存储到栈顶指针所指的位置上 */
  Stack[StackPointer] = Data;
  /* 更新栈顶指针的值 */
  StackPointer++;
  }
  /* 出栈函数 */
  char Pop(){
  /* 更新栈顶指针的值 */
  StackPointer--;
  /* 把数据从栈顶指针所指的位置中取出来 */
  return Stack[StackPointer];
}
c
/* 作为队列本质的数组 */
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 语言程序实现链表和二叉树的方法，就必须先了解何谓“结构体”。所谓结构体，就是把若干个数据项汇集到一处并赋予其名字后所形成的一个整体。

c
struct TestResult{
  char Chinese; /* 语文成绩 */
  char Math; /* 数学成绩 */
  char English; /* 英语成绩 */
};
struct TestResult xiaoming; /* 把结构体作为数据类型定义变量 */
xiaoming.Chinese = 80; /* 为成员数据 Chinese 赋值 */
xiaoming.Math = 90; /* 为成员数据 Math 赋值 */
xiaoming.English = 100; /* 为成员数据 English 赋值 */

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

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