C++学习笔记（34）

三十六、队列
示例：
#include <iostream>
using namespace std;
typedef int ElemType; // 自定义队列的数据元素为整数。
struct LNode
{
ElemType data; // 存储队列中的元素。
struct LNode* next; // next 指针。
};
struct LinkQueue
{
LNode* head,*tail; // 队列的头指针和尾指针。
};
// 初始化队列。
bool InitQueue(LinkQueue& QQ)
{
QQ.head = new (std::nothrow) LNode; // 分配头结点。
if (QQ.head == nullptr) return false; // 内存不足，返回失败。
QQ.head->next = nullptr; // 头结点的下一结点暂时不存在，置空。
QQ.tail = QQ.head; // 尾指针指向头结点。
return true;
}
// 销毁队列 QQ。
void DestroyQueue(LinkQueue& QQ)
{
LNode* tmp;
while (QQ.head != nullptr)
{
tmp = QQ.head->next; // tmp 保存下一结点的地址。
delete QQ.head; // 释放当前结点。
QQ.head = tmp; // 指针移动到下一结点。
}
}
// 元素入队。
bool InQueue(LinkQueue& QQ, const ElemType& ee)
{
if (QQ.head == nullptr) { cout << "队列未初始化。\n"; return false; }
LNode* tmp = new (std::nothrow) LNode; // 分配一个新结点。
if (tmp == nullptr) return false;
tmp->data = ee; // 把元素的值存入新结点。
tmp->next = nullptr;
QQ.tail->next = tmp; // 把 tmp 追加到 QQ.tail 之后。
QQ.tail = tmp; // 重新设置 tail 指针。
return true;
}
// 元素出队。
bool OutQueue(LinkQueue& QQ, ElemType& ee)
{
if (QQ.head == nullptr) { cout << "队列未初始化。\n"; return false; }
if (QQ.head->next == nullptr) { cout << "队列为空。\n"; return false; }
LNode* tmp = QQ.head->next; // tmp 指向第一个结点。
ee = tmp->data; // 把第一个结点的数据保存到 ee 中。
QQ.head->next = tmp->next; // 头结点的 next 指针指向第二个结点。
// 如果出队的是最后一个结点。
if (tmp == QQ.tail) QQ.tail = QQ.head;
delete tmp; // 释放已出队的结点。
return true;
}
// 显示队列中全部的元素。
void PrintQueue(LinkQueue& QQ)
{
if (QQ.head == nullptr) { cout << "队列未初始化。\n"; return ; }
LNode* pp = QQ.head->next; // 从第 1 个数据结点开始。
while (pp != NULL)
{
cout << pp->data << " " ;
pp = pp->next;
}
cout << endl;
}
// 求队列的长度。
int Length(LinkQueue& QQ)
{
if (QQ.head == nullptr) { cout << "队列未初始化。\n"; return false; }
LNode* pp = QQ.head->next; // 头结点不算，从第 1 个结点开始。
int length = 0;
while (pp != nullptr) { pp = pp->next; length++; }
return length;
}
// 清空队列。
void Clear(LinkQueue& QQ)
{
if (QQ.head == nullptr) { cout << "队列未初始化。\n"; return; }
// 清空队列是指释放链表全部的数据结点，但保留头结点。
LNode* tmp = QQ.head->next, * tmpnext;
while (tmp != nullptr)
{
tmpnext = tmp->next; // tmpnext 保存下一结点的地址。
delete tmp; // 释放当前结点。
tmp = tmpnext; // tmp 指针移动到下一结点。
}
QQ.head->next = nullptr;
QQ.tail = QQ.head; // 尾指针指向头结点。
}
int main()
{
LinkQueue QQ; // 创建队列。
memset(&QQ, 0, sizeof(QQ));
InitQueue(QQ); // 初始化队列。
cout << "元素（1、2、3、4、5）入队。\n";
InQueue(QQ, 1);
InQueue(QQ, 2);
InQueue(QQ, 3);
InQueue(QQ, 4);
InQueue(QQ, 5);
cout << "队列的长度是：" << Length(QQ) << "。\n";
cout << "队列中的元素是：";
PrintQueue(QQ);
ElemType ee; // 创建一个数据元素。
while (OutQueue(QQ, ee))
cout << "出队的元素值为" << ee << endl;
cout << "元素（11、12、13、14、15）入队。\n";
InQueue(QQ, 11);
InQueue(QQ, 12);
InQueue(QQ, 13);
InQueue(QQ, 14);
InQueue(QQ, 15);
cout << "队列的长度是：" << Length(QQ) << "。\n";
cout << "队列中的元素是：";
PrintQueue(QQ);
while (OutQueue(QQ, ee))
cout << "出队的元素值为" << ee << endl;
DestroyQueue(QQ); // 销毁队列 QQ。
}
四十、冒泡排序
示例：
#include <iostream>
using namespace std;
// 采用两层循环实现的方法。
// 参数 arr 是待排序数组的首地址，len 是数组元素的个数。
void bubblesort1(int arr[], int len)
{
if (len < 2) return; // 数组小于 2 个元素不需要排序。
bool ifswap=false; // 记录每轮排序过程中是否交换过元素，false-未交换；true-有交换。
// 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48
for (int ii = len - 1; ii > 0; ii--) // 一共进行 len-1 趟比较。
{
ifswap = false;
for (int jj = 0; jj < ii; jj++) // 每轮只需要比较 0......ii 之间的元素，ii 之后的元素是
已经排序好的。
{
if (arr[jj] > arr[jj + 1]) // 如果前面的元素大于后面的元素，则交换它位的
位置。
{
swap(arr[jj], arr[jj + 1]); // 交换两个元素的位置。
ifswap = true;
}
}
if (ifswap == false) return; // 如果这一轮没有交换过元素，说明数组已经是有序的
了。
}
}
// 采用递归实现的方法。
// 参数 arr 是待排序数组的首地址，len 是数组元素的个数。
void bubblesort2(int arr[], int len)
{
if (len < 2) return; // 数组小于 2 个元素不需要排序。
bool ifswap = false; // 记录每轮排序过程中是否交换过元素，false-未交换；true-有交换。
for (int jj = 0; jj < len - 1; jj++) // 每趟只需要比较 0......len-1 之间的元素，len-1 之后的元
素是已经排序好的。
{
if (arr[jj] > arr[jj + 1]) // 如果前面的元素大于后面的元素，则交换它位的
位置。
{
swap(arr[jj], arr[jj + 1]); // 交换两个元素的位置。
ifswap = true;
}
}
if (ifswap == false) return; // 如果这一轮没有交换过元素，说明数组已经是有序的了。
bubblesort2(arr, --len);
}
int main(int argc, char* argv[])
{
int arr[] = { 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48 }; // 待排序的数组。
int len = sizeof(arr) / sizeof(int); // 求数组长度。
//bubblesort1(arr, len); // 采用循环的方法。
bubblesort2(arr, len); // 采用递归的方法。
// 显示排序结果。
for (int ii = 0; ii < len; ii++) cout << arr[ii] << " ";
cout << endl;
}
四十一、选择排序
示例（未优化）：
#include <iostream>
using namespace std;
// 采用两层循环实现的方法。
// 参数 arr 是待排序数组的首地址，len 是数组元素的个数。
void selectsort1(int arr[], int len)
{
if (len < 2) return; // 数组小于 2 个元素不需要排序。
int iminpos; // 每趟循环选出的最小值的位置（数组的下标）。
// 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48
for (int ii = 0; ii < len - 1; ii++) // 一共进行 len-1 趟比较。
{
iminpos = ii;
for (int jj = ii + 1; jj < len; jj++) // 每趟只需要比较 ii+1......len-1 之间的元素，ii 之前的
元素是已经排序好的。
{
// 找出值更小的元素，记下它的位置。
if (arr[jj] < arr[iminpos]) iminpos = jj;
}
// 如果本趟循环的最小的元素不是起始位置的元素，则交换它们的位置。
if (iminpos != ii) swap(arr[ii], arr[iminpos]);
}
}
// 采用递归实现的方法。
// 参数 arr 是待排序数组的首地址，len 是数组元素的个数。
void selectsort2(int arr[], int len)
{
if (len < 2) return; // 数组小于 2 个元素不需要排序。
int iminpos = 0; // 每趟循环选出的最小值的位置（数组的下标）。
for (int ii = 1; ii < len; ii++)
{
// 找出值更小的元素，记下它的位置。
if (arr[ii] < arr[iminpos]) iminpos = ii;
}
// 如果本趟循环的最小的元素不是起始位置的元素，则交换它们的位置。
if (iminpos != 0) swap(arr[0], arr[iminpos]);
selectsort2(arr + 1, --len);
}
int main(int argc, char* argv[])
{
int arr[] = { 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48 }; // 待排序的数组。
int len = sizeof(arr) / sizeof(int); // 求数组长度。
selectsort1(arr, len); // 采用循环的方法。
//selectsort2(arr, len); // 采用递归的方法。
// 显示排序结果。
for (int ii = 0; ii < len; ii++) cout << arr[ii] << " ";
cout << endl;
}
示例（优化后）：
#include <iostream>
using namespace std;
// 采用两层循环实现的方法。
// 参数 arr 是待排序数组的首地址，len 是数组元素的个数。
void selectsort1(int arr[], int len)
{
if (len < 2) return; // 数组小于 2 个元素不需要排序。
int ileft, iright; // 每趟排序的最左和最右的位置。
int iminpos; // 每趟循环选出的最小值的位置（数组的下标）。
int imaxpos; // 每趟循环选出的最大值的位置（数组的下标）。
ileft = 0; iright = len - 1; // ileft 从 0 开始，iright 从 len-1 开始。
while (ileft < iright)
{
iminpos = imaxpos = ileft;
for (int ii = ileft; ii <= iright; ii++) // 每趟循环从 ileft 和 iright 之间选取元素。
{
// 找出值更小的元素，记下它的位置。
if (arr[ii] < arr[iminpos]) iminpos = ii;
// 找出值更大的元素，记下它的位置。
if (arr[ii] > arr[imaxpos]) imaxpos = ii;
}
// 如果本趟循环的最小的元素不是最左边的元素，则交换它们的位置。
if (iminpos != ileft) swap(arr[ileft], arr[iminpos]);
// 如果 imaxpos 的位置是 ileft，在上面的代码中 ileft 已被交换到了 iminpos 的位置。
// 所以 imaxpos 的值要修改为 iminpos。
if (imaxpos == ileft) imaxpos = iminpos;
// 如果本趟循环的最大的元素不是最右边的元素，则交换它们的位置。
if (imaxpos != iright) swap(arr[iright], arr[imaxpos]);
ileft++;
iright--;
}
}
// 采用递归实现的方法。
// 参数 arr 是待排序数组的首地址，len 是数组元素的个数。
void selectsort2(int arr[], int len)
{
if (len < 2) return;
int iminpos = 0; // 每趟循环选出的最小值的位置（数组的下标）。
int imaxpos = 0; // 每趟循环选出的最大值的位置（数组的下标）。
int ileft = 0;
int iright = len - 1;
for (int ii = ileft; ii <= iright; ii++) // 循环从 ileft 和 iright 之间选取元素。
{
// 找出值更小的元素，记下它的位置。
if (arr[ii] < arr[iminpos]) iminpos = ii;
// 找出值更大的元素，记下它的位置。
if (arr[ii] > arr[imaxpos]) imaxpos = ii;
}
// 如果本趟循环的最小的元素不是最左边的元素，则交换它们的位置。
if (iminpos != ileft) swap(arr[ileft], arr[iminpos]);
// 如果 imaxpos 的位置是 ileft，在上面的代码中 ileft 已被交换到了 iminpos 的位置。
// 所以 imaxpos 的值要修改为 iminpos。
if (imaxpos == ileft) imaxpos = iminpos;
// 如果本趟循环的最大的元素不是最右边的元素，则交换它们的位置。
if (imaxpos != iright) swap(arr[iright], arr[imaxpos]);
len = len - 2;
selectsort2(++arr, len);
}
int main(int argc, char* argv[])
{
int arr[] = { 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48 }; // 待排序的数组。
int len = sizeof(arr) / sizeof(int); // 求数组长度。
selectsort1(arr, len); // 采用循环的方法。
//selectsort2(arr, len); // 采用递归的方法。
// 显示排序结果。
for (int ii = 0; ii < len; ii++) cout << arr[ii] << " ";
cout << endl;
}
四十二、插入排序
示例：
#include <iostream>
using namespace std;
// 参数 arr 是待排序数组的首地址，len 是数组元素的个数。
void insertsort(int arr[], int len)
{
if (len < 2) return; // 数组小于 2 个元素不需要排序。
int itmp; // 当前需要排序的元素的值。
for (int ii = 1; ii < len; ii++) // ii 从 1 开始，因为第一个元素不需要排序，就像拿到第一张
牌一样。
{
itmp = arr[ii]; // 待排序元素。
// 从已排序元素的最右边开始，把大于当前排序的元素后移。
int jj; // 需要后移元素的计数器。
for (jj = ii - 1; jj >= 0; jj--)
{
if (arr[jj] <= itmp) break;
arr[jj + 1] = arr[jj]; // 逐个元素后移。
}
arr[jj + 1] = itmp; // 插入当前排序元素。
}
}
int main(int argc, char* argv[])
{
int arr[] = { 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48 }; // 待排序的数组。
int len = sizeof(arr) / sizeof(int); // 求数组长度。
insertsort(arr, len);
// 显示排序结果。
for (int ii = 0; ii < len; ii++) cout << arr[ii] << " ";
cout << endl;
}