线性表的顺序存储

线性表

线性表：零个或多个数据元素的有限序列。
首先它是一个序列，也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最以后一个元素无后继，其他每个元素都有且一个前驱和后继。

线性表的顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
简单说就是在内存中找了一块地方，通过占位的形式，把一定内存空间给占了。
顺序存储结构的三个属性：
1. 存储空间的起始位置
2. 线性表的最大存储空间
3. 线性表当前长度（元素的个数）

C 语言实现

#include <stdio.h>
#include <stdlib.h>

/*
 * 定义宏
 * LIST_LENGTH ：存放初始长度
 * LIST_CREMENT ：存放每次申请空间的大小
*/
#define LIST_LENGTH 100
#define LIST_CREMENT 20

// 类型重定义
typedef int tElem;      // 线性表元素的数据类型
typedef tElem * pElem;  // 元素指针
typedef struct List {
    pElem elem;         // 线性表存储元素
    int listLength;     // 线性表的长度
    int listSize;       // 线性表的空间大小
} List;
typedef enum Status     // 枚举数据
{
    ok = 1,Error = 0
} Status;


/*
 * 初始化线性表
 * 步骤：
 *  使用 malloc 为线性表申请空间
 *  判断是否申请成功
 *  对线性表的长度和空间进行初始化
*/
Status InitList(List * l)
{
    l->elem = (pElem) malloc(sizeof(tElem) * LIST_LENGTH);
    if(l->elem == 0)
    {
        printf("空间申请失败！");
        return Error;
    }

    l->listLength = 0;
    l->listSize += LIST_LENGTH;
}


/*
 * 判断线性表长度
 * 步骤：
 *  长度为 0 输出线性表为空
 *  否则输出线性表的长度
*/
void ListEmpty(List * l)
{
    if(l->listLength == 0)
    {
        printf("线性表为空 \n");
    }
    else
    {
        printf("线性表的长度为 %d\n",l->listLength);
    }
}


/*
 * 在线性表的第 i 个位置插入元素 e
 * 步骤：
 *  判断参数是否合法，若位置 i 小于 0 或大于线性表的长度，则参数不合法。
 *  判断空间是否充足，用线性表长度和空间作比较，若长度大于或等于线性表的空间则表示空间不足，使用 realloc 重新为线性表申请空间。
 *  判断空间是否申请成功，若成功则修改线性表的空间大小。
 *  遍历线性表，将元素插入线性表中。
 *  修改线性表的长度，长度自增
 *
*/
Status ListInsert(List * l,int i,tElem e)
{
    if(i < 0 || i > l->listLength)
    {
        printf("ListInsert() 参数错误！\n");
        return Error;
    }

    if(l->listLength >= l->listSize)
    {
        l->elem = (pElem) realloc(l,sizeof(tElem) * LIST_CREMENT);
        if(l->elem == 0)
        {
            printf("空间申请失败！");
            return Error;
        }
        else
        {
            l->listSize += LIST_CREMENT;
        }
    }

    for(int j = l->listLength; j > i; j++)
    {
        l->elem[j] = l->elem[j - 1];
    }
    l->elem[i] = e;
    l->listLength++;
    return ok;
}


/*
 * 获取第 i 个元素
 * 步骤：
 *  判断参数是否合法，若位置 i 小于 0 或大于线性表的长度，则参数不合法。
 *  打印第 i 个元素
*/
Status GetElem(List * l,int i)
{
    if(i < 0 || i > l->listLength)
    {
        printf("ListInsert() 参数错误！\n");
        return Error;
    }

    printf("线性表第 %d 个元素是 %d\n",i,l->elem[i]);
    return ok;
}


