线性表C++的两种实现(顺序表示、单链表)

dingallen216

在考研嘛，考408，数据结构肯定是跑不掉要学的。光看书光看书多少有点枯燥无聊，稍微实现些代码调节调节。本文是第一次写此类文章，之后随着复习进度的推进会继续整理。本文的代码通过c++实现，实现的基本操作与408考试大纲一致。如果有错误，或者有对计算机考研的建议，感谢您能够在评论区提出。
顺序表示的线性表
数据结构的定义

[C++] 纯文本查看 复制代码

// 静态分配
template<typename ElemType>
struct SqList {
public:
    ElemType data[MaxSize];
    int length;
};

// 动态分配
template<typename ElemType>
struct SeqList {
public:
    ElemType *data;
    int maxSize, length;
};

基本操作的定义
本文仅实现了静态分配的线性表。

[C++] 纯文本查看 复制代码

/*
 * 顺序表示的静态分配线性表的基本操作定义。
 * */

// 初始化表。构造一个空的线性表。
// 课本上是void InitList(SqList<ElemType> &L)，这在类型不确定的情况下多少有点不合理，故改为这样的定义。
// 此外，如果操作不违规，这一步其实是可以省略的。
template<typename ElemType>
bool InitList(SqList<ElemType> &L, ElemType v);

// 求表长。返回线性表L的长度，即L中数据元素的个数。
template<typename ElemType>
int Length(SqList<ElemType> L);

// 按值查找操作。在表L中查找具有给定关键字值的元素。
template<typename ElemType>
int LocateElem(SqList<ElemType> L, ElemType e);

// 按位查找操作。获取表L中第 i个位置的元素的值。这里我在实现的时候我想当然地把索引不合法的情况设置为返回值-1了，这个问题应该不是很大。
template<typename ElemType>
ElemType GetElem(SqList<ElemType> L, int i);

// 插入操作。在表L中的第i个位置上插入指定元素e。
template<typename ElemType>
bool ListInsert(SqList<ElemType> &L, int i, ElemType e);

// 删除操作。删除表L 中第 i 个位置的元素，并用e返回删除元素的值。
template<typename ElemType>
bool ListDelete(SqList<ElemType> &L, int i, ElemType &e);

// 输出操作。按前后顺序输出线性表L 的所有元素值。
template<typename ElemType>
void PrintList(SqList<ElemType> L);

// 判空操作。若L为空表，则返回 true，否则返回 false。
template<typename ElemType>
bool Empty(SqList<ElemType> L);

// 销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
template<typename ElemType>
void DestroyList(SqList<ElemType> &L);

基本操作的实现

[C++] 纯文本查看 复制代码

template<typename ElemType>
bool InitList(SqList<ElemType> &L, ElemType v) {

    L.length = 0;
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = v;
    }
    return true;
}

template<typename ElemType>
int Length(SqList<ElemType> L) {
    return L.length;
}

