线性表
线性表是最简单、最基本、最常用的数据结构。线性表是线性结构的抽象(Abstract)，线性结构的特点是结构中的数据元素之间存在一对一的线性关系。这种一对一的关系指的是数据元素之间的位置关系，即：
（ 1）除第一个位置的数据元素外，其它数据元素位置的前面都只有一个数据元素； （ 2）除最后一个位置的数据元素外，其它数据元素位置的后面都只有一个元素。
也就是说，数据元素是一个接一个的排列。因此，可以把线性表想象为一种数据元素序列的数据结构。
线性表就是位置有先后关系，一个接着一个排列的数据结构。
c# 1.1 提供了一个非泛型接口IList接口，接口中的项是object,实现了IList解扣子的类有ArrayList,ListDictionary,StringCollection,StringDictionary.
c# 2.0 提供了泛型的IList<T>接口，实现了List<T>接口的类有List<T>
线性表的接口定义
public interface IListDS<T> {
int GetLength(); //求长度
void Clear(); //清空操作
bool IsEmpty(); //判断线性表是否为空
void Add(T item); //附加操作
void Insert(T item, int i); //插入操作
T Delete(int i); //删除操作
T GetElem(int i); //取表元
T this[int index]{get;}//定义一个索引器 获取元素
int Locate(T value); //按值查找
}
线性表种类
- 顺序表
- 单链表
- 双向链表
- 循环链表
顺序表
在计算机内，保存线性表最简单、最自然的方式，就是把表中的元素一个接一个地放进顺序的存储单元，这就是线性表的顺序存储(Sequence Storage)。线性表的顺序存储是指在内存中用一块地址连续的空间依次存放线性表的数据元素，用这种方式存储的线性表叫顺序表(Sequence List)，如图所示。顺序表的特点是表中相邻的数据元素在内存中存储位置也相邻。
顺序表的存储
假设顺序表中的每个数据元素占w个存储单元，设第i个数据元素的存储地址为Loc(ai)，则有：
Loc(ai)= Loc(a1)+(i-1)*w 1≤i≤n式中的Loc(a1)表示第一个数据元素a1的存储地址，也是顺序表的起始存储地址，称为顺序表的基地址(Base Address)。也就是说，只要知道顺序表的基地址和每个数据元素所占的存储单元的个数就可以求出顺序表中任何一个数据元素的存储地址。并且，由于计算顺序表中每个数据元素存储地址的时间相同，所以顺序表具有任意存取的特点。(可以在任意位置存取东西)
C#语言中的数组在内存中占用的存储空间就是一组连续的存储区域，因此，数组具有任意存取的特点。所以，数组天生具有表示顺序表的数据存储区域的特性。
一个简单的自定义线性表，其实List就是一个线性表
using System;
namespace MyListDS
{
class MainClass
{
static SeqList<int> nums = new SeqList<int> ();
public static void Main (string[] args)
{
nums.Add (1);
nums.Add (2);
nums.Add (3);
nums.Add (4);
printNums ();
nums.Insert (5, 2);
printNums ();
nums.Remove (1);
printNums ();
Console.WriteLine (nums.IndexOf (6));
}
static void printNums() {
for(int i = 0; i < nums.Length(); i++) {
Console.Write(nums[i] + ",");
}
Console.WriteLine();
}
}
public class SeqList<T>:IListDS<T> {
private T[] datas;
private int count = 0;
public SeqList(int size) {
datas = new T[size];
count = 0;
}
public SeqList():this(10) {
}
public int Length() {
return count;
}
public void Clear() {
count = 0;
}
public bool IsEmpty() {
return false;
}
public void Add(T item) {
if (count == datas.Length) {
Console.WriteLine ("数组已存满");
} else {
datas [count] = item;
count++;
}
}
public void Insert(T item, int index) {
if (count == datas.Length) {
Console.WriteLine ("数组已存满");
} else {
for (int i = count - 1; i >= index; i--) {
datas [i + 1] = datas [i];
}
datas [index] = item;
count++;
}
}
public void Remove(int index) {
for (int i = index; i < count; i++) {
datas [i] = datas [i + 1];
}
count--;
}
public T this[int index] {
get{
return datas [index];
}
}
public T GetEle(int index) {
if (index >= 0 && index < count) {
return datas [index];
}
return default(T);
}
public int IndexOf(T value) {
for (int i = 0; i < count; i++) {
if(datas[i].Equals(value)) {
return i;
}
}
return -1;
}
}
public interface IListDS<T> {
int Length();
void Clear();
bool IsEmpty();
void Add(T item);
void Insert(T item, int index);
void Remove(int index);
T this[int index] { get; }
T GetEle(int index);
int IndexOf(T value);
}
}
单链表
顺序表是用地址连续的存储单元顺序存储线性表中的各个数据元素，逻辑上相邻的数据元素在物理位置上也相邻。因此，在顺序表中查找任何一个位置上的数据元素非常方便，这是顺序存储的优点。但是，在对顺序表进行插入和删除时，需要通过移动数据元素来实现，影响了运行效率。线性表的另外一种存储结构——链式存储(Linked Storage)，这样的线性表叫链表(Linked List)。链表不要求逻辑上相邻的数据元素在物理存储位置上也相邻，因此，在对链表进行插入和删除时不需要移动数据元素，但同时也失去了顺序表可随机存储的优点。
单链表的存储
链表是用一组任意的存储单元来存储线性表中的数据元素（这组存储单元可以是连续的，也可以是不连续的）。那么，怎么表示两个数据元素逻辑上的相邻关系呢？即如何表示数据元素之间的线性关系呢？为此，在存储数据元素时，除了存储数据元素本身的信息外，还要存储与它相邻的数据元素的存储地址信息。这两部分信息组成该数据元素的存储映像(Image)，称为结点(Node)。把存储据元素本身信息的域叫结点的数据域(Data Domain)，把存储与它相邻的数据元素的存储地址信息的域叫结点的引用域(Reference Domain)。因此，线性表通过每个结点的引用域形成了一根“链条”，这就是“链表”名称的由来。
如果结点的引用域只存储该结点直接后继结点的存储地址，则该链表叫单链表(Singly Linked List)。把该引用域叫 next。单链表结点的结构如图所示，图中 data 表示结点的数据域。
下图是线性表(a1,a2,a3,a4,a5,a6)对应的链式存储结构示意图
另外一种表示形式
单链表节点定义
using System;
namespace LinkListDS
{
class MainClass
{
static LinkList<int> linkList = new LinkList<int> ();
public static void Main (string[] args)
{
linkList.Add (1);
linkList.Add (2);
linkList.Add (3);
linkList.Add (4);
linkList.PrintList ();
Console.WriteLine ("在第2个位置插入数字5");
linkList.Insert (5, 2);
linkList.PrintList ();
Console.WriteLine ("移除第3位的数字");
linkList.Remove (3);
linkList.PrintList ();
Console.WriteLine ("位于第2位的数字" + linkList [2]);
Console.WriteLine ("位于第1位的数字" + linkList.GetEle (1));
Console.WriteLine ("数字4所在的位置索引为" + linkList.IndexOf (4));
linkList.Clear ();
linkList.PrintList ();
Console.WriteLine (linkList.IsEmpty ());
}
}
public class LinkList<T>:IListDS<T> {
private LinkNode<T> headNode;
public LinkList() {
headNode = null;
}
public int Length() {
LinkNode<T> temp = headNode;
int count = 1;
while (true) {
if (temp.Next != null) {
count++;
temp = temp.Next;
} else {
break;
}
}
return count;
}
public void Clear() {
headNode = null;
}
public bool IsEmpty() {
return headNode == null;
}
public void Add(T item) {
LinkNode<T> newNode = new LinkNode<T> (item);
if (headNode == null) {
headNode = newNode;
} else {
LinkNode<T> temp = headNode;
while (true) {
if (temp.Next != null) {
temp = temp.Next;
} else {
break;
}
}
temp.Next = newNode;
}
}
public void Insert(T item, int index) {
LinkNode<T> newNode = new LinkNode<T> (item);
if (index == 0) {
newNode.Next = headNode;
headNode = newNode;
} else {
LinkNode<T> temp = headNode;
for (int i = 1; i < index; i++) {
temp = temp.Next;
}
LinkNode<T> preNode = temp;
LinkNode<T> currentNode = temp.Next;
preNode.Next = newNode;
newNode.Next = currentNode;
}
}
public void Remove(int index) {
if (index == 0) {
headNode = headNode.Next;
} else {
LinkNode<T> temp = headNode;
for (int i = 1; i < index; i++) {
temp = temp.Next;
}
LinkNode<T> preNode = temp;
LinkNode<T> currentNode = temp.Next;
LinkNode<T> nextNode = currentNode.Next;
preNode.Next = nextNode;
}
}
public T this[int index] { get{
LinkNode<T> temp = headNode;
for (int i = 1; i <= index; i++) {
temp = temp.Next;
}
return temp.Data;
}
}
public T GetEle(int index) {
LinkNode<T> temp = headNode;
for (int i = 1; i <= index; i++) {
temp = temp.Next;
}
return temp.Data;
}
public int IndexOf(T value) {
LinkNode<T> temp = headNode;
int n = 0;
while (true) {
if (temp.Next != null) {
temp = temp.Next;
n++;
if (temp.Data.Equals(value)) {
break;
}
} else {
n = -1;
break;
}
}
return n;
}
public void PrintList() {
if (headNode == null) {
Console.WriteLine("null");
return;
}
LinkNode<T> temp = headNode;
string str = headNode.Data + ",";
while (true) {
if (temp.Next != null) {
temp = temp.Next;
str += temp.Data + ",";
} else {
break;
}
}
str = str.Remove (str.Length - 1);
Console.WriteLine(str);
}
}
public interface IListDS<T> {
int Length();
void Clear();
bool IsEmpty();
void Add(T item);
void Insert(T item, int index);
void Remove(int index);
T this[int index] { get; }
T GetEle(int index);
int IndexOf(T value);
}
class LinkNode<T> {
private T data;
private LinkNode<T> next;
public LinkNode(T value) {
data = value;
}
public LinkNode(T value, LinkNode<T> next) {
data = value;
this.next = next;
}
public LinkNode(LinkNode<T> next) {
this.next = next;
}
public LinkNode() {
data = default(T);
next = null;
}
public T Data {
get { return data; }
set { data = value; }
}
public LinkNode<T> Next {
get { return next; }
set { next = value; }
}
}
}
双向链表
前面介绍的单链表允许从一个结点直接访问它的后继结点，所以, 找直接后继结点的时间复杂度是 O(1)。但是,要找某个结点的直接前驱结点，只能从表的头引用开始遍历各结点。如果某个结点的 Next 等于该结点，那么，这个结点就是该结点的直接前驱结点。也就是说，找直接前驱结点的时间复杂度是 O(n)， n是单链表的长度。当然，我们也可以在结点的引用域中保存直接前驱结点的地址而不是直接后继结点的地址。这样，找直接前驱结点的时间复杂度只有 O(1)，但找直接后继结点的时间复杂度是 O(n)。如果希望找直接前驱结点和直接后继结点的时间复杂度都是 O(1)，那么，需要在结点中设两个引用域，一个保存直接前驱结点的地址，叫 prev，一个直接后继结点的地址，叫 next，这样的链表就是双向链表(Doubly Linked List)。双向链表的结点结构示意图如图所示。
public class DbNode<T>
{
private T data; //数据域
private DbNode<T> prev; //前驱引用域
private DbNode<T> next; //后继引用域
//构造器
public DbNode(T val, DbNode<T> p)
{
data = val;
next = p;
}
//构造器
public DbNode(DbNode<T> p)
{
next = p;
}
//构造器
public DbNode(T val)
{
data = val;
next = null;
}
//构造器
public DbNode()
{
data = default(T);
next = null;
}
//数据域属性
public T Data
{
get { return data; }
set { data = value; }
}
//前驱引用域属性
public DbNode<T> Prev
{
get { return prev; }
set { prev = value; }
}
//后继引用域属性
public DbNode<T> Next
{
get { return next; }
set { next = value; }
}
}
双向链表插入示意图
循环链表
有些应用不需要链表中有明显的头尾结点。在这种情况下，可能需要方便地从最后一个结点访问到第一个结点。此时，最后一个结点的引用域不是空引用，而是保存的第一个结点的地址（如果该链表带结点，则保存的是头结点的地址），也就是头引用的值。带头结点的循环链表(Circular Linked List)如图所示。
