算法导论10.2链表
带哨兵的双向链表,代码中我使用了nullptr,所以需要编译器升级,我的编译器是gcc/g++ 4.7.0这是可以的,编译的时候加参数—std=c++0x
节点中还可能有卫星元素
/* * IA_10.2LinkedLists.cpp * * Created on: Feb 12, 2015 * Author: sunyj */ #include <stdint.h> #include <iostream> class ListNode { public: ListNode() : key(0), data(0), prev(nullptr), next(nullptr) { } ListNode(int64_t const k, int64_t d) : key(k), data(d), prev(nullptr), next(nullptr) { } int64_t key; int64_t data; ListNode* prev; ListNode* next; }; // LIST-SEARCH(L, k) // x = L.nil.next // while ( x != L.nil and x.key != k) // x = x.next // return x // LIST-INSERT(L, x) // x.next = L.nil.next // L.nil.next.prev = x // L.nil.next = x // x.prev = L.nil // LIST-DELETE(L, x) // x.prev.next = x.next // x.next.prev = x.prev class LinkedList { public: LinkedList() : nil(&m_nil) { nil->prev = nil; nil->next = nil; nil->data = -1; // } ListNode* search(int64_t const k) { ListNode* x = nil->next; while (x != nil && k != x->key) { x = x->next; } return x; } void insert(ListNode* x) { x->next = nil->next; nil->next->prev = x; nil->next = x; x->prev = nil; } void del(ListNode* x) { x->prev->next = x->next; x->next->prev = x->prev; } void print() { ListNode* x = nil->next; while (nil != x) { std::cout << x->key << " "; x = x->next; } std::cout << std::endl; } private: ListNode m_nil; // empty list has noe node, pointer nill points to it. ListNode* nil; }; int main() { LinkedList list; ListNode node1(1, 100); ListNode node4(4, 400); ListNode node16(16, 1600); ListNode node9(9, 900); list.insert(&node1); list.insert(&node4); list.insert(&node16); list.insert(&node9); list.print(); ListNode node25(25, 2500); list.insert(&node25); list.print(); list.del(&node1); list.print(); ListNode* tmp; tmp = list.search(9); list.del(tmp); list.print(); return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。