template<typename ElemType>
int LocateElem(SqList<ElemType> L, ElemType e) {

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

template<typename ElemType>
ElemType GetElem(SqList<ElemType> L, int i) {

    assert(i >= 1 && i <= L.length);

    return L.data[i - 1];
}

template<typename ElemType>
bool ListInsert(SqList<ElemType> &L, int i, ElemType 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;
}

template<typename ElemType>
bool ListDelete(SqList<ElemType> &L, int i, ElemType &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;
}

template<typename ElemType>
void PrintList(SqList<ElemType> L) {

    for (int i = 0; i < L.length; i++) {
        std::cout << "线性表第" << i << "个位置的元素为：" << L.data[i - 1] << std::endl;
    }
}

template<typename ElemType>
bool Empty(SqList<ElemType> L) {
    return L.length > 0 ? true : false;
}

template<typename ElemType>
void DestroyList(SqList<ElemType> &L) {
    delete L;
}

单链表
单链表这块，没有像上面那样使用template来声明，因为这样实现会让代码的一些地方变得很不优雅，并且会做一些与教材本身无关的事情，故直接用int定义数据。
定义

[C++] 纯文本查看 复制代码

// 单链表结点的定义。
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

基本操作的定义

[C++] 纯文本查看 复制代码

/*
 * 带头结点的单链表的基本操作定义。
 * */
bool InitList(LinkList &L);
int Length(LinkList L);
int LocateElem(LinkList L, int e);
LNode *GetElem(LinkList L, int i);
bool InsertNextNode(LNode *p, int e); // 后插操作：在p结点之后插入元素e
bool ListInsert(LinkList &L, int i, int e);
bool ListDelete(LinkList &L, int i, int &e);
void PrintList(LinkList L);
bool Empty(LinkList L);
void DestoryList(LinkList &L);

基本操作的实现

[C++] 纯文本查看 复制代码

bool InitList(LinkList &L) {

    L = new LNode;
    if (L == NULL) return false;
    L->next = NULL;
    return true;
}

int Length(LinkList L) {

    LNode *p = L;
    int i = 0;
    while (p->next != NULL) {
        p = p->next;
        i++;
    }
    return i;
}

int LocateElem(LinkList L, int e) {

    LNode *p = L->next;
    for (int i = 1; p != NULL; ++i) {
        if (p->data == e) return i;
        p = p->next;
    }
    return -1;
}

LNode *GetElem(LinkList L, int i) {

    if (i < 0) return NULL;

    LNode *p = L;
    for (int j = 0; p != NULL && j < i; j++)
        p = p->next;

    return p;
}

bool InsertNextNode(LNode *p, int e) {

    if (p == NULL) return false;
    LNode *s = new LNode;
    if (s == NULL) return false;

    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

bool ListInsert(LinkList &L, int i, int e) {

    if (i < 1) return false;
    LNode *p = GetElem(L, i - 1);
    return InsertNextNode(p, e);
}

bool ListDelete(LinkList &L, int i, int &e) {

    if (i < 1) return false;
    LNode *p = GetElem(L, i - 1);
    if (p == NULL || p->next == NULL) return false;
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    delete q;
    return true;
}

void PrintList(LinkList L) {

    LNode *p = L->next;
    for (int i = 0; p != NULL; i++) {
        std::cout << "线性表第" << i << "个位置的元素为：" << p->data << std::endl;
    }
}

bool Empty(LinkList L) {
    return L->next != NULL ? true : false;
}

void DestoryList(LinkList &L) {

    LNode *p = L;
    LNode *temp;

    while (p != NULL) {
        temp = p;
        p = p->next;
        delete temp;
    }
}

尾插法和头插法建立单链表

[C++] 纯文本查看 复制代码

// 尾插法建立单链表,输入9999表示结束。
LinkList List_TailInsert(LinkList &L) {
    
    int x;
    L = new LNode;
    LNode *s, *r = L;
    std::cin >> x;
    while (x!=9999) {
        s = new LNode;
        s->data = x;
        r->next = s;
        r = s;
        std::cin >> x;
    }
    r->next = NULL;
    return L;
}

// 头插法建立单链表， 输入9999表示结束。
LinkList List_HeadInsert(LinkList &L) {

    int x;
    L = new LNode;
    L->next = NULL;
    LNode *s;
    std::cin >> x;
    while (x!=9999) {
        s = new LNode;
        s->data = x;
        s->next = L->next;
        L->next = s;
        std::cin >> x;
    }
    return L;
}

lyl610abc

这个排版，有点恐怖啊，希望能整理一下排版

dingallen216

lyl610abc 发表于 2021-5-5 15:26
这个排版，有点恐怖啊，希望能整理一下排版

整理好了，谢谢提醒。

Abrahams

同样在学习数据结构！考研加油

dingallen216

Abrahams 发表于 2021-5-5 17:09
同样在学习数据结构！考研加油

加油，兄弟

lin1

加油，正好在学数据结构和算法，刚看到链表就看见你的贴了。

cao777

标记一下 这个不错的