本系列收藏夹
爱发电！

结构体

在你愈加深入，尝试去实现一些更复杂功能的时候，你或许会发现，仅仅依靠一两个变量，来描述某一抽象或来描述某一实体是十分困难的。例如对于一个立方体，我们需要描述其长宽高，对于一个圆柱体，我们需要描述其底面半径和高。因此，我们使用结构体来将多个变量“打包”使得其在代码中成为一个整体，供我们使用。

struct 结构名{  
成员类型1 成员名1;  
成员类型2 成员名2;  
}变量名;  

请务必注意最后的分号。
如果我们不希望在定义结构体时声明变量，我们可以省略这个变量名，就像这样。

struct Cube{  
    int length;  
    int width;  
    int height;  
};  

struct Cube CubeObjectA;  

分开进行结构体的定义与结构体对象的定义。在更新的c++规范中，允许你在声明变量的时候无需输入struct，你也可以通过typedef关键字做到这一点。

typedef struct Cube MyCubeClass;  

MyCubeClass CubeObjectA;  

当然，typedef也可以与结构体声明写在一起

typedef struct struct_cube{  
    ...  
}Cube;  

Cube CubeObjectA;  

typedef是一种为变量类型进行“别名”的操作，你可以为任何类型声明typedef，例如

typedef int MyInt;  
typedef unsigned int uint;  

在你声明完一个结构体的变量后，我们需要使用这个变量。例如在Cube结构体中有length、width、height三个变量，或者我们称为三个属性，我们声明了该结构体的变量，或者说对象，CubeObjectA。
在这种操作进行的时候，我们的结构体类似于一种模板，这种模板可以用来表示一个立体方块，那么当我们需要在代码中使用一个立体方块的时候，我们会使用这个模板创造出一个真正的数据“方块”，与模板不同的是模板本身只有一个结构，而这个方块是“对象”拥有自己的数据，这个操作是广义上的“实例化”，而这个模板则是广义上的“类”，我们创建的则是一个“对象”。
为什么说是广义上的，因为“类”本身是C++语言中的一个语法，而其同样是编程中的一类概念，我在另一系列面向对象的程序设计与其在游戏开发中使用 文章中详细探讨过这个概念，我强烈建议你阅读完本篇文章后详细阅读一下这个系列。
回到我们的话题上来，我们拥有了一个对象 CubeObjectA，当然，我们要操作其数据，因此我们需要使用“成员访问运算符 . ”他就像这样

CubeObjectA.length = 100;  
CubeObjectA.width = 50;  
CubeObjectA.height = 10;  
printf("A的体积是 %d",CubeObjectA.length * CubeObjectA.width * CubeObjectA.height);  

共用体

我们使用结构体解决了一个对象需要用多个数据的问题，而共用体则解决了另一个更加冷僻的问题。
当我们需要使用一个数据，但这个数据的“类型”本身会改变的时候，我们需要使用共用体。
其格式与结构体类似，但使用union 取代struct，他就像这样

union Data{  
    int i;  
    unsigned int ui;  
    double lf;  
};  

union Data DataObj;  

在使用时，与结构体不同，共用体的内存是互相重叠的，也就是当你为其中的某个成员赋值时，例如我为DataObj.i赋值时，我实际上做的是将数据以i所表示的int类型格式，存储在DataObj的内存区域中，而我们对结构体做同样的操作时，我们是将数据存在CubeObjectA中为length准备的区域中。
差别在于，当我继续为DataObj.ui赋值的时候，其所写入的内存与i是同样的内存，这个操作因此也改变了DataObj.i所表达的值，当你读取i时，你实际上做的是 “用i所代表的int格式读取ui代表的unsigned int格式存入时候的值”
这在涉及内存操作的时候很有用，你可以很方便的吧一个数据分割成数个小块，通过union与struct的嵌套。

结构体的嵌套

你可以嵌套使用结构体与共用体，你可以将他们直接嵌套在一起，也可以分开声明，然后嵌套。

struct S_A{  
    int a;  
    char b;  
};  
struct S_B{  
    struct S_A sa;  
    char c;  
};  

struct S_B{  
    struct S_A{  
        int a;  
        char b;  
    } sa;  
    char c;  
};  

当你这么做的时候，你需要通过连续的成员访问你来访问内层成员。

S_BObj.sa.a;  

访问B结构体中A结构体的属性a。

类与模板

