[源码分析] 简单说说链表和一个应用实例

辛昕 2014-12-24 22:31 楼主

      主题楼里的内容，不是很切题，扯了很多东西（所以如果喜欢直接看代码和干货的朋友请直接看二楼.......）不过我还是写了个人一些开始使用算法，结构的体会和心得。

      对于算法和数据结构，常常有两种极端看法。    一种是觉得非常高深，难以触及，比如很多的算法书，一开篇就是一堆很复杂的计算分析。而对于毕业很多年的我们，不管你当年高数复变很高分还是和我一样刚刚合格，可能很多人都是很难看懂那些分析。但实际上，对我们中的很多人，我们更多的时候是需要去学习一种已经被设计出来的算法或者数据结构——我们中有多少人是打算去设计算法的呢？如果不是，至少是不是先学会如何在已有的方案里挑选合适的结构，算法，而且还需要稍作修改，以适应在自己面对的问题里使用呢？
      ——比如现在提到的链表，他的“标准”实现就是需要 malloc/free的，但在单片机，尤其是裸机程序中，我们通常被告诫尽量不要使用malloc/free函数，所以，我们需要另一种折中方案，用一个静态数组作为空间，然后通过对数组下标的计算操作模拟 malloc/free这对动态分配函数。一般这种方案被称为游标实现。除了需要预先预留一个足够大的数组以外，它的使用和语境，和标准链表实现完全一模一样——我的意思是，你可以通过只改写这两个函数，然后直接套在原来的链表API里就可以了。

      另一种，是觉得某些基础结构很简单，实现起来又麻烦，干脆就不用了。比如三种最基础的数据结构，链表队列栈。它们的概念确实非常简单，但是实际上，如果我们真的完全理解了它的用途，并妥善使用，那其实还是会发现它们虽然简单，却威力无比。
      但从我们看到的一些实现，我们经常会发现，他们对这些数据结构的理解，其实是有偏差的，甚至有的基本都错了。

      比如我自己，我第一个真正开始大量使用数据结构是队列，我把它用在串口接收上。但直到我对着书去写，我才发现我以前从来没有理解队列的本质特点就是通过移动头和尾来避免直接移动数据本身，以保证它的操作时间可以被控制在一定的范围内（数学不好）。

   另外一点要强调的是，即使是同一个结构，算法，不同的人都会有不同的出发点和定义的方式。
   而我个人对此的态度是，我会选择一个大家比较公认而且我自己也觉得挺不错的定义，然后尽全力去试图理解他的出发点，把并按它的定义严格完成实现。由于选择看书的原因，我看的是 Mark Allen Weiss(以后简称 M.A.K)的 C语言描述这本书，我觉得他的定义和（部分）实现都相当的标准的感觉，而且在我几经使用后都发现他的定义确实很有道理，所以基本上都以他的定义为实现版本。

强者为尊，弱者，死无葬身之地

回复评论（22）

2推荐辛昕

简单解释一下前驱元这个概念，它来自于中译本。意思是指上一个元素。简单的说如果装着X的表元的Next指向装着Y的表元的地址，那么，我们就称表元 Y的前驱元是 X

/*
这是一个可以使用标准 malloc/free的版本
*/
struct node;
typedef struct node Node;
typedef Node *pNode;
typedef pNode List;
typedef pNode Position;
typedef char ElementType ;
// 判断链表是否空
int IsEmpty(List L);
// 判断是否表尾
int IsLast(Position P,List L);
// 寻找链表中是否有某个元素，并返回其位置
Position Find(ElementType X,List L);
// 寻找元素的前驱元：删除函数用
Position FindPrevious(ElementType X,List L);
// 删除链表中某个元素
void Delete(ElementType X,List L);
// 在某个位置插入元素X
void Insert(ElementType X,List L,Position P);
// 删除链表
void DeleteList(List L);
// 获得链表头位置
Position Header(List L);
// 获取链表首元素
Position First(List L);
// ？？
Position Advance(Position P);
// 检索位置P的元素
ElementType Retrieve(Position P);
struct node
{
ElementType Element;
Position Next;
};
// 面向调用者，可能需要增加的API
/*
MakeEmpty()在书里没看到实现，下了答案也没有找到。依我网上看到的理解，这个相当于
创建链表的API。所以我干脆换个更直接的名字 CreateList;
*/
// 创建链表
List CreateList(void);

