线性表是线性数据结构的常见形式，每⼀个数据元素依次相连，每⼀个数据元素只有⼀个前驱和⼀个后继，所有数据元素被串成了⼀串，可以进行增加、删除数据元素等操作。

线性表共有两种实现方式:顺序实现（顺序表）与链接实现（链接表）。

线性表的定义list.h

//
// 线性表的定义
//

#ifndef DS_LIST_H
#define DS_LIST_H
template <class elemType>
class list {
public:
    virtual void clear() = 0;  // 清空线性表
    virtual int length() const = 0;  // 获取线性表的长度，即元素个数
    // 在第i个位置插入一个元素x
    virtual void insert(int i, const elemType &x) = 0;
    virtual void remove(int i) = 0;  // 删除第i个元素
    // 搜索元素x是否在线性表中出现
    virtual int search(const elemType &x) const = 0;
    virtual elemType visit(int i) const = 0;  // 访问线性表第i个元素
    virtual void traverse() const = 0;        // 遍历线性表
    virtual ~list() {};
};
#endif //DS_LIST_H

顺序表的顺序实现是将线性表的数据元素存放在一块连续的空间(即数组)中，用存放位置反映数据元素之间的关系，将第个元素放在数组的下标为i的位置上(从0开始计数)，这样在物理位置上相邻的元素在逻辑结构中也是相邻的。

顺序表的定义和实现seqList.h

//
// 顺序表的定义和实现
//

#ifndef DS_SEQLIST_H
#define DS_SEQLIST_H
#include <iostream>

#include "list.h"
using namespace std;

template <class elemType>
class seqList : public list<elemType> {
private:
    elemType *data;
    int currentLength;
    int maxSize;
    void doubleSpace();

public:
    seqList(int initSize = 10);
    ~seqList() { delete[] data; }  // 释放动态数组的空间
    void clear() { currentLength = 0; }
    int length() const { return currentLength; }
    void insert(int i, const elemType &x);
    void remove(int i);
    int search(const elemType &x) const;
    elemType visit(int i) const { return data[i]; }
    void traverse() const;
};

template <class elemType>
seqList<elemType>::seqList(int initSize) {
    data = new elemType[initSize];
    maxSize = initSize;
    currentLength = 0;
}

template <class elemType>
int seqList<elemType>::search(const elemType &x) const {
    int i;
    // 使用for循环逐位搜索data[i]是否等于x
    for (i = 0; i < currentLength && data[i] != x; ++i);
    if (i == currentLength)
        return -1;
    else
        return i;
}

template <class elemType>
void seqList<elemType>::traverse() const {
    for (int i = 0; i < currentLength; ++i) cout << data[i] << ' ';
    cout << endl;
}

// 在第i个位置插入元素x
template <class elemType>
void seqList<elemType>::insert(int i, const elemType &x) {
    // 如果当前表长已经达到了申请空间的上限，则必须执行扩大数组空间的操作
    if (currentLength == maxSize) doubleSpace();

    // 将第 i 个元素到最后一个元素的储存位置全部后移一个位置
    for (int j = currentLength; j > i; j--) data[j] = data[j - 1];
    data[i] = x;
    ++currentLength;
}

// 自动扩容
template <class elemType>
void seqList<elemType>::doubleSpace() {
    elemType *tmp = data;
    maxSize *= 2;
    data = new elemType[maxSize];  // 申请容量翻倍的新空间
    for (int i = 0; i < currentLength; ++i)
        data[i] = tmp[i];  // 将数据从旧空间复制到新空间
    delete[] tmp;        // 回收旧空间
}

// 删除第i个位置的元素
template <class elemType>
void seqList<elemType>::remove(int i) {
    // 将第i+1个元素到最后一个元素全部前移一个位置
    for (int j = i; j < currentLength - 1; j++) data[j] = data[j + 1];
    --currentLength;
}
#endif //DS_SEQLIST_H

顺序表的测试seqList.cpp

//
// 顺序表的测试
//

#include <iostream>

#include "seqList.h"
using namespace std;

int main() {
    //实例化类型为int的seqList
    seqList<int> intSeqList(10);
    cout << std::addressof(intSeqList) << endl;
    intSeqList.insert(0,12);

    //实例化类型为string的seqList
    seqList<string> stringSeqList(20);
    cout << std::addressof(stringSeqList) << endl;
    stringSeqList.insert(0,"a");

    cout << intSeqList.length() << endl;
    cout << stringSeqList.length() << endl;
    return 0;

}

顺序表的显著缺点

  • 插入和删除数据时必须移动大量数据元素。
  • 必须预先为顺序表准备存储空间。当表长小于数组长度时，部分空间闲置浪费；当表长大于数组长度时，需要扩容。

链接表的链接实现是将每个数据元素存放在⼀个独⽴的存储单元（结点）中，并在这个结点中附加指向邻接结点的地址指针。访问任意⼀个数据元素后，就可以通过指向邻接结点的指针寻找下⼀个结点。

链接表不需要事先定义空间，⼀般采⽤动态存储的⽅法，即插⼊⼀个元素时申请⼀个结点的空间，删除⼀个元素时释放⼀个结点的空间。插⼊元素时动态申请结点空间并链接到表中，删除元素时释放结点空间，因此不会造成空间的闲置，且对相邻结点的修改只涉及对邻接结点指针的修改，不会引起⼤量数据的移动。