在C++中，更多的时候你需要使用类来解决上述“结构体”中的我们需要解决的问题，你可以简单的理解为结构体是一种更原始的“类”。
另一方面，你可以使用C++的“模板”技巧来解决参数类型不确定所导致的可能的问题，这两个内容过于重要以至于我会花费相当多的篇幅去讲解，但在这一切之前，我衷心的建议你阅读我的另一系列文章面向对象的程序设计与其在游戏开发中使用 ，来认识面向对象编程。

指针

我们来到了99%初学者最不想面对的一个话题，如果你想正确的认识指针，你需要详细的了解C++的内存机制，但这真的不是“必要”的，但相对的你需要养成良好的指针使用习惯，清楚哪里是“雷区”避免去触碰。
我们先解决第一个问题，什么是指针。
数据，或者说变量是储存于内存之中的，在这里内存就像是一个小区，里面住着居民，而指针在这之中就相当与一个“门牌号”。但与现实生活中相当不同的是，小区的房间都没有门，而程序员是一个合法的杀手，当作为编程者的你，由于使用了错误的“门牌号”访问或修改了这个房间的数据“居民”，那么当你真正需要这个数据的时候就会出现逻辑上的问题，更可怕的是这种错误是完全无法被计算机发现的，你只能单步执行你的代码，监视大量的数据后，来发现某次错误的存取，修正这个错误。
首先，你需要了解和指针相关的两个运算符 取地址：& 和取值：*，其功能和其字面上看起来的一样，取得某个变量的地址，和取得某个地址处的值。
我们都知道在C语言中，值是有其类型的，因此，指针也是有类型的。首先，一个类型为“没有类型”可以被创建为void*，你可以用其来作为一个中间人传递不同的指针类型，并通过类型转换为自己所需要的。而一个拥有类型的如int *则在指向地址的同时，还代表其所包含的是int类型的数据，即他的长度。

安全的使用

比起指针的技巧，安全的使用指针是更加重要的。首先，一个最容易陷入的陷阱是局部变量，还记得作用域章节中的局部变量嘛？这些变量在离开其作用域后就会被“收回”待后来者加以利用，那么在收回之前，我保留这个内存地址的指针，在收回之后的某个节点我对这个指针的值进行了修改，这种操作的后果是什么呢？没有人知道。
另外一方面，指针是允许加减运算的，其作用是“偏移”，例如指针p+3，其作用就相当与arr[3]，p就相当于arr[0]，这就与数组有了相同的问题，越界问题，尤其当你的内存是自行申请、涉及到结构体的时候，这种内存结构相比数组更加复杂。

内存的申请与释放

我们有内存申请与释放机制，虽然你不会用到。他们是malloc和free函数，malloc会返回一个空指针，也就是void*类型的指针，然后我们将其做强制转换，一般是我们的结构体类型。但是请注意我们在未来会使用new和delete功能。

结构体指针

结构体会有多个成员，在结构体形态下，我们使用成员访问运算符. 在指针形态下我们对应的成员访问运算符为箭头->减号和大于号组成的一个很形象的箭头，例如 CubeObjA->length。

链式表

我们学过了线性表，并套用数组直接实现了这个功能，链式表同样是一种表，其由一个个节点构成，每个结点存有数据的同时，记录了其下个结点“地址”，这个地址并不一定是前文中的指针，也有可能是数组的偏移量。这样由一个个节点所链接起来的表，被称作链表。其优点在于拥有极快的插入速度，但对于一个有序序列因为其需要从首个节点开始逐个访问，因此其访问速度没有线性表快。

一个链式表看起来像这样  
Head  
 |  
 v    +-----v    +-----v    +-----> NULL  
|A, Next|  |B，Next|  |C，Next|  

而其在内存中表示，则可能是这样的  

|B，Next|A，Next|C，Next|  

这展示了链式表的一个基本特点，逻辑上相连的元素物理上不是相连的。

链表是由一个个节点构成的，因此我们首先要做的就是实现一个数组链表的节点

struct link_list_node{  
    int data;  
    unsigned short next;  
};  

我们会把数据储存在data中，吧下一个元素的数组下标储存在next，我使用的无符号短类型，其范围是0～65535这足够我们用了。接下来我需要为这个链表申请内存。

struct LinkList{  
    struct link_list_node node[1000];  
    unsigned short head;  
};  

struct LinkList list;  

这是一个由链表结点组成的数组，并维护一个链表。最后我们还需要定义一个空结点，用在储存下标的变量，以表示其后什么也没有。

