面向对象案例

本文作者：程序员飞云

本站地址：https://www.flycode.icu

项目目标

实现动态可变的数据容器

添加元素（末尾，指定下标）
删除元素（下标，按照元素删除，清空）
修改元素（下标）
获取元素（下标）
元素排序
元素下标查询
容器中的元素拼接为字符串返回

项目分析

可变容器：数组版，双链表版本

定义接口模板类(QFMutableContainer.h)

#pragma once

// 定义类模板
template<typename E>
class QFMutableContainer {
public:
  //末尾添加元素
  virtual void add(E ele) = 0;

  // 指定位置添加元素
  virtual void add(int index, E ele) = 0;

  // 删除指定位置元素
  virtual E remove(int index) = 0;

  // 删除指定元素
  virtual bool removeElement(E ele) = 0;

  // 清空元素
  virtual void clear() = 0;

  // 修改指定下标元素
  virtual E set(int index, E ele) = 0;

  // 获取指定下标元素
  virtual E get(int index = 0) = 0;

  // 元素排序
  virtual void sort() = 0;

  // 获取对应元素的下标
  virtual int index(E ele) = 0;

  //容器元素字符串返回
  virtual string str() = 0;

    //析构函数
  virtual ~QFMutableContainer() {

  };
};

数组实现

定义数组

#pragma once
#include "QFMutableContainer.h"
#include <string>
using namespace std;

// 数组实现
template<typename E>
class QFMutableArray: public QFMutableContainer<E>{
private:
  // 存放元素
  E* array;
  int len;

public:
  //末尾添加元素
  void add(E ele) override;

  // 指定位置添加元素
  void add(int index, E ele) override;

  // 删除指定位置元素
  E remove(int index) override ;

  // 删除指定元素
  bool removeElement(E ele) override;

  // 清空元素
  void clear() override;

  // 修改指定下标元素
  E set(int index, E ele) override;

  // 获取指定下标元素
  E get(int index = 0) override;

  // 元素排序
  void sort() override ;

  // 获取对应元素的下标
  int index(E ele) override;

  //容器元素字符串返回
  string str() override ;


  // 析构函数
  ~QFMutableArray() override;

    // 构造函数
  QFMutableArray();
};

template<typename E>
inline void QFMutableArray<E>::add(E ele)
{
}

template<typename E>
inline void QFMutableArray<E>::add(int index, E ele)
{
}

template<typename E>
inline E QFMutableArray<E>::remove(int index)
{
  return E();
}

template<typename E>
inline bool QFMutableArray<E>::removeElement(E ele)
{
  return false;
}

template<typename E>
inline void QFMutableArray<E>::clear()
{
}

template<typename E>
inline E QFMutableArray<E>::set(int index, E ele)
{
  return E();
}

template<typename E>
inline E QFMutableArray<E>::get(int index)
{
  return E();
}

template<typename E>
inline void QFMutableArray<E>::sort()
{
}

template<typename E>
inline int QFMutableArray<E>::index(E ele)
{
  return 0;
}

template<typename E>
inline string QFMutableArray<E>::str()
{
  return string();
}

template<typename E>
inline QFMutableArray<E>::~QFMutableArray()
{
  if (array != nullptr) {
    delete array;
    array = nullptr;
  }
}

template<typename E>
inline QFMutableArray<E>::QFMutableArray()
{
  array = new E[0];
  len = 0;
}

实现字符串返回

#include <sstream>

template<typename E>
inline string QFMutableArray<E>::str()
{
  if (len == 0) {
    return "[]";
  }
    // 拼接元素
  ostringstream oss;
  oss << "[";

  for (int i = 0; i < len - 2; i++) {
    oss << array[i] << ", ";
  }

  oss << array[len - 1] << "]";

  return string();
}

实现添加元素到末尾

可以创建一个新的数组，将原来的数组元素都添加到这个新数组里面去，然后最后一位添加新元素，扩大长度，删除原数组，修改原数组指向

