C#数据结构与算法揭秘三 链表

上文我们讨论了一种最简单的线性结构——顺序表，这节我们要讨论另一种线性结构——链表。

什么是链表了，不要求逻辑上相邻的数据元素在物理存储位置上也相邻存储的线性结构称之为链表。举个现实中的例子吧，假如一个公司召开了视频会议的吧，能在北京总公司人看到上海分公司的人，他们就好比是逻辑上相邻的数据元素，而物理上不相连。这样就好比是个链表。 链表分为①单链表，②单向循环链表，③双向链表，④双向循环链表。

介绍各种各样链表之前，我们要明白这样一个概念。什么是结点。在存储数据元素时，除了存储数据元素本身的信息外，还要存储与它相邻的数据元素的存储地址信息。这两部分信息组成该数据元素的存储映像(image)，称为结点(node)。在c语言这些面向过程语言中，实现节点是通过指针的形式，在。net中，是通过模拟指针——类对象嵌套的形式。

然后，首先，介绍单链表。如果结点的引用域只存储该结点直接后继结点的存储地址， 则该链表叫单链表(singly linked list)。把该引用域叫 next。单链表结点的结构如图所示，图中 data表示结点的数据域。

现实中，就像一队盲人过马路。如图所示

   

把单链表结点看作是一个类，类名为 node<t>。单链表结点类的实现如下所示。 

public class node<t>
{
//一队盲人过马路 存储的是盲人的姓名
private t data; //数据域 存储数据的对象
//一队盲人过马路 指向的是下一个盲人对象。
private node<t> next; //引用域 指向下一个对象

//构造器
public node(t val, node<t> p)
{
data = val;
next = p;
}

//构造器
public node(node<t> p)
{
next = p;
}

//构造器
public node(t val)
{
data = val;
next = null;
}

//构造器
public node()
{
data = default(t);
next = null;
}

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

//引用域属性
public node<t> next
{
get
{
return next;
}
set
{
next = value;
}
}
}

下图是线性表(a1,a2,a3,a4,a5,a6)对应的链式存储结构示意图。

单链表类 linklist<t>源代码的实现说明如下所示。首先申明一下，他继承与ilistds这个接口。

//这是一个盲人过马路的类的模拟

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;

不懂的一切尽在图例中

这个方法的算法复杂度是o(n)
}

//就是在一队中增加了插队的人员

//在单链表的第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;
}

一切尽在图例中

}

 这个方法的算法复杂度o(n)

 

//删除单链表的第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;
}
此步骤为o(1)  

 

//不是的头位置的吧，就寻找相应位置的节点，在进行删除。他这个排队前面的人指向后面的人。这就是新的队伍了  没找到，就返回错误。
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);
}

不懂的如图所示：

此方法的运行时间复杂度是o(n)
}

//获得单链表的第i个数据元素

//知道队伍 我要查询出队伍中第n个人是那位，
public t getelem(int i)
{

//如果是空的就返回为错误的结果
if (isempty())
{
console.writeline("list is empty!");
return default(t);
}

//从图接点数  第n个的结果了
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);
}
}

不懂的，一切尽在图例中。

此方法的时间的复杂度是o(n)

//我要查询张山的位于队伍的第几个位置

//在单链表中查找值为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;

这个算法复杂度是o(n2)
}

}

这节我们讨论链表的基本操作，并且画图以证明，下届中我们将讨论双向链表，环形链表 应用举例。