数据结构 线性表 代码

线性表是一种常见的基础数据结构，它是由n个相同类型的元素构成的有限序列。在计算机中，线性表可以使用数组或者链表来实现。

使用数组实现线性表的代码示例（以C语言为例）：

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

#define MAXSIZE 100 // 定义线性表的最大长度

typedef int ElementType; // 定义元素类型

typedef struct {
    ElementType data[MAXSIZE]; // 存储元素的数组
    int length; // 线性表当前长度
} SeqList;

// 初始化线性表
void InitList(SeqList *L) {
    L->length = 0;
}

// 在线性表L的第i个位置插入新元素e
int ListInsert(SeqList *L, int i, ElementType e) {
    if (L->length == MAXSIZE) {
        return 0; // 表满
    }
    if (i < 1 || i > L->length + 1) {
        return 0; // 位置不合法
    }
    for (int k = L->length - 1; k >= i - 1; k--) {
        L->data[k + 1] = L->data[k]; // 后移元素
    }
    L->data[i - 1] = e;
    L->length++;
    return 1;
}

// 其他线性表操作函数可以根据需要继续实现，如删除元素、查找元素等

使用链表实现线性表的代码示例（以C语言为例）：

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

typedef int ElementType; // 定义元素类型

typedef struct Node {
    ElementType data; // 数据域
    struct Node *next; // 指针域
} Node, *LinkedList;

// 初始化线性表
LinkedList InitList() {
    LinkedList L = (LinkedList)malloc(sizeof(Node));
    if (!L) {
        exit(1);
    }
    L->next = NULL;
    return L;
}

// 在链表L中的第i个位置插入新元素e
int ListInsert(LinkedList L, int i, ElementType e) {
    int j = 0;
    LinkedList p = L, s;
    while (p && j < i - 1) {
        p = p->next;
        ++j;
    }
    if (!p || j > i - 1) {
        return 0; // 位置不合法
    }
    s = (LinkedList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return 1;
}

// 其他线性表操作函数可以根据需要继续实现，如删除元素、查找元素等

线性表的实现可以通过数组或链表来完成，各有其特点和适用场景。数组实现的线性表可以实现随机访问，而链表实现的线性表在插入和删除操作时更为高效，因为它不需要移动大量的元素。