template<typename E>
inline void QFMutableArray<E>::add(E ele)
{
  // 创建一个新数组，长度为之前数组的个数+1，将原来数组元素都拷贝到新数组，将新元素放在数组末尾
  E* newArray = new E[len + 1];
  // 元素拷贝
  for (int i = 0; i < len; i++) {
    newArray[i] = array[i];
  }
  // 新数组尾部插入元素
  newArray[len ] = ele;
  // 长度自增
  len++;
  // 删除原数组
  delete array;
  // 修改指针指向
  array = newArray;
}

添加元素到指定位置

主要步骤和上面类似，但是区别在于，当遇到对应的index下标的时候，此时新的数组就不需要添加旧数组里面的元素，跳过当前循环，等所有的元素都遍历完成后，在将指定元素插入到对应位置。

template<typename E>
inline void QFMutableArray<E>::add(int index, E ele)
{
  if (index > len || index < 0) {
    cout << "下标位置不合理" << endl;
    return;
  }

  //新建数组
  E* newArray = new int[len+1];

  // 拷贝元素
  for (int j = 0 ,i = 0; j < len+1; j++) {
    // 不拷贝
    if (j == index) {
      continue;
    }
    newArray[j] = array[i++];
  }

  // 设置元素
  newArray[index] = ele;

  // 扩大长度
  len++;
  // 删除原数组
  delete array;
  // 重新指向新数组
  array = newArray;
}

删除指定下标

依然是出现一个位数不一致的情况，处理方式和上面的一样，需要跳过当前这一位

template<typename E>
inline E QFMutableArray<E>::remove(int index)
{
  if (index >= len || index < 0) {
    cout << "下标不合理" << endl;
    return -1;
  }
  // 创建新数组，长度减1
  E* newArray = new E[len - 1];
  // 记录目标值
  E temp = array[index];
  // 遍历数组
  for (int i = 0,j = 0; i < len; i++) {
    // 如果是指定的下标，就跳过循环
    if (i == index) {
      continue;
    }
    newArray[j++] = array[i];
  }

  // 长度减少
  len--;
  // 删除原数组
  delete array;
  // 指针指向新数组
  array = newArray;

  return temp;
}

寻找指定元素

template<typename E>
inline int QFMutableArray<E>::index(E ele)
{
  for (int i = 0; i < len; i++) {
    if (ele == array[i]) {
      return i;
    }
  }
  return -1;
}

删除指定元素

目前设定里面不存在对应的重复元素，需要先找到下标，然后利用之前写好的删除下标元素函数

template<typename E>
inline bool QFMutableArray<E>::removeElement(E ele)
{
  // 找到下标
  E idx = index(ele);
  // 判断是否存在
  if (idx == -1) {
    return false;
  }
  // 移除元素
  remove(idx);
  return true;
}

清空数组

只需要删除原数组

template<typename E>
inline void QFMutableArray<E>::clear()
{
  // 清除原数组
  delete array;
  // 重置数组
  array = new E[0];
  len = 0;
}

指定下标修改元素

template<typename E>
inline E QFMutableArray<E>::set(int idx, E ele)
{
  if (idx < 0 || idx >= len) {
    cout << "下标不合理" << endl;
    return -1;
  }
  // 备份原来的值
  E temp = array[idx];
  // 修改值
  array[idx] = ele;
  return temp ;
}

数组元素排序(冒泡)

