C# 顺序表
非常标准的顺序表结构，等同于C#中的List<T>，但是List<T>在排错查询和数据结构替换上存在缺陷，一些情况会考虑使用自己定义的数据结构
1.优化方向 下表使用冒泡排序，可以考虑优化算法
/*************************************** 作者: 未闻花语 版本: v1.5 最后修改时间: 2018/05/18 电话: 159****7727 功能&使用方法: * 泛型顺序表 [Update] * 1.新增了预扩容功能 （新增了一个构造函数 在创建之初设置其容量大小） * 2.所有判断相等的方法都是通过 委托传入 包括 “排序”及 “判断是否存在” * 3.扩容大小为原大小的1.5倍， 如果觉得不合适 可自行调整 一般为1.5倍 * 4.增加了插入函数 * 5.添加了预扩容的安全校验 * * 优点: * 1.无需为表示表中对象的关系而增加额外的存储空间 * 2.可以快速的获取表中任一位置的数据 * 3.C#中的List就是使用的这种存储形式 * * 缺点： * 1.插入和删除操作 移动的元素过多 时间开销大 * 2.长度增长时对内存开销较大（现在修改为原数据的大小的1.5倍） * ，会存在内存浪费！一般称为内存碎片。 * * 适用： * 适用于数据长度变化不大 且 索取频繁的情况 * * * 存在方法： * <0> ----------- MyArrayList<T>() -------- 无参构造 * <1> ----------- Size() ------------------ 得到使用空间 * <2> ----------- Expansion()（私有）------ 扩容 * <3> ----------- Add(T data) ------------- 添加数据 * <4> ----------- (r)T At(int index) ------ 得到数据 * <5> ----------- Clear() ----------------- 清空数据 * <6> ----------- (r)T this[int index] ---- 得到/设置 数据【索引器】 * <7> ----------- SortSmallToBig() -------- 排序(从小到大)（冒泡排序） * <8> ----------- Show(Action<T>) --------- 自定义打印 * <9> ----------- Contains(T) ------------- bool类型返回是否包含这个东西 * <10> ---------- Insert(T _data, int _index) 插入 * <11> ---------- Delete(_index) ---------- 删除数据 * * 存在属性： * Capacity ------ 容量 * Size ---------- 当前使用空间 ***************************************/ #if UNITY_EDITOR using UnityEngine; #endif using System.Collections; using System; namespace MyList { public class MyArrayList<T> { //容量 int m_capacity; //使用量 int m_size; //堆 --- 指针 T[] obj; //构造0 (无参构造) public MyArrayList() { //内存容量 (默认为4) m_capacity = 4; //空间使用量归0 m_size = 0; //开堆 obj = new T[m_capacity]; } //构造1 (带参构造) public MyArrayList(int _capacity) { //内存容量 m_capacity = _capacity > 1 ? _capacity : 2; //空间使用量归0 m_size = 0; //开堆 obj = new T[m_capacity]; } //方法 --- 扩容 void Expansion() { //容量 == 使用量 if (m_size == m_capacity) { ////容量扩大一倍 //m_capacity *= 2; //容量扩大为原来的1.5倍 m_capacity = (int)(m_capacity * 1.5); //数据开堆 T[] nt = new T[m_capacity]; //复制数据 for (int i = 0; i < m_size; ++i) { nt[i] = obj[i]; } //修改数据结构指针指向 obj = nt; } } //方法 --- 数据添加 public void Add(T data) { //扩容 Expansion(); //放入数据 obj[m_size++] = data; } //方法 --- 插入 public void Insert(T _data, int _index) { //容量检查 Expansion(); //移动数据 for (int i = Size; i > _index; i--) { obj[i] = obj[i - 1]; } //填入数据 obj[_index] = _data; m_size++; } //方法 --- 得到数据[下标索引] public T At(int index) { //参数检查 if (index < 0 || index >= m_size) return default(T); else return obj[index]; } //方法 --- 清空 public void Clear() { //使用空间修改为0就可以了 m_size = 0; } //索引器a public T this[int index] { set { //设置数据 在 范围内 if (index >= 0 && index < m_size) { obj[index] = value; } } get { if (index >= 0 && index < m_size) return obj[index]; else return default(T); } } //声明委托 //case 1 -------------- Left > Right //case 0 -------------- Left == Right //case -1 -------------- Left < Right public delegate int CompareTo(T _objLeft, T _objRight); //方法 --- 排序(冒泡) public void SortSmallToBig(CompareTo CTF) { //冒泡排序 for (int i = 0; i < m_size; ++i) { for (int j = m_size - 1; j > i; --j) { if (CTF(obj[i], obj[j]) > 0) { T temp = obj[i]; obj[i] = obj[j]; obj[j] = temp; } } } } //遍历显示(C#控制台显示) public void Show(Action<T> _func) { //遍历 for (int i = 0; i < m_size; ++i) { //这个显示方式比 _func(obj[i]); } } //遍历查找 public bool Contains(T t, CompareTo CTF) { //遍历 for (int i = 0; i < m_size; ++i) { if (CTF(t, obj[i]) == 0) { return true; } } //否则return false return false; } //属性 ----- 返回容量 public int Capacity { get { return m_capacity; } } //属性 ----- 返回使用空间 public int Size { get { return m_size; } } //删除数据 public void Delete(int _index) { if (_index < 0 || _index > m_size - 1) return;
for (int i = _index; i < m_size; ++i)
{
if (i - 1 < 0)
continue;
obj[i - 1] = obj[i];
}
m_size--;
}
}
}
C# 链表（单向无头）
单向非闭环，无表头的链表，一般用于非队尾数据需要进行频繁删减的情况，由于没有表头所有排序算法写的有点low
1.优化方向，改成双向链表，但是改成双向链表会花点时间因为指针的操作比较多，很容易出现闭环的情况如下图
/***************************************
作者: 未闻花语
版本: v1.2
最后修改时间: 2018/05/20
电话: 159****7727
功能&使用方法:
* 泛型单向链表 [Update]
* 修改了Show函数的一个bug
* 没有表头！！
*
* 优点:
* 1.自然是插入和排序时，速度较快
* 2.当元素数目区间不确定时，不会有较大空间的浪费
*
* 缺点：
* 1.平凡的内存申请与销毁（可通过 修改成带缓存的链表或使用对象池来解决）
* 2.相较于顺序表 略微增加了内存开销
* 3.相较于顺序表 下标查询略微缓慢
*
* 适用：
* 适用于数据长度不确定，又存在平凡删减的情况
*
*
* 存在方法：
* <0> ----------- Add(T data) ------------- 添加数据
* <1> ----------- (r)T At(int index) ------ 得到数据[索引器]
* <2> ----------- Delete(_index) ---------- 删除数据
* <3> ----------- Inset(T _data, int _index) 插入数据
* <4> ----------- Clear() ----------------- 清空数据
*
* 存在属性：
* Capacity ------ 容量
* Size ---------- 当前使用空间
***************************************/
using System;
class Node<T>
{
private T m_data;
public T Data { get { return m_data; } set { m_data = value; } }
private Node<T> m_next;
public Node<T> Next { get { return m_next; } set { m_next = value; } }
public Node(T _data)
{
Data = _data;
this.Next = default(Node<T>);
}
}
public class JWMyLinkList<T>
{
//表头
Node<T> m_head;
//表长
private int m_size;
public int Size { get { return m_size; } }
//构造
public JWMyLinkList()
{
m_size = 0;
m_head = null;
}
//添加数据
public void Add(T _data)
{
Node<T> nNote = new Node<T>(_data);
if (Size == 0)
{
m_head = nNote;
}
else
{
Node<T> p = m_head;
while (p.Next != null)
{
p = p.Next;
}
p.Next = nNote;
}
m_size++;
}
//删除数据
public bool Delete(int _index)
{
if (_index < 0 || _index > Size - 1)
return false;
if (_index == 0)
{
m_head = m_head.Next;
m_size--;
return true;
}
Node<T> preP = m_head;
Node<T> afterP = m_head;
for (int i = 0; i < _index - 1; ++i)
preP = preP.Next;
if (_index == Size - 1)
afterP = null;
else
{
for (int i = 0; i < _index + 1; ++i)
afterP = afterP.Next;
}
preP.Next = afterP;
m_size--;
return true;
}
//插入数据
public bool Insert(T _data, int _index)
{
if (_index < 0 || _index > Size - 1)
return false;
Node<T> nNote = new Node<T>(_data);
if (_index == 0)
{
nNote.Next = m_head;
m_head = nNote;
m_size++;
return true;
}
Node<T> preP = m_head;
for (int i = 0; i < _index - 1; ++i)
preP = preP.Next;
nNote.Next = preP.Next;
preP.Next = nNote;
m_size++;
return true;
}
//得到数据
public T At(int _index)
{
T r = default(T);
if (_index < 0 || _index > Size - 1)
return r;
Node<T> P = m_head;
for (int i = 0; i < _index; ++i)
P = P.Next;
r = P.Data;
return r;
}
//索引器a
public T this[int _index]
{
set
{
//设置数据 在 范围内
if (_index >= 0 && _index < m_size)
{
Node<T> P = m_head;
for (int i = 0; i < _index; ++i)
P = P.Next;
P.Data = value;
}
}
get
{
if (_index >= 0 && _index < m_size)
{
Node<T> P = m_head;
for (int i = 0; i < _index; ++i)
P = P.Next;
return P.Data;
}
else
return default(T);
}
}
//清除数据
public void Clear()
{
if (m_size < 1)
return;
Node<T> A = m_head;
Node<T> B = A;
do
{
B = B.Next;
A.Next = null;
A = B;
} while ((B != null));
m_size = 0;
}
//声明委托
//case 1 -------------- Left > Right
//case 0 -------------- Left == Right
//case -1 -------------- Left < Right
public delegate int CompareTo(T _objLeft, T _objRight);
//判断存在 CompareTo CTF
public bool Contains(T _data, CompareTo CTF)
{
Node<T> A = m_head;
while (A != null)
{
if (CTF(A.Data, _data) == 0)
return true;
A = A.Next;
}
return false;
}
//遍历显示
public void Show(Action<T> _func)
{
if (m_size == 0)
return;
//遍历
Node<T> A = m_head;
while (A != null)
{
//这个显示方式比
_func(A.Data);
A = A.Next;
}
}
//方法 --- 排序(冒泡)
public void SortSmallToBig(CompareTo CTF)
{
//安全校验
if (Size < 2)
return;
Node<T> A = m_head;
Node<T> B = m_head;
//冒泡排序
for (int i = 0; i < m_size; ++i)
{
A = m_head;
B = A;
for (int j = m_size - 1; j > i; --j)
{
if (CTF(A.Next.Data, A.Data) < 0)
{
if (m_head == A)
{
m_head = A.Next;
A.Next = A.Next.Next;
m_head.Next = A;
B = m_head;
}
else
{
B.Next = A.Next;
A.Next = B.Next.Next;
B.Next.Next = A;
B = B.Next;
}
}
else
{
if (m_head != A)
{
B = B.Next;
}
A = A.Next;
}
}
}
}
}
测试运行程序
用于测试上述表的运行程序 & 结果
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; //包含命名空间 MyList using MyList; namespace DataStructure { class Program { static void Main(string[] args) { //随机名字的数组 string[] rNameSpace = new string[] {"蒋伟","吴悦","曾真","刘芸", "珠海妮","李小满","薛涵","邱伊雨","李晶晶","戴林江","代安东","黄挺", "陈政","叶小青","徐逸"}; //随机用户数 //(PS:测试用,没写限制 所以不要太大 最好不要超过10个) const int studentCount = 5; //开堆 //var team0 = new MyArrayList<Student>(3); var team0 = new MyLinkList<Student>(); Student[] students = new Student[studentCount]; //随机出现数据 并添加 当随机种子一样是数据一样 Random ra = new Random(6); for (int i = 0; i < studentCount;) { int id = ra.Next(1, 30); string name = rNameSpace[ra.Next(0, rNameSpace.Length)]; bool isGirl = ra.Next(0, 2) == 0 ? false : true; Student s0 = new Student(id, name, isGirl); //查找是否有相同的属性 if (team0.Contains(s0, StudentJudgeFunc0)) { continue; } else { team0.Add(s0); ++i; } } //遍历显示 & 属性调用 Console.WriteLine(""); Console.WriteLine("==================== 分割线 ===================="); Console.WriteLine(""); team0.Show(ShowFunc); Console.WriteLine(); //Console.WriteLine(string.Format("当前顺序表 --- 容量 ： {0}", team0.Capacity)); Console.WriteLine(string.Format("当前XX表 --- 大小 ： {0}", team0.Size)); Console.WriteLine(string.Format("下表索引器测试 --- 下标3姓名 ： {0}", team0[3].m_name)); Console.WriteLine(""); Console.WriteLine("==================== 排序后 ===================="); Console.WriteLine(""); team0.SortSmallToBig(StudentJudgeFunc0); team0.Show(ShowFunc); Console.WriteLine(""); Console.WriteLine("==================== 插入&删除测试 ===================="); Console.WriteLine(""); team0.Insert(new Student(16, rNameSpace[1], true), 2); team0.Delete(1); team0.Show(ShowFunc); Console.WriteLine(""); Console.WriteLine("==================== 清空测试 ===================="); Console.WriteLine(""); team0.Clear(); team0.Show(ShowFunc); } //比较函数 static int StudentJudgeFunc0(Student s0, Student s1) { if (s0.m_id == s1.m_id || s0.m_name.Equals(s1.m_name)) return 0; if (s0.m_id > s1.m_id) return 1; else return -1; } //显示函数 static void ShowFunc(Student _stu) { Console.WriteLine(string.Format("{1} [{0}] ---- {2}", _stu.m_id, _stu.m_name, _stu.m_isGirl ? "Gril" : "Boy")); } } class Student { //学号 public int m_id; //姓名 public string m_name; //性别 public bool m_isGirl; //构造 public Student(int _id, string _name, bool _isGirl) { m_id = _id; m_name = _name; m_isGirl = _isGirl; } } }
备注：
链表 Clear While循环条件错误，已经修改！