1.数据结构学习之线性表（一）
开篇：数据结构是程序应用里基础的学科。 官方来说，数据结构是计算机存储、组织数据的方式。
数据结构有着非常重要的重用，如果理解并且掌握它，在我们的学习或者工作中的开发会事半功倍。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。接下来，开始我们的数据结构学习之路吧。(代码为C#形式)
1.什么是线性表?
线性表是最基本、最简单、也是最常用的一种数据结构。例如我们开发中最常用的关系型数据库。
例如这张学生表。
| 学号 | 姓名 | 性别 | 年龄 |
| 1 | 阿黄 | 男 | 22 |
| 2 | 阿虎 | 女 | 23 |
| 3 | 阿蛋 | 男 | 24 |
在这张学生表中，这里的表为典型的线性表,由a1,a2......an组成的有限序列，在这张表中有3个数据元素，也称纪录，（学校，姓名..）这些称为数据项。
由此可见:线性表有如下特征:
1.有且仅有一个为开始元素的（在这里,阿黄是首个开始数据），它没有前趋，仅有一个后继元素(这里为阿虎)。
2.有且仅有一个为结束元素的（在这里,阿蛋是结束数据），它没有后继，仅有一个直接前趋势(这里为阿虎)。
3.除去首尾的两个元素，其余的为内部元素，有且仅有一个直接前趋势和直接后继元素(这里为阿虎)。
2.线性表的基本运算?
对于线性表，有这几种基本的运算:
1.增加元素 。2.查元素 。3.插入元素。4.删除元素等等。
接下来我会使用C# 来构建一个最基本的线性表类型(数组)，大家也可以使用自己的语言来改写。
3.代码片段
我们先新增个Array类，初始化的时候我们默认给容量Capacity为20。
public class Array { private int[] Data; private int Size; private readonly int Capacity; public bool IsFull => this.Capacity == this.Size; public Array(int capacity = 20) { this.Capacity = capacity; this.Data = new int[this.Capacity]; } }
Add方法在末尾添加元素。判断是否容量已满。满了就报了异常。加成功了，Size就会+1
1 public void Add(int value) 2 { 3 if (IsFull) 4 throw new Exception("Array is full"); 5 this.Size++; 6 this.Data[this.Size - 1] = value; 7 }
Insert方法在特定位置插入元素。
例如这张，此时5要插入到这个数组里，插入成功后应为1，2，5，3，4。长度Size会增加。
代码如下：只要循环当前插入的元素到数组长度。每一个都往后移动一位即可。插入之前的数据不动。
1 public void Insert(int index,int value) 2 { 3 if (index < 0) 4 throw new Exception("index is less than zero"); 5 if (index > this.Capacity-1 || index > this.Size) 6 throw new Exception("index is more than capacity or Size"); 7 for (int i = Size-1; i >index-1; i--) 8 { 9 this.Data[i + 1] = this.Data[i]; 10 } 11 this.Data[index] = value; 12 this.Size++; 13 }
Delete方法在删除元素。
1.根据索引删除元素，与插入类似，删除当前索引的值，后面的元素应全部往前移动一格。最后一为元素应置为空，长度Size也应减1。
1 public void Delete(int index) 2 { 3 if (index < 0) 4 throw new Exception("index is less than zero"); 5 if (index > this.Capacity-1) 6 throw new Exception("index is more than capacity"); 7 if (index > this.Size-1) 8 return; 9 for (int i = index; i < this.Size-1; i++) 10 { 11 this.Data[i] = this.Data[i+1]; 12 } 13 this.SetEmpty(this.Size-1); 14 this.Size--; 15 } 16 17 private void SetEmpty(int index) 18 { 19 this.Data[index] = default; 20 }
2.删除某个元素值，查找到这个值所在的索引，再去删除他。
public void DeleteElement(int value) { var eleIndex = -1; for (int i = 0; i < this.Size; i++) { if (this.Data[i] == value) eleIndex = i; } if (eleIndex < 0) return; this.Delete(eleIndex); }
跟新元素，这个嘛，比较简单。
1 public void Update(int index,int value) 2 { 3 if (index < 0) 4 throw new Exception("index is less than zero"); 5 if (index > this.Capacity - 1) 6 throw new Exception("index is more than capacity"); 7 if (index > this.Size - 1) 8 return; 9 this.Data[index] = value; 10 }
常规判断,判断数据是否存在，查找方法等等。
1 public bool IsContain(int value) 2 { 3 var isContain = false; 4 for (int i = 0; i < this.Size; i++) 5 { 6 if (this.Data[i] == value) 7 isContain = true; 8 } 9 return isContain; 10 } 11 12 public int Find(int value) 13 { 14 for (int i = 0; i < this.Size; i++) 15 { 16 if (this.Data[i] == value) 17 return i; 18 } 19 return -1; 20 } 21 22 public int Search(int index) 23 { 24 if(index>Size-1 || index<0) 25 throw new Exception("this index is empty or index is less than zero"); 26 return this.Data[index]; 27 } 28 29 public override string ToString() 30 { 31 var list = new List<int>(); 32 for (int i = 0; i < this.Size; i++) 33 { 34 list.Add(this.Data[i]); 35 } 36 return $"Use {this.Size}, Capacity {this.Capacity} Numbers is {string.Join(",", list.Select(i => i))}"; 37 }
写到这里。我们基本的写好了一个最简单的数组线性表。但有没有发现,我们写的这种结构局限性很大，比如他只支持int呀，我们肯定想支持各种类型。
而且我们此时的各中方法性能又如何呢，算句话说我们的空间复杂度又是如何的呢，容量问题又如何解决呢。我们下一章再来优化和改善这一数组结构。谢谢大家~~~~~~
