06 线性表

知识结构：

1. 线性表的定义与操作

1.1 线性表的定义

线性表（Linear List）是由$n(n\ge 0)$个相同类型的数据元素$a_0,a_1,\cdots ,a_{n-1}$组成的序列。即表中除首尾元素外，其它元素有且仅有一个直接前驱和直接后继。首元素仅有一个直接后继，尾元素仅有一个直接前驱，记为：$(a_0,a_1,\cdots ,a_{n-1})$。

表中数据元素的个数称为表的长度。

例1：字母表

$(a,b,c,d,\dots ,z)$

例2：学生成绩表

1.2 线性表的操作

• 随机存取：获取或设置指定索引处的数据元素值。（支持索引器）
• 插入操作：将数据元素值插入到指定索引处。
• 移除操作：移除线性表指定索引处的数据元素。
• 查找操作：寻找具有特征值域的结点并返回其下标。
• 得到表长：获取线性表中实际包含数据元素的个数。
• 是否为空：判断线性表中是否包含数据元素。
• 清空操作：移除线性表中的所有数据元素。

using System;namespace LinearStruct
{/// <summary>/// 线性表的抽象数据类型/// </summary>/// <typeparam name="T">线性表中元素的类型</typeparam>public interface ILinearList<T> where T : IComparable<T>{/// <summary>/// 获取线性表中实际包含元素的个数/// </summary>int Length { get; }/// <summary>/// 获取或设置指定索引处的元素/// </summary>/// <param name="index">要获取或设置的元素从零开始的索引</param>/// <returns>指定索引处的元素</returns>T this[int index] { get; set; }/// <summary>/// 判断线性表中是否包含元素/// </summary>/// <returns>如果包含元素返回false,否则返回true.</returns>bool IsEmpty();/// <summary>/// 将元素插入到指定索引处/// </summary>/// <param name="index">从零开始的索引,应在该位置插入data.</param>/// <param name="data">要插入的元素</param>void Insert(int index, T data);/// <summary>/// 移除线性表指定索引处的元素/// </summary>/// <param name="index">要移除元素从0开始的索引</param>void Remove(int index);/// <summary>/// 在线性表中寻找元素data./// </summary>/// <param name="data">要寻找的元素</param>/// <returns>如果存在返回该元素在线性表中的位置,否则返回-1.</returns>int Search(T data);/// <summary>/// 从线性表中移除所有元素/// </summary>void Clear();}
}

2. 线性表的顺序存储与实现

定义：利用顺序存储结构（即利用数组）实现的线性表，称为顺序表。

特点：逻辑结构与存储结构相同；具有随机存取的特点。

实现：

using System;namespace LinearStruct
{/// <summary>/// 用顺序存储结构实现的线性表/// </summary>/// <typeparam name="T">顺序表中元素的类型</typeparam>public class SeqList<T> : ILinearList<T> where T : IComparable<T>{/// <summary>/// 数据集合/// </summary>protected readonly T[] Dataset;/// <summary>/// 获取SeqList中实际包含元素的个数/// </summary>public int Length { get; private set; }/// <summary>/// 获取SeqList中最多包含元素的个数/// </summary>public int MaxSize { get; }/// <summary>/// 初始化SeqList类的新实例/// </summary>/// <param name="max">SeqList中最多包含元素的个数</param>public SeqList(int max){if (max <= 0)throw new ArgumentOutOfRangeException();MaxSize = max;Dataset = new T[MaxSize];Length = 0;}/// <summary>/// 获取或设置指定索引处的元素/// </summary>/// <param name="index">要获得或设置的元素从零开始的索引</param>/// <returns>指定索引处的元素</returns>public T this[int index]{get{if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();return Dataset[index];}set{if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();Dataset[index] = value;}}/// <summary>/// 判断SeqList中是否包含元素/// </summary>/// <returns>如果包含元素返回false,否则返回true.</returns>public bool IsEmpty(){return Length == 0;}/// <summary>/// 将元素插入到指定索引处/// </summary>/// <param name="index">从零开始的索引,应在该位置插入data.</param>/// <param name="data">要插入的元素</param>public void Insert(int index, T data){if (index < 0 || index > Length)throw new IndexOutOfRangeException();if (Length == MaxSize)throw new Exception("达到最大值");for (int i = Length; i > index; i--){Dataset[i] = Dataset[i - 1];}Dataset[index] = data;Length++;}/// <summary>/// 移除SeqList指定索引处的元素/// </summary>/// <param name="index">要移除元素从0开始的索引</param>public void Remove(int index){if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();for (int i = index; i < Length - 1; i++){Dataset[i] = Dataset[i + 1];}Length--;}/// <summary>/// 在SeqList中寻找元素data./// </summary>/// <param name="data">要寻找的元素</param>/// <returns>如果存在返回该元素在线性表中的位置,否则返回-1.</returns>public int Search(T data){int i;for (i = 0; i < Length; i++){if (Dataset[i].CompareTo(data) == 0)break;}return i == Length ? -1 : i;}/// <summary>/// 从SeqList中移除所有元素/// </summary>public void Clear(){Length = 0;}}
}

