Linux cアルゴリズムとデータ構造--双方向チェーンテーブル

最近ずっとC言语の基础を固めて、书いたいくつかの文章は主に自分の学习のノートになって、きっといくつかの小さい间违いが现れて、あるいは内容は比较的に初级で、自分の努力を通じていくつかの高いレベルの博文を书くことを望みます!
チェーンテーブルはlinux cにおいて非常に重要なデータ構造であり、双方向チェーンテーブルと一方向チェーンテーブルの違いは、各ノードに2つのポインタドメインがあり、それぞれそのノードの前のノードと後のノードを指している.
チェーンテーブルの操作は主にクエリー、挿入、削除、遍歴などで、次は双方向のチェーンテーブルを見て、主に小さな練習をして、印象を深めます!
コードは次のとおりです.
Dlist.h

#ifndef DList_H
#define DList_H
typedef  int Item;
typedef struct Node * PNode;
typedef PNode Position;
/*      */
typedef struct Node
{
    Item data;        /*   */
    PNode previous; /*    */
    PNode next;        /*    */
}Node;
/*      */
typedef struct
{
    PNode head;        /*     */
    PNode tail;        /*     */
    int size;
}DList;

/*    i   ，       */
Position MakeNode(Item i);

/*  p     */
void FreeNode(PNode p);

/*          */
DList* InitList();

/*        */
void DestroyList(DList *plist);

/*         ，         */
void ClearList(DList *plist);

/*       */
Position GetHead(DList *plist);

/*       */
Position GetTail(DList *plist);

/*      */
int GetSize(DList *plist);

/*  p       */
Position GetNext(Position p);

/*  p       */
Position GetPrevious(Position p);

/* pnode             */
PNode InsFirst(DList *plist,PNode pnode);

/*                */
PNode DelFirst(DList *plist);

/*        */
Item GetItem(Position p);

/*        */
void SetItem(Position p,Item i);

/*               ，               */
PNode Remove(DList *plist);

/*    p         S*/
PNode InsBefore(DList *plist,Position p,PNode s);

/*    p         s*/
PNode InsAfter(DList *plist,Position p,PNode s);

/*       i      */
PNode LocatePos(DList *plist,int i);

/*              visit()*/
void ListTraverse(DList *plist,void (*visit)());
#endif

DList.c  

#include"DList.h"
#include
#include
/*    i   ，       */
Position MakeNode(Item i)
{
    PNode p = NULL; 
    p = (PNode)malloc(sizeof(Node));
    if(p!=NULL)
    {
        p->data = i;
        p->previous = NULL;
        p->next = NULL;
    }    
    return p;
}
/*  p     */
void FreeNode(PNode p)
{
     free(p);
}
/*          */
DList * InitList()
{
    DList *plist = (DList *)malloc(sizeof(DList));
    PNode head = MakeNode(0); 
    if(plist!=NULL)
    {
        if(head!=NULL)
        {
            plist->head = head;
            plist->tail = head;
            plist->size = 0;
        }
        else
            return NULL;
    }
    return plist;
}

/*        */
void DestroyList(DList *plist)
{
    ClearList(plist);
    free(GetHead(plist));
    free(plist);
}

/*         */
int IsEmpty(DList *plist)
{
    if(GetSize(plist)==0&&GetTail(plist)==GetHead(plist))
        return 1;
    else
        return 0;
}
/*         ，         */
void ClearList(DList *plist)
{
    PNode temp,p;
    p = GetTail(plist);
    while(!IsEmpty(plist))
    {    
        temp = GetPrevious(p);
        FreeNode(p);
        p = temp;
        plist->tail = temp;
        plist->size--;
    }
}

/*       */
Position GetHead(DList *plist)
{
    return plist->head;
}

/*       */
Position GetTail(DList *plist)
{
    return plist->tail;
}

/*      */
int GetSize(DList *plist)
{
    return plist->size;
}

/*  p       */
Position GetNext(Position p)
{
    return p->next;
}

/*  p       */
Position GetPrevious(Position p)
{
    return p->previous;
}

/* pnode             */
PNode InsFirst(DList *plist,PNode pnode)
{
    Position head = GetHead(plist);

    if(IsEmpty(plist))
        plist->tail = pnode;
    plist->size++;

    pnode->next = head->next;
    pnode->previous = head;

    if(head->next!=NULL)
        head->next->previous = pnode;
    head->next = pnode;
    
    return pnode; 
}

/*          ,        */
PNode DelFirst(DList *plist)
{
    Position head = GetHead(plist);
    Position p=head->next;
    if(p!=NULL)
    {
        if(p==GetTail(plist))
            plist->tail = p->previous;
        head->next = p->next;
        head->next->previous = head;
        plist->size--;
        
    }    
    return p;
}

/*        */
Item GetItem(Position p)
{
    return p->data;
}

/*        */
void SetItem(Position p,Item i)
{
    p->data = i;
}

/*              ，               */
PNode Remove(DList *plist)
{
    Position p=NULL;
    if(IsEmpty(plist))
        return NULL;
    else
    {
        p = GetTail(plist);
        p->previous->next = p->next;
        plist->tail = p->previous;
        plist->size--;
        return p;
    }
}
/*    p         s*/
PNode InsBefore(DList *plist,Position p,PNode s)
{
    s->previous = p->previous;
    s->next = p;
    p->previous->next = s;    
    p->previous = s;

    plist->size++;
    return s;
}
/*    p         s*/
PNode InsAfter(DList *plist,Position p,PNode s)
{
    s->next = p->next;
    s->previous = p;
    
    if(p->next != NULL)
        p->next->previous = s;
    p->next = s;
    
    if(p = GetTail(plist))
        plist->tail = s;
    
    plist->size++;
    return s;
}

/*       i      */
PNode LocatePos(DList *plist,int i)
{
    int cnt = 0;
    Position p = GetHead(plist);
    if(i>GetSize(plist)||i<1)
        return NULL;

    while(++cnt<=i)
    {
        p=p->next;
    }

    return p;
}

/*              visit()*/
void ListTraverse(DList *plist,void (*visit)())
{
    Position p = GetHead(plist);
    if(IsEmpty(plist))
        exit(0);
    else
    {
        
        while(p->next!=NULL)
        {
            p = p->next;
            visit(p->data);            
        }        
    }
}

test.c

#include"DList.h"
#include
void print(Item i)
{
    printf("    %d 
",i);
}
main()
{
    DList *plist = NULL;
    PNode p = NULL;
    
    plist = InitList();
    p = InsFirst(plist,MakeNode(1));
    InsBefore(plist,p,MakeNode(2));
    InsAfter(plist,p,MakeNode(3));

    printf("p       %d
",GetItem(GetPrevious(p)));
    printf("p     %d
",GetItem(p));
    printf("p       %d
",GetItem(GetNext(p)));
    
    
    printf("          :
");
    ListTraverse(plist,print);
    printf("          %d   
",GetSize(plist));
    FreeNode(DelFirst(plist));
    printf("               :
");
    ListTraverse(plist,print);
    printf("          %d   
",GetSize(plist));
    DestroyList(plist);
    printf("      
");
}

実行結果は次のとおりです.