发表更新7 分钟读完 (大约1068个字)0次访问

箱子排序

链表用桶排序时间复杂度会较低

1.头文件虚基类linearlist.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#ifndef linearlist_
#define linearlist_
#include <iostream>
#include<string>
using namespace std;
template<class T>
class linearlist
{
public:
    virtual ~linearlist() {};

    virtual bool empty() const = 0;

    virtual int size() const = 0;

    virtual T& get(int theindex) const = 0;
 
    virtual int indexof(const T& theelement) const = 0;

    virtual void erase(int theindex) = 0;

    virtual void insert(int theindex, const T& theelement) = 0;

    virtual void output(ostream& out) const = 0;

};
#endif

2.头文件类声明chain.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#ifndef chain_H_
#define chain_H_
#include"linearlist.h"
template<class T>
struct chainnode
{
    T element;
    chainnode<T>* next;

    chainnode() {}
    chainnode(const T& element) { this->element = element; }
    chainnode(const T& element, chainnode<T>* next)
    {
        this->element = element;
        this->next = next;
    }
};
template<class T>
class chain :public linearlist<T>
{
public:
    chain(int initial = 10);
    chain(const chain<T>&);//复制构造函数
    ~chain();
    //
    bool empty()const { return listsize == 0; }
    int size()const { return listsize; }
    T& get(int theindex)const;
    int indexof(const T& theelement)const;
    void erase(int theindex);
    void insert(int theindex, const T& theelement);
    void output(ostream& out)const;
    void binsort(int range);

    //迭代器
    class iterator;
    iterator begin() { return iterator(firstnode); }
    iterator end() { return iterator(NULL); }

    class iterator
    {
    public:
        typedef forward_iterator_tag iterator_category;
        typedef T value_type;
        typedef ptrdiff_t difference_type;
        typedef T* pointer;
        typedef T& reference;

        // 构造函数
        iterator(chainnode<T>* theNode = NULL)
        {
            node = theNode;
        }

        // 解引用操作符
        T& operator*() const { return node->element; }
        T* operator->() const { return &node->element; }


        iterator& operator++()   // 前加加
        {
            node = node->next; return *this;
        }
        iterator operator++(int)    //后加加
        {
            iterator old = *this;
            node = node->next;
            return old;
        }

        bool operator!=(const iterator right) const
        {
            return node != right.node;
        }
        bool operator==(const iterator right) const
        {
            return node == right.node;
        }
    protected:
        chainnode<T>* node;
    };

protected:
    chainnode<T>* firstnode;//指向链表第一个节点的指针
    int listsize;
};


struct studentrecord
{
    int score;
    string* name;
    int operator != (const studentrecord& x) const
    {
        return score != x.score;
    }
    operator int()const { return score; }
};

#endif

3.类实现chain.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
#include "chain.h"
template<class T>
chain<T>::chain(int initial)//初始容积
{
    if (initial < 1)
    {
        exit(0);
    }
    firstnode = nullptr;
    listsize = 0;

}

template<class T>
chain<T>::chain(const chain<T>& thelist)
{
    //复制构造函数                就是复制链表
    listsize = thelist.listsize;
    //如果链表thelist为空
    if (listsize == 0)
    {
        firstnode = nullptr;
        return;
    }
    //非空，先复制第一个
    chainnode<T>* sourcenode = thelist.firstnode;//要复制链表thelist的节点
    firstnode = new chainnode<T>(sourcenode->element);//复制链表thelist的首元素
    sourcenode = sourcenode->next;
    chainnode<T>* targetnode = firstnode;//当前链表*this的最后一个节点
    while (sourcenode != nullptr)
    {
        //复制剩下的
        targetnode->next = new chainnode<T>(sourcenode->element);
        targetnode = targetnode->next;
        sourcenode = sourcenode->next;
    }
    targetnode->next = nullptr;
}

template<class T>
chain<T>::~chain()
{
    //析构，删除链表所有节点
    while (firstnode)
    {
        chainnode<T>* nextnode = firstnode->next;
        delete firstnode;
        firstnode = nextnode;
    }
}

template<class T>
T& chain<T>::get(int theindex)const
{
    //返回索引为theindex的元素
    //若元素不存在就抛出异常
    /*checkindex(theindex);*/

    //移向所需要的节点
    chainnode<T>* currentnode = firstnode;
    for (int i = 0; i < theindex; i++)
        currentnode = currentnode->next;
    return currentnode->element;
}

template<class T>
int chain<T>::indexof(const T& theelement)const
{
    //返回元素首次出现时的索引，若不存在返回-1
    chainnode<T>* currentnode = firstnode;
    int index = 0;
    while (currentnode && currentnode->element != theelement)
    {
        currentnode = currentnode->next;
        index++;

    }
    if (currentnode == nullptr)
        return -1;
    else
        return index;
}