本帖最后由辛昕于 2014-12-24 23:39 编辑

强者为尊，弱者，死无葬身之地

点赞 2014-12-24 23:33

沙发辛昕

现在说点实在的。

链表的概念很简单。
但为了更好地说明它，我觉得以普通数组来对比是一种不错的方式。

普通数组，是一组相同元素（比如char int 或者 double型数据）的连续排列，它们在内存上是连续分布的，我们可以直接通过 0，1，2，3.....去访问它的每个元素，专业的术语叫遍历。

链表其实是从属于表这个概念之下的一个子概念。
表代表的是一组元素以一种特定顺序排列起来的集合。

我们会发现，普通数组是表的一种最直观的表达。

但是，实际使用中，在某些情况下，我们会发现，普通数组有很多的缺陷：

举个例子，如果我们要在一个表中某个位置插入一个新的元素，我们就必须移动这个位置后面的所有元素，往后挪一个位置，然后才能放下新元素。

可以理解，这是一种很花时间的操作。

链表提供了一种解决这个问题的思路；
那就是表元不连续排列，而是通过一个附带单元，记录下一个表元的位置。因此我们在插入新表元的时候，只需要交换一下指针，就可以完成插入动作。

是的，链表的想法就是这么简单（它的实现也非常简单，居然不到100行）。

我真正把链表用到单片机上，是在做多级菜单的时候，但因为此前的实现受制于时间和原有项目的遗留代码影响，我在做的时候未能果断的采取链表。
——这两天终于发现为了增加一些新特性，最终我还是要用链表实现一次。

所以暂时，就不把这个实际例子贴上来（但随后，这个实现我要用在手机DIY的 12864实现界面上，届时我会单独开一个帖子把它的完整方案写个应用笔记。）

这里，我采用一个相对简单的类似于服务器/客户机带连接通信时，服务器维护链接列表的简单例子，作为实例说明。

完整的应用情形以及链表实现均见下面的帖子。

强者为尊，弱者，死无葬身之地

点赞 2014-12-24 22:44

板凳辛昕

