一、查找的基本概念
1.查找是数据结构中非常重要的一部分,无论你用的网站、日常生活电话号码、出门的地图、你想获取的信息......这些都要从查找开始。
2.查找常进行的操作:
(1)查询某个特定的元素是否在查找表中;
(2)检索摸某个个数据元素的属性;
(3)添加
(4)删除
3.查找的分类:
(1)静态查找 仅包含了操作的1-2
(2)动态查找 包含了操作的1-2-3-4
ps:如果只进行操作常用的结构是数组可以直接定位
对于能够进行包含添加删除类的链表是有优势的
整个问题应用与二叉树的话有链表的性质,又有查找的优势
二、静态查找
1.顺序扫描
2.二分查找,要求先排序的
static void Main(string[] args) { int[] temp = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1 }; quickSortRun(temp, 0, temp.Length - 1); Console.WriteLine(binarySearch(temp,9,0,temp.Length)); } //create a binary search you must first sort it public static int binarySearch(int[] temp, int key, int start, int end) { while (start < end) { int midPosition = (start + end) / 2; if (key == temp[midPosition]) { return midPosition; } else if (key < temp[midPosition]) { end = midPosition - 1; } else { start = midPosition + 1; } } return -1; } //quick sort public static int quickSort(int[] temp, int start, int end) { //decalre a variables of key int key = temp[start]; while (start < end) { //first get the position of below the start while (start < end && temp[end] > key) { end--; } temp[start] = temp[end]; //second get the position of above the start while (start < end && temp[start] < key) { start++; } temp[end] = temp[start]; } //end let the position key temp[start] = key; return start; } //quick sort is running public static void quickSortRun(int[] temp, int start, int end) { if (start < end) { int position = quickSort(temp, start, end); quickSortRun(temp, start, position - 1); quickSortRun(temp, position + 1, end); } }
三、动态查找
1.二叉树查找树 基本实现
(1)左子树不为空,则左子树小于根节点
(2)右子树不为空,则右子树大于根节点
(3)左右子树又是一个二叉排序树
=》优点:查找方面,时间的复杂度跟这个二叉树的深度有关系。最坏O(n)
=》缺点:当出现极端的情况下都是左子树或者右子树,那么意义不大了,纯粹一链表
=》平衡树方面:定义|左子树的度-右子树的度|<2 时间复杂度为O(log n)
=》红黑树 基本实现
=》 AVL 基本实现
2.B树的方面
=》可以看下索引方面,文件方面的查询
=》因为前段时间在看LUCENE
=》这些了解了回过头来继续看下
3.Hash方面
=》其实我倒现在都还不是太了解这些方面的东西
=》理解的范围只在于映射
4.TRIE树
=》对准字典方面的 我前面写的
相关推荐
实验目的或任务 通过指导学生上机实践,对常用数据结构的基本概念及其不同的实现方法的理论得到 进一步的掌握,并对在不同存储结构上实现不同的运算方式和技巧有所体会。 2. 实验教学基本要求 1.了解实验目的及实验...
包括顺序查找、二分查找、二叉排序树上查找以及散列表上查找的基本思想和算法实现。
实验内容及要求:定义B-树存储结构(要求m3;为方便操作,结点中增加双亲结点指针域,最底层的Fail结点用NULL指针表示并且所有结点均存储于内存)。定义B-树插入关键字函数、删除关键字函数、查找关键字函数以及按...
定义B-树存储结构(要求m3;为方便操作,结点中增加双亲结点指针域,最底层的Fail结点用NULL指针表示并且所有结点均存储于内存)。定义B-树插入关键字函数、删除关键字函数、查找关键字函数以及按层次遍历输出B-树...
兰州理工大学 二分查找算法、起泡排序、简单选择排序、直接插入排序、二分插入排序、快速排序算法
数据结构》(C语言版)的第1章综述数据、数据结构和抽象...其内容和章节编排1992年4月出版的《数据结构》(第二版)基本一致,但在本书中更突出了抽象数据类型的概念。全书采用类C语言作为数据结构和算法的描述语言。
基本思想是:首先将给定值key与表中中间位置记录的关键字相比较,若二者相等,则查找成功,否则根据比较的结果确定下次查找的范围是在中间记录的前半部分还是后半部分,然后在新的查找范围内进行同样的查找,如此...
#include using namespace std; #define True 11 #define False 0 #define Ok 111 #define Error -111 #define List_Init_Size 10 #define ListIncrement 10 typedef int Status;... //元素类型
广工的数据结构实验报告-静态查找表,你懂得……
1、编写二叉排序树的基本操作函数 (1)SearchNode( TREE *tree, int key,TREE **pkpt,TREE **kpt ) 查找结点函数; (2)InsertNode( TREE **tree, int key ) 二叉排序树插入函数; (3)DeleteNode( TREE **...
1、掌握查找的基本方法。 2、提交实验报告,报告内容包括:目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容与过程 实验内容: 编程分别对有序顺序表的...
数据结构基本实验程序,编程实现表的定义及常用操作:1)判断表示表是否为空;2)获取第i个节点的内容;3)删除;4)插入
实验六 查找 //顺序查找和二分查找 #include "stdio.h" #include "stdlib.h" #define N 20 typedef struct { int Key; }ElemType; typedef struct SSTable { ElemType *elem; int length; }SSTable; int Search_Seq...
基本要求: (1)设每个记录有下列数据项:电话号码、用户名、地址; (2)从文件中读取各记录,分别以电话号码和用户名为关键字建立不同的哈希表; (3)采用链地址法解决冲突; (4)查找并显示给定电话号码的记录; ...
第一章 1.1数据结构课程设计要求。 1.1.1数据结构课程设计问题描述。 从键盘读入一组数据,建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作 。 1.1.2数据结构课程设计基本要求。 建立二叉排序树并对其...
实验目的:掌握几种查找算法的基本思想 实验内容:实现几种查找算法并比较其算法性能 实验要求: 1、 以顺序存储结构来实现; 2、 实现顺序查找、折半查找、分块查找算法; 3、 所有查找算法应该以函数的形式表示; ...
数据结构中的查找和排序C语言实现代码(最基本的算法)
(5)输入顶点x,查找图G:若存在含x的顶点,则删除该结点及与之相关联的边,并作DFS遍历(执行操作3);否则输出信息“无x”; (6)判断图G是否是连通图,输出信息“YES”/“NO”; (7)如果选用的存储结构是邻接矩阵,则用...
数据结构方面的C代码,比较完善,希望能给大家带来帮助。。。
严蔚敏《数据结构》课件ppt版 一、基本问题问答: ...在严老师和其他很多的数据结构教材中都把查找和排序作为了一个独立的部分,这一 部分实际上主要在探讨算法,而不在是结构本身了。算法的概念将在后面提到。