线性表的顺序存储

线性表

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

线性表的顺序存储结构

1. 线性表的顺序存储结构，指的是用一段地址连续的 存储单元依次存储线性表的数据元素。
2. 简单说就是在内存中找了一块地方，通过占位的形式，把一定内存空间给占了。
3. 顺序存储结构的三个属性：
   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;
}

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 实现

// 结构体的构造函数
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();