数据结构链表实现
单向链表实现
公共接口
namespace AF
{
public interface IListDS<T>
{
/// <summary>
/// 长度
/// </summary>
int Length { get; }
/// <summary>
/// 索引获取
/// </summary>
/// <param name="index"></param>
T this[int index] { get; }
/// <summary>
/// 清空
/// </summary>
void Clear();
/// <summary>
/// 添加元素
/// </summary>
/// <param name="data"></param>
void Add(T data);
/// <summary>
/// 插入元素
/// </summary>
/// <param name="data"></param>
/// <param name="index"></param>
void Insert(T data,int index);
/// <summary>
/// 删除元素
/// </summary>
/// <param name="index"></param>
T Delete(int index);
/// <summary>
/// 根据数据获取下标
/// </summary>
/// <param name="data"></param>
/// <returns></returns>
int Loacte(T data);
/// <summary>
/// 根据下标获取数据
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
T GetElem(int index);
/// <summary>
/// 判断为空
/// </summary>
/// <returns></returns>
bool IsEmpty();
}
}Node节点类实现
namespace AF
{
public class Node<T> : INode<T>
{
private T data;
private Node<T> next;
public T Data
{
get => data;
set => data = value;
}
public Node<T> Next
{
get => next;
set => next = value;
}
public bool HasNext()
{
return next != default;
}
public Node()
{
}
public Node(T data)
{
this.data = data;
}
public Node(Node<T> next)
{
this.next = next;
}
public Node(T data,Node<T> next)
{
this.data = data;
this.next = next;
}
}
}LinkList实现
using System;
using System.Diagnostics;
using System.Security.Policy;
namespace AF
{
public class LinkList<T> : IListDS<T>
{
private Node<T> head;
public Node<T> Head => head;
private int length;
public int Length { get => length; }
private Node<T> GetNodeByIndex(int index)
{
Node<T> temp = head;
for (int i = 1; i <= index; i++)
{
temp = temp.Next;
}
return temp;
}
public T this[int index] => GetNodeByIndex(index).Data;
public void Clear()
{
head = null;
length = 0;
}
public void Add(T data)
{
Node<T> newNode = new Node<T>(data);
//为空节点时
if (IsEmpty())
{
head = newNode;
length++;
return;
}
Node<T> temp = head;
while (temp.HasNext())
{
temp = temp.Next;
}
length++;
temp.Next = newNode;
}
public void Insert(T data, int index)
{
Node<T> newNode = new Node<T>(data);
//插入改变的是头节点时
if (index == 0)
{
if (!IsEmpty())
newNode.Next = head;
head = newNode;
length++;
}
else
{
//否则先获取上一个节点
Node<T> prevTemp = GetNodeByIndex(index - 1);
if (prevTemp.HasNext())
newNode.Next = prevTemp.Next;
prevTemp.Next = newNode;
length++;
}
}
public T Delete(int index)
{
T data = default;
//删除的是头节点时
if (index == 0)
{
if (head == default)
return default;
data = head.Data;
if (head.HasNext())
head = head.Next;
else
head = default;
length--;
return data;
}
Node<T> prevTemp = GetNodeByIndex(index-1);
if (!prevTemp.HasNext())
return default;
data = prevTemp.Next.Data;
if (prevTemp.Next.HasNext())
prevTemp.Next = prevTemp.Next.Next;
else
prevTemp.Next = default;
length--;
return data;
}
public int Loacte(T data)
{
int index = 0;
if (IsEmpty())
return -1;
Node<T> temp = head;
while (temp.HasNext())
{
if (temp.Data.Equals(data))
return index;
temp = temp.Next;
index ++;
}
return -1;
}
public T GetElem(int index)
{
return this[index];
}
public bool IsEmpty()
{
return head == default;
}
}
}循环链表实现
using System;
using System.Collections.Generic;
namespace AF
{
public class LoopLinkList<T> : IListDS<T>
{
private Node<T> head;
private Node<T> rear;
public Node<T> Rear => rear;
private int length;
public int Length { get => length; }
public T this[int index] => GetNodeByIndex(index).Data;
private Node<T> GetNodeByIndex(int index)
{
Node<T> temp = head;
index %= length;
for (int i = 1; i <= index; i++)
{
temp = temp.Next;
}
return temp;
}
public void Clear()
{
head = null;
rear = null;
length = 0;
}
public void Add(T data)
{
Node<T> newNode = new Node<T>(data);
if (head == default)
{
head = newNode;
head.Next = head;
rear = head;
length++;
return;
}
newNode.Next = head;
rear.Next = newNode;
rear = newNode;
length++;
}
public void Insert(T data, int index)
{
Node<T> newNode = new Node<T>(data);
index %= length;
if (index == 0)
{
//不为空节点时
if (!IsEmpty())
newNode.Next = head;
else
{
newNode.Next = newNode;
rear = newNode;
}
head = newNode;
//只有一个节点时
if (rear == head.Next)
{
rear = head.Next;
}
rear.Next = head;
length++;
return;
}
Node<T> prevTemp = GetNodeByIndex(index - 1);
if(prevTemp.HasNext())
newNode.Next = prevTemp.Next;
prevTemp.Next = newNode;
if (index == length - 1)
rear = newNode;
length++;
}
public T Delete(int index)
{
T data = default;
index %= length;
if (index == 0)
{
if (head == default)
return default;
data = head.Data;
if (head.HasNext() && head.Next != head)
{
head = head.Next;
rear.Next = head;
}
else
{
head = default;
rear = default;
}
length--;
return data;
}
Node<T> prevTemp = GetNodeByIndex(index - 1);
if (prevTemp.HasNext())
return default;
data = prevTemp.Data;
if (prevTemp.Next != rear)
prevTemp.Next = prevTemp.Next.Next;
else
{
prevTemp.Next = head;
rear = prevTemp;
}
length--;
return data;
}
public int Loacte(T data)
{
if (IsEmpty())
return -1;
int index = 0;
Node<T> temp = head;
do
{
if (temp.Data.Equals(data))
return index;
temp = temp.Next;
index++;
} while (temp!=head);
return -1;
}
public T GetElem(int index)
{
return this[index];
}
public bool IsEmpty()
{
return head == default || rear == default;
}
}
}双向链表实现
using System;
namespace AF
{
public class EvenLinkList<T> : IListDS<T>
{
private Node<T> head;
public Node<T> Head;
private int length;
public int Length => length;
public T this[int index] => GetNodeByIndex(index).Data;
/// <summary>
/// 检测输入下标，不合法给出报错信息
/// </summary>
/// <param name="Index">输入的下标</param>
/// <param name="isLoop">是否循环遍历操作</param>
/// <param name="isAdd">添加元素链表可以为空</param>
/// <exception cref="Exception">链表越界问题</exception>
private void CheckIndex(int Index,bool isLoop = false,bool isAdd =false)
{
if (Index < 0 || (!isLoop && Index >= length) || (!isAdd && IsEmpty()))
{
throw new System.Exception("下标越界或者链表为空");
return;
}
}
/// <summary>
/// 根据下标获取节点信息
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
private Node<T> GetNodeByIndex(int index)
{
CheckIndex(index,true);
//防止多余的遍历
index %= length;
int mid = length / 2;
Node<T> temp = head;
if(index<=mid)
for (int i = 1; i <= index; i++)
{
temp = temp.Next;
}
else
{
int prevIndex = length - index;
for (int i = 1; i <= prevIndex; i++)
{
temp = temp.Prev;
}
}
return temp;
}
public void Clear()
{
head = null;
length = 0;
}
public void Add(T data)
{
Node<T> newNode = new Node<T>(data);
//为空的情况
if (IsEmpty())
{
head = newNode;
head.Next = head;
head.Prev = head;
length++;
return;
}
newNode.Prev = head.Prev;
newNode.Next = head;
head.Prev.Next = newNode;
head.Prev = newNode;
length++;
}
public void Insert(T data, int index)
{
CheckIndex(index,false,true);
if (index == 0 && IsEmpty())
{
Add(data);
return;
}
Node<T> newNode = new Node<T>(data);
Node<T> temp = GetNodeByIndex(index);
newNode.Prev = temp.Prev;
newNode.Next = temp;
temp.Prev.Next = newNode;
temp.Prev = newNode;
if (index == 0)
head = newNode;
length++;
}
public T Delete(int index)
{
CheckIndex(index);
T data = default;
if (index == 0 && length == 1)
{
data = head.Data;
head = default;
length--;
return data;
}
Node<T> temp = GetNodeByIndex(index);
data = temp.Data;
temp.Prev.Next = temp.Next;
temp.Next.Prev = temp.Prev;
length--;
return data;
}
public int Loacte(T data)
{
if (IsEmpty())
return -1;
int index = 0;
Node<T> temp = head;
do
{
if (temp.Data.Equals(data))
return index;
temp = temp.Next;
index++;
} while (temp != head);
return -1;
}
public T GetElem(int index)
{
return this[index];
}
public bool IsEmpty()
{
return head == default;
}
}
}本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 雪夜の自我救赎！
微信- 支付宝
评论
ValineDisqus
