今天受一个帖子的刺激，再次复习起了数据结构与算法，那本《数据结构与算法（java版）》我还剩图和高级排序的几章没看，工作上也没我的事需要处理，就用C#重新写了一遍链表结构，权作复习。
定义List接口：
<!----> public interface List
{
bool IsEmpty();
void Unshift(Object obj);
Object Shift();
void Push(Object obj);
Object Pop();
bool Contain(Object obj);
void Delete(Object obj);
void PrintAll();
Object getHead();
Object getTail();
void Clear();
}
实现单向链表：
<!----> //单向链表
public class SList:List
{
private SNode head, tail;
public SList()
{
this.head = this.tail = null;
}
public bool IsEmpty()
{
return head == null;
}
public void Unshift(Object obj)
{
head = new SNode(obj, head);
if (tail == null)
tail = head;
}
public Object Shift()
{
if (head == null)
throw new NullReferenceException();
Object value = head.value;
if (head == tail)
head = tail = null;
else
head = head.next;
return value;
}
public void Push(Object obj)
{
if (!IsEmpty())
{
tail.next = new SNode(obj);
tail = tail.next;
}
else
head = tail = new SNode(obj);
}
public Object Pop()
{
if (head == null)
throw new NullReferenceException();
Object obj = tail.value;
if (head == tail)
head = tail = null;
else
{
//查找前驱节点
for (SNode temp = head; temp.next != null && !temp.next.Equals(tail); temp = temp.next)
tail = temp;
tail.next = null;
}
return obj;
}
public void PrintAll()
{
string result = "";
for (SNode temp = head; temp != null; temp = temp.next)
result += " " + temp.value.ToString();
Console.WriteLine(result);
}
public bool Contain(Object obj)
{
if (head == null)
return false;
else
{
for (SNode temp = head; temp != null; temp = temp.next)
{
if (temp.value.Equals(obj))
return true;
}
}
return false;
}
public void Delete(Object obj)
{
if (!IsEmpty())
{
if (head == tail && head.value.Equals(obj))
head = tail = null;
else if (head.value.Equals(obj))
head = head.next;
else
{
//temp_prev为删除值的前驱节点
for (SNode temp_prev = head, temp = head.next; temp != null; temp_prev = temp_prev.next, temp = temp.next)
{
if (temp.value.Equals(obj))
{
temp_prev.next = temp.next; //设置前驱节点的next为下个节点
if (temp == tail)
tail = temp_prev;
temp = null;
break;
}
}
}
}
}
public Object getHead()
{
return this.head.value;
}
public Object getTail()
{
return this.tail.value;
}
public void Clear()
{
do
{
Delete(head.value);
} while (!IsEmpty());
}
}
class SNode
{
public Object value;
public SNode next;
public SNode(Object value, SNode next)
{
this.value = value;
this.next = next;
}
public SNode(Object value)
{
this.value = value;
this.next = null;
}
}
实现双向链表：
<!----> //双向链表
public class LinkedList:List
{
private LinkedNode head, tail;
public LinkedList()
{
head = tail = null;
}
public bool IsEmpty()
{
return head == null;
}
public void Unshift(Object obj)
{
if (IsEmpty())
head = tail = new LinkedNode(obj);
else
{
head = new LinkedNode(obj, null, head);
head.next.prev = head;
}
}
public Object Shift()
{
if (IsEmpty())
throw new NullReferenceException();
Object obj = head.value;
if (head == tail)
head = tail = null;
else
{
head = head.next;
head.prev = null;
}
return obj;
}
public void Push(Object obj)
{
if (IsEmpty())
head = tail = new LinkedNode(obj);
else
{
tail = new LinkedNode(obj, tail, null);
tail.prev.next = tail;
}
}
public Object Pop()
{
if (IsEmpty())
throw new NullReferenceException();
Object value = tail.value;
if (head == tail)
head = tail = null;
else
{
tail = tail.prev;
tail.next = null;
}
return value;
}
public bool Contain(Object obj)
{
if (IsEmpty())
return false;
else
{
for (LinkedNode temp = head; temp != null; temp = temp.next)
if (temp.value.Equals(obj))
return true;
}
return false;
}
public void Delete(Object obj)
{
if (IsEmpty())
throw new NullReferenceException();
if (head == tail)
head = tail = null;
else
{
for (LinkedNode temp = head; temp != null; temp = temp.next)
{
if (temp.value.Equals(obj))
{
if (temp.value.Equals(obj))
{
if (temp == tail)
{
tail = tail.prev;
tail.next = null;
break;
}
else if (temp == head)
{
head.next.prev = null;
head = head.next;
}
else
temp.prev.next = temp.next;
}
}
}
}
}
public void PrintAll()
{
string result = "";
for(LinkedNode temp=head;temp!=null;temp=temp.next)
result += " " + temp.value.ToString();
Console.WriteLine(result);
}
public Object getHead()
{
return this.head.value;
}
public Object getTail()
{
return this.tail.value;
}
public void Clear()
{
do
{
Delete(head.value);
} while (!IsEmpty());
}
}
class LinkedNode
{
public Object value;
public LinkedNode prev;
public LinkedNode next;
public LinkedNode(Object value, LinkedNode prev, LinkedNode next)
{
this.value = value;
this.next = next;
this.prev = prev;
}
public LinkedNode(Object value)
{
this.value = value;
}
}
分享到：
相关推荐
### C#实现单向链表 #### 一、引言 单向链表是一种常见的数据结构，在计算机科学中被广泛应用于解决各种问题。它由一系列节点组成，每个节点包含一个数据元素以及指向下一个节点的引用。本文将详细介绍如何在C#中...
在深入探讨如何使用C#实现双向链表之前，我们首先需要理解双向链表的基本概念及其在数据结构中的重要性。双向链表是一种线性数据结构，其中每个元素（节点）包含一个指向前一个节点和后一个节点的引用，这与只包含一...
本文将详细讲解如何在C#中实现单向链表，结合源码解析来帮助你深入理解其内部机制。 首先，我们要知道什么是单向链表。单向链表是由一系列节点组成，每个节点包含两个部分：数据域和指针域。数据域存储实际的数据，...
本教程将深入探讨C#实现链表的相关知识，为初学者提供实践指导。 一、链表概念 链表不同于数组，它不是一块连续的内存空间。链表由一系列节点组成，每个节点包含数据元素以及指向下一个节点的引用（或称为指针）。...
了解了这些基础知识后，你可以在实际项目中灵活运用链表，比如构建动态数据结构、实现高级算法（如LRU缓存策略）等。通过实践，你将能更深入地理解链表的强大之处。在提供的压缩包文件“C#链表”中，可能包含了示例...
下面我们将详细探讨C#中单向链表的实现。 首先，我们定义一个链表节点类(Node)，它有两个属性：`Data`用于存储数据，`Next`用于存储指向下一个节点的引用。代码如下： ```csharp public class Node { public int ...
本篇文章将详细探讨如何在C#中实现一个双链表，并结合模板、接口和结构体等关键概念。 1. **双向链表的基础** 双向链表与单链表的主要区别在于，每个节点不仅存储数据，还包含两个指针：一个指向下一个节点（后继...
在C#中，System.Collections.Generic命名空间提供了一个名为LinkedList类，用于实现链表数据结构。LinkedList类包含节点（LinkedListNode）作为链表中的元素，每个节点存储一个值，并通过引用指向下一个节点。链表...
接下来，我们将深入探讨C#中单向链表的概念、实现以及操作。 一、单向链表的概念 单向链表由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域存储实际的数据，而指针域（通常称为`Next`）指向链表中的...
本篇文章将深入探讨C#中的链表实现，包括链表的基本概念、结构以及如何通过`MyLinkedList.cs`和`Node.cs`这两个文件来创建一个自定义链表。 链表是一种线性数据结构，与数组不同，它的元素可以在内存中的任何位置。...
本主题聚焦于使用C#语言通过泛型来实现一个单向链表。链表是一种非连续、非顺序存储的数据结构，由一系列节点（也称为元素或记录）组成，每个节点包含数据和指向下一个节点的引用。在C#中，泛型提供了一种方式，可以...
本篇文章将深入探讨C#中的双向链表（Doubly Linked List）的实现，这是一类允许从两端进行访问的链式数据结构。 双向链表与单链表的主要区别在于每个节点不仅存储元素值，还包含两个指针，一个指向前一个节点，另一...
阶段练习：实现链表（LinkedList） 简介：写一个链表的数据结构，要求实现IList接口。 具体要求： 1、 使用代码规范。 2、 至少对IList中的Add，Remove，Insert，Indexer，IEnumerator进行单元测试。 3、 对上述每个...
本文将详细讲解C#中链表的实现，并特别关注加强版链表，它支持了C#语言的`foreach`语句进行遍历。这对于初学者来说是一个很好的实践案例。 链表是一种线性数据结构，不同于数组，它的元素不是在内存中连续存储的。...
c#语言实现链表基本功能，包括添加元素、删除元素和遍历链表的功能。
在C#中，`System.Collections.Generic`命名空间提供了一个名为`LinkedList<T>`的链表类，它实现了`IEnumerable<T>`接口，支持LINQ查询。`LinkedListNode<T>`类代表链表中的一个节点，包含`Value`属性用于存储数据，...
使用Unity3D和C#实现的基于十字链表的AOI逻辑。 AOI based on orthogonal linked list which is implemented by C# in Unity3D. 1. 概述 AOI（Area Of Interest）是常用于游戏的一种算法，使用的是空间划分的思想...
本资源提供了C#语言实现的三种不同类型的链表：单链表、双向链表和循环链表的完整源码，这对于理解和实践C#编程中的链表操作极其有价值。 首先，我们来详细探讨单链表。单链表是一种线性数据结构，其中每个节点包含...
在本文中，我们将深入探讨如何利用链表来实现这个功能，并扩展相关的C#链表知识。 首先，我们需要理解链表的基本概念。链表不同于数组，它不连续存储数据，而是通过节点之间的引用连接。每个节点包含两部分：数据...
了解如何在C#中实现常见的数据结构（如链表、二叉树等）对于开发者来说是非常有价值的技能。 #### 二、链表在C#中的实现 链表是一种线性数据结构，其中元素按照特定顺序存储，并通过指针链接在一起。链表在内存中...