箱排序

假定用一个链表保存一个班级学生清单。结点的数据有：学生姓名和考试分数。假设分数是0~100的整数。

采用箱排序可以把分数相同的结点放在同一个箱子里，然后把箱子连接起来就得到了有序的链表

链表定义

  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
225
226
227
#include<iostream>
#include <sstream>

using namespace std;

class illegalParameterValue {
public:
    illegalParameterValue() : message("Illegal parameter value") {}

    explicit illegalParameterValue(char *theMessage) {
        message = theMessage;
    }

    explicit illegalParameterValue(const string &theMessage) {
        message = theMessage;
        cout << message << endl;
    }

    void outputMessge() {
        cout << message << endl;
    }

private:
    string message;
};

// 链表结点的结构定义
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 chainList {
public:
    // 构造函数，复制构造函数和构析函数
    chainList(int initialCapacity = 10);

    chainList(const chainList<T> &);

    ~chainList();

    // 抽象数据类型ADT的方法
    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;

protected:
    void checkIndex(int theIndex) const; // 如果索引无效抛出异常
    chainNode<T> *firstNode; // 指向链表第一个结点的指针
    int listSize;
};

template<class T>
void chainList<T>::checkIndex(int theIndex) const {
    if (theIndex < 0 || theIndex >= size()) {
        stringstream s;
        s << "theIndex " << theIndex << " is illegal";
        illegalParameterValue(s.str());
    }
}

// 构造函数和复制构造函数
template<class T>
chainList<T>::chainList(int initialCapacity) {
    // 构造函数
    if (initialCapacity < 1) {
        ostringstream s;
        s << "Initial capacity = " << initialCapacity << " Muse be > 0 ";
        throw illegalParameterValue(s.str());
    }
    firstNode = nullptr;
    listSize = 0;
}

template<class T>
chainList<T>::chainList(const chainList<T> &theList) {
    // 复制构造函数
    listSize = theList.listSize;
    if (listSize == 0) {
        // 链表theList为空
        firstNode = nullptr;
        return;
    }
    // 链表theList为非空
    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>
chainList<T>::~chainList() {
    // 链表构析函数，删除链表的所有节点
    while (firstNode != nullptr) {
        // 删除首结点
        chainNode<T> *nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
}

// get方法
template<class T>
T &chainList<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;
}

// 返回元素theElement首次出现时的索引
template<class T>
int chainList<T>::indexOf(const T &theElement) const {
    // 返回元素theElement首次出现时的索引
    // 若该元素不存在，则返回-1
    // 搜寻链表寻找元素theElement
    chainNode<T> *currentNode = firstNode;
    int index = 0;
    while (currentNode != nullptr && currentNode->element != theElement) {
        // 移向下一个结点
        currentNode = currentNode->next;
        ++index;
    }
    // 确定是否找到所需的元素
    if (currentNode == nullptr)
        return -1;
    else
        return index;
}

// 删除索引为theIndex的元素
template<class T>
void chainList<T>::erase(int theIndex) {
    // 删除索引为theIndex元素
    // 若该元素不存在，则抛出异常
    checkIndex(theIndex);
    // 索引有效
    chainNode<T> *deleteNode;
    if (theIndex == 0) {
        // 删除链表的头节点
        deleteNode = firstNode;
        firstNode = firstNode->next;
    } else {
        // 用指针p指向要删除节点的前驱结点
        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;
}

// 插入theElement并使得其索引为theIndex
template<class T>
void chainList<T>::insert(int theIndex, const T &theElement) {
    // 在索引为theIndex的位置上
    // 若该位置非法，则抛出异常
    if (theIndex < 0 || theIndex > listSize) {
        // 无效索引
        ostringstream s;
        s << "index = " << theIndex << " size = " << listSize;
        throw illegalParameterValue(s.str());
    }
    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之后插入
        p->next = new chainNode<T>(theElement, p->next);
    }
    ++listSize;
}

template<class T>
void chainList<T>::output(ostream &out) const {
    // 把链表放入输出流
    for (auto *currentNode = firstNode; currentNode != nullptr; currentNode = currentNode->next)
        out << currentNode->element;
}

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

结点定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
struct studentRecord {
    string name;
    int score;
	// 重载类型转换操作符int()，这样可以使用+、/、<=和!=这些算数和关系操作符
    explicit operator int() const { return score; } // 重载类型转换操作符int()转换为int类型
	// 重载操作符int()只有在操作符号!=和<<以外操作中被调用
    int operator!=(const studentRecord &x) const { return score != x.score; } // 重载运算符
};
// 重载<<
ostream &operator<<(ostream &out, const studentRecord &x) {
    out << x.name << ": " << x.score << endl;
    return out;
}

箱排序方法定义

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 使用链表的多个方法进行箱排序
void binSort(chainList<studentRecord> &theChain, int range) {
    // 按分数排序
    chainList<studentRecord> *bin; // 声明箱子
    bin = new chainList<studentRecord>[range + 1]; // 总共有range+1个箱子

    // 把学生记录从链表中取出，然后分配到箱子中
    int numberOfElements = theChain.size(); // 记录链表中元素数量
    for (int i = 0; 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()) { // 如果第j个箱子中的元素不为0
            studentRecord x = bin[j].get(0); // 拿出第j个箱子中的第一个元素
            bin[j].erase(0); // 然后从箱子中删除该元素
            theChain.insert(0, x); // 将该元素通过头插法加入到链表中
        }
    }
    delete[] bin; // 最后删除箱子
}

