当前位置：首页 > news >正文

《C#数据结构与算法》—集合、映射

news 2025/7/1 12:20:24

5-1基于无序链表实现集合、5-2基于无序链表实现映射

集合

什么是集合？

集合(Set)作为存储数据的容器时：

它是不允许存储相同元素的。只能保留一份。
能快速的帮助我们进行去重操作，过滤掉重复的元素

集合的应用

典型的应用：词汇量统计，统计一篇英文文章的总单词数
使用集合进行去重。看看不同的单词总数有多少个，判断英文文章的阅读难度。

集合的接口

ISet.cs

namespace DataStucture
{interface ISet<E>{int Count { get; }bool IsEmpty { get; }void Add(E e);void Remove(E e);bool Contains(E e);}
}

TestHelper.cs

功能用途

核心功能：读取文本文件，将其内容拆分为独立的单词（简陋的分词），并返回单词列表。
典型应用场景：
- 文本分析（如词频统计）。
- 为数据结构（如哈希表、字典树）提供测试数据。
- 自然语言处理（NLP）的预处理步骤（但分词逻辑较简单，不处理词性、时态等复杂情况）。

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;namespace DataStucture
{/// <summary>/// 辅助测试类/// </summary>class TestHelper{//读取名为filename的文件，并将它分词，分词后存入list中并返回使用public static List<string> ReadFile(string filename){//使用StreamReader读取filename文件信息FileStream fs = new FileStream(filename, FileMode.Open);//使用StreamReader读取filename文件信息StreamReader sr = new StreamReader(fs);//将读取的单词存入动态数组words中List<string> words = new List<string>();// 分词操作，这是一个非常简陋的分词方式//只要单词拼写不一样，我们就认为是不同的单词。不考虑单词的词性和时态。while (!sr.EndOfStream) // 如果没有读取到filename末尾。就继续while读取{//读取一行字符串并去除字符串的头部和尾部的空白符号，存储在contents中string contents = sr.ReadLine().Trim();//寻找contents第一个字母的位置int start = FirstCharacterIndex(contents, 0);//开始分词逻辑，将一个个的单词存储在数组words中for (int i = start + 1; i <= contents.Length; i++){if (i == contents.Length || !Char.IsLetter(contents[i])){string word = contents.Substring(start, i - start).ToLower();words.Add(word);start = FirstCharacterIndex(contents, i);i = start + 1;}elsei++;}}// 关闭流对象释放资源fs.Close();sr.Close();return words;}//寻找字符串s中，从start的位置开始的第一个字母字符的位置private static int FirstCharacterIndex(string s, int start){for (int i = start; i < s.Length; i++){if (char.IsLetter(s[i])){return i;}}return s.Length;}}
}

Program.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Net.Http.Headers;namespace DataStucture
{class Program{static void Main(string[] args){Stopwatch t = new Stopwatch();Console.WriteLine("英文");List<string> words = TestHelper.ReadFile("测试文件1/英文.txt");Console.WriteLine("单词总数：" + words.Count);LinkedList1Set<string> set = new LinkedList1Set<string>();foreach (var word in words){set.Add(word);}Console.WriteLine("不同单词的总数：" + set.Count);Console.WriteLine("运行时间：" +t. ElapsedMilliseconds);Console.Read();}}
}

输出结果

结论：是一个顺序的查找方式、效率低下

映射

什么是映射？

映射：指两个元素之间相互“对应”的关系

映射的案例

在C#中使用字典（Dictionary）表示，存储键值对的数据

键 (Key)	值 (Value)
身份证号码	人
车牌号码	车
学生学号	学生
单词词频	单词

字典的接口

IDictionary.cs

namespace DataStucture
{interface IDictionary<Key,Value>{//数量int Count { get; }//是否为空bool IsEmpty { get; }//添加void Add(Key key,Value value);//删除void Remove(Key key);//查找 （查看字典中是否有这个键）void ContainKey(Key key);//传入一个键 获取 对应的值Value Get(Key key);//修改void Set(Key key, Value newvalue);}
}

LinkedList3.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;namespace DataStucture
{class LinkedList3<Key,Value>{//创建节点类private class Node{public Key key;      //键public Value value;  //值public Node next;    //下一个元素的指针//构造函数public Node(Key key,Value value,Node next){this.key = key;this.value = value;this.next = next;}//打印 方法public override string ToString(){return key.ToString() + ":" + value.ToString();}}private Node head;  //标记头部引用private int N;  //键值对数量//构造函数  链表的初始状态public LinkedList3(){head = null;N = 0;}public int Count { get { return N; } }public bool IsEmpty { get { return N == 0; } }//查找是否有该节点private Node GetNode(Key key){Node cur = head;while (cur!=null){if (cur.key.Equals(key)){return cur;}cur = cur.next;}return null;}//增public void Add(Key key,Value value){Node node = GetNode(key);if (node == null){head = new Node(key, value, head);N++;}else{node.value = value;}}//判断是否存在public  bool Contains(Key key){return GetNode(key) != null;}//获取public Value Get(Key key){Node node = GetNode(key);if(node==null){throw new ArgumentException("键" + key + "不存在");}else{return node.value;}}//改public void Set(Key key,Value newvalue){Node node = GetNode(key);if (node == null){throw new ArgumentException("键" + key + "不存在");}else{node.value = newvalue;}}//删public void Remove(Key key){// 空链表直接返回if (head == null){return;}// 要删除的是头节点if (head.key.Equals(key)){head = head.next;  // 头指针指向下一个节点N--;}// 要删除的是中间或尾部节点else{Node cur = head;Node pre = null;while (cur != null){if (cur.key.Equals(key))  // 找到目标节点{break;}pre = cur;          // 记录前驱节点cur = cur.next;     // 移动到下一个节点}// 确认找到目标节点if (cur != null)       {pre.next = pre.next.next;   // 跳过当前节点（删除）N--;}}}}
}

Program.cs

using Elasticsearch.Net.Specification.IndicesApi;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Net.Http.Headers;namespace DataStucture
{class Program{static void Main(string[] args){Console.WriteLine("双城记");List<string> words = TestHelper.ReadFile("测试文件1/双城记.txt");Console.WriteLine("单词总数：" + words.Count);Stopwatch t = new Stopwatch();LinkedList3Dictionary<string,int> dic = new LinkedList3Dictionary<string,int>();t.Start();foreach (var word in words){if (!dic.ContainsKey(word)){dic.Add(word,1);}else{dic.Set(word, dic.Get(word) + 1);}}t.Stop();Console.WriteLine("不同单词的总数：" + dic.Count);Console.WriteLine("city出现的频次：" +dic.Get("city"));Console.WriteLine("运行时间：" +t.ElapsedMilliseconds);Console.Read();}}
}

输出结果：