数据结构简明备忘录线性表

线性表是线性结构的抽象，线性结构的特点是结构中的数据元素之间存在一对一的线性关系。

线性表

线性表是线性结构的抽象，线性结构的特点是结构中的数据元素之间存在一对一的线性关系。
数据元素之间的位置关系是一个接一个的排列：
.除第一个位置的数据元素外，其他数据元素位置的前面都只有一个数据元素。
.除最后一个位置的外，其他数据元素位置的后面都只有一个元素。
线性表通常表示为：L=(D,R)
D是数据元素的有限集合
R是数据元素之间关系的有限集合

线性表的基本操作：
代码如下:

<br>public interface IListDS<t> { <br>int GetLength(); //求长度 <br>void Clear(); //清空 <br>bool IsEmpty(); //判空 <br>void Append(T item); //附加 <br>void Insert(T item, int i); //插入 <br>T Delete(int i); //删除 <br>T GetElement(int i); //取表元素 <br>int Locate(T value); //按值查找 <br>} <br> <br><strong>顺序表</strong> <br><br>顺序表是线性表的顺序存储(Sequence Storage)，是指在内存中用一块地址连续的空间依次存放线性表的数据元素(Sequence List)，具有随机存取的特点。 <br><br>w: 每个数据元素占w个存储单元 <br>A1:顺序表的基地址(Base Address) <br>Loc(Ai)=Loc(A1)+(i-1)*w 1<=i<=n <br><br>为了理解顺序表，闪电学习了这样一个例题，有兴趣的朋友可以在自己的机器上写一下。 <br>有数据类型为整型的顺序表La和Lb，其数据元素均按从小到大的升序排列，编写一个算法将它们合并成一个表Lc，要求Lc中数据元素也按升序排列。 <br><strong>算法思路：</strong> <br>依次扫描La和Lb的数据元素，比较La和Lb当前数据元素的值，将较小值的数据元素赋给Lc，如此直到一个顺序表被扫描完，然后将未完的那个顺序表中余下的数据元素赋给Lc即可。Lc的容量要能够容纳La和Lb两个表相加的长度。 <br>思路图示： <br><br> 代码如下:<br>public class SeqList<t> : IListDS<t> { <br>private int maxsize; //顺序表的容量 <br>private T[] data; //数组，用于存储顺序表中的数据元素 <br>private int last; //指示顺序表最后一个元素的位置 <br><br>//构造器 <br>public SeqList(int size) <br>{ <br>data = new T[size]; <br>maxsize = size; <br>last = -1; //如果顺序表为空，last=-1 <br>} <br>//索引器 <br>public T this[int index] <br>{ <br>get { return data[index]; } <br>set { data[index] = value; } <br>} <br>//最后一个元素的位置属性 <br>public int Last <br>{ <br>get { return last; } <br>} <br>//容量属性 <br>public int Maxsize <br>{ <br>get { return maxsize; } <br>set { maxsize = value; } <br>} <br>//判断顺序表是否为空 <br>public bool IsEmpty() <br>{ <br>if (last == -1) <br>return true; <br>else <br>return false; <br>} <br>//判断顺序表是否为满 <br>public bool IsFull() <br>{ <br>if (last == maxsize - 1) <br>return true; <br>else <br>return false; <br>} <br>//求顺序表的长度 <br>public int GetLength() <br>{ <br>return last + 1; <br>} <br>//清空顺序表 <br>public void Clear() <br>{ <br>last = -1; <br>} <br>//在顺序表末尾添加新元素 <br>public void Append(T item) <br>{ <br>if (IsFull()) <br>{ <br>Console.WriteLine("List is full."); <br>return; <br>} <br>data[++last] = item; <br>} <br><br>//在顺序表第i个数据元素位置插入一个数据元素 <br>public void Insert(T item, int i) <br>{ <br>if (IsFull()) <br>return; <br>if (i < 1 || i > last + 2) <br>return; <br>if (i == last + 2) <br>data[last + 1] = item; <br>else <br>{ <br>for (int j = last; j >= i - 1; --j) <br>{ <br>data[j + 1] = data[j]; <br>} <br>data[i - 1] = item; <br>} <br>++last; <br>} <br>//删除顺序表的第i个数据元素 <br>public T Delete(int i) <br>{ <br>T tmp = default(T); <br>if (IsEmpty()) <br>return tmp; <br>if (i < 1 || i > last + 1) <br>return tmp; <br>if (i == last + 1) <br>tmp = data[last--]; <br>else <br>{ <br>tmp = data[i - 1]; <br>for (int j = i; j <= last; ++j) <br>data[j] = data[j + 1]; <br>} <br>--last; <br>return tmp; <br>} <br>//获得顺序表的第i个数据元素 <br>public T GetElement(int i) <br>{ <br>if (IsEmpty() || (i < 1) || (i > last + 1)) <br>return default(T); <br>return data[i-1]; <br>} <br>//在顺序表中查找值为value的数据元素 <br>public int Locate(T value) <br>{ <br>if (IsEmpty()) <br>return -1; <br>int i = 0; <br>for (i = 0; i <= last; ++i) <br>{ <br>if (value.Equals(data[i])) <br>break; <br>} <br>if (i > last) <br>return -1; <br>return i; <br>} <br>}<br><br> 代码如下:<pre class="brush:php;toolbar:false layui-box layui-code-view layui-code-notepad"><ol class="layui-code-ol"><li><br>public class GenericList <br>{ <br>public GenericList() <br>{ } <br>public SeqList<int> Merge(SeqList<int> La, SeqList<int> Lb) <br>{ <br>SeqList<int> Lc = new SeqList<int>(La.Maxsize+Lb.Maxsize); <br>int i = 0; <br>int j = 0; <br>int k = 0; <br>//两个表中元素都不为空 <br>while ((i <= (La.GetLength() - 1)) && (j <= (Lb.GetLength() - 1))) <br>{ <br>if (La[i] < Lb[j]) <br>Lc.Append(La[i++]); <br>else <br>Lc.Append(Lb[j++]); <br>} <br>//a表中还有数据元素 <br>while (i <= (La.GetLength() - 1)) <br>Lc.Append(La[i++]); <br>//b表中还有数据元素 <br>while (j <= (Lb.GetLength() - 1)) <br>Lc.Append(Lb[j++]); <br>return Lc; <br>} <br>} <br> <br>客户端代码： <br> 代码如下:<pre class="brush:php;toolbar:false layui-box layui-code-view layui-code-notepad"><ol class="layui-code-ol"><li><br>static void Main(string[] args) <br>{ <br>SeqList<int> sl1 = new SeqList<int>(4); <br>sl1.Append(1); <br>sl1.Append(3); <br>sl1.Append(4); <br>sl1.Append(7); <br>SeqList<int> sl2 = new SeqList<int>(6); <br>sl2.Append(2); <br>sl2.Append(5); <br>sl2.Append(6); <br>sl2.Append(8); <br>sl2.Append(11); <br>sl2.Append(14); <br>GenericList gl = new GenericList(); <br>SeqList<int> sl3 = gl.Merge(sl1, sl2); <br>Console.WriteLine("length:" + sl3.GetLength()); <br>for (int i = 0; i < sl3.GetLength(); i++) <br>{ <br>Console.WriteLine(i + ":" + sl3[i]); <br>} <br>} <br> <br>好了，下一次学习链表。 <br>作者：LevinLee                    </int></int></int></int></int></li></ol></pre></int></int></int></int></int></li></ol></pre></t></t></t>