下载掌阅APP，畅读海量书库
立即打开
对于C语言的高阶编程，这里将简明扼要地对相关知识点和数据结构进行介绍，包括C语言的文件操作、排序算法、队列以及链表做基本的程序展示。由于篇幅限制，对于数据结构中的堆、栈、树和图的操作这里不做探讨。如果大家对数据结构很感兴趣，可以继续阅读相关的书籍。理论讲得再好，不如亲自动手实践，让我们开始学习吧。
C语言支持文件的增删改查等各种操作。文件其实就是存储在计算机外部存储区，是系统用来管理数据的一种构造类型。文件根据逻辑结构、存储介质、数据的组织形式分为很多种，按照数据的组织形式可分为文本文件和二进制文件。文本文件中数据是以字符（ASCII码）的形式存储，而二进制文件存储的数据就是0和1。文本文件的优点是存储量大，便于对字符操作，缺点是读写速度慢；二进制文件的优点是占用存储空间小，读写速度快，缺点是不方便人的理解。
在标准C语言中文件操作的常用函数定义在头文件<stdio.h>，如打开文件流的函数fopen()，其函数原型为FILE∗fopen(const char∗filename，const char∗mode)，其他文件操作函数见表3-5。
表3-5 文件操作函数列表
（续）
数据在磁盘上怎么写不是由文件打开方式决定的，而是由写入函数决定的。数据怎么从磁盘上读也不是由文件打开方式决定的，而是由读取函数决定的。上面说的数据怎么写是指，一种类型的变量是怎么存的。比如int 12，可以直接存12的二进制码（4个字节），也可以存字符‘1’和字符‘2’。数据怎么读是指要读一个int变量，是直接读sizeof（int）个字节，还是逐个字符地读，直到读到的字符不是数字字符。
文件操作首先要知道文件的类型，区分是文本文件还是二进制文件，这样在使用具体的读写操作时不容易出现未知错误，如表3-6所示。
表3-6 文件操作方式列表
同一个文件从磁盘读取到内存时，对于文本和二进制两种方式下，内存中的内容一般不相同，这就是两种打开方式的实质性差别。因此建议，以ASCII码字符写入的文本文件，最好以文本方式读；以二进制方式写入的二进制文件，最好以二进制方式读，否则可能会发生错误。
队列，简称队，是一种操作受限的线性表，其限制在表的一端进行插入，另一端进行删除。可进行插入的一端称为队尾（rear），可进行删除的一端称为队头（front）。向队中插入元素叫入队，新元素进入之后就称为新的队尾元素；从队中删除元素叫出队，元素出队后，其后继节点元素就称为新的队头元素。
队列的特点是先进先出，英文简称FIFO，可以和数据结构中的栈结构对比，因为栈结构是先进后出。从队列的存储结构分，队列分为顺序队列和循环队列。队列在内存中存放的方式又分为顺序表和链式队列。
（1）头元初始化队列：InitQueue(Q)
操作前提：Q为未初始化的队列。
操作结果：将Q初始化为一个空队列。
（2）判断队列是否为空：IsEmpty（Q）
操作前提：队列Q已经存在。
操作结果：若队列为空则返回1，否则返回0。
（3）判断队列是否已满：IsFull（Q）
操作前提：队列Q已经存在。
操作结果：若队列为满则返回1，否则返回0。
（4）入队操作：EnterQueue（Q，data）
操作前提：队列Q已经存在。
操作结果：在队列Q的队尾插入data。
（5）出队操作：DeleteQueue（Q，&data）
操作前提：队列Q已经存在且非空。
操作结果：将队列Q的队头元素出队，并使用data带回出队元素的值。
（6）取队首元素：GetHead（Q，&data）
操作前提：队列Q已经存在且非空。
操作结果：若队列为空则返回1，否则返回0。
（7）清空队列：ClearQueue（&Q）
操作前提：队列Q已经存在。
操作结果：将Q置为空队列。
（8）销毁队列：DestoryQueue（&Q）
操作前提：队列Q已经存在。
操作结果：Q队列不存在。
链表就是能够在计算机内存中申请逻辑上连续物理内存不连续的线性表。用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。在编程中，有时想动态申请内存空间，数组满足不了我们要求，原因在于数组是内存地址连续的空间，这时就可以使用链表来满足编程需求。
链表的头节点是人为规定的，头节点就是在链表的第一个节点之前附设一个节点，它没有直接前驱。没有头节点的情况复杂很多，因为要考虑在头节点前或者后插入，而有头节点只用考虑是不是在最后插入。没有头节点，连删除第一个节点都很困难，因为要判断头节点是不是为空。总之，没有头节点要考虑两头的事情，很麻烦，有了头节点只需考虑末尾的事情。
链表分为单链表和双链表，其区别在于节点结构的不同。
单链表的节点结构如下。
双链表的节点结构如下。
在链表中插入节点，要判断插入链表的位置，主要分为在链表表头插入节点、在链表中间位置插入节点以及在链表尾部插入节点。虽然节点插入链表中位置不同，但是插入方法是相通的。插入步骤分为两步，第一步将新节点的尾指针（next）指向插入位置后面的节点，第二步是将插入位置前一个节点的尾指针（next）指向新插入的节点，具体代码如下。
由于链表中的节点在物理内存中是分散存储的，因此在链表中查找指定数据元素，最常用的方法是：从表头依次遍历表中节点，用被查找元素与各节点数据域中存储的数据元素进行比对，直至比对成功或遍历至链表最末端的NULL表示失败，代码如下。
在链表中删除指定数据节点时，实际上就是将这个节点直接去掉，但是直接去掉可能会产生不好的影响，比如这个删掉的节点没有释放内存，并且这个节点还在指向这个链表的某个节点，所以这样的操作是很危险的，需要对删掉的节点进行释放内存操作，具体代码如下。
链表的节点内容修改和链表节点查找相似，因为节点内容的修改是基于查找的基础上找到节点所在位置，然后对其数据域内容进行更新，代码如下。
1）循环链表分为循环单链表和循环双链表，循环单链表中最后一个节点的指针不是NULL，而改为指向头节点，从而整个链表形成一个环。循环单链表中没有指针域为NULL的节点。循环单链表的判空条件不是头节点的指针是否为空，而是它是否等于头指针。在循环双链表L中，当某节点∗p为尾节点时，p->next=L；当循环双链表为空表时，其头节点的prior域和next域都等于NULL。
2）静态链表是借助数组来描述线性表的链式存储结构。节点也有数据域和指针域，但是与之前链表中的指针不同的是，这里的指针是节点的相对地址（数组下标），又称为游标。
排序是在计算机中经常进行的一种操作，简而言之，就是帮助杂乱无章的数据元素回归自己的正确位置。排序算法可以分为内部排序和外部排序，常见的内部排序算法有冒泡排序、快速排序、插入排序、选择排序、希尔排序、归并排序、堆排序和基数排序等。这里我们仅讨论冒泡排序、选择排序以及插入排序的代码实现。
冒泡排序是一种简单的排序算法。这种排序算法重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就交换过来。走访数列的工作是重复地进行直到没有需要交换的元素，也就是说该数列已经排序完成。冒泡算法的名字由来是因为较小的元素经由交换，会慢慢“浮”到数列的顶端，相关代码如下。
选择排序是一种简单直观的排序算法，其工作原理是首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕，相关代码如下。
插入排序算法描述的是一种简单直观的排序算法，其工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，相关代码如下。
通常判断一个算法的好坏取决于时间复杂度、空间复杂度以及稳定性。稳定性指的是如果a原本在b前面，而a=b，排序之后a仍然在b的前面。不稳定的算法表现为：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面。时间复杂度是对排序数据的总的操作次数，反映当n变化时，操作次数呈现什么规律。空间复杂度是算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。