鱼C论坛

 找回密码
 立即注册
查看: 2648|回复: 0

[学习笔记] 《数据结构和算法》——线性查找和二叉排序树

[复制链接]
发表于 2017-8-24 16:23:21 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
线性索引查找:
当数据不是以顺序的方式存储时,我们无法对数据进行二分查找等高效的查找方式,所以我们采用了线性索引查找
1)稠密索引查找:对于数据量不是特别大的,我们可以对数据建立一个一一对应的索引表,我们多索引表进行排序后,我们就可以对索引表进行二分查找等较为高效的算法。
2)分块索引:将无序的数据分成多个小块,每个小块可以取一个特征量作为标志,如该块数据中的最大值,使块内数据无序,但是块间有序排列。我们可以对块进行高效查找,对块内进行顺序查找
3)倒排索引:将多个数据的关键字提取后,建立索引表,储存关键字出现的位置

二叉排序树:
对于乱序的数据,我们易于插入和删除,但是不易于查找,而二叉排序树则成功的做到了兼顾二者。我们首先选择一个根节点,创建时,我们使所有左子树上的节点小于根节点,使所有右子树上的节点大于根节点,即在储存数组时,把较根节点小的放在左子树上,较根节点大的放在右子树上。
1)查找:我们从根节点开始,不断地和目标数据进行比较,当节点数据小于目标数据时,再比较节点的右子树的数据和目标数据,反之则比较节点的左子树的数据和目标数据,直至找到或者节点的左子树或右子树为空,我们利用指针来储存位置,返回0和1来表示是否找到目标数据的位置
2)添加:从根节点开始,不断地将目标数据和节点数据进行比较,若目标数据较大,则移动指针至其右子树,反之则移动到其的左子树,直至节点左或右子树为空,将目标元素赋值到节点的左或右子树
3)删除:删除时除了被删除数据的删除,还需要将被删除节点的新数据进行补充;此时分为三个情况,当被删除节点为叶子时,直接删除该节点;当被删除节点只有左(右)子树时,将其左(右)子树连在该节点前驱;当被删除节点有左右子树时,我们用该节点的直接后继(左子树的最右边的叶子节点)去替换该节点,删除其直接后继。

