荷兰国旗
作者:
yuyi417
,
2023-03-08 20:29:52
,
所有人可见
,
阅读 243
荷兰国旗问题:设有一个条块序列,每个条块为红(0)、白(1)、兰(2)三种颜色中的一种。假设该序列采用顺序表存储,设计一个时间复杂度为O(n)的算法,使得这些条块按红、白、兰的顺序排好,即排成荷兰国旗图案。
C++ 代码
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<windows.h>
using namespace std;
const int N = 1e5 + 10;
typedef struct
{
int data[N];
int length;
}SqList;
void CreateList(SqList * &L, int a[], int n) //创建一个顺序表
{
int i = 0, k = 0;
L = (SqList*)malloc(sizeof(SqList));
while (i < n)
{
L->data[i] = a[i];
k++; i++;
}
L->length = k;
}
void color(int n) //调整控制器颜色
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), n);
return;
}
void DispList(SqList* L) //输出顺序表
{
for (int i = 0; i < L->length; i++)
{
if (L->data[i] == 0) color(207);
if (L->data[i] == 1) color(240);
if (L->data[i] == 2) color(158);
printf("%d", L->data[i]);
color(15);//程序结束后的颜色需要重置一下
}
}
void move1(SqList*& L) //排成荷兰国旗的顺序
{
int i = -1,j = 0,k = L->length;
while (j < k)
{
if (L->data[j] == 0)
{
i++;
swap(L->data[i],L->data[j]);
j++;
}
else if (L->data[j] == 2)
{
k--;
swap(L->data[k],L->data[j]);
}
else j++; //L->data[j]==1的情况
}
}
int main()
{
int n;
int a[N];
string b;//使用字符串输入好看一点,不然就得一行一行的输入
cout << "请输入想要输入的元素个数:";
cin >> n;
cout << "请输入要输入的元素:" << endl;
cin >> b;
//for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < b.size() ; i++) a[i] = (b[i] - '0');
SqList* L;
CreateList(L,a,n);
cout << "调整前的原始顺序:" << endl;
DispList(L);
cout << endl;
move1(L);
cout << "调整后的顺序:" << endl;
DispList(L);
}