C++实现双向链表(List)

listC++容器类中的“顺序存储结构”所包含的一种结构。list是非连续存储结构,具有双链表结构,支持前向/后向遍历,且支持高效的随机删除/插入。

实现代码如下:

**list.h**

#pragma once

#include<stdio.h>

#include<assert.h>

#include<iostream>

using namespace std;

typedef int DataType;

struct ListNode

{

ListNode* _next;

ListNode* _prev;

DataType _data;

ListNode(DataType x)

:_data(x)

, _next(NULL)

, _prev(NULL)

{}

};

**test.cpp**

#define _CRT_SECURE_NO_WARNINGS 1

#include "list.h"

class List{

typedef ListNode Node;

public:

List()

:_head(new Node(DataType())){

_head->_next = _head;

_head->_prev = _head;

}

List(const List& l)

:_head(new Node(DataType())){

_head->_next = _head;

_head->_prev = _head;

Node* cur = l._head->_next;

while (cur!=l._head){

PushBack(cur->_data);

cur = cur->_next;

}

}

List& operator=(const List& l){

if (this != &l){

//swap(_head, l._head);

}

return *this;

}

~List(){

Node* cur = _head->_next;

while (cur != _head){

Node* next= cur->_next;

delete cur;

cur = next;

}

delete _head;

_head = NULL;

}

void PushBack(DataType x){

Node* prev = _head->_prev;

Node* new_node = new Node(x);

prev->_next = new_node;

new_node->_prev = prev;

_head->_prev = new_node;

new_node->_next = _head;

}

void PushFront(DataType x){//插在头结点之后

Node* cur = _head->_next;

Node* new_node = new Node(x);

new_node->_next = cur;

cur->_prev = new_node;

new_node->_prev = _head;

_head->_next = new_node;

}

void PopBack(){

Node* delete_node = _head->_prev;

Node* cur = delete_node->_prev;

_head->_prev = cur;

cur->_next = _head;

delete delete_node;

}

void PopFront(){

Node* delete_node = _head->_next;

Node* cur = delete_node->_next;

_head->_next = cur;

cur->_prev = _head;

delete delete_node;

}

Node* Find(DataType x){

Node* to_find = _head->_next;

while (to_find != _head){

if (to_find->_data == x){

return to_find;

}

to_find = to_find->_next;

}

return NULL;

}

void Insert(Node* pos, DataType x){//在pos位置前插入数据

assert(pos);

Node* new_node = new Node(x);

Node* prev = pos->_prev;

new_node->_next = pos;

pos->_prev = new_node;

new_node->_prev = prev;

prev->_next = new_node;

}

void Erase(Node* pos){

assert(pos);

Node* prev = pos->_prev;

Node* next = pos->_next;

prev->_next = next;

next->_prev = prev;

delete pos;

}

void Print() const{

Node* cur = _head->_next;

cout <<" _head->";

while (cur!= _head){

cout << cur->_data << "->";

cur = cur->_next;

}

cout << endl;

Node* pos = _head->_prev;

while (pos != _head){

cout << pos->_data << "<-";

pos = pos->_prev;

}

cout << "_head" << endl;

}

private:

Node* _head;

};

void TestList(){

List L;

L.PushBack(1);

L.PushBack(2);

L.PushBack(4);

L.PushBack(5);

L.PopBack();

L.Print();

ListNode* pos = L.Find(1);

printf("pos->data:%d[%p]\n",pos->_data,pos);

pos = L.Find(2);

printf("pos->data:%d[%p]\n", pos->_data, pos);

pos = L.Find(4);

printf("pos->data:%d[%p]\n", pos->_data, pos);

printf("\n");

L.Insert(pos, 3);

L.Print();

L.Erase(pos);

L.Print();

printf("\n");

List L1;

L1.PushFront(4);

L1.PushFront(3);

L1.PushFront(2);

L1.PushFront(1);

L1.Print();

L1.PopFront();

L1.Print();

}

int main(){

TestList();

return 0;

}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。

以上是 C++实现双向链表(List) 的全部内容, 来源链接: utcz.com/p/245210.html

回到顶部