线性表顺序存储实现-动态数组

  1 // 2018-06-22
  2 // 线性表顺序存储实现-动态数组
  3 #include<stdio.h>
  4 #include<stdlib.h>
  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("
");
 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("
");
179 
180     printf("L.length = %d
", La.length);
181     i = ListEmpty(La);
182     printf("L是否为空：i = %d (1:是 0：否)
",i);
183     printf("
");
184 
185     i = ClearList(&La);
186     printf("清空L后，L.length = %d
", La.length);
187     i = ListEmpty(La);
188     printf("L是否为空：i = %d (1:是 0：否)
", i);
189     printf("
");
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
",La.length);
196     printf("
");
197 
198     i = ListInsert(&La, 1, 0);
199     printf("在L的表头插入0后，L.data = ");
200     ListTraverse(La);
201     printf("L.length = %d
", La.length);
202     printf("
");
203 
204     GetElem(La, 5, &e);
205     printf("第 5 个元素的值为:%d
", e);
206     printf("
");
207 
208     for ( j = 3; j <= 4; j++)
209     {
210         k = LocateElem(La, j); // 查找位序
211         if (k)
212             printf("元素%d的位序是%d
", j, k);
213         else
214             printf("没有值为%d的元素
", j);
215     }
216     j = 9;
217     i = ListDelete(&La, j, &e);
218     if (i == ERROR)
219         printf("删除第%d个数据失败
", j);
220     else
221         printf("删除第%d个元素的值为：%d
", j, e);
222     printf("L.length = %d
", La.length);
223     printf("L.data = ");
224     ListTraverse(La);
225     printf("
");
226 
227     k = ListLength(La);
228     j = k + 1; // 删除第length+1个元素
229     i = ListDelete(&La, j, &e);
230     if (i == ERROR)
231         printf("删除第%d个数据失败
", j);
232     else
233         printf("删除第%d个元素的值为%d
", 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("
");
240     UnionL(&La, Lb);
241     printf("L.length = %d
", La.length);
242     printf("依次输出合并之后的L.data = ");
243     ListTraverse(La);
244     printf("
");
245 
246     getchar();
247     return 0;
248 }