首页 > 代码库 > C++__双向链表(练习)

C++__双向链表(练习)

双向链表

 

link.h

#ifndef LINK_H_
#define LINK_H_

#define HEADER 0
#define TAIL -1

typedef int data_type;

enum LINK_OP {
    LINK_ERR = -1, LINK_OK
};

class LINK {
private:
    data_type data;
    LINK *next;
    LINK *last;
public:
    LINK();
    LINK(data_type data);
    virtual ~LINK();

    data_type getData() const;
    LINK *getLast() const;
    LINK *getNext() const;
    void setData(data_type data);
    void setLast(LINK *last);
    void setNext(LINK *next);

//    LINK *CreateList(data_type tData);
//    void DestroyList(LINK *pList);
    int InsertItem(LINK *pList, data_type tData, int iOffset);
    int DeleteItem(LINK *pList, data_type *pData, int iOffset);
    int UpdateItem(LINK *pList, data_type tNew, data_type tOld);
    int SearchItem(LINK *pList, data_type tData);
    void ShowList(LINK *pList, int iFlag);
    void operator delete(void *pList);
};

#endif /* LINK_H_ */

 

 

link.cpp

#include "LINK.h"
#include <iostream>
using namespace std;

LINK::LINK() {
    // TODO Auto-generated constructor stub
    this->setData(0);
    this->setLast(this);
    this->setNext(this);
}

LINK::LINK(data_type data) {
    // TODO Auto-generated constructor stub
    this->setData(data);
    this->setLast(this);
    this->setNext(this);
}

LINK::~LINK() {
    // TODO Auto-generated destructor stub
}

data_type LINK::getData() const {
    return data;
}

LINK *LINK::getLast() const {
    return last;
}

LINK *LINK::getNext() const {
    return next;
}

void LINK::setData(data_type data) {
    this->data =http://www.mamicode.com/ data;
}

void LINK::setLast(LINK *last) {
    this->last = last;
}

void LINK::setNext(LINK *next) {
    this->next = next;
}

/*
LINK *LINK::CreateList(data_type tData) {
    LINK *pList = new LINK(tData);
    if (!pList)
        return NULL;

    return pList;
}

void LINK::DestroyList(LINK *pList) {
    if (!pList)
        return;

    LINK *Tmp = pList->getNext();
    while (pList != Tmp) {
        pList->setNext(Tmp->getNext());
        delete Tmp;
        Tmp = pList->getNext();
    }
    delete pList;
    pList = NULL;

    return;
}
*/

int LINK::InsertItem(LINK *pList, data_type tData, int iOffset) {
    if ((!pList) || -1 > iOffset)
        return LINK_ERR;

    LINK *New = new LINK(tData);
    if (!New)
        return LINK_ERR;
    LINK *Tmp = NULL;
    switch (iOffset) {
    case HEADER:
        Tmp = pList->getNext();
        New->setNext(Tmp);
        Tmp->setLast(New);
        New->setLast(pList);
        pList->setNext(New);
        break;

    case TAIL:
        Tmp = pList->getLast();
        Tmp->setNext(New);
        New->setNext(pList);
        New->setLast(Tmp);
        pList->setLast(New);
        break;

    default:
        Tmp = pList->getNext();
        while (iOffset--) {
            Tmp = Tmp->getNext();
        }
        New->setNext(Tmp->getNext());
        Tmp->getNext()->setLast(New);
        New->setLast(Tmp);
        Tmp->setNext(New);
        break;
    }

    return LINK_OK;
}

int LINK::DeleteItem(LINK *pList, data_type *pData, int iOffset) {
    if ((!pList) || (!pData) || -1 > iOffset)
        return LINK_ERR;

    LINK *Del = NULL;
    switch (iOffset) {
    case HEADER:
        Del = pList->getNext();
        *pData = http://www.mamicode.com/Del->getData();
        pList->setNext(Del->getNext());
        Del->getNext()->setLast(pList);
        break;

    case TAIL:
        Del = pList->getLast();
        *pData = http://www.mamicode.com/Del->getData();
        pList->setLast(Del->getLast());
        Del->getLast()->setNext(pList);
        break;

    default:
        Del = pList->getNext();
        while (iOffset--) {
            Del = Del->getNext();
        }
        Del->getNext()->setLast(Del->getLast());
        Del->getLast()->setNext(Del->getNext());
        *pData = http://www.mamicode.com/Del->getData();
        break;
    }
    Del->setNext(NULL);
    delete Del;

    return LINK_OK;
}

int LINK::UpdateItem(LINK *pList, data_type tNew, data_type tOld) {
    if (!pList)
        return LINK_ERR;

    int flage = 1;

    LINK *Tmp = pList;
    while (flage) {
        if (Tmp->getData() == tOld) {
            Tmp->setData(tNew);
            break;
        }
        Tmp = Tmp->getNext();
        if (Tmp == pList)
            flage = 0;
    }

    return LINK_OK;
}

int LINK::SearchItem(LINK *pList, data_type tData) {
    if (!pList)
        return LINK_ERR;

    int i = 0;
    int flage = 1;
    LINK *Tmp = pList;
    while (flage) {
        if (Tmp->getData() == tData) {
            cout << "The data is No." << i << endl;
            return i;
        }
        Tmp = Tmp->getNext();
        i++;
        if (Tmp == pList)
            flage = 0;
    }

    return LINK_OK;
}

void LINK::ShowList(LINK *pList, int iFlag) {
    if (!pList)
        return;

    int flage = 1;

    LINK *Tmp = NULL;
    switch (iFlag) {
    case HEADER:
        Tmp = pList;
        while (flage) {
            cout << Tmp->getData() << "  ";
            Tmp = Tmp->getNext();
            if (Tmp == pList)
                flage = 0;
        }
        break;

    case TAIL:
        Tmp = pList;
        while (flage) {
            cout << Tmp->getData() << "  ";
            Tmp = Tmp->getLast();
            if (Tmp == pList)
                flage = 0;
        }
        break;

    default:
        break;
    }
    cout << endl;

    return;
}

void LINK::operator delete(void *pList) {
    if (!pList)
        return;

    LINK *Tmp = ((LINK *) pList)->getNext();
    while ((Tmp != pList) && (NULL != Tmp)) {
        ((LINK *)pList)->setNext(Tmp->getNext());
        cout<<Tmp->getData()<<"  ";
        free(Tmp);
        Tmp = ((LINK *) pList)->getNext();
    }
    cout<<((LINK *)pList)->getData()<<endl;
    free(pList);

    return;
}

 

 

main.cpp

#include "LINK/LINK.h"

#include <iostream>
using namespace std;

void function() {
    int i = 9;
    LINK *pList = new LINK(i);
    if (!pList)
        return;

    while (i--) {
        pList->InsertItem(pList, i, 0);
    }

//    link.ShowList(pList, 0);
    pList->ShowList(pList, -1);
    pList->InsertItem(pList, 999, 7);
    pList->ShowList(pList, -1);
    pList->DeleteItem(pList, &i, 1);
    pList->ShowList(pList, -1);
    pList->DeleteItem(pList, &i, 11);
    pList->ShowList(pList, -1);
    pList->UpdateItem(pList, 888, 999);
    pList->ShowList(pList, -1);
    pList->SearchItem(pList, 5);
    pList->ShowList(pList, -1);
//    pList->DestroyList(pList);
    delete pList;
    cout << "end" << endl;

}

int main() {
    function();
    return 0;
}

 

C++__双向链表(练习)