第一、创建一个接口
为了统一顺序表和链表的方法命名，先创建一个接口，里面定义了一般线性表所有方法的名称。
定义接口的原因：1.外部对不论顺序表还是链表的操作是一样的；2.但是顺序表和链表的具体方法实现不一样
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace case1
{//这是一个接口，头字母用I
//定义接口的原因：1.外部对不论顺序表还是链表的操作是一样的；2.但是顺序表和链表的具体方法实现不一样
//因此，接口只定义方法（不定义变量）。但是顺序表和链表由于具体的方法实现不同，所以要定义“私有”变量。
interface IList
{
int GetLength();
void Clear();
bool IsEmpty();
void Add(T item);
void Insert(T item, int index);
T Delete(int index);
T this[int index] { get; }
T GetEle(int index);
int Locate(T valve);
}
}
接口定义完成。
第二、实现顺序表
继承接口，把接口中所有的方法都实现。
//这是一个顺序表
//顺序表实现方式
class SeqList : IList
{
private T[] data;//用来存储数据
private int count = 0;//表示存储了多少个数据
public SeqList(int size)//size就是最大容量
{
data = new T[size];
count = 0;
}
public SeqList() : this(10)//默认构造函数，容量是10
{//这个方法引用了上面的方法，用this
}
public T this[int index]
{//索引器，可以让类像数组一样，直接访问中间变量 test[i]
get { return GetEle(index); }
}
public void Add(T item)
{
if (count == data.Length)
{
Console.WriteLine("当前数组已满");
}
else
{
data[count] = item;
count++;
}
}
public void Clear()
{
count = 0;
}
public T Delete(int index)
{
T temp = data[index];
for (int i = index + 1; i < count; i++)
{
data[i - 1] = data[i];//把数据向前移动
}
count--;
return temp;
}
public T GetEle(int index)
{
if (index >= 0 && index <= count - 1)//索引存在
{
return data[index];
}
else
{
Console.WriteLine("索引不存在");
return default(T);
}
}
public int GetLength()
{
return count;
}
public void Insert(T item, int index)
{
for (int i = count - 1; i >= index; i--)//从后往前遍历
{
data[i + 1] = data[i];
}//index后面的数据往后移动一位
data[index] = item;
count++;
}
public bool IsEmpty()
{
return count == 0;
}
public int Locate(T valve)
{
for (int i = 0; i < count; i++)
{
if (data[i].Equals(valve))
{
return i;
}
}
return -1;
}
}
第三、定义链中的结点
链表的结点包含两个元素，一是数据，二是指针（指向下一个结点）。
数据就用泛型。指针就用这个结点的类。并不是像C语言中的指针这样真正意义上的指针。这里的指针就是下一个结点本身。
class Node{//单链表的结点 //定义了结点构造函数和“私有”变量 private T data;//存储数据 private Node next;//指针 用来指向下一个元素 //下面有四个构造函数 public Node() { data = default(T); next = null; } public Node(T value) { data = value; next = null; } public Node(T value, Node next) { this.data = value; this.next = next; } public Node(Node next) { this.next = next; } //获取设置变量data public T Data { get { return data; } set { data = value; } } //获取设置变量next public Node Next { get { return next; } set { next = value; } } }
由于next指针的本质就是结点，所以在这个结点的类中又定义了这个类本身的实例指针。
所以可以理解为套娃：结点包含有子成员——下一个结点，也就是指针。
第四、实现链表
class LinkList: IList { private Node head;//存储一个头结点 //构造函数 public LinkList() { head = null; } public T this[int index] { get { return GetEle(index); } } public void Add(T item) { Node newNode = new Node (item);//根据新的数据创建一个新的结点 //如果结点为空，那么这个新的结点就是头结点 if (head == null) { head = newNode; } else {//把新来的结点放到链表的尾部 //要访问链表的尾结点 Node temp = head; while (true) { if(temp.Next!=null) { temp = temp.Next; } else { break; } } temp.Next = newNode; } } public void Clear() { head = null;//后面会自动回收 } public T Delete(int index) { T data = default(T); if (index == 0) { data = head.Data; head = head.Next; } else { Node temp = head; for (int i = 0; i < index; i++) { //让temp向后移动一个位置 temp = temp.Next; } Node preNode = temp; Node currentNode = temp.Next; data = currentNode.Data; Node nextNode = temp.Next.Next; preNode.Next = nextNode; } return data; } public T GetEle(int index) { Node temp = head; for (int i = 0; i < index; i++) { //让temp向后移动一个位置 temp = temp.Next; } return temp.Data; } public int GetLength() { if (head == null) return 0; Node temp = head; int count = 1; while (true) { if (temp.Next != null) { count++; temp = temp.Next; } else { break; } } return count; } public void Insert(T item, int index) { Node newNode = new Node (item); if (index == 0) { newNode.Next = head; head = newNode; } else { Node temp = head; for(int i = 0; i < index; i++) { //让temp向后移动一个位置 temp = temp.Next; } Node preNode = temp; Node currentNode = temp.Next; preNode.Next = newNode; newNode.Next = currentNode; } } public bool IsEmpty() { return head == null; } public int Locate(T value) { Node temp = head; if (temp == null) { return -1; } else { int index = 0; while (true) { if (temp.Data.Equals(value)) { return index; } else { if (temp.Next != null) { temp = temp.Next; } else { break; } } } return -1; } } }
可见链表中的方法和顺序表中的方法名称都一样，都是接口中的方法。而且都实现了一样的功能。
实例化顺序表和链表，测试功能
class Program
{
static void Main(string[] args)
{
//1.使用顺序表
//IList seqList = new SeqList();
//2.使用链表（当前使用）
IList seqList = new LinkList();
seqList.Add("123");
seqList.Add("456");
seqList.Add("789");
Console.WriteLine(seqList.GetEle(0));
Console.WriteLine(seqList[0]);
seqList.Insert("777", 1);
for (int i = 0; i < seqList.GetLength(); i++)
{
Console.Write(seqList[i] + " ");
}
Console.WriteLine();
seqList.Delete(0);
for (int i = 0; i < seqList.GetLength(); i++)
{
Console.Write(seqList[i] + " ");
}
Console.WriteLine();
seqList.Clear();
Console.WriteLine(seqList.GetLength());
Console.ReadLine();
}
}
可以把上面所有的类和接口都放在一个源文件里；也可以各自放在一个源文件里，但是要放在一个项目/命名空间下。
结果当然都一样，如果不一样，那就要去顺序表或者链表中调啦。
