注册 登录
编程论坛 → 数据结构与算法

数据结构学习贴....《学习的开始》

z286503288 发布于 2011-08-24 00:08， 830 次点击
因为刚刚开始学习数据结构...开一个帖子发我做数据结构后面习题的答案....大概就这样吧....另外...我用的是C++和C...虽然大部分都是用C++没怎么用C....各位看官请不必手下留情，尽情吐槽

首先是链式线性表.
#ifndef CHAIN_H
#define CHAIN_H

#include <iostream>
using namespace std;


template<class T>
class Chain{
private:
    template<class T>
    class ChainNode{
        friend Chain<T>;
    private:
        T data;
        ChainNode<T> *link;
    };

public:
    Chain()
     { first = 0; length = 0; }
    Chain(const Chain<T> &c);
    ~Chain();

    bool isEmpty() const
     { return length == 0; }
    int Length() const
     { return length; }
    bool Find(int k, T &x)const;
    int Search(const T &x) const;

    Chain<T>& Delete(int k, T &x);
    Chain<T>& Insert(int k, const T &x);
    void Output(ostream &out);

    void Reverse();
    void Alternate(const Chain<T> &a, const Chain<T> &b);
    void Merge(const Chain<T> &a, const Chain<T> &b);
    void Split(Chain<T> &a, Chain<T> &b);
private:
    ChainNode<T> *first;
    int length;
};

template<class T>
void Chain<T>::Split(Chain<T> &a, Chain<T> &b)
{
    ChainNode<T> *p = first;
    int n = 1, m = 1;
    for(int i = 0; i != length; i++){
        if((i+1)%2){
            a.Insert(n++, p->data);
        }else{
            b.Insert(m++, p->data);
        }
        p = p->link;
    }
}

template<class T>
void Chain<T>::Merge(const Chain<T> &a, const Chain<T> &b){
    ChainNode<T> *a1 = a.first, *b1 = b.first;
    int value = 0;// 0 1 2 3
    int i = 1, n = 0, m = 0;
    while(1){
        if(value == 0){

            if(b.length == m){
                value = 2;
                continue;
            }else{
                value = 1;
            }

            if(a1->data >= b1->data){
                value = 1;
                continue;
            }

            Insert(i++, a1->data);
            a1 = a1->link;
            n++;
            if(b.length == m){
                value = 2;
            }else{
                value = 1;
            }
        }else if(value == 1){

            if(a.length == n){
                value = 3;
                continue;
            }else{
                value = 0;
            }

            if(a1->data <= b1->data){
                value = 1;
                continue;
            }

            Insert(i++, b1->data);
            b1 = b1->link;
            m++;
            if(a.length == n){
                value = 3;
            }else{
                value = 0;
            }
        }else if(value == 2){
            ;
            for(int j = i; n != a.length; ++n){
                Insert(j++, a1->data);
                a1 = a1->link;
            }
            break;
        }else{
            ;
            for(int j = i; m != b.length; ++m){
                Insert(j++, b1->data);
                b1 = b1->link;
            }
            break;
        }
    }   
}

template<class T>
void Chain<T>::Alternate(const Chain<T> &a, const Chain<T> &b)
{
    ChainNode<T> *a1 = a.first, *b1 = b.first;
    int value = 0;// 0 1 2 3
    int i = 1, n = 0, m = 0;
    while(1){
        if(value == 0){
            Insert(i++, a1->data);
            a1 = a1->link;
            n++;
            if(b.length == m){
                value = 2;
            }else{
                value = 1;
            }
        }else if(value == 1){
            Insert(i++, b1->data);
            b1 = b1->link;
            m++;
            if(a.length == n){
                value = 3;
            }else{
                value = 0;
            }
        }else if(value == 2){
            for(int j = i; n != a.length; ++n){
                Insert(j++, a1->data);
                a1 = a1->link;
            }
            break;
        }else{
            for(int j = i; m != b.length; ++m){
                Insert(j++, b1->data);
                b1 = b1->link;
            }
            break;
        }
    }
}

template<class T>
void Chain<T>::Reverse()
{

    int value;
    if(length % 2){
        value = 0;
    }else{
        value = 1;
    }
    T x;
    ChainNode<T> *p = first, *q = first;
    for(int i = 0; i != length/2-value; ++i){
        for(int j = 1; j != length - i; ++j){
            q = q->link;
        }
        x = p->data;
        p->data = q->data;
        q->data = x;
        
        p = p->link;
        
    }
}

