数据结构拾遗—

数据结构拾遗——查找

这一章内容好多，总结了好久

 1 #pragma once
 2 #include <vector>
 3 using namespace std;
 4 template <class T>
 5 int SequentialSearch(const vector<T> &v, T key) {
 6     int answer = 0;
 7     for (auto i : v)
 8     {
 9         if (key == i)
10             break;
11         answer++;
12     }
13     return answer;
14 }

 1 #pragma once
 2 #pragma once
 3 #include <vector>
 4 using namespace std;
 5 
 6 template <class T>
 7 int compareT(T t1,T t2) {
 8     if (t1 == t2)
 9         return 0;
10     else
11     {
12         if (t1 < t2)
13             return -1;
14         else
15             return 1;
16     }
17 }
18 template <class T>
19 int BinarySearch(const vector<T> &v, T key) {
20     int low = 0, high = v.size() - 1, mid;
21     while (low <= high)
22     {
23         mid = (low + high) / 2;
24         switch (compareT(key,v[mid]))
25         {
26         case 0:
27             return mid;
28         case 1:
29             low = mid + 1;
30             break;
31         case -1:
32             high = mid - 1;
33             break;
34         }
35     }
36     return v.size();
37 }

 1 template <class T>
 2 int InterpolationSearch(const vector<T> &v, T key) {
 3     int low = 0, high = v.size() - 1, mid;
 4     while (low <= high)
 5     {
 6         mid = low + (key - v[low]) / (v[high] - v[low])*(high-low);
 7         switch (compareT(key, v[mid]))
 8         {
 9         case 0:
10             return mid;
11         case 1:
12             low = mid + 1;
13             break;
14         case -1:
15             high = mid - 1;
16             break;
17         }
18     }
19     return v.size();
20 }

 1 #pragma once
 2 #include <iostream>
 3 using namespace std;
 4 
 5 struct BiTNode
 6 {
 7     int data;
 8     struct BiTNode *lchild, *rchild;
 9 };
10 
11 
12 void MiddleRoot(const BiTNode const *T) {
13     if (T)
14     {
15         if (T->lchild)
16             MiddleRoot(T->lchild);
17 
18         cout << T->data << " ";
19 
20         if (T->rchild)
21             MiddleRoot(T->rchild);
22     }
23 }
24 
25 void FirstRoot(const BiTNode const *T) {
26     if (T)
27     {
28         cout << T->data << " ";
29 
30         if (T->lchild)
31             FirstRoot(T->lchild);
32 
33         if (T->rchild)
34             FirstRoot(T->rchild);
35     }
36 }
37 
38 void LastRoot(const BiTNode const *T) {
39     if (T)
40     {
41         if (T->lchild)
42             LastRoot(T->lchild);
43 
44         if (T->rchild)
45             LastRoot(T->rchild);
46 
47         cout << T->data << " ";
48     }
49 }

