C#数据结构与算法揭秘四

简介:

上节说过这节会讲双向链表,环形链表和应用举例,我们开始吧!!!!

首先,明白什么是双向链表。所谓双向链表是如果希望找直接前驱结点和直接后继结点的时间复杂度都是 O(1),那么,需要在结点中设两个引用域,一个保存直接前驱结点的地址,叫 prev,一个直接后继结点的地址,叫 next,这样的链表就是双向链表(Doubly Linked List)。双向链表的结点结构示意图如图所示。

双向链表结点的定义与单链表的结点的定义很相似, ,只是双向链表多了一个字段 prev。其实,双向链表更像是一根链条一样,你连我,我连你,不清楚,请看图。

双向链表结点类的实现如下所示

//一个链条的类

public class DbNode
{

//当前的数据所在
private T data; //数据域记录的数据的 
private DbNode prev; //前驱引用域 前驱 引用位置 
private DbNode next; //后继引用域 后来链条的位置

//构造器 这是不是初始化 
public DbNode(T val, DbNode p)
{
data = val;
next = p;
}

//构造器 这是不是初始化
public DbNode(DbNode p)
{
next = p;
}

//构造器  吧这个链子相应值 传递给他
public DbNode(T val)
{
data = val;
next = null;
}

//构造器  构造一个空的链子
public DbNode()
{
data = default(T);
next = null;
}

//数据域属性
public T Data
{
get
{
return data;
}
set
{
data = value;
}
}

//前驱引用域属性
public DbNode Prev
{
get
{
return prev;
}
set
{
prev = value;
}
}

//后继引用域属性
public DbNode Next
{
get
{
return next;
}
set
{
next = value;
}
}
}

说了这么多双向链表接点的类的属性,我们要看一看他的相关的操作。这里只做一些画龙点睛地方的描述

插入操作:设 p是指向双向链表中的某一结点,即 p存储的是该结点的地址,现要将一个结点 s 插入到结点 p 的后面,插入的源代码如下所示:操作如下: 

p.Next.Prev = s;
s.Prev = p;
s.Next = p.Next;
p.Next = s;

插入过程如图所示(以 p 的直接后继结点存在为例) 。

注意:引用域值的操作的顺序不是唯一的,但也不是任意的,操作必须放到操作的前面完成,否则 p 直接后继结点的就找不到了。这一点需要读者把每个操作的含义搞清楚。此算法时间操作消耗在查找上,其时间的复杂度是O(n).

下面,看他的删除操作,以在结点之后删除为例来说明在双向链表中删除结点的情况。 设 p是指向双向链表中的某一结点,即 p存储的是该结点的地址,现要将一个结点 s插入到结点 p的后面 。伪代码如下:操作如下:

p.Next = P.Next.Next;
p.Next.Prev = p.Prev;

删除过程如图所示(以 p的直接后继结点存在为例)

相应的算法的时间复杂度也是消耗到结点的查找上,其复杂度应该是O(n)

查找操作与单链表的极其的类似,也是从头开始遍历。相应伪代码如图所示:

current.next=p.next.next

current.prev=p.next.prev;

相应的伪代码如下图所示:

该算法的时间复杂度,是一个个的遍历的过程中,顾时间复杂度是O(n)

获取当前的双向链表长度与 查找类似,不做过多的赘述,这里,我们把双向链表基本概念和操作基本介绍完了,下面介绍一个重要的链表——环形链表。

首先,还是老样子,看看环形链表的定义。有些应用不需要链表中有明显的头尾结点。在这种情况下,可能需要方便地从最后一个结点访问到第一个结点。此时,最后一个结点的引用域不是空引用,而是保存的第一个结点的地址(如果该链表带结点,则保存的是头结点的地址) ,也就是头引用的值。我们把这样的链表结构称之为环形链表。他就像小朋友手拉手做游戏。如图所示。

用链表如图所示:

这里基本添加,删除,操作的操作与单链表简直是一模一样,这里就没有必要写这些东西。我们主要看他们一些简单应用。

应用举例一 已知单链表 H,写一算法将其倒置,即实现如图所示的操作,其中(a)为倒置前,(b)为倒置后。

算法思路:由于单链表的存储空间不是连续的,所以,它的倒置不能像顺表那样,把第 i 个结点与第 n-i 个结点交换(i 的取值范围是 1 到 n/2,n 为单链表的长度) 。其解决办法是依次取单链表中的每个结点插入到新链表中去。并且,为了节省内存资源,把原链表的头结点作为新链表的头结点。存储整数的单链表的倒置的算法实现如下:

