一种单向链表的实现

一种单向链表的实现

赶了个单向链表，写吐了。前插还没写以后补吧。有些功能还没测试

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#define ok 1
#define err -1
#define ONE_LIST_DATA_SIZE 16
//#define LOG


//链表数据结构体
typedef struct{
    uint8_t data[ONE_LIST_DATA_SIZE];
}ListData;

//链表结构体
typedef struct{
    ListData data;
    struct List *NestList;
}List;

//链表信息结构体(描述链表长度，最后一个链表项的位置)
typedef struct
{
    struct List *ListTail;
    int32_t ListLen;
}ListHeadMsg;

//L0为所查链表项的前驱的指针，L1为所查链表项的指针
typedef struct
{
    List *L0;
    List *L1;
}GetListMsg;

//获取保存在链表头部的链表信息
ListHeadMsg * HeadListMsg(List *ListHead)
{
    ListHeadMsg *msg;
    msg=(ListHeadMsg *)(&ListHead->data);

    #ifdef LOG
    printf("ListHeadMsg:ListHead=%d\n",ListHead);
    printf("ListHeadMsg:ListHeadMsg=%d\n",msg);
    printf("ListHeadMsg:Msg.ListTail=%d\n",msg->ListTail);
    printf("ListHeadMsg:Msg.ListLen=%d\n",msg->ListLen);
    #endif // LOG

    if(msg) return msg;
    return NULL;
}

//销毁链表，释放内存
int DestroyList(List *ListHead)
{
    List *p,*q;
    if(!ListHead) return err;
    q=ListHead;
    p=q->NestList;
    for(;p!=NULL;)
    {
        free(p);
        q=p;
        p=q->NestList;
    }
    free(ListHead);
    return ok;
}

//清空链表
int ClearList(List *ListHead)
{
    if(DestroyList(ListHead->NestList)==ok)
    {
        ListHead->NestList=NULL;
        return ok;
    }
    return err;
}

//判断链表是否为空表，为空返回 ok
int ListEmpty(List *ListHead)
{
    if(ListHead->NestList) return err;
    return ok;
}

//取链表长度
int ListLength(List *ListHead)
{
    ListHeadMsg *msg;
    msg=HeadListMsg(ListHead);
    return msg->ListLen;
}

//取在位置i处的链表项和i-1处的链表项的地址信息（通过GetListMsg *msg取回）
int GetListSite(List *ListHead,int i,GetListMsg *msg)
{
    List *p,*q;
    int16_t x;

    if(i>ListLength(ListHead)&&i<1)
        return err;

    q=ListHead;
    p=q->NestList;
    for(x=1;p&&x<i;x++)
    {
        q=p;
        p=q->NestList;
    }

    if(p)
    {
        msg->L1=p;
        msg->L0=q;
        return ok;
    }
    else
    {
        msg->L1=q;
        msg->L0=NULL;
        return ok;
    }

}

//取第i个链表项的数据
int GetElem(List *ListHead,int16_t i,ListData *data)
{
    GetListMsg msg;
    if(GetListSite(ListHead,i,&msg)==ok)
    {
        memcpy(data,msg.L1,sizeof(ListData));
        return ok;
    }
    return err;
}

//寻找链表项L1的前驱链表项（通过List *L2取回前驱链表项的数据）
int PriorElem(List *ListHead,List *L1,List *L2)
{
    List *p,*q;
    int x;
    q=ListHead;
    p=q->NestList;
    for(x=1;p&&memcmp(L1,p,sizeof(List));x++)
    {
        q=p;
        p=p->NestList;
    }
    if(p&&x>1)
    {
        memcpy(L2,p,sizeof(List));
        return ok;
    }
    return err;
}

//寻找链表项L1的后继链表项（通过List *L2取回后继的数据）
int NextElem(List *ListHead,List *L1,List *L2)
{

    List *p,*q;
    q=ListHead;
    p=q->NestList;
    for(;p&&memcmp(L1,p,sizeof(List));)
    {
        q=p;
        p=p->NestList;
    }
    if(p->NestList)
    {
        memcpy(L2,p->NestList,sizeof(List));
        return ok;
    }
    return err;
}

//在链表中的第i个链表项前插入链表项L1
int ListInsert(List *ListHead,int i,List *L1)
{
    return err;
}