BinaryTree

  1 /*
  2 创建时间
  3 20170419
  4 说明
  5 二叉排序树练习
  6 */
  7 #pragma once
  8 #include "BinaryTree.h"
  9 
 10 int SearchBST(BiTNode *Tree, int key, BiTNode *f, BiTNode **p) {
 11     if (!Tree)
 12     {
 13         *p = f;
 14         return 0;
 15     }
 16     else if (key == Tree->data)
 17     {
 18         *p = Tree;
 19         return 1;
 20     }
 21     else if (key < Tree->data)
 22         return SearchBST(Tree->lchild, key, Tree, p);
 23 
 24     else
 25         return SearchBST(Tree->rchild, key, Tree, p);
 26 }
 27 
 28 int InsertBST(BiTNode **Tree, int key) {
 29     BiTNode *p, *s;
 30     if (!SearchBST(*Tree,key,NULL,&p))
 31     {
 32         s = (BiTNode*)malloc(sizeof(BiTNode));
 33         s->data = key;
 34         s->lchild = s->rchild = NULL;
 35         if (!p)
 36             *Tree = s;
 37         else if (key<p->data)
 38             p->lchild = s;
 39         else
 40             p->rchild = s;
 41         return 1;
 42     }
 43     else
 44     {
 45         return 0;
 46     }
 47 }
 48 
 49 int Delete(BiTNode **p) {
 50     BiTNode *q, *s;
 51     if ((*p)->rchild == NULL)
 52     {
 53         q = *p;
 54         *p = (*p)->lchild;
 55         free(q);
 56     }
 57     else if ((*p)->lchild == NULL)
 58     {
 59         q = *p;
 60         *p = (*p)->rchild;
 61         free(q);
 62     }
 63     else
 64     {
 65         q = *p;
 66         s = (*p)->lchild;
 67         while (s->rchild)
 68         {
 69             q = s;
 70             s = s->rchild;
 71         }
 72         (*p)->data = s->data;
 73         //Delete(&s);
 74         if (q!=*p)
 75         {
 76             q->rchild = s->lchild;
 77         }
 78         else
 79         {
 80             q->lchild = s->lchild;
 81         }
 82         free(s);
 83     }
 84     return 1;
 85 }
 86 
 87 int DeleteBST(BiTNode **T, int key) {
 88     if (!T)
 89         return 0;
 90 
 91     else 
 92     {
 93         if ((*T)->data == key)
 94             return Delete(T);
 95 
 96         else if (key < (*T)->data)
 97             return DeleteBST(&(*T)->lchild, key);
 98 
 99         else
100             return DeleteBST(&(*T)->rchild, key);
101     }
102 }

  1 #pragma once
  2 #include <iostream>
  3 using namespace std;
  4 
  5 struct BiTNode_avl
  6 {
  7     int data;
  8     int bf;
  9     struct BiTNode_avl *lchild, *rchild;
 10 };
 11 
 12 void R_Rotate(BiTNode_avl **p) {
 13     BiTNode_avl *L;
 14     L = (*p)->lchild;
 15     (*p)->lchild = L->rchild;
 16     L->lchild = (*p);
 17     *p = L;
 18 }
 19 
 20 void L_Rotate(BiTNode_avl **p) {
 21     BiTNode_avl *R;
 22     R = (*p)->rchild;
 23     (*p)->lchild = R->lchild;
 24     R->lchild = (*p);
 25     *p = R;
 26 }
 27 
 28 #define  LH +1
 29 #define  EH 0
 30 #define  RH -1
 31 
 32 void LeftBalance(BiTNode_avl **T) {
 33     BiTNode_avl *L, *Lr;
 34     L = (*T)->lchild;
 35     switch (L->bf)
 36     {
 37     case LH:
 38         (*T)->bf = L->bf = EH;
 39         R_Rotate(T);
 40         break;
 41     case RH:
 42         Lr = L->rchild;
 43         switch (Lr->bf)
 44         {
 45         case LH:
 46             (*T)->bf = RH;
 47             L->bf = EH;
 48             break;
 49         case EH:
 50             (*T)->bf = L->bf = EH;
 51             break;
 52         case RH:
 53             (*T)->bf = EH;
 54             L->bf = LH;
 55             break;
 56         }
 57         Lr->bf = EH;
 58         L_Rotate(&(*T)->lchild);
 59         R_Rotate(T);
 60     }
 61 }
 62 
 63 int InsertAVL(BiTNode_avl **T, int e, int *taller) {
 64     if (!*T)
 65     {
 66         *T = (BiTNode_avl *)malloc(sizeof(BiTNode_avl));
 67         (*T)->data = e;
 68         (*T)->lchild = (*T)->rchild = NULL;
 69         (*T)->bf = EH;
 70         *taller = true;
 71     }
 72     else
 73     {
 74         if (e == (*T)->data)
 75         {
 76             *taller = false;
 77             return false;
 78         }
 79         if (e < (*T)->data)
 80         {
 81             if (!InsertAVL(&(*T)->lchild,e,taller))
 82             {
 83                 return false;
 84             }
 85             if (taller)
 86             {
 87                 switch ((*T)->bf)
 88                 {
 89                 case LH:
 90                     LeftBalance(T);
 91                     *taller = false;
 92                     break;
 93                 case EH:
 94                     (*T)->bf = LH;
 95                     *taller = true;
 96                     break;
 97                 case RH:
 98                     (*T)->bf = EH;
 99                     *taller = false;
100                     break;
101                 }
102             }
103         }
104         else
105         {
106             if (!InsertAVL(&(*T)->rchild,e,taller))
107             {
108                 return false;
109             }
110             if (*taller)
111             {
112                 switch ((*T)->bf)
113                 {
114                 case LH:
115                     (*T)->bf = EH;
116                     *taller = false;
117                     break;
118                     
119                 case EH:
120                     (*T)->bf = RH;
121                     *taller = true;
122                     break;
123                 case RH:
124                     RightBalance(T);
125                     *taller = false;
126                     break;
127                 }
128             }
129         }
130     }
131     return true;
132 }