数据结构简明入门教程

零、前言

为了弥补教材衔接处的设计问题，特查阅相关资料后书成此文，以助更好地使用教材自学。

为了方便展示，部分代码采用了中文命名的变量名，若需编译，需要使用 C++11 标准的编译器，否则会报错。

一、struct 关键字

struct可以创建结构。

假设我们要创建一个名为“银行存单”的结构，其中包含“金额”、“利率”和“时长”三个信息，我们可以得到下图的结构示意。

结构，图示1.jpg

在 C++ 中，利用struct就可以这么写：

struct 银行存单
{
    double 金额;
    double 利率;
    int    时长;//按月份计算
};

注意，别忘了上面括号结尾后的分号。至于为什么会有分号，会在后面说明。

创建好结构之后，我们便可以使用结构。像定义其他变量一样定义一个银行存单类型变量test。

int alpha; //变量 alpha，类型为“整型（int）”。
银行存单 test; //变量 test，类型为“银行存单”。

我们可以定义一个函数方便对类型进行数据的写入。

void 数据写入(银行存单 &temp)
{
    cout << "存入金额？";
    cin >> temp.金额;
    
    cout << "利率？";
    cin >> temp.利率;
    
    cout << "存入几个月？";
    cin >> temp.时长;
}

这样，一个完整的程序就写好了：

#include<iostream>
using namespace std;

/*
* 定义结构
*/

struct 银行存单
{
    double 金额;
    double 利率;
    int    时长;//按月份计算
};

/*
* 定义写入结构的函数
*/

void 数据写入(银行存单 &temp)
{
    cout << "存入金额？";
    cin >> temp.金额;
    
    cout << "利率？";
    cin >> temp.利率;
    
    cout << "存入几个月？";
    cin >> temp.时长;
}

int main()
{
    银行存单 test; //定义变量
    数据写入(test);//写入变量
    cout << "一共存入" << test.金额 << "元。"; //使用变量
    return 0;
}

一些更方便的写法，你可以定义一个结构类型的函数，并予以赋值：

银行存单 创建存单(double 金额, double 利率, int 时长)
{
    银行存单 temp;
    temp.金额 = 金额;
    temp.利率 = 利率;
    temp.时长 = 时长;
    return temp;
}

这样，可以在声明变量后快速赋值：

银行存单 test = 创建存单(2000, 0.003, 12);

事实上，还有这种赋值方法：

银行存单 test = {2000, 0.003, 12}; //按照顺序

此外，结构还可以套入结构。

例如需要有以下结构层次：

结构，图示2.jpg

我们可以这么写：

struct Date
{
    int year;
    int month;
    int day;
};

struct person
{
    string name;
    char sex;
    Date birthday;
};

让我们回到最开始遗留的一个问题，为什么struct的花括号结尾要多一个分号？这是因为struct支持你在定义好结构后立即创建一个变量，比如：

struct 银行存单
{
    //...
} test1, test2;

但更规范一些的写法，最好是将结构和变量的声明分开来写。

二、typedef 关键字

typedef用于简写或重命名类型。

假如，一个不恰当的例子——你不喜欢“int”这个词，你希望它变为“cafe”，即：

int num; //不喜欢
cafe num; //喜欢

有了typedef，你可以这么做：

typedef int cafe;
cafe num;

同样的，你可以给上文的结构起名。假如我们命名一个结构shopTicket，我们希望 以ST称呼这个结构，我们可以这么做：

typedef shopTicket ST;

或者在定义结构的时候就用上：

typedef struct shopTicket
{
    //...
} ST;

也就是说，下面两段代码等价。

struct shopTicket
{
    //...
};
typedef shopTicket ST;

typedef struct shopTicket
{
    //...
} ST;

我个人觉得，用前一种分开定义的写法更利于阅读。

三、链表

假如存在一种这样的模式：

结构，图示3.jpg

一个结构，包含数据和下一个结构地址的指针，这样构成的就是单链表。为了知道第一个结构的位置，我们还需要一个额外的head指针指向第一个结构。像这样的一个结构，我们称之为节点（list node）。

struct ListNode
{
    int data; //数据
    ListNode *link; //下一个地址的指针
};
typedef ListNode* ListNodePtr; //我们设指向节点的指针类型叫 ListNodePtr。

//Ptr是 pointer 的缩写，即指针。

我们先创建一个指向第一个结构的指针，叫head。

ListNodePtr head;

然后，我们像图里那样，向该结构的数据部分（即data）写入12。

(*head).data = 12;

由于圆点操作符.的优先级高于*，所以我们需要用括号把*head围住。

这样写看起来很麻烦，对吧？在 C++ 中，我们有更好的写法——箭头操作符->。也就是说，上面的语句可以简化为

head->data = 12;

其实这很像自然语言——自head指向的data，值为12。

利用相同的方法，你可以创建多个ListNode类型的变量，逐一连接起来他们。

对于最后一个节点，他的指针应该宣告结束，否则乱指的指针可能会造成灾难性后果。我们通常设置为NULL。

在 C++ 中，NULL等同于0。尽管如此，我们通常还是把结束节点的指针设置为NULL而不是0。NULL意味着链的结束。由于NULL和0的相等，有时候会带来麻烦。在 C++11 中，引入了专门代表空指针的字面量nullptr。可选地，我们可以用这个代替NULL。

四、结语

至此，你已经对数据结构以及链表做了初步的入门，相信接下来你已经可以借助书本学习了。祝你好运。

五、参考资料

1. Walter Savitch 《 C++ 入门经典（第九版）》ISBN 978-7-302-40297-8
2. C typedef | 菜鸟教程