c++数据结构线性表

C++中的线性表可以使用数组或链表来实现。数组实现的线性表具有随机访问的特点，而链表实现的线性表则具有插入和删除元素的高效性。

以下是C++中数组实现线性表的基本操作：

1.初始化线性表

const int 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;
    }
    L.length = 0;
}

2.插入元素

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++;
    return true;
}

3.删除元素

bool ListDelete(SqList &L, int i, int &e) {
    if (i < 1 || i > L.length) {
        return false;
    }
    e = L.data[i - 1];
    for (int j = i; j < L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

4.查找元素

int LocateElem(SqList L, int e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;
        }
    }
    return 0;
}

以下是C++中链表实现线性表的基本操作：

1.定义链表节点

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

2.初始化链表

void InitList(LinkList &L) {
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
}

3.插入元素

bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
    }
    LNode *p = L;
    int j = 0;
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p) {
        return false;
    }
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

4.删除元素

bool ListDelete(LinkList &L, int i, int &e) {
    if (i < 1) {
        return false;
    }
    LNode *p = L;
    int j = 0;
    while (p->next && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!(p->next) || j > i - 1) {
        return false;
    }
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

5.查找元素

LNode* GetElem(LinkList L, int i) {
    if (i < 0) {
        return NULL;
    }
    LNode *p = L;
    int j = 0;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;
}