#define NULL_NODE 1000  

在这之后，我们将通过两个蹩脚的例子来描述链表的细节，这并非我们的最终代码，我只是用其作为一个示例来展示链表的特点与技巧。
在这时，你的程序看上去是这样

#include <cstdio>  
#define NULL_NODE 1000  
#define ARR_SIZE 1000  

struct link_list_node{  
  int data;  
  unsigned short next;  
};  
struct LinkList{  
  struct link_list_node node[ARR_SIZE];  
  unsigned short head;  
};  
int main(){  
  struct LinkList list;  
}  

遵守我们的好习惯，在使用数据之前需要进行初始化，链表是从头开始，环环相扣链接的，从这个角度来思考链表在“刚出生”的状态是什么样的？
首先，我们的链表中什么也没有，所以head指向的应该就是空，也就是我们定义的NULL_NODE。而同时，链表节点也都是散落着的，从原理上考虑，所有链表节点也都没有内容，他们的next指向的也应该是空，这或许要求我们使用一个循环来遍历所有1000个链表节点并为他们赋值。
但是我们也可以吧这项工作交给“增加”并将功能设计为“初始化并增加某个节点”。
在继续思考之前，我需要再次声明，完成一件工作有无数种方法，目前我们作为学习者并不会要求死扣时间，因此我认为你们可以多多尝试不同的方法，了解他们的差异与优缺点。
因此我提出一种解决方案：

• 将node数组划分为两个区域，“已分配”和“未分配”，使用一个额外的变量来表示未分配区的“顶端”
• 增加一个方块时，从未分配区取出一个方块，并配置这个方块
• 删除一个方块，吧最后一个方块存入未分配区，将其数据交给待删除方块
  这实际上是另一种数据结构的缩影，我们将在下篇文章详细讨论的队列与堆栈，现在，你只需要理解提出的解决方案。

为了达到这一点，我们需要一个变量，或者“书挡”来隔开已分配区和未分配区，将它加入LinkList结构体中。

unsigned short empty;  

然后实现初始化

void LinkList_init(&LinkList l){  
  l.head = NULL_NODE;  
  l.empty = 0;  
}  

这时，我们的链表看起来像这样

head -> NULL_NODE  
|////|////|////|  
^未使用  

下面我们的第一个问题，就是需要完成我们的增加，增加以后的链表看起来像这样

head -> A -> NULL_NODE  

|A|////|////  
  ^未使用  

