用于表示组数据类型及其在代码中用法的类
4.50/5 (2投票s)
2004年11月29日
3分钟阅读
42867
631
一个表示组数据类型及其在代码中用法的示例代码。
引言
与 Pascal 等其他编程语言不同，C# 中不存在组数据类型。因此，我决定编写一个这样的类来表示组类型。
背景
组类型的两个主要基本思想是：
- 顺序不重要，因此 {1,2,3} 和 {3,2,1} 这两个组是相等的。这就是为什么在处理组时，你不会询问成员在组中的位置，而只会询问成员是否属于该组。
- 组中的每个成员只计算一次，因此 {1,2,3,1,1} 和 {1,2,3} 这两个组是相等的，当然，更通用的表示法是 {1,2,3}。
所有关于组的操作符都基于这些主要思想。
使用代码
主类是 Group。Group 的 public 方法有：
public Group (params string[] group): 构造函数。public void update(params string[] group): 用新的组更新组。public void clear(): 清空组。public Group copyto(): 将组复制到另一个组。public void print(): 将类的成员打印到控制台。public override string ToString(): 以string形式返回组的成员。public int power(): 返回组的大小。public bool is_empty(): 检查组是否为空。public bool is_exist(s): 检查s是否存在于组中。public static Group operator+(Group g, string s): 向组添加成员。public static Group operator+(string s, Group g): 将成员添加到组。public static Group operator+(Group g1,Group g2): 两个组之间的并集操作符。public static Group operator*(Group g1,Group g2): 两个组之间的交集操作符。public static Group operator-(Group g, string s): 从组中移除成员。public static Group operator-(Group g1, Group g2): 从一个组中减去另一个组。public static bool operator<=(Group g1, Group g2): 检查g1组是否是g2的子集或等于g2。public static bool operator>=(Group g1, Group g2): 检查g2组是否是g1的子集或等于g1。public static bool operator==(Group g1, Group g2): 检查g1是否等于g2。public static bool operator!=(Group g1, Group g2): 检查g1是否与g2不同。public static bool operator<(Group g1, Group g2): 检查g1是否是g2的子集，但不等于g2。public static bool operator>(Group g1, Group g2): 检查g2是否是g1的子集，但不等于g1。public Group[] P(): 计算当前组的所有子组。
用于计算组的子组的 P 方法使用了堆栈类，堆栈类是 Group 类的一个 private 类，表示堆栈数据结构。stack 的 public 属性和方法有：
public int count: 返回堆栈大小的属性。
public stack(int sub_group_size): 构造函数。public void push(int val): 向堆栈推送元素。public int pop(): 从堆栈弹出元素。public int scan(int i): 返回位置i的值。public bool is_empty(): 检查堆栈是否为空。
所有这些方法都很简单明了，代码可以在附加到文档的源文件中找到，因此我没有在此处显示代码，除了计算当前组子组的 P 方法。
P 方法很复杂，花费了我很长时间来编写。我编写这个方法时的第一个想法是使用递归，但后来我改变了主意，决定使用堆栈，我认为这是一个明智的选择。
这是 P 方法的代码，由于其复杂性，它有非常详细的注释。
//return all the subgroups of current group
public Group[] P()
{
//hold the sub groups
Group[] temp=new Group[(int)((Math.Pow(2,this.power())-1))];
//hold the positions of the members of each sub group
stack s=new stack(this.power());
int sub_group_size=1; //hold the size of each sub group
int sub_group_counter=0; //hold the index of each sub group
int member_position=0, //hold the value poped up from satck
prev_member_position=-1; //hold the previous value poped up from stack
//loop to control the creation of each group of subgroups
//according to their size
while (sub_group_size<=this.power())
{
//initialize the stack for each size n from 1 ro n
for (int i=1;i<=sub_group_size;i++)
s.push(i);
//the process of building sub groups at each size is continue
//until the stack is empty.
//when the stack is empty it's mean that we finished creating all the
//sub groups of this size.
while (!s.is_empty())
{
temp[sub_group_counter]=new Group();
for (int i=0;i<=s.count-1;i++) //building specific subgroup
temp[sub_group_counter]+=(string)this.group[s.scan(i)-1];
sub_group_counter++;
//after creating each specific sub group we should to drop out
//from stack all the positions that came to end or in a nother word
//finished their job in the most internal loop
do
{
prev_member_position=member_position;
member_position=s.pop();
}
while (member_position>=this.power() ||
prev_member_position==member_position+1);
//if the stack is not empty we should advance the new internal position
//and if necessary also to accomplish new positions instead of the
//positions we droped out
if (member_position!=-1)
{
s.push(++member_position); //advancing the new internal position
//accomplishing the new sub group to the correct size instead
//of the positions we droped out from the stack
for (int i=s.count;i<sub_group_size;i++)
s.push(++member_position);
}
} //end of loop control about the stack emptiness
sub_group_size++;
} //end of loop control about the sub group size
return temp;
}
这是一个演示使用 Group 类的示例代码。
using System;
using Groups;
class main
{
static void Main(string[] args)
{
//this program is coming to demonstrate the use of the Group class.
//the input of the program is lists of words.
//the outputs are:
// 1. all the words in each list (every word is displayed only once).
// 2. all the words exist in each list that don't exist in the other lists.
// 3. all the words of all input lists (every word is displayed only once).
// 4. all the common words which exist
// in all the lists(every word is dispayed once).
// 5. the most representing relation between every pair of lists.
int lists_counter;
Group g=new Group();
System.Console.WriteLine();
num_of_lists:
try
{
System.Console.Write("please insert number of lists: ");
lists_counter=int.Parse(System.Console.ReadLine());
}
catch (Exception)
{
goto num_of_lists;
}
Group[] group=new Group[lists_counter];
for (int i=0;i<=lists_counter-1;i++)
{
System.Console.Write("please insert list" +
"of words with space between them: ");
string s=System.Console.ReadLine();
string[] list=s.Split(' ');
group[i]=new Group(list);
}
//printing the members of every group
System.Console.WriteLine();
System.Console.WriteLine("printing the groups");
System.Console.WriteLine("===================");
for (int i=0;i<=group.Length-1;i++)
group[i].print();
System.Console.WriteLine();
//printing the members of every group which not belong to the other groups
g.clear();
System.Console.WriteLine("printing members of each group" +
" that don't belong to other groups");
System.Console.WriteLine("==============================" +
"===================================");
for (int i=0;i<=group.Length-1;i++)
{
g=group[i].copyto();
for (int j=0;j<=group.Length-1;j++)
if (i!=j) g-=group[j];
g.print();
}
System.Console.WriteLine();
//printing the union of all lists
System.Console.WriteLine("printing the union of all lists");
System.Console.WriteLine("===============================");
g.clear();
for (int i=0;i<=group.Length-1;i++)
g+=group[i];
g.print();
System.Console.WriteLine();
//printing the intersection of all lists
System.Console.WriteLine("printing the intersection of all lists");
System.Console.WriteLine("======================================");
g=group[0];
for (int i=1;i<=group.Length-1;i++)
g*=group[i];
g.print();
System.Console.WriteLine();
//printing the relation between each pair of groups
System.Console.WriteLine("printing the relation between each pair of groups");
System.Console.WriteLine("==================================================");
System.Console.WriteLine();
for (int i=0;i<=group.Length-2;i++)
for (int j=i+1;j<=group.Length-1;j++)
if (i!=j)
{
if (group[i]<group[j])
System.Console.WriteLine("{0} < {1}",group[i],group[j]);
else if (group[i]>group[j])
System.Console.WriteLine("{0} > {1}",group[i],group[j]);
else if (group[i]==group[j])
System.Console.WriteLine("{0} = {1}",group[i],group[j]);
else
System.Console.WriteLine("{0} <> {1}",group[i],group[j]);
}
System.Console.ReadLine();
}
}
关注点
代码中最具挑战性的部分是 P 方法。通过编写这段代码，我还学会了如何处理运算符重载，在这方面，我为缺少 = 运算符感到遗憾，因为我注意到它不能被重载。
历史
- 2004/11/26 – 初始版本。