有序数组
顾名思义：有顺序排列的数组 以下是需要运用到的方法： Rank（Key key） 排名：找出小于指定键的键数量 Add（Key key） 添加键（不允许添加重复键） Remove（Key key） 删除键 Contains（Key key） 查看是否包含指定键 Key Select（int k） 找出排名为 k 的键 Key Max（） 最大键 Key Min（） 最小键 Key Floor（Key key） 向下取整：找出小于等于该建的最大键 Key Ceiling（Key key）想上取整：找出大于等于该键的最小键 Bool IsEmpty 数组是否为空 int Count 数组元素个数
在有序数组中添加、删除元素
Rank：返回两个值，mid、l。 如果数组中有传进去的 key 值，那就返回数组中的 key 值 ➡ mid ！！！ 如果数组中没有传进去的 key 值，那就在返回小于 key 值的数量 ➡ L ！！！ 注意：方法中的三个变量都是数组中的索引！！！ Add：往有序数组中添加元素 不允许添加重复键 if (i < N && keys[i].CompareTo(key) == 0) return; 只要检测到，数组中的元素与传进来的值有相同的，就不执行下面代码
/// <summary>/// where 用于约束泛型的/// 例如：where Key : IComparable<Key>/// Key 类型是 IComparable 接口/// IComparable：要比较的对象的类中实现，可以比较该对象和另一个对象，可以让类的数据具有可比较性/// 并且 IComparable 提供一个方法：CompareTo（object obj）返回三个 int 类型的变量，-1、0、1/// 应用：假设 person1.CompareTo(person2)>0 ,意思是：/// 如果 person1 大于 person2 返回 1 ;/// 如果 person1 等于 person2 返回 0 ;/// 如果 person1 小于 person2 返回 -1 ;/// </summary>class SortedArray1<Key> where Key : IComparable<Key>{private Key[] keys;private int N;public SortedArray1(int capacity){keys = new Key[capacity];}public SortedArray1() : this(10) { }public int Count { get { return N; } }public bool IsEmpty { get { return N == 0; } }/// <summary>/// 返回两个值，mid、l。/// 如果数组中有传进去的 key 值，那就返回数组中的 key 值➡mid ！！！/// 如果数组中没有传进去的 key 值，那就在返回小于 key 值的数量➡L ！！！/// 注意：方法中的三个变量都是数组中的索引！！！/// </summary>public int Rank(Key key){int l = 0; //代表数组头部的索引int r = N - 1; //代表数组尾部的索引while (l <= r){//中间值int mid = l + (r - l) / 2;if (key.CompareTo(keys[mid]) < 0)r = mid - 1;else if (key.CompareTo(keys[mid]) > 0)l = mid + 1;elsereturn mid;}return l;}/// <summary>/// 往有序数组中添加元素/// 不允许添加重复键/// </summary>public void Add(Key key){int i = Rank(key);if (N == keys.Length)ResetCapacity(keys.Length * 2);// 如果从 Rank 中返回的值（也就是 i ），在小于数组的容量的 同时 数组中有元素和传进来的值相同//就不进来以下操作if (i < N && keys[i].CompareTo(key) == 0)return;//将 大于等于 i 的数组索引元素通通往后移一位//就是从最后开始移一位，一直到不在大于等于 i 为止for (int j = N - 1; j >= i; j--)keys[j + 1] = keys[j];//将数组的第 i 个索引元素赋值为传进来的值keys[i] = key;N++;}/// <summary>/// 删除有序数组中的指定元素/// </summary>public void Remove(Key key){if (IsEmpty)return;//Rank 中返回的值（也就是 i ）int i = Rank(key);if (i == N || keys[i].CompareTo(key) != 0)return;//就是将数组第 i + 1个索引开始，赋值给前一位，直到 N -1;for (int j = i + 1; j <= N - 1; j++)keys[j - 1] = keys[j];//数组的容量自减//然后，将数组第 N 个索引元素 变为 零N--;keys[N] = default(Key);if (N == keys.Length / 4){ResetCapacity(keys.Length / 2);}}/// <summary>/// 输出最小键/// </summary>public Key Min(){if (IsEmpty)throw new ArgumentException("数组为空");return keys[0];}/// <summary>/// 输出最大键/// </summary>public Key Max(){if (IsEmpty)throw new ArgumentException("数组为空");return keys[N - 1];}/// <summary>/// 返回数组索引 k 的键/// </summary>public Key Select(int k){if (k < 0 || k >= N)throw new ArgumentException("索引为空");return keys[k];}/// <summary>/// 查看是否包含指定键➡key/// </summary>public bool Contains(Key key){int i = Rank(key);if (i < N && keys[i].CompareTo(key) == 0)return true;return false;}/// <summary>/// 向下取整，找出小于等于该键的最大键/// </summary>public Key Floor(Key key){int i = Rank(key);if (i < N && keys[i].CompareTo(key) == 0)return keys[i];if (i == 0)throw new ArgumentException("没有找到小于和等于" + key + "的最大键");elsereturn keys[i - 1];}/// <summary>/// 向上取整，找出大于等于该键的最小键/// </summary>public Key Ceiling(Key key){int i = Rank(key);if (i == N)throw new ArgumentException("没有找到大于或等于" + key + "的最小键");elsereturn keys[i];}//调整数组容量的大小private void ResetCapacity(int newCapacity){Key[] newKeys = new Key[newCapacity];for (int i = 0; i < N; i++)newKeys[i] = keys[i];keys = newKeys;}//输出链表类的信息public override string ToString(){StringBuilder res = new StringBuilder();res.Append("[");for (int i = 0; i < N; i++){res.Append(keys[i]);if (i != N - 1)res.Append(", ");}res.Append("]");return res.ToString();}}class Program{private static void Main(string[] args){int[] arr = { 84, 48, 68, 35, 63, 24, 65, 62, 25, 64, 16, 38, 39, 59, 74 };SortedArray1<int> sortedArray1 = new SortedArray1<int>();for (int i = 0; i < arr.Length; i++)sortedArray1.Add(arr[i]);Console.WriteLine(sortedArray1);Console.WriteLine(sortedArray1.Min());Console.WriteLine(sortedArray1.Max());Console.WriteLine(sortedArray1.Select(5));Console.WriteLine(sortedArray1.Floor(30));Console.WriteLine(sortedArray1.Ceiling(30));Console.ReadKey();}}
运行结果：
链表集合与有序数组集合的性能对比
两者在性能上之所以有那么大的区别，原因在于： 链表集合是根据顺序查找法一个个进行查找 有序数组集合是二分查找法，在数组元素量大并且是按顺序排列的情况下，二分查找法是高效的！ 不过有序数组的 Add、Remove 时间复杂度跟链表数组是一样的，都是O（N） 但查找数据的时间复杂度是O（Log n）
//有序数组集合
//继承Iset 集合 接口，是为了添加数组的增删改查函数
//为了让类中的数据有比较性，所以继承 IComparable 是必要的
class SortedArray1Set<Key>:ISet<Key>where Key:IComparable<Key>
{
private SortedArray1<Key> s;
public int Count { get { return s.Count; } }
public bool IsEmpty { get { return s.IsEmpty; } }
public SortedArray1Set(int capacity)
{
s = new SortedArray1<Key>(capacity);
}
public SortedArray1Set()
{
s = new SortedArray1<Key>();
}
public void Add(Key key)
{
s.Add(key);
}
public bool Contains(Key key)
{
return s.Contains(key);
}
public void Remove(Key key)
{
s.Remove(key);
}
}
//链表集合
class LinkedLIstISet<E>:ISet<E>
{
LinkedList1<E> list;
public LinkedLIstISet()
{
list = new LinkedList1<E>();
}
public int Count { get { return list.Count; } }
public bool IsEmpty { get { return list.IsEmpty; } }
public void Add(E e)
{
if (!Contains(e))
list.AddFrist(e);
}
public bool Contains(E e)
{
return list.Containa(e);
}
public void Remove(E e)
{
list.Remove(e);
}
}
//将链表集合与有序数组集合性能对比
class Program
{
//
public static long TestSet(ISet<string> set, List<string> words)
{
Stopwatch t = new Stopwatch();
t.Start();
foreach (var word in words)
set.Add(word);
t.Stop();
return t.ElapsedMilliseconds;
}
private static void Main(string[] args)
{
Console.WriteLine("双城记");
List<string> words = TestHelper.ReadFile("测试文件1/双城记.txt");
Console.WriteLine("词汇量总数：" + words.Count);
Console.WriteLine();
Console.WriteLine("链表集合");
LinkedLIstISet<string> linkedLIstISet = new LinkedLIstISet<string>();
long t1 = TestSet(linkedLIstISet, words);
Console.WriteLine("不同单词的总数：" + linkedLIstISet.Count );
Console.WriteLine("运行时间：" + t1 + "ms" );
Console.WriteLine();
Console.WriteLine("有序数组集合");
SortedArray1Set<string> sortedArray1Set = new SortedArray1Set<string>();
long t2 = TestSet(sortedArray1Set, words);
Console.WriteLine("不同单词的总数：" + sortedArray1Set.Count);
Console.WriteLine("运行时间：" + t2 + "ms");
Console.ReadKey();
}
}
运行结果：
基于有序数组实现映射
有序数组实现映射的底层代码：
有序数组的集合与有序数组的映射两者没有本质区别，底层的逻辑代码都是一样的，唯一不一样的： 有序数组的集合只需要存储一个变量值，而有序数组的映射需要存储两个变量值。
//有序数组
//存储的元素必须是可比较的。这样才能进行排序。
//数据类型Key必须是实现了可比较的接口IComparable<Key>，才能进行元素的存储。
//where Key:IComparable<Key> 对Key进行泛型约束，限定Key类型，不能是任意类型
class SortedArray2<Key,Value> where Key : IComparable<Key>
{
private Key[] keys;
private Value[] values;
private int N;
public SortedArray2(int capacity)
{
keys = new Key[capacity];
values = new Value[capacity];
}
public SortedArray2() : this(10) { }
public int Count { get { return N; } }
public bool IsEmpty { get { return N == 0; } }
/// <summary>
/// 返回两个值，mid、l。
/// 如果数组中有传进去的 key 值，那就返回数组中的 key 值➡mid ！！！
/// 如果数组中没有传进去的 key 值，那就在返回小于 key 值的数量➡L ！！！
/// 注意：方法中的三个变量都是数组中的索引！！！
/// </summary>
public int Rank(Key key)
{
int l = 0; //代表数组头部的索引
int r = N - 1; //代表数组尾部的索引
while (l <= r)
{
//中间值
int mid = l + (r - l) / 2;
if (key.CompareTo(keys[mid]) < 0)
r = mid - 1;
else if (key.CompareTo(keys[mid]) > 0)
l = mid + 1;
else
return mid;
}
return l;
}
public Value GetValue(Key key)
{
if (IsEmpty)
throw new ArgumentException("数组为空");
int i = Rank(key);
if (i < N && keys[i].CompareTo(key) == 0)
return values[i];
else
throw new ArgumentException("键"+key+"不存在");
}
/// <summary>
/// 往有序数组中添加元素
/// 不允许添加重复键
/// </summary>
public void Add(Key key,Value value)
{
int i = Rank(key);
if (N == keys.Length)
ResetCapacity(keys.Length * 2);
// 如果从 Rank 中返回的值（也就是 i ），在小于数组的容量的 同时 数组中有元素和传进来的值相同
//就不进来以下操作
if (i < N && keys[i].CompareTo(key) == 0)
{
values[i] = value;
return;
}
//将 大于等于 i 的数组索引元素通通往后移一位
//就是从最后开始移一位，一直到不在大于等于 i 为止
for (int j = N - 1; j >= i; j--)
keys[j + 1] = keys[j];
//将数组的第 i 个索引元素赋值为传进来的值
keys[i] = key;
values[i] = value;
N++;
}
/// <summary>
/// 删除有序数组中的指定元素
/// </summary>
public void Remove(Key key)
{
if (IsEmpty)
return;
//Rank 中返回的值（也就是 i ）
int i = Rank(key);
if (i == N || keys[i].CompareTo(key) != 0)
return;
//就是将数组第 i + 1个索引开始，赋值给前一位，直到 N -1;
for (int j = i + 1; j <= N - 1; j++)
{
keys[j - 1] = keys[j];
values[j - 1] = values[j];
}
//数组的容量自减
//然后，将数组第 N 个索引元素 变为 零
N--;
keys[N] = default(Key);
values[N] = default(Value);
if (N == keys.Length / 4)
{
ResetCapacity(keys.Length / 2);
}
}
/// <summary>
/// 输出最小键
/// </summary>
public Key Min()
{
if (IsEmpty)
throw new ArgumentException("数组为空");
return keys[0];
}
/// <summary>
/// 输出最大键
/// </summary>
public Key Max()
{
if (IsEmpty)
throw new ArgumentException("数组为空");
return keys[N - 1];
}
/// <summary>
/// 返回数组索引 k 的键
/// </summary>
public Key Select(int k)
{
if (k < 0 || k >= N)
throw new ArgumentException("索引为空");
return keys[k];
}
/// <summary>
/// 查看是否包含指定键➡key
/// </summary>
public bool Contains(Key key)
{
int i = Rank(key);
if (i < N && keys[i].CompareTo(key) == 0)
return true;
return false;
}
/// <summary>
/// 向下取整，找出小于等于该键的最大键
/// </summary>
public Key Floor(Key key)
{
int i = Rank(key);
if (i < N && keys[i].CompareTo(key) == 0)
return keys[i];
if (i == 0)
throw new ArgumentException("没有找到小于和等于" + key + "的最大键");
else
return keys[i - 1];
}
/// <summary>
/// 向上取整，找出大于等于该键的最小键
/// </summary>
public Key Ceiling(Key key)
{
int i = Rank(key);
if (i == N)
throw new ArgumentException("没有找到大于或等于" + key + "的最小键");
else
return keys[i];
}
//调整数组容量的大小
private void ResetCapacity(int newCapacity)
{
Key[] newKeys = new Key[newCapacity];
Value[] NewValues = new Value[newCapacity];
for (int i = 0; i < N; i++)
{
newKeys[i] = keys[i];
NewValues[i] = values[i];
}
keys = newKeys;
values = NewValues;
}
//输出链表类的信息
public override string ToString()
{
StringBuilder res = new StringBuilder();
res.Append("[");
for (int i = 0; i < N; i++)
{
res.Append("{" + keys[i] + "," + values[i] + "}");
if (i != N - 1)
res.Append(", ");
}
res.Append("]");
return res.ToString();
}
}
将有序数组的映射，其底层代码进行封装调用
class SortedArray2Dictionary<Key,Value>:IDictionary<Key,Value>where Key:IComparable<Key>
{
private SortedArray2<Key, Value> s2;
public int Count { get { return s2.Count; } }
public bool IsEmpty { get { return s2.IsEmpty; } }
public SortedArray2Dictionary(int capacity)
{
s2 = new SortedArray2<Key, Value>(capacity);
}
public SortedArray2Dictionary()
{
s2 = new SortedArray2<Key, Value>();
}
//O(N)
public void Add(Key key, Value value)
{
s2.Add(key, value);
}
//O(N)
public void Remove(Key key)
{
s2.Remove(key);
}
//O(log n)
public bool ContainKey(Key key)
{
return s2.Contains(key);
}
//O(log n)
public Value Get(Key key)
{
return s2.GetValue(key);
}
//O(log n)
public void Set(Key key, Value NewValue)
{
s2.Add(key, NewValue);
}
}
//调用
class Program
{
public static long TestDicitionary(IDictionary<string,int> dic , List<string> words)
{
Stopwatch t = new Stopwatch();
t.Start();
foreach (var word in words)
{
//如果单词不存在字典中，说明是第一次遇见这个单词，频次设为1
if (!dic.ContainKey(word))
dic.Add(word, 1);
else //如果单词已经存在字典中，将单词对应的频次 +1
dic.Set(word, dic.Get(word) + 1);
}
t.Stop();
return t.ElapsedMilliseconds;
}
private static void Main(string[] args)
{
Console.WriteLine("双城记");
List<string> words = TestHelper.ReadFile("测试文件1/双城记.txt");
Console.WriteLine("词汇量总数：" + words.Count);
Console.WriteLine();
Console.WriteLine("链表集合");
LinkedList3Dictionary<string,int> dic1 = new LinkedList3Dictionary<string, int>();
long t1 = TestDicitionary(dic1, words);
Console.WriteLine("不同单词的总数：" + dic1.Count);
Console.WriteLine("运行时间：" + t1 + "ms");
Console.WriteLine();
Console.WriteLine("有序数组集合");
SortedArray2Dictionary<string,int> dic2 = new SortedArray2Dictionary<string, int>();
long t2 = TestDicitionary(dic2, words);
Console.WriteLine("不同单词的总数：" + dic2.Count);
Console.WriteLine("运行时间：" + t2 + "ms");
Console.ReadKey();
}
}
运行结果：
若有收获，就点个赞吧
0 人点赞
