荷兰国旗问题(顺序表和链表)

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;
}LinkNode; 
void  InitLinkNode(LinkNode *L)
{
	L=(LinkNode*)malloc(sizeof(LinkNode));
 L->next =NULL;
}
void CreateLinkNode(LinkNode *&L,int a[],int n)
{
 int i;
LinkNode *s;
L=(LinkNode*)malloc(sizeof(LinkNode));
L->next =NULL;
	for(i=0;i<n;i++)
	{
		s=(LinkNode *)malloc(sizeof(LinkNode));
		s->data=a[i];
		s->next=L->next;
		L->next =s;
	}
}
void DispLinkNode(LinkNode*L)
{
	LinkNode *p=L->next ;
    while(p!=NULL)
	{
	cout<<p->data ;
	p=p->next ;
	}
}
void move(LinkNode *&L)
{
 LinkNode *L1,*L2,*r,*r1,*r2,*p;
  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()
{
    LinkNode * L;
    int a[12] = { 1,0,2,1,0,0,1,2,2,1,0,2 };
    InitLinkNode(L);
    CreateLinkNode(L,a,12);
    move(L);
    DispLinkNode(L);
    return 0;
}

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->