大话数据结构-线性表

阅读量：6004 次

发布时间：2019-06-20

本文共 11738 字，大约阅读时间需要 39 分钟。

文章知识点来至于大话数据结构里边章节知识，这篇主要介绍线性表在计算机中的存储形式，以及线性表的顺序存储和链式存储方式。同时附上来线性表的顺序存储和链式存储的实现过程。相关代码源码请查看文章最后，文章末尾提供了源代码工程下载地址。

最近在复习数据结构时，感触颇深。推荐程序员们有时间都可以复习下，数据结构不仅仅是一门课程，它更能理清我们开发功能的业务逻辑，然后对Bug说Bye

数据结构绪论

1、数据结构

逻辑结构

集合结构：元素之间没有关系

线性结构：一对一

树形结构：一对多

图形结构：多对多

物理结构

定义：指数据的逻辑结构在计算机中的存储形式

储存类型

顺序存储结构

链式存储结构

算法

1 算法定义

算法是解决待定问题求解步骤的描述，在计算机中表现为指令的有序序列，并且每条指令表示一个或多个操作

2 算法特性

输入

输出

有穷性

确定性

可行性

3 算法时间复杂度

T(n) = O(f(n)), 表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增加率相同，称作算法的渐进时间复杂度

4 算法时间复杂度推导方法

常数阶

对数阶

平方阶

5 算法的设计要求

正确性

可读性

健壮性

高效性

低存储量需求

线性表

1 线性表的物理结构

线性表的顺序存储结构

线性表的链式存储结构

2 线性表的顺序存储结构

优点

无需为表示表中元素间的逻辑关系增加额外的存储空间

可以快速的存取表中任意位置的元素

缺点

插入和删除需要移动大量元素

造成存储空间的碎片

3 线性表的链式存储结构

链表结构图

代码描述

Typeof strcut Node

{

ElemType data,

Struct *next

} Node;

Typeof stuct Node *LinkList;

数据描述

Ai元素数据域p->data, 指针域p->next

Ai+1元素数据域p->next->data = ai+1

4 单链表结构和数据存储结构优缺点

存储分配方式

顺序存储结构用一段连续的存储单元依次存储线性表的数据元素

单链表存储结构采用链式存储结构，用一组任意的存储单元存放线性表的元素

时间性能

查找：顺序存储结构为O(1) 单链表O(n)

插入和删除：顺序存储为O(n)，单链表在现出某位置的指针后仅为O(1)

空间性能

顺序存储需要预分配存储空间，单链表不需要预分配存储空间，元素个数不受限制

5 线性表的存储实现源代码

1、线性表的顺序存储：