应用：

using System;
using LinearStruct;namespace ExampleList
{class Program{static void Main(string[] args){ListTest(new SeqList<string>(500));// 2// a1// a3}private static void ListTest(ILinearList<string> lst){lst.Insert(0, "a1");lst.Insert(1, "a2");lst.Insert(2, "a3");lst.Remove(1);Console.WriteLine(lst.Length);for (int i = 0; i < lst.Length; i++){Console.WriteLine(lst[i]);}}}
}

3. 线性表的链式存储与实现

利用指针方式实现的线性表称为链表（单链表、循环链表、双向链表）。它不要求逻辑上相邻的数据元素在物理位置上也相邻，即：逻辑结构与物理结构可以相同也可以不相同。

例3：将线性表$(a_3,a_4,a_5)$以链表的形式存储。

3.1 单链表

定义：每个结点只含有一个链域（指针域）的链表。即：利用单链域的方式存储线性表的逻辑结构。

结构：

实现：

对结点的封装：

using System;namespace LinearStruct
{/// <summary>/// 单链表结点/// </summary>/// <typeparam name="T">结点中数据元素的类型</typeparam>public class SNode<T> where T : IComparable<T>{/// <summary>/// 获取或设置该结点的数据元素/// </summary>public T Data { get; set; }/// <summary>/// 获取或设置该结点的后继结点/// </summary>public SNode<T> Next { get; set; }/// <summary>/// 初始化SNode类的新实例/// </summary>/// <param name="data">该结点的数据元素</param>/// <param name="next">该结点的后继结点</param>public SNode(T data, SNode<T> next = null){Data = data;Next = next;}}
}

对单链表的封装：

using System;namespace LinearStruct
{/// <summary>/// 用链式存储结构实现的线性表--单链表/// </summary>/// <typeparam name="T">单链表中元素的类型</typeparam>public class SLinkList<T> : ILinearList<T> where T : IComparable<T>{/// <summary>/// 存储头结点/// </summary>protected SNode<T> PHead { get; set; }/// <summary>/// 获取SLinkList中实际包含元素的个数/// </summary>public int Length { get; private set; }/// <summary>/// 初始化SLinkList类的新实例/// </summary>public SLinkList(){Length = 0;PHead = null;}/// <summary>/// 将元素插入到单链表的首部/// </summary>/// <param name="data">要插入的元素</param>public void InsertAtFirst(T data){PHead = new SNode<T>(data, PHead);Length++;}/// <summary>/// 获得指定索引处的结点/// </summary>/// <param name="index">元素从零开始的索引</param>/// <returns>指定索引处的结点</returns>private SNode<T> Locate(int index){if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();SNode<T> temp = PHead;for (int i = 0; i < index; i++){temp = temp.Next;}return temp;}/// <summary>/// 将元素插入到单链表的尾部/// </summary>/// <param name="data">要插入的元素</param>public void InsertAtRear(T data){if (PHead == null){PHead = new SNode<T>(data);}else{Locate(Length - 1).Next = new SNode<T>(data);}Length++;}/// <summary>/// 获取或设置指定索引处的元素/// </summary>/// <param name="index">要获得或设置的元素从零开始的索引</param>/// <returns>指定索引处的元素</returns>public T this[int index]{get{if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();return Locate(index).Data;}set{if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();Locate(index).Data = value;}}/// <summary>/// 判断SLinkList中是否包含元素/// </summary>/// <returns>如果包含元素返回false,否则返回true.</returns>public bool IsEmpty(){return Length == 0;}/// <summary>/// 将元素插入到指定索引处/// </summary>/// <param name="index">从零开始的索引,应在该位置插入data.</param>/// <param name="data">要插入的元素</param>public void Insert(int index, T data){if (index < 0 || index > Length)throw new IndexOutOfRangeException();if (index == 0){InsertAtFirst(data);}else if (index == Length){InsertAtRear(data);}else{SNode<T> temp = Locate(index - 1);temp.Next = new SNode<T>(data, temp.Next);Length++;}}/// <summary>/// 移除SLinkList指定索引处的元素/// </summary>/// <param name="index">要移除元素从0开始的索引</param>public void Remove(int index){if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();if (index == 0){PHead = PHead.Next;}else{SNode<T> temp = Locate(index - 1);temp.Next = temp.Next.Next;}Length--;}/// <summary>/// 在SLinkList中寻找元素data./// </summary>/// <param name="data">要寻找的元素</param>/// <returns>如果存在返回该元素在线性表中的位置,否则返回-1.</returns>public int Search(T data){int i;SNode<T> temp = PHead;for (i = 0; i < Length; i++){if (temp.Data.CompareTo(data) == 0)break;temp = temp.Next;}return i == Length ? -1 : i;}/// <summary>/// 从SLinkList中移除所有元素/// </summary>public void Clear(){PHead = null;Length = 0;}}
}

应用：

using System;
using LinearStruct;namespace ExampleList
{class Program{static void Main(string[] args){ListTest(new SLinkList<string>());// 2// a1// a3}private static void ListTest(ILinearList<string> lst){lst.Insert(0, "a1");lst.Insert(1, "a2");lst.Insert(2, "a3");lst.Remove(1);Console.WriteLine(lst.Length);for (int i = 0; i < lst.Length; i++){Console.WriteLine(lst[i]);}}}
}

3.2 循环链表

定义：是一种首尾相连的单链表。即：在单链表中，将尾结点的指针域null改为指向PHead，就得到单链形式的循环链表。

表现形式：

通常情况下，使用尾指针表示循环链表。

实现：

对循环链表的封装：

using System;namespace LinearStruct
{/// <summary>/// 用链式存储结构实现的线性表--循环链表/// </summary>/// <typeparam name="T">循环链表中元素的类型</typeparam>public class CLinkList<T> : ILinearList<T> where T : IComparable<T>{/// <summary>/// 存储尾部结点/// </summary>protected SNode<T> PRear { get; set; }/// <summary>/// 获取CLinkList中实际包含元素的个数/// </summary>public int Length { get; private set; }/// <summary>/// 获取或设置指定索引处的元素/// </summary>/// <param name="index">要获得或设置的元素从零开始的索引</param>/// <returns>指定索引处的元素</returns>public T this[int index]{get{if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();return Locate(index).Data;}set{if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();Locate(index).Data = value;}}/// <summary>/// 初始化CLinkList类的新实例/// </summary>public CLinkList(){Length = 0;PRear = null;}/// <summary>/// 判断CLinkList中是否包含元素/// </summary>/// <returns>如果包含元素返回false,否则返回true.</returns>public bool IsEmpty(){return Length == 0;}/// <summary>/// 将元素插入到循环链表的尾部/// </summary>/// <param name="data">要插入的元素</param>public void InsertAtRear(T data){if (IsEmpty()){PRear = new SNode<T>(data);PRear.Next = PRear;}else{SNode<T> temp = new SNode<T>(data, PRear.Next);PRear.Next = temp;PRear = temp;}Length++;}/// <summary>/// 将元素插入到循环链表的首部/// </summary>/// <param name="data">要插入的元素</param>public void InsertAtFirst(T data){if (IsEmpty()){PRear = new SNode<T>(data);PRear.Next = PRear;}else{SNode<T> temp = new SNode<T>(data, PRear.Next);PRear.Next = temp;}Length++;}/// <summary>/// 获得指定索引处的结点/// </summary>/// <param name="index">元素从零开始的索引</param>/// <returns>指定索引处的结点</returns>private SNode<T> Locate(int index){if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();SNode<T> temp = PRear.Next;for (int i = 0; i < index; i++){temp = temp.Next;}return temp;}/// <summary>/// 将元素插入到指定索引处/// </summary>/// <param name="index">从零开始的索引,应在该位置插入data.</param>/// <param name="data">要插入的元素</param>public void Insert(int index, T data){if (index < 0 || index > Length)throw new IndexOutOfRangeException();if (index == 0){InsertAtFirst(data);}else if (index == Length){InsertAtRear(data);}else{SNode<T> temp = Locate(index - 1);temp.Next = new SNode<T>(data, temp.Next);Length++;}}/// <summary>/// 移除CLinkList指定索引处的元素/// </summary>/// <param name="index">要移除元素从0开始的索引</param>public void Remove(int index){if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();if (PRear == PRear.Next){PRear = null;}else{if (index == Length - 1){SNode<T> temp = Locate(Length - 2);temp.Next = PRear.Next;PRear = temp;}else if (index == 0){PRear.Next = PRear.Next.Next;}else{SNode<T> temp = Locate(index - 1);temp.Next = temp.Next.Next;}}Length--;}/// <summary>/// 在CLinkList中寻找元素data./// </summary>/// <param name="data">要寻找的元素</param>/// <returns>如果存在返回该元素在线性表中的位置,否则返回-1.</returns>public int Search(T data){int i;SNode<T> temp = PRear;for (i = 0; i < Length; i++){if (temp.Next.Data.CompareTo(data) == 0)break;temp = temp.Next;}return (i == Length) ? -1 : i;}/// <summary>/// 从CLinkList中移除所有元素/// </summary>public void Clear(){Length = 0;PRear = null;}}
}

应用：

using System;
using LinearStruct;namespace ExampleList
{class Program{static void Main(string[] args){ListTest(new CLinkList<string>());// 2// a1// a3}private static void ListTest(ILinearList<string> lst){lst.Insert(0, "a1");lst.Insert(1, "a2");lst.Insert(2, "a3");lst.Remove(1);Console.WriteLine(lst.Length);for (int i = 0; i < lst.Length; i++){Console.WriteLine(lst[i]);}}}
}

3.3 双向链表

定义：每个结点含有两个链域（指针域）的链表。即：利用双链域的方式存储线性表的逻辑结构。

结构：

实现：

对结点的封装：

using System;namespace LinearStruct
{/// <summary>/// 双向链表结点/// </summary>/// <typeparam name="T">结点中数据元素的类型</typeparam>public class DNode<T> where T : IComparable<T>{/// <summary>/// 获取或设置该结点的前趋结点/// </summary>public DNode<T> Prior { get; set; }/// <summary>/// 获取或设置该结点的后继结点/// </summary>public DNode<T> Next { get; set; }/// <summary>/// 获取或设置该结点的数据元素/// </summary>public T Data { get; set; }/// <summary>/// 初始化DNode类的新实例/// </summary>/// <param name="data">该结点的数据元素</param>/// <param name="prior">该结点的前趋结点</param>/// <param name="next">该结点的后继结点</param>public DNode(T data, DNode<T> prior = null, DNode<T> next = null){Prior = prior;Data = data;Next = next;}}
}

对双向链表的封装：

using System;namespace LinearStruct
{/// <summary>/// 用链式存储结构实现的线性表--双链表/// </summary>/// <typeparam name="T">结点中数据元素的类型</typeparam>public class DLinkList<T> : ILinearList<T> where T : IComparable<T>{/// <summary>/// 存储头结点/// </summary>protected DNode<T> PHead { get; set; }/// <summary>/// 存储尾结点/// </summary>protected DNode<T> PRear { get; set; }/// <summary>/// 获取DLinkList中实际包含元素的个数/// </summary>public int Length { get; private set; }/// <summary>/// 初始化DLinkList类的新实例/// </summary>public DLinkList(){PHead = null;PRear = null;Length = 0;}/// <summary>/// 将元素插入到双链表的首部/// </summary>/// <param name="data">要插入的元素</param>public void InsertAtFirst(T data){if (IsEmpty()){DNode<T> temp = new DNode<T>(data);PHead = temp;PRear = temp;}else{DNode<T> temp = new DNode<T>(data, null, PHead);PHead.Prior = temp;PHead = temp;}Length++;}/// <summary>/// 将元素插入到双链表的尾部/// </summary>/// <param name="data">要插入的元素</param>public void InsertAtRear(T data){if (IsEmpty()){DNode<T> temp = new DNode<T>(data);PHead = temp;PRear = temp;}else{DNode<T> temp = new DNode<T>(data, PRear, null);PRear.Next = temp;PRear = temp;}Length++;}/// <summary>/// 获得指定索引处的结点/// </summary>/// <param name="index">元素从零开始的索引</param>/// <returns>指定索引处的结点</returns>private DNode<T> Locate(int index){if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();DNode<T> temp = PHead;for (int i = 0; i < index; i++){temp = temp.Next;}return temp;}/// <summary>/// 将元素插入到指定索引处/// </summary>/// <param name="index">从零开始的索引,应在该位置插入data.</param>/// <param name="data">要插入的元素</param>public void Insert(int index, T data){if (index < 0 || index > Length)throw new IndexOutOfRangeException();if (index == 0){InsertAtFirst(data);}else if (index == Length){InsertAtRear(data);}else{DNode<T> temp1 = Locate(index);DNode<T> temp2 = new DNode<T>(data, temp1.Prior, temp1);temp2.Prior.Next = temp2;temp2.Next.Prior = temp2;Length++;}}/// <summary>/// 移除DLinkList指定索引处的元素/// </summary>/// <param name="index">要移除元素从0开始的索引</param>public void Remove(int index){if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();if (Length == 1){PHead = null;PRear = null;}else{if (index == 0){PHead = PHead.Next;PHead.Prior = null;}else if (index == Length - 1){PRear = PRear.Prior;PRear.Next = null;}else{DNode<T> temp = Locate(index);temp.Prior.Next = temp.Next;temp.Next.Prior = temp.Prior;}}Length--;}/// <summary>/// 判断DLinkList中是否包含元素/// </summary>/// <returns>如果包含元素返回false,否则返回true.</returns>public bool IsEmpty(){return Length == 0;}/// <summary>///  从DLinkList中移除所有元素/// </summary>public void Clear(){Length = 0;PHead = null;PRear = null;}/// <summary>/// 在DLinkList中寻找元素data./// </summary>/// <param name="data">要寻找的元素</param>/// <returns>如果存在返回该元素在线性表中的位置,否则返回-1.</returns>public int Search(T data){int i;DNode<T> temp = PHead;for (i = 0; i < Length; i++){if (temp.Data.CompareTo(data) == 0)break;temp = temp.Next;}return i == Length ? -1 : i;}/// <summary>/// 获取或设置指定索引处的元素/// </summary>/// <param name="index">要获得或设置的元素从零开始的索引</param>/// <returns>指定索引处的元素</returns>public T this[int index]{get{if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();return Locate(index).Data;}set{if (index < 0 || index > Length - 1)throw new IndexOutOfRangeException();Locate(index).Data = value;}}}
}

应用：

using System;
using LinearStruct;namespace ExampleList
{class Program{static void Main(string[] args){ListTest(new DLinkList<string>());// 2// a1// a3}private static void ListTest(ILinearList<string> lst){lst.Insert(0, "a1");lst.Insert(1, "a2");lst.Insert(2, "a3");lst.Remove(1);Console.WriteLine(lst.Length);for (int i = 0; i < lst.Length; i++){Console.WriteLine(lst[i]);}}}
}

后台回复「搜搜搜」，随机获取电子资源！
欢迎关注，请扫描二维码：