読み込んでいます...

在上以节中讲解了单链表的开发和一些操作方法,从上一节中可以看出,单链表在有指针特性的编程语言中特别有用,而在没有指针的编程语言中并不是特别有用,特别是C#和JAVA这类的高级编程语言。如果要使用链表,则可以使用静态链表,静态链表结构如下图所示。

在静态链表中,其链表的结构同样包括data和next。其中data是存放数据的部分,而next是用来存放指针,上图的结构声明是一个足够大的结构数组,在结构中,并不能从前面的0、1、2、3、4序号进行查看,而需要从next数据进行查看。例如上面结构中链表的一个数据是a4,它的下一个数据就是数据的第一个元素(由a4.next=1可知),由此可以推出a2就是链表中a4的下一个元素,最后其结构可以以此类推。

在创建静态链表时,可以通过程序实现,这里只是创建一个固定的静态链表并执行插入和删除操作,示例代码如下所示。

public struct Node  
{  
    
public int data;  
    
public int next;  
}  

Node[] sd = new Node[100];  

protected void CreateNode()  
{  
    
for (int i = 0; i < 5; i++)  
    {  
        sd[i].data
= i;  
        sd[i].next
= i + 1;  
    }  
    sd[
5].next = -1;
}

上述代码创建了一个长度为5的链表,创建后如下图所示。

在创建后,其中a1是第一个元素,a1的下一个元素为a2,依次类推,为了程序理解和编写方便,这里可以创建一个类似顺序表的结构。在执行数据插入时,可以通过更改相应的next值进行结构的插入,示例代码如下所示。

protected void Insert(int place,int data,int l)  
{  
    
//首先找到位置的前一个节点  
    sd[l].data = data;  
    sd[l].next
= l+1;  
    sd[l
+ 1].next = -1;  
    sd[place].next
= l;  
    
//然后找到位置的后一个节点  
}

执行插入的方法非常简单,例如要在节点1处插入数据,那么节点0的next值应该等于节点1,而节点1的next值应该等于节点0的next值,在执行插入操作后,结构体的结构如下图所示。

修改后,a2的下一个节点是a6,而a6的下一个节点为a3,则说明了在a2和a3之间进行了节点的插入。

当需要执行节点的删除时,只需要修改删除节点的指针即可,例如删除第一个节点,则只需将第0个节点的next值更改为第一个节点的next值即可,但是值得注意的是,如果执行了删除操作,其中并没有真正意义上删除数组中的数据,只是暂时屏蔽了(与C++不同的是,对于创建的节点可以使用Delete进行删除),所以在执行删除后,还需要依次进行数据的覆盖,即将当前位置后的数据覆盖前面的数据,示例代码如下所示。

protected void Delete(int place,int n)  
{  
    sd[place
- 1].next = sd[place].next;  
    
int i=0;  
    
while (sd[i].next != -1)  
    {  
        sd[place]
= sd[place + 1];  
        i
++;  
        place
++;  
    }  
}

在执行插入、删除时,还需要查找是否超出链表的长度,示例代码如下所示。

protected int GetLength()  
{  
    
int i = 0;  
    
while (sd[i].next != -1)  
    {  
        i
++;  
    }  
    
return i;  
}

在调用中,很多情况都需要获取链表的长度并进行判断,这里就不详细编写了,主函数代码如下所示。

static void Main(string[] args)  
{  
    Program p
= new Program();  
    p.CreateNode();  
    Console.WriteLine(
"插入前链表的长度为" + p.GetLength());  
    p.Insert(
0, 100, p.GetLength());  
    Console.WriteLine(
"插入后链表的长度为" + p.GetLength());  
    p.Delete(
1,p.GetLength());  
    Console.WriteLine(
"删除后链表的长度为" + p.GetLength());  
    p.OutPut();  
    Console.ReadKey();  
}

由于在创建静态链表时,是自动创建,这里就需要读者了解了基本步骤后,自行更改其中的代码自行实现咯。

435路过 2评论 数据结构 阅读全文..
  1. cs@ss @

    如今这样的博客太多了
    如今这样的无技术含量的文章也太多了

  2. 置顶的更新,文章汇总 : GuoJing's Blog | 用心对待每一行代码 @

    [...] 潜心学习数据结构 – C#语言描述(四:静态链表) [...]

:-D :-? 8) :cry: 8-O :lol: :-x :-| :?: :-P :oops: :roll: :( :) :-o :wink: more »