public class CustomArray    {        private const int MAXLENGTH = 10000;        private object[] _array;        private readonly int _maxLength;        private int _length;        public CustomArray() : this(MAXLENGTH)        {        }        public CustomArray(int maxLength)        {            if (maxLength > MAXLENGTH)            {                throw new ArgumentOutOfRangeException(string.Format("数组长度必须小于{0}", MAXLENGTH));            }            _maxLength = maxLength;            _array = new object[100];        }        public void AddValue(object value)        {            if (GetLength() == _maxLength)            {                throw new ArgumentOutOfRangeException("数组已经达到最大值");            }            ExpandCustomArray();            _array[GetLength()] = value;            _length++;        }        ///         /// 获取所引处的值        /// 
        /// 具体位置， 从1开始        /// 
              public object GetValue(int index)        {            if (index < 1 || index > GetLength())            {                throw new ArgumentOutOfRangeException();            }            return _array[index - 1];        }        ///         /// 在指定的索引位置插入值        /// 
        /// 插入的值        /// 索引位置        public void Insert(object value, int index)        {            if (GetLength() == _maxLength)            {                throw new ArgumentOutOfRangeException("数组已经达到最大值");            }            if (index < 1 || index > GetLength())            {                throw new ArgumentOutOfRangeException("索引已超出数组范围");            }            ExpandCustomArray();          for (var i = GetLength() ; i >= index; i--)          {              _array[i] = _array[i - 1];          }            _array[index - 1] = value;            _length++;        }        private void ExpandCustomArray()        {            if (_array.Length == GetLength())            {                var tempArray = new object[_array.Length + 100];                for (var i = 0; i < _array.Length; i++)                {                    tempArray[i] = _array[i];                }                _array = tempArray;            }        }        public int GetLength()        {            return _length;        }        public int IndexOf(object value)        {            for (var index = 1; index <= GetLength(); index++)            {                if (_array != null &&_array[index - 1].Equals(value))                {                    return index;                }            }            return -1;        }        public object Delete(int index)        {            if (index > GetLength() || index < 1)            {                throw  new ArgumentOutOfRangeException();            }            var deletedValue = _array[index - 1];            for (var i = index - 1; i < GetLength() - 1; i++)            {                _array[i] = _array[i + 1];            }            _length--;            return deletedValue;        }        public void Clear()        {            _array = new object[0];            _length = 0;        }    }

View Code

2、线性表的链式存储

public class CustomLinkList    {        private int _length;        private CustomLinkNode _headerNode;        private CustomLinkNode _lastNode;        public CustomLinkList()        {            _headerNode = new CustomLinkNode(null);            _lastNode = _headerNode;        }        public int GetLength()        {            return _length;        }        public int IndexOf(CustomLinkNode node)        {            var index = 1;            var compareNode = _headerNode.Next;            while (compareNode != null)            {                if (Object.ReferenceEquals(compareNode, node))                {                    break;                }                compareNode = compareNode.Next;                index++;            }            if (index > GetLength())            {                return -1;            }            return index;        }        public CustomLinkNode GetNode(int index)        {            if (index < 1 || index > GetLength())            {                throw new ArgumentOutOfRangeException("索引已经超出链表范围");            }            var beforeNode = GetContainHeaderNode(index - 1);            if (beforeNode == null || beforeNode.Next == null)            {                throw new NoNullAllowedException();            }            return beforeNode.Next;        }        public void AddNode(CustomLinkNode node)        {            _lastNode.Next = node;            _lastNode = node;            _length++;        }        public void InsertNode(CustomLinkNode node, int index)        {            if (index < 1 || index > GetLength())            {                throw  new ArgumentOutOfRangeException("索引已经超出链表范围");            }            var beforeNode = GetContainHeaderNode(index - 1);            if (beforeNode == null || beforeNode.Next == null)            {                throw  new NoNullAllowedException();            }            var insertedNode = beforeNode.Next;            node.Next = insertedNode;            beforeNode.Next = node;            _length++;        }        public CustomLinkNode DeleteNode(int index)        {            if (index < 1 || index > GetLength())            {                throw new ArgumentOutOfRangeException("索引已经超出链表范围");            }            var beforeNode = GetContainHeaderNode(index - 1);            if (beforeNode == null || beforeNode.Next == null)            {                throw new NoNullAllowedException();            }            var deletedNode = beforeNode.Next;            beforeNode.Next = deletedNode.Next;                        if (index == GetLength())            {                _lastNode = beforeNode;            }            _length--;            return deletedNode;        }        private CustomLinkNode GetContainHeaderNode(int index)        {            var i = 0;            var beforeNode = _headerNode;            while (beforeNode != null)            {                if (i == index)                {                    break;                }                i++;                beforeNode = beforeNode.Next;            }            if (beforeNode == null)            {                throw new NoNullAllowedException();            }            return beforeNode;        }    }

View Code

3、单元测试

private static void TestCustomArray()        {            var customArray = new CustomArray.CustomArray(10);            Assert.IsEqual(customArray.GetLength(), 0);            for (var i = 1; i <=10; i++)            {                customArray.AddValue(i * 100);            }            Assert.IsEqual(customArray.GetLength(), 10);            Assert.IsException(customArray.AddValue, (object)210, typeof(ArgumentOutOfRangeException));            var deleteValue = customArray.Delete(5);            Assert.IsEqual(customArray.GetLength(), 9);            Assert.IsEqual((int) deleteValue,  500);            Assert.IsEqual((int)customArray.GetValue(5), 600);            customArray.Insert(500, 5);            Assert.IsEqual(customArray.GetLength(), 10);            Assert.IsEqual((int)customArray.GetValue(5), 500);            Assert.IsEqual((int)customArray.GetValue(6), 600);            Assert.IsException(customArray.Insert, (object)1000, 0, typeof(ArgumentOutOfRangeException));            Assert.IsException(customArray.Insert, (object)1000, 10, typeof(ArgumentOutOfRangeException));            Assert.IsEqual(customArray.IndexOf(100), 1);            Assert.IsEqual(customArray.IndexOf(200), 2);            Assert.IsEqual(customArray.IndexOf(500), 5);        }        private static void TestCustomLinkList()        {            var customLinkList = new CustomLinkList.CustomLinkList();            var node1 = new CustomLinkNode(1);            customLinkList.AddNode(node1);            var node2 = new CustomLinkNode(2);            customLinkList.AddNode(node2);            var node3 = new CustomLinkNode(3);            customLinkList.AddNode(node3);            var node4 = new CustomLinkNode(4);            customLinkList.AddNode(node4);            var node5 = new CustomLinkNode(5);            customLinkList.AddNode(node5);            Assert.IsEqual(customLinkList.GetLength(), 5);            Assert.IsEqual( (int)customLinkList.GetNode(1).Data, 1);            Assert.IsEqual((int)customLinkList.GetNode(3).Data, 3);            Assert.IsEqual((int)customLinkList.GetNode(5).Data, 5);            var node11 = new CustomLinkNode(11);            var afterNode = customLinkList.GetNode(1);            customLinkList.InsertNode(node11, 1);            Assert.IsEqual((int)customLinkList.GetNode(1).Data, 11);            Assert.IsEqual((int)customLinkList.GetNode(2).Data, (int)afterNode.Data);            var node33 = new CustomLinkNode(33);            afterNode = customLinkList.GetNode(4);            customLinkList.InsertNode(node33, 4);            Assert.IsEqual((int)customLinkList.GetNode(4).Data, 33);            Assert.IsEqual((int)customLinkList.GetNode(5).Data, (int)afterNode.Data);            afterNode = customLinkList.GetNode(7);            var node55 = new CustomLinkNode(55);            customLinkList.InsertNode(node55, 7);            Assert.IsEqual((int)customLinkList.GetNode(7).Data, 55);            Assert.IsEqual((int)customLinkList.GetNode(8).Data, (int)afterNode.Data);            Assert.IsEqual(customLinkList.GetLength(), 8);            var deletedNode = customLinkList.DeleteNode(1);            Assert.IsEqual((int)deletedNode.Data, 11);            Assert.IsEqual((int)customLinkList.GetNode(1).Data, 1);            deletedNode = customLinkList.DeleteNode(3);            Assert.IsEqual((int)deletedNode.Data, 33);            Assert.IsEqual((int)customLinkList.GetNode(3).Data, 3);            deletedNode = customLinkList.DeleteNode(5);            Assert.IsEqual((int)deletedNode.Data, 55);            Assert.IsEqual((int)customLinkList.GetNode(5).Data, 5);            Assert.IsEqual(customLinkList.GetLength(), 5);            Assert.IsEqual(customLinkList.IndexOf(node1), 1);            Assert.IsEqual(customLinkList.IndexOf(node3), 3);            Assert.IsEqual(customLinkList.IndexOf(node5), 5);            Assert.IsEqual(customLinkList.IndexOf(node11), -1);            Assert.IsException
      
       (customLinkList.DeleteNode, 0, typeof(ArgumentOutOfRangeException));            Assert.IsException
       
        (customLinkList.DeleteNode, 6, typeof(ArgumentOutOfRangeException));            Assert.IsException(customLinkList.InsertNode, node1, 0, typeof(ArgumentOutOfRangeException));            Assert.IsException(customLinkList.InsertNode, node1, 6, typeof(ArgumentOutOfRangeException));        }

View Code

源代码下载地址：