//在链表中的第i个链表项后插入链表项L1
int ListInsertRight(List *ListHead,int i,List *L1)
{
    GetListMsg msg;
    ListHeadMsg *HeadMsg;
    HeadMsg=HeadListMsg(ListHead);
    if(HeadMsg==NULL) return;
    if((GetListSite(ListHead,i,&msg))==ok)
    {
        #ifdef LOG
        printf("ListInsertRight:ListHead=%d\n",ListHead);
        printf("ListInsertRight:ListHeadMsg=%d\n",HeadMsg);
        printf("ListInsertRight:Msg.ListTail=%d\n",HeadMsg->ListTail);
        printf("ListInsertRight:Msg.ListLen=%d\n",HeadMsg->ListLen);
        #endif

        if((i<=(HeadMsg->ListLen))&&i>0)
        {
            L1->NestList=(msg.L1)->NestList;
            (msg.L1)->NestList=L1;
            HeadMsg->ListTail=L1;
            HeadMsg->ListLen+=1;
            return ok;
        }
        else if((i==0)&&(HeadMsg->ListLen==0))
        {
            ListHead->NestList=L1;
            L1->NestList=NULL;
            HeadMsg->ListLen=1;
            HeadMsg->ListTail=L1;
            return ok;
        }
        else if(i==HeadMsg->ListLen)
        {
            ((List *)(HeadMsg->ListTail))->NestList=L1;
            L1->NestList=L1;
        }
        return err;
    }
    return err;
}

//删除第i链表项（通过L1取回链表项的值）
int ListDelest(List *ListHead,int32_t i,List *L1)
{
    GetListMsg msg;
    ListHeadMsg *HeadMsg;
    if(GetListSite(ListHead,i,&msg)==ok)
    {
        memcpy(L1,msg.L1,sizeof(ListData));
        free(msg.L1);
        HeadMsg=HeadListMsg(ListHead);
        HeadMsg->ListLen-=1;
        return ok;
    }
    return err;
}

//初始化一个空的链表
int InitList(List **ListHead)
{
    ListHeadMsg *msg;
    *ListHead = (List *)malloc(sizeof(List));
    if(!ListHead) return err;
    memset(&(*ListHead)->data,0,sizeof(ListData));
    (*ListHead)->NestList=NULL;
    msg=HeadListMsg(*ListHead);
    msg->ListTail=NULL;
    msg->ListLen=0;

    #ifdef LOG
    printf("InitList:ListHead=%d\n",*ListHead);
    printf("InitList:ListHeadMsg=%d\n",msg);
    printf("InitList:Msg.ListTail=%d\n",msg->ListTail);
    printf("InitList:Msg.ListLen=%d\n",msg->ListLen);
    #endif // LOG


    return ok;
}

//创建一个长度为i的链表
int CreatLists(List **ListHead,int32_t i)
{
    int32_t x;
    List *L1;
    ListHeadMsg *msg;
    if(InitList(&L1)!=err)
        *ListHead=L1;
    else
        return err;
    printf("CreatLists:ListHead=%d\n",*ListHead);
    for(x=0;x<i;x++)
    {
        ListInsertRight(*ListHead,x,(List *)malloc(sizeof(List)));

        #ifdef LOG
        msg=HeadListMsg(*ListHead);
        printf("CreatLists:ListHead=%d\n",*ListHead);
        printf("CreatLists:ListHeadMsg=%d\n",msg);
        printf("CreatLists:Msg.ListTail=%d\n",msg->ListTail);
        printf("CreatLists:Msg.ListLen=%d\n",msg->ListLen);
        #endif // LOG
    }
    return ok;
}

int main()
{
    List *newlist;
    List L1;
    GetListMsg msg;
    ListData data;
    if(CreatLists(&newlist,6)==ok)    //创建一个6个链表项的链表
    {
        GetListSite(newlist,5,&msg);    //获取第5个链表项的地址
        printf("链表长度:%d\n",ListLength(newlist));
        ((ListData)((msg.L1)->data)).data[0]=1;
        GetElem(newlist,5,&data);    //取第五个链表项的数据；
        printf("data:%d",data.data[0]);
    }

    return 0;
}