附上二叉排序树的代码
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<iostream>
  4. using namespace std;

  5. class node
  6. {
  7. public:
  8.         int data;
  9.         node *lchild = NULL, *rchild = NULL;
  10. };
  11. void Input(node *&r)
  12. {
  13.         int n;
  14.         node *cp=NULL;
  15.         cout << "input the numbers(end with -1):" << endl;
  16.         cin >> n;
  17.         while (n != -1)
  18.         {
  19.                 if (r == NULL)
  20.                 {
  21.                         r = new node;
  22.                         cp = r;
  23.                 }
  24.                 else
  25.                 {
  26.                         cp = r;
  27.                         while (1)
  28.                         {
  29.                                 if (n < cp->data)
  30.                                 {
  31.                                         if (cp->lchild == NULL)
  32.                                         {
  33.                                                 cp->lchild = new node;
  34.                                                 cp = cp->lchild;
  35.                                                 break;
  36.                                         }
  37.                                         cp = cp->lchild;
  38.                                 }
  39.                                 else
  40.                                 {
  41.                                         if (cp->rchild == NULL)
  42.                                         {
  43.                                                 cp->rchild = new node;
  44.                                                 cp = cp->rchild;
  45.                                                 break;
  46.                                         }
  47.                                         cp = cp->rchild;
  48.                                 }
  49.                         }
  50.                 }
  51.                 cp->data = n;
  52.                 cin >> n;
  53.         }
  54. }

  55. void AddNode(node *r)
  56. {
  57.         int key;
  58.         cout << "input the number:";
  59.         cin >> key;
  60.         node *cp = r,*np=NULL;
  61.         if (r == NULL)
  62.         {
  63.                 cout << "wrong,no root" << endl;
  64.         }
  65.         while (1)
  66.         {
  67.                 if (key >= cp->data)
  68.                 {
  69.                         if (cp->rchild == NULL)
  70.                         {
  71.                                 cp->rchild = new node;
  72.                                 cp->rchild->data = key;
  73.                                 return;
  74.                         }
  75.                         cp = cp->rchild;
  76.                 }
  77.                 else
  78.                 {
  79.                         if (cp->lchild == NULL)
  80.                         {
  81.                                 cp->lchild = new node;
  82.                                 cp->lchild->data = key;
  83.                                 return;
  84.                         }
  85.                         cp = cp->lchild;
  86.                 }
  87.         }
  88.        
  89.        

  90. }

  91. void FindNode(node *r)
  92. {
  93.         int key;
  94.         cout << "input the number:";
  95.         cin >> key;
  96.         node *cp = r;
  97.         int flag = 0;
  98.         while (cp != NULL)
  99.         {
  100.                 if (cp->data == key)
  101.                 {
  102.                         flag = 1;
  103.                         break;
  104.                 }
  105.                 if (key < cp->data)
  106.                 {
  107.                         cp = cp->lchild;
  108.                 }
  109.                 else
  110.                 {
  111.                         cp = cp->rchild;
  112.                 }
  113.         }
  114.         if (!flag)
  115.         {
  116.                 cout << "No such number" << endl;
  117.         }
  118.         else
  119.         {
  120.                 cout << "YES" << endl;
  121.         }
  122. }

  123. void DeleteNode2(node *p,node *pp,int dir)
  124. {
  125.         node *cp = p;

  126.         if (cp->lchild == NULL)
  127.         {
  128.                 if (dir)
  129.                 {
  130.                         pp->rchild = cp->rchild;
  131.                 }
  132.                 else
  133.                 {
  134.                         pp->lchild = cp->rchild;
  135.                 }
  136.         }
  137.     else if (cp->rchild == NULL)
  138.         {
  139.                 if (dir)
  140.                 {
  141.                         pp->rchild = cp->lchild;
  142.                 }
  143.                 else
  144.                 {
  145.                         pp->lchild = cp->lchild;
  146.                 }
  147.         }
  148.         else
  149.         {
  150.                 pp = cp;
  151.                 cp = cp->lchild;
  152.                 while (cp->rchild != NULL)
  153.                 {
  154.                         pp = cp;
  155.                         cp = cp->rchild;
  156.                 }
  157.                 node *d = NULL;
  158.                 p->data = cp->data;
  159.                 if (pp != p)
  160.                 {
  161.                         pp->rchild = cp->lchild;
  162.                         d = cp;
  163.                 }
  164.                 else
  165.                 {
  166.                         pp->lchild = NULL;
  167.                         d = cp;
  168.                 }

  169.                 delete d;
  170.                
  171.         }

  172. }

  173. void DeleteNode1(node *r)
  174. {
  175.         node *cp = r,*pp=r;
  176.         int flag = 1,key;
  177.         cout << "input the delete number:";
  178.         cin >> key;
  179.         int dir = 0;
  180.         while (cp != NULL)
  181.         {
  182.                 if (cp->data == key)
  183.                 {
  184.                         DeleteNode2(cp,pp,dir);
  185.                         break;
  186.                 }
  187.                 if (key < cp->data)
  188.                 {
  189.                         dir = 0;
  190.                         pp = cp;
  191.                         cp = cp->lchild;
  192.                 }
  193.                 else
  194.                 {
  195.                         dir = 1;
  196.                         pp = cp;
  197.                         cp = cp->rchild;
  198.                 }
  199.         }
  200. }

  201. void print(node *cp)
  202. {
  203.         if (cp == NULL)
  204.         {
  205.                 return;
  206.         }
  207.         cout << cp->data << " ";
  208.         if (cp->lchild != NULL)
  209.         {
  210.                 print(cp->lchild);
  211.         }
  212.         if (cp->rchild != NULL)
  213.         {
  214.                 print(cp->rchild);
  215.         }

  216. }

  217. int main()
  218. {
  219.         node *r=NULL,*cp=NULL;
  220.         Input(r);//输入无序数据
  221.         int choice = 1;
  222.         cout << "1——>添加数据" << endl << "2——>删除数据" <<  endl << "3——>查找数据" <<endl<<"4——>打印数据表"<< endl;
  223.         while (choice)
  224.         {
  225.                 cout << "input your choice:";
  226.                 cin >> choice;
  227.                 switch (choice)
  228.                 {
  229.                 case 1:
  230.                         AddNode(r);
  231.                         break;
  232.                 case 2:
  233.                         DeleteNode1(r);
  234.                         break;
  235.                 case 3:
  236.                         FindNode(r);
  237.                         break;
  238.                 case 4:
  239.                         cout << "the number is:";
  240.                         print(r);
  241.                         cout << endl;
  242.                         break;
  243.                 case 0:
  244.                         break;
  245.                 default:
  246.                         cout << "Wrong Input!" << endl;
  247.                         break;

  248.                 }
  249.         }

  250.         system("PAUSE");
  251. }
复制代码

评分

参与人数 1鱼币 +2 收起 理由
小甲鱼 + 2

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 03:39

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表