1. #include "stdio.h"    
    2. #include "string.h"
    3. #include "ctype.h"      
    4. #include "stdlib.h"   
    5. #include "io.h"  
    6. #include "math.h"  
    7. #include "time.h"
    9. #define OK 1
    10. #define ERROR 0
    11. #define TRUE 1
    12. #define FALSE 0
    14. #define MAXSIZE 20 /* 存储空间初始分配量 */
    16. typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
    17. typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
    20. Status visit(ElemType c)
    21. {
    22.     printf("%d ",c);
    23.     return OK;
    24. }
    26. typedef struct Node
    27. {
    28.     ElemType data;
    29.     struct Node *next;
    30. }Node;
    31. typedef struct Node *LinkList; /* 定义LinkList */
    33. /* 初始化顺序线性表 */
    34. Status InitList(LinkList *L) 
    35. { 
    36.     *L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */
    37.     if(!(*L)) /* 存储分配失败 */
    38.             return ERROR;
    39.     (*L)->next=NULL; /* 指针域为空 */
    41.     return OK;
    42. }
    44. /* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
    45. Status ListEmpty(LinkList L)
    46. { 
    47.     if(L->next)
    48.             return FALSE;
    49.     else
    50.             return TRUE;
    51. }
    53. /* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
    54. Status ClearList(LinkList *L)
    55. { 
    56.     LinkList p,q;
    57.     p=(*L)->next;           /*  p指向第一个结点 */
    58.     while(p)                /*  没到表尾 */
    59.     {
    60.         q=p->next;
    61.         free(p);
    62.         p=q;
    63.     }
    64.     (*L)->next=NULL;        /* 头结点指针域为空 */
    65.     return OK;
    66. }
    68. /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
    69. int ListLength(LinkList L)
    70. {
    71.     int i=0;
    72.     LinkList p=L->next; /* p指向第一个结点 */
    73.     while(p)                        
    74.     {
    75.         i++;
    76.         p=p->next;
    77.     }
    78.     return i;
    79. }
    81. /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
    82. /* 操作结果：用e返回L中第i个数据元素的值 */
    83. Status GetElem(LinkList L,int i,ElemType *e)
    84. {
    85.     int j;
    86.     LinkList p;        /* 声明一结点p */
    87.     p = L->next;        /* 让p指向链表L的第一个结点 */
    88.     j = 1;        /*  j为计数器 */
    89.     while (p && j<i)  /* p不为空或者计数器j还没有等于i时，循环继续 */
    90.     {   
    91.         p = p->next;  /* 让p指向下一个结点 */
    92.         ++j;
    93.     }
    94.     if ( !p || j>i ) 
    95.         return ERROR;  /*  第i个元素不存在 */
    96.     *e = p->data;   /*  取第i个元素的数据 */
    97.     return OK;
    98. }
    100. /* 初始条件：顺序线性表L已存在 */
    101. /* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
    102. /* 若这样的数据元素不存在，则返回值为0 */
    103. int LocateElem(LinkList L,ElemType e)
    104. {
    105.     int i=0;
    106.     LinkList p=L->next;
    107.     while(p)
    108.     {
    109.         i++;
    110.         if(p->data==e) /* 找到这样的数据元素 */
    111.                 return i;
    112.         p=p->next;
    113.     }
    115.     return 0;
    116. }
    119. /* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
    120. /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
    121. Status ListInsert(LinkList *L,int i,ElemType e)
    122. { 
    123.     int j;
    124.     LinkList p,s;
    125.     p = *L;   
    126.     j = 1;
    127.     while (p && j < i)     /* 寻找第i个结点 */
    128.     {
    129.         p = p->next;
    130.         ++j;
    131.     } 
    132.     if (!p || j > i) 
    133.         return ERROR;   /* 第i个元素不存在 */
    134.     s = (LinkList)malloc(sizeof(Node));  /*  生成新结点(C语言标准函数) */
    135.     s->data = e;  
    136.     s->next = p->next;      /* 将p的后继结点赋值给s的后继  */
    137.     p->next = s;          /* 将s赋值给p的后继 */
    138.     return OK;
    139. }
    141. /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
    142. /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
    143. Status ListDelete(LinkList *L,int i,ElemType *e) 
    144. { 
    145.     int j;
    146.     LinkList p,q;
    147.     p = *L;
    148.     j = 1;
    149.     while (p->next && j < i)    /* 遍历寻找第i个元素 */
    150.     {
    151.         p = p->next;
    152.         ++j;
    153.     }
    154.     if (!(p->next) || j > i) 
    155.         return ERROR;           /* 第i个元素不存在 */
    156.     q = p->next;
    157.     p->next = q->next;            /* 将q的后继赋值给p的后继 */
    158.     *e = q->data;               /* 将q结点中的数据给e */
    159.     free(q);                    /* 让系统回收此结点，释放内存 */
    160.     return OK;
    161. }
    163. /* 初始条件：顺序线性表L已存在 */
    164. /* 操作结果：依次对L的每个数据元素输出 */
    165. Status ListTraverse(LinkList L)
    166. {
    167.     LinkList p=L->next;
    168.     while(p)
    169.     {
    170.         visit(p->data);
    171.         p=p->next;
    172.     }
    173.     printf("\n");
    174.     return OK;
    175. }
    177. /*  随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
    178. void CreateListHead(LinkList *L, int n) 
    179. {
    180.     LinkList p;
    181.     int i;
    182.     srand(time(0));                         /* 初始化随机数种子 */
    183.     *L = (LinkList)malloc(sizeof(Node));
    184.     (*L)->next = NULL;                      /*  先建立一个带头结点的单链表 */
    185.     for (i=0; i<n; i++) 
    186.     {
    187.         p = (LinkList)malloc(sizeof(Node)); /*  生成新结点 */
    188.         p->data = rand()%100+1;             /*  随机生成100以内的数字 */
    189.         p->next = (*L)->next;    
    190.         (*L)->next = p;                        /*  插入到表头 */
    191.     }
    192. }
    194. /*  随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */
    195. void CreateListTail(LinkList *L, int n) 
    196. {
    197.     LinkList p,r;
    198.     int i;
    199.     srand(time(0));                      /* 初始化随机数种子 */
    200.     *L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */
    201.     r=*L;                                /* r为指向尾部的结点 */
    202.     for (i=0; i<n; i++) 
    203.     {
    204.         p = (Node *)malloc(sizeof(Node)); /*  生成新结点 */
    205.         p->data = rand()%100+1;           /*  随机生成100以内的数字 */
    206.         r->next=p;                        /* 将表尾终端结点的指针指向新结点 */
    207.         r = p;                            /* 将当前的新结点定义为表尾终端结点 */
    208.     }
    209.     r->next = NULL;                       /* 表示当前链表结束 */
    210. }
    212. int main()
    213. {        
    214.     LinkList L;
    215.     ElemType e;
    216.     Status i;
    217.     int j,k;
    218.     i=InitList(&L);
    219.     printf("初始化L后：ListLength(L)=%d\n",ListLength(L));
    220.     for(j=1;j<=5;j++)
    221.             i=ListInsert(&L,1,j);
    222.     printf("在L的表头依次插入1～5后：L.data=");
    223.     ListTraverse(L); 
    225.     printf("ListLength(L)=%d \n",ListLength(L));
    226.     i=ListEmpty(L);
    227.     printf("L是否空：i=%d(1:是 0:否)\n",i);
    229.     i=ClearList(&L);
    230.     printf("清空L后：ListLength(L)=%d\n",ListLength(L));
    231.     i=ListEmpty(L);
    232.     printf("L是否空：i=%d(1:是 0:否)\n",i);
    234.     for(j=1;j<=10;j++)
    235.             ListInsert(&L,j,j);
    236.     printf("在L的表尾依次插入1～10后：L.data=");
    237.     ListTraverse(L); 
    239.     printf("ListLength(L)=%d \n",ListLength(L));
    241.     ListInsert(&L,1,0);
    242.     printf("在L的表头插入0后：L.data=");
    243.     ListTraverse(L); 
    244.     printf("ListLength(L)=%d \n",ListLength(L));
    246.     GetElem(L,5,&e);
    247.     printf("第5个元素的值为：%d\n",e);
    248.     for(j=3;j<=4;j++)
    249.     {
    250.             k=LocateElem(L,j);
    251.             if(k)
    252.                     printf("第%d个元素的值为%d\n",k,j);
    253.             else
    254.                     printf("没有值为%d的元素\n",j);
    255.     }
    258.     k=ListLength(L); /* k为表长 */
    259.     for(j=k+1;j>=k;j--)
    260.     {
    261.             i=ListDelete(&L,j,&e); /* 删除第j个数据 */
    262.             if(i==ERROR)
    263.                     printf("删除第%d个数据失败\n",j);
    264.             else
    265.                     printf("删除第%d个的元素值为：%d\n",j,e);
    266.     }
    267.     printf("依次输出L的元素：");
    268.     ListTraverse(L); 
    270.     j=5;
    271.     ListDelete(&L,j,&e); /* 删除第5个数据 */
    272.     printf("删除第%d个的元素值为：%d\n",j,e);
    274.     printf("依次输出L的元素：");
    275.     ListTraverse(L); 
    277.     i=ClearList(&L);
    278.     printf("\n清空L后：ListLength(L)=%d\n",ListLength(L));
    279.     CreateListHead(&L,20);
    280.     printf("整体创建L的元素(头插法)：");
    281.     ListTraverse(L); 
    283.     i=ClearList(&L);
    284.     printf("\n删除L后：ListLength(L)=%d\n",ListLength(L));
    285.     CreateListTail(&L,20);
    286.     printf("整体创建L的元素(尾插法)：");
    287.     ListTraverse(L); 
    290.     return 0;
    291. }