第三章 线性表(C#实现)

1、线性表

  概念::零个或多个数据元素的有序序列。

  描述:

2、线性表的抽象数据类型:

  ADT线性表

  Data:线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType。其中除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素,数据元素之间的关系是一对一的关系。

  Operation

  Init(*L):初始化操作,建立一个空的线性表;

  IsEmpty(*L):判断线性表是否为空,若为空,则返回true,否则返回false;

  Clear(*L):清空线性表;

  GetElem(*L,i):返回线性表位置为i的元素;

  LocateElem(*L,e):返回线性表中与元素i相同值的位置;

  Insert(*L,i,e):在线性表i位置插入元素e;

  Delete(*L,i):删除线性表位置i的元素;

  GetLength(*L):获得当前线性表的长度。

endADT

3、线性表的顺序存储结构

  概念:用一段地址连续的存储单元存储线性表的数据元素。

  如图:

    

    算法的C#语言实现

    

  /// <summary>
    /// 线性表的顺序存储结构
    /// </summary>
    public class SequentialStorageLinearList<T>
    {
        //最大存放数量
        private int _maxLength;

        /// <summary>
        /// 最大存储数量
        /// </summary>
        public int MaxLength
        {
            get
            {
                return _maxLength;
            }
        }

        // 当前存放位置
        private int _currentLength;

        private T[] _LinearList;

        //利用构造函数创建一个数组,用来存放数据
        public SequentialStorageLinearList(int maxLength)
        {
            if (maxLength <= 0)
                throw new Exception("The length can not be less than zero.");
            _maxLength = maxLength;
            _currentLength = 0;
            _LinearList = new T[_maxLength];
        }

        /// <summary>
        /// 判断线性表是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return _currentLength == 0;
        }

        /// <summary>
        /// 清空所有的元素
        /// </summary>
        public void ClearAll()
        {
            if (_currentLength > 0)
            {
                /*
                 * 在高级语言.net中,我们可以重新创建一个新的数组,将其指向当前的_linearList
                 *由于是托管代码,资源不需要手动释放,会自动释放
                 *但是在c语言中,我们需要手动的释放其占用的空间(free)
                 */
                _LinearList = new T[0];
            }
        }

        /// <summary>
        /// 根据
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        public T GetElement(int i)
        {
            if (_currentLength == 0 || _currentLength < i || i < 1)
                throw new Exception("Not find any Element.");
            T t = _LinearList[i];
            return t;
        }

        /// <summary>
        /// 查找数据中是否存在元素e
        /// </summary>
        /// <param name="e"></param>
        /// <returns></returns>
        public int IndexOf(T e)
        {
            if (_currentLength == 0)
                throw new Exception("The array is empty.");
            for (int i = 0; i < _currentLength; i++)
            {
                T t = _LinearList[i];
                /*
                 * T可能是引用类型,我们暂时的比较方式,不考虑重写equals
                 */
                if (t.Equals(e))
                {
                    return i;
                }
            }
            return -1;
        }

        /// <summary>
        /// 在位置i处插入元素e
        /// </summary>
        /// <param name="e">待插入的元素e</param>
        /// <param name="i">插入位置i</param>
        public void Insert(T e, int i)
        {
            //数组已经存满
            if (_currentLength == _maxLength)
                throw new Exception("The array is full.");
            //当i位置不在范围内
            if (i < 1 || i > _currentLength + 1)
                throw new Exception("The location is illegal.");
            //若插入的数据不在表尾,在需要移动插入位置后面的数据一位
            if (i <= _currentLength - 1)
            {
                for (int j = _currentLength - 1; j > i; j--)
                {
                    _LinearList[j + 1] = _LinearList[j];
                }
            }
            _LinearList[i - 1] = e;
            _currentLength++;
        }

        /// <summary>
        /// 删除位置i处的元素
        /// </summary>
        /// <param name="i">位置i</param>
        public void Delete(int i)
        {
            if (_currentLength == 0)
                throw new Exception("The array is Empty.");
            if (i < 1 || i > _currentLength)
                throw new Exception("The location is illegal.");
            //删除位置i元素后需要将i后面的元素依次递增一位
            if (i < _currentLength)
            {
                for (int k = k-1; k < _currentLength; k++)
                {
                    _LinearList[k - 1] = _LinearList[k];
                }
            }
            _currentLength--;
        }
    }

4、线性表的链式存储结构

  数据域:存储数据元素信息的域;

  指针域:存储直接后继位置的域;

  节点(Node):由数据域和指针域组成的数据元素ai的存储映像;

  我们把由n个节点链结成一个链表,即为线性表的链式存储结构。

  如图:

    

