上一篇中，我们说到录入的数据需要保存在一个双向链表中，今天我们就来说说这个数据结构该如何实现。
链表
每一种数据结构都有各自的特点。链表的特点是：任意位置的添加和删除速度快，遍历速度快，查询速度慢。
我们选择链表的目的是方便我们随时在任意位置进行增、删、改、查工作。其实一个单项链表就能够满足我们的要求，但为了提高训练难度，我们选择使用双向链表。
双向链表
数据结构设计
#ifndef __LIST_NODE_H__
#define __LIST_NODE_H__
#include "Record.h"
typedef struct _tagListNode
{
Record* _pR;
struct _tagListNode* _pPre;
struct _tagListNode* _pNext;
}ListNode;
ListNode* g_pL;
ListNode* g_pCur;
int g_ListCnt;
void ListsInit();
void ListDestroy();
void ListAdd(Record* pR);
void ListDel(ListNode* pNode);
int ListCnt();
void ListTraverShow();
#endif
这个是我们上一篇中给出的头文件ListNode.h的定义。主要分为三个部分：
- 结构体
结构体ListNode用来定义链表中每个节点，其中，_pPre和_pNext两个ListNode类型指针分别用来指向这个节点的前驱节点和后继节点，_pR用来指向节点中保存的记录内容。
注意：在定义结构体时，两个指针不能使用ListNode这个关键字定义，因为此时这个关键字还没有被定义完成。
- 全局变量
指针g_pL始终用来指向链表的头结点，有了它我们就能够让整个链表随时在掌握中。指针g_pCur指向的是当前节点，其实就是链表的尾节点。每次添加新记录时，我们都在这个指针所指向的节点后面追加一个新节点，把内容保存在这个节点中，之后让这个指针指向这个新节点。
gListCnt用来记录链表中保存了多少条记录。
- 数据结构功能
最下边的这一组函数用来提供各种功能。我们可以通过调用这些函数来完成数据在内存中的存储。
功能实现
接下来我们新建文件ListNode.c来实现链表的各种功能函数。
1. 初始化
为了体现“高内聚，低耦合”的设计思想，我们希望设计出的双向链表只需要调用一个ListInit()就能完成初始化，不需要任何其他数据类型的单独声明。这就要求我们在函数内部完成各个全局变量的管理。
双向链表的初始化实际上是头结点的创建和各个变量的初始化过程。请看下面这个函数：
void ListInit()
{
g_pL = (ListNode*)malloc(sizeof(ListNode));
g_pCur = g_pL;
g_pCur->_pR = NULL;
g_pCur->_pPre = NULL;
g_pCur->_pNext = NULL;
g_ListCnt = 0;
}
这就是初始化函数。首先创建一个结点，用g_pL指针指向它，之后让尾部指针g_pCur也指向这个节点。之后把所有相关的变量全部初始化。是不是很简单呢。
链表的存储空间是由每一个节点来提供的，而每次添加内容时都需要申请一个新节点空间去保存数据。
2. 添加记录
默认的添加方法是在链表尾部增加一个新节点，如下图：
添加节点
过程如下：
- 创建一个新ListNode变量，申请堆空间
- 将新记录数据保存到新ListNode中
- g_pCur的_pNext指针指向新节点
- 新节点的_pPre指针指向g_pCur节点
- g_pCur指针指向新节点
完成这几个动作之后，新加入的节点成为了链表新的尾节点。代码如下：
void ListAdd(Record* pR)
{
g_pCur->_pR = pR;
ListNode* pNode = (ListNode*)malloc(sizeof(ListNode));
g_pCur->_pNext = pNode;
pNode->_pNext = NULL;
pNode->_pPre = g_pCur;
g_pCur = g_pCur->_pNext;
g_pCur->_pR = NULL;
g_pCur->_pNext = NULL;
g_ListCnt++;
}
3. 删除记录
删除节点的动作相对复杂一些，当外部传入某一个节点时，将这个节点从链表中删除。具体操作如下图：
删除节点
如图所示，具体的删除流程如下：
- 找到输入节点的前后节点，由于我们的设计方法，需要考虑删除的是首节点或尾节点的特殊情况。
- 让前面节点的_pNext指针指向后面节点
- 让后面节点的_pPre指针指向前面节点
- 释放需要删除节点的空间
代码如下：
void ListDel(ListNode* pNode)
{
if (g_ListCnt < 1)
{
return;
}
if (pNode->_pPre == NULL)
{
g_pL = g_pL->_pNext;
g_pL->_pPre = NULL;
}
else if (pNode->_pNext == NULL)
{
pNode->_pPre->_pNext = NULL;
}
else
{
pNode->_pPre->_pNext = pNode->_pNext;
pNode->_pNext->_pPre = pNode->_pPre;
}
RecordDestroy(pNode->_pR);
free(pNode);
g_ListCnt--;
}
注意两种特殊情况的处理。
4. 遍历打印
数据都保存进链表之后，我们需要依次把这些内容打印出来。这个功能由两部分组成：
- 遍历链表
- 打印数据
打印数据这部分，我们已经把它封装成一个独立的函数了，在Record.h中声明了。我们只需要实现遍历功能就好。
链表的遍历其实就是让一个ListNode指针从首节点开始依次像后访问每一个节点。代码如下：
void ListTraverShow()
{
ListNode* pNode;
for (pNode = g_pL; pNode->_pR != NULL; pNode = pNode->_pNext)
{
RecordPrint(pNode->_pR);
}
}
创建一个pNode指针，让它从首节点开始依次通过_pNext指向每一个节点，之后通过RecordPrint打印这个节点的内容。
5. 释放
这是最后一个功能了，我们在程序退出前需要手动释放链表中的每一个节点。方法很简单，遍历这个链表，依次释放每一个节点的空间。
void ListDestroy()
{
for (g_pCur = g_pL; g_pCur != NULL;)
{
RecordDestroy(g_pCur->_pR);
g_pL = g_pCur->_pNext;
free(g_pCur);
g_pCur = g_pL;
}
g_ListCnt = 0;
}
现在我们已经实现了一个双向循环链表的基本功能了。下一篇我们开始讨论如何用这个链表为程序提供服务。
留下一个练习题，如何在链表的任意位置添加一个新节点呢？请自己实现一个方法。
我是天花板，让我们一起在软件开发中自我迭代。
如有任何问题，欢迎与我联系。
上一篇：21天C语言代码训练营（第十二天）
下一篇：21天C语言代码训练营（第十四天）
网友评论