C++语言单链表实现荷兰旗问题

C++语言单链表实现荷兰旗问题

一.设备及软件
VC6.0

二.语言
C++

三.涉及的数据结构与算法
单链表、尾插法

四.问题描述
荷兰旗问题亦称三色旗问题。
这里荷兰旗用0，1，2分别表示三种颜色：红，白，蓝。用数组存放一串数字。开始是打乱顺序的排列，要求用单链表分别存放这三种数，然后按旗子的颜色，红，白，蓝顺序输出。

五.主要注意点
荷兰旗问题的C++代码分为这几部分：

1. 结构化单链表；
2. 创建单链表；
3. 初始化单链表；
4. 实现主要程序；（关键）
5. 输出单链表。

其中：

1）结构化单链表

2）创建单链表

两个指针*r,*s，*r指向尾部，这里用尾插法。*s用于保存数组。循环插入数组后，注意释放尾部结点的空间。（具体代码在代码部分可见）

3）初始化单链表

4）输出单链表

5）关键代码分析

荷兰旗关键程序，在于创建三张链表L1,L2,L3分别用三个指针*r1,*r2,*r3指向他们的尾部。

其中L1用L的头结点，L2,L3分别开辟新的头结点。

当P！=NULL，遍历数组，为0的尾插入到L1表中，为1的尾插入到L2表中，为2的尾插入到L3表中。q=p->next，临时保存p的下一个结点，p=q在往复循环判断。

最后注意释放三个指针*r1,*r2,*r3指向的尾部结点的空间。

该方法中可以包含输出方法。

代码：

执行结果：

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览35145 人正在系统学习中