链表应用实例之主机维护链接方列表虽然我曾经在PC机上写过一个简单的 socket套接字程序，利用多线程实现一个服务器响应多个客户端请求连接，当时做的是 tcp套接字，是带链接的。但是，当时因为只是个小示例程序，而当时的我也远没能理解到链表的用途。所以当时我并没意识到这个地方是一个使用链表的最简单例子。直到后来我在做CC2530透传时。当时我们是买了现成的zigbee透传模块。并不需要我自己做。测试我们是这样做的，一个主节点链接多个从节点，并随意断开连接的节点，再随意建立新链接的时候，我们发现采购的模块有一些奇怪的表现： 1.主机A 与从节点 a b c d依次建立了链接，然后断开 b，再试图连接b,却发现无法链接。 2.但如果是断开d，再链接d却是可以的； 3.还有更奇葩的。如果断开了c，想再链接c当然还是不行，但假如再断开d，然后先连d,再连c,却是可以的。我们的同事与厂方打电话沟通，得到的却是语焉不详的解释，以及后来这些模块我们没有采用......这些事情就都是后话了。但我当时的直觉就是，因为他没有采用合理的方式来维护链接的节点地址（维护就是，当建立连接的时候，要记录链接产生的地址，撤销时，要双方同时撤销，并遗弃原地址。双方有一方遗漏，都无法再次进行连接）。它肯定是用了某种很蹩脚的，或者使用了普通数组记录标志位的方式查询，然后因没有彻底测试通过，而出现这种奇特的BUG。为了让大家更好理解这个问题，我简单讲一下 CC2530链接的情况。虽然当时我们用的zigbee无线通信，但是就通信方式，其实和标准的 C/S（客户机服务器）模式是一模一样的。因为要建立的是带链接的通信。所以在真正开始传输数据以前先要建立连接——这当然也是通过传输数据，经过确认回复来实现。建立了链接后，建立链接的双方，都会得到同一个编号，这个编号本身是随机的，（当然实际实现中，它表现得就像建立链接的顺序一样）。此后，每一次主从节点通信都通过这个编号，类似于地址一样进行匹配和互相传输数据；同理，不管是主机方还是客户端都可以要求撤销链接。这里我们简单点，以客户端要求撤销为例子。一旦撤销，这个编号将不能再次使用——即使下次再和这个节点连接，产生的编号也不一定就是这个编号，简单的说，这是一个过期地址。现在回到我此前描述的情形。所谓的主机方要维护链接列表，它的实质要求就是。主机方会不断收到突发的客户端要求链接以及撤销链接。而主机方需要动态的维护一张表，以知道它当前有通过什么编号和某个节点保持着链接。第一种方案我们第一反应可以想到一种非常简单的实现方案。我们根据有多少个可能链接的节点建立一个定长数组，每个元素代表与该节点的连接情况，0表示未链接，1表示链接。不管是建立了或者撤销了链接，我们都可以简单的写0写1，而如果是要遍历主机与多少从机建立连接也很简单。只要依次遍历数组，检查哪个位0哪个位1即可。但是很显然，这样的程序是不具有实用性的。首先，可能的节点可能非常多，比如上万个十万个。（zigbee是不太可能了，但以太网上的服务器却是随随便便都可能的）。但一段时间内建立连接的却可能只有几十个上百个节点。我们不说浪费空间，就说我们要遍历完一次当前建立了多少个节点，都是一件非常耗费时间的事情。其次，在真实的环境里，我们可能会在使用中动态增加或者删除节点，这个时候，就会造成原来的程序无法使用或者冗余，降低效率。可以说，“预先设置一个固定长度“ 这种很简单很美好的想法，通常是没办法直接用在实用程序中的。第二种方案那我们不固定分配，我们只记录已经建立连接的节点编号呢?那我们就会很容易地发现自己面临着我们在介绍链表，用普通数组做对比时的那个情形。在这个应用情境里，我们会遭遇的困境是，我们要删除某个中间的链接，将会带来极其麻烦的和耗时间的后方数据集体向前一个位置的操作...... 所以，很显然，这个情形，使用链表来解决，是最合适的方案。 本帖最后由辛昕于 2014-12-24 23:12 编辑

强者为尊，弱者，死无葬身之地

点赞 2014-12-24 23:03

4楼辛昕

不知道大家写程序的习惯怎样。
假如是我，我会接着先考虑维护这个链接列表，需要一些什么操作（当然，我已经完成了链表的实现）。
然后再回头去具体实现。

考虑到大家和我一样，更想实实在在看到链表的实现，所以这里，在进一步写这个维护链接列表之前，我们先来考虑一下如何实现链表吧。

这里简单概括一下。
这套实现里实际上包含了两种不同形式的链表。
其中一种是我们可以自由使用malloc/free这两个动态分配函数的情形，我们可以称之为标准实现方案。

然后，如前面主题楼里所提到的，为了适应大多数情况下，单片机裸机编程，不适宜大量调用malloc/free——因为没有了系统的内存管理机制，纯粹靠C标准库，很容易造成大量内存碎片，造成无法再分配足够大的连续空间。
所以，在标准实现方案之外，我们会有一个相对作出折中的游标方案。

