发信人: nice (春天), 信区: DotNET        
标  题: C#快餐－9
发信站: BBS 水木清华站 (Thu Jul 26 02:09:54 2001)

Lesson 9.  Linked List

   We have learned enough C# machinery to write a simple data structure  
- linked list. Linked lists are used to save memory at a loss of speed.  
The are many different implementations of linked lists. The one bellow has
a head node and a tail node. These are dummy nodes which point to the first  
and last elements of the list respectively. List is empty when the head node  
points to the tail node. The tailnode points to itself.

using System;
class OutOfRange: Exception{}
class ListNode
{
    public int data;
    public ListNode next;
};
class List
{
    ListNode headnode, tailnode;
    //list constructor initializes headnode with 0 and makes it point to the
tail marker
    //headnode and tailnode do not contain any actual elements; tailnode alw
ays points to itself
    public List ()
    {
        headnode = new ListNode (); // List constructor allocates memory for
headnode and tailnode
        headnode.data = 0;
        //and does the initialization
        tailnode = new ListNode ();
        tailnode.data = 0;
        headnode.next = tailnode;
        tailnode.next = tailnode;
    }
    // *move_to_node returns pointer to the kth element in the linked list o
r error if list
    //has less than k elements; headnode and tailnode are not counted as ele
ments of the list
    public ListNode move_to_node (int k)
    {
        int i;
        ListNode temp = headnode;
        for (i = 0; i < k && temp != tailnode; i++)
        {
            temp = temp.next;
        }
        try {
            if (i < k)
                throw (new OutOfRange() );
        }
        catch (Exception e)
        {
            Console.WriteLine("Exception :{}", e);
        }
        return temp;
    }
    //insert node a_node after position k.headnode has 0s position;
    public void insert_node (ListNode a_node, int position)
    {
        a_node.next = move_to_node(position).next;
        move_to_node(position).next = a_node;
     }
     //delete node at position and reclaim its memory
    public void delete_node (int position)
    {
        //check that a_node is not a headnode or a tailnode; exit if it is
         try
        {
            if (position == 0 || position > list_length ()) // Headnode or t
ailnode cannot be deleted
                 throw (new OutOfRange());
        }
        catch (Exception e)
        {
             Console.WriteLine("Exception :{}", e);
        }
        ListNode temp;
        temp = move_to_node (position);
        move_to_node (position - 1).next = move_to_node (position + 1);
    }
    //return # of elements in the linked list excluding headnode and tailnod
e
    public int list_length()
    {
        int i;
        ListNode temp = headnode;
        for (i = 0; temp != tailnode; i++)
        {
            temp = temp.next;
         }
        return i - 1;
    }
    //return 1 position of integer k in list of length n
    int search(int k, int n)
    {
        try {
            if (list_length () > 0) // this assertion cheks that list exist
                 throw (new OutOfRange() );
        }
        catch (Exception e)
        {
            Console.WriteLine ("Exception :{}", e);
        }
        ListNode temp = headnode;
        temp = headnode.next;
        // move along the list till integer k is found or tailnode encounter
ed
        for (; temp.data != k && temp != tailnode; temp = temp.next)
            ;
        if (temp == tailnode)
        {
            // k is not in the list
            return 0;
        }
        else {
            // k is in the list;
            return 1;
        }
    }
    public void show_list()
    {
        ListNode temp = headnode;
        temp = headnode.next;
        for (; temp != tailnode; temp = temp.next)
            Console.WriteLine (temp.data);
    }
};
class Test{
    public static void Main ()
    {
        List first_list = new List ();
        ListNode node = new ListNode ();
        node.data = 1;
        first_list.insert_node (node, 0); // insert first node into list
        for (int i = 2; i < 11; i++) { // insert 9 more nodes
            node = new ListNode ();
            node.data = i;
            first_list.insert_node (node, 0);
        }
        first_list.show_list (); //show contents of the list
    }
}

Note how similar above implementation of the linked list to ones we have in  
C++. Just get rid of pointers, delete statements change cout to  
Console.WriteLine and you are ready to go.

--

※ 修改:·walts 於 Jul 26 10:16:51 修改本文·[FROM: 166.111.142.118]
※ 来源:·BBS 水木清华站 smth.org·[FROM: 166.111.176.234]
上一篇
返回上一页
回到目录
回到页首
下一篇