데이터 구조 - 선형 표 (순서 실현, 체인 실현, 다항식 계산)

13018 단어 교과 과정 설계
최근 에 데이터 구 조 를 하고 있 는데 선생님 께 서 대상 을 완전히 대상 으로 하 라 고 하 셔 서 C \ # 인터페이스 로 프로 그래 밍 을 하 셨 습 니 다.
코드 는 다음 과 같 습 니 다. 컴 파일 에 문제 가 없습니다. ADT 는 책 에 있 는 것 이 고 다른 것 은 자신 이 쓴 것 입 니 다.
 public delegate bool method(T a, T b);
    public delegate bool visit(T a);
    ///   
    interface iList
    {

        void InitList();

        void DestroyList();

        void ClearList();

        bool ListEmpty();

        int ListLength();

        T GetElem(int pos);

        int LocateElem(T elem, method fun);

        void PriorElem(T elem, ref T pre);

        void Next(T elem, ref T next);

        bool ListInsert(int i, T elem);

        bool ListDelete(int i, ref T elem);

        bool ListTraverse(visit tra);
    }
    /// 
    ///         
    /// 
    /// 
    ///     
    class SqList : iList
    {
        static int initSize = 50;
        static int sizeIncr = 20;
        T[] data = null;
        int cur = 0;
        int listSize = 0;
        int listMaxCap = initSize;

        public void InitList()
        {
            data = new T[50];
        }

        public void DestroyList()
        {
            listMaxCap = 50;
            data = null;
        }

        public void ClearList()
        {
            cur = 0;

        }

        public bool ListEmpty()
        {
            bool res = false;
            if (0 == listSize)
            {
                res = true;
            }
            return res;
        }

        public int ListLength()
        {
            return listSize;
        }

        public T GetElem(int pos)
        {
            if (pos < cur && pos > 0)
            {
                T tmp = data[pos];
                return tmp;
            }
            else
            {
                return default(T);
            }
        }

        public int LocateElem(T elem, method fun)
        {
            int pos = 0;
            for (int i = 0; i < listSize; i++)
            {
                if (fun(elem, data[i]))
                {
                    return pos;
                }
            }
            return -1;

        }

        public void PriorElem(T elem, ref T pre)
        {
            for (int i = 0; i < listSize; i++)
            {
                if (elem.Equals(data[i]))
                {
                    if (i > 0)
                    {
                        pre = data[i - 1];
                    }
                    else
                    {
                        pre = default(T);
                    }
                }
                else
                {
                    pre = default(T);
                }
            }
        }

        public void Next(T elem, ref T next)
        {
            for (int i = 0; i < listSize; i++)
            {
                if (elem.Equals(data[i]))
                {
                    if (i < listSize - 1)
                    {
                        next = data[i + 1];
                    }
                    else
                    {
                        next = default(T);
                    }
                }
                else
                {
                    next = default(T);
                }

            }
        }

        public bool ListInsert(int i, T elem)
        {
            bool res = false;
            if (System.Math.Abs((listSize - (listMaxCap - 1))) < 5)
            {
                T[] tmp = new T[listMaxCap];
                data.CopyTo(tmp, 0);
                data = new T[listMaxCap + sizeIncr];
                listMaxCap += sizeIncr;
                tmp.CopyTo(data, 0);
            }
            if (i < listSize && i > 0)
            {
                for (int j = listSize; j >= i - 1; j--)
                {
                    data[j] = data[j - 1];
                }
                data[i - 1] = elem;
                ++listSize;
                res = true;
            }
            return res;
        }

        public bool ListDelete(int i, ref T elem)
        {
            bool res = false;
            if (i >= 0 && i < listSize)
            {
                elem = data[i - 1];
                for (int j = i - 1; j < listSize; j++)
                {
                    data[j] = data[j + 1];
                }
                --listSize;
                res = true;
            }
            return res;
        }

        public bool ListTraverse(visit tra)
        {
            bool res = false;
            for (int i = 0; i < listSize; i++)
            {
                if (!tra(data[i]))
                {
                    res = false;
                }
                else
                {
                    res = true;
                }
            }
            return res;
        }
    }
    class singleLinkedList
    {
        public T data;
        public singleLinkedList next;
        public singleLinkedList()
        {
            data = default(T);
            next = null;
        }
    }
    /// 
    ///         
    /// 
    /// 
    public class LinkedList : iList
    {
        singleLinkedList data;
        int listSize = 0;

        public void InitList()
        {
            data = new singleLinkedList();
        }

        public void DestroyList()
        {
            data = null;
        }

        public void ClearList()
        {
            data = null;
        }

        public bool ListEmpty()
        {
            if (0 == listSize)
            {
                return true;
            }
            return false;
        }

        public int ListLength()
        {
            return listSize;
        }

        public T GetElem(int pos)
        {
            T tmp = default(T);
            singleLinkedList head;
            head = data;
            while (head.next != null)
            {
                --pos;
                if (pos == 0)
                {
                    tmp = head.data;
                }
                head = head.next;
            }
            return tmp;
        }

        public int LocateElem(T elem, method fun)
        {
            int pos = 0;
            singleLinkedList head = data;
            while (head.next != null)
            {
                ++pos;
                if (fun(head.data, elem))
                {
                    return pos;
                }
                head = head.next;
            }
            return -1;
        }

        public void PriorElem(T elem, ref T pre)
        {
            singleLinkedList head = data;
            singleLinkedList cursor = data;
            while (head.next != null)
            {
                if (head.data.Equals(elem))
                {
                    pre = cursor.data;
                }
                cursor = head;
                head = head.next;
            }
        }

        public void Next(T elem, ref T next)
        {
            singleLinkedList head = data;
            singleLinkedList cursor = data;
            while (head.next != null)
            {
                cursor = head;
                if (head.data.Equals(elem))
                {
                    if (cursor.next != null)
                    {
                        next = cursor.next.data;
                    }
                    else
                    {
                        next = default(T);
                    }
                }
                head = head.next;
            }
        }

        public bool ListInsert(int i, T elem)
        {
            if (i - 1 >= 0 && i < listSize)
            {
                if (data.next == null)
                {
                    singleLinkedList tmp = new singleLinkedList();
                    data.next = tmp;
                    tmp.data = elem;
                }
                singleLinkedList head = data;
                singleLinkedList cursor = data;
                while (head.next != null)
                {
                    cursor = head;
                    head = head.next;
                    --i;
                    if (0 == i)
                    {
                        singleLinkedList tmp = new singleLinkedList();
                        cursor.next = tmp;
                        tmp.data = elem;
                        tmp.next = head;
                        return true;
                    }
                }
                listSize++;
            }
            return false;
        }

        public bool ListDelete(int i, ref T elem)
        {
            bool res = false;
            singleLinkedList head = data;
            singleLinkedList cursor = data;
            while (head.next != null)
            {
                cursor = head;
                head = head.next;
                --i;
                if (0 == i)
                {

                    cursor.next = head.next;
                    head = null;
                    res = true;
                    break;
                }
            }
            return res;
        }

        public bool ListTraverse(visit tra)
        {
            singleLinkedList head = data;
            while (head.next != null)
            {
                if (tra(head.data))
                {
                    return false;
                }
                head = head.next;
            }
            return true;
        }
    }

    class Polynomial
    {
        public double[] datas;
        public bool CreatePolunomial(params double[] info)
        {
            if (info.Length != 0)
            {
                datas = new double[info.Length];
                info.CopyTo(datas, 0);
                return true;
            }
            else
            {
                return false;
            }
        }
        public bool DestroyPolyn()
        {
            if (datas != null)
            {
                datas = null;
                return true;
            }
            else
            {
                return false;
            }
        }
        public void PrintPolyn()
        {
            if (datas.Length >= 1)
            {
                System.Console.Write("{0}", datas[0]);
                for (int i = 1; i < datas.Length; i++)
                {
                    System.Console.Write("+{0}*X^{1}", datas[i], i);
                }
                System.Console.WriteLine();
            }
            else
            {
                System.Console.Write("{0}", datas[0]);
            }
        }
        public int PolynLength()
        {
            return datas.Length;
        }

        public Polynomial AddPolyn(ref Polynomial a, ref Polynomial b)
        {
            Polynomial tmp = new Polynomial();
            int maxL = a.PolynLength() > b.PolynLength() ? a.PolynLength() : b.PolynLength();
            tmp.datas = new double[maxL];
            int length = a.PolynLength() < b.PolynLength() ? a.PolynLength() : b.PolynLength();
            for (int i = 0; i < length; i++)
            {
                tmp.datas[i] = a.datas[i] + b.datas[i];
            }
            if (a.PolynLength() > b.PolynLength())
            {
                for (int i = b.PolynLength(); i < a.PolynLength(); i++)
                {
                    tmp.datas[i] = a.datas[i];
                }
            }
            else if (a.PolynLength() < b.PolynLength())
            {
                for (int i = a.PolynLength(); i < b.PolynLength(); i++)
                {
                    tmp.datas[i] = a.datas[i];
                }
            }
            return tmp;
        }
        public Polynomial SubtractPolyn(ref Polynomial a, ref Polynomial b)
        {
            Polynomial tmp = new Polynomial();
            int maxL = a.PolynLength() > b.PolynLength() ? a.PolynLength() : b.PolynLength();
            tmp.datas = new double[maxL];
            int length = a.PolynLength() < b.PolynLength() ? a.PolynLength() : b.PolynLength();
            for (int i = 0; i < length; i++)
            {
                tmp.datas[i] = a.datas[i] - b.datas[i];
            }
            if (a.PolynLength() > b.PolynLength())
            {
                for (int i = b.PolynLength(); i < a.PolynLength(); i++)
                {
                    tmp.datas[i] = 0 - a.datas[i];
                }
            }
            else if (a.PolynLength() < b.PolynLength())
            {
                for (int i = a.PolynLength(); i < b.PolynLength(); i++)
                {
                    tmp.datas[i] = 0 - a.datas[i];
                }
            }
            return tmp;
        }
    }

    ///   

좋은 웹페이지 즐겨찾기