双向循环链表 C++实现
发布时间：2024-11-08
双向循环链表
#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;
双向循环链表 C++实现.doc
将本文的Word文档下载到电脑
上一篇：第八章 内燃机污染物的生成与控制
