取不同元素(栈和队列)

取不同元素(栈和队列)

时间: 1ms        内存:1000M

描述:

题目:设线性顺序表A中含有N个有序整数,线性顺序表B为空,试编写一个算法将A中不相同的数据移入线性顺序表B中。要求对线性顺序表A只扫描一遍,并且不能扫描线性顺序表B。例如:A=(1,2,2,2,2,6,6,9,9)B=(1,2,6,9)

输入:

输入:

1 2 2 2 2 6 6 9 9

输出:

输出:

1 2 6 9

示例输入:

1 2 2 2 2 6 6 9 9

示例输出:

1 2 6 9

提示:

参考答案(内存最优[752]):

#include<stdio.h>   
#include<malloc.h> 
#include<string.h> 
#define SEN 100   
      
struct sqstack   
{   
    char *base;   
    char *top;   
    int size;   
};   
      
struct sqstack *initEmptyStack()   /*构建空輚*/
{   
    struct sqstack *p;   
    p=(struct sqstack *)malloc(sizeof(struct sqstack));   
    if(p!=NULL)   
    {   
        p->base=(char *)malloc(sizeof(struct sqstack)*SEN);   
        if(p->base!=NULL)   
        {   
            p->top=p->base;   
            p->size=SEN;   
            return p;   
        }   
    }   
    else
        free(p);   
    return NULL;   
}   
      
int push(struct sqstack *p,char a)         /*入栈*/
{   
    *p->top++=a;   
    return 0;   
}   
      
int gettop(struct sqstack *p)             /*取栈顶元素*/
{  
    if(p->base!=p->top)  
        return *(p->top-1);  
    return 0; 
} 


int pop(struct sqstack *p)              /*出栈*/
{   
    return *(--p->top);   
}   
      
int main()   
{    
    struct sqstack *p1,*p2; 
    int c,m=9; 
    p1=initEmptyStack(); 
	p2=initEmptyStack();
	scanf("%d",&c);
	push(p1,c);
	m--;
	while(m--)
	{
		scanf("%d",&c);
		if(gettop(p1)==c)
		{}
		else
			push(p1,c);
	}
	while(p1->base!=p1->top)
		push(p2,pop(p1));
	while(p2->base!=p2->top)
		printf("%d ",pop(p2));
	printf("\n");
    return 0;   
}

参考答案(时间最优[0]):

#include <iostream>
using namespace std;
int main()
{
    int a[100],b[100]={0};
    int i=0,j;
    while (cin>>a[i])
    {
        b[a[i]]=1;
        i++;
    }
    int k=1;
    for (j=0;j<=a[i-1];++j)
    {
        if (b[j]==1)
        {
            if (k==1)
            {
                cout<<j;
                k=0;
            }
            else
                cout<<" "<<j;
        }
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注