数据结构——查找（线性表的查找与树表的查找）

目录

1.查找

1.查找的基本概念

1.在哪里找？

 2.什么查找？

3.查找成功与否？ 

4.查找的目的是什么？ 

5.查找表怎么分类？ 

6.如何评价查找算法？ 

7.查找的过程中我们要研究什么？ 

2.线性表的查找 

1.顺序查找 

代码示例：

 1.顺序查找的改进

代码示例：

2.顺序查找的性能分析与特点 

2.折半查找 

代码示例：

1.折半查找的性能分析与特点 

3.分块查找（索引顺序查找） 

1.分块查找性能分析与优缺点 

3.树表的查找 

1.二叉排序树 

1.二叉排序树的存储结构

代码示例：

2.二叉排序树的递归查找 

代码示例： 

3.二叉排序树的查找分析 

平衡二叉树 

4.二叉排序数的操作-插入 

5.二叉排序树的操作-删除 

4.总的代码

---

1.查找

1.查找的基本概念

1.在哪里找？

 2.什么查找？

3.查找成功与否？ 

4.查找的目的是什么？ 

5.查找表怎么分类？ 

6.如何评价查找算法？ 

7.查找的过程中我们要研究什么？ 

2.线性表的查找 

1.顺序查找 

代码示例：

typedef struct {int key;
}elem;typedef struct {elem *r;int len;
}sstable;sstable st;int search_seq(sstable st,int key) {for(int i = st.len; i >= 1; --i) {if(st.r[i].key == key) return i;return 0;}
}

 

 1.顺序查找的改进

代码示例：

int Search_seq(sstable st,int key) {st.r[0].key = key;int i;for(i = st.len; st.r[i].key != key; --i);return i;
}

 

2.顺序查找的性能分析与特点 

 

2.折半查找 

代码示例：

 

int search_bin(sstable st,int key) {int low = 1;int high = st.len;while(low <= high) {int mid = (low + high) / 2;if(st.r[mid].key == key) return mid;else if(key < st.r[mid].key)high = mid - 1;else low = mid + 1;}return 0;
}

1.折半查找的性能分析与特点 

3.分块查找（索引顺序查找） 

1.分块查找性能分析与优缺点 

3.树表的查找 

1.二叉排序树 

1.二叉排序树的存储结构

代码示例：

 

typedef struct {int key;
}elemtype;typedef struct bstnode {elemtype data;struct bstnode *lchild, *rchild;
}bstnode,*bstree;bstree t;

2.二叉排序树的递归查找 

代码示例： 

bstree searchbst(bstree t,int key) {if((!t) || key == t -> data.key) return t;else if(key < t -> data.key)return searchbst(t -> lchild,key);else return searchbst(t -> rchild,key);
}

3.二叉排序树的查找分析 

平衡二叉树 

4.二叉排序数的操作-插入 

 

5.二叉排序树的操作-删除 

4.总的代码

#include<bits/stdc++.h>
using namespace std;typedef struct {int key;
}elem;typedef struct {elem *r;int len;
}sstable;sstable st;int search_seq(sstable st,int key) {for(int i = st.len; i >= 1; --i) {if(st.r[i].key == key) return i;return 0;}
}int Search_seq(sstable st,int key) {st.r[0].key = key;int i;for(i = st.len; st.r[i].key != key; --i);return i;
}int search_bin(sstable st,int key) {int low = 1;int high = st.len;while(low <= high) {int mid = (low + high) / 2;if(st.r[mid].key == key) return mid;else if(key < st.r[mid].key)high = mid - 1;else low = mid + 1;}return 0;
}typedef struct {int key;
}elemtype;typedef struct bstnode {elemtype data;struct bstnode *lchild, *rchild;
}bstnode,*bstree;bstree t;bstree searchbst(bstree t,int key) {if((!t) || key == t -> data.key) return t;else if(key < t -> data.key)return searchbst(t -> lchild,key);else return searchbst(t -> rchild,key);
}int main() {return 0;
}