文章目录

• 一、静态查找表
• • 1.1 顺序表查找
  • 1.2 有序表查找
  • • 1.2 .1折半查找（二分查找）
• 二、动态查找表
• 三、哈希表

一、静态查找表

1.1 顺序表查找

1.2 有序表查找

1.2 .1折半查找（二分查找）

优点：查找的效率高
缺点：已排好序，只适用于顺序存储

例题：
随机产生80 个整数构成的递增序列，
使用折半查找算法查找指定的整数，并统计比较次数。
提示：可用 a[i] = a[i-1] + rand() % 10 + 1 产生递增序列。 (1,10-1+1)

/*
* rand() % n +a;其中的a是起始值，n-1+a是终止值，n是整数的范围*/#include 
using namespace std;int c=0;//折半查找
int Search_bin(int *a, int key) {int low = 1;int high = 80;while (low<=high){c++;int mid=(low + high) / 2;if (key==a[mid]) {return mid;}else if(key<a[mid]){high = mid - 1;}else {low = mid + 1;}}return -1;
}int main() {int a[80];for (int i = 1; i <= 80; i++) {if (i == 1) {a[i] = rand() % 10 + 1;}else {a[i] = a[i - 1] + rand() % 10 + 1;}}for (int i = 1; i <= 80; i++) {cout << a[i] << "\t";if (i % 10 == 0) {cout << endl;}}cout << endl;int k;cout << "请输入你要查找的元素的值:";cin >> k;if (Search_bin(a,k)) {cout << k << "在a[]中位置为：" << Search_bin(a, k) << endl;cout << "比较次数为：" << c << endl;}else {cout << "不在a中";}return 0;
}

1.2.2 索引顺序表

二、动态查找表

二叉排序树（二叉查找树）

/*
输入10 个不同整数，依次插入到一颗初始为空的二叉排序树中，
并对其进行中序遍历，以验证树的正确性
*/
#include 
using namespace std;#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量//栈存储结构
typedef struct {int* base; //栈构造之前和销毁之后，值都为NULLint* top; //栈顶指针int stacksize; //当前已分配的存储空间，以元素为单位
}SqStack;/*初始化*/
int InitStack(SqStack& S) {S.base = (int*)malloc(STACK_INIT_SIZE * sizeof(int));if (!S.base) //存储分配失败exit(OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return 1;}
/*判断栈是否为空*/
int StackEmpty(SqStack S)
{if (S.base == S.top)return 1;elsereturn 0;
}/*插入*/
int Push(SqStack& S, int e) {//e 新的栈顶元素if (S.top - S.base >= S.stacksize) {S.base = (int*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(int));if (!S.base)exit(OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top++ = e;return 1;
}
/*删除栈顶元素并返回其值*/
int Pop(SqStack& S, int& e) {if (S.top == S.base)return 0;e = *--S.top;return 1;
}/*二叉链表存储结构*/
typedef struct BiTNode {int data;struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;int SearchBST(BiTree T, int key, BiTree f, BiTree& p)
//查找成功，参数p指向查找到的结点，f指向它的双亲；否则p指向key应插入的父结点或指向空（当T为空时）
{if (!T){p = f;return 0;}else if (key == T->data){p = T;return 1;}else if (key < T->data)return (SearchBST(T->lchild, key, T, p));elsereturn (SearchBST(T->rchild, key, T, p));
}int InsertBST(BiTree& T, int e)
//在二叉排序树中插入值为elem的元素，T指向二叉排序树根结点
{BiTree p = NULL, f = NULL;if (!SearchBST(T, e, f, p)) // 如果查找不成功{BiTree s = (BiTree)malloc(sizeof(BiTNode));s->data = e;s->lchild = s->rchild = NULL;if (!p) // 若二叉树为空被插结点作为树的根结点T = s; else if (e< p->data) //被插结点插入到p的左子树中p->lchild = s;else  //被插结点插入到p的右子树中p->rchild = s; return 1;}else // 查找成功,不插return 0; 
}/*非递归中序遍历*/
void InOrderTraverse(BiTree t)
{SqStack S;InitStack(S);BiTree p = t;while (p || !StackEmpty(S)){if (p) {Push(S, (int)p);p = p->lchild;}else {Pop(S, (int&)p);cout << p->data;p = p->rchild;}}}int main() {int a[10];cout << "输入10 个不同整数:" << endl;for (int i = 0; i < 10; i++) {cin >> a[i];}BiTree t;for (int i = 0; i < 10; i++) {InsertBST(t,a[i]);}InOrderTraverse(t);return 0;
}

三、哈希表

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！