List（double linked）

2019-11-08 01:01:42

字体：大中小

来源：转载

供稿：网友

简易版链表，目前还有些问题， 1.由于构造函数中会new一个Node，所以链表中会多出一个由默认T()构造的Node 2.打印链表中的元素非常不方便等

/*LIST-SEARCH(L,k)x=L.headwhile x!=NIL and key !=k x=x.nextreturn xLIST-INSERT(L,x)x.next= L.headif L.head!=NIL L.head.PRev=xL.head=xx.prev=NILLIST-DELETE(L,x)if x.prev!=NIL x.prev.next=x.nextelse L.head=x.nextif x.next!=NIL x.next.prev=x.prev*/

#pragma oncetemplate<class T>struct Node { T data; Node* prev; Node* next;};template<class T>class List {private: Node<T>* head;public: List(); ~List(); Node<T>* ListSearch(const T& k) const; bool ListInsert(const T rhs); bool ListDelete(T x);};

cpp

#include"List.h"#include<iostream>template<class T>List<T>::List() :head(new Node<T>) { head->prev = nullptr; head->next = nullptr; head->data = T();}template<class T>List<T>::~List() { while (head != nullptr) { auto de = head; head = head->next; delete de; }}template<class T>Node<T>* List<T>::ListSearch(const T& k) const { auto current = head; while (current != nullptr && current->data != k) { current = current->next; } return current;}template<class T>bool List<T>::ListInsert(const T rhs) { auto temp = new Node<T>; temp->data = rhs; head->prev = temp; temp->next = head; temp->prev = nullptr; head = temp; return true;}template<class T>bool List<T>::ListDelete(T x) { auto de = ListSearch(x); if (de != nullptr) { if (de->prev == nullptr&&de->next == nullptr) { delete de; }else if (de->prev == nullptr) { head = de->next; head->prev = nullptr; de->next = nullptr; delete de; }else if (de->next == nullptr){ de->prev->next = nullptr; de->prev = nullptr; delete de; } else { de->prev->next = de->next; de->next->prev = de->prev; de->prev = nullptr; de->next = nullptr; delete de; } return true; } return false;}

text:

int main() { List<int> Li; Li.ListInsert(1); Li.ListInsert(2); Li.ListInsert(3); Li.ListInsert(4); Li.ListInsert(5); std::cout << Li.ListSearch(1)->data << std::endl; std::cout << Li.ListSearch(2)->data << std::endl; std::cout << Li.ListSearch(3)->data << std::endl; std::cout << Li.ListSearch(4)->data << std::endl; std::cout << Li.ListSearch(5)->data << std::endl; Li.ListDelete(3); Li.ListDelete(5); return 0;}