随笔-13  评论-0  文章-2  trackbacks-0
双向链表的实现（Alpha1.0 ）
  1/**
  2        Double List base on dynamic array
  3        Version: 1.0
  4        Member function as follow:
  5        size()
  6        push_back(T)        // inset an elm
  7        erase(T)        // delete an elm
  8        empty()         // if it is an empty list
  9        print()
 10        find(T&)          // find an elm
 11
 12        Use C++ template
 13**/
 14#include<iostream>
 15using namespace std;
 16template<typename T>
 17struct Node
 18{
 19    T data;
 20    Node<T>* prev;
 21    Node<T>* next;
 22    Node(){ prev = NULL; next = NULL; }
 23};
 24
 25template<typename T>
 26class DList
 27{
 28     private:
 29     Node<T>* head;
 30     int size;
 31     public:
 32     DList();
 33     ~DList(){ delete head; size = 0; }
 34     int Size(){ return size; }
 35     bool empty() { return size == 0; }
 36     void push_back(const T&);
 37     T front() const{ return head->data;}
 38     void find(const T&);
 39     void erase(const T&);
 40     void print() const;
 41};
 42
 43template<typename T> DList<T>::DList()
 44{
 45    head = new Node<T>;
 46    head->prev = NULL;
 47    head->next = NULL;
 48    size = 0;
 49}
 50
 51template<typename T> void DList<T>::push_back(const T& one)
 52{
 53    Node<T>* p = head;
 54    if( size == 0 ) p->data = one;
 55    else
 56    {
 57        while( p->next != NULL )
 58        p = p->next;
 59        Node<T>* new_node = new Node<T>;
 60        new_node->data = one;
 61        new_node->next = NULL;
 62        new_node->prev = p;
 63        p->next = new_node;
 64    }
 65    size++;
 66}
 67
 68template<typename T> void DList<T>::find(const T& one)
 69{
 70    Node<T>* p = head;
 71    while( p->next != NULL )
 72    {
 73        if( p->data == one ) {cout << "It's in the position of " << size - 1 << endl; break;}
 74        else p = p->next;
 75    }
 76    if( p->data == one && p->next == NULL ) cout << "It's the last element" << endl;
 77    else cout << "No such an element!" << endl;
 78}
 79
 80template<typename T> void DList<T>::erase(const T& one)
 81{
 82    Node<T>* p = head;
 83    while( p->next != NULL )
 84    {
 85        if(p->data == one)
 86        {
 87            p->next->prev = p->prev;
 88            p = p->prev;
 89            p->next = p ->next->next;
 90            size--;
 91            break;
 92        }
 93        else p = p->next;
 94    }
 95
 96    if( p->data == one && p->next== NULL )
 97    {
 98        p->prev->next = NULL;
 99        size--;
100    }
101    else
102    cout << "No such an element!" << endl;
103}
104
105template<typename T> void DList<T>::print() const
106{
107    Node<T>* p = head;
108    while( p -> next!= NULL )
109    {
110        cout << p->data << " ";
111        p = p->next;
112    }
113    cout << p->data << endl;
114}
115
116// Test Function
117#include<iostream>
118int main()
119{
120    DList<int> list;
121    int n;
122    cout << "Please input the number which you want to create!" << endl;
123    cin >> n;
124    cout << "Input the number you want to add in the array.\n";
125    cout<< "----------------------------------------------------------------\n\n";
126    while(n--) // cin.hasnext()
127    {
128        int a;
129        cin >> a;
130        list.push_back(a);
131    }
132    cout << "You input the array as follow" << endl;
133    list.print();
134    cout << "Do you want to delete an element ?" << endl;
135    cout << "Yes/No?" << endl;
136    string s;
137    cin >> s;
138    if( s == "yes" || s == "YES" )
139    {
140        cout << "which number?" << endl;
141        int tem;
142        cin >> tem;
143        list.erase(tem);
144        cout << "Now the array as follow" << endl;
145        list.print();
146    }
147    cout << "Do you want to find an element?" << endl;
148    cout << "Yes/No?" << endl;
149    string s2;
150    cin >> s2;
151    if( s2== "yes" || s2 == "YES" )
152    {
153        cout << "which number?" << endl;
154        int tem;
155        cin >> tem;
156        list.find(tem);
157    }
158
159    cout << "Now the size of the array is " << list.Size() << endl;
160    cout << "The first number is :" << list.front() <<endl;
161    cout<< endl;
162    cout<< "----------------------------------------------------------------\n\n";
163    system("pause");
164    return 0;
165
166}
167
168
posted on 2009-02-22 21:58 亦夏 阅读(170) 评论(0)  编辑 收藏 引用 所属分类: DataStruct

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 亦夏