|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
线性索引查找:
当数据不是以顺序的方式存储时,我们无法对数据进行二分查找等高效的查找方式,所以我们采用了线性索引查找
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");
- }
复制代码 |
评分
-
查看全部评分
|