XIAOSUO 记录个人学习的足迹

摘要：Hash是各种数据结构中最为重要的数据结构之一；Hash具有O(1)的数据检索效率；Hash的空间开销却通常很大，以空间换取时间；适用于读取操作频繁，写入操作很少的操作类型。 一、存储结构 .NET中hash以数组的方式保存，数组的大小为素数，当数组中存在的数据项个数大于数组容量的扩张因子倍数时，数组进行扩张。 我们先看一下Hashtable类中的构造函数和一些重要数据项，如以下代码： public class Hashtable : IDictionary, ISerializable, IDeserializationCallback, ICloneable { //其他部分 private struct bucket { public Object key; //实际保存的键对象，如果key==buckets或者null，认为该项数据已经被清除 public Object val; //实际保存的值对象 public int hash_coll; //hash值最高位（31bit）表示在该位上是否发生过冲突 //即按照hash算法，在插入数据时如果计算到该位置发现hash_coll(31bit)==1，那么认为该位置曾经发生过冲突， //从当前位置使用hash算法计算后可能会继续发现可用的数据 } private bucket[] buckets; //保存数据的hash桶 private int count; //hash表中实际包含数据项个数 private int occupancy; //在hashtable中标记的冲突位个数 private int loadsize; private float loadFactor; //装载因子，如果 当前hash表中的实际数据项个数*装载因子hash表中保存数据项的桶的大小 //那么当前保存数据项桶需要扩容至少当前容量2倍的素数大小 //其他部分 //capacity为hash表中可以保存的数据项的期望值，注意：这个值并不等于保存数据项的hash桶的实际大小 public Hashtable(int capacity, float loadFactor) { if (capa…… 阅读全文

摘要：通常有两类方法处理冲突：开放定址(Open Addressing)法和拉链(Chaining)法。前者是将所有结点均存放在散列表T[0..m-1]中；后者通常是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表T[0..m-1]中。 一、开放定址法 （1）开放地址法解决冲突的方法 用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。 注意： ①用开放定址法建立散列表时，建表前须将表中所有单元(更严格地说，是指单元中存储的关键字)置空。 ②空单元的表示与具体的应用相关。 【例】关键字均为非负数时，可用-1来表示空单元，而关键字为字符串时，空单元应是空串。 总之：应该用一个不会出现的关键字来表示空单元。 （2）开放地址法的一般形式 开放定址法的一般形式为： hi=(h(key)+di)％m 1≤i≤m-1 其中： ①h(key)为散列函数，di为增量序列，m为表长。 ②h(key)是初始的探查位置，后续的探查位置依次是hl，h2，…，hm-1，即h(key)，hl，h2，…，hm-1形成了一个探查序列。 ③若令开放地址一般形式的i从0开始，并令d0=0，则h0=h(key)，则有： hi=(h(key)+di)％m 0≤i≤m-1 探查序列可简记为hi(0≤i≤m-1)。 （3）开放地址法堆装填因子的要求 开放定址法要求散列表的装填因子α≤l，实用中取α为0.5到0.9之间的某个值为宜。 （4）形成探测序列的方法 按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。 ①线性探查法(Linear Probing) 该方法的基本思想是： 将散列表T[0..m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：d，d+l，d+2，…，m-1，0，1，…，d-1 即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到T[d-1]为止。 探查…… 阅读全文

摘要：一、散列函数的选择有两条标准：简单和均匀。 简单指散列函数的计算简单快速； 均匀指对于关键字集合中的任一关键字，散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说，散列函数能将子集K随机均匀地分布在表的地址集{0，1，…，m-1}上，以使冲突最小化。 二、常用散列函数 为简单起见，假定关键字是定义在自然数集合上。 （1）平方取中法 具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。 将一组关键字(0100，0110，1010，1001，0111)平方后得(0010000，0012100，1020100，1002001，0012321) 若取表长为1000，则可取中间的三位数作为散列地址集： (100，121，201，020，123)。 相应的散列函数用C#实现很简单： public int Hash(int key) { //假设key是4为整数 key *= key; key /= 100; //先求平方值，后去掉末尾的两位数 return key % 1000; //取中间三为数作为散列地址返回 } （2）除余法 该方法是最为简单常用的一种方法。它是以表长m来除关键字，取其余数作为散列地址，即 h(key)=key％m 该方法的关键是选取m。选取的m应使得散列函数值尽可能与关键字的各位相关。m最好为素数。 如若选m是关键字的基数的幂次，则就等于是选择关键字的最后若干位数字作为地址，而与高位无关。于是高位不同而低位相同的关键字均互为同义词。 如若关键字是十进制整数，其基为10，则当m=100时，159，259，359，…，等均互为同义词。 （3）相乘取整法 该方法包括两个步骤：首先用关键字key乘上某个常数A(0A1)，并抽取出key.A的小数部分；然后用m乘以该小数后取整。即： 该方法最大的优点是选取m不再像除余法那样关键。比如，完全可选择它是2的整数次幂。虽然该方法对任何A的值都适用，但对某些值效果会更好。Knuth建议选取 该函数的C#代码为： double A = 0.6180339887; int m = 2; public int Hash(int key) { double d=k…… 阅读全文

摘要：一、散列表 设所有可能出现的关键字集合记为U(简称全集)。实际发生(即实际存储)的关键字集合记为K（|K|比|U|小得多）。 散列方法是使用函数h将U映射到表T[0..m-1]的下标上（m=O(|U|)）。这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。 其中： ① h：U→{0，1，2，…，m-1} ，通常称h为散列函数(Hash Function)。散列函数h的作用是压缩待处理的下标范围，使待处理的|U|个值减少到m个值，从而降低空间开销。 ② T为散列表(Hash Table)。 ③ h(Ki)(Ki∈U)是关键字为Ki结点存储地址(亦称散列值或散列地址)。 ④ 将结点按其关键字的散列地址存储到散列表中的过程称为散列(Hashing) 二、散列表的冲突现象 （1）冲突 两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。 上图中的k2≠k5，但h(k2)=h(k5)，故k2和K5所在的结点的存储地址相同。 （2）安全避免冲突的条件 最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件： ①其一是|U|≤m ②其二是选择合适的散列函数。 这只适用于|U|较小，且关键字均事先已知的情况，此时经过精心设计散列函数h有可能完全避免冲突。 （3）冲突不可能完全避免 通常情况下，h是一个压缩映像。虽然|K|≤m，但|U|m，故无论怎样设计h，也不可能完全避免冲突。因此，只能在设计h时尽可能使冲突最少。同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到表中。 （4）影响冲突的因素 冲突的频繁程度除了与h相关外，还与表的填满程度相关。 设m和n分别表示表长和表中填人的结点数，则将α=n/m定义为散列表的装填因子(Load Factor)。α越大，表越满，冲突的机会也越大。通常取α≤1。 阅读全文

摘要：一、按平均时间将排序分为四类 （1）平方阶(O(n2))排序 一般称为简单排序，例如插入、选择和冒泡排序； （2）线性对数阶(O(nlgn))排序 如快速、堆和归并排序； （3）O(n1+￡)阶排序 ￡是介于0和1之间的常数，即0￡1，如希尔排序； （4）线性阶(O(n))排序 如基数排序。 二、各种排序方法比较 简单排序中插入最好，快速排序最快，当文件为正序时，插入和冒泡均最佳。 三、影响排序效果的因素 因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素： ①待排序的记录数目n； ②记录的大小(规模)； ③关键字的结构及其初始状态； ④对稳定性的要求； ⑤语言工具的条件； ⑥存储结构； ⑦时间和辅助空间复杂度等。 四、不同条件下，排序方法的选择 (1)若n较小(如n≤50)，可采用插入或选择排序。 当记录规模较小时，插入排序较好；否则因为选择移动的记录数少于插人，应选选择排序为宜。 (2)若文件初始状态基本有序(指正序)，则应选用插人、冒泡或随机的快速排序为宜； (3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。 若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和插入排序结合在一起使用。先利用插入排序求得较长的有序子文件，然后再两两归并之。因为插入排序是稳定的，所以改进后的归并排序仍是稳定的。 (4)在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程。 当文件的n个关键字随机分布时，任何借助于比较的排序算法，至少需要O(nlgn)的时间。 (5)如果编程语言没有提供指针及递归，导致实现归并、快速(它们用递归实现较简单)和基数(使用了指针)等排序算法变得复杂。此时可考虑用其它排序。 (6)这些排序算法中，输人数据均是存储在一个向量中。当记录的规模较大时，为避免耗费大量的时间去移动记录，可以用链表作为存储结构。譬如插入排序、归并排序、基数排序都易于在链表上实现…… 阅读全文

摘要：分配排序的基本思想：排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)。 一、两种多关键码排序方法 最高位优先法（MSD法）。先按k1排序，将序列分成若干子序列，每个子序列中的记录具有相同的k1值；再按k2排序，将每个子序列分成更小的子序列；然后，对后面的关键码继续同样的排序分成更小的子序列，直到按kd排序分组分成最小的子序列后，最后将各个子序列连接起来，便可得到一个有序的序列。前面介绍的扑克牌先按花色再按面值进行排序的方法就是MSD法 最次位优先法（LSD法）。先按kd排序，将序列分成若干子序列，每个子序列中的记录具有相同的kd值；再按kd-1排序，将每个子序列分成更小的子序列；然后，对后面的关键码继续同样的排序分成更小的子序列，直到按k1排序分组分成最小的子序列后，最后将各个子序列连接起来，便可得到一个有序的序列。前面介绍的扑克牌先按面值再按花色进行排序的方法就是LSD法。 二、基于LSD方法的链式基数排序的基本思想 “多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字，可以看作由多个数位或多个字符构成的多关键字，此时可以采用“分配-收集”的方法进行排序，这一过程称作基数排序法，其中每个数字或字符可能的取值个数称为基数。比如，扑克牌的花色基数为4，面值基数为13。在整理扑克牌时，既可以先按花色整理，也可以先按面值整理。按花色整理时，先按红、黑、方、花的顺序分成4摞（分配），再按此顺序再叠放在一起（收集），然后按面值的顺序分成13摞（分配），再按此顺序叠放在一起（收集），如此进行二次分配和收集即可将扑克牌排列有序。 三、基数排序的实现 public class RadixNodeT { private T data; //数据域 private RadixNodeT next; //引用域 public RadixNode(T val, RadixNodeT p) { data = val; next = p; } public RadixNode(RadixNodeT p) { next = p;…… 阅读全文

摘要：对于排序大列表数据，一个有效的排序算法是归并排序。类似于快速排序算法，其使用的是分治法来排序。归并排序的基本思想是：将两个或两个以上的有序子序列”归并”为一个有序序列。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列“归并”为一个有序序列。 一、基本思想 二路归并排序的基本思想是：将有n个记录的原始序列看作n个有序子序列，每个子序的长度为1，然后从第一个子序列开始，把相邻的子序列两两合关，得到n/2个长度为2或1的子序列（当子序列的个数为奇数时，最后一组合并得到的序列长度为1），我们把这一过程称为一次归并排序，对一次归并排序的n/2个子序列采用上述方法继续顺序成对归并，如此重复，当最后得到长度为n的一个子序列时，该子序列便是原始序列归并排序后的有序序列。 第一步，将列表中的11个元素看成11个有序的序列，每个子序列的长度为1，然后两两归并，得到5个长度为2和1个长度为1的有序子序列。 第二步，将6个有序子序列两两归并，得到2个长度为4和1个长度为3的有序子序列。 第三步，将2个长度为4的有序子序列归并，得到第三趟归并结果。 第四步，将长度为8有序子序列和长度为3的有序子序列归并，得到第四趟归并结果，是长度为11的一个有序子序列。 二、并归排序的实现 public class MergeSort { //P=NP: public static Listint Demo(Listint data) { var arr = data.ToArray(); if (data.Count 2) { return data; } int middle = (int)Math.Floor(((decimal)(data.Count / 2))); var left = arr.AsSpan().Slice(0, middle).ToArray(); var right = arr.AsSpan().Slice(middle).ToArray(); return Merge(Demo(left.ToList()), Demo(right.ToList())); } …… 阅读全文

摘要：快速排序是C.R.A.Hoare于1962年提出的一种分区交换排序。它采用了一种分治法(Divide-and-ConquerMethod)策略，分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。快速排序是目前己知的平均速度最快的一种排序方法。 一、基本思想 快速排序方法的基本思想是：从待排序的n个记录中任意选取一个记录Ri（通常选取序列中的第一个记录）作标准，调整序列中各个记录的位置，使排在Ri前面的记录的关键字都小于Ri的关键字，排在Ri后面的记录的关键字都大于Ri的关键字，我们把这样一个过程称作一次快速排序。在第一次快速排序中，确定了所选取的记录Ri最终在序列中的排列位置，同时也把剩余的记录分成了两个子序列。对两个子序列分别进行快速排序，又确定了两个记录在序列中应处的位置，并将剩余的记录分成了四个子序列，如此重复下去，当各个子序列的长度为1时，全部记录排序完毕。 二、快速排序的实现 public class QuickSort { //排序算法--- 遍历--判断 ---交换-------降低 public static Listint Demo(Listint data, int left = 0, int? right = null) { int len = data.Count, partitionIndex; right = right ?? data.Count - 1; if (left right) { partitionIndex = partition(data, left, right.Value); Demo(data, left, partitionIndex - 1); Demo(data, partitionIndex + 1, right); } return data; } //分块的 左边是啥??? 右边是啥?? static int partition(Listint data, i…… 阅读全文

摘要：一、基本思想 将被排序的记录的关键字垂直排列，首先将第一个记录的关键字与第二个记录的关键字进行比较，若前者大于后者，则交换两个记录，然后比较第二个记录与第三个记录的关键字，依次类推，直到第n-1个记录与第n个记录的关键字比较为止。上述过程称为第一趟起泡排序，其结果使得关键字最大的记录被安排在最后一个记录的位置上。然后进行第二趟起泡排序，对前n-1条记录进行同样的排序，使得关键字次大的记录被安排在第n-1个记录的位置上。一般地，第i趟起泡排序从第一条记录到第i条记录依次比较相邻两条记录的关键字，并在逆序时交换相邻记录，其结果使得这i条记录中关键字最大的记录被交换到第i条记录的位置上。整个排序过程需要K（1≤K≤n-1）趟起泡排序，判断起泡排序结束的条件是在一趟起泡排序的过程中，没有进行过记录交换的操作。从下图中可见，在起泡排序的过程中，关键字较小的记录像水中的气泡逐渐向上飘浮，而关键字较大的记录好比石块逐渐向下沉，每一次有一块最大的石块沉到底。 二、冒泡排序的实现 public class BubbleSort { public static Listint Demo(Listint data) { for (var i = 0; i data.Count; i++)//i { for (var j = 0; j data.Count - 1 - i; j++)//j { if (data[j] data[j + 1]) { var temp = data[j + 1];///空间复杂度 //J+1--多了一个 data[j + 1] = data[j];//-j+1-- data[j] = temp; } } } return data; } } 三、时间复杂度分析 冒泡排序算法的最好情况是记录已全部排…… 阅读全文

摘要：一、基本思想 堆排序是针对直接选择排序所存在的上述问题的一种改进方法。它在寻找当前关键字最小记录的同时，还保存了本次排序过程中所产生的其他比较信息。 设有n个元素组成的序列{a0,a1,…an-1}，若满足下面的条件： （1）这些元素是一棵完全二叉树的结点，且对于i=0，1，…，n-1，ai是该完全二叉 树编号为i的结点； （2）满足下列不等式： 则称该序列为一个堆。堆分为最大堆和最小堆两种。满足不等式(a)的为最小堆，满足不等式(b)的为最大堆。 　　 由堆的定义可知，堆有如下两个性质： （1）最大堆的根结点是堆中关键码最大的结点，最小堆的根结点是堆中关键码最小的结点，我们称堆的根结点记录为堆顶记录。 （2）对于最大堆，从根结点到每个叶子结点的路径上，结点组成的序列都是递减有序的；对于最小堆，从根结点到每个叶子结点的路径上，结点组成的序列都是递增有序的。 将待排序的记录序列建成一个堆，并借助于堆的性质进行排序的方法叫作堆排序。堆排序的基本思想是：设有n个记录，首先将这n个记录按关键码建成堆，将堆顶记录输出，得到n个记录中关键码最大（或最小）的记录；调整剩余的n-1个记录，使之成为一个新堆，再输出堆顶记录；如此反复，当堆中只有一个元素数时，整个序列的排序结束，得到的序列便是原始序列的非递减或非递增序列。 从堆排序的基本思想中可看出，在堆排序的过程中，主要包括两方面的工作： （1）如何将原始的记录序列按关键码建成堆； （2）输出堆顶记录后，怎样调整剩下记录，使其按关键码成为一个新堆。 首先，以最大堆为例讨论第一个问题：如何将n个记录的序列按关键码建成堆。 考虑数字序列70、30、40、10、80、20、91、100、75、60、45 完全二叉树构建最大堆的示意图 二、堆排序的实现 在实现堆排序算法之前，先要实现将完全二叉树构建成最大堆的算法，然后在构建的堆之上实现堆排序，具体实现如下： public class HeapSort { static int _count; public static Listint Demo(Listint data) { Build(data); for (var i = data.Count - 1; i 0; i--) …… 阅读全文