可复用性的链式存储结构的线性表的实现---单链表

链表：                
            链表是一种物理上非连续、非顺序的，的逻辑顺序是通过链表中的链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储的数据域，另一个是存储下一个结点地址的域。 相比于，操作。
特点：
            的链式存储表示的特点是用一组任意的存储的（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个与其直接后继数据元素 之间的逻辑关系，对数据元素 来说，除了其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个"结点"（如概述旁的图所示），表示线性表中一个。线性表的链式存储表示，有一个缺点就是要找一个数，必须要从头开始找起，十分麻烦。

//头文件

#ifndef _LINKLIST_H_
#define _LINKLIST_H_

typedef void LinkList;

typedef struct _tag_LinkListNode LinkListNode;
struct _tag_LinkListNode
{
    LinkListNode* next; //定义结点指针
};
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

//C源文件

#include <stdio.h>
#include <malloc.h>
#include "LinkList.h"

typedef struct _tag_LinkList   //定义头结点
{
    LinkListNode header; //定义指针指向第一个元素
    int length; //链表长度
}TLinkList;

LinkList* LinkList_Create()
{
    TLinkList* ret = (TLinkList*)malloc(sizeof(TLinkList));
    //为结点分配空间
    if( ret != NULL)
    {
        ret->length = 0;
        ret->header.next = NULL;
    }
    return ret;
}

void LinkList_Destroy(LinkList* list)
{
    free(list);
}

void LinkList_Clear(LinkList* list)
{
    TLinkList* sList = (TLinkList*)list;

    if( sList != NULL )
    {
        sList->length = 0;
        sList->header.next = NULL;
    }
}

int LinkList_Length(LinkList* list)
{
    TLinkList* sList = (TLinkList*)list;

    int ret = -1;
    if( sList != NULL )
    {
        ret = sList->length;
    }
    return ret;
}

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{
    TLinkList* sList = (TLinkList*)list;

    int ret = 1;
    int i = 0;

    ret = ret && (sList != NULL); //判断链表是否合法
    ret = ret && (pos >= 0) && (node->next != NULL);
    //判断插入位置是否合法

    if( ret )
    {
        LinkListNode* current = (LinkListNode*)sList;
        for(i=0; ( (i<pos) && (current->next != NULL) ); i++)
        {
            current = current->next;
        }

        node->next = current->next;
        current->next = node;
        sList->length++;
    }

    return ret;
}

LinkListNode* LinkList_Get(LinkList* list, int pos)
{
    TLinkList* sList = (TLinkList*)list;

    LinkListNode* ret = NULL;
    int i = 0;

    if( (sList != NULL) && ((0<=pos) && (pos<=LinkList_Length(sList))) )
    {
        LinkListNode* current = (LinkListNode*)sList;
        for(i=0; i<pos; i++)
        {
            current = current->next;
        }
        ret = current->next;
    }
    return ret;
}

LinkListNode* LinkList_Delete(LinkList* list, int pos)
{
    TLinkList* sList = (TLinkList*)list;

    LinkListNode* ret = NULL;
    int i = 0;

    if( (sList != NULL) && ((0<=pos) && (pos<sList->length)) )
    {
        LinkListNode* current = (LinkListNode*)sList;
        for(i=0; i<pos; i++)
        {
            current = current->next;
        }
        ret = current->next;
        current->next = ret->next;

        sList->length--;
    }
    return ret;
}

//测试文件

#include <stdio.h>
#include <stdlib.h>
#include "LinkList.h"

struct value    //定义数据元素
{
    LinkListNode header;  //定义指针域
    int v;                //定义数据域
};

int main()
{
    LinkList* list = LinkList_Create();
    int i;

    struct value v1;
    struct value v2;
    struct value v3;
    struct value v4;
    struct value v5;

    v1.v = 1;
    v2.v = 2;
    v3.v = 3;
    v4.v = 4;
    v5.v = 5;

    LinkList_Insert(list,(LinkListNode*)&v1,LinkList_Length(list));
    LinkList_Insert(list,(LinkListNode*)&v2,LinkList_Length(list));
    LinkList_Insert(list,(LinkListNode*)&v3,LinkList_Length(list));
    LinkList_Insert(list,(LinkListNode*)&v4,LinkList_Length(list));
    LinkList_Insert(list,(LinkListNode*)&v5,LinkList_Length(list));

    for(i=0; i<LinkList_Length(list); i++)
    {
        struct value* pv = (struct value*)LinkList_Get(list,i);

        printf("%d\n",pv->v);
    }

    while( LinkList_Length(list)>0 )
    {
        struct value* pv = (struct value*)LinkList_Delete(list,0);

        printf("%d\n",pv->v);
    }

    LinkList_Destroy(list);

    return 0;
}