C++学习笔记（30）

二十三、随机数
在实际开发中，经常用到随机数，例如：纸牌的游戏洗牌和发牌、生成测试数据等。
函数原型：
void srand(unsigned int seed); // 初始化随机数生成器（播种子）。
int rand(); // 获一个取随机数。
随机数生成器使用前如果不初始化，每次获取的随机数是相同的，通常用当前时间的秒数（time(0)
函数的返回值）初始化随机数生成器。
功能需求：
写一个函数，随机生成 n 个整数，不允许重复。
函数原型：
void rrand(int arr[], const size_t len, const int minvalue=0);
rrand(arr, 10); // 5 3 2 1 4 6 9 8 7 0
rrand(arr, 10, 10); // 15 13 12 11 14 16 19 18 17 10
示例：
#include <iostream>
using namespace std;
void rrand(int arr[], const size_t len, const int minvalue = 0)
{
srand(time(0)); // 用当前时间（1970-1-1 到现在的秒数）作为随机数的种子。
for (int ii = 0; ii < len; ii++) {
while (true) {
// 获取一个随机数，但是，这个数值不一定是有效的，可能在数组 arr 中已存在。
int tmp = rand() % len + minvalue;
// 判断获取的随机数 tmp 是否已存在数组 arr 中。
int jj;
for (jj = 0; jj < ii; jj++) // 注意，这里只遍历数组中有效的元素就行了，不是整个
数组。
if (tmp == arr[jj]) break;
if (jj == ii) { // 如果 jj==ii，表示 tmp 不在数组 arr 中，把 tmp
存入 arr[ii]。
arr[ii] = tmp; break; // 跳出 while 循环。
}
}
}
}
int main()
{
int arr[10];
rrand(arr, 10);
for (int ii = 0; ii < 10; ii++)
cout << arr[ii] << " ";
cout << endl;
}
二十四、随机发牌
一副牌有 54 张，除掉大小王，还有 52 张，用 1-52 之间的数字表示，把它随机发给 4 个玩家。
函数原型：
// arr：每个玩家的牌面，第一维的大小是 4。
void dealcards(int arr[][13]);
要求：为了达到更好的随机效果，不能把洗好的牌按顺序发给玩家，要随机发放。
50 44 19 45 22 40 8 27 17 13 51 29 18 37 34 12 2 5 46 33 31 4 32 35 14 9 23 43 21
39 6 52 11 38 30 3 15 41 16 20 10 24 28 48 26 36 7 47 25 42 49 1
49 43 18 44 21 39 7 26 16 12 50 28 17 36 33 11 1 4 45 32 30 3 31 34 13 8 22 42 20
38 5 51 10 37 29 2 14 40 15 19 9 23 27 47 25 35 6 46 24 41 48 0
玩家一：42 4
玩家二：48
玩家三：46
玩家四：26
提示：可以利用上节课的成果，能达到发牌的效果就行了，代码不拘一格。
示例：
#include <iostream>
using namespace std;
void rrand(int arr[], const size_t len, const int minvalue = 0)
{
srand(time(0)); // 用当前时间（1970-1-1 到现在的秒数）作为随机数的种子。
for (int ii = 0; ii < len; ii++) {
while (true) {
// 获取一个随机数，但是，这个数值不一定是有效的，可能在数组 arr 中已存在。
int tmp = rand() % len + minvalue;
// 判断获取的随机数 tmp 是否已存在数组 arr 中。
int jj;
for (jj = 0; jj < ii; jj++) // 注意，这里只遍历数组中有效的元素就行了，不是整个
数组。
if (tmp == arr[jj]) break;
if (jj == ii) { // 如果 jj==ii，表示 tmp 不在数组 arr 中，把 tmp
存入 arr[ii]。
arr[ii] = tmp; break; // 跳出 while 循环。
}
}
}
}
// arr：每个玩家的牌面，第一维的大小是 3。
void dealcards(int arr[][13])
{
int arr1[52]; // 洗牌数组。
rrand(arr1, 52, 1); // 得到洗牌数组。
for (int ii = 0; ii < 52; ii++)
cout << arr1[ii] << " ";
cout << endl;
int arr2[52]; // 发牌数组。
rrand(arr2, 52); // 得到发牌顺序数组。
for (int ii = 0; ii < 52; ii++)
cout << arr2[ii] << " ";
cout << endl;
int jj = 0; // 已发牌的数组下标，从 0-51。
for (int ii = 0; ii < 13; ii++) // 一共发 13 轮。
{
arr[0][ii] = arr1[arr2[jj++]];
arr[1][ii] = arr1[arr2[jj++]];
arr[2][ii] = arr1[arr2[jj++]];
arr[3][ii] = arr1[arr2[jj++]];
}
}
int main()
{
int arr2[4][13];
dealcards(arr2);
for (int ii = 0; ii < 13; ii++)
cout << arr2[0][ii] << " ";
cout << endl;
for (int ii = 0; ii < 13; ii++)
cout << arr2[1][ii] << " ";
cout << endl;
for (int ii = 0; ii < 13; ii++)
cout << arr2[2][ii] << " ";
cout << endl;
for (int ii = 0; ii < 13; ii++)
cout << arr2[3][ii] << " ";
cout << endl;
cout << endl;
}
三十、静态顺序表
示例（数据元素为整数）：
#include <iostream>
using namespace std;
#define MAXSIZE 100 // 顺序表的最大长度
typedef int ElemType; // 给数据元素的数据类型起个别名。
struct SeqList // 静态顺序表的结构体。
{
ElemType data[MAXSIZE]; // 用静态数组存储顺序表中的元素。
size_t length; // 顺序表的表长（有效元素的个数）。
};
// 清空顺序表。
void ClearList(SeqList& LL)
{
//LL.length = 0; // 表长置为 0。
//memset(LL.data, 0, sizeof(ElemType) * MAXSIZE); // 清空数组。
memset(&LL, 0, sizeof(SeqList)); // 清空结构体。
}
// 在顺序表 LL 的第 pos 个位置插入元素 ee，返回值：true-成功；false-失败。
// 注意：在数据结构中，位置 pos 从 1 开始，不是从 0 开始。
// 6 8 2 1 12 4 5 3 7 // 顺序表中的元素。
// 1 2 3 4 5 6 7 8 9 10 // 位置。
// 0 1 2 3 4 5 6 7 8 9 // 数组下标。
bool InsertList(SeqList& LL, const size_t pos, const ElemType& ee)
{
if (LL.length == MAXSIZE) { cout << "顺序表已满，不能插入。\n"; return false; }
// 判断位置 pos 是否合法。
if ((pos < 1) || (pos > LL.length + 1)) {
cout << "插入位置" << pos << "不合法，应该在 1-" << LL.length + 1 << "之间。\n";
return false;
}
// 把 pos 和 pos 之后的元素后移。
if (pos < LL.length + 1)
memmove(LL.data + pos, LL.data + pos - 1, (LL.length - pos + 1) * sizeof(ElemType));
// 把元素 ee 的值赋值给顺序表的第 pos 个元素。
//memcpy(&LL.data[pos - 1], &ee, sizeof(ElemType)); // 采用 memcpy 是为了兼容 ee 为
结构体的情况。
LL.data[pos - 1] = ee; // 在 C++中，结构体也可以用=赋值。
LL.length++; // 表长加 1。
return true;
}
// 求顺序表的表长，返回值表 LL 中元素的个数。
size_t LengthList(const SeqList& LL)
{
return LL.length;
}
// 获取顺序表中第 pos 个元素的值，存放在 ee 中，返回值：false-失败；true-成功。
bool GetElem(const SeqList LL, const size_t pos, ElemType& ee)
{
// 判断位置 pos 是否合法。
if ((pos < 1) || (pos > LL.length)) return false;
ee = LL.data[pos - 1];
return true;
}
// 在顺序表 LL 的头部插入元素 ee。
bool PushFront(SeqList& LL, const ElemType& ee)
{
return InsertList(LL, 1, ee);
}
// 在顺序表 LL 的尾部插入元素 ee。
bool PushBack(SeqList& LL, const ElemType& ee)
{
return InsertList(LL, LL.length + 1, ee);
}
// 查找 ee 在顺序表 LL 中的位置，返回值：0-元素 ee 在表 LL 中不存在，>0 元素 ee 在表 LL 中的
位置。
size_t FindElem(const SeqList& LL, const ElemType& ee)
{
for (size_t ii = 0; ii < LL.length; ii++)
{
// 如果元素 ee 为结构体，以下代码要修改（比较数据元素的关键字）。
if (LL.data[ii] == ee) return ii + 1;
}
return 0;
}
// 删除顺序表 LL 中的第 pos 个元素，返回值：0-位置 pos 不合法；1-成功。
bool DeleteElem(SeqList& LL, const size_t pos)
{
// 判断位置 pos 是否合法，注意，pos 从 1 开始，不是从 0 开始，0 不符合人类的习惯。
if ((pos < 1) || (pos > LL.length)) {
cout << "删除位置" << pos << "不合法，应该在 1-" << LL.length << "之间。\n";
return false;
}
// 把 pos 之后的元素前移。
memmove(&LL.data[pos - 1], &LL.data[pos], sizeof(ElemType) * (LL.length - pos));
LL.length--; // 表长减 1。
return true;
}
// 删除顺序表 LL 中头元素。
bool PopFront(SeqList& LL)
{
return DeleteElem(LL, 1);
}
// 删除顺序表 LL 中尾元素。
bool PopBack(SeqList& LL)
{
return DeleteElem(LL, LL.length);
}
// 判断顺序表是否为空，返回值：true-空，false-非空。
bool IsEmpty(const SeqList& LL)
{
if (LL.length == 0) return true;
return false;
}
// 显示顺序表中全部的元素。
void PrintList(const SeqList& LL)
{
if (LL.length == 0) { cout << "表为空。\n"; return; }
for (size_t ii = 0; ii < LL.length; ii++)
{
cout << LL.data[ii] << " ";
}
cout << endl;
}
int main()
{
SeqList LL; // 创建顺序表。
ClearList(LL); // 清空顺序表。
ElemType ee; // 创建一个数据元素。
cout << "在表中插入元素（1、2、3、4、5、6、7、8、9、10）。\n";
ee = 1; InsertList(LL, 1, ee);
ee = 2; InsertList(LL, 1, ee);
ee = 3; InsertList(LL, 1, ee);
ee = 4; InsertList(LL, 1, ee);
ee = 5; InsertList(LL, 1, ee);
ee = 6; InsertList(LL, 1, ee);
ee = 7; InsertList(LL, 1, ee);
ee = 8; InsertList(LL, 1, ee);
ee = 9; InsertList(LL, 1, ee);
ee = 10; InsertList(LL, 1, ee);
PrintList(LL);
cout << "在表头插入元素（11），表尾插入元素（12）。\n";
ee = 11; PushFront(LL, ee);
ee = 12; PushBack(LL, ee);
PrintList(LL);
cout << "在第 5 个位置插入元素（13）。\n";
ee = 13; InsertList(LL, 5, ee);
PrintList(LL);
cout << "删除表中第 7 个元素。\n";
DeleteElem(LL, 7); PrintList(LL);
cout << "删除表头元素。\n";
PopFront(LL); PrintList(LL);
cout << "删除表尾元素。\n";
PopBack(LL); PrintList(LL);
GetElem(LL, 5, ee);
cout << "第 5 个元素的值是" << ee << "。\n";
ee = 8;
cout << "元素值为 8 的位置是=" << FindElem(LL, ee) << endl;
}
示例（数据元素为结构体）：
#include <iostream>
using namespace std;
#define MAXSIZE 100 // 顺序表的最大长度
typedef struct stgirl // 超女结构体。
{
int bh;
char name[21];
} ElemType; // 给数据元素的数据类型起个别名。
struct SeqList // 静态顺序表的结构体。
{
ElemType data[MAXSIZE]; // 用静态数组存储顺序表中的元素。
size_t length; // 顺序表的表长（有效元素的个数）。
};
// 清空顺序表。
void ClearList(SeqList& LL)
{
//LL.length = 0; // 表长置为 0。
//memset(LL.data, 0, sizeof(ElemType) * MAXSIZE); // 清空数组。
memset(&LL, 0, sizeof(SeqList)); // 清空结构体。
}
// 在顺序表 LL 的第 pos 个位置插入元素 ee，返回值：true-成功；false-失败。
// 注意：在数据结构中，位置 pos 从 1 开始，不是从 0 开始。
// 6 8 2 1 12 4 5 3 7 // 顺序表中的元素。
// 1 2 3 4 5 6 7 8 9 10 // 位置。
// 0 1 2 3 4 5 6 7 8 9 // 数组下标。
bool InsertList(SeqList& LL, const size_t pos, const ElemType& ee)
{
if (LL.length == MAXSIZE) { cout << "顺序表已满，不能插入。\n"; return false; }
// 判断位置 pos 是否合法。
if ((pos < 1) || (pos > LL.length + 1)) {
cout << "插入位置" << pos << "不合法，应该在 1-" << LL.length + 1 << "之间。\n";
return false;
}
// 把 pos 和 pos 之后的元素后移。
if (pos < LL.length + 1)
memmove(LL.data + pos, LL.data + pos - 1, (LL.length - pos + 1) * sizeof(ElemType));
// 把元素 ee 的值赋值给顺序表的第 pos 个元素。
//memcpy(&LL.data[pos - 1], &ee, sizeof(ElemType)); // 采用 memcpy 是为了兼容 ee 为
结构体的情况。
LL.data[pos - 1] = ee; // 在 C++中，结构体也可以用=赋值。
LL.length++; // 表长加 1。
return true;
}
// 求顺序表的表长，返回值表 LL 中元素的个数。
size_t LengthList(const SeqList& LL)
{
return LL.length;
}
// 获取顺序表中第 pos 个元素的值，存放在 ee 中，返回值：false-失败；true-成功。
bool GetElem(const SeqList LL, const size_t pos, ElemType& ee)
{
// 判断位置 pos 是否合法。
if ((pos < 1) || (pos > LL.length)) return false;
ee = LL.data[pos - 1];
return true;
}
// 在顺序表 LL 的头部插入元素 ee。
bool PushFront(SeqList& LL, const ElemType& ee)
{
return InsertList(LL, 1, ee);
}
// 在顺序表 LL 的尾部插入元素 ee。
bool PushBack(SeqList& LL, const ElemType& ee)
{
return InsertList(LL, LL.length + 1, ee);
}
// 查找 ee 在顺序表 LL 中的位置，返回值：0-元素 ee 在表 LL 中不存在，>0 元素 ee 在表 LL 中的
位置。
size_t FindElem(const SeqList& LL, const ElemType& ee)
{
for (size_t ii = 0; ii < LL.length; ii++)
{
// 如果元素 ee 为结构体，以下代码要修改（比较数据元素的关键字）。
if (LL.data[ii].bh == ee.bh) return ii + 1;
}
return 0;
}
// 删除顺序表 LL 中的第 pos 个元素，返回值：0-位置 pos 不合法；1-成功。
bool DeleteElem(SeqList& LL, const size_t pos)
{
// 判断位置 pos 是否合法，注意，pos 从 1 开始，不是从 0 开始，0 不符合人类的习惯。
if ((pos < 1) || (pos > LL.length)) {
cout << "删除位置" << pos << "不合法，应该在 1-" << LL.length << "之间。\n";
return false;
}
// 把 pos 之后的元素前移。
memmove(&LL.data[pos - 1], &LL.data[pos], sizeof(ElemType) * (LL.length - pos));
LL.length--; // 表长减 1。
return true;
}
// 删除顺序表 LL 中头元素。
bool PopFront(SeqList& LL)
{
return DeleteElem(LL, 1);
}
// 删除顺序表 LL 中尾元素。
bool PopBack(SeqList& LL)
{
return DeleteElem(LL, LL.length);
}
// 判断顺序表是否为空，返回值：true-空，false-非空。
bool IsEmpty(const SeqList& LL)
{
if (LL.length == 0) return true;
return false;
}
// 显示顺序表中全部的元素。
void PrintList(const SeqList& LL)
{
if (LL.length == 0) { cout << "表为空。\n"; return; }
for (size_t ii = 0; ii < LL.length; ii++)
{
cout << LL.data[ii].bh << " ";
}
cout << endl;
}
int main()
{
SeqList LL; // 创建顺序表。
ClearList(LL); // 清空顺序表。
ElemType ee; // 创建一个数据元素。
// 注意，在以下测试代码中，我没有管超女结构体的 name 字段。
cout << "在表中插入元素（1、2、3、4、5、6、7、8、9、10）。\n";
ee.bh = 1; InsertList(LL, 1, ee);
ee.bh = 2; InsertList(LL, 1, ee);
ee.bh = 3; InsertList(LL, 1, ee);
ee.bh = 4; InsertList(LL, 1, ee);
ee.bh = 5; InsertList(LL, 1, ee);
ee.bh = 6; InsertList(LL, 1, ee);
ee.bh = 7; InsertList(LL, 1, ee);
ee.bh = 8; InsertList(LL, 1, ee);
ee.bh = 9; InsertList(LL, 1, ee);
ee.bh = 10; InsertList(LL, 1, ee);
PrintList(LL);
cout << "在表头插入元素（11），表尾插入元素（12）。\n";
ee.bh = 11; PushFront(LL, ee);
ee.bh = 12; PushBack(LL, ee);
PrintList(LL);
cout << "在第 5 个位置插入元素（13）。\n";
ee.bh = 13; InsertList(LL, 5, ee);
PrintList(LL);
cout << "删除表中第 7 个元素。\n";
DeleteElem(LL, 7); PrintList(LL);
cout << "删除表头元素。\n";
PopFront(LL); PrintList(LL);
cout << "删除表尾元素。\n";
PopBack(LL); PrintList(LL);
GetElem(LL, 5, ee);
cout << "第 5 个元素的值是" << ee.bh << "。\n";
ee.bh = 8;
cout << "元素值为 8 的位置是=" << FindElem(LL, ee) << endl;
}