/*
 * 获取元素 e 前一个元素
 * 步骤：
 *  初始化一个位置 i = -1，遍历线性表获取元素 e 的位置
 *  判断 i 的值：
 *      i = -1 表示元素 e 不在线性表中；
 *      i = 0 表示元素 e 是线性表的第一个元素，无前一个元素；
 *      否则打印元素 e 前一个元素
*/
Status PriorElem(List * l,tElem e)
{
    int i = -1;
    for(int j = 0; j < l->listLength; j++)
    {
        if(l->elem[j] == e) i = j;
    }
    if(i == -1)
    {
        printf("元素 %d 不在线性表中！\n",e);
        return Error;
    }
    else if (i == 0)
    {
        printf("元素 %d 是线性表的第一个元素，无前一个元素！\n",e);
        return Error;
    }
    else
    {
        printf("元素 %d 的前一个元素是：%d\n",e,l->elem[i-1]);
        return ok;
    }
}


/*
 * 获取元素 e 的后一个元素
 * 步骤：
 *  初始化一个位置 i = -1，遍历线性表获取元素 e 的位置
 *  判断 i 的值：
 *      i = -1 表示元素 e 不在线性表中；
 *      i 等于线性表长度减 1 表示元素 e 是线性表的最后一个元素，无后一个元素；
 *      否则打印元素 e 后一个元素
*/
Status NextElem(List * l,tElem e)
{
    int i = -1;
    for(int j = 0; j < l->listLength; j++)
    {
        if(l->elem[j] == e) i = j;
    }
    if(i == -1)
    {
        printf("元素 %d 不在线性表中！\n",e);
        return Error;
    }
    else if (i == l->listLength - 1)
    {
        printf("元素 %d 是线性表的最后一个元素，无后一个元素！\n",e);
        return Error;
    }
    else
    {
        printf("元素 %d 的后一个元素是：%d\n",e,l->elem[i+1]);
        return ok;
    }
}


/*
 * 遍历线性表
 * 步骤：
 *  判断线性表是否为空表。
 *  循环遍历，输出线性表索引和元素。
*/
void ListTraverse(List * l)
{
    if(l->listLength > 0)
    {
        for(int i = 0; i < l->listLength; i++)
        {
            printf("线性表的第 %d 个元素是：%d\n",i,l->elem[i]);
        }
    }
    else
    {
        printf("线性表为空！\n");
    }
}

/*
 * 删除第 i 个元素
 * 步骤：
 *  判断参数是否合法，若位置 i 小于 0 或大于线性表的长度，则参数不合法。
 *  遍历 i 后面线性表，用后一个元素替代前一个元素。
 *  修改线性表的长度。
*/
Status ListDelete(List * l,int i)
{
    if(i < 0 || i > l->listLength)
    {
        printf("ListInsert() 参数错误！\n");
        return Error;
    }

    for(int j = i; j < l->listLength; j++)
    {
        l->elem[j] = l->elem[j + 1];
    }

    l->listLength --;
    return ok;
}


/*
 * 清空线性表
 * 步骤：
 *  修改线性表的长度为 0
*/
void ClearList(List * l)
{
    l->listLength = 0;
}

/*
 * 销毁线性表
 * 步骤：
 *  释放线性表空间。
 *  修改线性表的长度为 0
 *  修改线性表空间大小为 0
*/
void DestroyList(List * l)
{
    free(l->elem);
    l->listLength = 0;
    l->listSize = 0;
}

