找老师要java的数据结构代码结果发来了这个。
单链表类LinkList<T>的实现说明如下所示。
public class LinkList<T> : IListDS<T> {
private Node<T> head; //单链表的头引用
//头引用属性
public Node<T> Head
{
get
{
return head;
}
set
{
head = value;
}
}
//构造器
public LinkList()
{
head = null;
}
//求单链表的长度
public int GetLength()
{ Node<T> p = head;
int len = 0;
while (p != null)
{
++len;
p = p.Next;
}
return len;
}
//清空单链表
public void Clear()
{
head = null;
}
//判断单链表是否为空
public bool IsEmpty()
{
if (head == null)
{
return true;
}
else
{
return false;
}
}
//在单链表的末尾添加新元素
public void Append(T item)
{
Node<T> q = new Node<T>(item);
Node<T> p = new Node<T>();
if (head null)
{
head = q;
return;
}
p = head;
while (p.Next != null)
{
p = p.Next;
}
p.Next = q;
}
//在单链表的第i个结点的位置前插入一个值为item的结点
public void Insert(T item, int i)
{
if (IsEmpty() || i < 1)
{
Console.WriteLine("List is empty or Position is error!");
return;
}
if (i == 1)
{
Node<T> q = new Node<T>(item);
q.Next = head;
head = q;
return;
}
Node<T> p = head;
Node<T> r = new Node<T>();
int j = 1;
while (p.Next != null&& j < i)
{
r = p;
p = p.Next;
++j;
}
if (j i)
{
Node<T> q = new Node<T>(item);
q.Next = p;
r.Next = q;
}
}
//在单链表的第i个结点的位置后插入一个值为item的结点
public void InsertPost(T item, int i)
{
if (IsEmpty() || i < 1)
{
Console.WriteLine("List is empty or Position is error!");
return;
}
if (i == 1)
{
Node<T> q = new Node<T>(item);
q.Next = head.Next;
head.Next = q;
return;
}
Node<T> p = head;
int j = 1;
while (p != null&& j < i)
{
p = p.Next;
++j;
}
if (j i)
{
Node<T> q = new Node<T>(item);
q.Next = p.Next;
p.Next = q;
}
}
//删除单链表的第i个结点
public T Delete(int i)
{
if (IsEmpty()|| i < 0)
{
Console.WriteLine("Link is empty or Position is
error!");
return default(T);
}
Node<T> q = new Node<T>();
if (i 1)
{
q = head;
head = head.Next;
return q.Data;
}
Node<T> p = head;
int j = 1;
while (p.Next != null&& j < i)
{
++j;
q = p;
p = p.Next;
}
if (j i)
{
q.Next = p.Next;
return p.Data;
}
else
{
Console.WriteLine("The ith node is not exist!");
return default(T);
}
}
//获得单链表的第i个数据元素
public T GetElem(int i)
{
if (IsEmpty())
{
Console.WriteLine("List is empty!");
return default(T);
}
Node<T> p = new Node<T>();
p = head;
int j = 1;
while (p.Next != null&& j < i)
{
++j;
p = p.Next;
}
if (j i)
{
return p.Data;
}
else
{
Console.WriteLine("The ith node is not exist!");
return default(T);
}
}
//在单链表中查找值为value的结点
public int Locate(T value)
{
if(IsEmpty())
{
Console.WriteLine("List is Empty!");
return -1;
}
Node<T> p = new Node<T>();
p = head;
int i = 1;
while (!p.Data.Equals(value)&& p.Next != null)
{
P = p.Next;
++i;
}
return i;
}
}
1、求单链表的长度
求单链表的长度与顺序表不同。顺序表可以通过指示表中最后一个数据元素
的 last 直接求得，因为顺序表所占用的空间是连续的空间，而单链表需要从头
引用开始，一个结点一个结点遍历，直到表的末尾。
public int GetLength()
{
Node<T> p = head;
int len = 0;
while (p != null)
{
++len;
p = p.Next;
}
return len;
}
2、清空操作
清空操作是指清除单链表中的所有结点使单链表为空，此时，头引用 head
为null。
清空单链表的算法实现如下：
public void Clear()
{
head = null;
} 3、判断单链表是否为空
如果单链表的头引用为null，则单链表为空，返回true，否则返回false。
判断单链表是否为空的算法实现如下：
public bool IsEmpty()
{
if (head == null)
{
return true;
}
else
{
return false;
}
}
4、附加操作
单链表的附加操作也需要从单链表的头引用开始遍历单链表，直到单链表的
末尾，然后在单链表的末端添加一个新结点。
附加操作的算法实现如下：
public void Append(T item)
{
Node<T> q = new Node<T>(item);
Node<T> p = new Node<T>();
if (head null)
{
head = q;
return;
}
p = head;
while (p.Next != null)
{
p = p.Next;
}
p.Next = q;
}
单链表的插入操作是指在表的第 i 个位置结点处插入一个值为 item 的新结
点。插入操作需要从单连表的头引用开始遍历，直到找到第i个位置的结点。插
入操作分为在结点之前插入的前插操作和在结点之后插入的后插操作。
（1）前插操作
前插操作需要查找第i个位置的结点的直接前驱。设p指向第i个位置的
结点，q 指向待插入的新结点，r 指向 p 的直接前驱结点，将 q 插在 p 之前的操
作。如果要在第一个结点之前插入新结点，则需要把p结点的地址
保存在q的引用域中，然后把p的地址保存在头引用中。
public void Insert(T item, int i)
{
if (IsEmpty() || i < 1)
{
Console.WriteLine(“List is empty or Position is error!”);
return;
}
if (i == 1)
{
Node<T> q = new Node<T>(item);
q.Next = head;
head = q;
return;
}
Node<T> p = head;
Node<T> r = new Node<T>();
int j = 1;
while (p.Next != null&& j < i)
{
r = p;
p = p.Next;
++j;
}
if (j i)
{
Node<T> q = new Node<T>(item);
q.Next = p;
r.Next = q;
}
else
{
Console.Writeline(“Position is error!”);
}
return;
}
（2）后插操作：
设p指向第i个位置的结点，q指向待插入的新结点，将q插在p之后
单链表的后插操作的算法实现如下：
public void InsertPost(T item, int i)
{
if (IsEmpty() || i < 1)
{
Console.WriteLine(“List is empty or Position is error!”);
return;
}
if (i == 1)
{
Node<T> q = new Node<T>(item);
q.Next = head.Next;
head.Next = q;
return;
}
Node<T> p = head;
int j = 1;
while (p.Next != null&& j < i)
{
p = p.Next;
++j;
}
if (j i)
{
Node<T> q = new Node<T>(item);
q.Next = p.Next;
p.Next = q;
}
else
{
Console.WriteLine(“Position is error!”);
}
return;
}
6、删除操作
单链表的删除操作是指删除第 i 个结点，返回被删除结点的值。删除操作
也需要从头引用开始遍历单链表，直到找到第i个位置的结点。如果i为1，则
要删除第一个结点，则需要把该结点的直接后继结点的地址赋给头引用。对于其
它结点，由于要删除结点，所以在遍历过程中需要保存被遍历到的结点的直接前
驱，找到第i个结点后，把该结点的直接后继作为该结点的直接前驱的直接后继。
删除操作的算法实现如下：
public T Delete(int i)
{
if (IsEmpty()|| i < 0)
{
Console.WriteLine("Link is empty or Position is
error!");
return default(T);
} Node<T> q = new Node<T>();
if (i 1)
{
q = head;
head = head.Next;
return q.Data;
}
Node<T> p = head;
int j = 1;
while (p.Next != null&& j < i)
{
++j;
q = p;
p = p.Next;
}
if (j i)
{
q.Next = p.Next;
return p.Data;
}
else
{
Console.WriteLine("The ith node is not exist!");
return default(T);
}
}
代码是c#的，将就看看吧