#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int a[100];//有序表,默认为递增
int length;//有序表长度
void Creat_Sqlist(){
   scanf("%d",&length);
   for(int i=0;i<length;i++){
    scanf("%d",&a[i]);
   }
}
int Binary_Search(int key){
  int low=0,high=length-1,mid;
  while(low<=high){
   mid=(low+high)/2;
   if(a[mid]==key)
     return 1;
   else if(a[mid]>key)
   high=mid-1;
   else
   low=mid+1;
  }
 return 0;
}
//二叉树的声明
struct BiNode{
  int data;
  struct BiNode *lchild,*rchild;
};

struct BiNode *p=NULL;
//T指向该二叉树，key表示关键字,f指向T的双亲,p指向当前节点
int SearchBST(BiNode *T,int key,BiNode *f,BiNode *&p){//查找
   if(T==NULL)
   {
   p=f;
   return 0;
   }
   else if(key==T->data)
   {
   p=T;
   return 1;
   }
   else if(key<T->data)
   return SearchBST(T->lchild,key,T,p);
   else
   return SearchBST(T->rchild,key,T,p);
}

void InsertBST(BiNode *&T,int e){//插入
   if(SearchBST(T,e,NULL,p)==0)
   {
   struct BiNode *s=(BiNode *)malloc(sizeof(BiNode));
   s->data=http://www.mamicode.com/e;
   s->lchild=s->rchild=NULL;
   if(p==NULL)
   T=s;
   else if(e<p->data)
   p->lchild=s;
   else
   p->rchild=s;
   }
}

void Delete(BiNode *&p){
  if(p->rchild==NULL){
   struct BiNode *q;
   q=p;
   p=p->lchild;
   free(q);
  }
  else if(p->lchild==NULL)
  {
   struct BiNode *q;
   q=p;
   p=p->rchild;
   free(q);
  }
  else{
  struct BiNode *q,*s;
  q=p;
  s=p->lchild;
  while(s->rchild){
   q=s;
   s=s->rchild;
  }
  p->data=http://www.mamicode.com/s->data;
  if(q!=p)
  q->rchild=s->lchild;
  else
  q->lchild=s->lchild;
  free(s);
  }
}

void DeleteBST(BiNode *&T,int key){//节点的删除操作
  if(T==NULL)
   return ;
  else
  {
   if(key==T->data)
   Delete(T);
   else if(key<T->data)
   DeleteBST(T->lchild,key);
   else
   DeleteBST(T->rchild,key);
  }
}
//二叉排序树的中序遍历
void InOrderTravel(BiNode *T){
   if(T){
    InOrderTravel(T->lchild);
    printf("%d ",T->data);
    InOrderTravel(T->rchild);
   }
}

int main()
{
    int key;
    printf("请输入有序表的长度以及各元素的值\n");
    Creat_Sqlist();
    printf("请输入要查找的关键字\n");
    scanf("%d",&key);
    if(Binary_Search(key))
    printf("找到该元素\n");
    else
    printf("未找到该元素\n");


    struct BiNode *T=NULL;//二叉树的初始节点
    int data[10];//数组data表示随机产生的一组关键字
     printf("产生的随机关键字\n");
    for(int i=0;i<10;i++)
    {
      data[i]=rand()%1000+1;
      printf("%d ",data[i]);
    }
    for(int i=0;i<10;i++)//建立二叉排序树
      InsertBST(T,data[i]);
    printf("\n");
    printf("输出该二叉排序树的中序遍历\n");
    InOrderTravel(T);
    printf("\n");
    printf("请输入要删除的关键字\n");
    scanf("%d",&key);
    DeleteBST(T,key);
    printf("输出删除节点后该二叉排序树的中序遍历\n");
    InOrderTravel(T);
    return 0;
}

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define N 13

struct SqList{
 int a[100];//用来建立哈希表
 int length;
};

struct node{
  int data;
  struct node *next;
};
struct node *Hash[N];

//哈希函数
int Hash_Func(int key){
  return key%N;
}

void Creat_Hash_Table(struct SqList T){//拉链法建立的哈希表
  int pos;
  struct node *p,*tmp;
  for(int i=0;i<=N-1;i++){//表头的初始化
   Hash[i]=(struct node *)malloc(sizeof(struct node));
   Hash[i]->next=NULL;
  }
  for(int i=0;i<=T.length-1;i++){
   pos=Hash_Func(T.a[i]);
   p=(struct node *)malloc(sizeof(struct node));
   p->data=http://www.mamicode.com/T.a[i];
   p->next=NULL;
   if(Hash[pos]->next==NULL)//新节点的插入
   Hash[pos]->next=p;
   else{
   tmp=Hash[pos];
   while(tmp->next){
    tmp=tmp->next;
   }
   tmp->next=p;
   }
  }
}

void Travel_Hash_Table(){//遍历该哈希表
   struct node *tmp;
  for(int i=0;i<=N-1;i++){
    tmp=Hash[i];
   while(tmp->next){
    printf("%d ",tmp->next->data);
    tmp=tmp->next;
   }
  }
  printf("\n");
}

//线性探测法建立哈希表
struct exnode{
   int flag;//标记该位置是否被占用
   int data;
}HashTable[N];

int d[N];//增量数组

void CreatHashTable(struct SqList T){
  int pos;
  int j;
  for(int i=0;i<N;i++){//增量数组的初始化
   d[i]=i+1;
  }
  for(int i=0;i<N;i++){//哈希表元素标志位的初始化
  HashTable[i].flag=0;//0表示未使用
  HashTable[i].data=http://www.mamicode.com/0;
  }
  for(int i=0;i<=T.length-1;i++){
   pos=Hash_Func(T.a[i]);
   if(HashTable[pos].flag==0){
    HashTable[pos].data=T.a[i];
    HashTable[pos].flag=1;
   }
   else{
   j=0;
   int tmp=pos;//冲突的处理,pos=(pos+d[j])%N这样写是错误的，如果这样写pos每次都会被更新，因此需要额外定义一个tmp
   while(HashTable[tmp].flag!=0){
   tmp=(pos+d[j])%N;
   j++;
   }
    HashTable[tmp].data=T.a[i];
    HashTable[tmp].flag=1;
   }
  }
}

//输出该哈希表
void TravelHashTable(){
  for(int i=0;i<=N-1;i++){
    printf("%d ",HashTable[i].data);
  }
  printf("\n");
}


int main()
{
    struct SqList  s;
    printf("输入节点个数\n");
    scanf("%d",&s.length);
    printf("各节点的值由随机函数产生\n");
    for(int i=0;i<=s.length-1;i++){
     s.a[i]=rand()%20+1;
    }
    printf("输出每个节点的随机值\n");
    for(int i=0;i<=s.length-1;i++){
      printf("%d ",s.a[i]);
    }
    printf("\n");
    printf("拉链法建立哈希表并输出每个节点的值\n");
    Creat_Hash_Table(s);
    Travel_Hash_Table();



    printf("输入节点个数,节点个数不能超过N\n");
    scanf("%d",&s.length);
    printf("各节点的值由随机函数产生\n");
    for(int i=0;i<=s.length-1;i++){
     s.a[i]=rand()%20+1;
    }
    printf("输出每个节点的随机值\n");
    for(int i=0;i<=s.length-1;i++){
      printf("%d ",s.a[i]);
    }
    printf("\n");
    printf("线性探测法建立哈希表并输出每个节点的值\n");
    CreatHashTable(s);
    TravelHashTable();
    return 0;
}