# 荷兰国旗问题（顺序表和链表）

2020/4/9 19:01:24 人评论 次浏览 分类：学习教程

``````//荷兰国旗问题  顺序表
#include <iostream>
using namespace std;
typedef struct
{
int data[20];
int length;
}SqList;
void InitList(SqList* L)
{
L = (SqList*)malloc(sizeof(SqList));
int length = 0;
}
int Creast_List(SqList*& L, int a[], int n)
{
int i, k = 0;
L = (SqList*)malloc(sizeof(SqList));
for (i = 0; i < n; i++)
{
L->data[i] = a[i];
k++;
}
L->length = k;
return 0;
}
void move_Sqlist(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++;
}
}
void DispSqlis(SqList* L)
{
int i;
if (L->length == 0)
return;
for (i = 0; i < L->length; i++)
{
cout << L->data[i];
}
}
int main()
{
SqList * L=0;
int a[12] = { 1,0,2,1,0,0,1,2,2,1,0,2 };
InitList(L);
Creast_List(L, a, 12);
move_Sqlist(L);
DispSqlis(L);
return 0;
}
``````

``````//荷兰国旗问题  单链表
#include <iostream>
using namespace std;
typedef struct LNode
{
int data;
struct LNode *next;
{
L->next =NULL;
}
{
int i;
L->next =NULL;
for(i=0;i<n;i++)
{
s->data=a[i];
s->next=L->next;
L->next =s;
}
}
{
while(p!=NULL)
{
cout<<p->data ;
p=p->next ;
}
}
{
L1=NULL;
L2=NULL;
p=L->next ;
r=L;
while(p!=NULL)
{
if(p->data ==0)
{
r->next =p;
r=p;
}
else if(p->data ==1)
{
if(L1==NULL)
{
L1=p;
r1=p;
}
else
{
r1->next =p;
r1=p;
}
}
else
{
if(L2==NULL)
{
L2=p;
r2=p;
}
else
{
r2->next =p;
r2=p;
}
}
p=p->next ;
}
r->next =r1->next =r2->next=NULL;//去掉这句会陷入死循环
r->next =L1;
r1->next =L2;
}
int main()
{
int a[12] = { 1,0,2,1,0,0,1,2,2,1,0,2 };
move(L);