5、单链表

  链表的每个将结点中只包含一个指针域,我们称为单链表。同时我们把链表中第  一个结点的存储位置称为头指针。同时在链表的第一个结点前附设一个结点,称  为头结点。

  单链表的C#实现:

  

 /// <summary>
    /// 单链表的实现
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class SingleNode<T>
    {
        /// <summary>
        /// 序号
        /// </summary>
        public int Index { get; private set; }

        /// <summary>
        /// 头指针
        /// </summary>
        public SingleNode<T> HeadNode { get; private set; }

        /// <summary>
        /// 指针域
        /// </summary>
        public SingleNode<T> NextNode { get; set; }

        /// <summary>
        /// 数据域
        /// </summary>
        public T Data { get; set; }

        public SingleNode()
        {
            HeadNode = new SingleNode<T>();
            Index = 0;
            NextNode = null;
        }

        public SingleNode(T t)
        {
            Data = t;
            NextNode = null;
        }

        /// <summary>
        /// 判断单链表是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return Index == 0;
        }

        /// <summary>
        /// 清空所有的元素
        /// </summary>
        public void ClearAll()
        {
            if (Index > 0)
            {
                NextNode = null;
                Data = default(T);
                Index = 0;
            }
        }

        /// <summary>
        /// 获得位置为i的元素
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        public SingleNode<T> GetElement(int i)
        {
            if (Index == 0 || Index < i || i < 1)
                throw new Exception("Not find any Element.");
            SingleNode<T> head = HeadNode;
            SingleNode<T> next;
            for (int k = 0; k < Index; k++)
            {
                next = head.NextNode;
                if (next.Index == i)
                {
                    return next;
                }
                head = next.NextNode;
            }
            return null;
        }

        /// <summary>
        /// 查找数据中是否存在元素e
        /// </summary>
        /// <param name="e"></param>
        /// <returns></returns>
        public int IndexOf(T e)
        {
            if (Index == 0)
                throw new Exception("The array is empty.");
            SingleNode<T> head = HeadNode;
            SingleNode<T> next;
            for (int k = 0; k < Index; k++)
            {
                next = head.NextNode;
                if (next.Equals(e))
                {
                    return next.Index;
                }
                head = next.NextNode;
            }
            return -1;
        }

        /// <summary>
        /// 在位置i处插入元素e
        /// </summary>
        /// <param name="e">待插入的元素e</param>
        /// <param name="i">插入位置i</param>
        public void Insert(T t, int i)
        {
            /*
              *1.先判断i是否存在
             *2.若存在则创建一个空节点,将值t赋给该空节点
             *3.修改该节点的前驱和后继节点
              */
            if (i < 1 || i > Index)
                throw new Exception("The location is illegal.");
            //获得当前位置i的节点
            var preNode = GetElement(i);

            //创建空节点
            SingleNode<T> currentNode = new SingleNode<T>(t);

            //修改前驱节点指向当前节点
            var nextNode = preNode.NextNode;
            preNode.NextNode = currentNode;

            //将新节点的后继节点修改
            currentNode.NextNode = nextNode;

            Index++;
        }

        /// <summary>
        /// 删除位置i处的元素
        /// </summary>
        /// <param name="i">位置i</param>
        public void Delete(int i)
        {
            /*
             *1.查找位置为i的节点
             *2.修改节点的前继节点为查找节点的下一节点
             */
            //获得当前位置i-1的节点
            if (i < 1 || i > Index)
                throw new Exception("The location is illegal.");
            var preNode = GetElement(i - 1);
            var nextNextNode = preNode.NextNode.NextNode;
            preNode.NextNode = nextNextNode;
            Index--;
        }
    }
 

6、循环链表

  将单链表中终端节点的指针端由空指针改为指向头节点,这样整个单链表就成为了一个环,这种头尾相接的单链表称为单循环链表。

  如图:

    

  实现代码类似与单链表。

7、双向链表

  在单链表的每个节点中,再设置一个指向其前驱节点的指针,从而形成的链表,我们称为双向链表。

  如图:

    

  C#代码实现:

  

8、链表和线性表的优缺点比较

    如图:

      

9、参考资料:

   单链表的19种操作: http://www.cnblogs.com/lifuqing/archive/2011/08/20/List.html

    单链表的C#实现:http://www.cnblogs.com/linzheng/news/2011/07/14/2106173.html

原文地址:https://www.cnblogs.com/xiuyuanjing/p/4115254.html