《数据结构与STL》笔记和习题（1）

最近突然想学习一下C++，就找了一本《C++编程思想》来看，感觉课后习题练手没有

什么感觉，就又找了这本《数据结构与STL》，发现每章后面都有些实验和小项目，练

手蛮不错的，随便也可以试着学习一下STL和模板，为进一步深入学习做准备。

Chapter 2

这一章主要是介绍性的，所以随便看了看，就开始做课后的实验。

#实现一个Linked list，支持简单的Iterator功能

/*
 * A brief implementation of liked list,
 * which supports iterator.
 */

template <class T>
class Linked {
protected:
    struct Node {
        T     ele;
        Node  *next;

        Node(): next(NULL) {}
        Node(const T &x): ele(x), next(NULL) {}
    };

    size_t length; // linked list length
    Node   *head;
    Node   *tail;

public:
    class Iterator{
    private:
        Node *nodePtr;
    public:
        Iterator(Node* newPtr = NULL): nodePtr(newPtr) {}
        Iterator operator++(int); // iterator++
        Iterator operator=(const Iterator&);
        Iterator operator++();    // ++iterator
        T operator*() const;
        bool operator==(const Iterator&) const;
        bool operator!=(const Iterator&) const;
    };

    Linked() {
        tail = new Node();
        head = tail;
        length = 0;
    }
    ~Linked() {
        while (head != tail)
            pop_front();
        delete tail;
    }
    inline size_t size() const;
    void push_front(const T& item);
    void front(T& item) const;
    void pop_front();
    inline bool empty() const;
    inline Iterator begin() const;
    inline Iterator end() const;

};

为了尝试一下模板，我故意把一些函数的实现放在了类的外面，结果返回Iterator的函数

老是报错：没有相关的constructor，deconstructor啥的

template <class T>
Linked<T>::Iterator Linked<T>::Iterator::operator++() {
    nodePtr = nodePtr->next;
    return *this;
}

//在Linked<T>::Iterator前加一个class，就可以了。
template <class T>
class Linked<T>::Iterator Linked<T>::Iterator::operator++() {
    nodePtr = nodePtr->next;
    return *this;
}

百度了一下，“依赖受限名称不能作为类型使用，除非在前面加上 typename关键字“

具体原理，先不管了，现在这不是重点。就先把雷埋在这里吧，呵呵。

下面是一个简单的测试：

#include <iostream>
#include <string>

#include "Linked.h"

using namespace std;

int main() {
    Linked<string> strList;

    string str;
    cout << "Input 10 words" << endl;
    for (int i=0; i<10; i++) {
        cin >> str;
        strList.push_front(str);
    }
    cout << "strList.size: " << strList.size() << endl;
    strList.front(str);
    strList.pop_front();
    strList.front(str);
    cout << "Pop the top, the new front is:  " << str << endl;
    cout << "New size: " << strList.size() << endl;
    cout << "Go through list with iterator: " << endl;
    Linked<string>::Iterator itr;
    for (itr = strList.begin(); itr != strList.end(); itr++)
        cout << *itr << " ";
    cout << endl;
    itr = strList.begin();
    ++itr;
    cout << "The second word: " << *itr << endl;
    return 0;
}

总结一下，感觉自己对C++太不熟悉，这个实验中至少有以下几点不懂：

1） 运算符重载函数返回类型，是引用还是值呢？

2）返回过程中的拷贝构造，还有赋值方面，都疑云重重。

3）模板相当不懂啊。

希望大家能给点意见给我这个悲哀的后进者，谢谢。

最后给出完整代码：

#ifndef LINKED_H
#define LINKED_H

#include <cassert>

/*
 * A brief implementation of liked list,
 * which supports iterator.
 */

template <class T>
class Linked {
protected:
    struct Node {
        T     ele;
        Node  *next;

        Node(): next(NULL) {}
        Node(const T &x): ele(x), next(NULL) {}
    };

    size_t length; // linked list length
    Node   *head;
    Node   *tail;

public:
    class Iterator{
    private:
        Node *nodePtr;
    public:
        Iterator(Node* newPtr = NULL): nodePtr(newPtr) {}
        Iterator operator++(int); // iterator++
        Iterator operator=(const Iterator&);
        Iterator operator++();    // ++iterator
        T operator*() const;
        bool operator==(const Iterator&) const;
        bool operator!=(const Iterator&) const;
    };

    Linked() {
        tail = new Node();
        head = tail;
        length = 0;
    }
    ~Linked() {
        while (head != tail)
            pop_front();
        delete tail;
    }
    inline size_t size() const;
    void push_front(const T& item);
    void front(T& item) const;
    void pop_front();
    inline bool empty() const;
    inline Iterator begin() const;
    inline Iterator end() const;

};

template <class T>
bool Linked<T>::Iterator::operator!=(const Iterator &itr) const {
    if (nodePtr != itr.nodePtr)
        return true;
    return false;
}

template <class T>
bool Linked<T>::Iterator::operator==(const Iterator &itr) const {
    if (nodePtr == itr.nodePtr)
        return true;
    return false;
}

template <class T>
T Linked<T>::Iterator::operator*() const {
    return nodePtr->ele;
}

template <class T>
class Linked<T>::Iterator Linked<T>::Iterator::operator++() {
    nodePtr = nodePtr->next;
    return *this;
}

template <class T>
class Linked<T>::Iterator Linked<T>::Iterator::operator=(const Iterator &itr) {
    if (this != &itr) {
        nodePtr = itr.nodePtr;
    }
    return *this;
}

template <class T>
class Linked<T>::Iterator Linked<T>::Iterator::operator++(int x) {
    Iterator temp = *this;
    nodePtr = nodePtr->next;
    return temp;
}

template <class T>
class Linked<T>::Iterator Linked<T>::begin() const {
    return Iterator(head);
}

template <class T>
class Linked<T>::Iterator Linked<T>::end() const {
    return Iterator(tail);
}

template <class T>
bool Linked<T>::empty() const {
    if (length > 0)
        return true;
    else
        return false;
}

template <class T>
void Linked<T>::pop_front() {
    assert(length > 0);
    Node *oldPtr = head;
    head = head->next;
    delete oldPtr;
    length--;
}

template <class T>
void Linked<T>::front(T &item) const {
    assert(length > 0);
    item = head->ele;
}

template <class T>
void Linked<T>::push_front(const T &item) {
    Node *newPtr = new Node(item);
    newPtr->next = head;
    head = newPtr;
    length++;
}

template <class T>
size_t Linked<T>::size() const {
    return length;
}

#endif // LINKED_H