template<typename E>
inline void QFMutableArray<E>::sort()
{
  for (int i = 0; i < len; i++) {
    for (int j = 0; j < len - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        E temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
}

完整代码

#pragma once
#include "QFMutableContainer.h"
#include <iostream>
#include <sstream>
using namespace std;

// 数组实现
template<typename E>
class QFMutableArray: public QFMutableContainer<E>{
private:
  // 存放元素
  E* array;
  int len;

public:
  //末尾添加元素
  void add(E ele) override;

  // 指定位置添加元素
  void add(int index, E ele) override;

  // 删除指定位置元素
  E remove(int index) override ;

  // 删除指定元素
  bool removeElement(E ele) override;

  // 清空元素
  void clear() override;

  // 修改指定下标元素
  E set(int index, E ele) override;

  // 获取指定下标元素
  E get(int index = 0) override;

  // 元素排序
  void sort() override ;

  // 获取对应元素的下标
  int index(E ele) override;

  //容器元素字符串返回
  string str() override ;


  // 析构函数
  ~QFMutableArray() override;

  // 构造函数
  QFMutableArray();

  // 返回当前数组元素个数
  int length() override;
};

template<typename E>
inline void QFMutableArray<E>::add(E ele)
{
  // 创建一个新数组，长度为之前数组的个数+1，将原来数组元素都拷贝到新数组，将新元素放在数组末尾
  E* newArray = new E[len + 1];
  // 元素拷贝
  for (int i = 0; i < len; i++) {
    newArray[i] = array[i];
  }
  // 新数组尾部插入元素
  newArray[len ] = ele;
  // 长度自增
  len++;
  // 删除原数组
  delete array;
  // 修改指针指向
  array = newArray;
}

template<typename E>
inline void QFMutableArray<E>::add(int index, E ele)
{
  if (index > len || index < 0) {
    cout << "下标位置不合理" << endl;
    return;
  }

  //新建数组
  E* newArray = new int[len+1];

  // 拷贝元素
  for (int j = 0 ,i = 0; j < len+1; j++) {
    // 不拷贝
    if (j == index) {
      continue;
    }
    newArray[j] = array[i++];
  }

  // 设置元素
  newArray[index] = ele;

  // 扩大长度
  len++;
  // 删除原数组
  delete array;
  // 重新指向新数组
  array = newArray;
}

template<typename E>
inline E QFMutableArray<E>::remove(int index)
{
  if (index >= len || index < 0) {
    cout << "下标不合理" << endl;
    return -1;
  }
  // 创建新数组，长度减1
  E* newArray = new E[len - 1];
  // 记录目标值
  E temp = array[index];
  // 遍历数组
  for (int i = 0,j = 0; i < len; i++) {
    // 如果是指定的下标，就跳过循环
    if (i == index) {
      continue;
    }
    newArray[j++] = array[i];
  }

  // 长度减少
  len--;
  // 删除原数组
  delete array;
  // 指针指向新数组
  array = newArray;

  return temp;
}

template<typename E>
inline bool QFMutableArray<E>::removeElement(E ele)
{
  // 找到下标
  E idx = index(ele);
  // 判断是否存在
  if (idx == -1) {
    return false;
  }
  // 移除元素
  remove(idx);

  return true;

}

template<typename E>
inline void QFMutableArray<E>::clear()
{
  // 清除原数组
  delete array;
  // 重置数组
  array = new E[0];
  len = 0;
}

template<typename E>
inline E QFMutableArray<E>::set(int idx, E ele)
{
  if (idx < 0 || idx >= len) {
    cout << "下标不合理" << endl;
    return -1;
  }
  // 备份原来的值
  E temp = array[idx];
  // 修改值
  array[idx] = ele;
  return temp ;
}

template<typename E>
inline E QFMutableArray<E>::get(int idx)
{
  if (idx < 0 || idx >= len) {
    cout << "下标不合理" << endl;
    return -1;
  }

  return array[idx];
}

template<typename E>
inline void QFMutableArray<E>::sort()
{
  for (int i = 0; i < len; i++) {
    for (int j = 0; j < len - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        E temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
}

template<typename E>
inline int QFMutableArray<E>::index(E ele)
{
  for (int i = 0; i < len; i++) {
    if (ele == array[i]) {
      return i;
    }
  }
  return -1;
}

template<typename E>
inline string QFMutableArray<E>::str()
{
  if (len == 0) {
    return "[]";
  }

  ostringstream oss;
  oss << "[";

  for (int i = 0; i < len - 1; i++) {
    oss << array[i] << ", ";
  }

  oss << array[len - 1] << "]";

  return oss.str();

}

template<typename E>
inline QFMutableArray<E>::~QFMutableArray()
{
  if (array != nullptr) {
    delete array;
    array = nullptr;
  }
}

template<typename E>
inline QFMutableArray<E>::QFMutableArray()
{
  array = new E[0];
  len = 0;
}

template<typename E>
inline int QFMutableArray<E>::length()
{
  return len;
}

链表实现

设计链表

因为链表里面每个节点都有前驱和后继，所有使用析构函数的时候比较麻烦，所先不考虑，需要

#pragma once
#include "QFMutableList.hpp"


template<typename T>
class QFMutableList;

template<typename E>
class QFLinkNode {
  friend class QFMutableList<E>;

private:
  E ele;
  QFLinkNode<E>* next;
  QFLinkNode<E>* prev;

public:
  QFLinkNode(E ele);
};

template<typename E>
inline QFLinkNode<E>::QFLinkNode(E ele)
{
  this->ele = ele;
  this->next = nullptr;
  this->prev = nullptr;
}

定义实现

#pragma once
#include "QFMutableContainer.h"
#include "QFLinkNode.hpp"
#include <sstream>
using namespace std;



template<typename E>
class QFMutableList: public QFMutableContainer<E>{
private:
  QFLinkNode<E>* first;// 链表头节点
  QFLinkNode<E>* last;  //链表尾节点
  int len;             // 链表长度


public:
  QFMutableList();

  ~QFMutableList() override;

  //末尾添加元素
  void add(E ele) override;

  // 指定位置添加元素
  void add(int index, E ele) override;

  // 删除指定位置元素
  E remove(int index) override;

  // 删除指定元素
  bool removeElement(E ele) override;

  // 清空元素
  void clear() override;

  // 修改指定下标元素
  E set(int index, E ele) override;

  // 获取指定下标元素
  E get(int index = 0) override;

  // 元素排序
  void sort() override;

  // 获取对应元素的下标
  int index(E ele) override;

  //容器元素字符串返回
  string str() override;

  // 容器中元素的数量
  int length() override;
};

template<typename E>
inline QFMutableList<E>::QFMutableList()
{
  this->first = nullptr;
  this->last = nullptr;
  len = 0;
}

template<typename E>
inline QFMutableList<E>::~QFMutableList()
{
  // 删除所有的节点
  if (this->first != nullptr) {
    QFLinkNode<E>* p1 = this->first;
    QFLinkNode<E>* p2 = p1->next;
    while (p2 != nullptr) {
      delete p1;
      p1 = p2;
      p2 = p2->next;
    }
    delete p1;
    this->first = nullptr;
    this->last = nullptr;
    len = 0;
  }
}

template<typename E>
inline void QFMutableList<E>::add(E ele)
{
}

template<typename E>
inline void QFMutableList<E>::add(int index, E ele)
{
}

template<typename E>
inline E QFMutableList<E>::remove(int index)
{
  return E();
}

template<typename E>
inline bool QFMutableList<E>::removeElement(E ele)
{
  return false;
}

template<typename E>
inline void QFMutableList<E>::clear()
{
}

template<typename E>
inline E QFMutableList<E>::set(int index, E ele)
{
  return E();
}

template<typename E>
inline E QFMutableList<E>::get(int index)
{
  return E();
}

template<typename E>
inline void QFMutableList<E>::sort()
{
}

template<typename E>
inline int QFMutableList<E>::index(E ele)
{
  return 0;
}

template<typename E>
inline string QFMutableList<E>::str()
{

  return string();
}

template<typename E>
inline int QFMutableList<E>::length()
{
  return len;
}

添加元素

需要判断链表是否为空，如果为空，那么就first和last都是这个节点，不为空，需要将节点放在last的后面，重新定义last节点

template<typename E>
inline void QFMutableList<E>::add(E ele)
{
  // 创建一个新的链表
  QFLinkNode<E>* node = new QFLinkNode<E>(ele);

  // 判断元素数量,链表没有元素
  if (len == 0) {
    this->first = node;
    this->last = node;
  }
  else {
    // 链表里面有元素，将节点添加到last节点后
    this->last->next = node;
    node->prev = this->last;
    this->last = node;
  }
  len++;
}

转换为字符串

template<typename E>
inline string QFMutableList<E>::str()
{
  if (len == 0) {
    return "[]";
  }

  QFLinkNode<E>* cur = first;
  ostringstream oss;
  oss << "[";
  for (int i = 0; i < len - 1; i++) {
    oss << cur->ele << ", ";
    cur = cur->next;
  }
  oss << cur->ele << "]" << endl;

  return oss.str();
}

根据下标获取节点

private:
  QFLinkNode<E>* first;// 链表头节点
  QFLinkNode<E>* last;  //链表尾节点
  int len;             // 链表长度

  QFLinkNode<E>* getNode(int idx);// 通过下标获取指定节点

template<typename E>
inline QFLinkNode<E>* QFMutableList<E>::getNode(int idx)
{
  QFLinkNode<E>* p = first;
  for (int i = 0; i < index; i++) {
    p = p->next;
  }
  return p;
}

指定位置插入元素

需要明确当前插入的位置，三种情况

插入头部：需要改变first的指向
插入尾部：需要改变last的指向
插入中间：需要先找到目标节点的位置，记录前一个节点和当前节点，改变两个节点的指针

template<typename E>
inline void QFMutableList<E>::add(int index, E ele)
{
  if (index<0 || index>len) {
    cout << "下标不合理" << endl;
    return;
  }
  // 创建新节点
  QFLinkNode<E>* node = new QFLinkNode<E>(ele);
  // 1. index=0
  if (index == 0) {
    node->next = first;
    first->prev = node;
    first = node;
    len++;
  }
  else if (index == len) {
    //2. 尾节点
    last->next = node;
    node->prev = last;
    last = node;
    len++;
  }
  else {
    QFLinkNode<E>* cur = getNode(index);
    // 找到目标位置前一个节点
    QFLinkNode<E>* prev = cur->prev;
    // 找到当前位置的下一个节点
    QFLinkNode<E>* next = cur;
    // prev指向当前新的节点，当前新的节点的prev指向prev节点
    prev->next = node;
    node->prev = prev;
    // node指向next节点，node的next指向next节点，next节点的prev指向node
    node->next = next;
    next->prev = node;

    len++;
  }
}

删除指定下标元素

依然是需要分成三种清空

头部
尾部
中间节点

template<typename E>
inline E QFMutableList<E>::remove(int index)
{
  // 只有一个节点
  E temp;
  if (len == 1) {
    temp = first->ele;
    delete first;
    first = nullptr;
    last = nullptr;
    len--;
  }
  else {
    // 删除首节点
    if (index == 0) {
      temp = first->ele;
      first = first->next;
      delete first->prev;
      first->prev = nullptr;
      len--;
    }else if(index == len-1){
    // 尾节点
      temp = last->ele;
      last = last->prev;
      delete last->next;
      last->next = nullptr;
      len--;
    }
    else {
      // 中间节点
      // 记录当前节点的前后节点
      QFLinkNode<E>* node = getNode(index);
      temp = node->ele;

      QFLinkNode<E>* pre = node->prev;
      QFLinkNode<E>* nxt = node->next;
      // 改变前后节点指向
      pre->next = nxt;
      nxt->prev = pre;

      // 删除节点
      delete node;

      len--;
    }
  }

  return temp;
}

根据元素获取指定下标

template<typename E>
inline int QFMutableList<E>::index(E ele)
{
  QFLinkNode<E>* node = first;
  for (int i = 0; i < len; i++) {
    if (node->ele == ele) {
      return i;
    }
    cur = cur->next;
  }
  return -1;
}

根据内容删除节点

首先需要获取下标，然后根据下标删除

template<typename E>
inline bool QFMutableList<E>::removeElement(E ele)
{
  // 获取下标
  int idx = index(ele);
  if (idx == -1) {
    return false;
  }

  // 删除元素
  remove(idx);

  return true;
}

清空所有的节点

template<typename E>
inline void QFMutableList<E>::clear()
{
  // 删除所有的节点
  if (this->first != nullptr) {
    QFLinkNode<E>* p1 = this->first;
    QFLinkNode<E>* p2 = p1->next;
    while (p2 != nullptr) {
      delete p1;
      p1 = p2;
      p2 = p2->next;
    }
    delete p1;
    this->first = nullptr;
    this->last = nullptr;
    len = 0;
  }
}

修改元素

template<typename E>
inline E QFMutableList<E>::set(int index, E ele)
{
  // 1.获取节点
  QFLinkNode<E>* cur  = getNode(index);
  E temp = cur->ele;
  //2.修改数据
  cur->ele = ele;
  return temp;
}

获取指定下标节点元素

template<typename E>
inline E QFMutableList<E>::get(int index)
{
  // 获取节点
  QFLinkNode < E>* cur = getNode(index);
  return cur->ele;
}

排序(冒泡)

交换节点的代价比较大，往往需要牵涉到三个节点，而我们不需要改变节点位置，只需要改变节点值，这是最简单的一种方式。

template<typename E>
inline void QFMutableList<E>::sort()
{
  for (int i = 0; i < len; i++) {
    for (int j = 0; j < len - i - 1; j++) {
      QFLinkNode<E>* node1 = getNode(j);
      QFLinkNode<E>* node2 = getNode(j + 1);
      if (node1->ele > node2->ele) {
        E temp = node1->ele;
        node1->ele = node2->ele;
        node2->ele = temp;
      }
    }
  }
}

完整代码

#pragma once
#include "QFMutableContainer.h"
#include "QFLinkNode.hpp"
#include <sstream>
using namespace std;



template<typename E>
class QFMutableList: public QFMutableContainer<E>{
private:
  QFLinkNode<E>* first;// 链表头节点
  QFLinkNode<E>* last;  //链表尾节点
  int len;             // 链表长度

  QFLinkNode<E>* getNode(int idx);// 通过下标获取指定节点
public:
  QFMutableList();

  ~QFMutableList() override;

  //末尾添加元素
  void add(E ele) override;

  // 指定位置添加元素
  void add(int index, E ele) override;

  // 删除指定位置元素
  E remove(int index) override;

  // 删除指定元素
  bool removeElement(E ele) override;

  // 清空元素
  void clear() override;

  // 修改指定下标元素
  E set(int index, E ele) override;

  // 获取指定下标元素
  E get(int index = 0) override;

  // 元素排序
  void sort() override;

  // 获取对应元素的下标
  int index(E ele) override;

  //容器元素字符串返回
  string str() override;

  // 容器中元素的数量
  int length() override;
};

template<typename E>
inline QFLinkNode<E>* QFMutableList<E>::getNode(int idx)
{
  QFLinkNode<E>* p = first;
  for (int i = 0; i < idx; i++) {
    p = p->next;
  }
  return p;
}

template<typename E>
inline QFMutableList<E>::QFMutableList()
{
  this->first = nullptr;
  this->last = nullptr;
  len = 0;
}

template<typename E>
inline QFMutableList<E>::~QFMutableList()
{
  // 删除所有的节点
  clear();
}

template<typename E>
inline void QFMutableList<E>::add(E ele)
{
  // 创建一个新的链表
  QFLinkNode<E>* node = new QFLinkNode<E>(ele);

  // 判断元素数量,链表没有元素
  if (len == 0) {
    this->first = node;
    this->last = node;
  }
  else {
    // 链表里面有元素，将节点添加到last节点后
    this->last->next = node;
    node->prev = this->last;
    this->last = node;
  }
  len++;
}

template<typename E>
inline void QFMutableList<E>::add(int index, E ele)
{
  if (index<0 || index>len) {
    cout << "下标不合理" << endl;
    return;
  }
  // 创建新节点
  QFLinkNode<E>* node = new QFLinkNode<E>(ele);
  // 1. index=0
  if (index == 0) {
    node->next = first;
    first->prev = node;
    first = node;
    len++;
  }
  else if (index == len) {
    //2. 尾节点
    last->next = node;
    node->prev = last;
    last = node;
    len++;
  }
  else {
    QFLinkNode<E>* cur = getNode(index);
    // 找到目标位置前一个节点
    QFLinkNode<E>* prev = cur->prev;
    // 找到当前位置的下一个节点
    QFLinkNode<E>* next = cur;
    // prev指向当前新的节点，当前新的节点的prev指向prev节点
    prev->next = node;
    node->prev = prev;
    // node指向next节点，node的next指向next节点，next节点的prev指向node
    node->next = next;
    next->prev = node;

    len++;
  }
}

template<typename E>
inline E QFMutableList<E>::remove(int index)
{
  // 只有一个节点
  E temp;
  if (len == 1) {
    temp = first->ele;
    delete first;
    first = nullptr;
    last = nullptr;
    len--;
  }
  else {
    // 删除首节点
    if (index == 0) {
      temp = first->ele;
      first = first->next;
      delete first->prev;
      first->prev = nullptr;
      len--;
    }else if(index == len-1){
    // 尾节点
      temp = last->ele;
      last = last->prev;
      delete last->next;
      last->next = nullptr;
      len--;
    }
    else {
      // 中间节点
      // 记录当前节点的前后节点
      QFLinkNode<E>* node = getNode(index);
      temp = node->ele;

      QFLinkNode<E>* pre = node->prev;
      QFLinkNode<E>* nxt = node->next;
      // 改变前后节点指向
      pre->next = nxt;
      nxt->prev = pre;

      // 删除节点
      delete node;

      len--;
    }
  }

  return temp;
}

template<typename E>
inline bool QFMutableList<E>::removeElement(E ele)
{
  // 获取下标
  int idx = index(ele);
  if (idx == -1) {
    return false;
  }

  // 删除元素
  remove(idx);

  return true;
}

template<typename E>
inline void QFMutableList<E>::clear()
{
  // 删除所有的节点
  if (this->first != nullptr) {
    QFLinkNode<E>* p1 = this->first;
    QFLinkNode<E>* p2 = p1->next;
    while (p2 != nullptr) {
      delete p1;
      p1 = p2;
      p2 = p2->next;
    }
    delete p1;
    this->first = nullptr;
    this->last = nullptr;
    len = 0;
  }
}

template<typename E>
inline E QFMutableList<E>::set(int index, E ele)
{
  // 1.获取节点
  QFLinkNode<E>* cur  = getNode(index);
  E temp = cur->ele;
  //2.修改数据
  cur->ele = ele;
  return temp;
}

template<typename E>
inline E QFMutableList<E>::get(int index)
{
  // 获取节点
  QFLinkNode < E>* cur = getNode(index);
  return cur->ele;
}

template<typename E>
inline void QFMutableList<E>::sort()
{
  for (int i = 0; i < len; i++) {
    for (int j = 0; j < len - i - 1; j++) {
      QFLinkNode<E>* node1 = getNode(j);
      QFLinkNode<E>* node2 = getNode(j + 1);
      if (node1->ele > node2->ele) {
        E temp = node1->ele;
        node1->ele = node2->ele;
        node2->ele = temp;
      }
    }
  }
}

template<typename E>
inline int QFMutableList<E>::index(E ele)
{
  QFLinkNode<E>* node = first;
  for (int i = 0; i < len; i++) {
    if (node->ele == ele) {
      return i;
    }
    node = node->next;
  }
  return -1;
}

template<typename E>
inline string QFMutableList<E>::str()
{
  if (len == 0) {
    return "[]";
  }

  QFLinkNode<E>* cur = first;
  ostringstream oss;
  oss << "[";
  for (int i = 0; i < len - 1; i++) {
    oss << cur->ele << ", ";
    cur = cur->next;
  }
  oss << cur->ele << "]" << endl;

  return oss.str();
}

template<typename E>
inline int QFMutableList<E>::length()
{
  return len;
}

项目目标

项目分析

定义接口模板类(QFMutableContainer.h)

数组实现

定义数组

实现字符串返回

实现添加元素到末尾

添加元素到指定位置

删除指定下标

寻找指定元素

删除指定元素

清空数组

指定下标修改元素

数组元素排序(冒泡)

完整代码

链表实现

设计链表

定义实现

添加元素

转换为字符串

根据下标获取节点

指定位置插入元素

删除指定下标元素

根据元素获取指定下标

根据内容删除节点

清空所有的节点

修改元素

获取指定下标节点元素

排序(冒泡)

完整代码

评论

站内搜索