数据结构-用单链表实现荷兰国旗问题
(学数据结构的第4周)
(还是太菜，3/18调了3节课才调通)
问题简单描述
荷兰国旗有红白蓝三种颜色，分别用数字0、1、2表示。一个有头结点的关于0、1、2的随机排列，我们要实现将数字按照0、1、2的顺序排列。这也就是这道题名为荷兰国旗的原因，下图即为荷兰国旗，可谓生动形象。
单链表：
链表可以实现存储空间动态管理的链式存储结构，其中每个存储结点不仅包含元素本身的信息（数据域），而且包含表示元素之间逻辑关系的信息，C/C++采用指针实现。所谓单链表是每个结点中包含数据域外只设置一个指针域，其指向后继结点。
结点结构
┌───┬───┐
│data │next │
└───┴───┘
data域–存放结点值的数据域
next域–存放结点的直接后继的地址（位置）的指针域（链域）
思考：
（1）将1张单链表L分成3张单链表，数据域为0的存放在L1，数据域为1的存放在L2，数据域为2的存放在L3；
（2）将3张表连接在一起，成为1张表。
C代码如下
#include"linklist.cpp"
void sort(LinkNode *&L,LinkNode *&L1,LinkNode *&L2,LinkNode *&L3)
{
LinkNode *p=L->next,*r1,*r2,*r3;
L1=L;
r1=L1;
L2=(LinkNode *)malloc(sizeof(LinkNode));
L2->next=NULL;
r2=L2;
L3=(LinkNode *)malloc(sizeof(LinkNode));
L3->next=NULL;
r3=L3;
while(p!=NULL)
{
if(p->data==0)
{
r1->next=p;
r1=p;
p=p->next;
}
else if(p->data==1)
{
r2->next=p;
r2=p;
p=p->next;
}
else if(p->data==2)
{
r3->next=p;
r3=p;
p=p->next;
}
}
r1->next=L2->next;
r2->next=L3->next;
r3->next=NULL;
DispList(L);
}
int main()
{
LinkNode *h,*h1,*h2,*h3;
int a[]={0,1,0,2,1,2,0,1,2};
CreateListR(h,a,9);
DispList(h);
sort(h,h1,h2,h3);
return 0;
}
在“linklist.cpp”里包含了单链表的定义、建立、头插法/尾插法、查找等一系列基本运算。要用到如下：
#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LinkNode;
void CreateListR(LinkNode *&L,ElemType a[],int n)//尾插法
{
LinkNode *s,*r;
L=(LinkNode *)malloc(sizeof(LinkNode));
r=L;
for(int i=0;i<n;i++)
{
s=(LinkNode *)malloc(sizeof(LinkNode));
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
}
输出结果
