流星划过123 2016-07-10 13:06 采纳率: 50%
浏览 2292
已结题

c++问题,实现双向循环链表的插入删除等基本功能,以及构造函数和析构函数

谢谢各位师哥师姐,么么哒
这是 节点定义
template
struct DoubleNode
{

T data;
DoubleNode *right;
DoubleNode *left;

DoubleNode() {}
DoubleNode(const T& data)
{this->data = data;}
DoubleNode(const T& data, DoubleNode* right,DoubleNode* left)
{this->data = data;
this->right = right;
this->left = left;}
};

类的定义

template //类的声明
class HDoubleCircular {

public:
HDoubleCircular() {}//构造函数不会写
~HDoubleCircular();//析构函数不会
bool IsEmpty() const {return head->right == head;}
int Length() const;
bool Find(int k, T& x) const;
T Get(int k)const;
int Indexof(const T& x) const;
int Search(const T& x) const;
HDoubleCircular& Delete(int k);
HDoubleCircular& Insert(int k, const T& x);
void Output(ostream& out) const;

private:
DoubleNode *head;
int size
};

  • 写回答

2条回答 默认 最新

  • Johnny_Law 2016-07-10 21:57
    关注

    之前自己做的题目,类的名字不一定完全契合,但是应该可以参考。

    #include "List.hpp"
    #include
    #include
    #include
    #include

    void list::clear() {
    listPointer p = this->head;
    listPointer q = NULL;
    while (p != NULL) {
    q = p;
    p = p->next;
    delete q;
    }
    this->head = NULL;
    this->_size = 0;
    }

    list::list() {
    this->head = this->tail = NULL;
    this->_size = 0;
    }

    list::list(const list& another) {
    this->head = this->tail = NULL;
    this->_size = 0;
    this->assign(another);
    }

    list::list(const data_type datas[], int length) {
    this->head = this->tail = NULL;
    this->_size = 0;
    this->assign(datas, length);
    }

    list& list::operator=(const list& another) {
    this->assign(another);
    return *(this);
    }

    list::~list() { this->clear(); }

    bool list::empty() const { return this->_size == 0; }

    list::size_type list::size() const { return this->_size; }

    list::data_type& list::front() const {
    return this->empty() ? reinterpret_cast<data_type>(NULL) : head->data;
    }

    list::data_type& list::back() const {
    return this->empty() ? reinterpret_cast<data_type>(NULL) : tail->data;
    }

    inline std::string int2String(int a) {
    std::stringstream ss;
    ss << a;
    return ss.str();
    }

    std::string list::toString(void) const {
    if (this->_size == 0) {
    return "NULL";
    }
    std::string ret;
    listPointer p = this->head;
    ret += "NULL<-";
    while (p != NULL) {
    ret += int2String(p->data);
    if (p != this->tail) {
    ret += "<->";
    }
    p = p->next;
    }
    ret += "->NULL";
    return ret;
    }

    void list::assign(const list& another) {
    if (!(this == &another)) {
    this->clear();
    node* p = another.head;
    while (p != NULL) {
    this->push_back(p->data);
    p = p->next;
    }
    }
    }

    void list::assign(const data_type datas[], int length) {
    this->clear();
    for (int i = 0; i < length; i++) {
    this->push_back(datas[i]);
    }
    }

    void list::push_front(const data_type& data) {
    this->insert(0, data);
    assert(this->head->data == data);
    }

    void list::push_back(const data_type& data) {
    this->insert(this->_size, data);
    assert(this->tail->data == data);
    }

    void list::pop_front(void) { this->erase(0); }

    void list::pop_back(void) { this->erase(this->_size - 1); }

    void list::insert(int position, const data_type& data) {
    if (position == 0) {
    listPointer temp = new listNode(data, this->head);
    this->head = temp;
    assert(this->head != NULL);
    if (this->_size == 0) {
    this->tail = this->head;
    } else {
    this->head->next->prev = head;
    }
    this->_size++;
    } else if (position == this->_size) {
    listPointer temp = new listNode(data, NULL, this->tail);
    this->tail->next = temp;
    this->tail = this->tail->next;
    this->_size++;
    } else {
    listPointer p = at(position - 1);
    if (p != NULL) {
    listPointer temp = new listNode(data, p->next, p);
    p->next->prev = temp;
    p->next = temp;
    this->_size++;
    assert(this->at(position)->data == data);
    }
    }
    }

    void list::erase(int position) {
    if (this->empty()) return;
    if (position == 0) {
    if (this->_size == 1) {
    delete this->head;
    this->tail = this->head = NULL;
    } else {
    assert(head->next != NULL);
    this->head = this->head->next;
    delete this->head->prev;
    this->head->prev = NULL;
    this->_size--;
    }
    } else if (position == this->_size - 1) {
    this->tail = this->tail->prev;
    assert(tail != NULL);
    delete this->tail->next;
    this->tail->next = NULL;
    this->_size--;
    } else {
    listPointer p = at(position);
    if (p != NULL) {
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    this->_size--;
    }
    }
    }

    void list::split(int position, list* dest1, list* dest2) {
    if (dest1 == dest2) {
    throw dest1;
    return;
    }
    if (position < 0 || position > this->_size) return;
    listPointer p = this->head;
    int counter = 0;
    list temp1, temp2;
    while (p != NULL) {
    if (counter == position) {
    break;
    }
    temp1.push_back(p->data);
    p = p->next;
    counter++;
    }
    while (p != NULL) {
    temp2.push_back(p->data);
    p = p->next;
    }
    (*dest1) = temp1;
    (*dest2) = temp2;
    }

    list& list::merge(const list& src1, const list& src2) {
    list temp;
    if (src1.empty()) {
    temp = src2;
    } else {
    temp = src1;
    listPointer p = src2.head;
    while (p != NULL) {
    temp.push_back(p->data);
    p = p->next;
    }
    }
    *(this) = temp;
    return *(this);
    }

    list& list::remove_if(bool (*condition)(list::listPointer)) {
    listPointer p = this->head;
    while (p != NULL) {
    if (condition(p)) {
    if (p == this->head) {
    this->head = this->head->next;
    if (this->head != NULL) {
    this->head->prev = NULL;
    }
    delete p;
    this->_size--;
    p = this->head;
    if (p == NULL) {
    this->tail = NULL;
    }
    } else if (p == this->tail) {
    this->tail = this->tail->prev;
    this->tail->next = NULL;
    delete p;
    this->_size--;
    p = NULL;
    } else {
    p->prev->next = p->next;
    p->next->prev = p->prev;
    listNode* q = p->next;
    delete p;
    p = q;
    this->_size--;
    }
    } else {
    p = p->next;
    }
    }
    return *(this);
    }

    list& list::unique(void) {
    listPointer slow, fast;
    slow = this->head;
    while (slow != NULL) {
    fast = slow->next;
    while (fast != NULL) {
    if (fast->data == slow->data) {
    if (fast == this->head) {
    this->head = this->head->next;
    if (this->head != NULL) {
    this->head->prev = NULL;
    } else {
    this->tail = NULL;
    }
    fast = this->head;
    } else if (fast == this->tail) {
    this->tail = this->tail->prev;
    this->tail->next = NULL;
    delete fast;
    fast = NULL;
    } else {
    fast->next->prev = fast->prev;
    fast->prev->next = fast->next;
    listPointer temp = fast;
    fast = fast->next;
    delete temp;
    }
    this->_size--;
    } else {
    fast = fast->next;
    }
    }
    slow = slow->next;
    }
    return *(this);
    }

    list& list::reverse(void) {
    listPointer p = this->head;
    while (p != NULL) {
    listPointer q = p->prev;
    p->prev = p->next;
    p->next = q;
    p = p->prev;
    }
    listPointer q = this->tail;
    this->tail = this->head;
    this->head = q;
    return *(this);
    }

    list::data_type& list::operator {
    listPointer p = at(index);
    assert(p != NULL);
    return p->data;
    }

    list& list::operator+=(const list& another) {
    return this->merge(*this, another);
    }

    std::ostream& operator<<(std::ostream& os, const list& li) {
    return (os << li.toString());
    }

    觉得可以望采纳。

    评论

报告相同问题?

悬赏问题

  • ¥100 高价邀请复制 域天d8联网狗
  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?