线性表的顺序实现

线性表（linear_list）：

n个数据元素的有限序列
每个数据元素由若干数据项（item）组成，常将数据元素称为记录（record），含有大量记录
的线性表又称为文件。

线性表的顺序实现：

用一组地址连续的存储单元依次存储线性表的数据元素。
再用C语言实现时，需要在线性表初始化时分配一定大小的初始存储空间，但随着初始空间
被占用，需要考虑每次线性表空间增量的问题，下面实现仅仅是简单的选择一个空间增量，
在线性表满时重新分配空间。

顺序表的优缺点：
可以随机取表中任一元素，它的存储位置可用简单直观的公式表示：base + (pos-1) * sizeof(ElemType)
在插入与删除时需移动大量元素

顺序表的实现及相关操作：

（也可以直接在作者GitHub上查看，可能会看着舒服）

 1 // 线性表的顺序实现 
 2 
 3 #define ElemType int          // ElemType作为线性表以及之后其他容器内存储的元素的数据类型，本实现中使用int
 4 
 5 // 线性表的顺序实现
 6 #define LIST_INIT_SIZE 100    // 线性表存储空间的初始分配量
 7 #define LISTINCREMENT 10      // 线性表存储空间的分配增量
 8 typedef struct {
 9     ElemType *elem;           // 存储空间基址
10     int length;               // 线性表当前所用长度
11     int listsize;             // 当前分配的存储容量为 listsize * sizeof(ElemType)
12 }SqList;
13 
14 // 相关操作
15 
16 // 构造一个空的线性表
17 bool InitSqList(SqList *sqlist);
18 
19 // 在指定线性表存在的前提下：
20 
21 // 销毁指点线性表
22 void DestorySqList(SqList *sqlist);
23 
24 // 判断线性表是否为空
25 bool SqListEmpty(SqList *sqlist);
26 
27 // 获取指定线性表中元素个数
28 int SqListLength(SqList *sqlist);
29 
30 // 在线性表中指定位置元素存在的情况下返回该元素值
31 bool GetElem(SqList *sqlist, int i, ElemType *elem);
32 
33 // 返回指定元素在线性表中第一次出现的位置
34 bool LocateElem(SqList *sqlist, ElemType elem, int *pos);
35 
36 // 若指定元素在线性表中存在，且不是线性表中的第一个元素，返回该指定元素第一次出现位置的前一个元素
37 bool PriorElem(SqList *sqlist, ElemType cur_elem, ElemType *pr_elem);
38 
39 // 若指定元素在线性表中存在，且不是线性表中的最后一个元素，返回该指定元素第一次出现位置的后一个元素
40 bool NextElem(SqList *sqlist, ElemType cur_elem, ElemType *next_elem);
41 
42 // 在线性表指定位置插入新元素
43 bool SqListInsert(SqList *sqlist, int pos, ElemType elem);
44 
45 // 删除线性表指定位置元素，并返回该元素
46 bool SqListDelete(SqList *sqlist, int pos, ElemType *elem);
47 
48 // 遍历线性表，此处实现仅仅是将其输出到标准输出，若需要，可选择输出到文件等
49 void SqListTraverse(SqList *sqlist);
50 
51 // 增加线性表容量
52 bool SqListExtend(SqList *sqlist);
53 
54 // 将两个排好序的顺序表合并(默认从大到小排序)
55 bool MergeSqList(SqList *sq1, SqList *sq2, SqList *mersq);

  1 bool InitSqList(SqList *sqlist)
  2 {
  3     sqlist->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
  4 
  5     if (!sqlist->elem)
  6         return false;    // malloc失败
  7 
  8     sqlist->length = 0;
  9     sqlist->listsize = LIST_INIT_SIZE;    // 线性表初始长度
 10 
 11     return true;
 12 }
 13 
 14 void DestorySqList(SqList *sqlist)
 15 {
 16     free(sqlist->elem);
 17     sqlist->elem = NULL;
 18     sqlist->length = 0;
 19     sqlist->listsize = 0;
 20     // 此处释放分配给该线性表的存储空间，并将该线性表的length、listsize清零
 21 }
 22 
 23 bool SqListEmpty(SqList *sqlist)
 24 {
 25     if (sqlist->length)
 26         return false;
 27 
 28     return true;
 29 }
 30 
 31 int SqListLength(SqList *sqlist)
 32 {
 33     return sqlist->length;
 34 }
 35 
 36 bool GetElem(SqList *sqlist, int pos, ElemType *elem)
 37 {
 38     if (pos > sqlist->length || pos < 1)
 39         return false;
 40     
 41     *elem = sqlist->elem[pos - 1];
 42     
 43     return true;
 44 }
 45 
 46 bool LocateElem(SqList *sqlist, ElemType elem, int *pos)
 47 {
 48     int i = 0;
 49     for (; i < sqlist->length; i++) {
 50         if (sqlist->elem[i] == elem) {
 51             *pos = i + 1;          // 返回elem第一次出现的位置 i+1
 52             return true;
 53         }
 54     }
 55     
 56     // 线性表中不存在元素elem
 57     *pos = 0;
 58     return false;
 59 }
 60 
 61 bool PriorElem(SqList *sqlist, ElemType cur_elem, ElemType *pr_elem)
 62 {
 63     int i = 0;
 64 
 65     for (; i < sqlist->length; i++) {
 66         if (i != 0 && sqlist->elem[i] == cur_elem) {
 67             *pr_elem = sqlist->elem[i - 1];
 68             return true;
 69         }
 70     }
 71 
 72     return false;
 73 }
 74 
 75 bool NextElem(SqList *sqlist, ElemType cur_elem, ElemType *next_elem)
 76 {
 77     int i = 0;
 78 
 79     for (; i < sqlist->length - 1; i++) {
 80         if (cur_elem == sqlist->elem[i]) {
 81             *next_elem = sqlist->elem[i + 1];
 82             return true;
 83         }
 84     }
 85 
 86     return false;
 87 }
 88 
 89 bool SqListInsert(SqList *sqlist, int pos, ElemType elem)
 90 {
 91     // 若在线性表已满的情况下插入元素，需要先对线性表做扩从操作
 92     if (pos < 1 || pos > sqlist->length + 1)
 93         return false;    // 插入位置非法
 94 
 95     if (sqlist->length == sqlist->listsize) {
 96         if (!SqListExtend(sqlist)) {
 97             return false;    // realloc出错
 98         }
 99     }
100 
101     int i = sqlist->length;
102     for (; i >= pos; i--) {
103         sqlist->elem[i] = sqlist->elem[i - 1];
104     }
105 
106     sqlist->elem[pos - 1] = elem;
107     sqlist->length++;
108 
109     return true;
110 }
111 
112 bool SqListDelete(SqList *sqlist, int pos, ElemType *elem)
113 {
114     if (pos < 1 || pos > sqlist->length) {
115         return false;    // 删除位置出错 
116     }
117 
118     int i = pos - 1;
119     *elem = sqlist->elem[i];
120     for (; i < sqlist->length - 1; i++) {
121         sqlist->elem[i] = sqlist->elem[i + 1];
122     }
123 
124     sqlist->length--;
125 
126     return true;
127 }
128 
129 void SqListTraverse(SqList *sqlist)
130 {
131     int i;
132 
133     for (i = 0; i < sqlist->length; i++) {
134         printf("%d
", sqlist->elem[i]);
135     }
136 }
137 
138 bool SqListExtend(SqList *sqlist)
139 {
140     ElemType *newbase = (ElemType *)realloc(sqlist->elem, (sqlist->listsize + LISTINCREMENT) * sizeof(ElemType));
141 
142     if (!newbase)
143         return false;
144 
145     sqlist->elem = newbase;
146     sqlist->listsize += LISTINCREMENT;
147 
148     return true;
149 }
150 
151 bool MergeSqList(SqList *sq1, SqList *sq2, SqList *mersq)
152 {
153     mersq->elem = (ElemType *)malloc((sq1->length + sq2->length) * sizeof(ElemType));
154 
155     if (!mersq->elem)
156         return false;    // malloc失败
157 
158     mersq->length = 0;
159     mersq->listsize = sq1->length + sq2->length;
160 
161     int pos = 1, j = 0, k = 0;
162 
163     while (j < sq1->length - 1 && k < sq2->length) {
164         if (sq1->elem[j] <= sq2->elem[k]) {
165             if (!SqListInsert(mersq, pos++, sq1->elem[j]))
166                 return false;    // 插入错误
167 
168             ++j;
169         }
170         else {
171             if (!SqListInsert(mersq, pos++, sq2->elem[k]))
172                 return false;    // 插入错误
173 
174             ++k;
175         }
176     }
177 
178     // 插入剩余元素
179     while (j < sq1->length) {
180         if (!SqListInsert(mersq, pos++, sq1->elem[j]))
181             return false;    // 插入错误
182 
183         ++j;
184     }
185 
186     while (k < sq2->length) {
187         if (!SqListInsert(mersq, pos++, sq2->elem[k]))
188             return false;    // 插入错误
189 
190         ++k;
191     }
192 
193     return true;
194 }

测试程序与测试结果：

#include "linear_list.h"
#include "normalHead.h"

int main(void)
{
    SqList sqlist;
    if (InitSqList(&sqlist))
        printf("Init.. 
");

    int i;
    for (i = 0; i < 10; i++) {
        SqListInsert(&sqlist, i + 1, i + 1);
    }

    printf("Length = %d
", SqListLength(&sqlist));

    if (!SqListEmpty(&sqlist)) {
        printf("Not Empty!
");
    }

    int ele;
    if (GetElem(&sqlist, 5, &ele))
        printf("ele = %d
", ele);

    int pos;
    if (LocateElem(&sqlist, ele, &pos))
        printf("pos = %d
", pos);

    int pre;
    if (PriorElem(&sqlist, 5, &pre))
        printf("pre = %d
", pre);

    int next;
    if (NextElem(&sqlist, 5, &next))
        printf("next = %d
", next);

    int del;
    if (SqListDelete(&sqlist, 5, &del))
        printf("del = %d
", del);

    SqListTraverse(&sqlist);

    printf("
");

    SqList sq1, sq2, sq3;
    InitSqList(&sq1);
    InitSqList(&sq2);

    i = 1;

    for (; i <= 5; ++i) {
        SqListInsert(&sq1, i, 2 * i - 1);
        SqListInsert(&sq2, i, 2 * i);
    }

    MergeSqList(&sq1, &sq2, &sq3);

    SqListTraverse(&sq1);
    printf("
");
    SqListTraverse(&sq2);
    printf("
");
    SqListTraverse(&sq3);

    getchar();
    return 0;
}

/*
输出：
Init..
Length = 10
Not Empty!
ele = 5
pos = 5
pre = 4
next = 6
del = 5
1
2
3
4
6
7
8
9
10

1
3
5
7
9

2
4
6
8
10

1
2
3
4
5
6
7
9
8
10
*/