template<class T>
bool Chain<T>::Find(int k, T &x) const
{
    if (k <= 0 && k >= length){
        cerr << "Find:error input for K.";
        return false;
    }
    for(int i = 0; i != k; i++){
        first = first->link;
    }
    x = first->data;
    return true;

}

template<class T>
int Chain<T>::Search(const T &x) const
{
    for(int i = 0; i != length; i++){
        if(first->data == x)
            return i+1;
        first = first->link;
    }
   
    return 0;
}

template<class T>
void Chain<T>::Output(ostream &out)
{
   
    ChainNode<T> *p = first;
    for(int i = 0; i != length; i++){
        cout << p->data << " ";
        p = p->link;
    }
}

template<class T>
Chain<T>& Chain<T>::Delete(int k, T &x)
{
    if (k <= 0 && k >= length){
        cerr << "Delete:error input for K.";
        return *this;
    }

    ChainNode<T> *p;
    for(int i = 1; i != k; i++){
        first = first->link;
    }
    x = first->data;
    p = first->link;
    first->link = p->link;

    delete p;
    --length;
    return *this;
}

template<class T>
Chain<T>& Chain<T>::Insert(int k, const T &x)
{
    if(k <= 0){
        cerr << "Insert: error";
        return *this;
    }

    ChainNode<T> *p = new ChainNode<T>;
    if(k == 1){
        p->data = x;
        if(length != 0)
            p->link = first;
        else
            p->link = 0;
        first = p;
    }else if(k >= length){
        p->data = x;
        p->link = 0;

        ChainNode<T> *q = first;
        for(int j = 1; j != length; j++){
            q = q->link;
        }
        q->link = p;
    }else{
        p->data = x;
        p->link = first->link;
        first->link = p;
    }
    ++length;

    return *this;
}

template<class T>
Chain<T>::Chain(const Chain<T> &c)
{
    Chain<T> *c1 = new Chain<T>;

    ChainNode<T> *p = c.first;
    for(int i = 0; i != c.length; i++){
        c1->Insert(i+1, p->data);
        p = p->link;
    }
    first = c1->first;
    length = c1->length;


}

template<class T>
Chain<T>::~Chain()
{
    ChainNode<T> *p = first;
    for(int i = 0; i != length; i++){
        first = p;
        p = p->link;
        delete first;
    }
}

#endif

[ 本帖最后由 z286503288 于 2011-8-27 22:34 编辑 ]
7 回复
#2
z2865032882011-08-24 00:11
另外我想吐槽一下...看我用的是数据结构、算法与应用--C++语言描述  机械工业....
这个课后的习题敢不敢别这么多
每一章居然都有上百题....难道都要做完吗？

这次是数组线性表
#include <iostream>
using namespace std;

template<class T>
class LinerList{
public:
    LinerList(int Max = 10);
    ~LinerList();

    bool isEmpty() const;
    int Length() const;
    bool Find(int k, T &x) const;
    int Search(const T &x) const;
    void OutPut(ostream &out) const;

    LinerList<T> &Delete(int k, T &x);
    LinerList<T> &Insert(int k, const T &x);

    ostream& operator<<(ostream &out, const LinerList<T> &l)
    {
        l.OutPut(out);
        return out;
    }
private:
    int length
    T *first;
    int MaxSize
};

template<class T>
LinerList<T>::LinerList(int Max = 10)
{
    MaxSize = Max;
    length = 0;
    first = new T[Max];
}

template<class T>
LinerList<T>::~LinerList()
{
    MaxSize = 0;
    length = 0;
    delete [] first;
}

template<class T>
bool LinerList<T>::isEmpty() const
{
    return length == 0;
}

template<class T>
int LinerList<T>::Length() const
{
    return length;
}

template<class T>
bool LinerList<T>::Find(int k, T &x) const
{
    if(k<0 || k>length){
        cerr << "error : input error!" << endl;
        return false;
    }
    x = first[k];
    return true;
}

