データ構造--双方向リンク表

// DOUBLELINKLIST.h
/***************************************************************************
 * File: DOUBLELINKLIST.h
 * Author: suzhaoda ([email protected])
 *
 *     (   )
 * ADT (List)
 * Data
 *   {a1, a2, a3, ..., an}
 * Operation
 *   InitList(*L);                 L.
 *   CreateList(*L, n);             n     L.
 *   ListEmpty(L);                    L  ,  true,    false.
 *   ClearList(*L);                  L  .
 *   GetElem(L, i, *e);              L  i         e.
 *   LocateElem(L, e);           L   e     ,         .
 *                                ,  ,  0    .
 *   ListInsert(*L, i, e);       L  i        e.
 *   ListDelete(*L, i, *e);       L  i      ,  e    .
 *   ListLength(L);                  L     .
 *   ListTraverse(L);              L         
 * ENDADT
 *                     
 *                     --        --      --        --
 *           prior -->|^ |  +---|  | ...|  |  +---|  |
 *                     --   |    --      --   |    --
 *                    |a1|<-||->|a2| ...|am|<-||->|an|
 *                     --    |   --      --    |   --
 *            next -->|  |---+  |  | ...|  |---+  |^ | 
 *                     --        --      --        -- 
 *     ：
 *
 */
#ifndef DOUBLELINKLIST_H_INCLUDED
#define DOUBLELINKLIST_H_INCLUDED

/************************ data              ***********************/
#include <stdlib.h>             /* malloc()*/
#include <time.h>               /* time() */
#include <stdio.h>

#define OK    1
#define ERROR 0
#define TRUE  1
#define FALSE 0

typedef int ElemType;           /* ElemType           ,     int */
typedef int Status;             /* Status       ，            */

/*           */
typedef struct DulNode{
    ElemType data;
    struct DulNode* prior;      /*        */
    struct DulNode* next;       /*        */
}DulNode;

/*   DulLinkList */
typedef struct DulNode* DulLinkList;

/***************************** operation    *****************************/

/*
 *     ：    L   .
 *     :             L;
 */
Status InitList(DulLinkList* L);

/*
 *     ：    L  .
 *     ：    n     L,    true,     false
 */
Status CreateList(DulLinkList* L, int n);

/*
 *     ：    L   .
 *     ：      L  ,  true,    false.
 */
Status ListEmpty(DulLinkList L);

/*
 *     ：    L   ，1 <= i <= ListLength(L)
 *     ： e  L  i     
 */
Status GetElem(DulLinkList L, int i, ElemType* e);

/*
 *     :     L   。
 *     ：     L     。
 */
Status ClearList(DulLinkList* L);

/*
 *     ：    L   .
 *     ： L   e     ，           ，
 *             ，  0    
 */
int LocateElem(DulLinkList L, ElemType e);

/*
 *     :     L   ，1 <= i <= ListLength(L)
 *     ： L  i          e
 */
Status ListInsert(DulLinkList* L, int i, ElemType e);

/*
 *     :     L   ，1 <= i <= ListLength(L)
 *     ： L  i          e.
 */
Status ListDelete(DulLinkList* L, int i, ElemType* e);

/*
 *     ：    L    .
 *     ：      L     .
 */
int ListLength(DulLinkList L);

/*
 *     ：    L   
 *     ：   L         
 */
Status ListTraverse(DulLinkList L);
#endif // DOUBLELINKLIST_H_INCLUDED

// DOUBLELINKLIST.c
#include "DOUBLELINKLIST.h"

Status InitList(DulLinkList* L)
{
  *L = (DulLinkList)malloc(sizeof(DulNode));    /*      ,  L       */
  if(!(*L))                                     /*        */
    return ERROR;

  (*L) -> data = -1;
  (*L) -> prior = NULL;
  (*L) -> next = NULL;

  return OK;
}

Status CreateList(DulLinkList* L, int n)
{
  DulLinkList p;
  DulLinkList r;
  int i;

  srand(time(0));                         /*         */

  r = *L;                                 /* r        */
  for(i = 0; i < n; i++){
    p = (DulLinkList) malloc(sizeof(DulNode));
    p -> data = rand() % 100 + 1;         /*   100      */

    r -> next = p;                        /*                  */
    p -> prior = r;                       /*                   */

    r = p;                                /*                  */
  }
  r -> next = NULL;

  return OK;
}

Status ListEmpty(DulLinkList L)
{
  return (L -> next == NULL ? TRUE : FALSE);
}

Status GetElem(DulLinkList L, int i, ElemType* e)
{
  int j;
  DulLinkList p;             /*        */

  p = L -> next;             /*  p  L       */
  j = 1;                     /* j     */

  /* p          j   i ，     */
  while (p != NULL && j < i) {
    p = p -> next;           /*  p        */
    j++;
  }

  if (p == NULL || j > i)    /*  i       */
    return ERROR;

  *e = p -> data;            /*   i    */

  return OK;
}

Status ClearList(DulLinkList* L)
{
  DulLinkList p;
  DulLinkList q;

  p = (*L) -> next;          /*         */

  while(p != NULL){          /*      */
    q = p -> next;
    free(p);
    p = q;
  }
  (*L) -> next = NULL;
  return OK;
}

int LocateElem(DulLinkList L, ElemType e)
{
  int i;
  DulLinkList p;
  p = L -> next;             /*           */
  i = 1;                     /* i     */

  while(p != NULL){          /* p              */

    if(p -> data == e)
      return i;
    i++;
    p = p -> next;
  }
  return 0;
}

Status ListInsert(DulLinkList* L, int i, ElemType e)
{
  int j;
  DulLinkList p;
  DulLinkList s;

  p = (*L) -> next;
  j = 1;

  /*    i    */
  while(p != NULL && j < i){
    p = p -> next;
    j++;
  }
  /*  i       */
  if (p == NULL || j > i)
    return ERROR;

  /*       */
  s = (DulLinkList) malloc(sizeof(DulNode));
  s -> data = e;

  if (p -> next == NULL){
    s -> prior = p;
    s -> next = NULL;
    p -> next = s;
  }else{
    s -> prior = p;           /*  p  s    */
    s -> next = p -> next;    /*  p     s */
    p -> next -> prior = s;   /*  s  p    */
    p -> next = s;            /*   p    */
  }
  return OK;
}

Status ListDelete(DulLinkList* L, int i, ElemType* e)
{
  int j;
  DulLinkList p;
  DulLinkList q;

  p = (*L);                    /*       */
  j = 1;

  /*    i    */
  while(p -> next != NULL && j < i){
    p = p -> next;
    j++;
  }

  /*  i       */
  if ( p -> next == NULL || j > i)
    return ERROR;

  q = p -> next;               /* q         */
  p -> next = q -> next;       /*  q     p    */
  q -> next -> prior = p;      /*  p  q       */
  *e = q -> data;              /*  q       e */
  free(q);                     /*        ，     */

  return OK;
}

int ListLength(DulLinkList L)
{
  int i;
  DulLinkList p;

  i = 0;
  p = L -> next;

  while (p != NULL){
    i++;
    p = p -> next;
  }
  return i;
}

Status ListTraverse(DulLinkList L)
{
  DulLinkList p;
  p = L -> next;
  while(p != NULL){
      printf("%d ", p -> data);
      p = p -> next;
    }
  printf("
");
  return OK;
}
  <      >