1 // 2018-06-22  2 // 线性表顺序存储实现-动态数组  3 #include
     
        4 #include
      
         5   6 #define LIST_INIT_SIZE 5  // 符号常量 ，线性表存储空间的初试分配量  7 #define LIST_INCREMENT 10 // 符号常量 ，线性表存储空间的分配增量  8   9 #define OK 1 10 #define ERROR 0 11 #define TRUE 1 12 #define FALSE 0 13  14 typedef int ElemType; 15 typedef int Status; 16  17 typedef struct sqList 18 { 19     ElemType *elem;    // 存储空间基地址 20     int length;        // 线性表当前长度 21     int listsize;    // 当前分配的存储容量 22 }SqList; 23  24  25 /* 26 Status InitList(SqList *L); 27 Status ListInsert(SqList *L,int i,ElemType e); 28 Status ListTraverse(SqList L); 29 Status ListEmpty(SqList L); 30 Status ClearList(SqList *L); 31 Status GetElem(SqList L,int i,ElemType *e); 32 int LocateElem(SqList L,ElenType e); 33 Status ListDelete(SqList *L,int i,ElemType *e); 34 int ListLength(SqList L); 35 void UnionL(SqList *La,SqList Lb); 36 */ 37  38 // 初始化线性表 39 Status InitList(SqList *L) 40 { 41     L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); 42     if (!(L->elem)) 43         return ERROR; 44     L->length = 0;                     // 空表长度为0 45     L->listsize = LIST_INIT_SIZE;     // 初始化存储容量 46  47     return OK; 48 } 49  50 // 在 L 中第 i 个位置插入新的数据元素 e ，L 的长度增加 1 51 Status ListInsert(SqList *L, int i, ElemType e) 52 { 53     ElemType *newbase; 54     int k; 55  56     if (L->length == L->listsize) 57     { 58         // realloc(void *__ptr, size_t __size) 59         // 更改已经配置的内存空间，即更改由malloc()函数分配的内存空间的大小 60         newbase = (ElemType *)realloc(L->elem, (L->listsize + LIST_INCREMENT) * sizeof(ElemType)); 61         if (!newbase) 62             return ERROR; 63         L->elem = newbase; 64         L->listsize += LIST_INCREMENT; 65     } 66  67     if (!(i >= 1 && i <= L->length + 1)) 68         return ERROR; 69  70     if (i != L->length + 1)    // 插入的位置不在表尾 71     { 72         for (k = L->length - 1; k >= i - 1; k--) 73             *(L->elem + k + 1) = *(L->elem + k); 74     } 75     *(L->elem + i - 1) = e; 76     L->length++; 77     return OK; 78 } 79  80 Status ListTraverse(SqList L) 81 { 82     int i; 83     for (i = 0; i < L.length; i++) 84     { 85         printf("%d ", *(L.elem++)); 86     } 87     printf("\n"); 88     return OK; 89 } 90  91 Status ListEmpty(SqList L) 92 { 93     if (L.length == 0) 94         return OK; 95     else 96         return ERROR; 97 } 98  99 Status ClearList(SqList *L)100 {101     L->length = 0;102     return OK;103 }104 105 Status GetElem(SqList L, int i, ElemType *e)106 {107     if (L.length == 0) return ERROR;108     if (!(i >= 1 && i < L.length)) return ERROR;109     *e = *(L.elem + i - 1);110     return OK;111 }112 113 // 返回L中第1个与e满足关系的数据元素的位序114 int LocateElem(SqList L, ElemType e)115 {116     int i;117     if (L.length == 0)118         return 0;119     for (i = 0; i < L.length; i++)120     {121         if (*(L.elem + i) == e)122             return i + 1;123     }124     return 0;125 }126 127 Status ListDelete(SqList *L, int i, ElemType *e)128 {129     int k;130     if (L->length == 0) return ERROR;131     if (!(i >= 1 && i <= L->length)) return ERROR;132 133     *e = *(L->elem + i - 1);134     if (i != L->length)135     {136         for (k = i; k <= L->length - 1; k++)137         {138             *(L->elem + k - 1) = *(L->elem + k);139         }140     }141     L->length--;142     return OK;143 }144 145 int ListLength(SqList L)146 {147     return L.length;148 }149 150 void UnionL(SqList *La, SqList Lb)151 {152     int La_len, Lb_len, i;153     ElemType e;154 155     La_len = ListLength(*La);156     Lb_len = ListLength(Lb);157 158     for (i = 1; i <= Lb_len; i++)159     {160         GetElem(Lb, i, &e);161         if (!LocateElem(*La, e))162             ListInsert(La, ++La_len, e);163     }164 }165 166 int main()167 {168     SqList La, Lb;169     int i, j, k;170     ElemType e;171 172     i = InitList(&La);173 174     for (j = 1; j <= 5; j++)175         ListInsert(&La, 1, j);176     printf("在L的表头插入1~5后，L->data = ");177     ListTraverse(La);178     printf("\n");179 180     printf("L.length = %d\n", La.length);181     i = ListEmpty(La);182     printf("L是否为空：i = %d (1:是 0：否)\n",i);183     printf("\n");184 185     i = ClearList(&La);186     printf("清空L后，L.length = %d\n", La.length);187     i = ListEmpty(La);188     printf("L是否为空：i = %d (1:是 0：否)\n", i);189     printf("\n");190 191     for ( j = 0; j <= 10; j++)192         ListInsert(&La, j, j);193     printf("在L的表头插入1~10后，L->data = ");194     ListTraverse(La);195     printf("L.length = %d\n",La.length);196     printf("\n");197 198     i = ListInsert(&La, 1, 0);199     printf("在L的表头插入0后，L.data = ");200     ListTraverse(La);201     printf("L.length = %d\n", La.length);202     printf("\n");203 204     GetElem(La, 5, &e);205     printf("第 5 个元素的值为:%d\n", e);206     printf("\n");207 208     for ( j = 3; j <= 4; j++)209     {210         k = LocateElem(La, j); // 查找位序211         if (k)212             printf("元素%d的位序是%d\n", j, k);213         else214             printf("没有值为%d的元素\n", j);215     }216     j = 9;217     i = ListDelete(&La, j, &e);218     if (i == ERROR)219         printf("删除第%d个数据失败\n", j);220     else221         printf("删除第%d个元素的值为：%d\n", j, e);222     printf("L.length = %d\n", La.length);223     printf("L.data = ");224     ListTraverse(La);225     printf("\n");226 227     k = ListLength(La);228     j = k + 1; // 删除第length+1个元素229     i = ListDelete(&La, j, &e);230     if (i == ERROR)231         printf("删除第%d个数据失败\n", j);232     else233         printf("删除第%d个元素的值为%d\n", j, e);234     i = InitList(&Lb);235     for ( j = 8; j <= 15; j++)236         i = ListInsert(&Lb, 1, j);237     printf("依次输出Lb的元素:");238     ListTraverse(Lb);239     printf("\n");240     UnionL(&La, Lb);241     printf("L.length = %d\n", La.length);242     printf("依次输出合并之后的L.data = ");243     ListTraverse(La);244     printf("\n");245 246     getchar();247     return 0;248 }