1. #include "string.h"
    2. #include "ctype.h"      
    4. #include "stdio.h"    
    5. #include "stdlib.h"   
    6. #include "io.h"  
    7. #include "math.h"  
    8. #include "time.h"
    10. #define OK 1
    11. #define ERROR 0
    12. #define TRUE 1
    13. #define FALSE 0
    15. #define MAXSIZE 1000 /* 存储空间初始分配量 */
    17. typedef int Status;           /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
    18. typedef char ElemType;        /* ElemType类型根据实际情况而定，这里假设为char */
    21. Status visit(ElemType c)
    22. {
    23.     printf("%c ",c);
    24.     return OK;
    25. }
    27. /* 线性表的静态链表存储结构 */
    28. typedef struct 
    29. {
    30.     ElemType data;
    31.     int cur;  /* 游标(Cursor) ，为0时表示无指向 */
    32. } Component,StaticLinkList[MAXSIZE];
    35. /* 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，"0"表示空指针 */
    36. Status InitList(StaticLinkList space) 
    37. {
    38.     int i;
    39.     for (i=0; i<MAXSIZE-1; i++)  
    40.         space[i].cur = i+1;
    41.     space[MAXSIZE-1].cur = 0; /* 目前静态链表为空，最后一个元素的cur为0 */
    42.     return OK;
    43. }
    46. /* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
    47. int Malloc_SSL(StaticLinkList space) 
    48. { 
    49.     int i = space[0].cur;                   /* 当前数组第一个元素的cur存的值 */
    50.                                             /* 就是要返回的第一个备用空闲的下标 */
    51.     if (space[0]. cur)         
    52.         space[0]. cur = space[i].cur;       /* 由于要拿出一个分量来使用了， */
    53.                                             /* 所以我们就得把它的下一个 */
    54.                                             /* 分量用来做备用 */
    55.     return i;
    56. }
    59. /*  将下标为k的空闲结点回收到备用链表 */
    60. void Free_SSL(StaticLinkList space, int k) 
    61. {  
    62.     space[k].cur = space[0].cur;    /* 把第一个元素的cur值赋给要删除的分量cur */
    63.     space[0].cur = k;               /* 把要删除的分量下标赋值给第一个元素的cur */
    64. }
    66. /* 初始条件：静态链表L已存在。操作结果：返回L中数据元素个数 */
    67. int ListLength(StaticLinkList L)
    68. {
    69.     int j=0;
    70.     int i=L[MAXSIZE-1].cur;
    71.     while(i)
    72.     {
    73.         i=L[i].cur;
    74.         j++;
    75.     }
    76.     return j;
    77. }
    79. /*  在L中第i个元素之前插入新的数据元素e   */
    80. Status ListInsert(StaticLinkList L, int i, ElemType e)   
    81. {  
    82.     int j, k, l;   
    83.     k = MAXSIZE - 1;   /* 注意k首先是最后一个元素的下标 */
    84.     if (i < 1 || i > ListLength(L) + 1)   
    85.         return ERROR;   
    86.     j = Malloc_SSL(L);   /* 获得空闲分量的下标 */
    87.     if (j)   
    88.     {   
    89.         L[j].data = e;   /* 将数据赋值给此分量的data */
    90.         for(l = 1; l <= i - 1; l++)   /* 找到第i个元素之前的位置 */
    91.            k = L[k].cur;           
    92.         L[j].cur = L[k].cur;    /* 把第i个元素之前的cur赋值给新元素的cur */
    93.         L[k].cur = j;           /* 把新元素的下标赋值给第i个元素之前元素的ur */
    94.         return OK;   
    95.     }   
    96.     return ERROR;   
    97. }
    99. /*  删除在L中第i个数据元素   */
    100. Status ListDelete(StaticLinkList L, int i)   
    101. { 
    102.     int j, k;   
    103.     if (i < 1 || i > ListLength(L))   
    104.         return ERROR;   
    105.     k = MAXSIZE - 1;   
    106.     for (j = 1; j <= i - 1; j++)   
    107.         k = L[k].cur;   
    108.     j = L[k].cur;   
    109.     L[k].cur = L[j].cur;   
    110.     Free_SSL(L, j);   
    111.     return OK;   
    112. } 
    114. Status ListTraverse(StaticLinkList L)
    115. {
    116.     int j=0;
    117.     int i=L[MAXSIZE-1].cur;
    118.     while(i)
    119.     {
    120.             visit(L[i].data);
    121.             i=L[i].cur;
    122.             j++;
    123.     }
    124.     return j;
    125.     printf("\n");
    126.     return OK;
    127. }
    130. int main()
    131. {
    132.     StaticLinkList L;
    133.     Status i;
    134.     i=InitList(L);
    135.     printf("初始化L后：L.length=%d\n",ListLength(L));
    137.     i=ListInsert(L,1,'F');
    138.     i=ListInsert(L,1,'E');
    139.     i=ListInsert(L,1,'D');
    140.     i=ListInsert(L,1,'B');
    141.     i=ListInsert(L,1,'A');
    143.     printf("\n在L的表头依次插入FEDBA后：\nL.data=");
    144.     ListTraverse(L); 
    146.     i=ListInsert(L,3,'C');
    147.     printf("\n在L的“B”与“D”之间插入“C”后：\nL.data=");
    148.     ListTraverse(L); 
    150.     i=ListDelete(L,1);
    151.     printf("\n在L的删除“A”后：\nL.data=");
    152.     ListTraverse(L); 
    154.     printf("\n");
    156.     return 0;
    157. }