C语言 数据结构与算法 线性表

数据结构中逻辑结构分线性和非线性。

线性表即为线性结构中的一种。

线性表的特性 百度百科解释在此。

个人总结为 有始有终，顺序排列，首尾不相连（像火车一样）。

线性表的基本操作如下：

初始化，销毁，重置为空表，判断是否为空，查找表的长度，

查找元素的位置，根据位置查找元素，查找元素的上一个元素，查找元素的下一个元素，

插入元素，删除元素，遍历元素。

下面是顺序存储结构的C实现。（有时间可以尝试下链式存储结构的实现）

1#include <stdio.h>
2#include <stdlib.h>
3
4#define TRUE 1
5#define FALSE 0
6#define OK 1
7#define ERROR 0
8#define INIT_SIZE 10        //初始化表长度
9#define INCREMENT_SIZE 5    //增量
10
11typedef int Status;
12typedef int Elemtype;
13
14/*
15 * 数据存贮结构
16 */
17typedef struct
18{
19    Elemtype *elem;    //存储空间基址
20    int length;        //当前长度
21    int size;        //当前分配的表长大小
22}SqList;
23
24/*
25 * 初始化线性表
26 */
27Status InitList(SqList *L)
28{
29    L->elem = (Elemtype *) malloc(INIT_SIZE * sizeof(Elemtype));
30    if (!L->elem)
31    {
32        return ERROR;
33    }
34    L->length = 0;
35    L->size = INIT_SIZE;
36    return OK;
37}
38
39/*
40 * 销毁
41 */
42Status DestroyList(SqList *L)
43{
44    free(L->elem);
45    L->length = 0;
46    L->size = 0;
47    return OK;
48}
49
50/*
51 * 清空
52 */
53Status ClearList(SqList *L)
54{
55    L->length = 0;
56    return OK;
57}
58
59/*
60 * 是否为空
61 */
62Status isEmpty(const SqList L)
63{
64    if (0 == L.length)
65    {
66        return TRUE;
67    }
68    else
69    {
70        return FALSE;
71    }
72}
73
74/*
75 * 获取表长
76 */
77Status getLength(const SqList L)
78{
79    return L.length;
80}
81
82/*
83 * 获取指定位置的元素
84 */
85Status GetElem(const SqList L, int i, Elemtype *e)
86{
87    if (i < 1 || i > L.length)
88    {
89        return ERROR;
90    }
91    *e = L.elem[i-1];
92    return OK;
93}
94
95/*
96 * 比较元素大小
97 */
98Status compare(Elemtype e1, Elemtype e2)
99{
100    if (e1 == e2)
101    {
102        return 0;
103    }
104    else if (e1 < e2)
105    {
106        return -1;
107    }
108    else
109    {
110        return 1;
111    }
112}
113
114/*
115 * 查找元素的位置
116 */
117Status FindElem(const SqList L, Elemtype e, Status (*compare)(Elemtype, Elemtype))
118{
119    int i;
120    for (i = 0; i < L.length; i++)
121    {
122        if (!(*compare)(L.elem[i], e))
123        {
124            return i + 1;
125        }
126    }
127    if (i >= L.length)
128    {
129        return ERROR;
130    }
131}
132
133/*
134 * 查找当前元素的前一个元素
135 */
136Status PreElem(const SqList L, Elemtype cur_e, Elemtype *pre_e)
137{
138    int i;
139    for (i = 0; i < L.length; i++)
140    {
141        if (cur_e == L.elem[i])
142        {
143            if (i != 0)
144            {
145                *pre_e = L.elem[i - 1];
146            }
147            else
148            {
149                return ERROR;
150            }
151        }
152    }
153    if (i >= L.length)
154    {
155        return ERROR;
156    }
157}
158
159/*
160 * 查找当前元素的下一个元素
161 */
162Status NextElem(const SqList L, Elemtype cur_e, Elemtype *next_e)
163{
164    int i;
165    for (i = 0; i < L.length; i++)
166    {
167        if (cur_e == L.elem[i])
168        {
169            if (i < L.length - 1)
170            {
171                *next_e = L.elem[i + 1];
172                return OK;
173            }
174            else
175            {
176                return ERROR;
177            }
178        }
179    }
180    if (i >= L.length)
181    {
182        return ERROR;
183    }
184}
185
186/*
187 * 插入元素
188 */
189Status InsertElem(SqList *L, int i, Elemtype e)
190{
191    Elemtype *new;
192    if (i < 1 || i > L->length + 1)
193    {
194        return ERROR;
195    }
196    if (L->length >= L->size)
197    {
198        new = (Elemtype*) realloc(L->elem, (L->size + INCREMENT_SIZE) * sizeof(Elemtype));
199        if (!new)
200        {
201            return ERROR;
202        }
203        L->elem = new;
204        L->size += INCREMENT_SIZE;
205    }
206    Elemtype *p = &L->elem[i - 1];
207    Elemtype *q = &L->elem[L->length - 1];
208    for (; q >= p; q--)
209    {
210        *(q + 1) = *q;
211    }
212    *p = e;
213    ++L->length;
214    return OK;
215}
216
217/*
218 * 删除元素
219 */
220Status DeleteElem(SqList *L, int i, Elemtype *e)
221{
222    if (i < 1 || i > L->length)
223    {
224        return ERROR;
225    }
226    Elemtype *p = &L->elem[i - 1];
227    *e = *p;
228    for (; p < &L->elem[L->length]; p++)
229    {
230        *(p) = *(p + 1);
231    }
232    --L->length;
233    return OK;
234}
235
236/*
237 * 访问元素
238 */
239void visit(Elemtype e)
240{
241    printf("%d ", e);
242}
243
244/*
245 * 遍历表
246 */
247Status TraverseList(const SqList L, void (*visit)(Elemtype))
248{
249    int i;
250    for(i = 0; i < L.length; i++)
251    {
252        visit(L.elem[i]);
253    }
254    return OK;
255}
256
257//测试
258int main()
259{
260    SqList L;
261    if (InitList(&L))
262    {
263        Elemtype e;
264        printf("init_success\n");
265        int i;
266        for (i=0; i<10; i++)
267        {
268             InsertElem(&L, i+1, i);
269        }
270        printf("length is %d\n", getLength(L));
271        if (GetElem(L, 1, &e)) {
272        printf("This first element is %d\n", e);
273        }
274        else
275        {
276            printf("element id not exist\n");
277        }
278        printf("The 5 at %d\n", FindElem(L, 5, *compare));
279        PreElem(L, 6, &e);
280        printf("The 6's previoud element is %d\n",e);
281        NextElem(L, 6, &e);
282     printf("The 6's next element is %d\n", e);
283        DeleteElem(&L, 1, &e);
284        printf("delete first element is %d\n",e);
285        TraverseList(L, visit);
286    if (DestroyList(&L))
287    {
288        printf("\ndestory_success");
289    }
290    }
291}

  看了几遍 终于通了，对新手来说其中比较难理解的地方就是插入元素 那个操作里的 位移操作 举例如下

list 里原本有 1 2  3 4 5  当需要插入 6 到 第二个位置 需要把 2 3 4 5 都往后移动 但是在上面的代码里移动的是元素地址 从最后一个开始 从高位往地位移动 所以比较难理解。