全部代码

  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
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
#include<iostream>
#include <sstream>

using namespace std;

class illegalParameterValue {
public:
    illegalParameterValue() : message("Illegal parameter value") {}

    explicit illegalParameterValue(char *theMessage) {
        message = theMessage;
    }

    explicit illegalParameterValue(const string &theMessage) {
        message = theMessage;
        cout << message << endl;
    }

    void outputMessge() {
        cout << message << endl;
    }

private:
    string message;
};

// 链表结点的结构定义
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 chainList {
public:
    // 构造函数，复制构造函数和构析函数
    chainList(int initialCapacity = 10);

    chainList(const chainList<T> &);

    ~chainList();

    // 抽象数据类型ADT的方法
    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;

protected:
    void checkIndex(int theIndex) const; // 如果索引无效抛出异常
    chainNode<T> *firstNode; // 指向链表第一个结点的指针
    int listSize;
};

template<class T>
void chainList<T>::checkIndex(int theIndex) const {
    if (theIndex < 0 || theIndex >= size()) {
        stringstream s;
        s << "theIndex " << theIndex << " is illegal";
        illegalParameterValue(s.str());
    }
}

// 构造函数和复制构造函数
template<class T>
chainList<T>::chainList(int initialCapacity) {
    // 构造函数
    if (initialCapacity < 1) {
        ostringstream s;
        s << "Initial capacity = " << initialCapacity << " Muse be > 0 ";
        throw illegalParameterValue(s.str());
    }
    firstNode = nullptr;
    listSize = 0;
}