public void ReversLinkList(LinkList H)
{
Node p = H.Next;
Node q = new Node ();
H.Next = null;

while (p != null)
{
q = p;
p = p.Next;
q.Next = H.Next;
H.Next = q;
}
}
该算法要对链表中的结点顺序扫描一遍才完成了倒置,所以时间复杂度为O(n),但比同样长度的顺序表多花一倍的时间,因为顺序表只需要扫描一半的数据元素。这个是不是你已经头脑糊了吗?如果糊了把,请看我的图例的解释。

举例2,约瑟夫环问题,题目如下:

已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。求最后出列的人相应的编号。

  void JOSEPHUS(int n,int k,int m) //n为总人数,k为第一个开始报数的人,m为出列者喊到的数

  {

  /* p为当前结点 r为辅助结点,指向p的前驱结点 list为头节点*/

  LinkList p,r,list; /*建立循环链表*/

  for(int i=0;i

  {

  p=(LinkList)LNode;

  p.data=i;

  if(list==NULL)

  list=p;

  else

  r.link=p;

  r=p;

  }

  p.link=list; /*使链表循环起来*/

  p=list; /*使p指向头节点*/

  /*把当前指针移动到第一个报数的人*/

  for(i=0;i

  {

  r=p;

  p=p.link;

  }

  /*循环地删除队列结点*/

  while(p.link!=p)

  {

  for(i=0;i

  {

  r=p;

  p=p.link;

  }

  r.link=p.link;

  console.writeline("被删除的元素:{0} ",p.data);

  free(p);

  p=r.node.;

  } 

  console.writeLine("\n最后被删除的元素是:{0}",P.data);

    具体的算法,如图所示:

 

      这个算法的时间的复杂度是O(n2)
  

  }

还和大家分享的一个例子,就是我做做一个类似与网易邮箱的产品时候,几千万甚至数以亿级的大数量登录的时候,发现用户登录的时候真的慢,你猜我开始是怎么做的,就是直接查数据库,这当然是不行的。这怎么办了, 最后,我在一个高人的指教下,发现登录的时候速度飞快,怎么搞的。我把所有的数据库的数据读入到内存中,然后把数据用链表把他们串起来,到我查询某个用户时候,只比较用户的 字节数。

这就是我眼中的链表结构。

目录
相关文章
|
3月前
|
存储 运维 监控
基于 C# 语言的 Dijkstra 算法在局域网内监控软件件中的优化与实现研究
本文针对局域网监控系统中传统Dijkstra算法的性能瓶颈,提出了一种基于优先队列和邻接表优化的改进方案。通过重构数据结构与计算流程,将时间复杂度从O(V²)降至O((V+E)logV),显著提升大规模网络环境下的计算效率与资源利用率。实验表明,优化后算法在包含1000节点、5000链路的网络中,计算时间缩短37.2%,内存占用减少21.5%。该算法适用于网络拓扑发现、异常流量检测、故障定位及负载均衡优化等场景,为智能化局域网监控提供了有效支持。
72 5
|
4月前
|
存储 算法 安全
如何控制上网行为——基于 C# 实现布隆过滤器算法的上网行为管控策略研究与实践解析
在数字化办公生态系统中,企业对员工网络行为的精细化管理已成为保障网络安全、提升组织效能的核心命题。如何在有效防范恶意网站访问、数据泄露风险的同时,避免过度管控对正常业务运作的负面影响,构成了企业网络安全领域的重要研究方向。在此背景下,数据结构与算法作为底层技术支撑,其重要性愈发凸显。本文将以布隆过滤器算法为研究对象,基于 C# 编程语言开展理论分析与工程实践,系统探讨该算法在企业上网行为管理中的应用范式。
122 8
|
4月前
|
存储 监控 算法
解析公司屏幕监控软件中 C# 字典算法的数据管理效能与优化策略
数字化办公的时代背景下,企业为维护信息安全并提升管理效能,公司屏幕监控软件的应用日益普及。此软件犹如企业网络的 “数字卫士”,持续记录员工电脑屏幕的操作动态。然而,伴随数据量的持续增长,如何高效管理这些监控数据成为关键议题。C# 中的字典(Dictionary)数据结构,以其独特的键值对存储模式和高效的操作性能,为公司屏幕监控软件的数据管理提供了有力支持。下文将深入探究其原理与应用。
83 4
|
5月前
|
机器学习/深度学习 监控 算法
员工上网行为监控软件中基于滑动窗口的C#流量统计算法解析​
在数字化办公环境中,员工上网行为监控软件需要高效处理海量网络请求数据,同时实时识别异常行为(如高频访问非工作网站)。传统的时间序列统计方法因计算复杂度过高,难以满足低延迟需求。本文将介绍一种基于滑动窗口的C#统计算法,通过动态时间窗口管理,实现高效的行为模式分析与流量计数。
108 2
|
5月前
|
人工智能 运维 算法
基于 C# 深度优先搜索算法的局域网集中管理软件技术剖析
现代化办公环境中,局域网集中管理软件是保障企业网络高效运行、实现资源合理分配以及强化信息安全管控的核心工具。此类软件需应对复杂的网络拓扑结构、海量的设备信息及多样化的用户操作,而数据结构与算法正是支撑其强大功能的基石。本文将深入剖析深度优先搜索(Depth-First Search,DFS)算法,并结合 C# 语言特性,详细阐述其在局域网集中管理软件中的应用与实现。
110 3
|
3月前
|
监控 算法 数据处理
内网实时监控中的 C# 算法探索:环形缓冲区在实时数据处理中的关键作用
本文探讨了环形缓冲区在内网实时监控中的应用,结合C#实现方案,分析其原理与优势。作为固定长度的循环队列,环形缓冲区通过FIFO机制高效处理高速数据流,具备O(1)时间复杂度的读写操作,降低延迟与内存开销。文章从设计逻辑、代码示例到实际适配效果展开讨论,并展望其与AI结合的潜力,为开发者提供参考。
142 2
|
3月前
|
监控 算法 安全
公司电脑监控软件关键技术探析:C# 环形缓冲区算法的理论与实践
环形缓冲区(Ring Buffer)是企业信息安全管理中电脑监控系统设计的核心数据结构,适用于高并发、高速率与短时有效的多源异构数据处理场景。其通过固定大小的连续内存空间实现闭环存储,具备内存优化、操作高效、数据时效管理和并发支持等优势。文章以C#语言为例,展示了线程安全的环形缓冲区实现,并结合URL访问记录监控应用场景,分析了其在流量削峰、关键数据保护和高性能处理中的适配性。该结构在日志捕获和事件缓冲中表现出色,对提升监控系统效能具有重要价值。
80 1
|
4月前
|
存储 监控 算法
基于 C# 的局域网计算机监控系统文件变更实时监测算法设计与实现研究
本文介绍了一种基于C#语言的局域网文件变更监控算法,通过事件驱动与批处理机制结合,实现高效、低负载的文件系统实时监控。核心内容涵盖监控机制选择(如事件触发机制)、数据结构设计(如监控文件列表、事件队列)及批处理优化策略。文章详细解析了C#实现的核心代码,并提出性能优化与可靠性保障措施,包括批量处理、事件过滤和异步处理等技术。最后,探讨了该算法在企业数据安全监控、文件同步备份等场景的应用潜力,以及未来向智能化扩展的方向,如文件内容分析、智能告警机制和分布式监控架构。
109 3
|
4月前
|
存储 监控 算法
局域网上网记录监控的 C# 基数树算法高效检索方案研究
在企业网络管理与信息安全领域,局域网上网记录监控是维护网络安全、规范网络行为的关键举措。随着企业网络数据量呈指数级增长,如何高效存储和检索上网记录数据成为亟待解决的核心问题。基数树(Trie 树)作为一种独特的数据结构,凭借其在字符串处理方面的卓越性能,为局域网上网记录监控提供了创新的解决方案。本文将深入剖析基数树算法的原理,并通过 C# 语言实现的代码示例,阐述其在局域网上网记录监控场景中的具体应用。
107 7
|
4月前
|
存储 监控 算法
基于 C# 时间轮算法的控制局域网上网时间与实践应用
在数字化办公与教育环境中,局域网作为内部网络通信的核心基础设施,其精细化管理水平直接影响网络资源的合理配置与使用效能。对局域网用户上网时间的有效管控,已成为企业、教育机构等组织的重要管理需求。这一需求不仅旨在提升员工工作效率、规范学生网络使用行为,更是优化网络带宽资源分配的关键举措。时间轮算法作为一种经典的定时任务管理机制,在局域网用户上网时间管控场景中展现出显著的技术优势。本文将系统阐述时间轮算法的核心原理,并基于 C# 编程语言提供具体实现方案,以期深入剖析该算法在局域网管理中的应用逻辑与实践价值。
85 5