双向循环链表 C++实现

双向循环链表

#ifndef NODE_H

#define NODE_H

#define NULL 0

class node {

friend class LinkList;

private:

node(int element, node *pre, node *next)

{

this->m_element = element;

this->m_next = next;

this->m_pre = pre;

}

~node()

{

}

private:

int m_element;

node *m_next;

node *m_pre;

};

#endif

#ifndef LINKLIST_H

#define LINKLIST_H

#include "node.h"

class LinkList {

public:

LinkList();

virtual ~LinkList();

void addFirst(int i);

void addLast(int i);

void addList(int i, int pos);

int removeFirst();

int removeLast();

双向循环链表

int removeList(int pos);

int getFirst();

int getLast();

int getList(int pos);

void iterate();

private:

node *m_head;

int m_size;

};

#endif

#include <stdio.h>

#include "linkList.h"

//双向循环链表

LinkList::LinkList(): m_size(0)

{

m_head = new node(NULL, NULL, NULL);

m_head->m_next = m_head;

m_head->m_pre = m_head;

}

LinkList::~LinkList()

{

if (m_size)

{

node *p = m_head->m_next;

node *q = p;

for (int i = 0; i < m_size; i++)

{

q->m_next->m_pre = q->m_pre;

q->m_pre->m_next = q->m_next;

p = q;

q = q->m_next;

printf("%d..", p->m_element);

delete p;

双向循环链表

}

}

else

{

printf("The list is empty!!!\n");

}

}

void LinkList::addFirst(int i)

{

m_head->m_next = new node(i, m_head, m_head->m_next); m_head->m_next->m_next->m_pre = m_head->m_next; ++m_size;

}

void LinkList::addLast(int i)

{

m_head->m_pre = new node(i, m_head->m_pre, m_head); m_head->m_pre->m_pre->m_next = m_head->m_pre; ++m_size;

}

void LinkList::addList(int i, int pos)

{

if (pos < 0 || pos > m_size)

{

printf("pos is out of bound!!!\n");

return;

}

node *p = m_head;

if (pos < (m_size / 2.0))

{

for (int i = 0; i < pos; ++i)

{

p = p->m_next;

}

}

else

双向循环链表

{

for (int i = m_size; i >= pos; i--) {

p = p->m_pre;

}

}

p->m_pre = new node(i, p->m_pre, p); p->m_pre->m_pre->m_next = p->m_pre;

++m_size;

}

int LinkList::removeFirst()

{

if (!m_size)

{

printf("The list is empty!!!\n"); return -1;

}

node *p = m_head->m_next;

m_head->m_next = p->m_next; p->m_pre = m_head;

int rc = p->m_element;

delete p;

--m_size;

return rc;

}

int LinkList::removeLast()

{

if (!m_size)

{

printf("The list is empty!!!\n"); return -1;

}

node *p = m_head->m_pre;

双向循环链表

m_head->m_pre = p->m_next; p->m_next = m_head;

int last = p->m_element;

delete p;

--m_size;

return last;

}

int LinkList::removeList(int pos) {

if (!m_size)

{

printf("The list is empty!!!\n"); return -1;

}

node *p = m_head;

if (pos < (m_size / 2.0))

{

for (int i = 0; i < pos; i++) {

p = p->m_next;

}

}

else

{

for (int i = m_size; i >= pos; i--) {

p = p->m_pre;

}

}

p->m_pre->m_next = p->m_next; p->m_next->m_pre = p->m_pre;

int ele = p->m_element;

delete p;

--m_size;

return ele;

}

双向循环链表

int LinkList::getFirst()

{

if (!m_size)

{

printf("The list is empty!!!\n"); return -1;

}

return m_head->m_next->m_element; }

int LinkList::getLast()

{

if (!m_size)

{

printf("The list is empty!!!\n"); return -1;

}

return m_head->m_pre->m_element; }

int LinkList::getList(int pos)

{

if (!m_size)

{

printf("The list is empty!!!\n"); return -1;

}

node *p = m_head;

if (pos < (m_size / 2.0))

{

for (int i = 0; i < pos; i++) {

p = p->m_next;

}

return p->m_element; }

else

{

for(int i = 0; i >= pos; i--)

双向循环链表

{

p = p->m_pre;

}

return p->m_element; }

}

void LinkList::iterate()

{

if (!m_size)

{

printf("The Lise is empty!!!\n"); return;

}

node *p = m_head;

for (int i = 0; i < m_size; i++) {

p = p->m_next;

printf("%d ", p->m_element); }

}

#include <stdio.h>

#include <stdlib.h>

#include "linkList.h"

//双向循环链表

int main(int argc, char**argv) {

// LinkList list;

//

// list.addFirst(1);

// list.addFirst(2);

// list.addLast(3);

// list.addList(4, 2);

// list.addList(5, 3);

//

// list.iterate();

// printf("\n");

双向循环链表

} //printf("%d %d\n", list.getFirst(), list.getLast()); //list.removeList(2); //list.iterate(); LinkList *p = new LinkList; p->addFirst(1); p->addLast(2); p->addLast(3); p->addLast(4); p->removeList(2); delete p; system("pause"); return 0;