template<class T>
int LinerList<T>::Search(const T &x) const
{
    for(int i = 0; i != length; ++i){
        if(first[i] == x)
            return i;
    }
    return -1;
}

template<class T>
void OutPut(ostream &out) const
{
    for(int i = 0; i != length; ++i)
        out << first[i] << " ";

    out << endl;
}

template<class T>
LinerList<T>& LinerList<T>::Delete(int k, T &x)
{
    if(k<0 || k>length){
        cerr << "error : input error!" << endl;
        return 0;
    }

    x = first[k];
    for(; length != k; k++){
        first[k-1] = first[k]        
    }

    length--;

    return *this;
}

template<class T>
LinerList<T>& LinerList<T>::Insert(int k, const T &x)
{//之前插入
    if(k<0 || k>length){
        cerr << "error : input error!" << endl;
        return 0;
    }
    if(length+1 > MaxSize){
        cerr << "No 空间!" << endl;
        return 0;
    }

    for(int i = k; i <= length; ++i){
        first[i] = first[i-1];
    }
    first[k] = x;
    length++;

    return *this;

}

[ 本帖最后由 z286503288 于 2011-8-24 14:45 编辑 ]
#3
z2865032882011-08-24 15:28
修改的死去又活来啊

#ifndef LINERLIST_H
#define LINERLIST_H

#include <iostream>
using namespace std;

template<class T>
class LinerList{
public:
    LinerList(int Max = 1);
    ~LinerList();

    bool isEmpty() const;
    int Length() const;
    int MAXSIZE() const
     { return MaxSize; }
    bool Find(int k, T &x) const;
    int Search(const T &x) const;
    void OutPut(ostream &out) const;

    LinerList<T> &Delete(int k, T &x);
    LinerList<T> &Insert(int k, const T &x);

    void resize();
    void Reverse();
    void Half();
    LinerList(const LinerList<T> &L);

    void Reset()
     { current = &(first[0]); }
    T Current(int k) const;
    bool End() const
     { return current == first[length-1]; }
    bool Front() const
     { return current == first[0]; }
    void Next() const
    {
        if(End())
             //抛出错误;
        current++;
    }
    void Previous() const
    {
        if(Front())
            //抛出错误;
        current--;
    }

    void Alternate(const LinerList<T> &a, const LinerList<T> &b);
    void Merge(const LinerList<T> &a, const LinerList<T> &b);
    void Split(LinerList<T> &a, LinerList<T> &b);
private:
    int length;
    T *first;
    int MaxSize;
    T *current;
};

template<class T>
void LinerList<T>::Split(LinerList<T> &a, LinerList<T> &b)
{
    int m = 1, n = 1;
    for(int i = 0; i != length; ++i){
        if(i % 2){
            a.Insert(m++, first[i]);
        }else{
            b.Insert(n++, first[i]);
        }
    }
}

template<class T>
void LinerList<T>::Merge(const LinerList<T> &a, const LinerList<T> &b)
{
    MaxSize = a.MaxSize + b.MaxSize;
    length = a.length + b.length;
    T *p = new T[MaxSize];
   
    int m = 0, n = 0, i = 0;
    bool bm = true, bn = true;
    while(i != length){

        if(bm && a.first[m] <= b.first[n]){
            p[i++] = a.first[m++];
            if(m == a.length)
                bm = false;
        }else if(bn){
            p[i++] = b.first[n++];
            if(n == b.length)
                bn = false;
        }   
        
    }
    first = p;
}

template<class T>
void LinerList<T>::Alternate(const LinerList<T> &a, const LinerList<T> &b)
{
    MaxSize = a.MaxSize + b.MaxSize;
    length = a.length + b.length;
    T *p = new T[MaxSize];
   

    int value = 0;//设置4个值，0：a插入，1：b插入，2：a为空，3：b为空
    int m = 0, n = 0;
    for(int i = 0; i != length; i++){
        if(value == 0){
            if(n != b.length){
                value = 1;
            }else{
                value = 2;
            }
            p[i] = a.first[m++];
            
        }else if(value == 1){
            if(m != a.length){
                value = 0;
            }else{
                value = 3;
            }
            p[i] = b.first[n++];
        }else if(value == 2){
            for(int j = i; j != length; j++){
                p[j] = a.first[m++];
            }
            break;
        }else{
            for(int j = i; j != length; j++){
                p[j] = b.first[n++];
            }
            break;
        }

    }
    first = p;
}
template<class T>
T LinerList<T>::Current(int k) const
{
    Reset();
    for(int i = 0; i != k; i++){
        Next();
    }
    return *current;
}