template<class T>
chainList<T>::chainList(const chainList<T> &theList) {
    // 复制构造函数
    listSize = theList.listSize;
    if (listSize == 0) {
        // 链表theList为空
        firstNode = nullptr;
        return;
    }
    // 链表theList为非空
    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>
chainList<T>::~chainList() {
    // 链表构析函数，删除链表的所有节点
    while (firstNode != nullptr) {
        // 删除首结点
        chainNode<T> *nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
}

// get方法
template<class T>
T &chainList<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;
}

// 返回元素theElement首次出现时的索引
template<class T>
int chainList<T>::indexOf(const T &theElement) const {
    // 返回元素theElement首次出现时的索引
    // 若该元素不存在，则返回-1
    // 搜寻链表寻找元素theElement
    chainNode<T> *currentNode = firstNode;
    int index = 0;
    while (currentNode != nullptr && currentNode->element != theElement) {
        // 移向下一个结点
        currentNode = currentNode->next;
        ++index;
    }
    // 确定是否找到所需的元素
    if (currentNode == nullptr)
        return -1;
    else
        return index;
}

// 删除索引为theIndex的元素
template<class T>
void chainList<T>::erase(int theIndex) {
    // 删除索引为theIndex元素
    // 若该元素不存在，则抛出异常
    checkIndex(theIndex);
    // 索引有效
    chainNode<T> *deleteNode;
    if (theIndex == 0) {
        // 删除链表的头节点
        deleteNode = firstNode;
        firstNode = firstNode->next;
    } else {
        // 用指针p指向要删除节点的前驱结点
        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;
}

// 插入theElement并使得其索引为theIndex
template<class T>
void chainList<T>::insert(int theIndex, const T &theElement) {
    // 在索引为theIndex的位置上
    // 若该位置非法，则抛出异常
    if (theIndex < 0 || theIndex > listSize) {
        // 无效索引
        ostringstream s;
        s << "index = " << theIndex << " size = " << listSize;
        throw illegalParameterValue(s.str());
    }
    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之后插入
        p->next = new chainNode<T>(theElement, p->next);
    }
    ++listSize;
}

template<class T>
void chainList<T>::output(ostream &out) const {
    // 把链表放入输出流
    for (auto *currentNode = firstNode; currentNode != nullptr; currentNode = currentNode->next)
        out << currentNode->element;
}

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

#include"chainList.cpp"

// 用链表保存一个班级学生的清单
// 节点的数据域有：学生姓名，分数
// 假设分数是0~100的整数
struct studentRecord {
    string name;
    int score;

    explicit operator int() const { return score; }

    int operator!=(const studentRecord &x) const { return score != x.score; }
};

ostream &operator<<(ostream &out, const studentRecord &x) {
    out << x.name << ": " << x.score << endl;
    return out;
}

// 使用链表的多个方法进行箱排序
void binSort(chainList<studentRecord> &theChain, int range) {
    // 按分数排序
    chainList<studentRecord> *bin; // 声明箱子
    bin = new chainList<studentRecord>[range + 1]; // 总共有range+1个箱子

    // 把学生记录从链表中取出，然后分配到箱子中
    int numberOfElements = theChain.size(); // 记录链表中元素数量
    for (int i = 0; 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()) { // 如果第j个箱子中的元素不为0
            studentRecord x = bin[j].get(0); // 拿出第j个箱子中的第一个元素
            bin[j].erase(0); // 然后从箱子中删除该元素
            theChain.insert(0, x); // 将该元素通过头插法加入到链表中
        }
    }
    delete[] bin; // 最后删除箱子
}

int main() {
    auto *studentRecords = new chainList<studentRecord>(10);
    int score;
    string name;
    for (int i = 0; i < 10; ++i) {
        auto *sr = new studentRecord; // 为结点申请空间
        cin >> name >> score;
        sr->score = score; // 为结点赋值
        sr->name = name;
        studentRecords->insert(i, *sr); // 将结点插入链表中
    }
    // 查看输入结果
    cout << *studentRecords << endl;
    // 对链表进行箱排序
    binSort(*studentRecords, 5);
    cout << "排序后结果" << endl;
    cout << *studentRecords << endl;

}

输入

输出

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
A: 2
B: 4
C: 5
D: 4
E: 3
F: 0
G: 4
H: 3
I: 4
J: 4

排序后结果
F: 0
A: 2
E: 3
H: 3
B: 4
D: 4
G: 4
I: 4
J: 4
C: 5

箱排序#

链表定义#

结点定义#

箱排序方法定义#

全部代码#

输入#

输出#

箱排序

链表定义

结点定义

箱排序方法定义

全部代码

输入

输出