1. 遍历的时候不只用value check， 还会用到address check
2. C++ 生成随机数
主要函数：
1. 在双向链表插入新节点
2. 计算双向链表中元素的总个数
2. 删除某个值的所有元素
3. 删除某个值的单个元素
4. 统计等于某个值的元素个数
此外有一个Output函数用来输出测试结果
头结点是head, 如为NULL则该双向链表为空
感悟：
觉得在处理特殊单个节点的情况比较麻烦，要额外考虑出来
此外，用地址检测来确认遍历一圈，而不是用值data来检测
代码（包括测试的main函数）：
- #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;
- }
输出：
转载于:https://www.cnblogs.com/hktk/archive/2012/09/22/2698365.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/110316.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...