二分查找 && 利用二分查找插入
#include <stdio.h>
#define MAX 100
typedef struct{
int key;
}Node;
typedef Node SeqList[MAX+1];
//递归二分查找
int binSearch1(SeqList R, int k, int low, int high){
int mid;
if(low <= high){
mid = (low+high)/2;
if(R[mid].key == k)
return mid;
if(R[mid].key > k)
return binSearch1(R, k, low, mid-1);
else
return binSearch1(R, k, mid+1, high);
}
return 0;
}
//非递归查找
int binSearch2(SeqList R, int k, int low, int high){
int mid;
while(low <= high){
mid = (low+high)/2;
if(R[mid].key == k)
return mid;
if(R[mid].key > k)
high = mid-1;
else
low = mid+1;
}
return 0;
}
//插入
void binInsert(SeqList R, int n, int k){
int low=1, high=n,find=0, mid;
while(low<=high && !find){
mid = (low+high)/2;
if(R[mid].key == k){
find = mid;
break;
}
if(R[mid].key > k)
high = mid - 1;
else
low = mid + 1;
}
if(!find)
find = low;
for(int i=n; i>=find; i--){
R[i+1] = R[i];
}
R[find].key = k;
}
int main(){
SeqList R;
int t;
int n = 0;
int i;
while (1==1) {
scanf("%d", &t);
if(t == -9999)
break;
n++;
R[n].key = t;
}
i = binSearch1(R, 5, 1, n);
printf("%d\n", i);
binInsert(R, n, 5);
for(int j=1; j<=n+1; j++){
printf("%d->", R[j].key);
}
return 0;
}
二叉排序树
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int data;
struct Node \*lchild;
struct Node \*rchild;
}BSNode;
typedef BSNode \*BSTree;
BSTree insertBSTree(BSTree bst, int k){
if(bst == NULL){
bst = (BSNode \*)malloc(sizeof(BSNode));
bst->data = k;
bst->lchild = NULL;
bst->rchild = NULL;
}
BSTree lc;
BSTree rc;
if(k < bst->data){
lc = insertBSTree(bst->lchild, k);
bst->lchild = lc;
}
else if(k > bst->data){
rc = insertBSTree(bst->rchild, k);
bst->rchild = rc;
}
return bst;
}
void interOder(BSTree bst){
if(bst){
interOder(bst->lchild);
printf("%d->", bst->data);
interOder(bst->rchild);
}
}
int main(){
BSTree bst = NULL;
int t;
scanf("%d", &t);
while (t != -9999) {
bst = insertBSTree(bst, t);
scanf("%d", &t);
}
interOder(bst);
printf("\n");
return 0;
}
并判断第n个整数在前（n-1）个整数中出现的次数
#include<stdio.h>
#define MAX 100
int main(){
int a[MAX];
int i=0, n, t;
while(1==1){
scanf("%d ", &t);
if(t == -9999){
break;
}
i++;
a[i] = t;
};
for(int j=1; j<i; j++){
if(a[j] == a[i])
n++;
}
printf("第n个整数在前n-1个数中出现的次数为：%d\n", n);
return 0;
}