template<class T>
void chain<T>::erase(int theindex)
{
    /*checkindex(theindex);*/

    chainnode<T>* deletenode;
    if (theindex == 0)
    {
        deletenode = firstnode;
        firstnode = firstnode->next;
    }
    else
    {
        chainnode<T>* p = firstnode;
        for (int i = 0; i < theindex - 1; i++)
            p = p->next;
        deletenode = p->next;
        p->next = p->next->next;

    }
    listsize--;
    delete deletenode;
}

template<class T>
void chain<T>::insert(int theindex, const T& theelement)
{
    if (theindex<0 || theindex>listsize)
    {
        exit(0);
    }
    if (theindex == 0)
        firstnode = new chainnode<T>(theelement, firstnode);
    else
    {
        chainnode<T>* p = firstnode;
        for (int i = 0; i < theindex - 1; i++)
            p = p->next;
        p->next = new chainnode<T>(theelement, p->next);
    }
    listsize++;
}

template<class T>
void chain<T>::output(ostream& out)const
{
    for (chainnode<T>* currentnode = firstnode;
        currentnode;
        currentnode = currentnode->next)
        out << currentnode->element << "  ";
}

template<class T>
ostream& operator<<(ostream& out, const chain<T>& x)
{
    x.output(out);
    return out;
}

//将限制排序作为链表chain的一个成员方法
template<class T>
void chain<T>::binsort(int range)
{
    //创建并初始化箱子
    chainnode<T>** bottom, ** top;
    bottom = new chainnode<T>*[range + 1];
    top = new chainnode<T>*[range + 1];
    for (int b = 0; b <= range; b++)
        bottom[b] = nullptr;


    //把链表的节点分配到箱子
    for (; firstnode; firstnode = firstnode->next)
    {
        int thebin = firstnode->element;
        if (bottom[thebin] == nullptr)
            bottom[thebin] = top[thebin] = firstnode;
        else
        {
            //箱子不空
            top[thebin]->next = firstnode;
            top[thebin] = firstnode;
        }
    }

    //把箱子中的节点收集到有序链表
    chainnode<T>* y = nullptr;
    for (int thebin = 0; thebin <= range; thebin++)
    {
        if (bottom[thebin] != nullptr)
        {
            //箱子不空
            if (y == nullptr)
                firstnode = bottom[thebin];
            else
                y->next = bottom[thebin];
            y = top[thebin];
        }
    }
    if (y != nullptr)
        y->next = nullptr;
    delete[]bottom;
    delete[]top;
}

inline ostream& operator<<(ostream& out, const studentrecord& x)
{
    out << x.score << ' ' << *x.name << endl;
    return out;
}

inline void binsort(chain<studentrecord>& thechain, int range)
{
    //对箱子初始化
    chain<studentrecord>* bin;
    bin = new chain<studentrecord>[range + 1];

    //把学生记录从链表中取出然后分配到箱子里
    int numberofelements = thechain.size();
    for (int i = 1; i <= numberofelements; i++)
    {
        studentrecord x = thechain.get(0);
        thechain.erase(0);
        bin[x.score].insert(0, x);
    }

    //“稳定排序”，取两次正好还是原来的顺序


    //从箱子中收集元素
    for (int j = range; j >= 0; j--)
    {
        while (!bin[j].empty())
        {
            studentrecord x = bin[j].get(0);
            bin[j].erase(0);
            thechain.insert(0, x);
        }
    }
    delete[]bin;
}

4.一个简短的测试程序测试.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include"chain.cpp"
//int main()
//{
//	studentrecord i = { 99,"a" }, j = { 88,"b" }, k = { 77,"c" };
//	chain<studentrecord> a, b, c;
//	a.insert(0, i);
//	a.insert(1, j);
//	a.insert(2, k);
//	binsort(a, 100);
//	cout << a;
//	
//}

int main(void)
{
    studentrecord s;
    chain<studentrecord> thechain;
    for (int i = 1; i <= 20; i++)
    {
        s.score = i / 2;
        s.name = new string(s.score, 'a');
        thechain.insert(0, s);
    }
    cout << "The unsorted chain is" << endl;
    cout << thechain << endl;
    thechain.binsort(10);
    cout << "The sorted chain is" << endl;
    cout << thechain << endl;
}

箱子排序

https://potatonupt.github.io/2021/01/27/%E7%AE%B1%E5%AD%90%E6%8E%92%E5%BA%8F/

作者

我是呆呆啊

发布于

2021-01-27

更新于

2021-01-27

许可协议

#

投喂投喂投喂投喂TAT

评论

去B站

看看电影吧

最新文章

归档

标签

源码5
经典1
×