线性表：概念、顺序表实现与应用

线性表：概念、顺序表实现与应用

一、线性表的基本概念

线性表是一种极为基础且重要的数据结构哦。想象一下，它就像是一条排好队的队伍，队伍里的每个人或者说每个元素都是相同类型的呢。这个队伍可以很长，也可以很短，甚至可以一个人都没有（也就是空表啦）。在这个队伍里，除了排在最前面的第一个元素没有前面的伙伴，以及排在最后面的元素没有后面的伙伴外，其他的每个元素都恰好有一个紧挨着它前面的元素（这就是直接前驱哦），还有一个紧挨着它后面的元素（这就是直接后继啦）。比如说，一个班级学生的成绩按照顺序排列起来，就可以看作是一个线性表；或者你去超市列的购物清单，上面的商品一项一项地排着，这也是线性表哦。

二、顺序表的实现

（一）C 语言实现

首先呢，我们要知道顺序表在 C 语言里是怎么存储的哦。它其实就是用一个数组来存放这些元素的。我们先定义一个结构体，这个结构体就像是一个装着顺序表信息的盒子。

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

// 我们要先确定这个顺序表最多能放多少个元素，这就是最大长度啦
#define MAX_SIZE 100

// 这就是我们的顺序表结构体
typedef struct {
    int data[MAX_SIZE];  // 用来存放元素的数组，这里假设元素都是整数哦
    int length;  // 用来记录当前顺序表里面有多少个元素
} SeqList;

// 接下来我们要写一个函数来初始化这个顺序表，就像把一个空盒子准备好
void InitSeqList(SeqList *L) {
    L->length = 0;  // 一开始当然是没有元素啦，所以长度设为 0
}

// 然后是往顺序表里面插入元素的函数哦
int InsertSeqList(SeqList *L, int pos, int value) {
    // 先检查一下这个顺序表是不是已经满了，或者插入的位置是不是不对哦
    if (L->length >= MAX_SIZE || pos < 1 || pos > L->length + 1) {
        return 0;  // 如果有问题，就返回 0，表示插入失败
    }
    // 从最后一个元素开始，把后面的元素都往后挪一个位置，给要插入的元素腾出地方
    for (int i = L->length; i >= pos; i--) {
        L->data[i] = L->data[i - 1];
    }
    L->data[pos - 1] = value;  // 把要插入的元素放到指定的位置
    L->length++;  // 别忘了，顺序表的长度要加 1 哦
    return 1;  // 插入成功啦，返回 1
}

// 再写一个删除顺序表中元素的函数
int DeleteSeqList(SeqList *L, int pos) {
    // 先看看顺序表是不是空的，或者要删除的位置是不是不对
    if (L->length == 0 || pos < 1 || pos > L->length) {
        return 0;  // 如果有问题，就删除失败，返回 0
    }
    // 把要删除元素后面的元素都往前挪一个位置，就相当于把这个元素删掉啦
    for (int i = pos; i < L->length; i++) {
        L->data[i - 1] = L->data[i];
    }
    L->length--;  // 顺序表的长度也要减 1 哦
    return 1;  // 删除成功，返回 1
}

// 还有一个查找元素在顺序表中位置的函数
int SearchSeqList(SeqList *L, int value) {
    // 一个一个地找，看看哪个元素和我们要找的相等
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] == value) {
            return i + 1;  // 如果找到了，就返回它的位置，注意这里是从 1 开始计数的哦
        }
    }
    return 0;  // 如果没找到，就返回 0
}

// 最后写一个函数来打印顺序表，这样我们就能看到顺序表里面都有什么啦
void PrintSeqList(SeqList *L) {
    for (int i = 0; i < L->length; i++) {
        printf("%d ", L->data[i]);
    }
    printf("\n");
}

（二）Java 语言实现

在 Java 里，顺序表的实现也类似哦。我们先创建一个类来表示顺序表。

