C++实现线性表 |21xrx.com

C++实现线性表

2023-07-10 06:08:23 深夜i -- --

C++ 线性表实现

线性表是一种常见的数据结构，在计算机科学中被广泛使用。C++是一种面向对象编程语言，也可以用来实现线性表。下面将介绍如何使用C++实现线性表。

首先，定义一个结构体作为线性表的基本单元。该结构体应该包含一个存储元素的数组以及一个指向下一个元素的指针。


struct node{
  int data;
  node *next;
};

接下来，创建一个类来表示线性表。该类应该包含一个指向第一个元素的指针和一个整数表示线性表的大小。


class list{
public:
  list(); // 构造函数
  ~list(); // 析构函数
  void insert(int position, int value); // 插入元素
  void remove(int position); // 删除元素
  int search(int value); // 查找元素
  int size(); // 获取线性表的大小
private:
  node *head;
  int length;
};

构造函数应该初始化head指针为空，而析构函数应该释放所有节点。


list::list()
  head = nullptr;
  length = 0;
list::~list(){
  while(head != nullptr){
    node *temp = head;
    head = head->next;
    delete temp;
  }
}

插入元素时，需要先找到正确的位置，然后将新元素插入到该位置。这包括将该位置前一个元素的next指针指向新元素，以及将新元素的next指针指向该位置。


void list::insert(int position, int value){
  if(position < 0 || position > length)
    return;
  
  node *newNode = new node;
  newNode->data = value;
  if(position == 0)
    newNode->next = head;
    head = newNode;
  else{
    node *temp = head;
    for(int i = 0; i < position - 1; i++)
      temp = temp->next;
    
    newNode->next = temp->next;
    temp->next = newNode;
  }
  length++;
}

删除元素时，需要找到正确的位置，并将该位置前一个元素的next指针指向该位置后一个元素。还需要释放被删除元素的内存空间。


void list::remove(int position){
  if(position < 0 || position >= length)
    return;
  
  node *temp;
  if(position == 0)
    temp = head;
    head = head->next;
  else{
    node *prev = head;
    for(int i = 0; i < position - 1; i++)
      prev = prev->next;
    
    temp = prev->next;
    prev->next = temp->next;
  }
  delete temp;
  length--;
}

查找元素时，需要遍历整个线性表，如果找到了该元素，则返回它的位置，否则返回-1。


int list::search(int value){
  node *temp = head;
  for(int i = 0; i < length; i++){
    if(temp->data == value)
      return i;
    
    temp = temp->next;
  }
  return -1;
}

获取线性表的大小就是返回length变量的值。


int list::size()
  return length;

到此为止，我们已经使用C++实现了一个线性表。虽然这个实现并不完整，但它表示了一个简单的数据结构。使用面向对象的思想，可以创建更多的类和方法来扩展和优化它。

上一篇: idea打包java可执行jar包

下一篇: C++中如何表示n次方

评论区

()

相似文章