今天受一个帖子的刺激,再次复习起了数据结构与算法,那本《数据结构与算法(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#单向链表的实现的源码
此表现形式符合单向链表的思路,设计清晰。拓展方法时在CList类里写。
c#单向链表的实现,帮助大家学习,程序完全可以运行,
实现双向链表,符合双向链表的思路且易懂,拓展方便。
C#双向链表的实现的源码
阶段练习:实现链表(LinkedList) 简介:写一个链表的数据结构,要求实现IList接口。 具体要求: 1、 使用代码规范。 2、 至少对IList中的Add,Remove,Insert,Indexer,IEnumerator进行单元测试。 3、 对上述每个...
该代码应用到了模板、接口、结构体等,具有较好的复用性
不使用List,使用泛型类实现单链的增删。
本来是自己有一个小东西需要链表存储,从网上找的资源,发现有bug,该资源bug已修复
集合了对C#单向链表的实现。让大家熟悉对C#操作
c#链表实现求两个多项式的和,例子比较简单,有些功能还没有实现,请谅解
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运...
主要介绍了C#实现的简单链表类,涉及C#针对链表的定义、实现及链表节点的增加、删除与修改技巧,具有一定参考借鉴价值,需要的朋友可以参考下
主要介绍了C#双向链表LinkedList排序实现方法,涉及C#双向链表的定义与排序技巧,具有一定参考借鉴价值,需要的朋友可以参考下
( 【C#实例】链表实现自制List类
使用Unity3D和C#实现的基于十字链表的AOI逻辑。 AOI based on orthogonal linked list which is implemented by C# in Unity3D. 1. 概述 AOI(Area Of Interest)是常用于游戏的一种算法,使用的是空间划分的思想...
操作系统c++编程实现安全型双向链表,线程的创建,利用线程对链表进行增删改操作,并检验结果是否正确
本文实例讲述了C#通过链表实现队列的方法。分享给大家供大家参考。具体实现方法如下: public class Node { public int Data { get; set; } public Node Next { get; set; } public Node(int data) { this....