class SeqList {
    private int[] data;  // 用来存放元素的数组，这里也是假设元素是整数哦
    private int length;  // 记录顺序表中元素的个数
    private static final int MAX_SIZE = 100;  // 顺序表的最大长度

    // 构造函数，用来初始化顺序表
    public SeqList() {
        data = new int[MAX_SIZE];  // 创建数组
        length = 0;  // 初始长度为 0
    }

    // 插入元素的方法
    public boolean insert(int pos, int value) {
        // 检查顺序表是否已满，插入位置是否合法
        if (length >= MAX_SIZE || pos < 1 || pos > length + 1) {
            return false;
        }
        // 把元素往后挪，腾出位置
        for (int i = length; i >= pos; i--) {
            data[i] = data[i - 1];
        }
        data[pos - 1] = value;  // 插入元素
        length++;  // 长度加 1
        return true;
    }

    // 删除元素的方法
    public boolean delete(int pos) {
        // 检查顺序表是否为空，删除位置是否合法
        if (length == 0 || pos < 1 || pos > length) {
            return false;
        }
        // 把后面的元素往前挪
        for (int i = pos; i < length; i++) {
            data[i - 1] = data[i];
        }
        length--;  // 长度减 1
        return true;
    }

    // 查找元素位置的方法
    public int search(int value) {
        // 遍历数组找元素
        for (int i = 0; i < length; i++) {
            if (data[i] == value) {
                return i + 1;  // 找到就返回位置，从 1 开始计数
            }
        }
        return 0;  // 没找到返回 0
    }

    // 打印顺序表的方法
    public void print() {
        for (int i = 0; i < length; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }
}

三、顺序表的应用

（一）数据存储与管理

顺序表在数据存储和管理方面可是很有用的哦。比如说在学生成绩管理系统里，我们可以用顺序表来存学生的成绩信息。每个学生的成绩就像是顺序表中的一个元素，按照一定的顺序排列着。

（二）C 语言实现示例

#include <stdio.h>
#include "seqlist.c"  // 这里假设你的顺序表实现代码在 seqlist.c 文件里哦

int main() {
    SeqList studentScores;
    InitSeqList(&studentScores);  // 先初始化成绩顺序表

    // 插入学生成绩
    InsertSeqList(&studentScores, 1, 85);
    InsertSeqList(&studentScores, 2, 90);
    InsertSeqList(&studentScores, 3, 78);

    // 打印成绩列表，看看都有哪些成绩
    PrintSeqList(&studentScores);

    // 找一找成绩是 90 的在哪个位置
    int pos = SearchSeqList(&studentScores, 90);
    if (pos > 0) {
        printf("成绩 90 在第 %d 个位置\n", pos);
    } else {
        printf("未找到成绩 90\n");
    }

    // 把成绩是 78 的删掉
    DeleteSeqList(&studentScores, 3);

    // 再打印一次成绩列表，看看删掉后的情况
    PrintSeqList(&studentScores);

    return 0;
}

（三）Java 语言实现示例

public class SeqListApplication {
    public static void main(String[] args) {
        SeqList studentScores = new SeqList();  // 创建成绩顺序表对象

        // 插入学生成绩
        studentScores.insert(1, 85);
        studentScores.insert(2, 90);
        studentScores.insert(3, 78);

        // 打印成绩列表
        studentScores.print();

        // 查找成绩 90 的位置
        int pos = studentScores.search(90);
        if (pos > 0) {
            System.out.println("成绩 90 在第 " + pos + " 个位置");
        } else {
            System.out.println("未找到成绩 90");
        }

        // 删除成绩 78 的记录
        studentScores.delete(3);

        // 再次打印成绩列表
        studentScores.print();
    }
}

对于考研的同学们来说，线性表可是数据结构里的基础哦。一定要好好理解顺序表的这些知识，包括它的概念、实现方法还有应用场景。这样才能在考研的数据结构考试里应对自如哦。