int main() {
    List plist;

    // 初始化线性表
    InitList(&plist);

    // 判断线性表的长度
    printf("第一次判断线性表的长度：");
    ListEmpty(&plist);
    printf("\n");

    // 插入元素
    ListInsert(&plist,0,12);
    ListInsert(&plist,1,23);
    ListInsert(&plist,2,34);
    printf("第二次判断线性表的长度：");
    ListEmpty(&plist);
    printf("\n");

    // 获取第 i 个元素
    GetElem(&plist,1);
    printf("\n");

    // 获取元素 e 的前一个元素
    PriorElem(&plist,10);
    PriorElem(&plist,12);
    PriorElem(&plist,34);
    printf("\n");

    // 获取元素 e 的后一个元素
    NextElem(&plist,10);
    NextElem(&plist,34);
    NextElem(&plist,12);
    printf("\n");

    // 遍历线性表
    ListTraverse(&plist);
    printf("\n");

    // 删除第 i 个元素
    ListDelete(&plist,0);
    ListTraverse(&plist);
    printf("\n");

    // 清空线性表
    ClearList(&plist);
    ListTraverse(&plist);
    printf("\n");

    DestroyList(&plist);
    ListTraverse(&plist);
    printf("\n");

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319

Java

java

package Linear;
import java.util.*;

public class Demo01 {
    public static void main(String[] args) {
        order list = new order();
        list.InitList();
        list.Insert(0,20);
        list.Insert(0,10);
        list.Insert(2,30);
        System.out.printf("插入元素后，长度为 %d\n",list.data.length);
        list.PrintList();
        list.GetItem(2);
        list.PriorElem(20);
        list.NextElem(20);
        list.DelItem(1);
        System.out.println("删除元素后：");
        list.PrintList();
        list.ClearList();
        System.out.println("清空元素后：");
        list.PrintList();
    }
}

class order {
    int len = 0;        // 元素个数
    int size = 0;       // 空间大小
    int create = 10;    // 扩容幅度
    int[] data;         // 数据

    // 初始化
    public void InitList() {
        this.size += this.create;
        this.data = new int[this.size];
    }

    // 在第 i 个位置插入元素 e
    public void Insert(int i,int e) {
        if (i > this.len) {
            System.out.println("Insert() Parameter Error");
            return;
        }
        if (this.len >= this.size) {
            this.size += this.create;
            this.data = Arrays.copyOf(this.data,this.size);
        }
        for (int j = this.len; j > i; j--) this.data[j] = this.data[j - 1];
        this.data[i] = e;
        this.len++;
    }

    // 遍历线性表
    public void PrintList() {
        int i = 0;
        if (this.len == 0) {
            System.out.println("------ 线性表为空 ------");
            return;
        }
        while (i < this.len) {
            System.out.printf("\t线性表的第 %d 个元素是 %d\n",i,this.data[i]);
            i++;
        }
    }

    // 获取第 i 个元素
    public void GetItem(int i) {
        if (i >= this.len) {
            System.out.println("GetItem() Parameter Error");
            return;
        }
        System.out.printf("取出元素：线性表的第 %d 个元素是 %d\n",i,this.data[i]);
    }

    // 返回元素位置 (-1)-不存在
    public int GetIndex(int e) {
        int index = -1;
        int i = 0;
        while (i < this.len) {
            if (this.data[i] == e) {
                index = i;
                break;
            }
            i++;
        }
        return index;
    }

    // 获取元素 e 的前一个元素
    public void PriorElem(int e) {
        int index = this.GetIndex(e);
        if (index == -1) {
            System.out.printf("元素 %d 不在线性表中\n",e);
            return;
        }
        if (index == 0) {
            System.out.printf("元素 %d 是线性表的第一个元素，无前一个元素\n",e);
            return;
        }
        System.out.printf("元素 %d 的前一个元素是 %d\n",e,this.data[index - 1]);
    }

    // 获取元素 e 的前一个元素
    public void NextElem(int e) {
        int index = this.GetIndex(e);
        if (index == -1) {
            System.out.printf("元素 %d 不在线性表中\n",e);
            return;
        }
        if (index == this.len - 1) {
            System.out.printf("元素 %d 是线性表的最后一个元素，无后一个元素\n",e);
            return;
        }
        System.out.printf("元素 %d 的后一个元素是 %d\n",e,this.data[index + 1]);
    }

    // 删除一个元素
    public void DelItem(int i) {
        if (i >= this.len) {
            System.out.println("DelItem() Parameter Error");
            return;
        }
        for (int j = i; j < this.len; j++) this.data[j] = this.data[j + 1];
        this.len--;
    }

    // 清空线性表
    public void ClearList() {
        this.len = 0;
        this.size = 0;
    }
}

JavaScript 实现

javascript

// 结构体的构造函数
function ListNode() {
    this.data = [];
    this.len = 0;
}

// 线性表变量
let list;

/**
 * @description: 在指定位置插入元素
 * @param {*} i 位置
 * @param {*} e 元素
 */
const Insert = (i, e) => {
    if (i > list.len) {
        console.log("Insert() Parameter Error");
        return;
    }

    if (!list.len) {
        list.data[0] = e;
    } else {
        for (let j = list.len; j > i; j--) list.data[j] = list.data[j - 1];
        list.data[i] = e;
    }
    list.len++;
}

/**
 * @description: 获取指定位置的元素
 * @param {*} i 位置
 * @return {*} 元素
 */
const GetItem = (i) => {
    if (i > list.len) {
        console.log("GetItem() Parameter Error");
        return;
    }
    return list.data[i];
}

/**
 * @description: 获取元素位置
 * @param {*} e 元素
 * @return {*} 位置
 */
const GetItemIndex = (e) => {
    let i = -1;
    for (let index in list.data) {
        let item = list.data[index];
        if (item === e) i = index;
    }
    return i * 1;
}

/**
 * @description: 获取指定元素的前一个元素
 * @param {*} e 指定元素
 * @return {*} 前一个元素
 */
const PriorElem = (e) => {
    let index = GetItemIndex(e);
    if (index === -1) {
        console.log(`元素 ${e} 不在线性表中`);
        return;
    }
    if (!index) {
        console.log(`元素 ${e} 是线性表的第一个元素，无前一个元素`);
        return;
    }
    return list.data[index - 1];
}

/**
 * @description: 获取指定元素的后一个元素
 * @param {*} e 指定元素
 * @return {*} 后一个元素
 */
const NextElem = (e) => {
    let index = GetItemIndex(e);
    if (index === -1) {
        console.log(`元素 ${e} 不在线性表中`);
        return;
    }
    if (index === list.len - 1) {
        console.log(`元素 ${e} 是线性表的最后一个元素，无后一个元素`);
        return;
    }
    return list.data[index + 1];
}

/**
 * @description: 遍历线性表
 */
const ErgodicList = () => {
    for (let i = 0; i < list.len; i++) {
        console.log(`\t线性表的第 ${i} 个元素是 ${list.data[i]}`);
    }
}

/**
 * @description: 删除第 i 个位置的元素
 * @param {*} i 位置
 */
const DelIndex = (i) => {
    if (i > list.len) {
        console.log("DelIndex() Parameter Error");
        return;
    }
    for (let j = i; j < list.len; j++) {
        list.data[j] = list.data[j + 1];
    }
    list.len--;
    console.log(`第 ${i} 个元素删除成功`);
}

/**
 * @description: 清空线性表
 */
const ClearList = () => {
    list.data.length = 0;
    list.len = 0;
}

// 入口函数
const main = () => {
    list = new ListNode();
    Insert(0, 10);
    Insert(1, 20);
    Insert(1, 30);
    console.log("插入元素后：", list);

    let eIndex = 1;
    GetItem(eIndex) ? console.log(`获取元素：线性表的第 ${eIndex} 个元素是 ${GetItem(eIndex)}`) : '';

    let eItem = 30;
    PriorElem(eItem) ? console.log(`元素 ${eItem} 的前一个元素是 ${PriorElem(eItem)}`) : '';
    NextElem(eItem) ? console.log(`元素 ${eItem} 的后一个元素是 ${NextElem(eItem)}`) : '';

    console.log("遍历线性表：");
    ErgodicList();

    DelIndex(1);
    ErgodicList();

    ClearList();
    console.log("清空元素后：", list);

}

main();

线性表 ​