要注意的是，我们在认真理解了M.A.K的实现思路之后，按照他的原设计，我们将只另外构建用于替代malloc/free行为的游标空间数组和新的一对 alloc/free函数，然后使其能与标准 malloc/free函数提供相同的行为，已达到只需要更改使用这组内存分配函数，就可以使原标准实现变成更加适合单片机裸机程序适用的方案。

强者为尊，弱者，死无葬身之地

点赞 2014-12-24 23:18

5楼辛昕

按照前面说的，我采用的是 M.A.K C语言描述书里的定义来实现的。
书的全名数据结构与算法分析 ——C语言描述

我上传了一本，链接如下：
https://download.eeworld.com.cn/download/%E8%BE%9B%E6%98%95/28395

链表的”标准实现“ 在书中34页，下面贴上我自己实现的源码里的头文件 ——我对它做了一些注释，用以理解和理清每个函数的作用。以确定要实现的内容和范围

强者为尊，弱者，死无葬身之地

点赞 2014-12-24 23:33

7楼辛昕

在我的实现，我发现有某些关于链表的概念，书上没有明确理清，我们在看继续实现代码以前，最后理清一下它 ——当然，在我这来说，他是我在不断实现和使用中慢慢加深了对链表的理解后得到的内容。这里抛砖引玉，先说一说。 1.表头的约定 首先就是，M.A.K的版本中，他使用了空表头这个概念。毋庸置疑，表头表示的是 ”链表开始的地方“或者说”第一个表元“，这两个解释都说的通，而且看起来似乎是一样的，实则它有非常细微的差别。差别就在于，前者并没有强调，链表是从第一个表元开始的，这里的意思是说，前者强调的是，表头仅仅只是链表的开始位置，但这个位置本身并没有存储元素，第一个存储元素的表元在表头的next指针指向的位置；即实际上第二个位置才是存储第一个表元的地方。 M.A.K本人也认为这除了一种理解和处理方式上的选择，是否选择空表头或者表头当第一个表元使用，完全是个人习惯，并没有绝对对错。由于我决定严格按照他的定义实现，所以我采取了第一种解释。表头，指的是链表的开始位置，本身并不存储元素。因此，在这种约定下，我们可以得到一个解释的很好的空表的概念。这个表只有表头，head，但是它本身没有元素，而且它的next指针也暂时指向NULL（即空地址）。所谓空表，就是没有存储任何元素，但本身这个表却是存在的（因为表头承载了它的地址）。在这种情况下，我认为，所谓表头，和表，其实可以等同认为是同一个概念 ——因此你会看到，我在具体的实现中，并没有写 Head()这个函数，因为表头，亦即表，其实是同一个概念，而且它应当是在创建表时，由主调方获得并且保存的。 2.删除表元的约定 在前面的头文件中，我们会看到两个删除动作，一个是Delete,从形参可以看出，它是指删除一个表中的一个表元；另一个是 DeleteList，这个指的是删除表；这里一定要明确，删除表元和删除表当然是两个不同的动作，但是一个很细微的地方是，这两个动作是否会有较差的地方呢？如果我们稍微考虑一下删除表元的极端情形，就是试图对一个空表实行删除表元时，就会发现，如果我们没有事先作出一些强制规定的话，其实是很容易造成在这种情况下，，删除表元，实际上就是删除表的行为的。出于函数的单一性，即一个函数做的事情只是唯一确定的一件事情，所以，这里，既然M.A.K要特别的区分这两个函数，那表示，在他的定义中，删除表元是不应该出现变成删除表这种极端情形的。 ——稍后，我们在参考 M.A.K书中提供的部分函数实现时，我们会发现，这个理解是对的。因此，为了避免这种交叉，我们对删除表元作出的约定就是表头不允许删除。至于删除表这个动作的细微之处，我们稍后会在对实现的链表做测试时，结合实际应用的情形，做一个简单说明；暂时只想到这些，剩下的，在实现的代码中再补充注释。 本帖最后由辛昕于 2014-12-25 00:06 编辑

