数据结构练手01 线性表实现

C++的知识点很零碎繁琐，只是总结没啥作用，更多的应该是在实践中找问题。今天我去编写《数据结构，算法与应用 C++语言描述》中线性表的实现代码，感觉写代码能力生疏了好多。

编写过程中，我发现了几个问题，很值得关注：

1、我的代码是通过类模板编写的。很多人写代码的时候，都把声明和实现放在一个头文件里，primer中说要借用export才能实现分离编译，对于这点，我也不是很了解，但是我取巧了下，通过两个 #ifndef....#endif 达到了声明放在.h， 实现放在了.cpp中。

2、模板类中关于<<的重载，需要在声明中加入 <> ，要不然编译不通过。

3、cout 的刷新问题。 如 fun(int& x)， 若我们这么用 cout << fun(y) << y ; 屏幕上显示的不是y更新后的值，而是调用y前的值。而将它分成两个cout来输出，或者刷新后输出，那么将是正确的。

好的，贴代码： 实现环境 vs2010

// linearlist.h
#ifndef MY_LINEARLIST_H    // 在头文件中做保护头
#define MY_LINEARLIST_H
#include <ostream>
using namespace std;
template<class T>
class LinearList{
public:
    LinearList(int cap = 100);
    ~LinearList();
    bool isEmpty();
    int length();
    bool find(int pos, T& hold) const;
    int search(const T& x) const;
    LinearList<T>& drop(int pos, T& hold);
    LinearList<T>& insert(int pos, const T& x);
    void printt(ostream& os)const;
    friend ostream& operator << <>(ostream& os, const LinearList<T>& x);    // 问题二的出错，模板不好掌握呀
private:
    int size;
    int capacity;
    T* element;
};

#endif
#include "LinearList.cpp"           // 这里包含实现文件，这个技巧其实在 《C++ template》中有展示过。欲深入了解模板，此书必读！

// linearlist.cpp实现文件
#ifndef MY_LINEARLIST_CPP   //  这里又来个实现文件的保护头，这样就避免了多重定义，同时通过.h最后的#include实现了 实际上的头文件和实现文件在一个文件中。
#define MY_LINEARLIST_CPP
#include "LinearList.h"
#include <cstdlib>
#include <ostream>
template<class T>
LinearList<T>::LinearList(int cap)
{
    size = 0;
    capacity = cap;
    element = new T[capacity];
}

template<class T>
LinearList<T>::~LinearList(void)
{
    if (element != NULL) {
        delete[] element;
    }
}

template<class T>
bool LinearList<T>::isEmpty ()
{
    return size == 0;
}

template<class T>
int LinearList<T>::length()
{
    return size;
}

template<class T>
bool LinearList<T>::find(int pos,T& hold) const
{
    if (pos > size || pos < 1) return false;
    hold = element[pos-1];
    return true;
}

template<class T>
int LinearList<T>::search(const T& x) const
{
    for (int i=0; i<size; ++i) {
        if (element[i] = x) {
            return i+1;
        }
    }
    return 0;
}

template<class T>
LinearList<T>& LinearList<T>::drop(int pos, T& hold)
{
    if (pos > size || pos < 1) {
        exit(1);
    }
    hold = element[pos-1];
    for(int i=pos; i<size; ++i){
        element[i-1] = element[i];
    }
    --size;
    return *this;
}

template<class T>
LinearList<T>& LinearList<T>::insert(int pos, const T& x)
{
    if(size == capacity){
        T* newElement = new T[capacity*2];
        capacity <<= 1;
        for (int i=1; i<pos; ++i) {
            newElement[i-1] = element[i-1];
        }
        newElement[pos] = x;
        for(int i=pos; i<size; ++i){
            newElement[i+1] = element[i];
        }
        ++size;
        delete[] element;
        element = newElement;
    }else{
        for(int i=size; i>=pos; --i){
            element[i] = element[i-1];
        }
        element[pos-1] = x;
        ++size;
    }
    return *this;
}
template<class T>
void LinearList<T>::printt(ostream& out) const
{
    for (int i=0; i<size; ++i) {
        out << element[i] << " ";
    }
}
template<class T>
ostream& operator<< <>(ostream& out, const LinearList<T>& x)   // 问题2
{
    x.printt(out); return out;
}
#endif

1 int main()
 2 {
 3     LinearList<int> L(5);
 4 
 5     int y=0;
 6     L.insert (1,1);
 7         cout << L << endl;
 8     L.insert (2,2);
 9         cout << L << endl;
10     L.insert (3,3);
11         cout << L << endl;
12     cout << "y before: " << y << endl;
13     cout << "Find " << L.find(2,y) << " "<< y << endl;   // 问题3
14     cout << "y after " << y << endl;
15 
16 }

原文链接: https://www.cnblogs.com/IntellX/archive/2013/05/21/3091961.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