[NEFU]銳格 資料結構 作業

1.6109

#include <bits/stdc++.h>

using namespace std;

    typedef struct node{

        int data;

        struct node *next;

    }LNode,*LinkList;

    void creat(LNode *h)

    {

        h->next=NULL;

        LNode *r;

        r=h;

        LNode *p;

        int n;

        while(cin>>n){

            if(n==0) break;

            p=(LNode *)malloc(sizeof(LNode));

            p->data=n;

            p->next=r->next;

            r->next=p;

            r=p;

        }

    }

    void HB(LinkList &h1,LinkList &h2)

    {

        LNode *p1,*p2,*p3,*q;

        p1=h1->next;

        p2=h2->next;

        p3=h1;

        while(p1&&p2)

        {

            if(p1->data<p2->data)

            {

                p3->next=p1;

                p3=p1;

                p1=p1->next;

            }

            else if(p1->data>p2->data)

            {

                p3->next=p2;

                p3=p2;

                p2=p2->next;

            }

            else

            {

                p3->next=p1;

                p3=p1;

                p1=p1->next;

                q=p2->next;

                p2=q;

            }

        }

        //p3->next=p1?p1:p2;

        if(p1!=NULL){

            p3->next=p1;

        }

        else{

            p3->next=p2;

        }

    }

int main()

{

    LNode *h1,*h2;

    h1=(LNode *)malloc(sizeof(LNode));

    h2=(LNode *)malloc(sizeof(LNode));

    creat(h1);

    creat(h2);

    HB(h1,h2);

    LNode *p;

    p=h1->next;

    while(p!=NULL)

    {

        cout<<p->data<<' ';

        p=p->next;

    }

    delete h1,p;

    return 0;

}

2.6110

#include <bits/stdc++.h>

using namespace std;

const int N =1e4+10;

int main(){

    char s[N];

    stack<char> a;

    cin>>s;

    int m;

    int l=strlen(s);

    for(int i=0;i<l;i++)

    {

       if(s[i]=='('||s[i]=='['||s[i]=='{')

       {

           a.push(s[i]);

       }

       if(s[i]==']'){

           if(a.empty()||a.top()!='['){

               m=1;

               break;

           }

           else a.pop();

       }

       if(s[i]=='}'){

           if(a.empty()||a.top()!='{'){

               m=1;

               break;

           }

           else a.pop();

       }

       if(s[i]==')'){

           if(a.empty()||a.top()!='('){

               m=1;

               break;

           }

           else a.pop();

       }

    }

    if(!a.empty()){

        m=1;

    }

    if(m==1) cout<<'0';

    else cout<<'1';

    return 0;

}     

3.6111

#include <bits/stdc++.h>

using namespace std;

int u=0;

int y=0;

typedef struct node{

    char data;

    struct node *lchild;

    struct node *rchild;

}Tree,*BiTree;

void CREAT(Tree* &T){

    char c;

    cin>>c;

    if(c=='*') T=NULL;

    else{

        T=new Tree;

        T->data=c;

        CREAT(T->lchild);

        CREAT(T->rchild);

    }

}

void visit(BiTree b){

    cout<<b->data<<' ';

    u++;

}

void panduan(BiTree T,char ch){

    if(T->data==ch){

        y=2;

    }

}

int FIND(BiTree T,char x){

    if(!T) return 0;

    if(T->data==x){

        return 1;

    }

    if(FIND(T->lchild,x)||FIND(T->rchild,x)){

        visit(T);

        return 1;

    }

    else return 0;

}

int main(){

    BiTree t;

    CREAT(t);

    char ch;

    cin>>ch;

    panduan(t,ch);

    if(y==2) cout<<"沒有祖先結點";

    else {

    FIND(t,ch);

    if(u==0) cout<<ch<<"不存在";}

    return 0;

}

4.6112

#include <bits/stdc++.h>

using namespace std;

const int N=1e2+10;

int visted[N];

struct mg{

    int v[N];

    int ar[N][N];

};

void creat(mg &g,int n,int m){

    int p,o;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

            g.ar[i][j]=0;

        }

    }

    for(int i=1;i<=m;i++)

    {

        scanf("%d,%d",&p,&o);

        g.ar[p][o]=1;

    }

}

void dfs(mg &g,int i,int n){

    visted[i]=1;

    for(int j=i;j<=n;j++){

        if(visted[j]==0&&g.ar[i][j]){

            dfs(g,j,n);

        }

    }

}

int main(){

    mg g;

    int n,m;

    cin>>n>>m;

    creat(g,n,m);

    int j,k;

    cin>>j>>k;

    dfs(g,j,n);

    if(visted[k]==0) cout<<'0';

    else cout<<'1';

    return 0;

}

5.6114

#include <bits/stdc++.h>

using namespace std;

#define m 15

struct HashTable{

    int key;

};

void creatHash(HashTable HT[]);

void print(HashTable HT[]);

int main(){

    HashTable HT[m];

    creatHash(HT);

    print(HT);

    return 0;

}

void creatHash(HashTable HT[]){

    int hash_table[m];

    int n=0;

    while(cin>>hash_table[n]){

        if(hash_table[n]==0){

        break;

    }

    n++;

}

    int temp;

    for(int i=0;i<m;i++){

        HT[i].key=-1;

    }

    for(int i=0;i<n;i++){

        temp=hash_table[i] % 13;

        if(HT[temp].key==-1){

            HT[temp].key=hash_table[i];

        }

        else {

            int flag=0;

            for(int j=temp+1;j<m;j++){

                if(HT[j].key==-1){

                    HT[j].key=hash_table[i];

                    flag=1;

                    break;

                }

            }

            if(flag==0){

                for(int j=0;j<temp;j++){

                    if(HT[j].key==-1){

                        HT[j].key=hash_table[i];

                        break;

                    }

                }

            }

        }

    }

}

void print(HashTable HT[]){

    for(int i=0;i<m;i++){

        cout<<i<<' '<<HT[i].key<<endl;

    }

}