データ構造のオンラインテスト問題のまとめ

125246 ワード

1、アルゴリズムを作成し、2つの昇順チェーンテーブルを元の表空間内で1つの昇順チェーンテーブルにまとめる.

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct linklist
{
    int data;
    struct linklist *next;
}linklist;

linklist *creat()
{
    linklist *head;
    head=(linklist*)malloc(sizeof(linklist));
    linklist *p,*q=head;
    int temp;
    while(1)
    {
        scanf("%d",&temp);
        if(temp!=-9999)
        {
            p=(linklist*)malloc(sizeof(linklist));
            p->data=temp;
            q->next=p;
            q=p;
        }
        else
        {
            q->next=NULL;
            break;
        }
    }
    return head;
}

linklist* unionlist(linklist* &a,linklist* b)
{
    linklist *pa=a->next,*pb=b->next,*s,*r=a;
    while(pa!=NULL&&pb!=NULL)
    {
        if(pa->datadata)
        {
            r=pa;
            pa=pa->next;
        }
        else
        {
            s=(linklist*)malloc(sizeof(linklist));
            s->data=pb->data;
            s->next=pa;
            r->next=s;
            r=s;
            pb=pb->next;
        }
    }
    if(pb!=NULL)
    {
        r->next=pb;
    }
    return a;
}



int main()
{
    linklist *a,*b,*p;
    printf("input first linklist:");
    a=creat();
    printf("input second linklist:");
    b=creat();
    unionlist(a,b);
    p=a->next;
    while(p)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    return 0;
}

2、アルゴリズムを作成し、2つの昇順チェーンテーブルを元の表空間内で1つの降順チェーンテーブルにまとめる.

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct linklist
{
    int data;
    struct linklist *next;
}linklist;

linklist *creat()
{
    linklist *head;
    head=(linklist*)malloc(sizeof(linklist));
    linklist *p,*q=head;
    int temp;
    while(1)
    {
        scanf("%d",&temp);
        if(temp!=-9999)
        {
            p=(linklist*)malloc(sizeof(linklist));
            p->data=temp;
            q->next=p;
            q=p;
        }
        else
        {
            q->next=NULL;
            break;
        }
    }
    return head;
}

linklist* unionlist(linklist* &a,linklist* b)
{
    linklist *pa=a->next,*pb=b->next,*r=a,*s;
    while(pa!=NULL&&pb!=NULL)
    {
        if(pa->datadata)
        {
            r=pa;
            pa=pa->next;
        }
        else
        {
            s=(linklist*)malloc(sizeof(linklist));
            s->data=pb->data;
            s->next=pa;
            r->next=s;
            r=s;
            pb=pb->next;

        }
    }
    if(pb!=NULL)
    {
        r->next=pb;
    }
    return a;
}

void reverse_link(linklist* &a)
{
    linklist *p=a->next,*q;
    a->next=NULL;
    while(p)
    {
        q=p->next;
        p->next=a->next;
        a->next=p;
        p=q;
    }

}


int main()
{
    linklist *a,*b,*p;
    printf("input first linklist:");
    a=creat();
    printf("input second linklist:");
    b=creat();
    unionlist(a,b);
    reverse_link(a);
    p=a->next;
    while(p)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    return 0;
}

3、アルゴリズムを作成し、順序記憶構造で二つの昇順集合のA=A-B演算を実現する.(事実上は集合を求める差集合,すなわちAにのみ出現し,Bには出現しないAの要素である)

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define maxsize 20

typedef struct sqlist
{
    int data[maxsize];
    int length;
}sqlist,*lnode;

void create(lnode &l,int a[],int n)
{
    l=(sqlist*)malloc(sizeof(sqlist));
    for(int i=0;idata[i]=a[i];
    }
    l->length=n;
}

void del(lnode &l,int n)
{
    int i;
    for(i=n;ilength-1;i++)
    {
        l->data[i]=l->data[i+1];
    }
    l->length--;
}

void listminus(lnode &a,lnode b)
{
    int m=a->length,n=b->length;
    int i,j,k=0;
    for(i=0;ifor(j=k;j<=n;j++)
        {
            if(a->data[i]==b->data[j])
            {
                del(a,i);
                k=j+1;
            }
        }
    }
}

void show(lnode l)
{
    int i;
    for(i=0;ilength;i++)
        printf("%d ",l->data[i]);
}



int main()
{
    lnode A,B;
    int a[10],b[10];
    printf("the five number :");
    for(int i=0;i<5;i++)
    {
        scanf("%d",&a[i]);
    }
    printf("the five number :");
    for(int i=0;i<5;i++)
    {
        scanf("%d",&b[i]);
    }
    create(A,a,5);
    create(B,b,5);
    listminus(A,B);
    show(A);
    return 0;
}

4、アルゴリズムを作成し、単一チェーンテーブルで二つの昇順集合AとBの差集合を集合Cに保存する.即ちC=A-B演算を実現し、C中の要素の減少秩序を要求する.

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;

typedef struct node
{
    int data;
    struct node *next;
}node,*linklist;

void create(linklist l)
{
    int e;
    linklist p,q;
    p=l;
    printf("input the list:");
    scanf("%d",&e);
    while(e!=-9999)
    {
        q=(node*)malloc(sizeof(node));
        q->data=e;
        p->next=q;
        q->next=NULL;
        p=q;
        scanf("%d",&e);
    }
}

