《数据结构和算法》——线性查找和二叉排序树
线性索引查找：当数据不是以顺序的方式存储时，我们无法对数据进行二分查找等高效的查找方式，所以我们采用了线性索引查找
1)稠密索引查找：对于数据量不是特别大的，我们可以对数据建立一个一一对应的索引表，我们多索引表进行排序后，我们就可以对索引表进行二分查找等较为高效的算法。
2)分块索引：将无序的数据分成多个小块，每个小块可以取一个特征量作为标志，如该块数据中的最大值，使块内数据无序，但是块间有序排列。我们可以对块进行高效查找，对块内进行顺序查找
3)倒排索引：将多个数据的关键字提取后，建立索引表，储存关键字出现的位置
二叉排序树：
对于乱序的数据，我们易于插入和删除，但是不易于查找，而二叉排序树则成功的做到了兼顾二者。我们首先选择一个根节点，创建时，我们使所有左子树上的节点小于根节点，使所有右子树上的节点大于根节点，即在储存数组时，把较根节点小的放在左子树上，较根节点大的放在右子树上。
1)查找：我们从根节点开始，不断地和目标数据进行比较，当节点数据小于目标数据时，再比较节点的右子树的数据和目标数据，反之则比较节点的左子树的数据和目标数据，直至找到或者节点的左子树或右子树为空，我们利用指针来储存位置，返回0和1来表示是否找到目标数据的位置
2)添加：从根节点开始，不断地将目标数据和节点数据进行比较，若目标数据较大，则移动指针至其右子树，反之则移动到其的左子树，直至节点左或右子树为空，将目标元素赋值到节点的左或右子树
3)删除：删除时除了被删除数据的删除，还需要将被删除节点的新数据进行补充；此时分为三个情况，当被删除节点为叶子时，直接删除该节点；当被删除节点只有左（右）子树时，将其左（右）子树连在该节点前驱；当被删除节点有左右子树时，我们用该节点的直接后继（左子树的最右边的叶子节点）去替换该节点，删除其直接后继。
附上二叉排序树的代码#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
class node
{
public:
int data;
node *lchild = NULL, *rchild = NULL;
};
void Input(node *&r)
{
int n;
node *cp=NULL;
cout << "input the numbers(end with -1):" << endl;
cin >> n;
while (n != -1)
{
if (r == NULL)
{
r = new node;
cp = r;
}
else
{
cp = r;
while (1)
{
if (n < cp->data)
{
if (cp->lchild == NULL)
{
cp->lchild = new node;
cp = cp->lchild;
break;
}
cp = cp->lchild;
}
else
{
if (cp->rchild == NULL)
{
cp->rchild = new node;
cp = cp->rchild;
break;
}
cp = cp->rchild;
}
}
}
cp->data = n;
cin >> n;
}
}
void AddNode(node *r)
{
int key;
cout << "input the number:";
cin >> key;
node *cp = r,*np=NULL;
if (r == NULL)
{
cout << "wrong,no root" << endl;
}
while (1)
{
if (key >= cp->data)
{
if (cp->rchild == NULL)
{
cp->rchild = new node;
cp->rchild->data = key;
return;
}
cp = cp->rchild;
}
else
{
if (cp->lchild == NULL)
{
cp->lchild = new node;
cp->lchild->data = key;
return;
}
cp = cp->lchild;
}
}
}
void FindNode(node *r)
{
int key;
cout << "input the number:";
cin >> key;
node *cp = r;
int flag = 0;
while (cp != NULL)
{
if (cp->data == key)
{
flag = 1;
break;
}
if (key < cp->data)
{
cp = cp->lchild;
}
else
{
cp = cp->rchild;
}
}
if (!flag)
{
cout << "No such number" << endl;
}
else
{
cout << "YES" << endl;
}
}
void DeleteNode2(node *p,node *pp,int dir)
{
node *cp = p;
if (cp->lchild == NULL)
{
if (dir)
{
pp->rchild = cp->rchild;
}
else
{
pp->lchild = cp->rchild;
}
}
else if (cp->rchild == NULL)
{
if (dir)
{
pp->rchild = cp->lchild;
}
else
{
pp->lchild = cp->lchild;
}
}
else
{
pp = cp;
cp = cp->lchild;
while (cp->rchild != NULL)
{
pp = cp;
cp = cp->rchild;
}
node *d = NULL;
p->data = cp->data;
if (pp != p)
{
pp->rchild = cp->lchild;
d = cp;
}
else
{
pp->lchild = NULL;
d = cp;
}
delete d;
}
}
void DeleteNode1(node *r)
{
node *cp = r,*pp=r;
int flag = 1,key;
cout << "input the delete number:";
cin >> key;
int dir = 0;
while (cp != NULL)
{
if (cp->data == key)
{
DeleteNode2(cp,pp,dir);
break;
}
if (key < cp->data)
{
dir = 0;
pp = cp;
cp = cp->lchild;
}
else
{
dir = 1;
pp = cp;
cp = cp->rchild;
}
}
}
void print(node *cp)
{
if (cp == NULL)
{
return;
}
cout << cp->data << " ";
if (cp->lchild != NULL)
{
print(cp->lchild);
}
if (cp->rchild != NULL)
{
print(cp->rchild);
}
}
int main()
{
node *r=NULL,*cp=NULL;
Input(r);//输入无序数据
int choice = 1;
cout << "1——>添加数据" << endl << "2——>删除数据" <<endl << "3——>查找数据" <<endl<<"4——>打印数据表"<< endl;
while (choice)
{
cout << "input your choice:";
cin >> choice;
switch (choice)
{
case 1:
AddNode(r);
break;
case 2:
DeleteNode1(r);
break;
case 3:
FindNode(r);
break;
case 4:
cout << "the number is:";
print(r);
cout << endl;
break;
case 0:
break;
default:
cout << "Wrong Input!" << endl;
break;
}
}
system("PAUSE");
}
页:
[1]