客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
所谓查找是指根据给定的某个值，在一个给定的数据结构中查找指定元素的过程。 主要得查找技术：线性表查找技术 树型查找技术 哈希表查找技术 线性表查找技术 顺序查找 最简单的查找方法。基本思想：从表的一端开始，顺序扫描线性表，一次奖扫描到的结点的关键字和给定值K想比较。 顺序查找的效率不高，但下列两种情况下自能有顺序查找。 1.若顺序表为无序表 2.采用链式存储结构的线性表 int SeqSearch(SeqList<int> R, int Key) { int i; R.Data[R.GetLength()] = Key; for (i = 0; R.Data[i] != Key; i++) ; if (i > R.Maxsize - 2) return -2; else return i; } 二分查找 折半查找 要求线性表是有序表，即表中结点按关键字有序，并且用顺序表作为表的存储结构。 int BinSearch(SeqList<int> R, int Key) { int low = 0, high = R.GetLength() - 1, mid; //设置当前查找区间的上下界的初值 while (low <= high) { mid = (low + high) / 2; if (R.Data[mid] == Key) return mid; if (R.Data[mid] > Key) high = mid - 1; else low = mid + 1; } return -1; } 分块查找 无 哈希技术是查找和检索与唯一标识键相关信息的最好方法之一。哈希表的基本原理是将给定的键值转换为偏移地址来检索记录。 键转换为地址是通过一种关系来完成，就是哈希函数。哈希函数对键执行操作，从而给定一个哈希值，该值是代表可以找到该记录的位置。 哈希法的基本思想是：设置一个长度为m的表T，用一个函数将数据集合中n个记录的关键字尽可能唯一地转换成0~m-1范围内的数值. 哈希表的冲突现象 两个不同的关键字，由于哈希函数值相同，因而被映射到同一个位置，为冲突。 解决哈希冲突 链表法：将所有关键字为同义词的结点链接在同一个单链表中。即同一位置用单链表存储键相同而值不同的记录。
Search
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace DataStructure { public interface IListDS<T> { int GetLength(); //求长度 void Clear(); //清空操作 bool IsEmpty(); //判断线性表是否为空 bool IsFull(); //判断数据表是否已满 void Append(T item); //附加操作 void Insert(T item, int i); //插入操作 T Delete(int i); //删除操作 T GetElement(int i); //取表元 int Locate(T value); //按值查找 void Reserve(); //倒置 } public class SeqList<T> : IListDS<T> { private int maxsize; //顺序表的容量 private T[] data; //数组，用于存储数据表中的数据元素 private int last; //指示数据表中最后一个元素的位置 //索引器 public T this[int index] { get { return data[index]; } set { data[index] = value; } } public T[] Data { get { return data; } set { data = value; } } //属性 最后一个元素的位置 public int Last { get { return last; } } //属性 容量 public int Maxsize { get { return maxsize; } set { maxsize = value; } } //构造函数 public SeqList(int size) { data = new T[size]; maxsize = size; last = -1; } public int GetLength() { return last + 1; } public void Clear() { last = -1; } public bool IsEmpty() { if (last == -1) return true; else return false; } public bool IsFull() { if (last == maxsize - 1) return true; else return false; } public void Append(T item) { if (IsFull()) { Console.WriteLine("List is full !"); return; } data[++last] = item; } public void Insert(T item, int i) { if (IsFull()) { Console.WriteLine("List is Full !"); return; } if (i < 1 || i > last + 2) { Console.WriteLine("Postion is Error !"); return; } if (i == last + 2) { data[i - 1] = item; } else { for (int j = last; j >= i - 1; j--) { data[j + 1] = data[j]; } data[i - 1] = item; } ++last; } public T Delete(int i) { T tem = default(T); if (IsEmpty()) { Console.WriteLine("List is Empty !"); return tem; } if (i < 1 || i > last + 1) { Console.WriteLine("Postion is Error !"); return tem; } if (i == last + 1) { tem = data[last--]; return tem; } else { tem = data[i - 1]; for (int j = i; j <= last; j++) { data[j] = data[j + 1]; } } --last; return tem; } public T GetElement(int i) { if (IsEmpty() || i < 1 || i > last + 1) { Console.WriteLine("List is Empty or Postion is Error !"); return default(T); } return data[i - 1]; } public int Locate(T value) { if (IsEmpty()) { Console.WriteLine("List is Empty !"); return -1; } int i = 0; for (i = 0; i <= last; i++) { if (value.Equals(data[i])) break; } if (i > last) { return -1; } return i; } public void Reserve() { T tem; int len = GetLength(); for (int i = 0; i <= len / 2; i++) { tem = data[i]; data[i] = data[len - 1]; data[len - 1] = tem; } } /// <summary> /// 将两个升序整型顺序表合并成一个升序顺序表 /// 思路：依次扫描La Lb中的元素，比较La和Lb中当前元素，将较小的元素值赋值给Lc,如此直到一个被扫描完，然后把未完的那个剩余的元素付给Lc /// </summary> /// <param name="La"></param> /// <param name="Lb"></param> /// <returns></returns> public SeqList<int> Merge(SeqList<int> La, SeqList<int> Lb) { SeqList<int> Lc = new SeqList<int>(La.Maxsize + Lb.Maxsize); int i = 0; int j = 0; while ((i <= La.GetLength() - 1) && (j <= Lb.GetLength() - 1)) { if (La[i] < Lb[j]) { Lc.Append(La[i++]); } else { Lc.Append(Lb[j++]); } } //如果La中还有元素 while (i <= La.GetLength() - 1) { Lc.Append(La[i++]); } //如果Lb中还有元素 while (i < Lb.GetLength() - 1) { Lc.Append(Lb[i++]); } return Lc; } /// <summary> /// 已知顺序表La 构造顺序表Lb 使其包含La中所有不相同的数据元素 /// 思路： 先把La中的第一个元素付给Lb 然后从La的第二个元素开始 每一个元素与Lb的每一个元素比较 不同则附加到Lb末尾 /// </summary> /// <param name="La"></param> /// <returns></returns> public SeqList<int> Purge(SeqList<int> La) { SeqList<int> Lb = new SeqList<int>(La.Maxsize); Lb.Append(La[0]); for (int i = 1; i <= La.GetLength() - 1; ++i) { int j = 0; for (j = 0; j <= Lb.GetLength() - 1; ++j) { if (La[i].CompareTo(Lb[j]) == 0) { break; } } //没有相同的元素，把La中的元素附加到Lb if (j > Lb.GetLength() - 1) { Lb.Append(La[i]); } } return Lb; } } /// <summary> /// 定义解决冲突的链表的结点类型 /// </summary> public class chaintype { private int key; private chaintype next; public int Key { get { return key; } set { key = value; } } public chaintype Next { get { return next; } set { next = value; } } } public class SearchArithMetic { /// <summary> /// 插入排序 /// </summary> /// <param name="R"></param> public void InsertSort(SeqList<int> R) { for (int i = 1; i < R.Maxsize; i++) { if (R.Data[i] < R.Data[i - 1]) { int temp = R.Data[i]; int j = 0; for (j = i - 1; j >= 0 && temp < R.Data[j]; j--) { R.Data[j + 1] = R.Data[j]; } R.Data[j + 1] = temp; } } } /// <summary> /// 顺序查找算法 /// </summary> /// <param name="R"></param> /// <param name="Key"></param> /// <returns></returns> public int SeqSearch(SeqList<int> R, int Key) { int i; R.Data[R.GetLength()] = Key; for (i = 0; R.Data[i] != Key; i++) ; if (i > R.Maxsize - 2) return -2; else return i; } /// <summary> /// 二分查找算法 /// </summary> /// <param name="R"></param> /// <param name="Key"></param> /// <returns></returns> public int BinSearch(SeqList<int> R, int Key) { int low = 0, high = R.GetLength() - 1, mid; //设置当前查找区间的上下界的初值 while (low <= high) { mid = (low + high) / 2; if (R.Data[mid] == Key) return mid; if (R.Data[mid] > Key) high = mid - 1; else low = mid + 1; } return -1; } /// <summary> /// 除模取余法的哈希函数 /// </summary> /// <param name="key"></param> /// <param name="Mod"></param> /// <returns></returns> public int Hash(int key, int Mod) { return key % Mod; } /// <summary> /// 在哈希表中插入记录，用链表法解决冲突 /// </summary> /// <param name="a"></param> /// <param name="key"></param> /// <param name="Mod"></param> /// <returns></returns> public bool HashInsert(chaintype[] a, int key, int Mod) { int i; i = Hash(key, Mod); chaintype pre; chaintype cur; pre = a[i]; cur = a[i]; while (cur != null && cur.Key != key) { pre = cur; cur = cur.Next; } /*未查找到时插入该记录在对应的链表尾*/ if (cur == null) { cur = new chaintype(); cur.Key = key; cur.Next = null; /*在该链插入第一个记录*/ if (a[i] == null) a[i] = cur; else pre.Next = cur; return true; } return false; } public chaintype HashSearch(chaintype[] a, int key, int Mod) { chaintype p; int i = Hash(key, Mod); p = a[i]; while (p != null && p.Key != key) { p = p.Next; } if (p == null) return null; else return p; } } class Search { /* /// <summary> /// 顺序查找 /// </summary> /// <param name="R"></param> /// <param name="Key"></param> /// <returns></returns> public static int SeqSearch(SeqList<int> R, int Key) { int i; R.Data[R.GetLength()] = Key; for (i = 0; R.Data[i] != Key; i++) ; if (i > R.Maxsize - 2) return -2; else return i; } /// <summary> /// 二分查找 /// </summary> /// <param name="R"></param> /// <param name="Key"></param> /// <returns></returns> public static int BinSearch(SeqList<int> R, int Key) { int low = 0, high = R.GetLength() - 1, mid; //设置当前查找区间的上下界的初值 while (low <= high) { mid = (low + high) / 2; if (R.Data[mid] == Key) return mid; if (R.Data[mid] > Key) high = mid - 1; else low = mid + 1; } return -2; } static void Main() { SeqList<int> queue = new SeqList<int>(10); queue.Append(10); queue.Append(20); queue.Append(30); queue.Append(40); queue.Append(50); queue.Append(60); queue.Append(70); queue.Append(80); queue.Append(90); //int location = SeqSearch(queue, 90); int location = BinSearch(queue, 90); Console.WriteLine("您查找的数据为表中第{0}位!", location + 1); Console.ReadKey(); } */ public static void Main() { SeqList<int> numList = null; numList = new SeqList<int>(12); chaintype[] a = new chaintype[13]; char selectFlag; while (true) { Console.WriteLine("请输入操作选项："); Console.WriteLine("1.创建顺序表"); Console.WriteLine("2.对顺序表执行顺序查找"); Console.WriteLine("3.对顺序表执行二分查找"); Console.WriteLine("4.创建哈希表"); Console.WriteLine("5.在哈希表中查找关键字"); Console.WriteLine("6.退出"); selectFlag = Convert.ToChar(Console.ReadLine()); SearchArithMetic searchA = new SearchArithMetic(); switch (selectFlag) { case '1': { numList.Insert(70, numList.GetLength() + 1); numList.Insert(30, numList.GetLength() + 1); numList.Insert(40, numList.GetLength() + 1); numList.Insert(10, numList.GetLength() + 1); numList.Insert(80, numList.GetLength() + 1); numList.Insert(20, numList.GetLength() + 1); numList.Insert(90, numList.GetLength() + 1); numList.Insert(100, numList.GetLength() + 1); numList.Insert(75, numList.GetLength() + 1); numList.Insert(60, numList.GetLength() + 1); numList.Insert(45, numList.GetLength() + 1); Console.WriteLine("已插入顺序表的数字是："); Console.WriteLine("70 30 40 10 80 20 90 100 75 60 45"); break; } case '2': { Console.WriteLine("请输入要查找的数字:"); long time1 = System.DateTime.Now.Ticks; int num = Convert.ToInt32(Console.ReadLine()); int i = searchA.SeqSearch(numList, num); if (i == -1) Console.WriteLine("{0}在数字列表中不存在", num); else Console.WriteLine("{0}在数字列表中的序号为{1}", num, i); long time2 = System.DateTime.Now.Ticks; Console.WriteLine("顺序查找用时{0}", time2 - time1); break; } case '3': { long time1 = System.DateTime.Now.Ticks; new SearchArithMetic().InsertSort(numList); long time2 = System.DateTime.Now.Ticks; Console.WriteLine("请输入要查找的数字:"); int num = Convert.ToInt32(Console.ReadLine()); long time3 = System.DateTime.Now.Ticks; int i = searchA.BinSearch(numList, num); if (i == -1) Console.WriteLine("{0}在数据列表中不存在", num); else Console.WriteLine("{0}在数字列表中的序号为{1}", num, i + 1); long time4 = System.DateTime.Now.Ticks; Console.WriteLine("排序用时{0}", time2 - time1); Console.WriteLine("二分查找用时{0}", time4 - time3); Console.WriteLine("查找总用时{0}", time4 - time1); break; } case '4': { searchA.HashInsert(a, 70, 13); searchA.HashInsert(a, 30, 13); searchA.HashInsert(a, 40, 13); searchA.HashInsert(a, 10, 13); searchA.HashInsert(a, 80, 13); searchA.HashInsert(a, 20, 13); searchA.HashInsert(a, 90, 13); searchA.HashInsert(a, 100, 13); searchA.HashInsert(a, 75, 13); searchA.HashInsert(a, 60, 13); searchA.HashInsert(a, 45, 13); break; } case '5': { Console.WriteLine("请输入要查找的数字："); long time1 = System.DateTime.Now.Ticks; int num = Convert.ToInt32(Console.ReadLine()); chaintype p = searchA.HashSearch(a, num, 13); if(p==null) Console.WriteLine("{0}在数据列表中不存在", num); else Console.WriteLine("您查找的关键字是：{0}",p.Key ); long time2 = 全部评论
专题导读
热门推荐
热门话题
 阅读排行榜
|
请发表评论