linklist linkminus(linklist &a,linklist b)
{
    linklist p=a->next,q=b->next,pre=a,r;
    while(p && q)
    {
        if(p->data<q->data)
        {
            pre=p;
            p=p->next;
        }
        else if(p->data>q->data)
        {
            q=q->next;
        }
        else
        {
            pre->next=p->next;
            r=p;
            p=p->next;
            free(r);
        }
    }
    return a;
}

void putdata(linklist l)
{
    linklist p=l->next;
    printf("
");
    while(p)
    {
        printf("%d ",p->data);
        p=p->next;
    }

}

void reverse_link(linklist &a)
{
    linklist p=a->next,q;
    a->next=NULL;
    while(p)
    {
        q=p->next;
        p->next=a->next;
        a->next=p;
        p=q;
    }
}

int main()
{
    linklist A,B,C;
    A=(node*)malloc(sizeof(node));
    A->next=NULL;
    B=(node*)malloc(sizeof(node));
    B->next=NULL;
    create(A);
    create(B);
    C=linkminus(A,B);
    reverse_link(C);
    putdata(C);
    return 0;
}

5、アルゴリズムを作成し、単一チェーンテーブルをその場で逆置きする.

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct linklist
{
    int data;
    struct linklist *next;
}linklist;

linklist* creat()
{
    linklist* head;
    head=(linklist*)malloc(sizeof(linklist));
    linklist *p,*q=head;
    int temp;
    while(1)
    {
        scanf("%d",&temp);
        if(temp!=-9999)
        {
            p=(linklist*)malloc(sizeof(linklist));
            p->data=temp;
            q->next=p;
            q=p;
            p=p->next;
        }
        else
        {
            q->next=NULL;
            break;
        }
    }
    return head;
}

void reverse_link(linklist* &a)
{
    linklist *p=a->next,*q;
    a->next=NULL;
    while(p)
    {
        q=p->next;
        p->next=a->next;
        a->next=p;
        p=q;
    }
}

int main()
{
    linklist *a,*p;
    printf("input first linklist:");
    a=creat();
    p=a->next;
    while(p)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("
");
    reverse_link(a);
    p=a->next;
    while(p)
    {
        printf("%d ",p->data);
        p=p->next;

    }
    return 0;
}

6、アルゴリズムを作成し、二重チェーンテーブルのi番目の要素の前に要素を挿入する.

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct lnode
{
    int data;
    struct lnode *llink,*rlink;
}lnode,*linknode;

typedef struct
{
    linknode head,rear;
    int len;
}linklist;

void init(linklist &l)
{
    l.head=l.rear=(lnode*)malloc(sizeof(lnode));
    l.len=0;
    l.head->llink=l.head->rlink=l.head;
}

void create(linklist &l)
{
    linknode p;
    int e;
    init(l);
    scanf("%d",&e);
    while(e!=-9999)
    {
        p=(lnode*)malloc(sizeof(lnode));
        p->data=e;
        p->rlink=l.head->rlink;
        l.head->rlink=p;
        p->llink=l.head;
        p->rlink->llink=p;
        if(l.head==l.rear)
        {
            l.rear=p;
        }
        l.len++;
        scanf("%d",&e);
    }
}

int ins(linklist &l,int k,int e)
{
    int j;
    linknode p,q;
    if(k<1||k>l.len)return 0;
    p=l.head;
    j=0;
    while(j1)
    {
        p=p->rlink;
        j++;
    }
    q=(lnode*)malloc(sizeof(lnode));
    q->data=e;
    q->llink=p;
    q->rlink=p->rlink;
    p->rlink=q;
    if(k == ++l.len)
    {
        l.rear=q;
    }
    return 1;
}

void putdata(linklist l)
{
    linknode p = l.head->rlink;
    printf("
");
    while (p != l.head)
    {
        printf("%d,", p->data);
        p = p->rlink;
    }
}

int main()
{
    linklist l;
    int e;
    printf("
input to l:");
    create(l);
    putdata(l);
    ins(l,3,100);
    putdata(l);
    return 0;
}

7、アルゴリズムを作成し、1リットルの単鎖表のすべての値が同じ余分な要素を削除し、削除されたノード空間を解放する.

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;

typedef struct lnode
{
    int data;
    struct lnode *next;
}lnode,*linklist;

void create(linklist l)
{
    int e;
    linklist p,q;
    p=l;
    printf("input the list:");
    scanf("%d",&e);
    while(e!=-9999)
    {
        q=(lnode*)malloc(sizeof(lnode));
        q->data=e;
        p->next=q;
        q->next=NULL;
        p=q;
        scanf("%d",&e);
    }
}

void delsame(linklist &l)
{
    linklist p,q,pre;
    int flag=0;
    p=l;
    p=p->next;
    while(p)
    {
        if(!flag)
        {
            pre=p;
            p=p->next;
            if(p && pre->data==p->data)
            {
                pre->next=p->next;
                q=p;
                p=p->next;
                free(q);
                flag=1;
            }
        }
        else
        {
            if(pre->data==p->data)
            {

                pre->next=p->next;
                q=p;
                p=p->next;
                free(q);
            }
            else
            {
                flag=0;
            }
        }


    }
}

void putdata(linklist l)
{
    linklist p=l->next;
    printf("
");
    while(p)
    {
        printf("%d ",p->data);
        p=p->next;
    }

}

int main()
{
    linklist l;
    l=(lnode*)malloc(sizeof(lnode));
    l->next=NULL;
    create(l);
    putdata(l);
    delsame(l);
    putdata(l);
    return 0;
}

8、アルゴリズムを作成し、昇順単鎖表のすべての値が[mink,maxk]の間の要素を削除し、削除されたノード空間を解放する.

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct lnode
{
    int data;
    struct lnode *next;
}lnode,*linklist;

void create(linklist l)
{
    int e;
    linklist p,q;
    p=l;
    printf("input the list:");
    scanf("%d",&e);
    while(e!=-9999)
    {
        q=(lnode*)malloc(sizeof(lnode));
        q->data=e;
        p->next=q;
        q->next=NULL;
        p=q;
        scanf("%d",&e);
    }
}

int del(linklist &l,int mink,int maxk)
{
    linklist p,q,pre=NULL;
    if(mink>maxk)return 0;
    p=l;
    pre=p;
    p=p->next;
    while(p && p->dataif(p->data<=mink)
        {
            pre=p;
            p=p->next;
        }
        else
        {
            pre->next=p->next;
            q=p;
            p=p->next;
            free(q);
        }
    }
    return 1;
}

void putdata(linklist l)
{
    linklist p=l->next;
    printf("
");
    while(p)
    {
        printf("%d ",p->data);
        p=p->next;
    }

}

int main()
{
    linklist l;
    l=(lnode*)malloc(sizeof(lnode));
    l->next=NULL;
    create(l);
    putdata(l);
    del(l,3,8);
    putdata(l);
    return 0;
}

9、アルゴリズムを作成し、式の中の括弧がペアになっているかどうかを判断し、大、中、小の3種類の括弧を含む.

#include 
#include 
#include 
#include 
#define init_size 100
#define add_size 10

typedef struct sqstack
{
    char *data;
    int stacksize,top;
}sqstack;

void init_stack(sqstack &s)
{
    s.data=(char *)malloc(init_size*sizeof(char));
    s.top=0;
    s.stacksize=init_size;
}

int push(sqstack &s,char e)
{
    char *newdata;
    if(s.top==s.stacksize)
    {
        newdata=(char *)realloc(s.data,(init_size+add_size)*sizeof(char));
        if(!newdata)
            exit(0);
        s.data=newdata;
        s.stacksize+=add_size;
    }
    s.data[s.top++]=e;
    return 1;
}

int pop(sqstack &s,char &e)
{
    if(!s.top)
        return 0;
    e=s.data[--s.top];
    return 1;
}

int judge(char *s)
{
    int i;
    char x;
    sqstack r;
    init_stack(r);
    for(i=0;s[i]!='\0';i++)
    {
        if(s[i]=='('||s[i]=='['||s[i]=='{')
            push(r,s[i]);
        if(s[i]==')'||s[i]==']'||s[i]=='}')
        {
            pop(r,x);
            if(s[i]==')' && x!='(')return 0;
            if(s[i]==']' && x!='[')return 0;
            if(s[i]=='}' && x!='{')return 0;
        }
    }
    if(r.top)return 0;
    return 1;
}

int main()
{
    char c[111];
    gets(c);
    if(judge(c))printf("    ！");
    else printf("     ……");
    return 0;
}

10、アルゴリズムを作成し、hanoi塔問題を実現する.

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

void hanoi(int n,char x,char y,char z)
{
    if(n==1)printf("  %d     %c    %c 
",n,x,z);
    else
    {
        hanoi(n-1,x,z,y);
        printf("  %d     %c    %c 
",n,x,z);
        hanoi(n-1,y,x,z);
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    hanoi(n,'A','B','C');
    return 0;
}

11、アルゴリズムを作成し、サブストリングtの主ストリングsにおける位置を求める.

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define maxsize 255
int pos[maxsize];
typedef char sstring[maxsize+1];

int strassign(sstring &s,char *ch)
{
    int i=0;
    char *p=ch;
    while(i0]=i;
    if(*p)return 0;
    else return 1;
}

void findpos(sstring s,sstring t,int p)
{
    int i=p,j=1,k=0;
    while(i<=s[0])
    {
        if(s[i]==t[j])
        {
            i++;
            j++;
        }
        else
        {
            i=i-j+2;
            j=1;
        }
        if(j>t[0])
        {
            pos[k++]=i-j+1;
            j=1;
        }
    }
}


int main()
{
    sstring s,t;
    int i;
    memset(pos,-1,sizeof(pos));
    strassign(s,"abccdefcde");
    strassign(t,"cde");
    findpos(s,t,1);
    if(pos[0]==-1)printf("no finding!
");
    else
    {
        for(i=0;pos[i]!=-1;i++)
            printf("%d ",pos[i]);
        printf("
");
    }

    return 0;
}

12、アルゴリズムを作成し、主列s中のすべての列tと同じサブ列を削除する.

#include
#define MaxSize 100
typedef struct snode
{
    char data[MaxSize];
    int length;
}SqString;
void StrAssign(SqString &s,char cstr[])
{
    int i;
    for(i=0;cstr[i]!='\0';i++)
        s.data[i]=cstr[i];
    s.length=i;
}
void del(SqString &s,SqString t)
{
    int i=0,j=0,n=0,flag=0;
    while(iif (s.data[i]==t.data[j])
        {
            s.data[n++]=s.data[i++];
            j++;
            flag=1;
        }
        else
        {
            if(flag==0)
                s.data[n++]=s.data[i];
            i=i-j+1;
            j=0;
            flag=0;
        }
        if(j>=t.length)
        {
            n=n-t.length;
            j=0;
            flag=0;
        }
    }
    s.length=n;
    s.data[n]='\0';
}
int main(){
    char s[MaxSize],t[MaxSize];
    int a[MaxSize],i,j=0,r;
    SqString p,q;
    StrAssign(p,"fhfhfasdhfghf");
    StrAssign(q,"hf");
    del(p,q);
    puts(p.data);
    printf("
");
}

13、アルゴリズムを作成し、シリアルの比較演算を実現する.

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define maxsize 255
typedef char sstring[maxsize+1];

int strassign(sstring &s,char *ch)
{
    int i=0;
    char *p=ch;
    while(i0]=i;
    if(*p)return 0;
    else return 1;
}

int strcomp(sstring s,sstring t)
{
    int i=1;
    while(i<=s[0] && i<=t[0])
    {
        if(s[i]==t[i])i++;
        else if(s[i]>t[i])return 1;
        else return -1;
    }
    if(s[0]==t[0])return 0;
    else return s[0]-t[0];
}


int main()
{
    sstring s,t;
    int k;
    strassign(s,"abcd");
    strassign(t,"abce");
    k=strcomp(s,t);
    if(k>0)printf("s>t
");
    else if(k==0)printf("s=t
");
    else printf("s);
    return 0;
}

14、アルゴリズムを作成し、シリアルの接続演算を実現する.

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define maxsize 255
typedef char sstring[maxsize+1];

int strassign(sstring &s,char *ch)
{
    int i=0;
    char *p=ch;
    while(i0]=i;
    if(*p)return 0;
    else return 1;
}

int strconcat(sstring t,sstring s1,sstring s2)
{
    int i;
    if(s1[0]+s2[0]<=maxsize)
    {
        for(i=1;i<=s1[0];i++)
            t[i]=s1[i];
        for(i=1;i<=s2[0];i++)
            t[s1[0]+i]=s2[i];
        t[0]=s1[0]+s2[0];
        return 1;
    }
    else
    {
        for(i=1;i<=s1[0];i++)
            t[i]=s1[i];
        for(i=1;i<=maxsize;i++)
            t[s1[0]+i]=s2[i];
        t[0]=maxsize;
        return 0;
    }
}

void putdata(sstring s)
{
    int i;
    printf("
");
    for(i=1; i<=s[0]; i++)
        printf("%c",s[i]);
}

int main()
{
    sstring s,t,r;
    strassign(r,"");
    strassign(s,"abcdef");
    strassign(t," ghijk");
    strconcat(r,s,t);
    putdata(r);
    return 0;
}

15、アルゴリズムを編纂し、先に二叉木を遍歴することを実現する.

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define inf 0x3f3f3f3f

typedef struct tnode
{
    int data;
    struct tnode *lchild,*rchild;
}tnode,*bitree;

void visit(bitree t)
{
    printf("%c ",t->data);
}

void preorder(bitree t)
{
    if(t)
    {
        visit(t);
        preorder(t->lchild);
        preorder(t->rchild);
    }

}

void create(bitree &t)
{
    char ch;
    scanf("%c",&ch);
    getchar();
    if(ch=='#')t=NULL;
    else
    {
        t=(tnode*)malloc(sizeof(tnode));
        t->data=ch;
        printf("   %c     ：",ch);
        create(t->lchild);
        printf("   %c     ：",ch);
        create(t->rchild);
    }
}


int main()
{
    bitree t;
    printf("     ：");
    create(t);
    preorder(t);
    return 0;
}

16、アルゴリズムを作成し、中順に二叉木を遍歴する.

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct tnode
{
    int data;
    struct tnode *lchild,*rchild;
}tnode,*bitree;

void create(bitree &t)
{
    char ch;
    scanf("%c",&ch);
    getchar();
    if(ch == '#')t=NULL;
    else
    {
        t=(tnode*)malloc(sizeof(tnode));
        t->data=ch;
        printf("   %c     ：",ch);
        create(t->lchild);
        printf("   %c     ：",ch);
        create(t->rchild);
    }
}

void visit(bitree t)
{
    printf("%c ",t->data);
}

void inorder(bitree t)
{
    if(t)
    {
        inorder(t->lchild);
        visit(t);
        inorder(t->rchild);
    }

}

int main()
{
    bitree t;
    printf("     ：");
    create(t);
    inorder(t);
    return 0;
}

17、アルゴリズムを編纂し、後序に二叉木を遍歴することを実現する.

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct tnode
{
    int data;
    struct tnode *lchild,*rchild;
}tnode,*bitree;

void create(bitree &t)
{
    char ch;
    scanf("%c",&ch);
    getchar();
    if(ch == '#')t=NULL;
    else
    {
        t=(tnode*)malloc(sizeof(tnode));
        t->data=ch;
        printf("   %c     ：",ch);
        create(t->lchild);
        printf("   %c     ：",ch);
        create(t->rchild);
    }
}

void visit(bitree t)
{
    printf("%c ",t->data);
}

void posorder(bitree t)
{
    if(t)
    {
        posorder(t->lchild);
        posorder(t->rchild);
        visit(t);
    }
}

int main()
{
    bitree t;
    printf("     ：");
    create(t);
    posorder(t);
    return 0;
}

18、アルゴリズムを編纂し、層順に二叉木を遍歴することを実現する.

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct tnode
{
    int data;
    struct tnode *lchild,*rchild;
}tnode,*bitree;

void create(bitree &t)
{
    char ch;
    scanf("%c",&ch);
    getchar();
    if(ch == '#')t=NULL;
    else
    {
        t=(tnode*)malloc(sizeof(tnode));
        t->data=ch;
        printf("   %c     ：",ch);
        create(t->lchild);
        printf("   %c     ：",ch);
        create(t->rchild);
    }
}

void visit(bitree t)
{
    printf("%c ",t->data);
}

void levelorder(bitree t)
{
    queueq;
    bitree p;
    if(t)q.push(t);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        visit(p);
        if(p->lchild)q.push(p->lchild);
        if(p->rchild)q.push(p->rchild);
    }
}


int main()
{
    bitree bt;
    printf("     ：");
    create(bt);
    printf("       ：
");
    levelorder(bt);
    return 0;
}

19、アルゴリズムを作成し、二叉木の高さを計算する.

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct tnode
{
    int data;
    struct tnode *lchild,*rchild;
}tnode,*bitree;

void create(bitree &bt)
{
    char ch;
    scanf("%c",&ch);
    getchar();
    if(ch=='#')bt=NULL;
    else
    {
        bt=(tnode*)malloc(sizeof(tnode));
        bt->data=ch;
        printf("  %c     ：", ch);
        create(bt->lchild);
        printf("  %c     ：", ch);
        create(bt->rchild);
    }
}

int max(int a,int b)
{
    if(a>b)return a;
    else return b;
}

int treehigh(bitree t)
{
    int l,r,h;
    if(!t)h=0;
    else
    {
        l=treehigh(t->lchild);
        r=treehigh(t->rchild);
        h=max(l,r)+1;
    }
    return h;
}

int main()
{
    bitree t;
    printf("     ：");
    create(t);
    printf("%d",treehigh(t));
    return 0;
}

20、アルゴリズムを作成し、二叉樹の葉の結点個数を計算する.

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct tnode
{
    int data;
    struct tnode *lchild,*rchild;
}tnode,*bitree;

void create(bitree &t)
{
    char ch;
    scanf("%c",&ch);
    getchar();
    if(ch == '#')t=NULL;
    else
    {
        t=(tnode*)malloc(sizeof(tnode));
        t->data=ch;
        printf("   %c     ：",ch);
        create(t->lchild);
        printf("   %c     ：",ch);
        create(t->rchild);
    }
}

int leaves(bitree t,int &i)
{
    if(!t->lchild && !t->rchild)i++;
    else
    {
        leaves(t->lchild,i);
        leaves(t->rchild,i);
    }
}


int main()
{
    bitree t;
    int n=0;
     printf("     ：");
    create(t);
    leaves(t,n);
    printf("%d",n);
    return 0;
}

21、アルゴリズムを作成し、二叉木の左右の子木を交換する.

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct tnode
{
    int data;
    struct tnode *lchild,*rchild;
}tnode,*bitree;

void create(bitree &t)
{
    char ch;
    scanf("%c",&ch);
    getchar();
    if(ch=='#')t=NULL;
    else
    {
        t=(tnode*)malloc(sizeof(tnode));
        t->data=ch;
        printf("   %c     ：",ch);
        create(t->lchild);
        printf("   %c     ：",ch);
        create(t->rchild);
    }
}

void visit(bitree t)
{
    printf("%c ",t->data);
}

void preorder(bitree t)
{
    if(t)
    {
        visit(t);
        preorder(t->lchild);
        preorder(t->rchild);
    }

}

bitree exchange(bitree &t)
{
    if(t)
    {
        if(t->lchild || t->rchild)
        {
            bitree p,q;
            p=exchange(t->lchild);
            q=exchange(t->rchild);
            t->lchild=q;
            t->rchild=p;
        }
    }
    return t;
}

int main()
{
    bitree t;
    printf("     ：");
    create(t);
    printf("before change:");
    preorder(t);
    printf("
after change child:");
    exchange(t);
    preorder(t);
    printf("
");
    return 0;
}

22、アルゴリズムを作成し、2本の二叉木が等しいかどうかを判断する.(root 1の左サブツリーがroot 2の左サブツリーと同じである場合、root 1の右サブツリーはroot 2の右サブツリーと同じであり、この2つのツリーは同じである.root 1の左サブツリーがroot 2の右サブツリーと同じである場合、root 1の右サブツリーはroot 2の左サブツリーと同じであり、この2つのツリーは同じである.
注意私のところは2つの空木でも等しいと見なしていますが、状況によっては異なると説明する面接問題もあります)

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct tnode
{
    int data;
    struct tnode *lchild,*rchild;
}tnode,*bitree;

void create(bitree &t)
{
    char ch;
    scanf("%c",&ch);
    getchar();
    if(ch=='#')t=NULL;
    else
    {
        t=(tnode*)malloc(sizeof(tnode));
        t->data=ch;
        printf("   %c     ：",ch);
        create(t->lchild);
        printf("   %c     ：",ch);
        create(t->rchild);
    }
}

int bitreecomp(bitree t,bitree s)
{
    if(!t && !s)return 1;
    if(t && s)
    {
        if(t->data == s->data)
        {
            if(bitreecomp(t->lchild,s->lchild)&&bitreecomp(t->rchild,s->rchild) || bitreecomp(t->rchild,s->lchild)&&bitreecomp(t->lchild,s->rchild))
            {
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    bitree t,s;
    printf("         ：");
    create(t);
    printf("         ：");
    create(s);
    if(bitreecomp(t,s))printf("  ！");
    else printf("   !");
    return 0;
}

23、アルゴリズムを作成し、二叉木の複製を完了する.

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct tnode
{
    int data;
    struct tnode *lchild,*rchild;
}tnode,*bitree;

void create(bitree &t)
{
    char ch;
    scanf("%c",&ch);
    getchar();
    if(ch == '#')t=NULL;
    else
    {
        t=(tnode*)malloc(sizeof(tnode));
        t->data=ch;
        printf("   %c     ：",ch);
        create(t->lchild);
        printf("   %c     ：",ch);
        create(t->rchild);
    }
}

bitree copytree(bitree t)
{
    bitree l,r,p;
    if(t==NULL)return NULL;
    l=copytree(t->lchild);
    r=copytree(t->rchild);
    p=(tnode*)malloc(sizeof(tnode));
    p->data=t->data;
    p->lchild=l;
    p->rchild=r;
    return p;

}

void visit(bitree bt)
{
    printf("%c ",bt->data);
}

void preorder(bitree bt)
{
    if(bt)
    {
        visit(bt);
        preorder(bt->lchild);
        preorder(bt->rchild);
    }
}

int main()
{
    bitree p,bt;
    printf("     ：");
    create(bt);
    p=copytree(bt);
    preorder(bt);
    printf("
");
    preorder(p);
    return 0;
}

24、アルゴリズムを作成し、2本の二叉木が形態が似ているかどうかを判断する.

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct tnode
{
    int data;
    struct tnode *lchild,*rchild;
}tnode,*bitree;

void create(bitree &t)
{
    char ch;
    scanf("%c",&ch);
    getchar();
    if(ch=='#')t=NULL;
    else
    {
        t=(tnode*)malloc(sizeof(tnode));
        t->data=ch;
        printf("   %c     ：",ch);
        create(t->lchild);
        printf("   %c     ：",ch);
        create(t->rchild);
    }
}

int similar(bitree t1,bitree t2)
{
    if(t1==NULL || t2==NULL)
    {
        return (t1==NULL)&&(t2==NULL);
    }
    return similar(t1->lchild,t2->lchild) && similar(t1->rchild,t2->rchild);
}


int main()
{
    bitree t,s;
    printf("         ：");
    create(t);
    printf("         ：");
    create(s);
    if(similar(t,s))printf("  ！");
    else printf("   !");
    return 0;
}

25、アルゴリズムを作成し、子供の兄弟表現で格納された木の高さを計算する.

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct tnode
{
    int data;
    struct tnode *child,*brother;
}tnode,*bitree;

void create(bitree &t)
{
    char ch;
    scanf("%c",&ch);
    getchar();
    if(ch == '#')t=NULL;
    else
    {
        t=(tnode*)malloc(sizeof(tnode));
        t->data=ch;
        printf("   %c      ：",ch);
        create(t->child);
        printf("   %c      ：",ch);
        create(t->brother);
    }
}

int max(int a,int b)
{
    if(a>b)return a;
    else return b;
}

int depth(bitree t)
{
    int i,j=0;
    if(!t)return 0;
    i=1+depth(t->child);
    j=depth(t->brother);
    return max(i,j);
}

int main()
{
    bitree t;
    printf("     ：");
    create(t);
    printf("the depth is : %d",depth(t));
    return 0;
}

26.折半検索の非再帰アルゴリズムを与える.

#include 
#include 
#include 
#include 
#include 
using namespace std;

int bin_search(int key[],int low,int high,int k)
{
    int mid;
    if(low>high)return -1;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(k==key[mid])return mid;
        else if(k>key[mid])low=mid+1;
        else high=mid-1;
    }
    return -1;
}

int main()
{
    int n,k,i;
    int a[10]={1,2,3,4,5,6,7,8,9,10};
    printf("input the number:");
    scanf("%d",&k);
    n=bin_search(a,0,9,k);
    if(n!=-1)printf("the position is:%d
",n+1);
    else printf("There is no %d in array a
",k);
    return 0;
}

27、折半検索の再帰アルゴリズムを与える.

#include 

int bin_search(int key[],int low,int high,int k)
{
    int mid;
    if(low>high)return -1;
    else
    {
        mid=(low+high)/2;
        if(k==key[mid])return mid;
        else if(k>key[mid])return bin_search(key,mid+1,high,k);
        else return bin_search(key,low,mid-1,k);
    }
}

int main()
{
    int n,k,i;
    int a[10]={1,2,3,4,5,6,7,8,9,10};
    printf("input the number:");
    scanf("%d",&k);
    n=bin_search(a,0,9,k);
    if(n!=-1)printf("the position is:%d
",n+1);
    else printf("There is no %d in array a
",k);
    return 0;
}

28.インデックス順序テーブルを与えるブロックルックアップアルゴリズム.

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define maxsize 255

typedef struct index
{
    int index;
    int start;
    int len;
}index,indexlist[maxsize];

typedef struct node
{
    int data;
}node,nodelist[maxsize];

int block(nodelist a,indexlist b,int l,int k)
{
    int i,j;
    int low=0,high=l-1;
    while(low<=high)
    {
        int mid = (low+high)/2;
        if(k==b[mid].index)
        {
            i=mid;
            break;
        }
        else if(k1;
        else
            low=mid+1;
    }
    if(low>high)i=low;
    if(i==l)return -1;
    j=b[i].start;
    while(jif(k==a[j].data)break;
        else j++;
    }
    if(jreturn j;
    else return -1;
}

int main()
{
    nodelist r;
    int k=14;
    indexlist I;
    int a[]={8,14,6,9,10,22,34,18,19,31,40,38,54,66,46};
    int i;
    for(i=0;i<15;i++)
    {
        r[i].data=a[i];
    }
    I[0].index=14;
    I[0].len=5;
    I[0].start=0;
    I[1].index=34;
    I[1].len=5;
    I[1].start=5;
    I[2].index=66;
    I[2].len=5;
    I[2].start=10;
    i=block(r,I,3,k);
    if(i!=-1)
        printf("%d
",i+1);
    else
        printf("-1
");

    return 0;
}

29、二叉ソートツリーの挿入アルゴリズムを与える.

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;

typedef struct tnode
{
    int data;
    struct tnode *lchild, *rchild;
} tnode, *bitree;

int searchtree(bitree t, int key, bitree &p, bitree &q)
{
    p = t;
    q = NULL;
    while (p && key != p->data)
    {
        q = p;
        if (p->data > key)
        {
            p = p->lchild;
        }
        else
        {
            p = p->rchild;
        }

    }
    if (p)
    {
        return 1;
    }
    else
    {
        return 0;
    }

}

int ins(bitree &t, int e)
{
    bitree p = NULL, f = NULL;
    if (searchtree(t, e, p, f))
    {
        return 0;
    }
    p = (tnode*)malloc(sizeof(tnode));
    p->data = e;
    p->lchild = NULL;
    p->rchild = NULL;
    if (!f)
    {
        t = p;
    }
    else if (f->data > e)
    {
        f->lchild = p;
    }
    else
    {
        f->rchild = p;
    }
    return 1;
}

void visit(bitree p)
{
    printf("%d ", p->data);
}
void inorder(bitree bt)
{
    if (bt)
    {
        inorder(bt->lchild);
        visit(bt);
        inorder(bt->rchild);
    }
}

int main()
{
    bitree bt = NULL;
    int data;
    printf("please input data:");
    scanf("%d", &data);
    while (data != -9999)
    {
        ins(bt, data);
        scanf("%d", &data);
    }
    inorder(bt);
    return 0;
}

30、二叉ソートツリーの削除アルゴリズムを与える.(あなたの木が二叉ソートツリーであることを前提とします)

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;

typedef struct tnode
{
    int data;
    struct tnode *lchild,*rchild;
}tnode,*bitree;

int searchtree(bitree t,int key,bitree &p,bitree &q)
{
    p=t;
    q=NULL;
    while(p && p->data!=key)
    {
        q=p;
        if(p->data>key)
            p=p->lchild;
        else
            p=p->rchild;
    }
    if(p)return 1;
    else return 0;
}

int del(bitree &t,int key)
{
    bitree p=NULL,f=NULL,c,s;
    if(!searchtree(t,key,p,f))
        return 0;
    if(!p->lchild)
    {
        if(!f)t=p->rchild;
        else if(f->data>key)f->lchild=p->rchild;
        else f->rchild=p->rchild;
    }
    else if(!p->rchild)
    {
        if(!f)t=p->lchild;
        else if(f->data>key)f->lchild=p->lchild;
        else f->rchild=p->rchild;
    }
    else
    {
        c=p->lchild;
        s=c;
        while(s->rchild)
        {
            s=s->rchild;
        }
        s->rchild=p->rchild;
        if(!f)t=c;
        else if(f->data>key)f->lchild=c;
        else f->rchild=c;

    }
    free(p);
    return 1;
}

int ins(bitree &t,int e)
{
    bitree p=NULL,f=NULL;
    if(searchtree(t,e,p,f))return 0;
    p=(tnode*)malloc(sizeof(tnode));
    p->data=e;
    p->lchild=NULL;
    p->rchild=NULL;
    if(!f)t=p;
    else if(f->data>e)f->lchild=p;
    else f->rchild=p;
    return 1;
}

void visit(bitree p)
{
        printf("%d ", p->data);
}

void inorder(bitree bt)
{
        if (bt)
        {
                inorder(bt->lchild);
                visit(bt);
                inorder(bt->rchild);
        }
}

int main()
{
    bitree bt = NULL;
    int data;
    printf("please input data:");
    scanf("%d", &data);
    while (data != -9999)
    {
        ins(bt, data);
        scanf("%d", &data);
    }
    inorder(bt);
    printf("
");
    del(bt, 3);
    printf("
");
    inorder(bt);
    return 0;
}

31.直接挿入ソートアルゴリズムを与える.

#include 

void simple_ins(int r[],int n)
{
    int i,j;
    for(i=2;i<=n;i++)
    {
        r[0]=r[i];
        for(j=i-1;r[j]>r[0];j--)
        {
            r[j+1]=r[j];
        }
        r[j+1]=r[0];
    }
}

int main()
{
    int a[10]={0,18,4,56,12,35,15,4,3,1};
    int i;
    simple_ins(a,9);
    for(i=1;i<=9;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

32、折半挿入並べ替えアルゴリズムを与える.

#include 

void bin_ins(int r[],int n)
{
    int low,high,mid;
    int i,j;
    for(i=2;i<=n;i++)
    {
        r[0]=r[i];
        low=1;
        high=i-1;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(r[0]>=r[mid])
                low=mid+1;
            else
                high=mid-1;
        }
        for(j=i-1;j>=high+1;j--)
            r[j+1]=r[j];
        r[j+1]=r[0];
    }
}

int main()
{
    int a[10]={0,18,4,56,12,35,15,4,3,1};
    int i;
    bin_ins(a,9);
    for(i=1;i<=9;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

33.SHELLソートアルゴリズムを与える.

#include 

void shell(int r[],int n)
{
    int i,j;
    int d=n/2;
    while(d)
    {
        for(i=1+d;i<=n;i=i+d)
        {
            r[0]=r[i];
            for(j=i-d;j>0 && r[j]>r[0];j=j-d)
            {
                r[j+d]=r[j];
            }
            r[j+d]=r[0];
        }
        d/=2;
    }
}

int main()
{
    int a[10]={0,43,4,6,12,59,15,9,3,1};
    int i;
    shell(a,9);
    for(i=1;i<=9;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

34、泡の順序付けアルゴリズムを与える.

#include 

void bubble(int r[],int n)
{
    int i,j,flag=1;
    for(i=1;flag && i0;
        for(j=1;j<=n-i;j++)
        {
            if(r[j]>r[j+1])
            {
                r[0]=r[j];
                r[j]=r[j+1];
                r[j+1]=r[0];
                flag=1;
            }
        }
    }
}

int main()
{
    int a[10]={0,103,-5,6,12,59,15,99,3,1};
    int i;
    bubble(a,9);
    for(i=1;i<=9;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

35、双方向バブルソートアルゴリズムを与える.

#include 

void newbubble(int a[],int n)
{
    int low,high,j,temp,r,l;
    low=1;
    high=n;
    while(low1;
        l=low+1;
        for(j=low;j
        {
            if(a[j]>a[j+1])
            {
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
                r=j;
            }
        }
        high=r;
        for(j=high;j>low;j--)
        {
            if(a[j-1]>a[j])
            {
                temp=a[j-1];
                a[j-1]=a[j];
                a[j]=temp;
                l=j;
            }
        }
        low=l;
    }
}

int main()
{
    int a[10]={0,103,-5,6,12,59,15,99,3,1};
    int i;
    newbubble(a,9);
    for(i=1;i<=9;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

36.高速ソートアルゴリズムを与える.

#include 

void quicksort(int r[],int left,int right)
{
    int i=left,j=right,temp=r[left];
    if(left<right)
    {
        while(iwhile(i=temp)
            {
                j--;
            }
            if(iwhile(iif(ileft,i-1);
        quicksort(r,i+1,right);
    }

}

int main()
{
    int a[10]={0,85,-7,46,12,1,6,99,13,10};
    int i;
    quicksort(a,1,9);
    for(i=1;i<=9;i++)
    {
        printf("%d ",a[i]);
    }

    return 0;
}

37、簡単な選択並べ替えアルゴリズムを与える.

#include 

void select_sort(int r[],int n)
{
    int i,j,pos;
    for(i=1;ipos=i;
        for(j=i+1;j<=n;j++)
        {
            if(r[j]pos])
            {
                pos=j;
            }
        }
        if(pos!=i)
        {
            r[0]=r[pos];
            r[pos]=r[i];
            r[i]=r[0];
        }
    }
}

int main()
{
    int a[10]={0,233,45,-6,12,9,15,73,23,6};
    int i;
    select_sort(a,9);
    for(i=1;i<=9;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

38.スタック並べ替えアルゴリズムを与える.

#include 

void heap_adjust(int r[],int low,int high)
{
    int i,j;
    r[0]=r[low];
    i=low;
    j=2*i;
    while(j<=high)
    {
        if(jr[j+1])
        {
            j++;
        }
        if(r[0]>r[j])
        {
            r[i]=r[j];
            i=j;
            j=2*i;
        }
        else
        {
            break;
        }
    }
    r[i]=r[0];
}

void heap(int r[],int n)
{
    int i,j;
    for(i=n/2;i>0;i--)
    {
        heap_adjust(r,i,n);
    }
    for(i=n;i>1;i--)
    {
        r[0]=r[1];
        r[1]=r[i];
        r[i]=r[0];
        heap_adjust(r,1,i-1);
    }
}

int main()
{
    int a[10]={0,73,45,-11,17,9,5,778,87,11};
    int i;
    heap(a,9);
    for(i=1;i<=9;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

39.集計ソートアルゴリズムが与えられる.

#include 
#include <string.h>
#include <string>
#include 
#include 

void merge(int r[],int r1[],int low,int mid,int high)
{
    int i=low,j=mid+1,k=low;
    while(i<=mid && j<=high)
    {
        if(r[i]<=r[j])
        {
            r1[k++]=r[i++];
        }
        else
        {
            r1[k++]=r[j++];
        }
    }
    while(i<=mid)
    {
        r1[k++]=r[i++];
    }
    while(j<=high)
    {
        r1[k++]=r[j++];
    }
}

void mergepass(int r[],int r1[],int len,int n)
{
    int i=1;
    while( i + 2*len - 1 <= n )
    {
        merge(r,r1,i,i+len-1,i+2*len-1);
        i += 2 * len;
    }
    if(i+len-1len-1,n);
    }
    else
    {
        while(i<=n)
        {
            r1[i]=r[i];
            i++;
        }
    }
}

void mergesort(int r[],int n)
{
    int *r1,len=1;
    r1=(int*)malloc((n+1)*sizeof(int));
    while(lenlen,n);
        len*=2;
        mergepass(r1,r,len,n);
        len*=2;
    }
}

int main()
{
    int a[10]={0,73,45,-11,17,9,5,778,87,6};
    int i;
    mergesort(a,9);
    for(i=1;i<=9;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

pythonインポートjsonパッケージjsonで発生した問題を解析

アルゴリズムコンテスト入門経典java実現第一章--言語入門編