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

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


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