数据结构

学习C语言，是简单的学习了C语言的语法以及简单的算法和程序。C语言是面向过程的语言，所以我们更加专注算法的设计，以及算法在程序上的具体实现。之前，我们没有系统的介绍数据的封装，数据结构让我们系统的了解数据是如何封装和组织的。

首先，我们来考虑这样一个事情，如何利用数据描述一样事物。比如说，在做的各位同学，我们如何把诸位的信息存储到计算机上。一个学生的信息有哪些？学生的姓名，年龄，性别，学号等等。我们使用结构体的形式来封装这些信息，也就是说，自定义一个类型，用这个类型来描述学生。

我们把学生的很多基本信息封装到student这个自定类型里面，使用的时候，只要对学生的信息分别初始化就可以了。

方法一：

方法二：

我们有了学生，就可以组建班级了。

众所周知，班级是由很多学生组成的。描述一个班级的信息，需要包括学生这个类型。

同时，班级内的资源是有限的。首先，教室的空间有限，其次，教室里的桌椅板凳，以及计算机的数目也是有限的。所以，一个班级是有一定的容量的，即多能容纳的学生个数。

因此，我们如下进行定义一个班级：

这个班级多能容纳的学生数目是40，stu_num是用来表示当前这个班级内部学生数目的。

当这个班级增加一个学生，stu_num就会增加一。

我们通过下面的方式定义一个班级

定义班级后，我们要为这个班级的stu_num赋值为0，表示当前班级中的学生数目为0。

我们通过如下方式，向班级中插入学生。

注意，每次插入一个学生，就要为这个班级的stu_num加一。

这个例子为了简要演示插入操作，只向这个班级中插入2个学生。

下面表示了如何输出这个班级中的学生信息：

在屏幕上会打印出这个班级中的学生的信息。

以上的内容是为了说明，在C程序中，我们如何对数据进行封装，来表示我们想要表达的具体含义。

对于结构体的定义，如果你觉得struct这个关键字比较麻烦，可以使用typedef来定义一下这个类型的别名。

上图是未用typedef的方式，student是这个结构体的名字。

上图是使用了typedef的方式，student是我们利用typedef来定义的一个类型别名。我们未对这个结构体定义类型名称，直接使用typedef定义它的别名。

当然，也可以这样做：

这样定义了这个结构体的名字sutdent_def，并且为其定义了一个别名student。后面我们再使用这个结构体的时候，就无需加上struct这个关键字了。这样我们使用起来，比较像C默认的类型。

另一个问题，我们这样去定义class_1，只是定义了一个局部变量。退出这个函数，我们就找不到它了。当然，我们可以定义一个全局变量，但是定义过多的全局变量不是一个好的风格。我们采用在堆上为这个变量分配空间的方法。

我们定义了一个class类型的指针class_1。我们为这个指针在堆上分配空间。

访问结构体成员的过程中，我们需要使用->这个操作符。因为class_1是一个指针。

我们可以用类似这个种模式，去表示一个顺序存储的线性表。

顺序表的定义如下：

数据存储在一个数组中，当前表中的后一个元素下表存储在last这个变量中。

我们编写函数，来实现创建一个空线性表，为表插入一个值，删除一个值，以及判断表的状态等功能。

创建一个空表：

判断表是否为空表：

判断表是否为满表：

清空一个表：

遍历一个表，将其中的元素打印出来：

求一个表的长度（元素个数）：

往一个表中的某一个位置上插入一个元素：

在表中的某一个位置上删除一个元素：

在表中查找一个元素，返回其下标值：

删除表中的所有重复元素：

相比顺序表，链式表在插入和删除操作上有很高的效率。

链式表定义如下：

数据域保存的是一个整型的数字，此外还有个指向下一个节点的指针。

这个结构体定义定义了两个类型，一个是linknode节点类型，一个是linklist节点指针类型。Linklist用来表示指向一个链式表的指针。

创建一个空链表的函数如下：

这个函数返回了创建好的链表的表头节点地址。我们创建的是一个有头链表，空链表的标志是表头节点的下一节点地址为NULL。

然后，我们来判断一下链表是否为空：

判断链表的长度：

遍历链表，打印出链表中每个元素的具体值：

往指定的位置插入一个元素：

指定位置删除一个元素：

删除在链表中存在的元素：

清空一个链表：

将链表元素翻转存储：