9.29

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int id;
    int data;
    Node* next; 
};
Node* CreatList(){
    Node *head=new Node;
    Node *tail=head;
    int num=0;
    cin>>head->data;
    head->id=num++;
    int data;
    while(cin>>data){
        if(data==-1) break;
        Node *p=new Node;
        p->data=data;
        p->id=num++;
        p->next=NULL;
        tail->next=p;
        tail=p;
    }
    tail->next=head;
    return head;
}
void ShowList(Node *head){
    cout<<head->id<<' '<<head->data<<endl;
    Node *p=head->next;
    while(p!=head){
        cout<<p->id<<' '<<p->data<<endl;
        p=p->next;
    }
}
Node* Search(Node *head,Node *tail,int key){
    Node *p=head;
    while(p!=tail){
        if(p->data==key) break;
        p=p->next;
    }
    return p;
}
void Solve(Node* h){
    int key;
    Node* t=h;
    while(cin>>key){
        if(key>t->data) t=Search(t->next,h,key);
        else if(key<t->data) t=Search(h,t,key);
        cout<<t->id<<' ';
    }
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    Node *h=CreatList();
    ShowList(h);
    putchar(10);
    Solve(h);
    return 0;
}

9.31 判断一棵二叉树是不是二叉排序树。

...
int pre;
bool res=1;
void isBST(Node *root){
    if(!root) return;
    isBST(root->lchild);
    if(root->key<pre) res=0;
    pre=root->key;
    isBST(root->rchild);
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    Node *root=CreatTree();
    Node *p=root;
    while(p->lchild) p=p->lchild;
    pre=p->key;
    isBST(root);
    cout<<res;
    return 0;
}

9.45

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int key;
    Node *next;
};
Node *Hash[100];
int m;
int H(int x){return x%m;}
void CreatHash(){
    int key;
    while(cin>>key){
        int h=H(key);
        Node *p=new Node;
        p->key=key;
        if(!Hash[h]){
            Hash[h]=new Node;
            Hash[h]->next=NULL;
        }
        p->next=Hash[h]->next;
        Hash[h]->next=p;
    }
}
void ShowHash(){
    for(int i=0;i<m;i++){
        cout<<i<<' ';
        Node *p=Hash[i]->next;
        while(p){
            cout<<p->key<<' ';
            p=p->next;
        }
        putchar(10);
    }
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    cin>>m;
    CreatHash();
    ShowHash();
    return 0;
}