template<class T>
LinerList<T>::LinerList(const LinerList<T> &L)
{
   
    T *p = new T[L.MaxSize];
    for(int i = 0; i != L.length; ++i)
        p[i] = L.first[i];
   
    length = L.length;
    MaxSize = L.MaxSize;

    //delete [] first;
    first = p;
    Reset();
}

template<class T>
void LinerList<T>::Half()
{
    // T x;

    if(length != 0){
/*
        int value = length / 2;
        for(int i = 1; i <= value; i++){
            Delete(i+1, x);

        }
*/
        
        int value = length;
        length = 0;
        for(int i = 0, j = 0; i <= value; i += 2, ++j){
            first[j] = first[i];
            ++length;
        }
    }
}

template<class T>
void LinerList<T>::Reverse()
{
    T value;
    if(length % 2 == 0){
        for(int i = 0; i != length/ 2; i++){
            value = first[i];
            first[i] = first[length - i-1];
            first[length - i-1] = value;
        }
    }else{
        for(int i = 0; i != length / 2; i++){
            value = first[i];
            first[i] = first[length - i-1];
            first[length - i-1] = value;
        }
    }
}

template<class T>
void LinerList<T>::resize()
{
    if(length+1 >= MaxSize){
        MaxSize *= 2;
    }else{
        MaxSize /= 2;
    }
        T *list = new T[MaxSize];

        for(int i = 0; i != length; ++i){
            list[i] = first[i];
        }
        delete [] first;
        first = list;

}

template<class T>
LinerList<T>::LinerList(int Max = 1)
{
    MaxSize = Max;
    length = 0;
    first = new T[Max];
    Reset();
}

template<class T>
LinerList<T>::~LinerList()
{
    MaxSize = 0;
    length = 0;
    delete [] first;
}

template<class T>
bool LinerList<T>::isEmpty() const
{
    return length == 0;
}

template<class T>
int LinerList<T>::Length() const
{
    return length;
}

template<class T>
bool LinerList<T>::Find(int k, T &x) const
{
    if(k<0 || k>length){
        cerr << "error : input error!" << endl;
        return false;
    }
    x = first[k];
    return true;
}

template<class T>
int LinerList<T>::Search(const T &x) const
{
    for(int i = 0; i != length; ++i){
        if(first[i] == x)
            return i;
    }
    return -1;
}

template<class T>
void LinerList<T>::OutPut(ostream &out) const
{
    for(int i = 0; i != length; ++i)
        out << first[i] << " ";
}

template<class T>
LinerList<T>& LinerList<T>::Delete(int k, T &x)
{
    if(length*2 < MaxSize){
        resize();
    }

    if(k<0 || k>length){
        cerr << "error : input error!" << endl;
        //抛出错误
    }

    x = first[k-1];
    for(; length != k; k++){
        first[k-1] = first[k];
    }

    length--;

    return *this;
}

template<class T>
LinerList<T>& LinerList<T>::Insert(int k, const T &x)
{//之前插入
    if(length+1 > MaxSize){
        resize();
    }

    if(k<=0 || k>MaxSize){
        cerr << "error : input error!" << endl;
        //抛出错误.
    }
   

    for(int i = k; i <= length; ++i){
        first[i] = first[i-1];
    }
    first[k-1] = x;
    length++;

    return *this;

}

template<class T>
ostream& operator<<(ostream &out, const LinerList<T> &l)
{
    l.OutPut(out);
    return out;
}

#endif

[ 本帖最后由 z286503288 于 2011-8-26 17:26 编辑 ]
#4
z2865032882011-08-27 22:35
链表的基本就到这里...修改了几天
#5
z2865032882011-08-31 10:40
人太少...好是换地方好了...
#6
waterstar2011-09-11 14:44
纯纯的看数据结构的书简直就是一种折磨啊
#7
无名可用2011-09-11 22:55
链表最基本了。树要好好看看，对树的各种操作都渗透了很好的算法思想
1
©2025, BC-CN.NET
电脑版