C++有序双向链表

1. 遍历的时候不只用value check，还会用到address check

2. C++ 生成随机数

主要函数：

1. 在双向链表插入新节点

2. 计算双向链表中元素的总个数

2. 删除某个值的所有元素

3. 删除某个值的单个元素

4. 统计等于某个值的元素个数

此外有一个Output函数用来输出测试结果

头结点是head, 如为NULL则该双向链表为空

感悟：

觉得在处理特殊单个节点的情况比较麻烦，要额外考虑出来

此外，用地址检测来确认遍历一圈，而不是用值data来检测

代码（包括测试的main函数）：

[cpp]
view plain
copy

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
//Forward Declaration
template<class Type>
class DoubleLinkedList;
//Node with two pointers *next and *prev
template<class Type>
class Node{
friend class DoubleLinkedList<Type>;
private:
Type data;
Node *next;
Node *prev;
public:
Type getData(){
return data;
}
Node(): next(NULL),prev(NULL){}
Node(const Type& data){
Node::data = data;
next = NULL;
prev = NULL;
}
};
template<class Type>
class DoubleLinkedList{
private:
Node<Type> *head;
public:
DoubleLinkedList(): head(NULL){}
DoubleLinkedList(Node<Type>* head){
DoubleLinkedList::head = head;
head->next = head;
head->prev = head;
}
~DoubleLinkedList();
//Insert a new Node into the Double Linked List
Node<Type>* Insert(const Type& data);
//Delete all elements equal @parameter data
void DeleteAllElementsEqual(const Type& data);
//Delete one element equal @parameter data
void DeleteOneElementEqual(const Type& data);
//Get Count Of Element equal @parameter data
int GetCountOfElmentsEqual(const Type& data);
int getSize();
void Clear();
void Output();
};
template<class Type>
Node<Type>* DoubleLinkedList<Type>::Insert(const Type& data){
if(head == NULL){
DoubleLinkedList::head = new Node<Type>(data);
head->next = head;
head->prev = head;
return head;
}else{
Node<Type> *currentNode = head;
while(true){
/*
* if it traverses all the link , and has insert it in the last place
* or, finds the correct place to insert,
* then create the new Node(data),
* if new data smaller than the head ,
* then change the head pointer to the new inserted node
*/
if(currentNode->next == head || currentNode->data == data ||
(currentNode->data < data && data < currentNode->next->data)){
Node<Type>* newNode = new Node<Type>(data);
newNode->next = currentNode->next;
currentNode->next = newNode;
//here we insert a new Node, but
//its next pointer has been already modified!
newNode->prev = currentNode;
newNode->next->prev = newNode;
if(newNode->data < head->data)
head = newNode;
return newNode;
}
currentNode = currentNode->next;
}
}
}
template<class Type>
void DoubleLinkedList<Type>::Output(){
cout << endl << “OUTPUT: “ << endl;
if(head == NULL){
cout << “\nNULL LIST! “ << endl;
return;
}
Node<Type>* currentNode = head;
//Sequential Traversal from head
cout << “Sequential Traversal from head: “ << endl;
for(int i = 0;i < getSize();i++){
cout << currentNode->data << “, “;
currentNode = currentNode->next;
}
//Conversal Traversal from head
currentNode = head;
cout << endl << “Converse Traversal from head: “ << endl;
for(int i = 0;i < getSize();i++){
cout << currentNode->data << “, “;
currentNode = currentNode->prev;
}
cout << endl;
}
template<class Type>
int DoubleLinkedList<Type>::getSize(){
int size = 0;
if(head == NULL)
return size;
else{
Node<Type> *currentNode = head;
do{
size++;
}while((currentNode = currentNode->next) != head);
}
return size;
}
template<class Type>
void DoubleLinkedList<Type>::DeleteAllElementsEqual(const Type& data){
if(head == NULL)
return;
Node<Type> *currentNode = head;
//First, find the node whose value equal data
bool isExisted = false;
do{
if(currentNode->data == data){
isExisted = true;
break;
}
}while((currentNode = currentNode->next) != head);
if(isExisted){
while(currentNode->data == data){
//only one node left
if(currentNode == currentNode->next){
delete head;
head = NULL;
return;
}
//more than one node left
Node<Type> *tempNode = currentNode;
currentNode->prev->next = currentNode->next;
currentNode->next->prev = currentNode->prev;
currentNode = currentNode->next;
delete tempNode;
}
}
}
template<class Type>
void DoubleLinkedList<Type>::DeleteOneElementEqual(const Type& data){
if(head == NULL)
return;
Node<Type> *currentNode = head;
bool isExisted = false;
do{
if(currentNode->data == data){
isExisted = true;
break;
}
}while((currentNode = currentNode->next) != head);
if(isExisted){
//only one node left
if(currentNode == currentNode->next){
delete head;
head = NULL;
}
//More than one node left
Node<Type> *tempNode = currentNode;
currentNode->prev->next = currentNode->next;
currentNode->next->prev = currentNode->prev;
delete tempNode;
}
}
template<class Type>
void DoubleLinkedList<Type>::Clear(){
if(head == NULL)
return;
Node<Type> *currentNode = head;
do{
Node<Type> *tempNode = currentNode;
currentNode = currentNode->next;
delete tempNode;
}while(currentNode != head);
head = NULL;
}
template<class Type>
int DoubleLinkedList<Type>::GetCountOfElmentsEqual(const Type& data){
int count = 0;
Node<Type> *currentNode = head;
do{
if(currentNode->data == data)
count++;
}while((currentNode = currentNode->next) != head);
return count;
}
template<class Type>
DoubleLinkedList<Type>::~DoubleLinkedList(){
if(head == NULL)
return;
Node<Type> *currentNode = head->next;
while(currentNode != head){
Node<Type> *tempNode = currentNode;
currentNode = currentNode->next;
delete tempNode;
tempNode = NULL;
}
delete head;
head = NULL;
}
//Test Main
int main() {
DoubleLinkedList<int> *dList = new DoubleLinkedList<int>();
cout << “RANDOM INPUT: “ << endl;
srand(unsigned(time(0)));
for(int i = 0;i < 20;i++){
int newNumber = rand() % 10;
cout << dList->Insert(newNumber % 6)->getData() << ” , “;
}
cout << “\nlist size: “ << dList->getSize();
dList->Output();
cout << endl << “Count Elements equal 1: “;
cout << endl << “Number of All Elements equal 1: “
<< dList->GetCountOfElmentsEqual(1) << endl;
cout << endl << “Delete One Elements equal 2: “;
dList->DeleteOneElementEqual(2);
cout << endl << “list size after Delete One Element: “ << dList->getSize();
dList->Output();
cout << endl << “Delete All Elements equal 3: “;
dList->DeleteAllElementsEqual(3);
cout << endl << “list size after Delete: “ << dList->getSize();
dList->Output();
cout << endl << “Clear List: “;
dList->Clear();
cout << endl << “list size after Clear: “ << dList->getSize();
return 0;
}

输出：

C++有序双向链表

转载于:https://www.cnblogs.com/hktk/archive/2012/09/22/2698365.html

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/110316.html原文链接：https://javaforall.net

相关推荐

golang操作elasticsearch详解[通俗易懂]

eclipse配置tomcat安装及配置教程_vbras部署教程

数据库关系代数表达式学习[通俗易懂]

date和localdatetime转换_localDate

Dingo Api请求接口404？

MySQL连接查询

发表回复