[C++知识库]学习记录1

今天啊，首先，熟悉了一下链表的创建、数目的去重和排序，代码如下：

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int ber;
struct node *next;
}tt;
tt *a,*b,*tail1,*tail2;
tt *creat(int x)
{
? ? int i,j;
? ? tt *head,*tail;
? ? head=tail=(tt*)malloc(sizeof(tt));
? ? for(i=0;i<x;i++)
? ? ? ? {
? ? ? ? ? ? tt *txt=(tt*)malloc(sizeof(tt));
? ? ? ? ? ? scanf("%d",&txt->ber);
? ? ? ? ? ? tail->next=txt;
? ? ? ? ? ? tail=tail->next;
? ? ? ? }
? ? ? ? tail->next=NULL;
? ? return (head);
}
void sort(tt *goal)
{
? ? while(goal!=NULL)
? ? {
? ? ? ? tt *q,*p;
? ? ? ? p=goal;
? ? ? ? q=goal->next;
? ? ? ? while(q!=NULL)
? ? ? ? {
? ? ? ? ? ? if(q->ber==goal->ber)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? p->next=q->next;
? ? ? ? ? ? ? ? free(q);
? ? ? ? ? ? ? ? q=p->next;
? ? ? ? ? ? }
? ? ? ? ? ? else p=p->next,q=q->next;
? ? ? ? }
? ? ? ? goal=goal->next;
? ? }
}
int main()
{
? ? tt *a,*b;
? ? int m,n,i,j;
? ? scanf("%d%d",&m,&n);
? ? a=creat(m);
? ? b=creat(n);
? ? a=a->next;
? ? b=b->next;
? ? sort(a);
? ? sort(b);
? ? while(a!=NULL)
? ? {
? ? ? ? printf("%d ",a->ber);
? ? ? ? a=a->next;
? ? }
? ? printf("\n");
? ? while(b!=NULL)
? ? {
? ? ? ? printf("%d ",b->ber);
? ? ? ? b=b->next;
? ? }
}

其次是队列和栈的共同模拟。

队列问题主要使用两个变量代表其队首与队尾，这样子就会让操作变得清晰又简单了。栈的操作只需要使用一个变量就好了，输入一个数即top++，输出时将使用top--进行一点一点输出，即可符合栈的操作特性。

代码如下：

#include <stdio.h>
#include <string.h>
int a[10010],b[10010],flagz,flagt,top,back,top2;
void pushz(int t)
{
? ?a[++top]=t;
}
void pushteam(int t)
{
? ? b[back]=t;
? ? back++;
}
void popz()
{
? ? if(top==0)
? ? {
? ? ? ? flagz=1;
? ? ? ? return;
? ? }
? ? top--;
}
void popteam()
{
? ? if(top2>=back)
? ? {
? ? ? ? flagt=1;
? ? ? ? return;
? ? }
? ? top2++;
}
int main()
{
? ? int m,n,i;
? ? scanf("%d",&m);
? ? while(m--)
? ? {
? ? ? ? top=top2=back=flagz=flagt=0;
? ? ? ? scanf("%d",&n);
? ? ? ? while(n--)
? ? ? ? {
? ? ? ? ? ? char action[1000];
? ? ? ? ? ? int num;
? ? ? ? ? ? scanf("%s",action);
? ? ? ? ? ? if(strcmp(action,"push")==0)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? scanf("%d",&num);
? ? ? ? ? ? ? ? ? ? pushz(num);pushteam(num);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? else if(strcmp(action,"pop")==0)
? ? ? ? ? ? ? ? {popz();popteam();}
? ? ? ? }
? ? ? ? if(flagt)
? ? ? ? ? ? printf("error\n");
? ? ? ? if(flagz)
? ? ? ? ? ? printf("error\n");
? ? ? ? while(top2<back&&flagt==0)
? ? ? ? {
? ? ? ? ? ? if(top2==back-1)
? ? ? ? ? ? ? ? printf("%d\n",b[top2++]);
? ? ? ? ? ? else printf("%d ",b[top2++]);
? ? ? ? }
? ? ? ? for(i=1;i<=top&&flagz==0;i++)
? ? ? ? ? ? if(i==top)
? ? ? ? ? ? ? ? printf("%d\n",a[i]);
? ? ? ? ? ? else printf("%d ",a[i]);
? ? }
}

其实还复习瞅了瞅欧拉筛，重新看了优化版，发现优化版真是快得不行，只能说算法真牛。

他用位运算进行奇数判断，因为在计算机中位运算速度会更快，并且一旦遇到能取余所用素数的i（i为寻常数，就是你需要求素数的范围中的普通数）就跳出循环，这是为了保持每一个数据只访问一次，因为这样你会发现，之后会重复判断的地方会被剔除，就减少了时间复杂度。

代码如下：

#include <stdio.h>

int a[100010]={0},prime[100010]={0},i,j,cn=0;

void oula(int n)

{

? for(i=2;i<=n;i++)

? ? {

? ? ? if(!a[i]) prime[++cn]=i;

? ? ? for(j=1;j<=cn&&i*prime[j]<=n;j++)

? ? ? ? {

? ? ? ? ? a[i*prime[j]]=1;

? ? ? ? ? if(i%prime[j]==0) break;

? ? ? ? }

? ? }

}

int main()

{

? ?int n;

? ?scanf("%lld",&n);

? ?oula(n);

? ?for(i=1;i<=cn;i++)

? ? ?printf("%lld\n",prime[i]);

}

?