揭开内容无关链表的神秘面纱

当前位置 : 首页 > 网页制作 > CSS > 揭开内容无关链表的神秘面纱

揭开内容无关链表的神秘面纱

来源: 作者: 时间:2016-02-16 10:05
我第一次知道链表这个概念是在数据结构课堂上,当时我们使用的是清华严蔚敏老师主编的《数据结构》教程,那时认为链表节点就是数据+指向其他链表节点的指针,形如:[html] typed

我第一次知道链表这个概念是在数据结构课堂上,当时我们使用的是清华严蔚敏老师主编的《数据结构》教程,那时认为链表节点就是数据+指向其他链表节点的指针,形如:

[] typedef struct tagNode { 
TDataType data; 
struct tagNode *pNext; 
} TNode; 

typedef struct tagNode {
TDataType data;
struct tagNode *pNext;
} TNode;现在想来,那时完全只是停留在书本表面,后来看开源代码(linux,rtems,yaffs),发现链表节点还有可以不带数据的,形如:

[html]  typedef struct tagNode { 
struct tagNode *pNext; 
struct tagNode *pPre; 
} TNode; 

typedef struct tagNode {
struct tagNode *pNext;
struct tagNode *pPre;
} TNode;上述链表节点,不依赖于任何数据,这样的话,不需要针对每一份需要用链表来存储的数据都写一份链表的操作,所有的数据都可以共用同一份链表操作,下面看看这种与数据无关的链表是怎么做到共用的,假设我们有1份数据:

[html]  typedef struct tagData { 
..... 
} TData; 

typedef struct tagData {
.....
} TData;现在我们怎么把这份数据用链表来组织起来呢?

[html]  typedef struct tagLinkData { 
TNode node; 
TData data; 
} TLinkData; 
或 
typedef struct tagLinkData { 
TData data; 
TNode node; 
} TLinkData; 

typedef struct tagLinkData {
TNode node;
TData data;
} TLinkData;

typedef struct tagLinkData {
TData data;
TNode node;
} TLinkData;
通过上述结构将链表节点同所要关心的数据关联起来,链表节点可以放在数据的开头,也可以放在数据的结尾,如上,我一般在使用的时候将其放在数据的开头,因为这样比较方便,下面我就第1种情况讲讲这种与数据无关的链表是怎么使用的。我们知道,链表1般有追加,删除,获取第一个节点等等,下面我就这3个方面介绍其用法:

1.假设链表操作声明如下:

[html]  void append(TNode *pList, const TNode *pNode); 
void delete(TNode *pList, const TNode *pNode); 
const TNode *getFirst(const TNode *pList); 
TNode list; 
2.追加1个TLinkData到list链表中 

void append(TNode *pList, const TNode *pNode);
void delete(TNode *pList, const TNode *pNode);
const TNode *getFirst(const TNode *pList);
TNode list;
2.追加1个TLinkData到list链表中
TLinkData data;
append(&list, (const TNode *)&data);

如果node是放在data的末尾的话,这里的第二个参数就要改改了,(const TNode *)&data.node;

3.将节点pNode从list中删除

[html]  ?delete(&list, pNode); 

delete(&list, pNode);4.获取list的第1个节点,并使用它
const TNode *pNode = getFirst(&list);
const TLinkData *pLinkData = (const TLinkData *)pNode;
const TData &data = pLinkData->data;

如果node是放在data的末尾的话,第二行就不能直接这样转换了,pNode的地址需要减去1个sizeof(TData),才是首地址

Tag:
网友评论

<