c#数据结构之集合的实现（数组及链表两种实现）
集合的概念
集合是由一些确定的、彼此不同的成员或者元素构成的一个整体。如果将紧密相关的数据组合到一个集合中，则能够更有效地处理这些紧密相关的数据。代替编写不同的代码来处理每一单独的对象，您可以使用相同的调用代码来处理一个集合的所有元素。
在c#中可以使用 Array 类和 System.Collections 类添加、移除和修改集合中的个别元素或某一范围内的元素。甚至可以将整个集合复制到另一个集合中。在 .NET Framework 2.0 版中，泛型集合类提供了新功能，并使得创建强类型集合变得容易。
虽然c#中提供了多种集合类可供我们选择，但为了加深对这种数据类型的理解，构造自己的集合类无疑是最好的选择。下面给出了基于数组及链表两种实现的集合类。
定义集合实现的接口
view plaincopy to clipboardprint?
public interface IBag:IEnumerable
{
void Add(object element);
void AddAll(IBag bag);
int Size{get;}
bool IsEmpty();
object RemoveRandom();
object Remove(object target);
IBag Union(IBag bag);
bool Contains(object target);
}
public interface IBag:IEnumerable
{
void Add(object element);
void AddAll(IBag bag);
int Size{get;}
bool IsEmpty();
object RemoveRandom();
object Remove(object target);
IBag Union(IBag bag);
bool Contains(object target);
}
基于数组的集合实现
view plaincopy to clipboardprint?
public class ArrayBag:IBag
{
int DEDAULT_CAPACITY = 1000;
Random random = new Random();
int count=0;
object[] contents;
public ArrayBag()
{
contents = new object[DEDAULT_CAPACITY];
//count = 0;
}
public ArrayBag(int initialCapacity)
{
contents = new object[initialCapacity];
// count = 0;
}
#region IBag 成员
public void Add(object element)
{
if (Size == contents.Length)
{
ExpandCapacity();
}
contents[count] = element;
count++;
}
private void ExpandCapacity()
{
object[] temp = new object[contents.Length * 2];
for (int index = 0; index < contents.Length; index++)
{
temp[index] = contents[index];
}
contents = temp;
}
public void AddAll(IBag bag)
{
foreach (object o in bag)
{
Add(o);
}
}
public int Size
{
get { return count; }
}
public bool IsEmpty()
{
return (count==0);
}
public object RemoveRandom()
{
if (IsEmpty())
{
throw new Exception("this colleciton is empty!");
}
int choice = random.Next(count);
object result = contents[choice];
contents[choice] = contents[count - 1];
contents[count - 1] = null;
count--;
return result;
}
public object Remove(object target)
{
if (IsEmpty())
{
throw new Exception("the collection is empty");
}
int index = Find(target);
if (index == -1)
{
throw new Exception("not found!");
}
else
{
object result = contents[index];
contents[index] = contents[count - 1];
contents[count - 1] = null;
count--;
return result;
}
}
private int Find(object target)
{
for (int i = 0; i < count; i++)
{
if (contents[i].Equals(target))
return i;
}
return -1;
}
public IBag Union(IBag bag)
{
ArrayBag both = new ArrayBag();
for (int index = 0; index < count; index++)
{
both.Add(contents[index]);
}
foreach (object o in bag)
{
both.Add(o);
}
return both;
}
public bool Contains(object target)
{
if (Find(target) != -1)
{
return true;
}
else
{
return false;
}
}
public IEnumerator GetEnumerator()
{
for (int index = 0; index < count; index++)
{
yield return contents[index];
}
}
#endregion
public override string ToString()
{
StringBuilder sb = new StringBuilder();
for (int i = 0; i < count; i++)
{
sb.Append(contents[i] + " ");
}
return sb.ToString();
}
}
public class ArrayBag:IBag
{
int DEDAULT_CAPACITY = 1000;
Random random = new Random();
int count=0;
object[] contents;
public ArrayBag()
{
contents = new object[DEDAULT_CAPACITY];
//count = 0;
}
public ArrayBag(int initialCapacity)
{
contents = new object[initialCapacity];
// count = 0;
}
#region IBag 成员
public void Add(object element)
{
if (Size == contents.Length)
{
ExpandCapacity();
}
contents[count] = element;
count++;
}
private void ExpandCapacity()
{
object[] temp = new object[contents.Length * 2];
for (int index = 0; index < contents.Length; index++)
{
temp[index] = contents[index];
}
contents = temp;
}
public void AddAll(IBag bag)
{
foreach (object o in bag)
{
Add(o);
}
}
public int Size
{
get { return count; }
}
public bool IsEmpty()
{
return (count==0);
}
public object RemoveRandom()
{
if (IsEmpty())
{
throw new Exception("this colleciton is empty!");
}
int choice = random.Next(count);
object result = contents[choice];
contents[choice] = contents[count - 1];
contents[count - 1] = null;
count--;
return result;
}
public object Remove(object target)
{
if (IsEmpty())
{
throw new Exception("the collection is empty");
}
int index = Find(target);
if (index == -1)
{
throw new Exception("not found!");
}
else
{
object result = contents[index];
contents[index] = contents[count - 1];
contents[count - 1] = null;
count--;
return result;
}
}
private int Find(object target)
{
for (int i = 0; i < count; i++)
{
if (contents[i].Equals(target))
return i;
}
return -1;
}
public IBag Union(IBag bag)
{
ArrayBag both = new ArrayBag();
for (int index = 0; index < count; index++)
{
both.Add(contents[index]);
}
foreach (object o in bag)
{
both.Add(o);
}
return both;
}
public bool Contains(object target)
{
if (Find(target) != -1)
{
return true;
}
else
{
return false;
}
}
public IEnumerator GetEnumerator()
{
for (int index = 0; index < count; index++)
{
yield return contents[index];
}
}
#endregion
public override string ToString()
{
StringBuilder sb = new StringBuilder();
for (int i = 0; i < count; i++)
{
sb.Append(contents[i] + " ");
}
return sb.ToString();
}
}
基于链表的集合实现
view plaincopy to clipboardprint?
public class LinkNode
{
object element;
public object Element
{
get { return element; }
set { element = value; }
}
LinkNode next;
public LinkNode Next
{
get { return next; }
set { next = value; }
}
public LinkNode(object element)
{
this.element = element;
next = null;
}
public LinkNode()
{
}
}
public class LinkedBag:IBag
{
#region IBag 成员
LinkNode contents;
int count;
Random r = new Random();
public void Add(object element)
{
LinkNode node = new LinkNode(element);
node.Next = contents;
contents = node;
count++;
}
public void AddAll(IBag bag)
{
foreach (object o in bag)
{
Add(o);
}
}
public int Size
{
get { return count; }
}
public bool IsEmpty()
{
return (count==0);
}
public object RemoveRandom()
{
object result = null;
LinkNode previous, current;
if (IsEmpty())
{
throw new Exception("collection is empty!");
}
int choice = r.Next(count);
if (choice == 0)
{
result = contents.Element;
contents = contents.Next;
}
else
{
previous = contents;
for (int i = 1; i < choice; i++)
{
previous = previous.Next;
}
current = previous.Next;
result = current.Element;
previous.Next = current.Next;
}
count--;
return result;
}
public object Remove(object target)
{
bool found = false;
LinkNode previous, current;
object result = null;
if (IsEmpty())
{
throw new Exception("collection is empty!");
}
if (contents.Element.Equals(target))
{
result = contents.Element;
contents = contents.Next;
}
else
{
previous = contents;
current = previous.Next;
for(int i=1;i<count&&!found;i++)
{
if (current.Element.Equals(target))
{
found = true;
}
previous = current;
current = previous.Next;
}
if (!found)
{
throw new Exception("Elements not found!");
}
result = current.Next;
previous.Next = current.Next;
}
count--;
return result;
}
public IBag Union(IBag bag)
{
LinkedBag both = new LinkedBag();
foreach (LinkNode node in this)
{
both.Add(node.Element);
}
foreach (LinkNode node in bag)
{
both.Add(node.Element);
}
return both;
}
public bool Contains(object target)
{
bool found = false;
LinkNode current = contents;
while (current != null && !found)
{
if (current.Element.Equals(target))
{
found = true;
}
current = current.Next;
}
return found;
}
#endregion
#region IEnumerable 成员
public System.Collections.IEnumerator GetEnumerator()
{
LinkNode current = contents;
while (current != null)
{
yield return current;
current = current.Next;
}
}
#endregion
public override string ToString()
{
StringBuilder sb = new StringBuilder();
foreach (LinkNode node in this)
sb.Append(node.Element.ToString() + " ");
return sb.ToString();
}
}