强者为尊，弱者，死无葬身之地

点赞 2014-12-25 00:00

8楼辛昕

虽然还是有很罗嗦的嫌疑，但是，这次我却觉得是有必要的。
已经零点了，再写下去有点想吐。
为了免得标题党，我还是决定把实现代码贴上来。
其实已经实现好了，唯一的问题是残留了很多我当时的注释，这些注释应该被简练和增删。

至于一个简单的用于测试函数，明晚继续。
至于前面提到的一个面向实际使用情形的例子。维护链接表，将随后附上（游标方式实现）。

强者为尊，弱者，死无葬身之地

点赞 2014-12-25 00:09

9楼辛昕

/*
这个可以使用标准 malloc/free 函数的链表实现版本；
部分代码来自M.A.K（Mark Allen Weiss)的书上的版本；
其余为自己添补；
这个链表实现，还剩一个问题：删除表的动作；看起来，我要理解的问题在于：
为什么无法置NULL；
这个问题先放下；
下一步在此基础上，实现游标实现，适应不能自由使用malloc/free的场合；
*/
#include "List.h"
#include <stdlib.h>
// M.A.K
int IsEmpty(List L)
{
return (L->Next == NULL);
}
/* 在 M.A.K基础上，加入L非NULL的检查，这是安全起见
在这种防范之下，只需保证当前P的Next即可
*/
Position FindPrevious(ElementType X,List L)
{
Position P;
if(L == NULL)
return NULL;
P = L;
while( (P->Next != NULL) && (P ->Next->Element != X) )
P = P->Next;
return P;
}
//-----------------------------------------------------------------
/*
这个函数，原来属于 MakeEmpty()的实现；
创建包含了分配空表头的空间；
假如分配成功，将获得一个空表头（Next为NULL，Element未定义）
假如分配失败，则直接返回空指针，则该表创建失败不可用；
*/
List CreateList(void)
{
List L;
L = (List)malloc(sizeof(Node)*1);
if(L != NULL)
L->Next = NULL;
return L;
}
/*
插入表元
这里有个地方要小心，注意插入表元的顺序；
举例
H
H 4
H 4 6
我希望插入是往后走，而不是
H 6 4 这样只是这样操作起来不太好操作；
这不是这个函数的问题，只因我不指定特定位置，只因我从L位置插入；
这里没太大问题，因为无论如何，它至少不会把头给冲掉了；
*/
void Insert(ElementType X,List L,Position P)
{
Position Temp;
Temp = (List)malloc(sizeof(Node)*1);
if(Temp == NULL)
return;
Temp->Element = X;
Temp->Next = P->Next;
P->Next = Temp;
}
// M.A.K
int IsLast(Position P,List L)
{
return (P->Next == NULL);
}
/*
M.A.K
前驱元的有效性来自于 FindPrevious()的保证；
*/
void Delete(ElementType X,List L)
{
Position Prev,Temp;
Prev = FindPrevious(X,L);
if(Prev->Next != NULL)
{
Temp = Prev->Next;
Prev->Next = Temp->Next;
free(Temp);
}
}
Position Find(ElementType X,List L)
{
Position P;
P = L->Next;
while( (P != NULL) && (P ->Element != X) )
P = P->Next;
return P;
}
// 这个函数总是要用的；
// 虽说 cursor list无用；
/*
这是M.A.K的实现
这里有一个问题：它从第一个表元开始删除，即，它忽略了表头；
这也不怪它，因为表头或者说L，来自主调方，它也没办法删除；
问题是，如果是这样，那删除表又该怎么判断？
*/
void DeleteList(List L)
{
Position Temp,P;
P = L->Next;
L->Next = NULL;
while(P != NULL)
{
Temp = P->Next;
free(P);
P = Temp;
}
}
// end of file -------------------------------------------------------------------