这次的数据结构示例包括顺序表和单链表。已调试完毕。
- IListDS.cs：
using System;
namespace ListDS
{
//首先定义接口，列出了顺序表和单链表都将实现的功能
interface IListDS<T>
{
void Add(T item);
T Delete(int index);
T GetElem(int index);
int GetLength();
int Locate(T value);
void Clear();
void Insert(T item, int index);
}
}
- SeqList<T>.cs
using System;
namespace ListDS
{ //顺序表
//所有index从1开始，符合普遍的认知习惯
class SeqList<T>:IListDS<T>
{
T[] data; //存放数据元素
int count; //表示数据个数
public SeqList (int length) //重载构造函数
{
//顺序表的一个特点就是定长，当然如果长度不够可依需增加长度，
//但这本质上是通过增大长度实现扩容，其实也是定长的
data = new T[length];
count = 0;
}
public SeqList () : this (10) //采用初始化列表实现默认构造函数
{
}
public void Add (T item)
{
if (count == data.Length)
Console.WriteLine ("数组已满");
else {
data [count] = item;
count++;
}
}
//所有参数index定义为从1开始
public T Delete (int index)
{
//保留被删数据
T temp = data [index-1];
//index-1是元素在数组中的实际位置，从这个位置到最后，数据前移
for (int i = index-1; i < count - 1; i++) {
data [i] = data [i + 1];
}
count--;
return temp;
}
public T GetElem (int index)
{
if (index > 0 && index <= count)
return data [index-1];
else {
Console.WriteLine ("不存在");
return default(T);
}
}
public int GetLength ()
{
return count;
}
public int Locate (T value)
{
for (int i = 0; i < count; i++) {
if (data [i].Equals (value)) {
return i+1; //保持与index认知一致性
}
}
return -1;
}
public void Clear ()
{
count = 0;
}
public void Insert (T item, int index)
{
if (index > count)
Console.WriteLine ("越界");
else {
count++; //个数先加一，不然最后一个数据移动越界
//count从0开始所以到是第二个的实际数组位置是count-1-1
for (int i = count-2; i >=index-1; i--)
data[i + 1] = data[i]; //数据后移
data[index-1] = item;
}
}
}
}
- Node.cs
using System;
namespace ListDS
{ //实现单链表前先定义Node
public class Node<T>
{
T data; //数据
Node<T> next; //尾指针
public Node(){
data = default(T);
next = null;
}
public Node(T value){
data = value;
next = null;
}
public T Data {
get{ return data;}
set{ data = value;}
}
public Node<T> Next {
get{ return next;}
set{ next = value;}
}
}
}
- LinkList.cs
using System;
namespace ListDS
{
//单链表
//所有index全部从1开始，符合普遍的认知习惯.
class LinkList<T>:IListDS<T>
{
//创建头结点，是链表操作具有统一性
Node<T> head;
public LinkList ()
{
head = null;
}
public void Add (T item)
{
//新建节点
Node<T> newNode = new Node<T> (item);
//如果头结点为空，则将头结点指向新节点
if (head == null)
head = newNode;
else {
//创建一个暂时的遍历点
Node<T> temp = head;
//向后遍历
while (temp.Next != null)
temp = temp.Next;
//新节点连接到表尾
temp.Next = newNode;
}
}
public T Delete (int index)
{
T record = default(T);
if (head == null)
Console.WriteLine ("链表已空");
//删除头节点
else if (index == 1) {
record = head.Data;
head = head.Next;
}
else {
Node<T> temp = head;
int count = 1;
//先数一下存在多少个节点
while (temp.Next != null) {
count++;
temp = temp.Next;
}
if (count < index)
Console.WriteLine ("要删除的节点不存在");
else {
//注意将temp重新置为头结点位置，因为它在之前遍历节点数时已经移到最后
temp = head;
//遍历到指定节点的前一个节点停止
for (int i = 1; i < index-1; i++)
temp = temp.Next;
//记录删除点信息
record = temp.Next.Data;
//尾指针重定位
temp.Next = temp.Next.Next;
}
}
return record;
}
//假设此处index不越界，省得再遍历一遍了
public T GetElem (int index)
{
Node<T> temp = head;
for (int i = 1; i < index; i++)
temp = temp.Next;
return temp.Data;
}
public int GetLength ()
{
Node<T> temp = head;
int count = 1;
while (temp.Next != null) {
count++;
temp = temp.Next;
}
return count;
}
public int Locate (T value)
{
Node<T> temp = head;
int index = 1;
while (temp.Next != null) {
if (!temp.Data.Equals (value)) {
index++;
temp = temp.Next;
} else
break;
}
return index;
}
public void Clear ()
{
head = null;
//原来的节点数据被自动回收
}
public void Insert (T item, int index)
{
//先新建节点
Node<T> newNode = new Node<T> (item);
if (head == null) {
head = newNode;
} else {
//处理奇葩输入
if (index < 1)
Console.WriteLine ("看看清楚，位置不对");
else {
Node<T> temp = head;
//遍历到指定点的前一个节点
for(int i=1 ;i<index-1;i++ ){
temp = temp.Next;
}
//循序不可变
newNode.Next = temp.Next.Next;
temp.Next = newNode;
}
}
}
}
}
网友评论