數據結構(C#)--單鏈表

2007年最後一個月在忙碌度過了，最近在網上下了一本C#版本的數據結構的電子書，正好我也打算在把數據結構在過一遍，剛好可以看這本，還可以提高一下英文的閱讀能力。

書名是《DATA STRUCTURES AND ALGORITHMS USING C#》，作者：MICHAEL MCMILLAN

以後我會陸續把這本數的心得發上來，同時也把自己親手實踐過的代碼發上來，大家一起學習，一起進步。如果有什麼錯誤，大家可以發郵件或者留言給我。謝謝。由於該書的結構和我們一般教材的結構不是很一樣，所以我按照一般教材的順序，先從鏈表開始，原書鏈表是在第十一章才講的。書中代碼有問題的地方我會在注釋中標注出來。

 

namespace DataStruct
...{
    //定義單鏈表的表頭
    public class Node
    ...{
        //存儲數據，定義為基類，可以存不同類型的數據
        public Object Element;
        //指向下一個結點的引用
        public Node Link;

        //構造空結點
        public Node()
        ...{
            this.Element = null;
            this.Link = null;
        }
        //帶參數的構造器
        public Node(Object element)
        ...{
            this.Element = element;
            this.Link = null;
        }
    }

    public class LinkedList
    ...{
        //此處原書有誤，不應該設置為peotected，這樣會導致結點沒有實例化
        public Node Header;
        public LinkedList()
        ...{
            Header = new Node("header");
        }

        //查找鏈表中的元素
        private Node Find(Object item)
        ...{
            Node Current = new Node();
            Current = Header;
            //書中此處代碼有誤
            //while(Current.header !=item)
         while (Current.Element != item)
            ...{
                Current = Current.Link;
            }
            return Current;
        }

        //在鏈表中插入元素
        public void InsertNode(Object newItem,Object after)
        ...{
            Node Current = new Node();
            Node NewNode = new Node(newItem);
            Current = Find(after);
            if (Current != null)
            ...{
                NewNode.Link = Current.Link;
                Current.Link = NewNode;
            }
        }

        
        public Node FindPrevious(Object n)
        ...{
            Node Current = Header;
            while (!(Current.Link == null) && (Current.Link.Element != n))
            ...{
                Current = Current.Link;
            }
            return Current;
        }

        //刪除結點
        public void Remove(Object item)
        ...{
            Node P = FindPrevious(item);
            if (!(P.Link == null))
            ...{
                P.Link = P;
            }
        }

        //打印鏈表
        public void PrintList()
        ...{
            Node Current = new Node();
            Current = this.Header;
            while (Current.Link != null)
            ...{
                Console.WriteLine(Current.Link.Element);
                Current = Current.Link;
            }
        }
        
    }

    class Program
    ...{
        static void Main(string[] args)
        ...{
            //實例化結點
            Node FirstNode = new Node("Tommy");
            Node SecondNode = new Node("weiwei");
            Int32 Num = 5;
            //因為我們定義結點的時候是用object類型，所以結點可以存儲不同類型
            Node ThirdNode = new Node(Num);
            FirstNode.Link = SecondNode;
            SecondNode.Link = ThirdNode;
            ThirdNode.Link = null;
            LinkedList MyList = new LinkedList();
            //將頭結點指向第一個結點
            MyList.Header.Link = FirstNode;
            //插入結點
            MyList.InsertNode("advantech", "weiwei");
            MyList.InsertNode("插入鏈表", "Tommy");
            //打印鏈表中的結點元素
            MyList.PrintList();
            Console.ReadLine();
        }
    }
}