데이터 구조 - 선형 표 - 정적 링크 완전 실행 코드

  
  
  
  

   
   
   
   /***************************************************************************
  
  
  
  
 *
 *     
 * ADT (List)
 * Data
 *   {a1, a2, a3, ..., an}
 * Operation
 *   InitList(*L);                      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);            L  i      .
 *   ListLength(L);                   L     .
 * ENDADT
 *
 *     
 *                    0|a0| m|  ---->        
 *                    1|a1| 2|
 *                    2|a2| 3|
 *                      .. ..
 *                    i|ai| 0|
 *                      .. ..
 *                max-1|an| 1|  ---->      
 *
 *     ：
 *           2012-12-11       ,    ，      .
 */


/************************ data              *********************/

#define MAXSIZE 1000            /*           1000 */
#define OK      1
#define ERROR   0
#define TRUE    1
#define FALSE   0

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

/*          */
typedef struct{
    ElemType data;
    int cur;                      /*   (cursor)  0        */
}Component, StaticLinkList[MAXSIZE];

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

/*
 *     ：    L   。
 *     ：     space            
 *           cur                。
 *            cur             ，  
 *         。
 */
Status InitList(StaticLinkList space)
{
    int i;
    for(i = 0; i < MAXSIZE - 1; i++){
        space[i].cur = i + 1;
    }
    
    space[MAXSIZE - 1].cur = 0;   /*         ，       cur  0 */
    
    return OK;
}

/*
 *     ：    L   
 *     ：        ，  true，    false
 */
Status ListEmpty(StaticLinkList L)
{
    return (ListLength(L) == 0 ? TRUE : FALSE);
}

/*          ，          ，    0 */
int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur;         /*          cur   ，
                                                  . */
    
    /*              ，    
                   */
    if(space[0].cur)
        space[0].cur = space[i].cur;
    
    return i;
}

/*
 *     :     L   
 *     ：     L     0，    0
 *                     
 */
void ClearList(StaticLinkList L)
{
    int i;
    i = L[MAXSIZE - 1].cur;
    
    while(i){
        L[i].data = 0;
        ListDelete(L,i);
    }
}

/*
 *     ：    L   ，1 <= i <= ListLength(L)
 *     ： e  L  i     
 */
Status GetElem(StaticLinkList L, int i, ElemType *e)
{
    int j;
    int k;
    j = L[MAXSIZE - 1].cur;
    k = 1;
    
    while(j && k < i){
        j = L[j].cur;
        k++;
    }
    if(!j || k > i)
        return ERROR;
    
    *e = L[j].data;
    return OK;
}

/*
 *     ：    L   .
 *     ： L   e     ，           ，
 *             ，  0    
 */
Status LocateElem(StaticLinkList L, ElemType e)
{
    int i = L[MAXSIZE - 1].cur;
    
    while(i){
        if (L[i].data == e)
            return i;
        i = L[i].cur;
    }
    
    return 0;
}

/*
 *     :     L   ，1 <= i <= ListLength(L)
 *     ： L  i          e , L    1
 */
Status ListInsert(StaticLinkList L, int i, ElemType e)
{
    int j;
    int k;
    int l;
    
    k = MAXSIZE - 1;                  /*   k            ,     */
    
    if(i < 1 || i > ListLength(L) + 1)
        return ERROR;
    
    j = Malloc_SLL(L);                /*           */
    
    if(j){
        L[j].data = e;                  /*          data */
        for(l = 1; l <= i - 1; l++)     /*         i        */
            k = L[k].cur;
        
        L[j].cur = L[k].cur;            /*   i     cur       cur */
        L[k].cur = j;                   /*            i       cur */
        
        return OK;
    }
    
    return ERROR;
}

/*     k            ,       */
void Free_SLL(StaticLinkList space, int k)
{
    space[k].cur = space[0].cur;      /*       cur          cur */
    space[0].cur = k;                 /*                cur */
}

/*
 *     :     L   ，1 <= i <= ListLength(L)
 *     ：   L  i   e.
 */
Status ListDelete(StaticLinkList L, int i)
{
    int j;
    int k;
    
    if (i < 1 || i > ListLength(L))
        return ERROR;
    
    k = MAXSIZE - 1;
    for(j = 1; j <= i - 1; j++){      /*                   */
        k = L[j].cur;
    }
    j = L[k].cur;                     /*             */
    L[k].cur = L[j].cur;              /*                   
                                               */
    
    Free_SLL(L, j);
    return OK;
}

/*
 *     ：    L    .
 *     ：  L     .
 */
int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE - 1].cur;
    
    while(i){
        i = L[i].cur;
        j++;
    }
    
    return j;
}

int main()
{
//        ...
//    StaticLinkList L;
//    InitList(L);
    return 0;
}