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

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


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