线性表链式存储

上文中我们介绍了线性表顺序储存的方式，并给大家画了一幅比较详细的图（虽然看着比较凌乱），本文介绍的是数据储存的另外一种方式“链式储存”，这相当于我们之前提到过的单向链表，但是，本文与上一篇文章一样，都将数据的储存和算法进行了分离。这才是我们真正应该晋级了解的东西，如果只是一个单向链表，不足以我们耗费这么多精力。

【表示图】

下图是我们使用链式储存数据的方式表示图，其中用户层生成了栈上的数据，然后将栈上的数据使用强制类型转换转换成了实现层可以识别的数据，转换过程中，出现了数据截断，但这并不重要，重要的是截断后得到了一个 LinkListNode* 类型的指针，我们利用这些指针，将数据在实现内部串联成一个多个指向某地址的指针组成的链表，这些指针就指向了外部传递进来的数据的头部位置。这样就实现了，外部调用层管理数据的生命周期，而在实现层管理数据的储存和链接，中间通过一个 LinkListNode* 结构体巧妙的将数据转换为调用层和实现层都可识别的数据。

【实现代码】

#ifndef _LINK_LIST_H
#define _LINK_LIST_H

typedef void LinkList;
typedef struct _tag_LinkList_Node
{
struct _tag_LinkList_Node* next;
}LinkListNode;

//创建链式线性表
LinkList* LinkList_Create();

//销毁链式线性表
void LinkList_Destroy(LinkList* list);

//清空链式线性表
void LinkList_Clear(LinkList* list);

//获取链式线性表长度
int LinkList_Length(LinkList* list);

//往链式线性表中插入节点
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);

//获取链式线性表中某个位置的元素
LinkListNode* LinkList_Get(LinkList* list, int pos);

//删除链式线性表中某个位置的元素
LinkListNode* LinkList_Delete(LinkList* list, int pos);

#endif //_LINK_LIST_H

#include “LinkList.h”
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tag_LinkList
{
int length;
LinkListNode header;
}TLinkList;

LinkList* LinkList_Create()
{
TLinkList* tlist = (TLinkList*)malloc(sizeof(TLinkList));

tlist->length = 0;
tlist->header.next = NULL;

return tlist;
}

void LinkList_Destroy(LinkList* list)
{
if (NULL == list) return;
// 将类型转换为内部可识别的类型
TLinkList* tlist = (TLinkList*)list;

free(tlist);
}

void LinkList_Clear(LinkList* list)
{
if (NULL == list) return;
// 将类型转换为内部可识别的类型
TLinkList* tlist = (TLinkList*)list;

tlist->length = 0;
tlist->header.next = NULL;
}

int LinkList_Length(LinkList* list)
{
if (NULL == list) return -1;
// 将类型转换为内部可识别的类型
TLinkList* tlist = (TLinkList*)list;

return tlist->length;
}

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{
if (NULL == list) return -1;
// 将类型转换为内部可识别的类型
TLinkList* tlist = (TLinkList*)list;
// 备份指针，指向 tlist 表的头节点
LinkListNode* pCur = &tlist->header;

for (int i = 0; i < pos; i++)
{
// 备份指针后移到 pos 的位置的前一个节点
pCur = pCur->next;
}

// 让新来的节点先有所指向
node->next = pCur->next;
pCur->next = node;

// 记录链表有效节点个数的变量++
tlist->length++;

return 0;
}

LinkListNode* LinkList_Get(LinkList* list, int pos)
{
if (NULL == list) return NULL;
// 将类型转换为内部可识别的类型
TLinkList* tlist = (TLinkList*)list;
// 备份指针，指向 tlist 表的头节点
LinkListNode* pCur = &tlist->header;

for (int i = 0; i < pos; i++)
{
// 备份指针后移到 pos 的位置的前一个节点
pCur = pCur->next;
}

return pCur->next;
}

LinkListNode* LinkList_Delete(LinkList* list, int pos)
{
if (NULL == list) return NULL;
// 将类型转换为内部可识别的类型
TLinkList* tlist = (TLinkList*)list;
// 备份指针，指向 tlist 表的头节点
LinkListNode* pCur = &tlist->header;

for (int i = 0; i < pos; i++)
{
// 备份指针后移到 pos 的位置的前一个节点
pCur = pCur->next;
}

LinkListNode* pDel = pCur->next;
pCur->next = pDel->next;

tlist->length–;

return pDel;
}

#include “LinkList.h”
#include <stdio.h>

// 外部要储存的数据结构
typedef struct tag_Teacher
{
LinkListNode node;
int age;
char name[24];
}Teacher;

int main()
{
// 创建一个链表
LinkList* list = LinkList_Create();
if (NULL == list) return -1;

Teacher tea[10];
for (int i = 0; i < 10; i++)
{
tea[i].age = i + 20;
sprintf_s(tea[i].name, “teacher_%d”, i);
printf(“address = %p\n”, (LinkListNode*)&tea[i]);
LinkList_Insert(list, (LinkListNode*)&tea[i], i);
}

for (int i = 0; i < LinkList_Length(list); i++)
{
Teacher *pTea = (Teacher*)LinkList_Get(list, i);
printf(“address = %p, Teacher age = %d, name = %s\n”, pTea, pTea->age, pTea->name);
}

while (LinkList_Length(list))
{
Teacher *pTea = (Teacher*)LinkList_Delete(list, 0);
printf(“delete – Teacher age = %d, name = %s\n”, pTea->age, pTea->name);
}

LinkList_Destroy(list);

return 0;
}