`

对于一个空链表来说，我们的流程是，先修改未使用的第一个节点，然后将其加入到链表，同时将未使用区域后移。

结构体的嵌套

根据我们的想法，代码如下

  l.node[l.empty].data = d;  
  l.node[l.empty].next = NULL_NODE;  
  if(l.head == NULL_NODE)  
    l.head = l.empty;  

你可能感觉有些拗口，我们来一条条看

• 首先，未使用的标记为 empty 而其是结构体的一部分，所以其写作l.empty
• 而对于l.empty节点，在l.node 数组中，因此这个节点的真正表示应为 l.node[l.empty]
• 对于这个节点，其内部有data和next数值
• 加以组合，我们对这个节点的 data 使用 l.node[l.empty].data 来操作，next同理。

另一种情况，链表已经存在，我们向要新的节点连接到链表的末尾。或许你现在在想，把新节点插入到链表之中又怎么样呢？我已经提到过，这并不是真正的代码，而是一个蹩脚的例子。我们会在下一章真正讲解链表的操作时详细描述各种操作。

结构体的遍历

我们所需要的第一个步，就是找到结构体的末尾，他的特征是对于结点 x， x.next = NULL_NODE。
结构体和数组的最大不同，就在于结构体逻辑上相邻的节点并不在物理上相连，例如一个链表看起来是这样：

Head -> A -> B -> C -> D -> NULL_NODE  
这时我们需要一个指针p，从A开始寻找，并根据A 的next信息进入下一个结点，知道完成搜索  

Head -> A -> B  
        ^p  
(p = node[p].next)执行之后，p将指向B，不断重复直到找到末尾  

D -> NULL_NODE  
^p  

在找到P的值以后，我们就可以使用这个P，并加入我们的新节点。

else{  
    unsigned short p = l.head;  

    while(l.node[p].next != NULL_NODE) p = l.node[p].next; //遍历操作  

    l.node[p].next = l.empty;  
  }  

而最后，我们的函数看起来是这样的

bool LinkList_add(LinkList &l, int d){  
  if(l.empty == NULL_NODE) return false;  
  l.node[l.empty].data = d;  
  l.node[l.empty].next = NULL_NODE;  
  if(l.head == NULL_NODE)  
    l.head = l.empty;  
  else{  
    unsigned short p = l.head;  
    while(l.node[p].next != NULL_NODE) p = l.node[p].next;  
    l.node[p].next = l.empty;  
  }  
  l.empty++;  
  return true;  
}  

有头链表

我们在程序中，针对head的情况进行了判断，这并非是特例，我们在很多时候都需要特殊处理head头指针，例如在链表的头部插入与在链表的中间插入、删除链表头节点与删除链表中间节点。
在这种情况下，我们可以使用有头链表，这个链表由一个特殊的不保存数据的头节点，和其后续链表构成，看起来象是这样。

Head -> (头) -> A -> B -> C -> ...  

当使用这种结构时，我们永远操作的是链表中间，将涉及链表起始节点的操作“去耦合化”。

双向链表

在我们完成了添加操作后，我们再考虑删除操作
根据我们的思路，假设有一个这样的链表

                           +---v  
... -> L -> M -> N -> ... |X|Z|Y|///  
            ^删除            ^-+  

根据我们的思路， 我们要移动Y，并使其覆盖M的数据，这时我们需要操作如下

• 找到节点L，L的下个节点修改为N
• 找到节点X，X的下个节点修改Y的目的地，即为当前的M
• 使用Y覆盖M
• 移动未分配区标志，empty --

经过如此分析，我们需要执行两次查找操作，这种时间浪费是灾难性的。
也因此，我们寻求一种可以避免这种查找的方法

我们提出一种解决办法，让每个节点储存其下个节点的同时，也储存其上个节点的位置，这样再涉及其前一节点的操作时，不再需要搜索，直接就可以找到。

空间代替时间

不管是哪种链表，都使用了空间代替时间的方法，这也是非常常见的一种优化算法时间的方法，其代价则是占用更多的内存。这并非是简单的不选大的怎么赢，而是需要预先对目标进行分析，设计需要的功能，针对这些功能选择合适的链表。

快速排序

我们上篇文章提到了快速排序，我们会在这篇文章中解决它。
快速排序非常常用的一种不稳定排序方法，被称作排序界之光（我口胡的），其是基于排序界之耻冒泡排序的一种优化方案，他思路如下

• 选择一个标志量，将比其小的放在其左边，大的放在右边
• 完成一趟排序之后，对其左右分别执行快速排序

而我们要写成程序，需要根据这个思路设定流程

• 我们需要三个变量 i ，j 为待排区域的上下界， k为标志量，即a[i]
• j向下逼近，直到遇见第一个比k小的值，将其赋给a[i]
• i向上逼近，直到遇见第一个比k大的值，将其赋给a[j]
• 交替执行步骤2、3 直到 i与j相遇
• 递归执行 1-4步

你可以根据这个步骤尝试撰写代码，并使用我们上一篇文章的测试函数测试一下

void sort(unsigned short *a, int left, int right){  
  if(left >= right) return; //如果待排区域仅有一个元素，则停止递归  

  int i = left, j = right, k = a[left];  
  bool way = true; //交替执行 i、j  
  while(i < j){ //循环直到i、j相遇  
    if(way){  
      j--; //j从后向前逼近, 当前数的下一个开始，因为当前数总是i判断后交换过来的数字  
      if(a[j] < k){  
        a[i] = a[j];  
        way = false;  
      }  
    }else{  
      i++; //同理i处总是从j交换过来的数字，因此从下一个开始  
      if(a[i] > k){  
        a[j] = a[i];  
        way = true;        
      }  
    }  
  }  
  a[i] = k;  
  sort(a, left, i); //分别对左右两边继续进行排序  
  sort(a, i+1, right);  
}  

相比于前文中的种种初等排序，快排最为高级排序其程序要长许多，也更为复杂，但是对其进行10000个数字排序的时间甚至低于之前的希尔排序

性能分析

你可以发现，其每次进入递归都会将区域两等分，因此其等分步骤共有 logN（以二为底） 这样整个算法的最好和平均时间降低到了O(N * logN)，而最坏的情况，每次选取的都是最大/最小值，相当于一个冒泡排序 O(n ^ 2)。为了解决这种最坏情况，可以不使用首数字来进行排序，对数据进行建模以后，选取一个特定值作为分隔依据。