如果每个结点只存储指向直接后继结点的指针，则称为单链表。如果每个结点既存储指向直接后继的指针，⼜存储指向直接前驱的指针，则称为双链表。

单链表的定义和实现sLinkList.h

//
// 单链表的定义和实现
//

#ifndef DS_SLINKLIST_H
#define DS_SLINKLIST_H
#include <iostream>

#include "list.h"
using namespace std;

template <class elemType>
class sLinkList : public list<elemType> {
 private:
  struct node {
    elemType data;
    node *next;
    node(const elemType &x, node *n = nullptr) {
      data = x;
      next = n;
    }
    node() : next(nullptr) {}
    ~node() {};
  };

  node *head;
  int currentLength;
  node *find(int i) const;

 public:
  sLinkList() {
    head = new node;  // 申请头结点
    currentLength = 0;
  }
  ~sLinkList() {
    clear();
    delete head;  // 删除头结点
  }
  void clear();
  int length() const { return currentLength; }
  void insert(int i, const elemType &x);
  void remove(int i);
  int search(const elemType &x) const;
  elemType visit(int i) const;
  void traverse() const;
};

template <class elemType>
void sLinkList<elemType>::insert(int i, const elemType &x) {
  node *pos;
  pos = find(i - 1);  // 找到指向第i−1个结点的指针
  // 将第i−1个结点的后继指针指向新结点，新结点指向原来的第i个结点
  pos->next = new node(x, pos->next);
  ++currentLength;
}

template <class elemType>
void sLinkList<elemType>::remove(int i) {
  node *pos, *delp;
  pos = find(i - 1);  // 找到前一个结点的地址
  delp = pos->next;   // 找到要删除的结点
  pos->next = delp->next;  // 把前一个结点的指针指向delp的后一个结点
  delete delp;
  --currentLength;
}

// 按序删除头结点以外的所有真的包含元素的结点
template <class elemType>
void sLinkList<elemType>::clear() {
  node *p = head->next, *q;
  head->next = nullptr;
  while (p != nullptr) {
    q = p->next;
    delete p;
    p = q;
  }
  currentLength = 0;
}

// 返回第i个结点的地址
template <class elemType>
sLinkList<elemType>::node *sLinkList<elemType>::find(
    int i) const {
  node *p = head;
  while (i-- >= 0) p = p->next;
  return p;
}

template <class elemType>
int sLinkList<elemType>::search(const elemType &x) const {
  node *p = head->next;
  int i = 0;
  while (p != nullptr && p->data != x) {
    p = p->next;
    ++i;
  }
  if (p == nullptr)
    return -1;
  else
    return i;
}

template <class elemType>
elemType sLinkList<elemType>::visit(int i) const {
  return find(i)->data;  // 找到第i个结点的地址，访问其中的data
}

template <class elemType>
void sLinkList<elemType>::traverse() const {
  node *p = head->next;
  while (p != nullptr) {
    cout << p->data << "  ";
    p = p->next;
  }
  cout << endl;
}
#endif //DS_SLINKLIST_H

单链表表的测试seqListTest.cpp

//
// 单链表的测试
//

#include <iostream>

#include "sLinkList.h"
using namespace std;

int main() {
    sLinkList<int> sll;
    cout << std::addressof(sll) << endl;
    cout << sll.length() << endl;
    sll.insert(0,100);
    cout << sll.length() << endl;
    sll.insert(1,101);
    sll.traverse();
    return 0;

}

C++标准库中的顺序表
std::vector是C++标准库中的顺序表实现，是一种动态数组容器，可以根据需要动态调整大小。

//
// C++标准库中的顺序表
//

#include <iostream>

using namespace std;

int main() {

    std::vector<int> vec;
    for (int i = 0; i < 10; i++) {
        vec.push_back(i);
        std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;
    }
    return 0;

}

C++标准库中的链表
std::list是C++标准库中的双向链表实现，每个节点包含指向前一个节点和后一个节点的指针。它支持高效的插入和删除操作，但随机访问效率较低。

//
// C++标准库中的双向链表
//

#include <iostream>
#include <list>

using namespace std;

int main() {
    std::list<int> li = {1,2,3};
    li.push_front(10);// 在链表头部插入
    li.push_back(20);// 在链表尾部插入

    auto iter = li.begin();
    ++iter;
    const auto arr = {40,50,60};
    li.insert(iter,arr);// 在指定位置插入
    for(auto l : li)
        cout << " " << l;
    cout << endl;
    return 0;

}

std::forward_list（单向链表）

std::forward_list是C++11引入的单向链表实现，每个节点只包含指向下一个节点的指针。它比std::list更轻量，但只能单向遍历。

//
// C++标准库中的单向链表
//

#include <iostream>
#include <forward_list>

using namespace std;

int main() {

    std::forward_list<int> li = {1,2,3};
    li.push_front(10);// 在链表头部插入
    li.push_front(20);// 在链表头部插入

    auto iter = li.begin();
    ++iter;
    const auto arr = {40,50,60};
    li.insert_after(iter,arr);// 在指定位置插入
    for(auto l : li)
        cout << " " << l;
    cout << endl;
    return 0;

}
# c++ # 数据结构
Logo
AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

cover

程序员学 AI（八）：AI Agent 到底是什么？从回答问题到完成任务

avatar AI Agent技术社区
cover

22道AI Agent 工程师必会的面试题，别啥都不会就出去找工作

avatar AI Agent技术社区
cover

基于AI agent的智能图书馆

avatar AI Agent技术社区