数据结构线性表代码++++完整版

以下是一个完整版的线性表代码，包括顺序表和链表两种实现方式：

1. 顺序表实现：

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

typedef struct {
    int data[MaxSize]; // 存储线性表元素的数组
    int length; // 线性表的当前长度
} SqList; // 顺序表类型定义

// 初始化线性表
void InitList(SqList &L) {
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = 0; // 将所有元素初始化为0
    }
    L.length = 0; // 线性表长度初始化为0
}

// 插入元素
bool ListInsert(SqList &L, int i, int e) {
    if (i < 1 || i > L.length + 1) { // 判断插入位置是否合法
        return false;
    }
    if (L.length >= MaxSize) { // 判断线性表是否已满
        return false;
    }
    for (int j = L.length; j >= i; j--) { // 将插入位置后的元素依次后移
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e; // 将新元素插入到指定位置
    L.length++; // 线性表长度加1
    return true;
}

// 删除元素
bool ListDelete(SqList &L, int i, int &e) {
    if (i < 1 || i > L.length) { // 判断删除位置是否合法
        return false;
    }
    e = L.data[i - 1]; // 将被删除的元素赋值给e
    for (int j = i; j < L.length; j++) { // 将删除位置后的元素依次前移
        L.data[j - 1] = L.data[j];
    }
    L.length--; // 线性表长度减1
    return true;
}

// 查找元素
int LocateElem(SqList L, int e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1; // 返回元素在线性表中的位置
        }
    }
    return 0; // 没有找到返回0
}

2. 链表实现：

typedef struct Node {
    int data; // 存储数据元素
    struct Node *next; // 存储下一个节点的指针
} LNode, *LinkList; // 链表节点类型定义和链表类型定义

// 初始化链表
void InitList(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode)); // 创建头节点
    L->next = NULL; // 头节点的指针域初始化为NULL
}

// 插入元素
bool ListInsert(LinkList &L, int i, int e) {
    LinkList p = L, s; // p指向头节点，s为新节点
    int j = 0;
    while (p && j < i - 1) { // 寻找第i-1个节点
        p = p->next;
        j++;
    }
    if (!p || j > i - 1) { // 判断插入位置是否合法
        return false;
    }
    s = (LinkList)malloc(sizeof(LNode)); // 创建新节点
    s->data = e; // 将新元素赋值给新节点
    s->next = p->next; // 将新节点插入到第i个节点之后
    p->next = s;
    return true;
}

// 删除元素
bool ListDelete(LinkList &L, int i, int &e) {
    LinkList p = L, q; // p指向头节点，q为待删除节点
    int j = 0;
    while (p->next && j < i - 1) { // 寻找第i-1个节点
        p = p->next;
        j++;
    }
    if (!p->next || j > i - 1) { // 判断删除位置是否合法
        return false;
    }
    q = p->next; // 将待删除节点赋值给q
    e = q->data; // 将待删除节点的元素赋值给e
    p->next = q->next; // 将待删除节点从链表中删除
    free(q); // 释放待删除节点的内存空间
    return true;
}

// 查找元素
int LocateElem(LinkList L, int e) {
    LinkList p = L->next; // p指向第一个节点
    int i = 1;
    while (p) { // 遍历链表
        if (p->data == e) {
            return i; // 返回元素在链表中的位置
        }
        p = p->next;
        i++;
    }
    return 0; // 没有找到返回0
}