原生C++
/*******************************************************************************************
文件名 ： _List.h
作者 ： 李锋
功能 ： 链表
手机 ： 13828778863
Email : ruizhilf@139.com
创建时间 ： 2016年07月31日
最后一次修改时间 : 2024年07月30日
/// 链表是一种用来存储数据集合的数据结构。链表具有如下属性
///（1）元素通过指针依次相连
///（2）最后一个元素的指针为空（null）。
///（3）在程序的执行过程中，链表的长度可以自由伸缩。
///（4）链表的长度可以要求的任意长度（除非系统内存耗尽）。
///（5）它不会浪费内存空间（但会需要额外的内存空间存储指针）。
记住： Virtual C++ Bug: 模板继承用到父类成员访问时，要用 this->
********************************************************************************************/
#ifndef __LIST_H_
#define __LIST_H_
#include "_Macro.h"
#include "_Memory.h"
#include "_ByteArray.h"
#include "_Pair.h"
#include "_IteratorBase.h"
_LF_BEGIN_
template<class T> class _DList; //前置声明
/// <summary>
/// 排序顺序
/// </summary>
enum class _SortOrder
{
s_Minmax = 0, //从小到大
s_Maxmin = 1, //从大到小
s_null = 2 //无排序顺序
};
/// <summary>
/// 单链表节点
/// </summary>
/// <typeparam name="T"></typeparam>
/// 创建时间 2021年10月23日 最后一次修改时间 : 2021年10月23日
template<class T>
class _SListNode
{
public:
/// <summary>
/// 节点数据
/// </summary>
T Data;
/// <summary>
/// 下一个节点
/// </summary>
_SListNode<T>* Next;
/// <summary>
/// 构造函数
/// </summary>
/// <param name="aData"></param>
_SListNode(T aData)
{
Data = aData;
}
};
/// <summary>
/// C#语句：public class _DListNode<T>
/// </summary>
/// <typeparam name="T">默认数据</typeparam>
template<class T>
class _DListNode
{
public:
/// <summary>
/// 节点数据
/// </summary>
T Data;
/// <summary>
/// 前一个节点
/// </summary>
_DListNode<T>* Prev;
/// <summary>
/// 下一个节点
/// </summary>
_DListNode<T>* Next;
/// <summary>
/// 构造函数
/// </summary>
/// <param name="aData">默认数据</param>
_DListNode(const T& aData)
{
Data = aData;
Prev = null;
Next = null;
}
_DListNode()
{
Prev = null;
Next = null;
Data = T();
}
};
/// <summary>
/// 单链表：
/// 通常我们说的链表指的是单链表（singly linked list）。单链表包括一组结点，每个结
/// 点有一个 next 指针域，用来存储指向（逻辑上）下一个元素对应结点的指针。最后一个结点的
/// next指针域的值为null，这预示着已经到达链表的尾部。
///
/// </summary>
/// <typeparam name="T"></typeparam>
template<class T>
class _SList : public _Object
{
private:
/// <summary>
/// 第一个结点
/// </summary>
_SListNode<T>* _First;
/// <summary>
/// 结点数
/// </summary>
int _Count;
public:
inline const int& Count() { return _Count; }
inline const _SListNode<T>* First() { return _First; }
};
//------------------------------------------LDIterator
//参考网址： https://blog.csdn.net/qq_28398301/article/details/106321525 C++用for遍历自定义类
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
template<class T>
class _DListNodeIterator
{
public:
using value_type = T;
public:
/// <summary>
/// 当前节点
/// </summary>
_DListNode<T>* _Ptr; //命名与标库相同 _pCurrentNode;
/// <summary>
/// 当前链表
/// </summary>
const _DList<T>* _pCurrentList;
inline _DListNodeIterator()
{
_pCurrentList = null;
_Ptr = null;
}
inline _DListNodeIterator(const _DList<T>* pCurrentList)
{
assert(pCurrentList != null);
_pCurrentList = (_DList<T>*)pCurrentList;
_Ptr = null;
}
/// <summary>
/// 构造函数，传值迭代器管理的值
/// </summary>
/// <param name="pNode"></param>
inline _DListNodeIterator(const _DListNode<T>* pCurrentNode, const _DList<T>* pCurrentList)
{
_Ptr = (_DListNode<T>*)pCurrentNode;
_pCurrentList = (_DList<T>*)pCurrentList;
}
inline _DListNodeIterator(const _DListNodeIterator& it)
{
_Ptr = it._Ptr;
_pCurrentList = it._pCurrentList;
}
/*
/// <summary>
/// 比较实现
/// </summary>
/// <param name="that"></param>
/// <returns></returns>
bool operator != (const _DListNodeIterator& that) { return _pNode != that._pNode; }
bool operator > (const _DListNodeIterator& right) { return _pNode->Data > right._pNode->Data; }
bool operator < (const _DListNodeIterator& right) { return _pNode->Data < right._pNode->Data; }
/// <summary>
/// 自增实现
/// </summary>
/// <returns></returns>
inline _DListNodeIterator& operator ++ () { _pNode = _pNode->Next; return *this; }
/// <summary>
/// lf::_DList<int> d = { 1,3,5,8,2 };
/// auto it1 = d.begin();
/// cout << *it1 << "\n"; // 输出：1
/// cout << *(it1 + 2) << "\n"; // 输出：5
/// </summary>
/// <param name="nDiff"></param>
/// <returns></returns>
/// 创建时间： 2024-07-01 最后一修改时间：2024-07-01
inline _DListNodeIterator operator+(const size_t nDiff) {
_DListNodeIterator result(_pNode);
for (int n = 0; n < nDiff; ++n)
{
result._pNode = result._pNode->Next;
}
return result;
}
/// <summary>
/// 解引用，取值
/// </summary>
/// <typeparam name="T"></typeparam>
T& operator * () { return _pNode->Data; }
//LDIterator(const LDIterator&) = delete;
//LDIterator& operator=(const LDIterator&) = delete;
//~LDIterator() = default;
*/
public: //----------------------------重写
/// <summary>
/// 解引用，取值
/// </summary>
/// <typeparam name="T"></typeparam>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-03
inline T& operator * () const { return _Ptr->Data; }
/// <summary>
/// 向前移动为正，向后移动为负
/// </summary>
/// <param name="iDiff"></param>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-02
inline virtual void Move(const int& iDiff)
{
if (iDiff == 0) return;
if (iDiff > 0){
if (_Ptr == null) //已经是最后了，不能向后移了
{
return;
}
int n = 0;
while (true){
_Ptr = _Ptr->Next;
++n;
if (n == iDiff){ return; }
}
}else{
int n = 0;
if (_Ptr == null) {//向前移，减-1进入未尾元素
_Ptr = _pCurrentList->Last();
n = -1; //已经向前移了一位
if (n == iDiff) { return; }
}
while (true){
_Ptr = _Ptr->Prev;
--n;
if (n == iDiff){ return; }
}
}
throw "未重写代码？";
}
/// <summary>
///
/// </summary>
/// <param name="right"></param>
/// <returns></returns>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-02
inline _DListNodeIterator operator+(const int& iDiff)const {
_DListNodeIterator itResult(*this);
itResult.Move(iDiff);
return itResult;
}
/// <summary>
///
/// </summary>
/// <param name="right"></param>
/// <returns></returns>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-02
inline _DListNodeIterator operator-(const int& iDiff)const {
_DListNodeIterator itResult(*this);
itResult.Move(-iDiff);
return itResult;
}
/// <summary>
///
/// </summary>
/// <param name="r"></param>
/// <returns></returns>
/// 创建时间：2024-07-03 最后一次修改时间：2024-07-25
inline int operator-(const _DListNodeIterator& r)const {
int n1 = _pCurrentList->FindNodeIndex(_Ptr);
int n2 = _pCurrentList->FindNodeIndex(r._Ptr);
//assert(n1 != -1 && n2 != -1);
//确保 _pCurrentList->end() - _pCurrentList->begin() == _pCurrentList->Count
//超过边界，指针都设为指向最后一位元素的下一位
if (n1 == -1) n1 = _pCurrentList->Count;
if (n2 == -1) n2 = _pCurrentList->Count;
return n1 - n2;
}
/// <summary>
/// 前置加加
/// </summary>
/// <returns></returns>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-02
inline _DListNodeIterator& operator++() { Move(1); return *this; }
/// <summary>
/// 前置减减
/// </summary>
/// <returns></returns>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-02
inline _DListNodeIterator& operator--() { Move(-1); return *this; }
/// <summary>
/// 后置加加
/// </summary>
/// <param name=""></param>
/// <returns></returns>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-02
inline _DListNodeIterator operator++(int) {
_DListNodeIterator sResult(*this);
Move(1);
return sResult;
}
/// <summary>
/// 后置减减
/// </summary>
/// <param name=""></param>
/// <returns></returns>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-02
inline _DListNodeIterator operator--(int) {
_DListNodeIterator sResult(*this);
Move(-1);
return sResult;
}
/// <summary>
///
/// </summary>
/// <param name="r"></param>
/// <returns></returns>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-02
inline _DListNodeIterator& operator+=(const int& iDiff) {
Move(iDiff);
return *this;
}
/// <summary>
///
/// </summary>
/// <param name="r"></param>
/// <returns></returns>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-02
inline _DListNodeIterator& operator-=(const int& iDiff) {
Move(iDiff);
return *this;
}
/// <summary>
/// 关联代码：
/// _DList<int> d = { 1,3,53,55,35,97,35,10 };
/// d.end() - d.begin(); //8
/// </summary>
/// <param name="r"></param>
/// <returns></returns>
/// 创建时间：2024-07-03 最后一次修改时间：2024-07-03
inline int operator-(const _DListNodeIterator& r)
{
//note1 到最未尾的索引
//note2 到最未尾的索引
int i1 = 0, i2 = 0;
auto pNode1 = _Ptr;
auto pNode2 = r._Ptr;
//pNote1到结点未尾的距离
while (pNode1 != null)
{
pNode1 = pNode1->Next;
++i1;
}
//pNote2到结点未尾的距离
while (pNode2 != null)
{
pNode2 = pNode2->Next;
++i2;
}
// - (i1-i2) 值越小，离结点未越近，例如 null 结点，就是 0。
return i2 - i1;
}
//-------------------------------如果是非线性表，下面的运算符重载也要重写
inline bool operator!=(const _DListNodeIterator& r) { return this->_Ptr != r._Ptr; }
inline bool operator==(const _DListNodeIterator& r) { return this->_Ptr == r._Ptr; }
inline bool operator>(const _DListNodeIterator& r) { return this->_Ptr > r._Ptr; }
inline bool operator<(const _DListNodeIterator& r) { return this->_Ptr < r._Ptr; }
};
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
/// 创建时间： 2024-07-03 最后一修改时间：2024-07-03
template<class T>
class _DListNodeReverseIterator
{
public:
using value_type = T;
private:
/// <summary>
/// 当前节点
/// </summary>
_DListNode<T>* _pCurrentNode;
/// <summary>
/// 当前链表
/// </summary>
_DList<T>* _pCurrentList;
public:
inline _DListNodeReverseIterator()
{
_pCurrentList = null;
_pCurrentNode = null;
}
inline _DListNodeReverseIterator(const _DList<T>* pCurrentList)
{
assert(pCurrentList != null);
_pCurrentList = (_DList<T>*)pCurrentList;
_pCurrentNode = null;
}
/// <summary>
/// 构造函数，传值迭代器管理的值
/// </summary>
/// <param name="pNode"></param>
inline _DListNodeReverseIterator(const _DListNode<T>* pCurrentNode, const _DList<T>* pCurrentList)
{
_pCurrentNode = (_DListNode<T>*)pCurrentNode;
_pCurrentList = (_DList<T>*)pCurrentList;
}
inline _DListNodeReverseIterator(const _DListNodeReverseIterator& it)
{
_pCurrentNode = it._pCurrentNode;
_pCurrentList = it._pCurrentList;
}
/// <summary>
/// 解引用，取值
/// </summary>
/// <typeparam name="T"></typeparam>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-03
inline T& operator * ()const { return _pCurrentNode->Data; }
/// <summary>
/// 前置加加
/// </summary>
/// <returns></returns>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-02
inline _DListNodeReverseIterator& operator++() { Move(1); return *this; }
/// <summary>
/// 前置减减
/// </summary>
/// <returns></returns>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-02
inline _DListNodeReverseIterator& operator--() { Move(-1); return *this; }
/// <summary>
/// 后置加加
/// </summary>
/// <param name=""></param>
/// <returns></returns>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-02
inline _DListNodeReverseIterator operator++(int) {
_DListNodeIterator sResult(*this);
Move(1);
return sResult;
}
/// <summary>
/// 后置减减
/// </summary>
/// <param name=""></param>
/// <returns></returns>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-02
inline _DListNodeReverseIterator operator--(int) {
_DListNodeIterator sResult(*this);
Move(-1);
return sResult;
}
/// <summary>
/// 向后移动为正，向前移动为负
/// </summary>
/// <param name="iDiff"></param>
/// 创建时间：2024-07-02 最后一次修改时间：2024-07-02
inline void Move(const int& iDiff)
{
assert(_pCurrentList != null);
if (iDiff == 0) return;
if (iDiff > 0) { //向后移动
int n = 0;
if (_pCurrentNode == null) { //不能向前移动
_pCurrentNode = _pCurrentList->Last();
n = 1; //已经向后移动了一位
if (n == iDiff) { return; }
}
while (true) {
_pCurrentNode = _pCurrentNode->Prev;
++n;
if (n == iDiff) { return; }
}
}
else {
if (_pCurrentNode == null) { //不能向后移动
return;
}
int n = 0;
while (true) {
_pCurrentNode = _pCurrentNode->Next;
--n;
if (n == iDiff) { return;}
}
}
throw "未重写代码？";
}
inline bool operator!=(const _DListNodeReverseIterator& r) { return this->_pCurrentNode != r._pCurrentNode; }
inline bool operator==(const _DListNodeReverseIterator& r) { return this->_pCurrentNode == r._pCurrentNode; }
inline bool operator>(const _DListNodeReverseIterator& r) { return this->_pCurrentNode > r._pCurrentNode; }
inline bool operator<(const _DListNodeReverseIterator& r) { return this->_pCurrentNode < r._pCurrentNode; }
};
/// <summary>
/// 双向链表, 数据 T 要求能够比较大小，否则编译会出错。
/// </summary>
/// <typeparam name="T"></typeparam>
template<class T>
class _DList : public _Object
{
public:
using value_type = T;
using iterator = _DListNodeIterator<T>;
static const size_t npos = -1; //不可能的索引
protected:
_DListNode<T>* _First; //第一个节点
_DListNode<T>* _Last; //最后一个节点
size_t _Count; //节点个数
size_t _MaxBuffer; //双链表最大可以存储的元素个数
_SortOrder _so; //排序顺序
protected:
/// <summary>
/// 初台化数据
/// </summary>
/// <returns></returns>
inline void InitData()
{
_Count = 0; _First = null; _Last = null; _MaxBuffer = 100000;
_so = _SortOrder::s_null;
}
public: //---------------------------------------------------------------------------属性
__declspec(property(get = GetSortOrder, put = SetSortOrder) ) _SortOrder SortOrder;
const _SortOrder& GetSortOrder() const { return _so; }
virtual void SetSortOrder(const _SortOrder so) { _so = so; }
__declspec(property(get = GetCount)) const int Count;
/// <summary>
/// 为了兼容标准库。
/// 例：T = vector, string, _DList....
/// size_t nSize = T.size();
/// auto itBegin = T.begin();
/// </summary>
/// <returns></returns>
/// 创建时间： 2024-07-30 最后一修改时间：2024-07-30
int size()const { return _Count; }
inline int GetCount() const { return _Count; }
public:
//------------------------------------------------------------构造与析构
/// <summary>
/// 默认构造函数
/// </summary>
/// <returns></returns>
inline _DList()
{
InitData();
}
inline _DList(const _DList& dl)
{
//_cout << _t("inline _DList<T>::_DList(const _DList& dl)\n");
InitData();
_DListNode<T>* dn = dl.First();
while (dn != null)
{
Add(dn->Data);
dn = dn->Next;
}
}
inline _DList(const std::vector<T>& v) {
InitData();
for (const T& t : v)
{
Add(t);
}
}
inline _DList(const T& item)
{
InitData();
Add(item);
}
/// <summary>
/// 列表初始化 dList<int> idl = {1,2,3,4};
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="tList"></param>
inline _DList(std::initializer_list<T> tList)
{
InitData();
for (T t : tList) { Add(t); }
}
/// <summary>
/// 析构函数
/// </summary>
inline virtual ~_DList()
{
//_cout << _t("inline _DList<T>::~_DList()\n");
ClearData();
}
//------------------------------------------------------------属性
/// <summary>
/// 双链表最大可以存储的元素个数
/// </summary>
int MaxBuffer()const { return _MaxBuffer; }
/// <summary>
///设定双链表最大可以存储的元素个数
/// </summary>
/// <param name="nCaptionty"></param>
inline void MaxBuffer(const size_t &nCaptionty) { _MaxBuffer = nCaptionty; }
inline size_t csharp_Count() const { return _Count; }
inline _DListNode<T>* First()const { return _First; }
inline _DListNode<T>* Last()const { return _Last; }
inline _DListNodeIterator<T> begin()const { return _DListNodeIterator<T>(_First,this); }
inline _DListNodeReverseIterator<T> rbegin()const { return _DListNodeReverseIterator<T>(_Last,this); }
/// <summary>
///
/// </summary>
/// <returns></returns>
inline _DListNodeIterator<T> end()const
{
//迭代器使用的语句
//for (_DListNodeIterator<int> f = dl.begin(); f != dl.end(); f++) { }
return _DListNodeIterator<T>(null,this);
}
/// <summary>
///
/// </summary>
/// <returns></returns>
inline _DListNodeReverseIterator<T> rend()const
{
//迭代器使用的语句
//for (_DListNodeIterator<int> f = dl.begin(); f != dl.end(); f++) { }
return _DListNodeReverseIterator<T>(null, this);
}
//-----------------------------------------------------------运算符重载
/// <summary>
/// 重载的下标操作符 []
/// </summary>
T& operator[](const size_t& nIndex) const { return IndexOfNode(nIndex)->Data; }
/// <summary>
/// 重载的下标操作符 =
/// </summary>
/// 创建时间： ????-??-?? 最后一次修改时间：2024-04-19
inline _DList<T>& operator = (const _DList<T>& other)
{
if (this != &other)
{
ClearData();
Add(other);
}
return *this;
}
/// <summary>
/// 类型转换
/// </summary>
inline operator _string() const{ return ToString(); }
/// <summary>
/// 类型转换
/// </summary>
inline operator _stdstr() const { return ToString().Data; }
//---------------------------------------------------------虚函数重写
/// <summary>
/// 是否存在 item
/// </summary>
inline virtual bool Contains(const T& item){ return BinarySearch(item) != -1; }
/// <summary>
/// 交换两个节点的数据
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="iIndex1"></param>
/// <param name="iIndex2"></param>
/// <returns></returns>
inline bool SwapNodeData(const int& iIndex1, const int& iIndex2)
{
_DListNode<T>* pNode1, * pNode2;
pNode1 = IndexOfNode(iIndex1);
pNode2 = IndexOfNode(iIndex2);
if (!(pNode1 != null && pNode2 != null))
{
return false;
}
T ptmp = pNode1->Data;
pNode1->Data = pNode2->Data;
pNode2->Data = ptmp;
return true;
}
/// <summary>
/// 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小
/// 或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序
/// 的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="sortord"></param>
/// 创建时间： ???-??-?? 最后一次修改时间：???-??-?? 已测试
inline virtual void Sort_Selection(const _SortOrder& sortord = _SortOrder::s_Minmax)
{
if (_Count == 0 || _Count == 1) return;
_DListNode<T>* min = _First, * tmp = _First->Next;
if (sortord == _SortOrder::s_Minmax) //从小到大
{
while (min->Next != null)
{
while (tmp != null)
{
if (tmp->Data < min->Data) //交换数据
{
T pt = tmp->Data;
tmp->Data = min->Data;
min->Data = pt;
}
tmp = tmp->Next;
}
min = min->Next;
tmp = min->Next;
}
}
else
{
while (min->Next != null)
{
while (tmp != null)
{
if (tmp->Data > min->Data)
{
T pt = tmp->Data;
tmp->Data = min->Data;
min->Data = pt;
}
tmp = tmp->Next;
}
min = min->Next;
tmp = min->Next;
}
}
this->_so = sortord; //已排序
}
/// <summary>
/// 返回索引的节点
/// </summary>
inline virtual _DListNode<T>* IndexOfNode(const size_t& nPos)const
{
if (nPos >= _Count) //错误索引:
{
return NULL;
}
size_t nindex = 0;
if (nPos > _Count / 2)
{
_DListNode<T>* pNode = _Last;
while (pNode != null)
{
if (nindex++ == _Count - nPos - 1) { return pNode; }
pNode = pNode->Prev;
}
}
else
{
_DListNode<T>* pNode = _First;
while (pNode != null)
{
if (nindex++ == nPos)
{
return pNode;
}
pNode = pNode->Next;
}
}
return null;
}
/// <summary>
/// 把索引为nIndex的节点移到最后
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="iIndex"></param>
/// <returns></returns>
inline virtual bool MoveLast(const size_t& nIndex)
{
_DListNode<T>* pNode = IndexOfNode(nIndex);
if (pNode != null)
{
if (pNode == _Last)
return true;
if (pNode == _First) //此时最少两个节点
{
_First = _First->Next;
_First->Prev = null;
_Last->Next = pNode;
pNode->Prev = _Last;
_Last = pNode;
}
else
{
pNode->Prev->Next = pNode->Next;
pNode->Next->Prev = pNode->Prev;
_Last->Next = pNode;
pNode->Prev = _Last;
_Last = pNode;
}
return true;
}
return false;
}
/// <summary>
/// 把节点移到最后
/// </summary>
/// 创建时间： 2022-02-18 最后一次修改时间：2022-02-18
inline virtual bool MoveLast(_DListNode<T>* dnCurrent)
{
if (dnCurrent == null) return false;
this->_so = _SortOrder::s_null;
if (_Count == 0)
{
return false;
}
else if (_Count == 1)
{
return true;
}
else if (_Count == 2)
{
if (dnCurrent == _First) //交换_First 与 _Last 数据
{
T tmp = _First->Data;
_First->Data = _Last->Data;
_Last->Data = tmp;
}
return true;
}
else
{
if (dnCurrent == _First)
{
_First = _First->Next;
_First->Prev = null;
_Last->Next = dnCurrent;
dnCurrent->Next = null;
dnCurrent->Prev = _Last;
_Last = dnCurrent;
}
else if (dnCurrent != _Last)
{
dnCurrent->Prev->Next = dnCurrent->Next;
dnCurrent->Next->Prev = dnCurrent->Prev;
_Last->Next = dnCurrent;
dnCurrent->Next = null;
dnCurrent->Prev = _Last;
_Last = dnCurrent;
}
return true;
}
}
/// <summary>
/// 把索引为nIndex的节点移到最前
/// </summary>
/// <param name="iIndex"></param>
inline virtual bool MoveFirst(const size_t& nIndex)
{
_DListNode<T>* pNode = IndexOfNode(nIndex);
if (pNode != null)
{
if (pNode == _First)
return true;
if (pNode == _Last) //此时最少两个节点
{
_Last->Prev->Next = null;
_Last = _Last->Prev;
pNode->Prev = null;
pNode->Next = _First;
_First->Prev = pNode;
_First = pNode;
}
else
{
pNode->Prev->Next = pNode->Next;
pNode->Next->Prev = pNode->Prev;
pNode->Next = _First;
_First->Prev = pNode;
pNode->Prev = null;
_First = pNode;
}
return true;
}
return false;
}
/// <summary>
/// 将指定集合的元素添加到末尾
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="item"></param>
/// <returns></returns>
inline virtual bool Add(const T& item)
{
if (_Count == 0)
{
//_First = new _DListNode<T>(item);
_First = _Memory::New< _DListNode<T> >(1);
_First->Data = item;
_First->Next = null;
_First->Prev = null;
_Last = _First;
}
else
{
_DListNode<T>* pNew = _Memory::New< _DListNode<T> >(1);
pNew->Data = item;
pNew->Next = null;
pNew->Prev = _Last;
_Last->Next = pNew;
_Last = pNew;
}
++_Count;
this->_so = _SortOrder::s_null; //要重新排序
return true;
}
/// <summary>
/// 添加一个链表
/// </summary>
inline void Add(const _DList<T>& dList)
{
assert(&dList != null);
_DListNode<T>* pNode = dList._First;
while (pNode != null)
{
Add(pNode->Data);
pNode = pNode->Next;
}
}
protected:
/// <summary>
/// 在结点pListItem前面插入一个结点,成功，返回新的结点，否则返回null
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="pListItem"></param>
/// <param name="rData"></param>
/// <returns></returns>
inline virtual _DListNode<T>* InserNodeFront(_DListNode<T>* pListItem, const T& rData)
{
assert(pListItem != null);
_DListNode<T>* pNode = _Memory::New<_DListNode<T>>(1);
pNode->Data = rData;
//pNode
pNode->Next = pListItem;
pNode->Prev = pListItem->Prev;
//--pListItem->Prev
if (pListItem->Prev != null)
{
pListItem->Prev->Next = pNode;
}
else
{
_First = pNode;
}
//pListItem
pListItem->Prev = pNode;
++_Count;
return pNode;
}
/// <summary>
/// 在结点pListItem后面插入一个结点,成功，返回新的结点，否则返回０；
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="pListItem"></param>
/// <param name="rData"></param>
/// <returns></returns>
inline virtual _DListNode<T>* InserNodeBack(_DListNode<T>* pListItem, const T& rData)
{
if (pListItem == null) return null;
_DListNode<T>* pNode = _Memory::New<_DListNode<T>>(1);
pNode->Data = rData;
//pNode
pNode->Prev = pListItem;
pNode->Next = pListItem->Next;
//pListItem->Next
if (pListItem->Next != null)
{
pListItem->Next->Prev = pNode;
}
else
{
_Last = pNode;
}
//--pListItem
pListItem->Next = pNode;
++_Count;
return pNode;
}
//------------------------------------------------------------操作
public:
/// <summary>
/// 如果已排好序，它会按二分法查找，否则它会普通查找。
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
/// 创建时间： ????-??-?? 最后一次修改时间：????_??_?? 已测试
inline int BinarySearch(const T& item)const {
switch (this->_so)
{
case _SortOrder::s_Maxmin:
{
if (_Count == 0)
{
return -1;
}
if (_Count == 1)
{
//return (_First.Data as IComparable).CompareTo(item) == 0 ? 0 : -1; //C#
return _First->Data == item ? 0 : -1;
}
if (_Count == 2)
{
//if ((_First.Data as IComparable).CompareTo(item) == 0) return 0;
//if ((_First.Next.Data as IComparable).CompareTo(item) == 0) return 1;
if (_First->Data == item) return 0;
if (_First->Next->Data == item) return 1;
return -1;
}
int nPos = (int)_Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)_Count - 1; //右边远素
_DListNode<T>* pNode;
while (nRight >= 0 && nLeft >= 0)
{
pNode = IndexOfNode(nPos);
//int iCom = (item as IComparable).CompareTo(ld.Data);
if (item > pNode->Data)
{
if (nRight == nLeft || nPos == nLeft)
{
return -1;
}
nRight = nPos - 1;
}
else if (item < pNode->Data)
{
if (nRight == nLeft || nPos == nRight)
{
return -1;
}
nLeft = nPos + 1;
}
else
{
return nPos;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case _SortOrder::s_Minmax:
{
if (_Count == 0)
{
return -1;
}
if (_Count == 1)
{
//return (_First.Data as IComparable).CompareTo(item) == 0 ? 0 : -1;
return _First->Data == item ? 0 : -1;
}
if (_Count == 2)
{
//if ((_First.Data as IComparable).CompareTo(item) == 0) return 0;
//if ((_First.Next.Data as IComparable).CompareTo(item) == 0) return 1;
if (_First->Data == item) return 0;
if (_First->Next->Data == item) return 1;
return -1;
}
int nPos = (int)_Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)_Count - 1; //右边远素
_DListNode<T>* pNode = null;
while (nRight >= 0 && nLeft >= 0)
{
pNode = IndexOfNode(nPos);
//int iCom = (item as IComparable).CompareTo(ld.Data);
if (item < pNode->Data)
{
if (nRight == nLeft || nPos == nLeft)
{
return -1;
}
nRight = nPos - 1;
}
else if (item > pNode->Data)
{
if (nRight == nLeft || nPos == nRight)
{
return -1;
}
nLeft = nPos + 1;
}
else
{
return nPos;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case _SortOrder::s_null:
{
_DListNode<T>* pNode = _First;
int iCount = 0;
while (pNode != null)
{
if (pNode->Data == item)
{
return iCount;
}
pNode = pNode->Next;
++iCount;
}
break;
}
default:
{
return -1;
}
}
return -1;
}
/// <summary>
/// 清除节点，并释放内存
/// </summary>
/// <typeparam name="T"></typeparam>
/// 创建时间： ????-??-?? 最后一次修改时间：2022-12-24 (已测试）
inline void ClearData() override { ClearMemory(); }
/// <summary>
/// 清除节点，并释放内存
/// </summary>
inline void ClearMemory() override
{
_Count = 0;
_DListNode<T>* dn = _First;
while (dn != null)
{
if (dn->Prev != null)
_Memory::Delete< _DListNode<T> >(dn->Prev, 1);
dn = dn->Next;
}
if (_Last != null)
_Memory::Delete< _DListNode<T> >(_Last, 1);
_First = null;
_Last = null;
this->_so = _SortOrder::s_null;
}
/// <summary>
/// 复制一个链表，清除原来链表的数据
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="ld"></param>
inline void CopyFrom(const _DList<T>& ld)
{
if (this != &ld)
{
ClearData();
_DListNode<T>* pNode = ld._First;
while (pNode != null)
{
Add(pNode->Data);
pNode = pNode->Next;
}
}
}
/// <summary>
/// 移除指定索引处的元素
/// </summary>
/// <typeparam name="T">类型</typeparam>
/// <param name="iIndex">要移除的元素的从零开始的索引。</param>
/// <returns>成功返回true,否则返回false</returns>
/// 创建时间：????-??-?? 最后一次修改时间：2023-04-08
inline bool RemoveAt(const size_t& nIndex)
{
if (nIndex >= _Count) return false;
_DListNode<T>* pNode = _First;
size_t nCount = 0;
while (pNode != null)
{
if (nCount == nIndex)
{
if (pNode == _First)
{
if (_First->Next == null) //只有一个
{
ClearData();
return true;
}
else
{
_First = _First->Next;
_First->Prev = null;
--_Count;
_Memory::Delete< _DListNode<T> >(pNode, 1);
return true;
}
}
else if (pNode == _Last)
{
if (_Last->Prev == null)
{
ClearData();
return true;
}
else
{
_Last = _Last->Prev;
_Last->Next = null;
--_Count;
_Memory::Delete< _DListNode<T>>(pNode, 1);
return true;
}
}
else
{
pNode->Prev->Next = pNode->Next;
pNode->Next->Prev = pNode->Prev;
--_Count;
_Memory::Delete< _DListNode<T>>(pNode, 1);
return true;
}
}
pNode = pNode->Next;
++nCount;
}
return false;
}
/// <summary>
/// 查找一项数据
/// </summary>
inline _DListNode<T>* FindNodeItem(const T& item)const
{
switch (this->_so)
{
case _SortOrder::s_Maxmin:
{
if (_Count == 0)
{
return null;
}
if (_Count == 1)
{
//return (_First.Data as IComparable).CompareTo(item) == 0 ? _First : null;
return _First->Data == item ? _First : null;
}
if (_Count == 2)
{
//if ((_First.Data as IComparable).CompareTo(item) == 0) return _First;
//if ((_First.Next.Data as IComparable).CompareTo(item) == 0) return _First.Next;
if (_First->Data == item) return _First;
if (_First->Next->Data == item) return _First->Next;
return null;
}
int nPos = (int)(_Count / 2); //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)(_Count - 1); //右边远素
_DListNode<T>* pNode = null;
while (nRight >= 0 && nLeft >= 0)
{
pNode = IndexOfNode(nPos);
//int iCom = (item as IComparable).CompareTo(ld.Data);
if (item > pNode->Data)
{
if (nRight == nLeft || nPos == nLeft)
{
return null;
}
nRight = nPos - 1;
}
else if (item < pNode->Data)
{
if (nRight == nLeft || nPos == nRight)
{
return null;
}
nLeft = nPos + 1;
}
else
{
return pNode;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case _SortOrder::s_Minmax:
{
if (_Count == 0)
{
return null;
}
if (_Count == 1)
{
//return (_First.Data as IComparable).CompareTo(item) == 0 ? _First : null;
return _First->Data == item ? _First : null;
}
if (_Count == 2)
{
//if ((_First.Data as IComparable).CompareTo(item) == 0) return _First;
//if ((_First.Next.Data as IComparable).CompareTo(item) == 0) return _First.Next;
if (_First->Data == item) return _First;
if (_First->Next->Data == item) return _First->Next;
return null;
}
int nPos = (int)(_Count / 2); //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)(_Count - 1); //右边远素
_DListNode<T>* pNode = null;
while (nRight >= 0 && nLeft >= 0)
{
pNode = IndexOfNode(nPos);
//int iCom = (item as IComparable).CompareTo(ld.Data);
if (item < pNode->Data)
{
if (nRight == nLeft || nPos == nLeft)
{
return null;
}
nRight = nPos - 1;
}
else if (item > pNode->Data)
{
if (nRight == nLeft || nPos == nRight)
{
return null;
}
nLeft = nPos + 1;
}
else
{
return pNode;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case _SortOrder::s_null:
{
_DListNode<T>* pNode = _First;
while (pNode != null)
{
//总结:Equals比较的永远是变量的内容是否相同，而= =比较的则是引用地址是否相同(前提:此种类型内部没有对Equals 或= = 进行重写操作，
//否则输出可能会有不同)。string 类型是个特例，因为他的内部对这两个都进行了重写。
if (item == pNode->Data)
{
return pNode;
}
/*
if (pNode.Data.Equals(item))
{
return pNode;
}
*/
pNode = pNode->Next;
}
break;
}
default:
{
return null;
}
}
return null;
}
/// <summary>
/// 在链接中查找节点，返回节点的索引
/// </summary>
/// <param name="pFind"></param>
/// <returns></returns>
/// 创建时间：2024-07-03 最后一次修改时间：2024-07-03
inline int FindNodeIndex(const _DListNode<T>* pFind)const
{
if (pFind != null){
_DListNode<T>* pNode = _First;
int nIndex = 0;
while (pNode != null){
if (pNode == pFind)
return nIndex;
pNode = pNode->Next;
++nIndex;
}
}
return -1;
}
/// <summary>
/// 删除链表中的数据
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="pData"></param>
/// <returns></returns>
inline bool RemoveItem(const T& pData)
{
if (this->_so == _SortOrder::s_null)
{
_DListNode<T>* pNode = _First;
while (pNode != null)
{
if (pNode->Data == pData) //找到一项
{
if (pNode == _First) //删除的是第一个节点
{
if (_First->Next != null)
{
_First->Next->Prev = null;
_First = _First->Next;
}
else
{
_First = null;
_Last = null;
}
}
else if (pNode == _Last) //删除的是最后一个节点
{
if (_Last->Prev != null)
{
_Last->Prev->Next = null;
_Last = _Last->Prev;
}
else
{
_Last = null;
_Last = null;
}
}
else //删除的是中间的一个节点
{
pNode->Next->Prev = pNode->Prev;
pNode->Prev->Next = pNode->Next;
}
--_Count;
return true;
}
pNode = pNode->Next;
}
return false;
}
else
{
return RemoveAt(BinarySearch(pData));
}
}
/// <summary>
/// 删除最后一个节点
/// </summary>
/// 创建时间：2020-09-12 最后一次修改时间： 2023-01-18
inline bool DeleteLast()
{
auto pDelete = Last();
if (_Count <= 0)
{
return false;
}
else if (_Count == 1)
{
_First = null;
_Last = null;
_Count = 0;
}
else if (_Count == 2)
{
_Last = _First;
_Last->Prev = null;
_Last->Next = null;
_First->Next = null;
_First->Prev = null;
--_Count;
}
else
{
_Last->Prev->Next = null;
_Last = _Last->Prev;
--_Count;
}
_Memory::Delete<_DListNode<T>>(pDelete, 1);
return true;
}
/// <summary>
/// 添加一个元素，并把它放在首位，其它元素后移,如果后面的元素删除，总无素个数不变，如果元素个数为零，则添加一个无素。
/// </summary>
/// <param name="Item"></param>
/// <param name="bRemoveLast"></param>
/// 创建时间： 2022-04-19 最后一次修改时间：2022-04-19
inline void HistoryAdd(const T& Item, bool bRemoveLast)
{
if (_Count == 0) {
Add(Item);
}
else if (_Count == 1) {
if (bRemoveLast) {
_First->Data = Item;
}
else {
//把无素放在最前
_DListNode<T>* dnNew = _Memory::New<_DListNode<T>>(1);
dnNew->Data = Item;
_First->Prev = dnNew;
dnNew->Next = _First;
_First = dnNew;
++_Count;
}
}
else {
if (bRemoveLast) {
_DListNode<T>* dnDelete = _Last;
//删除最后一个元素
_Last = _Last->Prev;
_Last->Next = null;
_DListNode<T>* dnNew = _Memory::New<_DListNode<T>>(1);
dnNew->Data = Item;
_First->Prev = dnNew;
dnNew->Next = _First;
dnNew->Prev = null;
_First = dnNew;
_Memory::Delete< _DListNode<T>>(dnDelete, 1);
}
else {
//把无素放在最前
_DListNode<T>* dnNew = _Memory::New<_DListNode<T>>(1);
dnNew->Data = Item;
_First->Prev = dnNew;
dnNew->Next = _First;
dnNew->Prev = null;
_First = dnNew;
++_Count;
}
}
}
/// <summary>
/// 出栈(先进后出）,删除最后一个元素，
/// </summary>
/// 创建时间： 2022-04-19 最后一次修改时间：2023-04-06
inline T StackPop()
{
assert(_Count > 0);
T tResult = _Last->Data;
this->RemoveAt(_Count - 1);
return tResult;
}
//----------------------------------------------------------------------------------------------------Python List方法
/// <summary>
/// 将元素tItem添加到列表末尾。
/// </summary>
/// 创建时间： 2023-04-08 最后一次修改时间：2023-04-08
inline void Python_append(const T& tItem)
{
Add(tItem);
}
/// <summary>
/// 在位置nIndex后面插入一个元素tItem
/// </summary>
inline void Python_insert(const size_t &nIndex, const T& tItem)
{
InserNodeBack(IndexOfNode(nIndex), tItem);
}
/// <summary>
/// 在最前面插入一项
/// </summary>
/// <param name="tItem"></param>
/// 创建时间： 2024-04-16 最后一次修改时间：2024-04-16
inline void Inseart_front(const T& tItem)
{
_DListNode<T>* pNode = _Memory::New<_DListNode<T>>(1);
pNode->Data = tItem;
if (_First != null)
{
_First->Prev = pNode;
pNode->Next = _First;
pNode->Prev = null;
_First = pNode;
}
else
{
pNode->Next = null;
pNode->Prev = null;
_First = pNode;
_Last = pNode;
}
++_Count;
}
/// <summary>
/// 删除索引位置为nIndex的元素，并返回删除的元素值的拷贝，如果索引值nIndex = -1，则默认删除为最后一个元素。
/// </summary>
/// <param name="nIndex"></param>
/// <returns></returns>
/// 创建时间： 2023-04-08 最后一次修改时间：2023-04-09
inline T Python_pop(const size_t nIndex = npos)
{
if (nIndex == npos)
{
return StackPop();
}
else
{
auto dn = this->IndexOfNode(nIndex);
T tmp = T();
if (dn != null)
{
tmp = dn->Data;
DeleteNode(dn);
}
return tmp;
}
}
/// <summary>
/// 删除值为tItem的一项。
/// 注意，方法remove()只删除第一个指定的值。如果要删除的值可能在列表中出现多次，
/// 就需要使用循环来确保每个值都删除。
/// </summary>
inline bool Python_remove(const T& tItem)
{
int n = _Count;
DeleteNode(FindNodeItem(tItem));
return n == _Count;
}
protected:
/// <summary>
/// 删除链表中的节点
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="pListItem"></param>
/// <returns></returns>
//inline bool DeleteNode(const _DListNode<T>* pNodeDelete)
//{
// if (_Count == 0 || pNodeDelete == null)
// {
// return false;
// }
// _DListNode<T>* pNode = _First.Next;
// while (pNode != null)
// {
// if (pNode == pNodeDelete) //找到了
// {
// //pListItem->Prev
// if (pNodeDelete->Prev != null)
// {
// pNodeDelete->Prev->Next = pNodeDelete->Next;
// }
// else //删除的是第一个节点
// {
// _First = pNodeDelete.Next;
// }
// //pListItem->Next
// if (pNodeDelete->Next != null)
// {
// pNodeDelete->Next->Prev = pNodeDelete->Prev;
// }
// else //删除的是最后一个节点
// {
// _Last = pNodeDelete->Prev;
// }
// break;
// }
// pNode = pNode->Next;
// }
// if (pNode != null)
// {
// --_Count;
// _Memory::Delete< _DListNode<T> >(pNode,1); //C#不用清除内存
// return true;
// }
// return false;
//}
/// <summary>
/// 删除链表中的某一节点，注意，这个节点一定要是在链表中的。
/// </summary>
/// 创建时间： 2023-04-09 最后一次修改时间：2023-04-09
inline void DeleteNode(_DListNode<T>* pNodeDelete)
{
if (_Count == 0 || pNodeDelete == null) return;
if (_Count == 1)
{
ClearMemory();
}
else
{
if (pNodeDelete == _First) //删除的是第一个节点
{
_First = _First->Next;
_First->Prev = null;
}
else if (pNodeDelete == _Last)
{
_Last = _Last->Prev;
_Last->Next = null;
}
else
{
pNodeDelete->Prev->Next = pNodeDelete->Next;
pNodeDelete->Next->Prev = pNodeDelete->Prev;
}
--_Count;
_Memory::Delete< _DListNode<T> >(pNodeDelete, 1);
}
}
public:
//---------------------------------------------------------- C++
inline void Push_back(const T& TypeObject) { Add(TypeObject); }
public: //------------------------------------------------------------------重写
/// <summary>
/// 转换为字符串
/// </summary>
/// <returns></returns>
/// 创建时间： 2023-05-16 最后一次修改时间：2024-07-23
inline virtual _string ToSplitString(const _string& sSplitString) const override
{
//不可以这样： const _DList<_Object>* dp = (_DList<_Object> *)pList;
//就算 T 类型数据是从 _Object中继承也不可以。
_string sResult;
sResult.Add(_t("{"));
_string sp = sSplitString.Length == 0 ? _string(_t(",")) : sSplitString;
if(_Count > 0){
//是否继承处_Object
if (std::is_base_of<_Object, T>::value)
{
_Object* po;
if (_Count == 1)
{
po = (_Object*)(&_First->Data);
sResult.Add((_string)(*po));
}
_DListNode<T>* dn = this->_First;
while (dn != _Last)
{
po = (_Object*)(&dn->Data);
sResult.Add((_string)(*po));
sResult.Add(sp);
dn = dn->Next;
}
po = (_Object*)(&_Last->Data);
sResult.Add((_string)(*po));
}
else
{
if (typeid(T) == typeid(int))
{
_DListNode<T>* dn = this->_First;
while (dn != _Last)
{
int* pInt = (int*)&(dn->Data);
sResult.Add(_string::Java_valueOf(*pInt));
sResult.Add(sp);
dn = dn->Next;
}
if (this->Count > 0)
sResult.Add(_string::Java_valueOf(*((int*)(&(_Last->Data)))));
}
else if(typeid(T) == typeid(size_t))
{
_DListNode<T>* dn = this->_First;
while (dn != _Last)
{
size_t* pInt = (size_t*)&(dn->Data);
sResult.Add(_string::Java_valueOf(*pInt));
sResult.Add(sp);
dn = dn->Next;
}
if (this->Count > 0)
sResult.Add(_string::Java_valueOf(*((size_t*)(&(_Last->Data)))));
}
else if (typeid(T) == typeid(double))
{
if (_Count == 0) return sResult;
double* pd;
if (_Count == 1)
{
pd = (double*)(&(_First->Data));
sResult.Add(_Convert::DoubleToString(*pd));
}
_DListNode<T>* dn = this->_First;
while (dn != _Last)
{
pd = (double*)&(dn->Data);
sResult.Add(_Convert::DoubleToString(*pd));
sResult.Add(sp);
dn = dn->Next;
}
pd = (double*)&(_Last->Data);
sResult.Add(_Convert::DoubleToString(*pd));
}
else if (typeid(T) == typeid(_string))
{
_string* ps;
_DListNode<T>* dn = this->_First;
while (dn != _Last)
{
ps = (_string*)(&dn->Data);
sResult.Add(_t("\""));
sResult.Add(*ps);
sResult.Add(_t("\""));
sResult.Add(sp);
dn = dn->Next;
}
if (_Count > 0)
{
ps = (_string*)(&_Last->Data);
sResult.Add(_t("\""));
sResult.Add(*ps);
sResult.Add(_t("\""));
}
}
else if (typeid(T) == typeid(_StrA))
{
_StrA* ps;
if (_Count <= 0)
{
}
else if (_Count == 1)
{
ps = (_StrA*)(&_First->Data);
sResult.Add(_t("\""));
sResult.Add(*ps);
sResult.Add(_t("\""));
}
else
{
_DListNode<T>* dn = this->_First;
while (dn != _Last)
{
ps = (_StrA*)(&dn->Data);
sResult.Add(_t("\""));
sResult.Add(*ps);
sResult.Add(_t("\""));
sResult.Add(_t(','));
dn = dn->Next;
}
ps = (_StrA*)(&_Last->Data);
sResult.Add(_t("\""));
sResult.Add(*ps);
sResult.Add(_t("\""));
}
}
else //所有继承自 _Object 类的数据类型都可以
{
sResult.Add(_t("_LDList::ToSplitString重写,数据类型为："));
sResult.Add(_string(typeid(T).name()));
}
}
}
sResult.Add(_t("}\n"));
return sResult;
}
inline _string ToString()const
{
return ToSplitString(_t(""));
}
}; //--------------------------------------------------------------------------DList
//-----------------------------------------------------------------------SortedDList
/// <summary>
/// C#语句：public class SortList<T> : _DList<T>
/// </summary>
/// <typeparam name="T"></typeparam>
template<class T>
class SortedDList : public _DList<T>
{
};
//----------------------------------------------------------------------StringList
template<class T>
class _StrList : public _DList<T>
{
public:
//------------------------------------------------------------------构造与析构
_StrList() : _DList<T>() {};
_StrList(const _StrList<T>& sl) : _DList<T>(sl) {};
explicit _StrList(const _char* pStr, const _char* pSplit, bool bIgnoreEmptyString = false)
{
this->InitData();
SplitForSeparator(pStr, pSplit, bIgnoreEmptyString);
}
/// <summary>
/// 要加上 explicit阻止自动转换， 否则执行语名会自动调用这个构造函数 _StrList ls = { L"AA",L"BB"};
/// </summary>
/// <param name="sText"></param>
/// <param name="sSplit"></param>
/// <param name="bIgnoreEmptyString"></param>
explicit _StrList(const T& sText, const T& sSplit, bool bIgnoreEmptyString = false)
{
//assert(sText != null && sSplit != null);
//SplitForSeparator(sText.Data, sSplit.Data, bIgnoreEmptyString);
if (sText.Length == 0) { return; }
if (sSplit.Length == 0) { Add(sText); return; }
int iStart = 0;
int iIndex = sText.IndexOf(sSplit, iStart);
if (iIndex == -1)
{
Add(sText);
return;
}
while (iIndex != -1 && iStart + 1 <= sText.Length)
{
if (iIndex != iStart)
Add(sText.SubStr(iStart, iIndex - iStart));
else
{
if (!bIgnoreEmptyString) Add(T());
}
iStart = iIndex + sSplit.Length;
iIndex = sText.IndexOf(sSplit, iStart);
if (iIndex == -1 && sText.Length != iStart)
Add(sText.SubStr(iStart, sText.Length - iStart)); //拷贝最后一个
}
}
_StrList(std::initializer_list<T> aList)
{
for (T s : aList)
{
Add(s);
}
}
public:
//------------------------------------------------------------------操作
void writeToFile(const T& sFullPathName)
{
}
bool readToFile(const T& sFullPathName)
{
return false;
}
bool readToUnicodeFile(const T& sFileName, const T& sSplit)
{
return false;
}
/// <summary>
/// 获取所有字符串的总共长度
/// </summary>
/// <returns></returns>
/// 创建时间： 2022-11-05 最后一次修改时间： 2022-11-05
int GetStringLength() const
{
int iSum = 0;
auto dn = this->_First;
while (dn != null) {
iSum += (int)dn->Data.Length;
dn = dn->Next;
}
return iSum;
}
T connectForSeparator(const T& sConnector)const
{
if (this->_Count == 0) return _t("");
if (this->_Count == 1) return this->_First->Data;
T tmp(_t(""), GetStringLength() + sConnector.Length * this->_Count + 100);
_DListNode<T>* ldNode = this->_First;
while (ldNode != this->_Last)
{
tmp += ldNode->Data;
tmp += sConnector;
ldNode = ldNode->Next;
}
tmp += this->_Last->Data; //加入最后一项
return tmp;
}
T connectForSeparator(const _char& cConnector) const
{
return connectForSeparator(&cConnector);
}
/// <summary>
/// 返回分隔后的字符串列表
/// </summary>
/// <param name="pStr">原文本</param>
/// <param name="pSplit">分隔字符串</param>
/// <param name="bIgnoreEmptyString">是否忽略空字符串</param>
/// <returns>返回一个字符串列表</returns>
/// 创建时间： 2022-10-04 最后一修改时间：2022-10-05 已测试
_StrList<T>& SplitForSeparator(const _char* pStr, const _char* pSplit, bool bIgnoreEmptyString)
{
if (pStr == null || pSplit == null)
{
_cout << "在中_StrList::SplitForSeparator中" << L"pStr == null || pSplit == null" << "\n";
throw "pStr == null || pSplit == null";
}
this->ClearData();
if (pStr[0] == 0 || pSplit[0] == 0)
{
Add(_t(""), 0, 0);
return *this;
}
int i = 0;
int j = 0;
int nStart = 0, nEnd = 0;
while (pStr[i] != 0) {
// _cout << _t("pStr[i] = ") << pStr[i] << _t("\n"); //此句出错，无任何提示
bool bFind = true;
j = 0;
while (pSplit[j] != 0) {
if (pStr[i + j] != pSplit[j]) {
bFind = false;
break;
}
++j;
}
if (bFind) {
nEnd = i - 1; //此处如果 nEnd 是 int ，则 nEnd = i - 1 => nEnd = 18446744073709551615 => 溢出错误
if (bIgnoreEmptyString) {
if (nStart <= nEnd) {
Add(pStr, nStart, nEnd); //这里应nStart <= nEnd，而不是 nStart < nEnd，因为当 nStart = nEnd 还是有一个字符的
}
}
else {
Add(pStr, nStart, nEnd);
}
nStart = i + j;
i = nStart - 1;
}
++i;
}
//拷贝右边最后一项
if (bIgnoreEmptyString) {
if (nStart <= i - 1) {
Add(pStr, nStart, (int)i - 1);
}
}
else {
Add(pStr, nStart, (int)i - 1);
}
return *this;
}
//int SplitForSeparator(const T& sText, const _char& cSplit);
int IndexOf(const T& s)
{
int nIndex = 0;
auto dn = this->_First;
while (dn)
{
if (dn->Data == s) { return nIndex; }
++nIndex;
dn = dn->Next;
}
return -1;
}
int GetMaxSpaceLength(int nTabCount = 9, int nChineseCharactersCount = 3)const
{
int nMax = 0;
auto dn = this->_First;
while (dn)
{
int n = gs.s_length_space(dn->Data.Data, nTabCount, nChineseCharactersCount);
if (n > nMax) nMax = n;
dn = dn->Next;
}
return nMax;
}
/// <summary>
/// 用tab键使每行等长
/// </summary>
/// <param name="nTabCount"></param>
/// <returns></returns>
/// 创建时间： 2022-10-30 最后一次修改时间： 2022-10-30
T equilongTabLine(int nTabCount = 9)
{
this->RemoveHeadTab();
int iMax = GetMaxSpaceLength(nTabCount);
for (T& s : *this) {
int nSapceLength = gs.s_length_space(s.Data);
int n = (iMax - nSapceLength) / 9;
if (iMax - nSapceLength - n * 9 >= 5)
++n;
else
--n;
for (int j = 0; j < n; j++)
{
s.Add(_t("\t"));
}
}
return connectForSeparator(_t('\n')) + _t('\n');
}
/// <summary>
/// 计算所有行，如果每行都有开始处都有 \t ，则每行除去 \t , 除去个数以最少 \t 行为准。
/// 例：
/// \t\t abc
/// \t bcd
/// \t\t\t dd
/// 运行函数后变成
/// \t abc
/// bcd
/// \t\t dd
/// </summary>
/// 创建时间： 2022-11-05 最后一次修改时间： 2022-11-05
void RemoveHeadTab()
{
int iMin = 100000000;
for (T& s : *this) {
if (s.Length > 0)
{
int iCount = gs.s_headTabCount(s.Data);
if (iCount < iMin) { iMin = iCount; }
//log::d("iCount=" + iCount.ToString(), s);
}
}
//log::d("iMin=" + iMin.ToString());
if (iMin > 0)
{
for (T& s : *this) {
s = s.SubStr(iMin, s.Length - iMin);
}
}
}
//-----------------------------------------------------------------------虚函数
virtual bool Add(const T& item) override
{
//_cout << item << "\n";
return _DList<T>::Add(item);
}
void Add(const _StrList<T>& ls) //覆盖 父类重载函数 virtual bool Add(const T& item);
{
_DListNode<T>* pNode = ls._First;
while (pNode != null)
{
Add(pNode->Data);
pNode = pNode->Next;
}
}
/// <summary>
/// 添加拷贝nStartPos和nEndPos之间的字符，包括nStartPos和nEndPos。
/// </summary>
/// <param name="str"></param>
/// <param name="nStartPos"></param>
/// <param name="nEndPos"></param>
/// <returns></returns>
/// 创建时间： ????-??-?? 最后一次修改时间：????-??-?? 已测试（2024-08-16 ）
bool Add(const T& str, int nStartPos, int nEndPos)
{
if (str.Length == 0 || nEndPos - nStartPos < 0)
{
Add(T());
}
else {
int nLength = nEndPos - nStartPos + 1;
/*
_Mem<_char> m(nLength + 1);
for (int i = 0; i < nLength; ++i)
{
m.Data[i] = pStr[nStartPos + i];
}
m.Data[nLength] = 0;
*/
Add(str.SubStr(nStartPos, nLength));
}
return false;
}
_string ToSplitString(const _string& sSplitString) const override
{
/*
* auto dn = this->_First;
T sResult;
while (dn != this->_Last)
{
sResult.std_append(dn->Data);
sResult.std_append(sConnector);
dn = dn->Next;
}
if (this->_Last != null)
{
sResult.std_append(dn->Data);
}
char c = '\n';
sResult.std_append(c );
return sResult;
*/
return _DList<T>::ToSplitString(sSplitString);
}
};
/// <summary>
/// 不重复的字符串列表
/// </summary>
/// <typeparam name="T"></typeparam>
/// 创建时间： 2023-05-11 最后一次修改时间：2023-05-11
template<class T>
class _UStrList : public _StrList<T>
{
public:
/// <summary>
/// 加入一个串，如果这个串存在，则把这项移到最后。
/// </summary>
/// <param name="item"></param>
/// 创建时间： ????-??-?? 最后一次修改时间：2023-05-11 (已测试）
bool Add(const T& item)override
{
bool bFind = false;
_DListNode<T>* dnTemp = this->_First;
while (dnTemp != null)
{
if (dnTemp->Data == item)
{
this->MoveLast(dnTemp);
return false;
}
dnTemp = dnTemp->Next;
}
_StrList<T>::Add(item);
return true;
}
};
/// <summary>
/// 值都是唯一的字符串列表， Case Insensitive(不区分大小写)
/// </summary>
template<class T>
class _UStrListCI : public _StrList<T>
{
public:
/// <summary>
/// 加入一个串，如果这个串存在，则把这项移到最后。
/// </summary>
/// <param name="item"></param>
/// 创建时间： ????-??-?? 最后一次修改时间：2022-02-18
bool Add(const T& item)override
{
bool bFind = false;
_DListNode<T>* dnTemp = this->_First;
while (dnTemp != null)
{
if (dnTemp->Data.csharp_ToLower() == item.csharp_ToLower())
{
this->MoveLast(dnTemp);
return false;
}
dnTemp = dnTemp->Next;
}
_StrList<T>::Add(item);
return true;
}
/*
/// <summary>
/// 返回前面一个值
/// </summary>
/// <param name="tCurrValue"></param>
/// <returns></returns>
T& GetForward(T& sCurr)
{
int iIndex = BinarySearch(sCurr);
if (iIndex != -1)
{
if (iIndex + 1 < _Count)
return this[iIndex + 1];
}
return null;
}
/// <summary>
/// 返回后面的一个值
/// </summary>
/// <param name="sCurr"></param>
/// <returns></returns>
T& GetBack(T& sCurr)
{
int iIndex = BinarySearch(sCurr);
if (iIndex != -1)
{
if (iIndex - 1 < _Count && iIndex - 1 >= 0)
return this[iIndex - 1];
}
return null;
}
*/
};
/// <summary>
/// 已排序好的字符串列表
/// </summary>
template<class T>
class _SStrList : public _StrList<T>
{
public:
_SStrList(const _SortOrder so = _SortOrder::s_Minmax)
{
this->_so = so;
if (this->_so == _SortOrder::s_null)
{
throw _t("排序不能为空！");
}
}
//-------------------------------------------------------------------------------重写
/// <summary>
/// 快速添加字符串，差不多用了8个小时(两天），才写成。
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
bool Add(const T& item) override
{
if (this->_Count < 3)
{
bool bInsert = false;
_DListNode<T>* ld = this->_First;
while (ld != null)
{
if (this->_so == _SortOrder::s_Maxmin)
{
if (item >= ld->Data)
{
_StrList<T>::InserNodeFront(ld, item); bInsert = true;
break;
}
}
else
{
if (item <= ld->Data)
{
_StrList<T>::InserNodeFront(ld, item); bInsert = true; break;
}
}
ld = ld->Next;
}
if (!bInsert) _StrList<T>::Add(item);
return true;
}
int nPos = this->_Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = this->_Count - 1; //右边远素
if (this->_so == _SortOrder::s_Maxmin)
{
_DListNode<T>* ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = this->IndexOfNode(nPos);
if (item >= ld->Data)
{
if (nRight == nLeft || nPos == nLeft)
{
this->InserNodeFront(ld, item);
return true;
}
nRight = nPos - 1;
}
else
{
if (nRight == nLeft || nPos == nRight)
{
this->InserNodeBack(ld, item);
return true;
}
nLeft = nPos + 1;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
else
{
_DListNode<T>* ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = this->IndexOfNode(nPos);
if (item <= ld->Data)
{
if (nRight == nLeft || nPos == nLeft)
{
this->InserNodeFront(ld, item);
return true;
}
nRight = nPos - 1;
}
else
{
if (nRight == nLeft || nPos == nRight)
{
this->InserNodeBack(ld, item);
return true;
}
nLeft = nPos + 1;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
return true;
}
/// <summary>
/// 确定某元素是否在列表中
/// </summary>
/// <param name="item">查找的对象。对于引用类型，该值可以为 null。</param>
/// <returns>如果在列表中找到 item，则为 true，否则为 false。</returns>
bool Contains(const T& item) override
{
if (this->_Count == 0) return false;
if (this->_Count == 1) return this->_First->Data == item;
if (this->_Count == 2) return this->_First->Data == item || this->_First->Next->Data == item;
int nPos = (int)this->_Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)this->_Count - 1; //右边远素
_DListNode<T>* ld = null;
if (this->_so == _SortOrder::s_Maxmin)
{
while (nRight >= 0 && nLeft >= 0)
{
ld = this->IndexOfNode(nPos);
int iCom = item.CompareTo(ld->Data);
if (iCom > 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return false;
}
nRight = nPos - 1;
}
else if (iCom < 0)
{
if (nRight == nLeft || nPos == nRight)
{
return false;
}
nLeft = nPos + 1;
}
else
{
return true;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
else
{
while (nRight >= 0 && nLeft >= 0)
{
ld = this->IndexOfNode(nPos);
int iCom = item.CompareTo(ld->Data);
if (iCom < 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return false;
}
nRight = nPos - 1;
}
else if (iCom > 0)
{
if (nRight == nLeft || nPos == nRight)
{
return false;
}
nLeft = nPos + 1;
}
else
{
return true;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
return false;
}
};
/// <summary>
/// 值都是唯一的字符串列表,且已排好序，区分大小写
/// </summary>
template<class T>
class _SUStrList : public _SStrList<T>
{
public:
bool Add(const T& item)override
{
if (this->Contains(item))
return false;
return _SStrList<T>::Add(item);
}
_SUStrList(_SortOrder so = _SortOrder::s_Minmax) : _SStrList<T>(so)
{
}
};
/// <summary>
/// UStringListCI_值都是唯一,且已排序的字符串列表，不区分大小写
/// </summary>
template<class T>
class _SUStrListUI : public _SUStrList<T>
{
public:
_SUStrListUI(_SortOrder st) : _SUStrList<T>(st)
{
}
/// <summary>
/// 确定某元素是否在列表中
/// </summary>
/// <param name="item">查找的对象。对于引用类型，该值可以为 null。</param>
/// <returns>如果在列表中找到 item，则为 true，否则为 false。</returns>
bool Contains(const T& item) override
{
if (this->_Count == 0) return false;
if (this->_Count == 1) return this->_First->Data.ToLower().CompareTo(item.ToLower()) == 0;
if (this->_Count == 2) return this->_First->Data.ToLower().CompareTo(item.ToLower()) == 0 || this->_First->Next->Data.ToLower().CompareTo(item.ToLower()) == 0;
int nPos = (int)this->_Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)this->_Count - 1; //右边远素
_DListNode<T>* ld = null;
if (this->_so == _SortOrder::s_Maxmin)
{
while (nRight >= 0 && nLeft >= 0)
{
ld = this->IndexOfNode(nPos);
int iCom = item.ToLower().CompareTo(ld->Data.ToLower());
if (iCom > 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return false;
}
nRight = nPos - 1;
}
else if (iCom < 0)
{
if (nRight == nLeft || nPos == nRight)
{
return false;
}
nLeft = nPos + 1;
}
else
{
return true;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
else
{
while (nRight >= 0 && nLeft >= 0)
{
ld = this->IndexOfNode(nPos);
int iCom = item.ToLower().CompareTo(ld->Data.ToLower());
if (iCom < 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return false;
}
nRight = nPos - 1;
}
else if (iCom > 0)
{
if (nRight == nLeft || nPos == nRight)
{
return false;
}
nLeft = nPos + 1;
}
else
{
return true;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
return false;
}
};
_LF_END_
#endif
C++ CLI
/*****************************************************************************
创建时间 : 2006年12月19日
文件名 ： charp_list.h 翻译来自C#写的类(凡是后面带_csharp都是翻译自C#写的类)
作者 ： 李锋
Email : ruizhilf@139.com
联系电话 : 13828778863,25722732
－－－－－－－－－－－－－－－－－－－－－－最后一次修改时间：2020年05月09日
*******************************************************************************/
#ifndef _CSHARP_LIST_H_
#define _CSHARP_LIST_H_
#include "global_clr_extend.h"
#include "csharp_Pair.h"
_LF_BEGIN_
using namespace System;
using namespace System::Text::RegularExpressions;
using namespace System::IO;
using namespace System::Collections;
/// <summary>
/// 双向链表的节点
/// </summary>
/// <typeparam name="T"></typeparam>
template<class T>
ref class csharp_DListNode : IComparable<T>
{
public:
/// <summary>
/// 节点数据
/// </summary>
T Data;
/// <summary>
/// 前一个节点
/// </summary>
csharp_DListNode<T>^ Prev;
/// <summary>
/// 下一个节点
/// </summary>
csharp_DListNode<T>^ Next;
csharp_DListNode(T aData)
{
Data = aData;
Prev = null;
Next = null;
}
virtual int CompareTo(T data){
IComparable^ t1 = (IComparable^) Data;
IComparable^ t2 = (IComparable^) data;
return(t1->CompareTo(t2));
}
};
/// <summary>
/// 排序顺序
/// </summary>
enum class csharp_Sortord
{
s_min_max, //从小到大
s_max_min, //从大到小
s_null //无排序顺序
};
/// <summary>
/// 双向链表
/// https://learn.microsoft.com/zh-cn/previous-versions/visualstudio/visual-studio-2012/a174071k(v=vs.110
/// </summary>
template<class T>
ref class csharp_DList : System::Collections::IEnumerable
{
protected:
csharp_DListNode<T>^ _First; //第一个节点
csharp_DListNode<T>^ _Last; //最后一个节点
int _Count; //节点个数
csharp_Sortord _sortord; //排序顺序
inline void InitData() {
_Count = 0; _First = null; _Last = null;
_sortord = csharp_Sortord::s_null;
}
public:
//------------------------------------------------------------------------------------------构造函数
/// <summary>
/// 构造函数
/// </summary>
inline csharp_DList() { InitData(); }
csharp_DList(csharp_DList^ cs)
{
auto pNode = cs->_First;
while (pNode != null) {
Add(pNode->Data);
pNode = pNode->Next;
}
}
inline csharp_DList(... array<T>^ tArray) {
InitData();
for each (T t in tArray) { Add(t); }
}
public:
//------------------------------------------------------------------------------------------属性
/// <summary>
/// 实际包含的元素数
/// </summary>
property int Count
{
int get()
{
return _Count;
}
}
/*
virtual T this[int index]
{
get
{
return IndexOfNode(index)->Data;
}
set
{
IndexOfNode(index)->Data = value;
}
}
*/
/// <summary>
/// 获取或设置指定索引处的元素
/// </summary>
/// <param name="index">要获得或设置的元素从零开始的索引</param>
/// <returns>指定索引处的元素</returns>
T operator[](int index) {
csharp_DListNode<T>^ dn = IndexOfNode(index);
return dn->Data;
}
//---------------------------------------------------------------------------------运算符重载
/// <summary>
///
/// </summary>
/// <param name="dLeft"></param>
/// <param name="dlRight"></param>
/// <returns></returns>
/// 创建时间： 2021-11-07 最后一次修改时间：2021-11-07
static csharp_DList<T>^ operator +(csharp_DList<T>^ dLeft, csharp_DList<T>^ dlRight)
{
/*
csharp_DList<T>^ dlResult = gcnew csharp_DList<T>^ ();
dlResult->Add(dLeft);
dlResult->Add(dlRight);
return dlResult;
*/
return gcnew csharp_DList<T>^ { dLeft, dlRight };
}
//---------------------------------------------------------------------------------功能函数
/// <summary>
/// 将指定集合的元素添加到末尾
/// </summary>
/// <param name="item">要添加到的末尾处的对象。对于引用类型，该值可以为 null</param>
/// <returns>如成功，返回真，否则返回假</returns>
virtual void Add(T item)
{
if (_Count == 0)
{
_First = gcnew csharp_DListNode<T>(item);
_First->Next = null;
_First->Prev = null;
_Last = _First;
}
else
{
csharp_DListNode<T>^ pNew = gcnew csharp_DListNode<T>(item);
pNew->Next = null;
pNew->Prev = _Last;
_Last->Next = pNew;
_Last = pNew;
}
++_Count;
_sortord = csharp_Sortord::s_null; //要重新排序
}
/// <summary>
///
/// </summary>
/// <param name="nIndex"></param>
/// <param name="item"></param>
/// <returns></returns>
/// 创建时间： 2022-08-11 最后一次修改时间：2022-08-12
virtual void Insert(int nIndex, T item)
{
if (nIndex > _Count)
{
throw gcnew Exception(L"_DList->Insert 插入位置错误！");
}
if (nIndex == 0)
{
if (_First != null)
{
csharp_DListNode<T>^ dnNew = gcnew csharp_DListNode<T>(item);
_First->Prev = dnNew;
dnNew->Next = _First;
_First = dnNew;
++_Count;
_sortord = csharp_Sortord::s_null;
}
else
{
Add(item);
}
}
else if (nIndex == _Count)
{
Add(item);
}
else
{
csharp_DListNode<T>^ dnNew = gcnew csharp_DListNode<T>(item);
csharp_DListNode<T>^ dnNext = IndexOfNode(nIndex);
csharp_DListNode<T>^ dnPrev = dnNext->Prev;
dnNew->Next = dnNext;
dnNew->Prev = dnPrev;
dnNext->Prev = dnNew;
dnPrev->Next = dnNew;
++_Count;
_sortord = csharp_Sortord::s_null;
}
}
void Add(csharp_DList<T>^ dList)
{
if (dList == null)
{
throw gcnew System::Exception("csharp_DList<T>^->Add中参数dList==null");
}
csharp_DListNode<T>^ ld = dList->_First;
while (ld != null)
{
Add(ld->Data);
ld = ld->Next;
}
}
String^ ToString() override
{
if (_Count == 0) {
return L"";
}
else if (_Count == 1) {
return ((Object^)First->Data)->ToString();
}
else {
String^ sResult = "";
csharp_DListNode<T>^ dnNode = _First;
while (dnNode != _Last)
{
sResult += ((Object^)dnNode->Data)->ToString();
sResult += L",";
dnNode = dnNode->Next;
}
return sResult + ((Object^)_Last->Data)->ToString();
}
}
String^ ToString(String^ sSplit)
{
String^ sResult = "";
csharp_DListNode<T>^ dnNode = _First;
while (dnNode != null)
{
sResult += ((Object^)dnNode->Data)->ToString();
if (dnNode != Last)
sResult += sSplit;
dnNode = dnNode->Next;
}
return sResult;
}
/// <summary>
/// 使用指定的比较器在整个已排序的 中搜索元素，并返回该元素从零开始的索引
/// </summary>
/// <param name="item">要定位的对象。对于引用类型，该值可以为 null。</param>
/// <returns>如果找到 item，则为已排序的 的从零开始的索引；否则为-1; </returns>
int BinarySearch(T item)
{
IComparable^ icItem = (IComparable^)item;
switch (_sortord)
{
case csharp_Sortord::s_max_min:
{
if (Count == 0)
{
return -1;
}
if (Count == 1)
{
IComparable^ icTemp = (IComparable^)_First->Data;
return icTemp->CompareTo(icItem) == 0 ? 0 : -1;
}
if (Count == 2)
{
IComparable^ icTemp = (IComparable^)_First->Data;
if ( icTemp->CompareTo(icTemp) == 0) return 0;
icTemp = (IComparable^)_First->Next->Data;
if(icTemp->CompareTo(icTemp) == 0) return 1;
return -1;
}
int nPos = (int)Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)Count - 1; //右边远素
csharp_DListNode<T>^ ld;
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNode(nPos);
int iCom = icItem->CompareTo(ld->Data);
if (iCom > 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return -1;
}
nRight = nPos - 1;
}
else if (iCom < 0)
{
if (nRight == nLeft || nPos == nRight)
{
return -1;
}
nLeft = nPos + 1;
}
else
{
return nPos;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case csharp_Sortord::s_min_max:
{
if (Count == 0)
{
return -1;
}
if (Count == 1)
{
return icItem->CompareTo(First->Data) == 0 ? 0 : -1;
}
if (Count == 2)
{
if ( icItem->CompareTo(First->Data) == 0) return 0;
if ( icItem->CompareTo(First->Next->Data) == 0) return 1;
return -1;
}
int nPos = (int)Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)Count - 1; //右边远素
csharp_DListNode<T>^ ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNode(nPos);
int iCom = icItem->CompareTo(ld->Data);
if (iCom < 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return -1;
}
nRight = nPos - 1;
}
else if (iCom > 0)
{
if (nRight == nLeft || nPos == nRight)
{
return -1;
}
nLeft = nPos + 1;
}
else
{
return nPos;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case csharp_Sortord::s_null:
{
csharp_DListNode<T>^ pNode = _First;
int iCount = 0;
while (pNode != null)
{
if (((Object^)pNode->Data)->Equals(item))
{
return iCount;
}
pNode = pNode->Next;
++iCount;
}
break;
}
default:
{
return -1;
}
}
return -1;
}
/**
* 功能：清空所有元素的所有数据，并清空链表
* 创建时间：????/??/??
* 最后一次修改时间：2022-07-02
*/
void Clear()
{
_Count = 0;
csharp_DListNode<T>^ pTemp1 = _First;
while (pTemp1 != null)
{
csharp_DListNode<T>^ pTemp2 = pTemp1->Next;
pTemp1->Data = T(); // default(T);
pTemp1->Next = null;
pTemp1->Prev = null;
pTemp1 = pTemp2;
}
_First = null;
_Last = null;
}
/// <summary>
/// 确定某元素是否在列表中
/// </summary>
/// <param name="item">查找的对象。对于引用类型，该值可以为 null。</param>
/// <returns>如果在列表中找到 item，则为 true，否则为 false。</returns>
virtual bool Contains(T item)
{
return BinarySearch(item) != -1;
}
/// <summary>
/// 复制一个链表，清除原来链表的数据
/// </summary>
/// <param name="ld"></param>
void CopyFrom(csharp_DList<T>^ ld)
{
if (!this->Equals(ld))
{
Clear();
csharp_DListNode<T>^ ldItem = ld->_First;
while (ldItem != null)
{
Add(ldItem->Data);
ldItem = ldItem->Next;
}
}
}
/*
int IndexOf(T item)
{
return -1;
}
int IndexOf(T item, int index)
{
return -1;
}
void Insert(int index, T item)
{
}
int LastIndexOf(T item)
{
return -1;
}
int LastIndexOf(T item, int index, int Count)
{
return -1;
}
*/
/// <summary>
/// 移除指定索引处的元素
/// </summary>
/// <param name="iIndex">要移除的元素的从零开始的索引。</param>
/// <returns>成功返回true,否则返回false</returns>
bool RemoveAt(int iIndex)
{
if (iIndex < 0 || iIndex + 1 > _Count) { return false; }
csharp_DListNode<T>^ pNode = _First;
int iCount = 0;
while (pNode != null)
{
if (iCount == iIndex)
{
if (pNode == _First)
{
if (_First->Next == null) //只有一个
{
Clear();
return true;
}
else
{
_First = _First->Next;
_First->Prev = null;
--_Count;
return true;
}
}
else if (pNode == _Last)
{
if (_Last->Prev == null)
{
Clear();
return true;
}
else
{
_Last = _Last->Prev;
_Last->Next = null;
--_Count;
return true;
}
}
else
{
pNode->Prev->Next = pNode->Next;
pNode->Next->Prev = pNode->Prev;
pNode = null;
--_Count;
return true;
}
}
pNode = pNode->Next;
++iCount;
}
return false;
}
/// <summary>
/// 反向排列链表
/// </summary>
/// 创建时间： 2022-04-20 最后一次修改时间：2022-04-20
virtual void Reverse()
{
/*
csharp_DListNode<T>^ dnTemp = First;
while (dnTemp != null)
{
_Math::Swap< csharp_DListNode<T>^>(dnTemp->Next, dnTemp->Prev);
dnTemp = dnTemp->Prev;
}
_Math::Swap< csharp_DListNode<T>^>(_First, _Last);
*/
throw gcnew Exception("未完成！");
}
/// <summary>
/// 添加一个元素，并把它放在首位，其它元素后移,如果后面的元素删除，总无素个数不变，如果元素个数为零，则添加一个无素。
/// </summary>
/// <param name="Item"></param>
/// <param name="bRemoveLast"></param>
/// 创建时间： 2022-04-19 最后一次修改时间：2022-04-19
void StackPush(T Item, bool bRemoveLast) {
if (_Count == 0) {
Add(Item);
}
else if (_Count == 1) {
if (bRemoveLast) {
_First->Data = Item;
}
else {
//把无素放在最前
csharp_DListNode<T>^ dnNew = gcnew csharp_DListNode<T> (Item);
_First->Prev = dnNew;
dnNew->Next = _First;
_First = dnNew;
++_Count;
}
}
else {
if (bRemoveLast) {
//删除最后一个元素
_Last = _Last->Prev;
_Last->Next = null;
//把无素放在最前
csharp_DListNode<T>^ dnNew = gcnew csharp_DListNode<T>(Item);
_First->Prev = dnNew;
dnNew->Next = _First;
dnNew->Prev = null;
_First = dnNew;
}
else {
//把无素放在最前
csharp_DListNode<T>^ dnNew = gcnew csharp_DListNode<T>(Item);
_First->Prev = dnNew;
dnNew->Next = _First;
dnNew->Prev = null;
_First = dnNew;
++_Count;
}
}
}
/// <summary>
/// 删除第一个元素，出栈
/// </summary>
/// 创建时间： 2022-04-19 最后一次修改时间：2022-04-19
void StackPop() { RemoveAt(0); }
/*
/// <summary>
/// 转换成数组
/// </summary>
/// <returns></returns>
T[] ToArray()
{
T[] aResult = gcnew T[Count];
int n = 0;
csharp_DListNode<T>^ pNodeTemp = _First;
while (pNodeTemp != null)
{
aResult[n++] = pNodeTemp->Data;
pNodeTemp = pNodeTemp->Next;
}
return aResult;
}
*/
protected:
/// <summary>
/// 交换两个节点的数据
/// </summary>
/// <param name="nIndex1"></param>
/// <param name="nIndex2"></param>
/// <returns></returns>
virtual bool swapNodeData(int iIndex1, int iIndex2)
{
csharp_DListNode<T>^ pNode1, ^ pNode2;
pNode1 = IndexOfNode(iIndex1);
pNode2 = IndexOfNode(iIndex2);
if (!(pNode1 != null && pNode2 != null))
{
return false;
}
T ptmp = pNode1->Data;
pNode1->Data = pNode2->Data;
pNode2->Data = ptmp;
return true;
}
public:
/// <summary>
/// 选择排序可以说是最简单的一种排序方法：
/// 1->找到数组中最小的那个元素
/// 2->将最小的这个元素和数组中第一个元素交换位置
/// 3->在剩下的元素中找到最小的的元素，与数组第二个元素交换位置
/// 重复以上步骤，即可以得到有序数组。
/// </summary>
virtual void sort_selection(csharp_Sortord sortord)
{
if (_Count == 0 || _Count == 1) return;
/*
//is关键字用于检查对象是否与给定类型兼容。注意了，这里is并不是“是”的意思，而是“兼容”。
if (!(_First.Data is IComparable)) // 判断是否具有IComparable接口，以确定是否存在CompareTo()方法
{
throw gcnew Exception("没有IComparable接口");
}
*/
csharp_DListNode<T> ^dnMin = _First, ^dnTemp = _First->Next;
if (sortord == csharp_Sortord::s_min_max)
{
while (dnMin->Next != null)
{
while (dnTemp != null)
{
IComparable^ icTemp = (IComparable ^) dnTemp->Data;
if (icTemp->CompareTo(dnMin->Data) < 0) //交换位置
{
T pt = dnTemp->Data;
dnTemp->Data = dnMin->Data;
dnMin->Data = pt;
}
dnTemp = dnTemp->Next;
}
dnMin = dnMin->Next;
dnTemp = dnMin->Next;
}
}
else
{
while (dnMin->Next != null)
{
while (dnTemp != null)
{
IComparable^ icTemp = (IComparable ^ )dnTemp->Data;
if (icTemp->CompareTo(dnMin->Data) > 0)
{
T pt = dnTemp->Data;
dnTemp->Data = dnMin->Data;
dnMin->Data = pt;
}
dnTemp = dnTemp->Next;
}
dnMin = dnMin->Next;
dnTemp = dnMin->Next;
}
}
_sortord = sortord; //已排序
}
/// <summary>
/// 返回索引的节点,从零开始
/// </summary>
/// <param name="nPos"></param>
/// <returns></returns>
virtual csharp_DListNode<T>^ IndexOfNode(int iPos)
{
if (iPos >= _Count || iPos < 0) throw gcnew System::Exception(L"csharp_DListNode<T>^->IndexOfNode 错误索引: " + iPos.ToString() + "！");
unsigned int nindex = 0;
if (iPos > _Count / 2)
{
csharp_DListNode<T>^ pNode = _Last;
while (pNode != null)
{
if (nindex++ == _Count - iPos - 1) { return pNode; }
pNode = pNode->Prev;
}
}
else
{
csharp_DListNode<T>^ pNode = _First;
while (pNode != null)
{
if (nindex++ == iPos)
{
return pNode;
}
pNode = pNode->Next;
}
}
return null;
}
public:
/// <summary>
/// 在结点pListItem前面插入一个结点,成功，返回新的结点，否则返回０
/// </summary>
/// <param name="pListItem"></param>
/// <param name="pData"></param>
/// <returns></returns>
virtual csharp_DListNode<T>^ InserNodeFront(csharp_DListNode<T>^ pListItem, T pData)
{
if (pListItem == null)
{
throw gcnew System::Exception(L"函数提示：pListItem = null");
}
csharp_DListNode<T>^ pNode = gcnew csharp_DListNode<T>(pData);
//pNode
pNode->Next = pListItem;
pNode->Prev = pListItem->Prev;
//--pListItem->Prev
if (pListItem->Prev != null)
{
pListItem->Prev->Next = pNode;
}
else
{
_First = pNode;
}
//pListItem
pListItem->Prev = pNode;
++_Count;
return pNode;
}
/// <summary>
/// 在结点pListItem后面插入一个结点,成功，返回新的结点，否则返回０；
/// </summary>
/// <param name="pListItem"></param>
/// <param name="pData"></param>
/// <returns></returns>
virtual csharp_DListNode<T>^ InserNodeBack(csharp_DListNode<T>^ pListItem, T pData)
{
if (pListItem == null) return null;
csharp_DListNode<T>^ pNode = gcnew csharp_DListNode<T>(pData);
//pNode
pNode->Prev = pListItem;
pNode->Next = pListItem->Next;
//pListItem->Next
if (pListItem->Next != null)
{
pListItem->Next->Prev = pNode;
}
else
{
_Last = pNode;
}
//--pListItem
pListItem->Next = pNode;
++_Count;
return pNode;
}
/// <summary>
/// 找查一个项，而不是节点，返回的这个节点相当于指针。
/// </summary>
/// <param name="pData">项值</param>
/// <returns></returns>
csharp_DListNode<T>^ FindNodeItem(T item)
{
switch (_sortord)
{
case csharp_Sortord::s_max_min:
{
if (Count == 0)
{
return null;
}
if (Count == 1)
{
IComparable^ ic = (IComparable^)_First->Data;
return ic->CompareTo(item) == 0 ? _First : null;
}
if (Count == 2)
{
IComparable^ ic = (IComparable^)_First->Data;
if (ic->CompareTo(item) == 0) return _First;
ic = (IComparable^)_First->Next->Data;
if (ic->CompareTo(item) == 0) return _First->Next;
return null;
}
int nPos = (int)Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)Count - 1; //右边远素
csharp_DListNode<T>^ ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNode(nPos);
IComparable^ ic = (IComparable^)item;
int iCom = ic->CompareTo(ld->Data);
if (iCom > 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return null;
}
nRight = nPos - 1;
}
else if (iCom < 0)
{
if (nRight == nLeft || nPos == nRight)
{
return null;
}
nLeft = nPos + 1;
}
else
{
return ld;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case csharp_Sortord::s_min_max:
{
if (Count == 0)
{
return null;
}
if (Count == 1)
{
IComparable ^ic = (IComparable^)_First->Data;
return ic->CompareTo(item) == 0 ? _First : null;
}
if (Count == 2)
{
IComparable^ ic = (IComparable^)_First->Data;
if (ic->CompareTo(item) == 0) return _First;
ic = (IComparable^)_First->Next->Data;
if (ic->CompareTo(item) == 0) return _First->Next;
return null;
}
int nPos = (int)Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)Count - 1; //右边远素
csharp_DListNode<T>^ ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNode(nPos);
IComparable^ ic = (IComparable^)item;
int iCom = ic->CompareTo(ld->Data);
if (iCom < 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return null;
}
nRight = nPos - 1;
}
else if (iCom > 0)
{
if (nRight == nLeft || nPos == nRight)
{
return null;
}
nLeft = nPos + 1;
}
else
{
return ld;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case csharp_Sortord::s_null:
{
csharp_DListNode<T>^ pNode = _First;
while (pNode != null)
{
//总结:Equals比较的永远是变量的内容是否相同，而= =比较的则是引用地址是否相同(前提:此种类型内部没有对Equals 或= = 进行重写操作，
//否则输出可能会有不同)。String^ 类型是个特例，因为他的内部对这两个都进行了重写。
IComparable^ ic = (IComparable^)item;
if (ic->CompareTo(pNode->Data) == 0)
{
return pNode;
}
/*
if (pNode->Data->Equals(item))
{
return pNode;
}
*/
pNode = pNode->Next;
}
break;
}
default:
{
return null;
}
}
return null;
}
/// <summary>
/// 把索引为nIndex的节点移到最后
/// </summary>
/// <param name="nIndex"></param>
/// <returns></returns>
virtual bool MoveLast(int iIndex)
{
csharp_DListNode<T>^ pNode = IndexOfNode(iIndex);
if (pNode != null)
{
if (pNode == _Last)
return true;
if (pNode == _First) //此时最少两个节点
{
_First = _First->Next;
_First->Prev = null;
_Last->Next = pNode;
pNode->Prev = _Last;
_Last = pNode;
}
else
{
pNode->Prev->Next = pNode->Next;
pNode->Next->Prev = pNode->Prev;
_Last->Next = pNode;
pNode->Prev = _Last;
_Last = pNode;
}
return true;
}
return false;
}
/// <summary>
///
/// </summary>
/// <param name="dnCurrent"></param>
/// <returns></returns>
/// 创建时间： 2022-02-18 最后一次修改时间：2022-02-18
virtual bool MoveLast(csharp_DListNode<T>^ dnCurrent)
{
if (dnCurrent == null) return false;
_sortord = csharp_Sortord::s_null;
if (_Count == 0)
{
return false;
}
else if (_Count == 1)
{
return true;
}
else if (_Count == 2)
{
if (dnCurrent == _First) //交换_First 与 _Last 数据
{
T tmp = _First->Data;
_First->Data = _Last->Data;
_Last->Data = tmp;
}
return true;
}
else
{
if (dnCurrent == _First)
{
_First = _First->Next;
_First->Prev = null;
_Last->Next = dnCurrent;
dnCurrent->Next = null;
dnCurrent->Prev = _Last;
_Last = dnCurrent;
}
else if (dnCurrent != _Last)
{
dnCurrent->Prev->Next = dnCurrent->Next;
dnCurrent->Next->Prev = dnCurrent->Prev;
_Last->Next = dnCurrent;
dnCurrent->Next = null;
dnCurrent->Prev = _Last;
_Last = dnCurrent;
}
return true;
}
}
/// <summary>
/// 把索引为nIndex的节点移到最前
/// </summary>
/// <param name="nIndex"></param>
/// <returns></returns>
virtual bool MoveFirst(int iIndex)
{
csharp_DListNode<T>^ pNode = IndexOfNode(iIndex);
if (pNode != null)
{
if (pNode == _First)
return true;
if (pNode == _Last) //此时最少两个节点
{
_Last->Prev->Next = null;
_Last = _Last->Prev;
pNode->Prev = null;
pNode->Next = _First;
_First->Prev = pNode;
_First = pNode;
}
else
{
pNode->Prev->Next = pNode->Next;
pNode->Next->Prev = pNode->Prev;
pNode->Next = _First;
_First->Prev = pNode;
pNode->Prev = null;
_First = pNode;
}
return true;
}
return false;
}
public:
/// <summary>
/// 返回第一个节点
/// </summary>
property csharp_DListNode<T>^ First
{
csharp_DListNode<T>^ get()
{
return _First;
}
}
/// <summary>
/// 返回最后一个节点
/// </summary>
property csharp_DListNode<T>^ Last
{
csharp_DListNode<T>^ get() {
return _Last;
}
}
//--------------------------------------------------------------------------------------
/// <summary>
/// 删除链表中的数据
/// </summary>
/// <param name="pData"></param>
/// <returns></returns>
bool RemoveItem(T pData)
{
if (_sortord == csharp_Sortord::s_null)
{
csharp_DListNode<T>^ pListItem = _First;
while (pListItem != null)
{
if (pListItem->Data->Equals(pData)) //找到一项
{
if (pListItem == _First) //删除的是第一个节点
{
if (_First->Next != null)
{
_First->Next->Prev = null;
_First = _First->Next;
}
else
{
_First = null;
_Last = null;
}
}
else if (pListItem == _Last) //删除的是最后一个节点
{
if (_Last->Prev != null)
{
_Last->Prev->Next = null;
_Last = _Last->Prev;
}
else
{
_First = null;
_Last = null;
}
}
else //删除的是中间的一个节点
{
pListItem->Next->Prev = pListItem->Prev;
pListItem->Prev->Next = pListItem->Next;
}
--_Count;
return true;
}
pListItem = pListItem->Next;
}
return false;
}
else
{
return RemoveAt(BinarySearch(pData));
}
}
/// <summary>
/// 删除链表中的节点
/// </summary>
/// <param name="pListItem"></param>
/// <returns></returns>
bool DeleteNode(csharp_DListNode<T>^ pListItem)
{
if (_Count == 0 || pListItem == null)
{
return false;
}
csharp_DListNode<T>^ pNode = _First->Next;
while (pNode != null)
{
if (pNode == pListItem) //找到了
{
//pListItem->Prev
if (pListItem->Prev != null)
{
pListItem->Prev->Next = pListItem->Next;
}
else //删除的是第一个节点
{
_First = pListItem->Next;
}
//pListItem->Next
if (pListItem->Next != null)
{
pListItem->Next->Prev = pListItem->Prev;
}
else //删除的是最后一个节点
{
_Last = pListItem->Prev;
}
break;
}
pNode = pNode->Next;
}
if (pNode != null)
{
--_Count;
return true;
}
return false;
}
/// <summary>
/// 删除最后一个节点
/// </summary>
/// 创建时间：2020-09-12 最后一次修改时间： 2020-09-12
bool DeleteLast()
{
if (_Count <= 0)
{
return false;
}
else if (_Count == 1)
{
_First = null;
_Last = null;
_Count = 0;
return true;
}
else if (_Count == 2)
{
_Last = _First;
_Last->Prev = null;
_Last->Next = null;
_First->Next = null;
_First->Prev = null;
--_Count;
}
else
{
_Last->Prev->Next = null;
_Last = _Last->Prev;
--_Count;
}
return true; ;
}
//--------------------------------------------------------------------------接口
/// <summary>
//示例为了使一个类支持集合初始化器，它必须实现IEnumerable接口并至少具有一个Add方法。从C＃6开始，
//IEnumerable可以Add使用扩展方法使用自定义方法扩展任何实现的集合。
/// </summary>
/// 创建时间：2020-05-07 最后一次修改时间： 2020-05-07
/// <returns></returns>
virtual System::Collections::IEnumerator^ GetEnumerator()
{
return gcnew csharp_DListNodeEnum<T>(_First);
}
/// <summary>
/// 节点数据的foreach迭代
/// </summary>
/// 创建时间：2020-05-07 最后一次修改时间： 2020-05-07
/// <typeparam name="T"></typeparam>
template<class T>
ref class csharp_DListNodeEnum : System::Collections::IEnumerator
{
private:
csharp_DListNode<T>^ _dn;
csharp_DListNode<T>^ _dnCurr;
int _iIndex;
public:
csharp_DListNodeEnum(csharp_DListNode<T>^ dn)
{
_dn = dn;
_iIndex = -1;
}
/// <summary>
/// IEnumerator最终调用的是这个函数访问
/// </summary>
virtual property Object^ Current
{
Object^ get() {
return _dnCurr-> Data;
}
}
virtual bool MoveNext()
{
++ _iIndex; //指针首先向前移动一位
if (_dnCurr == null){
_dnCurr = _dn;
}else{
_dnCurr = _dnCurr-> Next;
}
return _dnCurr != null;
}
virtual void Reset()
{
_dnCurr = null;
_iIndex = -1;
}
};
};
/// <summary>
/// 已排序的链表
/// </summary>
template<class T>
ref class csharp_SortList : csharp_DList<T>{
public:
csharp_SortList(csharp_Sortord sortord)
{
_sortord = sortord;
}
//-------------------------------------------------------------------------------重写
/// <summary>
/// 添加一项到结尾处，item不能为NULL->
/// </summary>
/// <param name="item">项</param>
/// 创建时间： ????-??-?? 最后一次修改时间：2021-11-07
void Add(T item) override
{
if (item == null)
{
throw gcnew System::Exception(L"csharp_SortList->Add 方法提示：类型值不能为null！");
}
//if (!(item is IComparable)) // 判断是否具有IComparable接口，以确定是否存在CompareTo()方法
//{
// throw gcnew System::Exception(L"csharp_SortList<" + item->GetType()->Name + L">->Add 方法提示：类型“" + item->GetType()->Name + L"”没有IComparable接口！");
//}
IComparable^ icItem = item;
if (Count < 3)
{
bool bInsett = false; csharp_DListNode<T>^ ldNode = First;
while (ldNode != null)
{
if (_sortord == csharp_Sortord::s_max_min)
{
if (icItem->CompareTo(ldNode->Data) >= 0)
{
csharp_DList<T>::InserNodeFront(ldNode, item); bInsett = true; break;
}
}
else
{
if (icItem->CompareTo(ldNode->Data) <= 0)
{
csharp_DList<T>::InserNodeFront(ldNode, item); bInsett = true; break;
}
}
ldNode = ldNode->Next;
}
if (!bInsett) csharp_DList<T>::Add(item);
return;
}
int nPos = Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = Count - 1; //右边远素
if (_sortord == csharp_Sortord::s_max_min)
{
csharp_DListNode<T>^ ldNode = null;
while (nRight >= 0 && nLeft >= 0)
{
ldNode = IndexOfNode(nPos);
if (icItem->CompareTo(ldNode->Data) >= 0)
{
if (nRight == nLeft || nPos == nLeft)
{
InserNodeFront(ldNode, item);
return;
}
nRight = nPos - 1;
}
else
{
if (nRight == nLeft || nPos == nRight)
{
InserNodeBack(ldNode, item);
return;
}
nLeft = nPos + 1;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
else
{
csharp_DListNode<T>^ ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNode(nPos);
if (icItem->CompareTo(ld->Data) <= 0)
{
if (nRight == nLeft || nPos == nLeft)
{
InserNodeFront(ld, item);
return;
}
nRight = nPos - 1;
}
else
{
if (nRight == nLeft || nPos == nRight)
{
InserNodeBack(ld, item);
return;
}
nLeft = nPos + 1;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
return;
}
};
/// <summary>
/// 每个项的值都是唯一的链表
/// </summary>
template<class T>
ref class csharp_UniqueList : csharp_DList<T>{
public:
void Add(T item) override
{
if (BinarySearch(item) == -1)
{
csharp_DList<T>::Add(item);
}
}
};
/// <summary>
/// SUList_,已排序，且每一项的值都是唯一的链表
/// </summary>
template<class T>
ref class csharp_SUList : csharp_SortList<T>{
public:
/// <summary>
/// 将指定集合的元素添加到末尾
/// </summary>
/// <param name="item">要添加到的末尾处的对象。对于引用类型，该值可以为 null</param>
/// <returns>如成功，返回真，否则返回假</returns>
void Add(T item) override {
if (BinarySearch(item) == -1) {
csharp_SortList::Add(item);
}
}
csharp_SUList(csharp_Sortord sortord) : csharp_SortList<T>(sortord){
}
};
/// <summary>
/// 字符串列表
/// </summary>
ref class csharp_StringList : csharp_DList<String^>
{
public:
/// <summary>
/// 默认构函数
/// </summary>
csharp_StringList() { }
csharp_StringList(csharp_StringList^ cs) : csharp_DList<String^>(cs){ }
/// <summary>
/// 列表初始化
/// </summary>
/// <param name="sArray"></param>
/// 创建时间： 2022-10-25 最后一修改时间：2022-10-25
csharp_StringList(... cli::array<String^>^ sArray) : csharp_DList<String^>(sArray) { }
/// <summary>
/// 以分隔符构造一个字符串列表
/// </summary>
/// <param name="sText">原文字符串</param>
/// <param name="sSplit">分隔符</param>
/// <param name="bIgnoreEmptyString">返回列表，空字符串不忽略，如果没有分隔符，则回原字符</param>
/// 创建时间： ????-??-?? 最后一修改时间：2020-09-03
csharp_StringList(String^ sText, String^ sSplit, bool bIgnoreEmptyString){SplitForSeparator(sText, sSplit, bIgnoreEmptyString);}
csharp_StringList(String^ sText, String^ sSplit) { SplitForSeparator(sText, sSplit, false); }
/// 把列表写入文件
/// </summary>
/// <param name="sFileName">文件名</param>
void WriteToFile(String^ sFileName)
{
System::IO::File::Delete(sFileName);
csharp_DListNode<String^>^ dl = _First;
FileStream^ fs = File::Create(sFileName);
while (dl != null) {
array<unsigned char>^ bArray = System::Text::Encoding::Default->GetBytes(dl->Data);
fs->Write(bArray, 0, bArray->Length);
bArray = System::Text::Encoding::Default->GetBytes(L"\r\n");
//fs->WriteByte((byte)'\r'); 不行，UNICODE代码
//fs->WriteByte((byte)'\n');
if( dl != _Last)
fs->Write(bArray, 0, bArray->Length);
dl = dl->Next;
}
fs->Close();
}
/// <summary>
/// 从文件中读取列表分隔符为"\r\n";
/// </summary>
/// <param name="sFileName">文件名</param>
/// <returns></returns>
bool ReadToFile(String^ sFileName)
{
if (File::Exists(sFileName))
{
Clear();
FileStream^ fs = gcnew FileStream(sFileName, FileMode::Open, FileAccess::Read);
array<byte>^ bArray = gcnew array<byte>((int)fs->Length);
fs->Read(bArray, 0, bArray->Length);
fs->Close();
String^ sTemp = System::Text::Encoding::Default->GetString(bArray);
Add(gcnew csharp_StringList(sTemp, L"\r\n", false)); //调用构造函数，探马回一个对象，并不改变自身
return true;
}
else {
ga.p(L"文件不存在！");
}
return false;
}
/// <summary>
/// 从文件中读取列表分隔符
/// </summary>
/// <param name="sFileName"></param>
/// <param name="sSplit"></param>
/// <returns></returns>
bool readToUnicodeFile(String^ sFileName, String^ sSplit)
{
if (File::Exists(sFileName))
{
Clear();
FileStream ^fs = gcnew FileStream(sFileName, IO::FileMode::Open,IO::FileAccess::Read);
//Byte[] bArray = gcnew Byte[fs.Length];
//fs.Read(bArray, 0, bArray.Length);
array<Byte> ^bArray = gcnew array<Byte>((int)fs->Length);
fs->Read(bArray, 0, bArray->Length);
fs->Close();
Add(gcnew csharp_StringList(Encoding::Unicode->GetString(bArray), sSplit, false));
return true;
}
return false;
}
void SaveToUnicodeFile(String^ sFileName, String^ sSplit)
{
/*
if(_Count > 0)
{
String^ sContent = "";
int n = 1;
foreach(String^ s in this)
{
sContent += s;
if(n != _Count)
sContent += sSplit;
}
Byte[] bArray = System->Text->ASCIIEncoding->ASCII->GetBytes(sContent);
FileStream fs = gcnew FileStream(sFileName, FileMode->Create, FileAccess->Write);
fs->Write(bArray, 0, bArray->Length);
fs->Close();
}
*/
}
/// <summary>
/// 把所有字符串写入磁盘，但每个字符串中的空格和不可打印字符都不会写入，每15个字符串加入一个换行符。
/// </summary>
/// <param name="sFileName"></param>
/// <param name="sSplit"></param>
/// 创建时间： 2022-02-09 最后一次修改时间：2022-02-09
void WriteToTxtFile(String^ sFileName, String^ sSplit)
{
if (_Count > 0)
{
String^ sContent = "";
int n = 1;
for each (String ^ s in *this)
{
sContent += gce::s_RemoveUnprintableAndWhitespace(s);
if (n != _Count)
sContent += sSplit;
if (n % 15 == 0)
sContent += "\n";
++n;
}
File::WriteAllText(sFileName, sContent);
}
}
/// <summary>
/// 用分隔 符读取文本文件，空格和不可打印字符都不读取。
/// </summary>
/// <param name="sFileName"></param>
/// <param name="sSplit"></param>
/// 创建时间： 2022-02-09 最后一次修改时间：2022-02-18
void ReadFromTxtFile(String^ sFileName, String^ sSplit){
if (!File::Exists(sFileName))
return;
String^ sContent = gce::s_RemoveUnprintableAndWhitespace(File::ReadAllText(sFileName));
if (sContent->Trim()->Length > 0)
{
Add(gcnew csharp_StringList(sContent, sSplit, false));
}
}
/// <summary>
/// 用分隔符把每个项连成一片，如果分隔符为空，则直接连成一片
/// </summary>
/// <param name="sSeparator">分隔符</param>
/// <returns></returns>
String^ ConnectForSeparator(String^ sSeparator)
{
if (Count == 0) return "";
if (Count == 1) return First->Data;
String^ tmp = L"";
csharp_DListNode<String^>^ ldNode = First;
while (ldNode != this->Last)
{
tmp += (String^)ldNode->Data;
tmp += sSeparator;
ldNode = ldNode->Next;
}
tmp += (String^)Last->Data; //加入最后一项
return tmp;
}
/// <summary>
/// 用分隔符把每个项连成一片，如果分隔符为空，则直接连成一片
/// </summary>
/// <param name="cSeparator">分隔符</param>
/// <returns></returns>
String^ ConnectForSeparator(char cSeparator)
{
return ConnectForSeparator(cSeparator.ToString());
}
/// <summary>
/// 清空列表，用分隔符把字符串分裂成多项,返回项数
/// </summary>
/// <param name="sText"></param>
/// <param name="sSplit"></param>
/// <param name="bIgnoreEmptyString">是否忽略空字符串</param>
csharp_StringList^ SplitForSeparator(String^ sText, String^ sSplit, bool bIgnoreEmptyString)
{
Clear();
if (sText == null || sText->Length == 0) { return this; }
if (sSplit->Length == 0) { Add(sText); return this; }
int nPos = sText->IndexOf(sSplit);
int nFindStart = 0;
while (nPos != -1){
if (nPos - nFindStart == 0){
if (!bIgnoreEmptyString) {
Add(L"");
}
}else{
Add(sText->Substring(nFindStart, nPos - nFindStart));
}
nFindStart = nPos + sSplit->Length;
nPos = sText->IndexOf(sSplit, nFindStart);
if (nPos == -1){ //拷贝最后一个
if (nFindStart < sText->Length){
Add(sText->Substring(nFindStart, sText->Length - nFindStart));
}else{
if (!bIgnoreEmptyString){
Add(L"");
}
}
}
}
return this;
}
/// <summary>
/// 查找第一个可印的字符串，如果找到则返回它的值，没找到返回空字符中。
/// </summary>
/// <returns></returns>
/// 创建时间： 2022-01-21 最后一次修改时间：2022-01-21
String^ FindFirstPrintableStringValue()
{
csharp_DListNode<String^>^ pNode = _First;
while (pNode != null)
{
if (gce::s_IsHavePrintableChar(pNode->Data))
{
return pNode->Data;
}
pNode = pNode->Next;
}
return "";
}
/// <summary>
/// 查找第一个可印的字符串的索引，如果找到则返回它的索引，没找到返回-1。
/// </summary>
/// <returns></returns>
/// 创建时间： 2022-01-21 最后一次修改时间：2022-01-21
int FindFirstPrintableStringIndex()
{
csharp_DListNode<String^>^ pNode = _First;
int nResult = 0;
while (pNode != null)
{
if (gce::s_IsHavePrintableChar(pNode->Data))
{
return nResult;
}
pNode = pNode->Next;
++nResult;
}
return -1;
}
/// <summary>
///
/// </summary>
/// <param name="ls"></param>
/// <returns></returns>
/// 创建时间： ????-??-?? 最后一次修改时间：2021-10-10
virtual bool Add(csharp_StringList^ ls)
{
csharp_DListNode<String^>^ pNode = ls->_First;
while (pNode != null)
{
Add(pNode->Data);
pNode = pNode->Next;
}
return true;
}
/// <summary>
/// 是开头插入一个字符串
/// </summary>
/// <param name="sItem"></param>
/// <returns></returns>
/// 创建时间： 2022-01-18 最后一次修改时间：2022-01-18
virtual bool InserFront(String^ sItem)
{
if (_Count == 0)
Add(sItem);
InserNodeFront(_First, sItem);
return true;
}
/// <summary>
/// 查找字符吕 S
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
/// <exception cref="Exception"></exception>
/// 创建时间： ????-??-?? 最后一次修改时间：2022-09-18
int IndexOf(String^ s)
{
//if(s->Length == 0){ throw gcnew Exception("字符串不能为空！");}
csharp_DListNode<String^>^ pNode = _First;
int iIndex = 0;
while (pNode != null)
{
if (pNode->Data == s)
{
return iIndex;
}
pNode = pNode->Next;
++iIndex;
}
return -1;
}
static csharp_StringList^ FromSplit(String^ sText, String^ sSplit) {
return gcnew csharp_StringList(sText, sSplit,true);
}
};
/// <summary>
/// 已排序好的字符串列表
/// </summary>
ref class csharp_SStringList : csharp_StringList
{
public:
csharp_SStringList(csharp_Sortord sortord)
{
if (sortord == csharp_Sortord::s_null)
{
throw gcnew System::Exception(L"排序不能为空！");
}
_sortord = sortord;
}
//-------------------------------------------------------------------------------重写
/// <summary>
/// 快速添加字符串，差不多用了8个小时(两天），才写成。
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
void Add(String^ item) override
{
if (Count < 3)
{
bool bInsett = false; csharp_DListNode<String^> ^ld = _First;
while (ld != null)
{
if (_sortord == csharp_Sortord::s_max_min)
{
if (item->CompareTo(ld->Data) >= 0)
{
csharp_StringList::InserNodeFront(ld, item); bInsett = true; break;
}
}
else
{
if (item->CompareTo(ld->Data) <= 0)
{
csharp_StringList::InserNodeFront(ld, item); bInsett = true; break;
}
}
ld = ld->Next;
}
if (!bInsett) csharp_StringList::Add(item);
return;
}
int nPos = Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = Count - 1; //右边远素
if (_sortord == csharp_Sortord::s_max_min)
{
csharp_DListNode<String^> ^ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNode(nPos);
if (item->CompareTo(ld->Data) >= 0)
{
if (nRight == nLeft || nPos == nLeft)
{
InserNodeFront(ld, item);
return;
}
nRight = nPos - 1;
}
else
{
if (nRight == nLeft || nPos == nRight)
{
InserNodeBack(ld, item);
return;
}
nLeft = nPos + 1;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
else
{
csharp_DListNode<String^> ^ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNode(nPos);
if (item->CompareTo(ld->Data) <= 0)
{
if (nRight == nLeft || nPos == nLeft)
{
InserNodeFront(ld, item);
return;
}
nRight = nPos - 1;
}
else
{
if (nRight == nLeft || nPos == nRight)
{
InserNodeBack(ld, item);
return;
}
nLeft = nPos + 1;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
return;
}
/// <summary>
/// 确定某元素是否在列表中
/// </summary>
/// <param name="item">查找的对象。对于引用类型，该值可以为 null。</param>
/// <returns>如果在列表中找到 item，则为 true，否则为 false。</returns>
bool Contains(String^ item) override
{
if (Count == 0) return false;
if (Count == 1) return First->Data->CompareTo(item) == 0;
if (Count == 2) return First->Data->CompareTo(item) == 0 || First->Next->Data->CompareTo(item) == 0;
int nPos = (int)Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)Count - 1; //右边远素
csharp_DListNode<String^>^ ld = null;
if (_sortord == csharp_Sortord::s_max_min)
{
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNode(nPos);
int iCom = item->CompareTo(ld->Data);
if (iCom > 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return false;
}
nRight = nPos - 1;
}
else if (iCom < 0)
{
if (nRight == nLeft || nPos == nRight)
{
return false;
}
nLeft = nPos + 1;
}
else
{
return true;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
else
{
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNode(nPos);
int iCom = item->CompareTo(ld->Data);
if (iCom < 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return false;
}
nRight = nPos - 1;
}
else if (iCom > 0)
{
if (nRight == nLeft || nPos == nRight)
{
return false;
}
nLeft = nPos + 1;
}
else
{
return true;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
return false;
}
};
/// <summary>
/// 值都是唯一的字符串列表
/// </summary>
/// <typeparam name="T"></typeparam>
ref class csharp_UStringList : csharp_StringList
{
public:
void Add(String^ item)override
{
if (BinarySearch(item) == -1)
csharp_StringList::Add(item);
}
void Add(array<String^>^ sArray)
{
for (int i = 0; i < sArray->Length; ++i)
{
Add(sArray[i]);
}
}
bool Add(csharp_StringList^ ls)override
{
bool bResult = true;
csharp_DListNode<String^> ^pFirst = ls->First;
while (pFirst != null)
{
if (BinarySearch(pFirst->Data) == -1)
{
csharp_StringList::Add(pFirst->Data);
}
else
{
bResult = false;
}
pFirst = pFirst->Next;
}
return bResult;
}
};
/// <summary>
/// 值都是唯一的字符串列表,且已排好序，区分大小写
/// </summary>
ref class csharp_SUStringList : csharp_SStringList
{
public:
void Add(String^ item)override
{
if (Contains(item))
return;
csharp_SStringList::Add(item);
}
csharp_SUStringList(csharp_Sortord sortord)
: csharp_SStringList(sortord)
{
}
};
/// <summary>
/// 值都是唯一的字符串列表， Case Insensitive(不区分大小写)
/// </summary>
ref class csharp_UStringListCI : csharp_StringList
{
public:
/// <summary>
/// 加入一个串，如果这个串存在，则把这项移到最后。
/// </summary>
/// <param name="item"></param>
/// 创建时间： ????-??-?? 最后一次修改时间：2022-02-18
void Add(String^ item)override
{
bool bFind = false;
csharp_DListNode<String^>^ dnTemp = _First;
while (dnTemp != null)
{
if (dnTemp->Data->ToLower() == item->ToLower())
{
MoveLast(dnTemp);
bFind = true;
break;
}
dnTemp = dnTemp->Next;
}
if (!bFind)
csharp_StringList::Add(item);
}
/// <summary>
/// 返回前面一个值
/// </summary>
/// <param name="tCurrValue"></param>
/// <returns></returns>
String^ GetForward(String^ sCurr)
{
int iIndex = BinarySearch(sCurr);
if (iIndex != -1)
{
if (iIndex + 1 < Count)
return this[iIndex + 1];
}
return null;
}
/// <summary>
/// 返回后面的一个值
/// </summary>
/// <param name="sCurr"></param>
/// <returns></returns>
String^ GetBack(String^ sCurr)
{
int iIndex = BinarySearch(sCurr);
if (iIndex != -1)
{
if (iIndex - 1 < Count && iIndex - 1 >= 0)
return this[iIndex - 1];
}
return null;
}
};
/// <summary>
/// UStringListCI_值都是唯一,且已排序的字符串列表，不区分大小写
/// </summary>
ref class csharp_SUStringListUI : csharp_SUStringList
{
public:
csharp_SUStringListUI(csharp_Sortord sortord) : csharp_SUStringList(sortord)
{
}
/// <summary>
/// 确定某元素是否在列表中
/// </summary>
/// <param name="item">查找的对象。对于引用类型，该值可以为 null。</param>
/// <returns>如果在列表中找到 item，则为 true，否则为 false。</returns>
bool Contains(String^ item) override
{
if (Count == 0) return false;
if (Count == 1) return First->Data->ToLower()->CompareTo(item->ToLower()) == 0;
if (Count == 2) return First->Data->ToLower()->CompareTo(item->ToLower()) == 0 || First->Next->Data->ToLower()->CompareTo(item->ToLower()) == 0;
int nPos = (int)Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)Count - 1; //右边远素
csharp_DListNode<String^>^ ld = null;
if (_sortord == csharp_Sortord::s_max_min)
{
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNode(nPos);
int iCom = item->ToLower()->CompareTo(ld->Data->ToLower());
if (iCom > 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return false;
}
nRight = nPos - 1;
}
else if (iCom < 0)
{
if (nRight == nLeft || nPos == nRight)
{
return false;
}
nLeft = nPos + 1;
}
else
{
return true;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
else
{
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNode(nPos);
int iCom = item->ToLower()->CompareTo(ld->Data->ToLower());
if (iCom < 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return false;
}
nRight = nPos - 1;
}
else if (iCom > 0)
{
if (nRight == nLeft || nPos == nRight)
{
return false;
}
nLeft = nPos + 1;
}
else
{
return true;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
return false;
}
};
/// <summary>
/// 历史记录，相当于栈
/// </summary>
/// <typeparam name="T"></typeparam>
/// 创建时间：2022-03-06 最后一次修改时间：2022-04-19
template <class T>
ref class csharp_UniqueStack
{
private:
csharp_DList<T>^ m_List;
/// <summary>
/// 元素容量
/// </summary>
int m_Capacity;
public:
property csharp_DList<T>^ List {
csharp_DList<T>^ get() {
return m_List;
}
}
property int Capacity{
int get() {
return m_Capacity;
}
}
/// <summary>
/// 无素个数
/// </summary>
property int Count {
int get() {
return m_List->Count;
}
}
csharp_UniqueStack(int nCapacity)
{
if (nCapacity <= 0)
{
throw gcnew System::Exception(L"容量不能小于等于 0 ！");
m_Capacity = 15;
}
else
{
m_Capacity = nCapacity;
}
m_List = gcnew csharp_DList<T>();
}
/// <summary>
/// 添加一项
/// </summary>
/// <param name="item"></param>
/// 创建时间： 2022-04-19 最后一次修改时间：2022-04-19
void Push(T item)
{
bool bFind = m_List->RemoveItem(item); //如果找到，则删除
if (!bFind)
{
if (m_List->Count < m_Capacity)
{
m_List->StackPush(item,false);
}
else
{
//插入一个Item，所有元素后移一位
m_List->StackPush(item, true);
}
}
else
{
//插入一个Item，所有元素后移一位
m_List->StackPush(item, true);
}
}
/// <summary>
/// 出栈
/// </summary>
void Pop() { List->StackPop(); }
};
ref class csharp_HistoryStringList : csharp_UniqueStack<String^>
{
public:
String^ ToString()override
{
String^ sResult = "";
for each(String ^s in List)
{
sResult += s + "||";
}
if (sResult != "")
{
sResult = sResult->Substring(0, sResult->Length - 2);
}
return sResult;
}
void FromString(String^ sVaule)
{
List->Clear();
csharp_StringList ^ls = gcnew csharp_StringList(sVaule,"||",false);
csharp_DListNode<String^> ^dnNode = ls->Last;
while (dnNode != null) {
Push(dnNode->Data);
dnNode = dnNode->Prev;
}
}
csharp_HistoryStringList(int nCapacity) : csharp_UniqueStack(nCapacity) { }
};
ref class csharp_HistoryStringListPair : csharp_UniqueStack<csharp_Pair<String^, String^>^>
{
public:
String^ ToString()override
{
String^ sResult = L"";
for each(csharp_Pair<String^, String^> ^pair in List)
{
sResult += (String^)pair->First + L"," + (String^)pair->Second + L"||";
}
if (sResult != "")
{
sResult = sResult->Substring(0, sResult->Length - 2);
}
return sResult;
}
void FromString(String^ sVaule)
{
List->Clear();
csharp_StringList ^ls1 = gcnew csharp_StringList(sVaule,"||",false);
csharp_DListNode<String^> ^dnNode = ls1->Last;
while (dnNode != null)
{
csharp_StringList^ ls2 = gcnew csharp_StringList(dnNode->Data, L",", false);
if (ls2->Count == 2)
{
Push(ls2[0], ls2[1]);
}
dnNode = dnNode->Prev;
}
}
csharp_HistoryStringListPair(int nCapacity) : csharp_UniqueStack(nCapacity) { }
void Push(String^ s1, String^ s2) { csharp_UniqueStack<csharp_Pair<String^, String^>^>::Push( gcnew csharp_Pair<String^, String^>(s1, s2)); }
csharp_Pair<String^, String^>^ IndexOfFirst(String^ sFirst)
{
for each(csharp_Pair<String^, String^> ^pair in List)
{
if (pair->First == sFirst)
return pair;
}
return null;
}
csharp_Pair<String^, String^> ^IndexOfSecond(String^ sSecond)
{
for each (csharp_Pair<String^, String^> ^pair in List)
{
if (pair->Second == sSecond)
return pair;
}
return null;
}
};
template<class T1, class T2>
ref class csharp_PairList : System::Collections::IEnumerable
{
public:
csharp_DList< csharp_Pair<T1, T2>^ > ^m_list;
property csharp_DList<csharp_Pair<T1, T2>^>^ List{
csharp_DList<csharp_Pair<T1, T2>^>^ get() { return m_list; }
}
csharp_PairList()
{
m_list = gcnew csharp_DList<csharp_Pair<T1, T2>^>();
}
csharp_Pair<T1, T2> ^GetIndex(int iIndex)
{
csharp_DListNode<csharp_Pair<T1, T2>^> ^dn = m_list->IndexOfNode(iIndex);
if (dn == null)
return null;
else
return dn->Data;
}
void RemoveAt(int iIndex)
{
m_list->RemoveAt(iIndex);
}
void Clear()
{
m_list->Clear();
}
void Add(T1 First, T2 Second)
{
m_list->Add(gcnew csharp_Pair<T1, T2>(First, Second));
}
void Add(csharp_Pair<T1, T2> ^p)
{
m_list->Add(p);
}
void CopyTo(System::Collections::IList^ il1, System::Collections::IList^ il2)
{
il1->Clear();
il2->Clear();
for each(csharp_DListNode< csharp_Pair<T1, T2>^> ^dn in m_list)
{
il1->Add(dn->Data->First);
il2->Add(dn->Data->First);
}
}
property int Count{ int get() { return m_list->Count; } }
/// <summary>
/// 创建时间： ????-??-?? 最后一次修改时间：2020-05-31
/// 查找sFirstStringValue,找不到返回NULL
/// </summary>
/// <param name="sFirst"></param>
/// <returns></returns>
csharp_Pair<T1, T2>^ IndexFirst(T1 sFirstStringValue)
{
for each(csharp_Pair<T1, T2>^ p in m_list)
{
if ( p->First == sFirstStringValue)
return p;
}
return null;
}
/// <summary>
/// 创建时间： ????-??-?? 最后一次修改时间：2020-05-31
/// 查找sSecondStringValue,找不到返回NULL
/// </summary>
/// <param name="sFirst"></param>
/// <returns></returns>
csharp_Pair<T1, T2> ^IndexSecond(T2 sSecondStringValue)
{
for each(csharp_Pair<T1, T2>^ p in m_list)
{
if (p.Second.Equals(sSecondStringValue))
return p;
}
return null;
}
/// <summary>
/// 创建时间： 2020-05-31 最后一次修改时间：2020-05-31
/// 查找第一项，找到返回第二项的值，没找到返回第二项的默认值。
/// </summary>
/// <param name="sFirstStringValue"></param>
/// <returns></returns>
T2 IndexFirstValue(T1 sFirstStringValue)
{
for each(csharp_Pair<T1, T2> ^p in m_list)
{
if (p.First.Equals(sFirstStringValue))
return p.Second;
}
return default(T2);
}
/// <summary>
/// 创建时间： 2020-05-31 最后一次修改时间：2020-05-31
/// 查找第三项，找到返回第一项的值，没找到返回第一项的默认值。
/// </summary>
/// <param name="sSecondStringValue"></param>
/// <returns></returns>
T1 IndexSecondValue(T2 sSecondStringValue)
{
for each(csharp_Pair<T1, T2> ^p in m_list)
{
if (p.Second.Equals(sSecondStringValue))
return p.First;
}
return default(T1);
}
virtual System::Collections::IEnumerator ^GetEnumerator()
{
return m_list->GetEnumerator();
}
};
ref class csharp_StringPairList : csharp_PairList<String^, String^>
{
public:
/// <summary>
/// 依据slFirst查找Second
/// </summary>
/// <param name="slFirst"></param>
/// 创建时间：2020-05-09 最后一次修改时间：2020-05-09
/// <returns></returns>
csharp_StringList^ GetSecondList(csharp_StringList^ slFirst)
{
csharp_StringList ^slResult = gcnew csharp_StringList();
for each(csharp_Pair<String^, String^> ^p in this)
{
if (slFirst->FindNodeItem(p->First) != null)
{
slResult->Add(p->Second);
}
}
return slResult;
}
/// <summary>
/// 依据slSecond查找First
/// </summary>
/// <param name="slSecond"></param>
/// 创建时间：2020-05-09 最后一次修改时间：2020-05-09
/// <returns></returns>
csharp_StringList ^GetFirstList(csharp_StringList ^slSecond)
{
csharp_StringList ^slResult = gcnew csharp_StringList();
for each(csharp_Pair<String^, String^> ^p in this)
{
if (slSecond->FindNodeItem(p->Second) != null)
{
slResult->Add(p->First);
}
}
return slResult;
}
virtual System::Collections::IEnumerator^ GetEnumerator() override
{
return m_list->GetEnumerator();
}
};
_LF_END_
#endif
C#
/*****************************************************************************
创建时间 : 2006年12月19日
文件名 ： List_.cs
作者 ： 李锋
Email : ruizhilf@139.com
联系电话 : 13828778863,25722732
－－－－－－－－－－－－－－－－－－－－－－最后一次修改时间：2022年10月10日
*******************************************************************************/
using System;
using System.Collections.Generic;
using System.Collections;
using System.Text.RegularExpressions;
using System.IO;
using System.Diagnostics;
namespace lf
{
#region DListNode_(双向链表的节点)
/// <summary>
/// 双向链表的节点
/// </summary>
/// <typeparam name="T"></typeparam>
public class DListNode_<T>
{
/// <summary>
/// 节点数据
/// </summary>
public T Data;
/// <summary>
/// 前一个节点
/// </summary>
public DListNode_<T> Prev;
/// <summary>
/// 下一个节点
/// </summary>
public DListNode_<T> Next;
public DListNode_(T aData)
{
Data = aData;
Prev = null;
Next = null;
}
}
#endregion
#region Sortord_( 排序方式)
/// <summary>
/// 排序顺序
/// </summary>
public enum Sortord_
{
s_min_max, //从小到大
s_max_min, //从大到小
s_null //无排序顺序
}
#endregion
#region //====================================================== DList_(双向链表)
/// <summary>
/// 双向链表
/// </summary>
/// <typeparam name="T"></typeparam>
public class DList_<T> : IEnumerable
{
protected DListNode_<T> _First; //第一个节点
protected DListNode_<T> _Last; //最后一个节点
protected int _Count; //节点个数
protected Sortord_ _sortord; //排序顺序
//------------------------------------------------------------------------------------------属性
/// <summary>
/// 实际包含的元素数
/// </summary>
public int Count
{
get
{
return _Count;
}
}
/// <summary>
/// 获取或设置指定索引处的元素
/// </summary>
/// <param name="index">要获得或设置的元素从零开始的索引</param>
/// <returns>指定索引处的元素</returns>
public virtual T this[int index]
{
get
{
return IndexOfNote(index).Data;
}
set
{
IndexOfNote(index).Data = value;
}
}
//---------------------------------------------------------------------------------构造与析构
//---------------------------------------------------------------------------------运算符重载
/// <summary>
///
/// </summary>
/// <param name="dLeft"></param>
/// <param name="dlRight"></param>
/// <returns></returns>
/// 创建时间： 2021-11-07 最后一次修改时间：2021-11-07
public static DList_<T> operator +(DList_<T> dLeft, DList_<T> dlRight)
{
/*
DList_<T> dlResult = new DList_<T> ();
dlResult.Add(dLeft);
dlResult.Add(dlRight);
return dlResult;
*/
return new DList_<T> { dLeft, dlRight };
}
//---------------------------------------------------------------------------------功能函数
/// <summary>
/// 将指定集合的元素添加到末尾
/// </summary>
/// <param name="item">要添加到的末尾处的对象。对于引用类型，该值可以为 null</param>
/// <returns>如成功，返回真，否则返回假</returns>
public virtual void Add(T item)
{
if (_Count == 0)
{
_First = new DListNode_<T>(item);
_First.Next = null;
_First.Prev = null;
_Last = _First;
}
else
{
DListNode_<T> pNew = new DListNode_<T>(item);
pNew.Next = null;
pNew.Prev = _Last;
_Last.Next = pNew;
_Last = pNew;
}
++_Count;
_sortord = Sortord_.s_null; //要重新排序
}
/// <summary>
///
/// </summary>
/// <param name="nIndex"></param>
/// <param name="item"></param>
/// <returns></returns>
/// 创建时间： 2022-08-11 最后一次修改时间：2022-08-12
public virtual void Insert(int nIndex, T item)
{
if ((uint)nIndex > (uint)_Count)
{
throw new Exception("DList_.Insert 插入位置错误！");
}
if (nIndex == 0)
{
if(_First != null)
{
DListNode_<T> dnNew = new DListNode_<T>(item);
_First.Prev = dnNew;
dnNew.Next = _First;
_First = dnNew;
++_Count;
_sortord = Sortord_.s_null;
}
else
{
Add(item);
}
}
else if(nIndex == _Count)
{
Add(item);
}
else
{
DListNode_<T> dnNew = new DListNode_<T>(item);
DListNode_<T> dnNext = IndexOfNote(nIndex);
DListNode_<T> dnPrev = dnNext.Prev;
dnNew.Next = dnNext;
dnNew.Prev = dnPrev;
dnNext.Prev = dnNew;
dnPrev.Next = dnNew;
++_Count;
_sortord = Sortord_.s_null;
}
}
public void Add(DList_<T> dList)
{
if (dList == null)
{
throw new System.Exception("DList_<T>.Add中参数dList==null");
}
DListNode_<T> ld = dList._First;
while (ld != null)
{
Add(ld.Data);
ld = ld.Next;
}
}
public override string ToString()
{
string sResult = "";
DListNode_<T> dnNode = _First;
while (dnNode != null)
{
sResult += dnNode.Data.ToString();
sResult += "\n";
dnNode = dnNode.Next;
}
return sResult;
}
public string ToString(string sSplit)
{
string sResult = "";
DListNode_<T> dnNode = _First;
while (dnNode != null)
{
sResult += dnNode.Data.ToString();
if(dnNode != Last)
sResult += sSplit;
dnNode = dnNode.Next;
}
return sResult;
}
/// <summary>
/// 使用指定的比较器在整个已排序的 中搜索元素，并返回该元素从零开始的索引
/// </summary>
/// <param name="item">要定位的对象。对于引用类型，该值可以为 null。</param>
/// <returns>如果找到 item，则为已排序的 的从零开始的索引；否则为-1; </returns>
public int BinarySearch(T item)
{
switch (_sortord)
{
case Sortord_.s_max_min:
{
if (Count == 0)
{
return -1;
}
if (Count == 1)
{
return (_First.Data as IComparable).CompareTo(item) == 0 ? 0 : -1;
}
if (Count == 2)
{
if( (_First.Data as IComparable).CompareTo(item) == 0) return 0;
if ((_First.Next.Data as IComparable).CompareTo(item) == 0) return 1;
return -1;
}
int nPos = (int)Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)Count - 1; //右边远素
DListNode_<T> ld;
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNote(nPos);
int iCom = (item as IComparable).CompareTo(ld.Data);
if (iCom > 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return -1;
}
nRight = nPos - 1;
}
else if (iCom < 0)
{
if (nRight == nLeft || nPos == nRight)
{
return -1;
}
nLeft = nPos + 1;
}
else
{
return nPos;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case Sortord_.s_min_max:
{
if (Count == 0)
{
return -1;
}
if (Count == 1)
{
return (_First.Data as IComparable).CompareTo(item) == 0 ? 0 : -1;
}
if (Count == 2)
{
if ((_First.Data as IComparable).CompareTo(item) == 0) return 0;
if ((_First.Next.Data as IComparable).CompareTo(item) == 0) return 1;
return -1;
}
int nPos = (int)Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)Count - 1; //右边远素
DListNode_<T> ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNote(nPos);
int iCom = (item as IComparable).CompareTo(ld.Data);
if (iCom < 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return -1;
}
nRight = nPos - 1;
}
else if (iCom > 0)
{
if (nRight == nLeft || nPos == nRight)
{
return -1;
}
nLeft = nPos + 1;
}
else
{
return nPos;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case Sortord_.s_null:
{
DListNode_<T> pNote = _First;
int iCount = 0;
while (pNote != null)
{
if (pNote.Data.Equals(item))
{
return iCount;
}
pNote = pNote.Next;
++iCount;
}
break;
}
default:
{
return -1;
}
}
return -1;
}
/**
* 功能：清空所有元素的所有数据，并清空链表
* 创建时间：????/??/??
* 最后一次修改时间：2022-07-02
*/
public void Clear()
{
_Count = 0;
DListNode_<T> pTemp1 = _First;
while (pTemp1 != null)
{
DListNode_<T> pTemp2 = pTemp1.Next;
pTemp1.Data = default(T);
pTemp1.Next = null;
pTemp1.Prev = null;
pTemp1 = pTemp2;
}
_First = null;
_Last = null;
}
/// <summary>
/// 确定某元素是否在列表中
/// </summary>
/// <param name="item">查找的对象。对于引用类型，该值可以为 null。</param>
/// <returns>如果在列表中找到 item，则为 true，否则为 false。</returns>
public virtual bool Contains(T item)
{
return BinarySearch(item) != -1;
}
/// <summary>
/// 复制一个链表，清除原来链表的数据
/// </summary>
/// <param name="ld"></param>
public void CopyFrom(DList_<T> ld)
{
if (!this.Equals(ld))
{
Clear();
DListNode_<T> ldItem = ld._First;
while (ldItem != null)
{
Add(ldItem.Data);
ldItem = ldItem.Next;
}
}
}
/*
public int IndexOf(T item)
{
return -1;
}
public int IndexOf(T item, int index)
{
return -1;
}
public void Insert(int index, T item)
{
}
public int LastIndexOf(T item)
{
return -1;
}
public int LastIndexOf(T item, int index, int Count)
{
return -1;
}
*/
/// <summary>
/// 移除指定索引处的元素
/// </summary>
/// <param name="iIndex">要移除的元素的从零开始的索引。</param>
/// <returns>成功返回true,否则返回false</returns>
public bool RemoveAt(int iIndex)
{
if (iIndex < 0 || iIndex + 1 > _Count) { return false; }
DListNode_<T> pNode = _First;
int iCount = 0;
while (pNode != null)
{
if (iCount == iIndex)
{
if (pNode == _First)
{
if (_First.Next == null) //只有一个
{
Clear();
return true;
}
else
{
_First = _First.Next;
_First.Prev = null;
--_Count;
return true;
}
}
else if (pNode == _Last)
{
if (_Last.Prev == null)
{
Clear();
return true;
}
else
{
_Last = _Last.Prev;
_Last.Next = null;
--_Count;
return true;
}
}
else
{
pNode.Prev.Next = pNode.Next;
pNode.Next.Prev = pNode.Prev;
pNode = null;
--_Count;
return true;
}
}
pNode = pNode.Next;
++iCount;
}
return false;
}
/// <summary>
/// 反向排列链表
/// </summary>
/// 创建时间： 2022-04-20 最后一次修改时间：2022-04-20
public virtual void Reverse()
{
DListNode_<T> dnTemp = First;
while(dnTemp != null)
{
LMath.Swap(ref dnTemp.Next, ref dnTemp.Prev);
dnTemp = dnTemp.Prev;
}
LMath.Swap(ref _First, ref _Last);
}
/// <summary>
/// 添加一个元素，并把它放在首位，其它元素后移,如棵后面的元素删除，总无素个数不变，如果无素个数为零，则添加一个无素。
/// </summary>
/// <param name="Item"></param>
/// <param name="bRemoveLast"></param>
/// 创建时间： 2022-04-19 最后一次修改时间：2022-04-19
public void StackPush(T Item, bool bRemoveLast = false){
if (_Count == 0){
Add(Item);
}
else if (_Count == 1){
if (bRemoveLast){
_First.Data = Item;
}
else{
//把无素放在最前
DListNode_<T> dnNew = new DListNode_<T>(Item);
_First.Prev = dnNew;
dnNew.Next = _First;
_First = dnNew;
++_Count;
}
}
else{
if (bRemoveLast){
//删除最后一个元素
_Last = _Last.Prev;
_Last.Next = null;
//把无素放在最前
DListNode_<T> dnNew = new DListNode_<T>(Item);
_First.Prev = dnNew;
dnNew.Next = _First;
dnNew.Prev = null;
_First = dnNew;
}
else {
//把无素放在最前
DListNode_<T> dnNew = new DListNode_<T>(Item);
_First.Prev = dnNew;
dnNew.Next = _First;
dnNew.Prev = null;
_First = dnNew;
++_Count;
}
}
}
/// <summary>
/// 删除第一个元素，出栈
/// </summary>
/// 创建时间： 2022-04-19 最后一次修改时间：2022-04-19
public void StackPop(){ RemoveAt(0); }
/// <summary>
/// 转换成数组
/// </summary>
/// <returns></returns>
public T[] ToArray()
{
T[] aResult = new T[Count];
int n = 0;
DListNode_<T> pNoteTemp = _First;
while (pNoteTemp != null)
{
aResult[n++] = pNoteTemp.Data;
pNoteTemp = pNoteTemp.Next;
}
return aResult;
}
/// <summary>
/// 交换两个节点的数据
/// </summary>
/// <param name="nIndex1"></param>
/// <param name="nIndex2"></param>
/// <returns></returns>
protected virtual bool swapNoteData(int iIndex1, int iIndex2)
{
DListNode_<T> pNote1, pNote2;
pNote1 = IndexOfNote(iIndex1);
pNote2 = IndexOfNote(iIndex2);
if (!(pNote1 != null && pNote2 != null))
{
return false;
}
T ptmp = pNote1.Data;
pNote1.Data = pNote2.Data;
pNote2.Data = ptmp;
return true;
}
/// <summary>
/// 选择排序可以说是最简单的一种排序方法：
/// 1.找到数组中最小的那个元素
/// 2.将最小的这个元素和数组中第一个元素交换位置
/// 3.在剩下的元素中找到最小的的元素，与数组第二个元素交换位置
/// 重复以上步骤，即可以得到有序数组。
/// </summary>
public virtual void sort_selection(Sortord_ sortord)
{
if (_Count == 0 || _Count == 1) return;
//is关键字用于检查对象是否与给定类型兼容。注意了，这里is并不是“是”的意思，而是“兼容”。
if (!(_First.Data is IComparable)) // 判断是否具有IComparable接口，以确定是否存在CompareTo()方法
{
throw new Exception("没有IComparable接口");
}
DListNode_<T> min = _First, tmp = _First.Next;
if (sortord == Sortord_.s_min_max)
{
while (min.Next != null)
{
while (tmp != null)
{
if ((tmp.Data as IComparable).CompareTo(min.Data) < 0) //交换位置
{
T pt = tmp.Data;
tmp.Data = min.Data;
min.Data = pt;
}
tmp = tmp.Next;
}
min = min.Next;
tmp = min.Next;
}
}
else
{
while (min.Next != null)
{
while (tmp != null)
{
if ((tmp.Data as IComparable).CompareTo(min.Data) > 0)
{
T pt = tmp.Data;
tmp.Data = min.Data;
min.Data = pt;
}
tmp = tmp.Next;
}
min = min.Next;
tmp = min.Next;
}
}
_sortord = sortord; //已排序
}
/// <summary>
/// 返回索引的节点,从零开始
/// </summary>
/// <param name="nPos"></param>
/// <returns></returns>
public virtual DListNode_<T> IndexOfNote(int iPos)
{
if (iPos >= _Count || iPos < 0) throw new System.Exception("DListNode_<T>.IndexOfNote 错误索引: " + iPos.ToString() + "！");
uint nindex = 0;
if (iPos > _Count / 2)
{
DListNode_<T> pNote = _Last;
while (pNote != null)
{
if (nindex++ == _Count - iPos - 1){ return pNote;}
pNote = pNote.Prev;
}
}
else
{
DListNode_<T> pNote = _First;
while (pNote != null)
{
if (nindex++ == iPos)
{
return pNote;
}
pNote = pNote.Next;
}
}
return null;
}
/// <summary>
/// 在结点pListItem前面插入一个结点,成功，返回新的结点，否则返回０
/// </summary>
/// <param name="pListItem"></param>
/// <param name="pData"></param>
/// <returns></returns>
protected virtual DListNode_<T> InserNoteFront(DListNode_<T> pListItem, T pData)
{
if (pListItem == null)
{
throw new System.Exception("函数提示：pListItem = null");
}
DListNode_<T> pNote = new DListNode_<T>(pData);
//pNote
pNote.Next = pListItem;
pNote.Prev = pListItem.Prev;
//--pListItem->Prev
if (pListItem.Prev != null)
{
pListItem.Prev.Next = pNote;
}
else
{
_First = pNote;
}
//pListItem
pListItem.Prev = pNote;
++_Count;
return pNote;
}
/// <summary>
/// 在结点pListItem后面插入一个结点,成功，返回新的结点，否则返回０；
/// </summary>
/// <param name="pListItem"></param>
/// <param name="pData"></param>
/// <returns></returns>
protected virtual DListNode_<T> InserNoteBack(DListNode_<T> pListItem, T pData)
{
if (pListItem == null) return null;
DListNode_<T> pNote = new DListNode_<T>(pData);
//pNote
pNote.Prev = pListItem;
pNote.Next = pListItem.Next;
//pListItem->Next
if (pListItem.Next != null)
{
pListItem.Next.Prev = pNote;
}
else
{
_Last = pNote;
}
//--pListItem
pListItem.Next = pNote;
++_Count;
return pNote;
}
/// <summary>
/// 找查一个项，而不是节点，返回的这个节点相当于指针。
/// </summary>
/// <param name="pData">项值</param>
/// <returns></returns>
public DListNode_<T> FindNodeItem(T item)
{
switch (_sortord)
{
case Sortord_.s_max_min:
{
if (Count == 0)
{
return null;
}
if (Count == 1)
{
return (_First.Data as IComparable).CompareTo(item) == 0 ? _First : null;
}
if (Count == 2)
{
if ((_First.Data as IComparable).CompareTo(item) == 0) return _First;
if ((_First.Next.Data as IComparable).CompareTo(item) == 0) return _First.Next;
return null;
}
int nPos = (int)Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)Count - 1; //右边远素
DListNode_<T> ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNote(nPos);
int iCom = (item as IComparable).CompareTo(ld.Data);
if (iCom > 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return null;
}
nRight = nPos - 1;
}
else if (iCom < 0)
{
if (nRight == nLeft || nPos == nRight)
{
return null;
}
nLeft = nPos + 1;
}
else
{
return ld;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case Sortord_.s_min_max:
{
if (Count == 0)
{
return null;
}
if (Count == 1)
{
return (_First.Data as IComparable).CompareTo(item) == 0 ? _First : null;
}
if (Count == 2)
{
if ((_First.Data as IComparable).CompareTo(item) == 0) return _First;
if ((_First.Next.Data as IComparable).CompareTo(item) == 0) return _First.Next;
return null;
}
int nPos = (int)Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)Count - 1; //右边远素
DListNode_<T> ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNote(nPos);
int iCom = (item as IComparable).CompareTo(ld.Data);
if (iCom < 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return null;
}
nRight = nPos - 1;
}
else if (iCom > 0)
{
if (nRight == nLeft || nPos == nRight)
{
return null;
}
nLeft = nPos + 1;
}
else
{
return ld;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case Sortord_.s_null:
{
DListNode_<T> pNote = _First;
while (pNote != null)
{
//总结:Equals比较的永远是变量的内容是否相同，而= =比较的则是引用地址是否相同(前提:此种类型内部没有对Equals 或= = 进行重写操作，
//否则输出可能会有不同)。string 类型是个特例，因为他的内部对这两个都进行了重写。
if ((item as IComparable).CompareTo(pNote.Data) == 0)
{
return pNote;
}
/*
if (pNote.Data.Equals(item))
{
return pNote;
}
*/
pNote = pNote.Next;
}
break;
}
default:
{
return null;
}
}
return null;
}
/// <summary>
/// 把索引为nIndex的节点移到最后
/// </summary>
/// <param name="nIndex"></param>
/// <returns></returns>
protected virtual bool MoveLast(int iIndex)
{
DListNode_<T> pNote = IndexOfNote(iIndex);
if (pNote != null)
{
if (pNote == _Last)
return true;
if (pNote == _First) //此时最少两个节点
{
_First = _First.Next;
_First.Prev = null;
_Last.Next = pNote;
pNote.Prev = _Last;
_Last = pNote;
}
else
{
pNote.Prev.Next = pNote.Next;
pNote.Next.Prev = pNote.Prev;
_Last.Next = pNote;
pNote.Prev = _Last;
_Last = pNote;
}
return true;
}
return false;
}
/// <summary>
///
/// </summary>
/// <param name="dnCurrent"></param>
/// <returns></returns>
/// 创建时间： 2022-02-18 最后一次修改时间：2022-02-18
protected virtual bool MoveLast(DListNode_<T> dnCurrent)
{
if (dnCurrent == null) return false;
_sortord = Sortord_.s_null;
if(_Count == 0)
{
return false;
}
else if(_Count == 1)
{
return true;
}
else if(_Count == 2)
{
if(dnCurrent == _First) //交换_First 与 _Last 数据
{
T tmp = _First.Data;
_First.Data = _Last.Data;
_Last.Data = tmp;
}
return true;
}
else
{
if (dnCurrent == _First)
{
_First = _First.Next;
_First.Prev = null;
_Last.Next = dnCurrent;
dnCurrent.Next = null;
dnCurrent.Prev = _Last;
_Last = dnCurrent;
}
else if (dnCurrent != _Last)
{
dnCurrent.Prev.Next = dnCurrent.Next;
dnCurrent.Next.Prev = dnCurrent.Prev;
_Last.Next = dnCurrent;
dnCurrent.Next = null;
dnCurrent.Prev = _Last;
_Last = dnCurrent;
}
return true;
}
}
/// <summary>
/// 把索引为nIndex的节点移到最前
/// </summary>
/// <param name="nIndex"></param>
/// <returns></returns>
protected virtual bool MoveFirst(int iIndex)
{
DListNode_<T> pNote = IndexOfNote(iIndex);
if (pNote != null)
{
if (pNote == _First)
return true;
if (pNote == _Last) //此时最少两个节点
{
_Last.Prev.Next = null;
_Last = _Last.Prev;
pNote.Prev = null;
pNote.Next = _First;
_First.Prev = pNote;
_First = pNote;
}
else
{
pNote.Prev.Next = pNote.Next;
pNote.Next.Prev = pNote.Prev;
pNote.Next = _First;
_First.Prev = pNote;
pNote.Prev = null;
_First = pNote;
}
return true;
}
return false;
}
/// <summary>
/// 返回第一个节点
/// </summary>
public DListNode_<T> First
{
get
{
return _First;
}
}
/// <summary>
/// 返回最后一个节点
/// </summary>
public DListNode_<T> Last
{
get { return _Last; }
}
//--------------------------------------------------------------------------------------
/// <summary>
/// 构造函数
/// </summary>
public DList_()
{
_Count = 0; _First = null; _Last = null;
_sortord = Sortord_.s_null;
}
/// <summary>
/// 删除链表中的数据
/// </summary>
/// <param name="pData"></param>
/// <returns></returns>
public bool RemoveItem(T pData)
{
if (_sortord == Sortord_.s_null)
{
DListNode_<T> pListItem = _First;
while (pListItem != null)
{
if (pListItem.Data.Equals(pData)) //找到一项
{
if (pListItem == _First) //删除的是第一个节点
{
if (_First.Next != null)
{
_First.Next.Prev = null;
_First = _First.Next;
}
else
{
_First = null;
_Last = null;
}
}
else if (pListItem == _Last) //删除的是最后一个节点
{
if (_Last.Prev != null)
{
_Last.Prev.Next = null;
_Last = _Last.Prev;
}
else
{
_First = null;
_Last = null;
}
}
else //删除的是中间的一个节点
{
pListItem.Next.Prev = pListItem.Prev;
pListItem.Prev.Next = pListItem.Next;
}
--_Count;
return true;
}
pListItem = pListItem.Next;
}
return false;
}
else
{
return RemoveAt(BinarySearch(pData));
}
}
/// <summary>
/// 删除链表中的节点
/// </summary>
/// <param name="pListItem"></param>
/// <returns></returns>
public bool DeleteNode(DListNode_<T> pListItem)
{
if (_Count == 0 || pListItem == null)
{
return false;
}
DListNode_<T> pNote = _First.Next;
while (pNote != null)
{
if (pNote == pListItem) //找到了
{
//pListItem->Prev
if (pListItem.Prev != null)
{
pListItem.Prev.Next = pListItem.Next;
}
else //删除的是第一个节点
{
_First = pListItem.Next;
}
//pListItem->Next
if (pListItem.Next != null)
{
pListItem.Next.Prev = pListItem.Prev;
}
else //删除的是最后一个节点
{
_Last = pListItem.Prev;
}
break;
}
pNote = pNote.Next;
}
if (pNote != null)
{
--_Count;
return true;
}
return false;
}
/// <summary>
/// 删除最后一个节点
/// </summary>
/// 创建时间：2020-09-12 最后一次修改时间： 2020-09-12
public bool DeleteLast()
{
if (_Count <= 0)
{
return false;
}
else if (_Count == 1)
{
_First = null;
_Last = null;
_Count = 0;
return true;
}
else if(_Count == 2)
{
_Last = _First;
_Last.Prev = null;
_Last.Next = null;
_First.Next = null;
_First.Prev = null;
--_Count;
}
else
{
_Last.Prev.Next = null;
_Last = _Last.Prev;
--_Count;
}
return true; ;
}
//--------------------------------------------------------------------------接口
/// <summary>
//示例为了使一个类支持集合初始化器，它必须实现IEnumerable接口并至少具有一个Add方法。从C＃6开始，
//IEnumerable可以Add使用扩展方法使用自定义方法扩展任何实现的集合。
/// </summary>
/// 创建时间：2020-05-07 最后一次修改时间： 2020-05-07
/// <returns></returns>
public IEnumerator GetEnumerator()
{
return new DListNoteEnum_<T>(_First);
}
}
/// <summary>
/// 节点数据的foreach迭代
/// </summary>
/// 创建时间：2020-05-07 最后一次修改时间： 2022-10-10
/// <typeparam name="T"></typeparam>
public class DListNoteEnum_<T> : IEnumerator
{
private DListNode_<T> _dn;
private DListNode_<T> _dnCurr;
private int _iIndex;
public DListNoteEnum_(DListNode_<T> dn)
{
_dn = dn;
_iIndex = -1;
}
/// <summary>
/// IEnumerator最终调用的是这个函数访问
/// </summary>
public Object Current { get{ return _dnCurr.Data; } }
public virtual bool MoveNext()
{
++_iIndex; //指针首先向前移动一位
if (_dnCurr == null)
{
_dnCurr = _dn;
}
else
{
_dnCurr = _dnCurr.Next;
}
return _dnCurr != null;
}
public virtual void Reset()
{
_dnCurr = null;
_iIndex = -1;
}
};
#endregion
#region//====================================================== SortList_ 已排序的链表
/// <summary>
/// 已排序的链表
/// </summary>
/// <typeparam name="T"></typeparam>
public class SortList_<T> : DList_<T>
{
public SortList_(Sortord_ sortord)
{
_sortord = sortord;
}
//-------------------------------------------------------------------------------重写
/// <summary>
/// 添加一项到结尾处，item不能为NULL.
/// </summary>
/// <param name="item">项</param>
/// 创建时间： ????-??-?? 最后一次修改时间：2021-11-07
public override void Add(T item)
{
if (item == null)
{
throw new System.Exception("SortList_.Add 方法提示：类型值不能为null！");
}
if ( !(item is IComparable) ) // 判断是否具有IComparable接口，以确定是否存在CompareTo()方法
{
throw new System.Exception("SortList_<" + item.GetType().Name + ">.Add 方法提示：类型“" + item.GetType().Name + "”没有IComparable接口！");
}
if (Count < 3)
{
bool bInsett = false; DListNode_<T> ldNote = First;
while (ldNote != null)
{
if (_sortord == Sortord_.s_max_min)
{
if ((item as IComparable).CompareTo(ldNote.Data) >= 0)
{
base.InserNoteFront(ldNote, item); bInsett = true; break;
}
}
else
{
if ((item as IComparable).CompareTo(ldNote.Data) <= 0)
{
base.InserNoteFront(ldNote, item); bInsett = true; break;
}
}
ldNote = ldNote.Next;
}
if (!bInsett) base.Add(item);
return;
}
int nPos = Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = Count - 1; //右边远素
if (_sortord == Sortord_.s_max_min)
{
DListNode_<T> ldNote = null;
while (nRight >= 0 && nLeft >= 0)
{
ldNote = IndexOfNote(nPos);
if ((item as IComparable).CompareTo(ldNote.Data) >= 0)
{
if (nRight == nLeft || nPos == nLeft)
{
InserNoteFront(ldNote, item);
return;
}
nRight = nPos - 1;
}
else
{
if (nRight == nLeft || nPos == nRight)
{
InserNoteBack(ldNote, item);
return;
}
nLeft = nPos + 1;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
else
{
DListNode_<T> ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNote(nPos);
if ((item as IComparable).CompareTo(ld.Data) <= 0)
{
if (nRight == nLeft || nPos == nLeft)
{
InserNoteFront(ld, item);
return;
}
nRight = nPos - 1;
}
else
{
if (nRight == nLeft || nPos == nRight)
{
InserNoteBack(ld, item);
return;
}
nLeft = nPos + 1;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
return;
}
}
#endregion
#region//================================================= UniqueList_ 每个项的值都是唯一的链表
/// <summary>
/// 每个项的值都是唯一的链表
/// </summary>
/// <typeparam name="T"></typeparam>
public class UniqueList_<T> : DList_<T>
{
public override void Add(T item)
{
if (BinarySearch(item) == -1)
{
base.Add(item);
}
}
}
#endregion
#region //========================== =========SUList_,已排序，且每一项的值都是唯一的链表
/// <summary>
/// SUList_,已排序，且每一项的值都是唯一的链表
/// </summary>
/// <typeparam name="T"></typeparam>
public class SUList_<T> : SortList_<T>
{
/// <summary>
/// 将指定集合的元素添加到末尾
/// </summary>
/// <param name="item">要添加到的末尾处的对象。对于引用类型，该值可以为 null</param>
/// <returns>如成功，返回真，否则返回假</returns>
public override void Add(T item)
{
if (BinarySearch(item) == -1)
{
base.Add(item);
}
}
public SUList_(Sortord_ sortord)
: base(sortord)
{
}
}
#endregion
#region //================================＝＝=======StringList_字符串列表
/// <summary>
/// 字符串列表
/// </summary>
public class StringList_ : DList_<string>
{
/// <summary>
/// 默认构函数
/// </summary>
public StringList_()
{
}
/// <summary>
/// 以分隔符构造一个字符串列表
/// </summary>
/// <param name="sText">原文字符串</param>
/// <param name="sSplit">分隔符</param>
/// <param name="bIgnoreEmptyString">返回列表，空字符串不忽略，如果没有分隔符，则回原字符</param>
/// 创建时间： ????-??-?? 最后一修改时间：2020-09-03
public StringList_(string sText, string sSplit, bool bIgnoreEmptyString = false)
{
if(sText == null || sText.Length == 0){ return; }
if(sSplit.Length == 0) { Add(sText); return; }
int nPos = sText.IndexOf(sSplit);
int nFindStart = 0;
while(nPos != -1)
{
if (nPos - nFindStart == 0)
{
if (!bIgnoreEmptyString)
{
Add("");
}
}
else
{
Add(sText.Substring(nFindStart, nPos - nFindStart));
}
nFindStart = nPos + sSplit.Length;
nPos = sText.IndexOf(sSplit, nFindStart);
if(nPos == -1) //拷贝最后一个
{
if(nFindStart < sText.Length)
{
Add(sText.Substring(nFindStart, sText.Length - nFindStart));
}
else
{
if (!bIgnoreEmptyString)
{
Add("");
}
}
}
}
}
#if !WINDOWS_UWP
/// <summary>
/// 把列表写入文件
/// </summary>
/// <param name="sFileName">文件名</param>
public void WriteToFile(string sFileName)
{
System.IO.File.Delete(sFileName);
DListNode_<string> dl = First;
FileStream fs = File.Create(sFileName);
while (dl != null)
{
byte[] bArray = System.Text.Encoding.Default.GetBytes(dl.Data);
fs.Write(bArray, 0, bArray.Length);
bArray = System.Text.Encoding.Default.GetBytes("\r\n");
//fs.WriteByte((byte)'\r'); 不行，UNICODE代码
//fs.WriteByte((byte)'\n');
fs.Write(bArray, 0, bArray.Length);
dl = dl.Next;
}
fs.Close();
}
/// <summary>
/// 从文件中读取列表分隔符为"\r\n";
/// </summary>
/// <param name="sFileName">文件名</param>
/// <returns></returns>
public bool ReadToFile(string sFileName)
{
if (File.Exists(sFileName))
{
FileStream fs = new FileStream(sFileName, FileMode.Open, FileAccess.Read);
Byte[] bArray = new Byte[fs.Length];
fs.Read(bArray, 0, bArray.Length);
fs.Close();
CopyFrom(System.Text.Encoding.Default.GetString(bArray)._Split("\r\n"));
return true;
}
return false;
}
/// <summary>
/// 从文件中读取列表分隔符
/// </summary>
/// <param name="sFileName"></param>
/// <param name="sSplit"></param>
/// <returns></returns>
public bool readToUnicodeFile(string sFileName,string sSplit)
{
if (File.Exists(sFileName))
{
FileStream fs = new FileStream(sFileName, FileMode.Open, FileAccess.Read);
Byte[] bArray = new Byte[fs.Length];
fs.Read(bArray, 0, bArray.Length);
fs.Close();
CopyFrom(System.Text.Encoding.Unicode.GetString(bArray)._Split(sSplit));
return true;
}
return false;
}
public void SaveToUnicodeFile(string sFileName, string sSplit)
{
/*
if(_Count > 0)
{
string sContent = "";
int n = 1;
foreach(string s in this)
{
sContent += s;
if(n != _Count)
sContent += sSplit;
}
Byte[] bArray = System.Text.ASCIIEncoding.ASCII.GetBytes(sContent);
FileStream fs = new FileStream(sFileName, FileMode.Create, FileAccess.Write);
fs.Write(bArray, 0, bArray.Length);
fs.Close();
}
*/
}
/// <summary>
/// 把所有字符串写入磁盘，但每个字符串中的空格和不可打印字符都不会写入，每15个字符串加入一个换行符。
/// </summary>
/// <param name="sFileName"></param>
/// <param name="sSplit"></param>
/// 创建时间： 2022-02-09 最后一次修改时间：2022-02-09
public void WriteToTxtFile(string sFileName, string sSplit)
{
if (_Count > 0)
{
string sContent = "";
int n = 1;
foreach (string s in this)
{
sContent += s._RemoveUnprintableAndWhitespace();
if (n != _Count)
sContent += sSplit;
if(n % 15 == 0)
sContent += "\n";
++n;
}
File.WriteAllText(sFileName,sContent);
}
}
/// <summary>
/// 用分隔 符读取文本文件，空格和不可打印字符都不读取。
/// </summary>
/// <param name="sFileName"></param>
/// <param name="sSplit"></param>
/// 创建时间： 2022-02-09 最后一次修改时间：2022-02-18
public void ReadFromTxtFile(string sFileName, string sSplit)
{
if (!File.Exists(sFileName))
return;
string sContent = File.ReadAllText(sFileName)._RemoveUnprintableAndWhitespace();
if(sContent.Trim().Length > 0)
{
CopyFrom(sContent._Split(sSplit));
}
}
#endif
/// <summary>
/// 用分隔符把每个项连成一片，如果分隔符为空，则直接连成一片
/// </summary>
/// <param name="sSeparator">分隔符</param>
/// <returns></returns>
public string ConnectForSeparator(string sSeparator)
{
if (Count == 0) return "";
if (Count == 1) return First.Data;
string tmp = "";
DListNode_<string> ldNote = First;
while (ldNote != Last)
{
tmp += ldNote.Data;
tmp += sSeparator;
ldNote = ldNote.Next;
}
tmp += Last.Data; //加入最后一项
return tmp;
}
/// <summary>
/// 用分隔符把每个项连成一片，如果分隔符为空，则直接连成一片
/// </summary>
/// <param name="cSeparator">分隔符</param>
/// <returns></returns>
public string ConnectForSeparator(char cSeparator)
{
return ConnectForSeparator(cSeparator.ToString());
}
/// <summary>
/// 清空列表，用分隔符把字符串分裂成多项,返回项数
/// </summary>
/// <param name="sText"></param>
/// <param name="sSplit"></param>
/// <returns></returns>
public int splitForSeparator(string sText, char cSplit)
{
Clear();
string[] sl = sText.Split(cSplit);
for (int i = 0; i < sl.Length; ++i)
{
Add(sl[i]);
}
return Count;
}
/// <summary>
/// 查找第一个可印的字符串，如果找到则返回它的值，没找到返回空字符中。
/// </summary>
/// <returns></returns>
/// 创建时间： 2022-01-21 最后一次修改时间：2022-01-21
public string FindFirstPrintableStringValue()
{
DListNode_<string> pNote = _First;
while (pNote != null)
{
if(pNote.Data._IsHavePrintableChar())
{
return pNote.Data;
}
pNote = pNote.Next;
}
return "";
}
/// <summary>
/// 查找第一个可印的字符串的索引，如果找到则返回它的索引，没找到返回-1。
/// </summary>
/// <returns></returns>
/// 创建时间： 2022-01-21 最后一次修改时间：2022-01-21
public int FindFirstPrintableStringIndex()
{
DListNode_<string> pNote = _First;
int nResult = 0;
while (pNote != null)
{
if (pNote.Data._IsHavePrintableChar())
{
return nResult;
}
pNote = pNote.Next;
++nResult;
}
return -1;
}
/// <summary>
///
/// </summary>
/// <param name="ls"></param>
/// <returns></returns>
/// 创建时间： ????-??-?? 最后一次修改时间：2021-10-10
public virtual bool Add(StringList_ ls)
{
DListNode_<string> pNote = ls._First;
while (pNote != null)
{
Add(pNote.Data);
pNote = pNote.Next;
}
return true;
}
/// <summary>
/// 是开头插入一个字符串
/// </summary>
/// <param name="sItem"></param>
/// <returns></returns>
/// 创建时间： 2022-01-18 最后一次修改时间：2022-01-18
public virtual bool InserFront(string sItem)
{
if(_Count == 0)
Add(sItem);
InserNoteFront(_First,sItem);
return true;
}
/// <summary>
/// 查找字符吕 S
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
/// <exception cref="Exception"></exception>
/// 创建时间： ????-??-?? 最后一次修改时间：2022-09-18
public int IndexOf(string s)
{
//if(s.Length == 0){ throw new Exception("字符串不能为空！");}
DListNode_<string> pNote = _First;
int iIndex = 0;
while (pNote != null)
{
if (pNote.Data == s)
{
return iIndex;
}
pNote = pNote.Next;
++iIndex;
}
return - 1;
}
}
#endregion
#region //================================＝＝=======LSStringList已排序好的字符串列表
/// <summary>
/// 已排序好的字符串列表
/// </summary>
public class SStringList_ : StringList_
{
public SStringList_(Sortord_ sortord)
{
if (sortord == Sortord_.s_null)
{
throw new System.Exception("排序不能为空！");
}
_sortord = sortord;
}
//-------------------------------------------------------------------------------重写
/// <summary>
/// 快速添加字符串，差不多用了8个小时(两天），才写成。
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
public override void Add(string item)
{
if (Count < 3)
{
bool bInsett = false; DListNode_<string> ld = First;
while (ld != null)
{
if (_sortord == Sortord_.s_max_min)
{
if (item.CompareTo(ld.Data) >= 0)
{
base.InserNoteFront(ld, item); bInsett = true; break;
}
}
else
{
if (item.CompareTo(ld.Data) <= 0)
{
base.InserNoteFront(ld, item); bInsett = true; break;
}
}
ld = ld.Next;
}
if (!bInsett) base.Add(item);
return;
}
int nPos = Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = Count - 1; //右边远素
if (_sortord == Sortord_.s_max_min)
{
DListNode_<string> ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNote(nPos);
if (item.CompareTo(ld.Data) >= 0)
{
if (nRight == nLeft || nPos == nLeft)
{
InserNoteFront(ld, item);
return;
}
nRight = nPos - 1;
}
else
{
if (nRight == nLeft || nPos == nRight)
{
InserNoteBack(ld, item);
return;
}
nLeft = nPos + 1;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
else
{
DListNode_<string> ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNote(nPos);
if (item.CompareTo(ld.Data) <= 0)
{
if (nRight == nLeft || nPos == nLeft)
{
InserNoteFront(ld, item);
return;
}
nRight = nPos - 1;
}
else
{
if (nRight == nLeft || nPos == nRight)
{
InserNoteBack(ld, item);
return;
}
nLeft = nPos + 1;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
return;
}
/// <summary>
/// 确定某元素是否在列表中
/// </summary>
/// <param name="item">查找的对象。对于引用类型，该值可以为 null。</param>
/// <returns>如果在列表中找到 item，则为 true，否则为 false。</returns>
public override bool Contains(string item)
{
if (Count == 0) return false;
if (Count == 1) return First.Data.CompareTo(item) == 0;
if (Count == 2) return First.Data.CompareTo(item) == 0 || First.Next.Data.CompareTo(item) == 0;
int nPos = (int)Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)Count - 1; //右边远素
DListNode_<string> ld = null;
if (_sortord == Sortord_.s_max_min)
{
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNote(nPos);
int iCom = item.CompareTo(ld.Data);
if (iCom > 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return false;
}
nRight = nPos - 1;
}
else if (iCom < 0)
{
if (nRight == nLeft || nPos == nRight)
{
return false;
}
nLeft = nPos + 1;
}
else
{
return true;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
else
{
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNote(nPos);
int iCom = item.CompareTo(ld.Data);
if (iCom < 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return false;
}
nRight = nPos - 1;
}
else if (iCom > 0)
{
if (nRight == nLeft || nPos == nRight)
{
return false;
}
nLeft = nPos + 1;
}
else
{
return true;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
return false;
}
}
#endregion
#region //================================＝＝=======UStringList_值都是唯一的字符串列表，区分大小写
/// <summary>
/// 值都是唯一的字符串列表
/// </summary>
/// <typeparam name="T"></typeparam>
public class UStringList_ : StringList_
{
public override void Add(string item)
{
if(BinarySearch(item) == -1)
base.Add(item);
}
public void Add(string[] sArray)
{
for (int i = 0; i < sArray.Length; ++i)
{
Add(sArray[i]);
}
}
public override bool Add(StringList_ ls)
{
bool bResult = true;
DListNode_<string> pFirst = ls.First;
while (pFirst != null)
{
if (BinarySearch(pFirst.Data) == -1)
{
base.Add(pFirst.Data);
}
else
{
bResult = false;
}
pFirst = pFirst.Next;
}
return bResult;
}
}
#endregion
#region//======================================SUStringList_ 值都是唯一的字符串列表,且已排好序，区分大小写
/// <summary>
/// 值都是唯一的字符串列表,且已排好序，区分大小写
/// </summary>
public class SUStringList_ : SStringList_
{
public override void Add(string item)
{
if (Contains(item))
return;
base.Add(item);
}
public SUStringList_(Sortord_ sortord)
: base(sortord)
{
}
}
#endregion
#region //================================＝＝=======UStringListCI_值都是唯一的字符串列表，不区分大小写
/// <summary>
/// 值都是唯一的字符串列表， Case Insensitive(不区分大小写)
/// </summary>
public class UStringListCI_ : StringList_
{
/// <summary>
/// 加入一个串，如果这个串存在，则把这项移到最后。
/// </summary>
/// <param name="item"></param>
/// 创建时间： ????-??-?? 最后一次修改时间：2022-02-18
public override void Add(string item)
{
bool bFind = false;
DListNode_<string> dnTemp = First;
while(dnTemp != null)
{
if(dnTemp.Data.ToLower() == item.ToLower())
{
MoveLast(dnTemp);
bFind = true;
break;
}
dnTemp = dnTemp.Next;
}
if (!bFind)
base.Add(item);
}
/// <summary>
/// 返回前面一个值
/// </summary>
/// <param name="tCurrValue"></param>
/// <returns></returns>
public string GetForward(string sCurr)
{
int iIndex = BinarySearch(sCurr);
if (iIndex != -1)
{
if (iIndex + 1 < Count)
return this[iIndex + 1];
}
return null;
}
/// <summary>
/// 返回后面的一个值
/// </summary>
/// <param name="sCurr"></param>
/// <returns></returns>
public string GetBack(string sCurr)
{
int iIndex = BinarySearch(sCurr);
if (iIndex != -1)
{
if (iIndex - 1 < Count && iIndex - 1 >= 0)
return this[iIndex - 1];
}
return null;
}
}
#endregion
#region //================================＝＝=======UStringListCI_值都是唯一,且已排序的字符串列表，不区分大小写
/// <summary>
/// UStringListCI_值都是唯一,且已排序的字符串列表，不区分大小写
/// </summary>
public class SUStringListUI_ : SUStringList_
{
public SUStringListUI_(Sortord_ sortord): base(sortord)
{
}
/// <summary>
/// 确定某元素是否在列表中
/// </summary>
/// <param name="item">查找的对象。对于引用类型，该值可以为 null。</param>
/// <returns>如果在列表中找到 item，则为 true，否则为 false。</returns>
public override bool Contains(string item)
{
if (Count == 0) return false;
if (Count == 1) return First.Data.ToLower().CompareTo(item.ToLower()) == 0;
if (Count == 2) return First.Data.ToLower().CompareTo(item.ToLower()) == 0 || First.Next.Data.ToLower().CompareTo(item.ToLower()) == 0;
int nPos = (int)Count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)Count - 1; //右边远素
DListNode_<string> ld = null;
if (_sortord == Sortord_.s_max_min)
{
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNote(nPos);
int iCom = item.ToLower().CompareTo(ld.Data.ToLower());
if (iCom > 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return false;
}
nRight = nPos - 1;
}
else if (iCom < 0)
{
if (nRight == nLeft || nPos == nRight)
{
return false;
}
nLeft = nPos + 1;
}
else
{
return true;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
else
{
while (nRight >= 0 && nLeft >= 0)
{
ld = IndexOfNote(nPos);
int iCom = item.ToLower().CompareTo(ld.Data.ToLower());
if (iCom < 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return false;
}
nRight = nPos - 1;
}
else if (iCom > 0)
{
if (nRight == nLeft || nPos == nRight)
{
return false;
}
nLeft = nPos + 1;
}
else
{
return true;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
}
return false;
}
}
#endregion
/// <summary>
/// 历史记录，相当于栈
/// </summary>
/// <typeparam name="T"></typeparam>
/// 创建时间：2022-03-06 最后一次修改时间：2022-04-19
public class UniqueStack_<T>
{
private DList_<T> m_List;
private int m_Capacity;
public DList_<T> List => m_List;
/// <summary>
/// 元素容量
/// </summary>
public int Capacity => m_Capacity;
/// <summary>
/// 无素个数
/// </summary>
public int Count => m_List.Count;
public UniqueStack_(int nCapacity = 15)
{
if(nCapacity <= 0)
{
lg.ShowError("容量不能小于等于 0 ！");
m_Capacity = 15;
}
else
{
m_Capacity = nCapacity;
}
m_List = new DList_<T>();
}
/// <summary>
/// 添加一项
/// </summary>
/// <param name="item"></param>
/// 创建时间： 2022-04-19 最后一次修改时间：2022-04-19
public void Push(T item)
{
bool bFind = m_List.RemoveItem(item); //如果找到，则删除
if (!bFind)
{
if (m_List.Count < m_Capacity)
{
m_List.StackPush(item);
}
else
{
//插入一个Item，所有元素后移一位
m_List.StackPush(item,true);
}
}
else
{
//插入一个Item，所有元素后移一位
m_List.StackPush(item);
}
}
/// <summary>
/// 出栈
/// </summary>
public void Pop() => List.StackPop();
}
public class HistoryStringList_ : UniqueStack_<string>
{
public override string ToString()
{
string sResult = "";
foreach (string s in List)
{
sResult += s + "||";
}
if (sResult != "")
{
sResult = sResult.Substring(0, sResult.Length - 2);
}
return sResult;
}
public void FromString(string sVaule)
{
List.Clear();
StringList_ ls = sVaule._Split("||");
DListNode_<string> dnNode = ls.Last;
while (dnNode != null){
Push(dnNode.Data);
dnNode = dnNode.Prev;
}
}
public HistoryStringList_(int nCapacity = 15) : base(nCapacity) { }
}
public class HistoryStringListPair_ : UniqueStack_<Pair_<string, string>>
{
public override string ToString()
{
string sResult = "";
foreach (Pair_<string, string> pair in List)
{
sResult += pair.First + "," + pair.Second + "||";
}
if (sResult != "")
{
sResult = sResult.Substring(0, sResult.Length - 2);
}
return sResult;
}
public void FromString(string sVaule)
{
List.Clear();
StringList_ ls1 = sVaule._Split("||");
DListNode_<string> dnNode = ls1.Last;
while (dnNode != null)
{
StringList_ ls2 = dnNode.Data._Split(",");
if (ls2.Count == 2)
{
Push(ls2[0], ls2[1]);
}
dnNode = dnNode.Prev;
}
}
public HistoryStringListPair_(int nCapacity = 15) : base(nCapacity) { }
public void Push(string s1, string s2) { base.Push(new Pair_<string, string>(s1, s2)); }
public Pair_<string, string> IndexOfFirst(string sFirst)
{
foreach (Pair_<string, string> pair in List)
{
if (pair.First == sFirst)
return pair;
}
return null;
}
public Pair_<string, string> IndexOfSecond(string sSecond)
{
foreach(Pair_<string, string> pair in List)
{
if(pair.Second == sSecond)
return pair;
}
return null;
}
}
public class LPairList<T1, T2> : IEnumerable
{
DList_<Pair_<T1, T2>> m_list;
public DList_<Pair_<T1, T2>> List { get { return m_list; } }
public LPairList()
{
m_list = new DList_<Pair_<T1, T2>>();
}
public Pair_<T1, T2> GetIndex(int iIndex)
{
DListNode_<Pair_<T1, T2>> dn = m_list.IndexOfNote(iIndex);
if (dn == null)
return null;
else
return dn.Data;
}
public void RemoveAt(int iIndex)
{
m_list.RemoveAt(iIndex);
}
public void Clear()
{
m_list.Clear();
}
public void Add(T1 First, T2 Second)
{
m_list.Add(new Pair_<T1, T2>(First, Second));
}
public void Add(Pair_<T1, T2> p)
{
m_list.Add(p);
}
public void CopyTo(IList il1, IList il2)
{
il1.Clear();
il2.Clear();
foreach (DListNode_<Pair_<T1, T2>> dn in m_list)
{
il1.Add(dn.Data.First);
il2.Add(dn.Data.First);
}
}
public int Count { get { return m_list.Count; } }
/// <summary>
/// 创建时间： ????-??-?? 最后一次修改时间：2020-05-31
/// 查找sFirstStringValue,找不到返回NULL
/// </summary>
/// <param name="sFirst"></param>
/// <returns></returns>
public Pair_<T1, T2> IndexFirst(T1 sFirstStringValue)
{
foreach (Pair_<T1, T2> p in m_list)
{
if (p.First.Equals(sFirstStringValue))
return p;
}
return null;
}
/// <summary>
/// 创建时间： ????-??-?? 最后一次修改时间：2020-05-31
/// 查找sSecondStringValue,找不到返回NULL
/// </summary>
/// <param name="sFirst"></param>
/// <returns></returns>
public Pair_<T1, T2> IndexSecond(T2 sSecondStringValue)
{
foreach (Pair_<T1, T2> p in m_list)
{
if (p.Second.Equals(sSecondStringValue))
return p;
}
return null;
}
/// <summary>
/// 创建时间： 2020-05-31 最后一次修改时间：2020-05-31
/// 查找第一项，找到返回第二项的值，没找到返回第二项的默认值。
/// </summary>
/// <param name="sFirstStringValue"></param>
/// <returns></returns>
public T2 IndexFirstValue(T1 sFirstStringValue)
{
foreach (Pair_<T1, T2> p in m_list)
{
if (p.First.Equals(sFirstStringValue))
return p.Second;
}
return default(T2);
}
/// <summary>
/// 创建时间： 2020-05-31 最后一次修改时间：2020-05-31
/// 查找第三项，找到返回第一项的值，没找到返回第一项的默认值。
/// </summary>
/// <param name="sSecondStringValue"></param>
/// <returns></returns>
public T1 IndexSecondValue(T2 sSecondStringValue)
{
foreach (Pair_<T1, T2> p in m_list)
{
if (p.Second.Equals(sSecondStringValue))
return p.First;
}
return default(T1);
}
IEnumerator IEnumerable.GetEnumerator()
{
return m_list.GetEnumerator();
}
}
public class LStringPairList : LPairList<string, string>
{
/// <summary>
/// 依据slFirst查找Second
/// </summary>
/// <param name="slFirst"></param>
/// 创建时间：2020-05-09 最后一次修改时间：2020-05-09
/// <returns></returns>
public StringList_ GetSecondList(StringList_ slFirst)
{
StringList_ slResult = new StringList_();
foreach (Pair_<string, string> p in this)
{
if (slFirst.FindNodeItem(p.First) != null)
{
slResult.Add(p.Second);
}
}
return slResult;
}
/// <summary>
/// 依据slSecond查找First
/// </summary>
/// <param name="slSecond"></param>
/// 创建时间：2020-05-09 最后一次修改时间：2020-05-09
/// <returns></returns>
public StringList_ GetFirstList(StringList_ slSecond)
{
StringList_ slResult = new StringList_();
foreach (Pair_<string, string> p in this)
{
if (slSecond.FindNodeItem(p.Second) != null)
{
slResult.Add(p.First);
}
}
return slResult;
}
}
}
Java
/***************************************************************************************************
创建时间 : 2020年01月12日
文件名: : LDList.java
作者 : 李锋
Email : ruizhilf@139.com
联系电话 : 13828778863
作用 : 双向链表
此文件暂时以 C# 编程风格，因为 C#也有一份代码，是从C#移植过来的。
----------------------------------------------------------------------最后一次修改时间： 2022年07月02日
**************************************************************************************************/
package JavaPlatform.System;
import java.util.ArrayList;
import java.util.Iterator;
import JavaPlatform.jp;
class DListNote_<T>
{
/**
* 节点数据
*/
public T data;
/**
* 前一个节点
*/
public DListNote_<T> prev;
/**
* 下一个节点
*/
public DListNote_<T> next;
/**
* 功能：定位节点指针。
*
* @param nMove 指针移动的个数，0为不变，负数是向上prev方法移动，正数是向下next移动。
* @return 返回指向节点的指针 ，移动超出范围返回值为null。
* 创建时间：2022/07/02 最后一次修改时间：2022/07/02
*/
public DListNote_<T> pointerTo(int nMove)
{
if ( nMove >= 0){ //向下
int n = 0;
DListNote_<T> pTemp = this;
//计数
while(pTemp != null){
if( n == nMove) break;
pTemp = pTemp.next;
++ n;
}
return pTemp;
}else{ //向上
int n = 0;
DListNote_<T> pTemp = this;
//计数
while(pTemp != null){
if( n == - nMove ) break;
pTemp = pTemp.prev;
++ n;
}
return pTemp;
}
}
public DListNote_(T adata) {
data = adata;
}
}
/**
* The type D list.
*
* @param <T> the type parameter
*/
public class DList_<T extends Comparable<T>> implements Iterable<T>{
/**
* 排序方式
*/
public enum Sortord_
{
s_min_max, //从小到大
s_max_min, //从大到小
s_null //无排序顺序
}
protected DListNote_<T> _first; //第一个节点
protected DListNote_<T> _last; //最后一个节点
protected int _count; //节点个数
protected Sortord_ _sortord; //排序顺序
/**
* 适用于 foreach 语句
* @return
*/
public Iterator<T> iterator() {
/*
return new Iterator() {
private int m_cursor = -1;
@Override
public T next() {
++m_cursor;
return indexOfNote(m_cursor).data;
}
@Override
public boolean hasNext() {
return m_cursor + 1 < _count;
}
};*/
return new DListNoteEnum_<T>(_first);
}
private void initData(){
_count = 0;
_first = null;
_last = null;
_sortord = Sortord_.s_null;
}
/**
* Instantiates a new D list.
*/
/// <summary>
/// 构造函数
/// </summary>
public DList_() { initData(); }
@SafeVarargs
public DList_(T... args){
initData();
for( T t: args){ add(t); }
}
/**
* Get first d list note.
*
* @return the d list note
*/
public DListNote_<T> getFirst(){ return _first; }
/**
* Get last d list note.
*
* @return the d list note
*/
public DListNote_<T> getLast(){ return _last; }
/**
* Get sortord sortord.
*
* @return the sortord
*/
public Sortord_ getSortord(){ return _sortord; }
/**
* Get count int.
*
* @return the int
*/
/// <summary>
/// 实际包含的元素数
/// </summary>
public int getCount(){
return _count;
}
/**
* Add boolean.
*
* @param item the item
* @return the boolean
*/
/// <summary>
/// 将指定集合的元素添加到末尾
/// </summary>
/// <param name="item">要添加到的末尾处的对象。对于引用类型，该值可以为 null</param>
/// <returns>如成功，返回真，否则返回假</returns>
public Boolean add(T item){
if (_count == 0){
_first = new DListNote_<T>(item);
_first.next = null;
_first.prev = null;
_last = _first;
}else{
DListNote_ pNew = new DListNote_<T>(item);
pNew.next = null;
pNew.prev = _last;
_last.next = pNew;
_last = pNew;
}
++_count;
return true;
}
/**
* Add.
*
* @param dList the d list
*/
public void add(DList_<T> dList){
if (dList == null){
throw new NullPointerException();
}
DListNote_<T> ld = dList._first;
while (ld != null){
add(ld.data);
ld = ld.next;
}
}
/**
* Index of note d list note.
*
* @param iPos the pos
* @return the d list note
*/
/// <summary>
/// 返回索引的节点,从零开始
/// </summary>
/// <param name="nPos"></param>
/// <returns></returns>
public DListNote_<T> indexOfNote(int iPos)
{
if (iPos >= _count || iPos < 0) throw new IndexOutOfBoundsException();
int nindex = 0;
if (iPos > _count / 2)
{
DListNote_<T> pNote = _last;
while (pNote != null)
{
if (nindex++ == _count - iPos - 1){ return pNote;}
pNote = pNote.prev;
}
}
else
{
DListNote_<T> pNote = _first;
while (pNote != null)
{
if (nindex++ == iPos)
{
return pNote;
}
pNote = pNote.next;
}
}
return null;
}
/**
* Bnary search int.
*
* @param item the item
* @return the int
*/
/// <summary>
/// 使用指定的比较器在整个已排序的 中搜索元素，并返回该元素从零开始的索引
/// </summary>
/// <param name="item">要定位的对象。对于引用类型，该值可以为 null。</param>
/// <returns>如果找到 item，则为已排序的 的从零开始的索引；否则为-1; </returns>
public int bnarySearch(T item)
{
switch (_sortord)
{
case s_max_min:
{
if (_count == 0)
{
return -1;
}
if (_count == 1)
{
return _first.data.compareTo(item) == 0 ? 0 : -1;
}
if (_count == 2)
{
if( _first.data.compareTo(item) == 0) return 0;
if ( _first.next.data.compareTo(item) == 0) return 1;
return -1;
}
int nPos = _count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = _count - 1; //右边远素
DListNote_<T> ld;
while (nRight >= 0 && nLeft >= 0)
{
ld = indexOfNote(nPos);
int iCom = item.compareTo(ld.data);
if (iCom > 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return -1;
}
nRight = nPos - 1;
}
else if (iCom < 0)
{
if (nRight == nLeft || nPos == nRight)
{
return -1;
}
nLeft = nPos + 1;
}
else
{
return nPos;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case s_min_max:
{
if (_count == 0)
{
return -1;
}
if (_count == 1)
{
return _first.data.compareTo(item) == 0 ? 0 : -1;
}
if (_count == 2)
{
if (_first.data.compareTo(item) == 0) return 0;
if (_first.next.data.compareTo(item) == 0) return 1;
return -1;
}
int nPos = (int)_count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = (int)_count - 1; //右边远素
DListNote_<T> ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = indexOfNote(nPos);
int iCom = item.compareTo(ld.data);
if (iCom < 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return -1;
}
nRight = nPos - 1;
}
else if (iCom > 0)
{
if (nRight == nLeft || nPos == nRight)
{
return -1;
}
nLeft = nPos + 1;
}
else
{
return nPos;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case s_null:
{
DListNote_<T> pNote = _first;
int iCount = 0;
while (pNote != null)
{
if (pNote.data.equals(item))
{
return iCount;
}
pNote = pNote.next;
++iCount;
}
break;
}
default:
{
return -1;
}
}
return -1;
}
/**
* Contains boolean.
*
* @param item the item
* @return the boolean
*/
/// <summary>
/// 确定某元素是否在列表中
/// </summary>
/// <param name="item">查找的对象。对于引用类型，该值可以为 null。</param>
/// <returns>如果在列表中找到 item，则为 true，否则为 false。</returns>
public boolean contains(T item)
{
return bnarySearch(item) != -1;
}
/**
* Copy from.
*
* @param ld the ld
*/
/// <summary>
/// 复制一个链表，清除原来链表的数据
/// </summary>
/// <param name="ld"></param>
public void copyFrom(DList_<T> ld)
{
if (!this.equals(ld))
{
clear();
DListNote_<T> ldItem = ld._first;
while (ldItem != null)
{
add(ldItem.data);
ldItem = ldItem.next;
}
}
}
/*
/// <summary>
/// 转换成数组
/// </summary>
/// <returns></returns>
public T[] toArray()
{
T[] aResult = new T[_count]; //错误: 创建泛型数组
int n = 0;
DListNote_ pNoteTemp = _first;
while (pNoteTemp != null)
{
aResult[n++] = pNoteTemp.data;
pNoteTemp = pNoteTemp.next;
}
return aResult;
}
*/
/**
* Swap notedata boolean.
*
* @param iIndex1 the index 1
* @param iIndex2 the index 2
* @return the boolean
*/
/// <summary>
/// 交换两个节点的数据
/// </summary>
/// <param name="nIndex1"></param>
/// <param name="nIndex2"></param>
/// <returns></returns>
public boolean swapNotedata(int iIndex1, int iIndex2)
{
DListNote_<T> pNote1, pNote2;
pNote1 = indexOfNote(iIndex1);
pNote2 = indexOfNote(iIndex2);
if (!(pNote1 != null && pNote2 != null))
{
return false;
}
T pTmp = pNote1.data;
pNote1.data = pNote2.data;
pNote2.data = pTmp;
return true;
}
/**
* Sort selection.
*
* @param sortord the sortord
*/
/// <summary>
/// 选择排序可以说是最简单的一种排序方法：
/// 1.找到数组中最小的那个元素
/// 2.将最小的这个元素和数组中第一个元素交换位置
/// 3.在剩下的元素中找到最小的的元素，与数组第二个元素交换位置
/// 重复以上步骤，即可以得到有序数组。
/// </summary>
public void sort_selection(Sortord_ sortord)
{
_sortord = sortord; //已排序
if (_count == 0 || _count == 1) return;
DListNote_<T> min = _first, tmp = _first.next;
if (sortord == Sortord_.s_min_max)
{
while (min.next != null)
{
while (tmp != null)
{
if ( tmp.data.compareTo(min.data) < 0) //交换位置
{
T pt = tmp.data;
tmp.data = min.data;
min.data = pt;
}
tmp = tmp.next;
}
min = min.next;
tmp = min.next;
}
}
else
{
while (min.next != null)
{
while (tmp != null)
{
if (tmp.data.compareTo(min.data) > 0)
{
T pt = tmp.data;
tmp.data = min.data;
min.data = pt;
}
tmp = tmp.next;
}
min = min.next;
tmp = min.next;
}
}
}
/**
* Inser note front d list note.
*
* @param pListItem the p list item
* @param pData the p data
* @return the d list note
*/
/// <summary>
/// 在结点pListItem前面插入一个结点,成功，返回新的结点，否则返回０
/// </summary>
/// <param name="pListItem"></param>
/// <param name="pData"></param>
/// <returns></returns>
protected DListNote_ InserNoteFront(DListNote_ pListItem, T pData)
{
if (pListItem == null)
{
throw new NullPointerException();
}
DListNote_ pNote = new DListNote_(pData);
//pNote
pNote.next = pListItem;
pNote.prev = pListItem.prev;
//--pListItem->prev
if (pListItem.prev != null)
{
pListItem.prev.next = pNote;
}
else
{
_first = pNote;
}
//pListItem
pListItem.prev = pNote;
++_count;
return pNote;
}
/**
* Inser note back d list note.
*
* @param pListItem the p list item
* @param pData the p data
* @return the d list note
*/
/// <summary>
/// 在结点pListItem后面插入一个结点,成功，返回新的结点，否则返回０；
/// </summary>
/// <param name="pListItem"></param>
/// <param name="pData"></param>
/// <returns></returns>
protected DListNote_ InserNoteBack(DListNote_ pListItem, T pData)
{
if (pListItem == null) return null;
DListNote_ pNote = new DListNote_(pData);
//pNote
pNote.prev = pListItem;
pNote.next = pListItem.next;
//pListItem->next
if (pListItem.next != null)
{
pListItem.next.prev = pNote;
}
else
{
_last = pNote;
}
//--pListItem
pListItem.next = pNote;
++_count;
return pNote;
}
/**
* Find note item d list note.
*
* @param item the item
* @return the d list note
*/
/// <summary>
/// 找查一个项，而不是节点，返回的这个节点相当于指针。
/// </summary>
/// <param name="pData">项值</param>
/// <returns></returns>
public DListNote_ findNoteItem(T item)
{
switch (_sortord)
{
case s_max_min:
{
if (_count == 0)
{
return null;
}
if (_count == 1)
{
return _first.data.compareTo(item) == 0 ? _first : null;
}
if (_count == 2)
{
if (_first.data.compareTo(item) == 0) return _first;
if (_first.next.data.compareTo(item) == 0) return _first.next;
return null;
}
int nPos = _count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = _count - 1; //右边远素
DListNote_<T> ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = indexOfNote(nPos);
int iCom = item.compareTo(ld.data);
if (iCom > 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return null;
}
nRight = nPos - 1;
}
else if (iCom < 0)
{
if (nRight == nLeft || nPos == nRight)
{
return null;
}
nLeft = nPos + 1;
}
else
{
return ld;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case s_min_max:
{
if (_count == 0)
{
return null;
}
if (_count == 1)
{
return _first.data.compareTo(item) == 0 ? _first : null;
}
if (_count == 2)
{
if (_first.data.compareTo(item) == 0) return _first;
if (_first.next.data.compareTo(item) == 0) return _first.next;
return null;
}
int nPos = _count / 2; //nPos在中间，所以无素一定要大于等于3才行
int nLeft = 0; //左边远素
int nRight = _count - 1; //右边远素
DListNote_<T> ld = null;
while (nRight >= 0 && nLeft >= 0)
{
ld = indexOfNote(nPos);
int iCom = item.compareTo(ld.data);
if (iCom < 0)
{
if (nRight == nLeft || nPos == nLeft)
{
return null;
}
nRight = nPos - 1;
}
else if (iCom > 0)
{
if (nRight == nLeft || nPos == nRight)
{
return null;
}
nLeft = nPos + 1;
}
else
{
return ld;
}
nPos = nLeft + (nRight - nLeft + 1) / 2;
}
break;
}
case s_null:
{
DListNote_<T> pNote = _first;
while (pNote != null)
{
//总结:Equals比较的永远是变量的内容是否相同，而= =比较的则是引用地址是否相同(前提:此种类型内部没有对Equals 或= = 进行重写操作，
//否则输出可能会有不同)。string 类型是个特例，因为他的内部对这两个都进行了重写。
if (item.compareTo(pNote.data) == 0)
{
return pNote;
}
/*
if (pNote.data.Equals(item))
{
return pNote;
}
*/
pNote = pNote.next;
}
break;
}
default:
{
return null;
}
}
return null;
}
/**
* Move last boolean.
*
* @param iIndex the index
* @return the boolean
*/
/// <summary>
/// 把索引为nIndex的节点移到最后
/// </summary>
/// <param name="nIndex"></param>
/// <returns></returns>
protected boolean moveLast(int iIndex)
{
DListNote_ pNote = indexOfNote(iIndex);
if (pNote != null)
{
if (pNote == _last)
return true;
if (pNote == _first) //此时最少两个节点
{
_first = _first.next;
_first.prev = null;
_last.next = pNote;
pNote.prev = _last;
_last = pNote;
}
else
{
pNote.prev.next = pNote.next;
pNote.next.prev = pNote.prev;
_last.next = pNote;
pNote.prev = _last;
_last = pNote;
}
return true;
}
return false;
}
/**
* Move first boolean.
*
* @param iIndex the index
* @return the boolean
*/
/// <summary>
/// 把索引为nIndex的节点移到最前
/// </summary>
/// <param name="nIndex"></param>
/// <returns></returns>
protected boolean moveFirst(int iIndex)
{
DListNote_ pNote = indexOfNote(iIndex);
if (pNote != null)
{
if (pNote == _first)
return true;
if (pNote == _last) //此时最少两个节点
{
_last.prev.next = null;
_last = _last.prev;
pNote.prev = null;
pNote.next = _first;
_first.prev = pNote;
_first = pNote;
}
else
{
pNote.prev.next = pNote.next;
pNote.next.prev = pNote.prev;
pNote.next = _first;
_first.prev = pNote;
pNote.prev = null;
_first = pNote;
}
return true;
}
return false;
}
/**
* Remove item boolean.
*
* @param pData the p data
* @return the boolean
*/
/// <summary>
/// 删除链表中的数据
/// </summary>
/// <param name="pData"></param>
/// <returns></returns>
public boolean RemoveItem(T pData)
{
if (_sortord == Sortord_.s_null)
{
DListNote_ pListItem = _first;
while (pListItem != null)
{
if (pListItem.data.equals(pData)) //找到一项
{
if (pListItem == _first) //删除的是第一个节点
{
if (_first.next != null)
{
_first.next.prev = null;
_first = _first.next;
}
else
{
_first = null;
_last = null;
}
}
else if (pListItem == _last) //删除的是最后一个节点
{
if (_last.prev != null)
{
_last.prev.next = null;
_last = _last.prev;
}
else
{
_first = null;
_last = null;
}
}
else //删除的是中间的一个节点
{
pListItem.next.prev = pListItem.prev;
pListItem.prev.next = pListItem.next;
}
--_count;
return true;
}
pListItem = pListItem.next;
}
return false;
}
else
{
return removeAt(bnarySearch(pData));
}
}
/**
* Delete node boolean.
*
* @param pListItem the p list item
* @return the boolean
*/
/// <summary>
/// 删除链表中的节点
/// </summary>
/// <param name="pListItem"></param>
/// <returns></returns>
protected boolean deleteNode(DListNote_ pListItem)
{
if (_count == 0 || pListItem == null)
{
return false;
}
DListNote_ pNote = _first.next;
while (pNote != null)
{
if (pNote == pListItem) //找到了
{
//pListItem->prev
if (pListItem.prev != null)
{
pListItem.prev.next = pListItem.next;
}
else //删除的是第一个节点
{
_first = pListItem.next;
}
//pListItem->next
if (pListItem.next != null)
{
pListItem.next.prev = pListItem.prev;
}
else //删除的是最后一个节点
{
_last = pListItem.prev;
}
break;
}
pNote = pNote.next;
}
if (pNote != null)
{
--_count;
return true;
}
return false;
}
/**
* 功能：清空所有元素的所有数据，并清空链表
* 创建时间：????/??/??
* 最后一次修改时间：2022-07-02
*/
public void clear(){
_count = 0;
DListNote_ pTemp1 = _first;
while (pTemp1 != null){
DListNote_ pTemp2 = pTemp1.next;
pTemp1.data = null;
pTemp1.next = null;
pTemp1.prev = null;
pTemp1 = pTemp2;
}
_first = null;
_last = null;
}
/**
* Remove at boolean.
*
* @param iIndex the index
* @return the boolean
*/
/// <summary>
/// 移除指定索引处的元素
/// </summary>
/// <param name="iIndex">要移除的元素的从零开始的索引。</param>
/// <returns>成功返回true,否则返回false</returns>
public Boolean removeAt(int iIndex)
{
if (iIndex < 0 || iIndex + 1 > _count) { return false; }
DListNote_ pNode = _first;
int iCount = 0;
while (pNode != null)
{
if (iCount == iIndex)
{
if (pNode == _first)
{
if (_first.next == null) //只有一个
{
clear();
return true;
}
else
{
_first = _first.next;
_first.prev = null;
--_count;
return true;
}
}
else if (pNode == _last)
{
if (_last.prev == null)
{
clear();
return true;
}
else
{
_last = _last.prev;
_last.next = null;
--_count;
return true;
}
}
else
{
pNode.prev.next = pNode.next;
pNode.next.prev = pNode.prev;
pNode = null;
--_count;
return true;
}
}
pNode = pNode.next;
++iCount;
}
return false;
}
/**
* Printlf.
*/
public void printlf(){
jp.p(toString());
}
/**
* 功能：删除一段链表，注意：pDeleteNoteStart 一定要在链表内。
*
* @param pDeleteNoteStart 开始删除的位置
* @param bDown 删除方向，向下还是向上，prev 为向上，next 为向上
* @param nCount 要删除的个数，包括 pDeleteNoteStart
* @return 返回实际删除的个数 作者：李锋 创建时间：2022/07/02 最后一次修改时间：2022/07/02
*/
public int removeNotes(DListNote_ pDeleteNoteStart,boolean bDown,int nCount){
if(_count <= 0 || nCount <= 0 || pDeleteNoteStart == null ) return 0;
if(pDeleteNoteStart == _first){ //如果删除的开始位置是链表中的第一个节点
if( bDown ){ //向下
int n = 0;
DListNote_ pTemp = _first;
//计数
while(pTemp != null){
++ n;
pTemp.data = null;
pTemp = pTemp.next;
if( n == nCount) break;
}
if(pTemp == null){
clear();
return _count;
}
else { //重新设置 _first
pTemp.prev = null;
_first = pTemp;
_count -= nCount;
return nCount;
}
}
else{ //向上，只删除一个,重新设置 _first
if(_count == 1){
clear();
}else{
-- _count;
_first.data = null;
DListNote_ pTemp = _first.next;
pTemp.prev = null;
_first = pTemp;
}
return 1;
}
}else if(pDeleteNoteStart == _last){ //如果删除的开始位置是链表中的最后一个节点
if( bDown ){ //向下,只删除一个,重新设置 _last
if(_count == 1){
clear();
}else{
-- _count;
_last.data = null;
DListNote_ pTemp = _last.prev;
pTemp.next = null;
_last = pTemp;
}
return 1;
}
else{ //向上
int n = 0;
DListNote_ pTemp = _last;
//计数
while(pTemp != null){
++ n;
pTemp.data = null;
pTemp = pTemp.prev;
if( n == nCount) break;
}
if(pTemp == null){
clear();
return _count;
}
else { //重新设置 _last
pTemp.next = null;
_last = pTemp;
_count -= nCount;
return nCount;
}
}
}else{
if( bDown ){
int n = 0;
DListNote_ pTemp = pDeleteNoteStart;
//计数
while(pTemp != null){
++ n;
pTemp.data = null;
pTemp = pTemp.next;
if( n == nCount) break;
}
if(pTemp == null) //_last也删掉了
{
pDeleteNoteStart.prev.next = null;
_last = pDeleteNoteStart.prev;
_count -= n;
return n; //实际删除个数
}
else {
pDeleteNoteStart.prev.next = pTemp;
pTemp.prev = pDeleteNoteStart.prev;
_count -= nCount;
return nCount;
}
}
else
{
int n = 0;
DListNote_ pTemp = pDeleteNoteStart;
//计数
while(pTemp != null){
++ n;
pTemp.data = null;
pTemp = pTemp.prev;
if( n == nCount) break;
}
if(pTemp == null) { //_first 也删掉了
pDeleteNoteStart.next.prev = null;
_first = pDeleteNoteStart.next;
_count -= n;
return n; //实际删除个数
}
else {
pTemp.next = pDeleteNoteStart.next;
pDeleteNoteStart.next.prev = pTemp;
_count -= nCount;
return nCount;
}
}
}
}
/**
* 添加一个元素，并把它放在首位，其它元素后移,如果后面的元素删除，总无素个数不变，如果无素个数为零，则添加一个无素。
*
* @param Item the item
* @param bRemoveLast 创建时间： 2022-04-19 最后一次修改时间：2022-04-19
*/
public void stackPush(T Item, boolean bRemoveLast){
if (_count == 0){
add(Item);
}
else if (_count == 1){
if (bRemoveLast){
_first.data = Item;
}
else{
//把无素放在最前
DListNote_ dnNew = new DListNote_(Item);
_first.prev = dnNew;
dnNew.next = _first;
_first = dnNew;
++_count;
}
}
else{
if (bRemoveLast){
//删除最后一个元素
_last = _last.prev;
_last.next = null;
//把无素放在最前
DListNote_ dnNew = new DListNote_(Item);
_first.prev = dnNew;
dnNew.next = _first;
dnNew.prev = null;
_first = dnNew;
}
else {
//把无素放在最前
DListNote_ dnNew = new DListNote_(Item);
_first.prev = dnNew;
dnNew.next = _first;
dnNew.prev = null;
_first = dnNew;
++_count;
}
}
}
/**
* Stack pop.
*/
/// <summary>
/// 删除第一个元素，出栈
/// </summary>
/// 创建时间： 2022-04-19 最后一次修改时间：2022-04-19
public void stackPop(){ removeAt(0); }
/**
* To array list array list.
*
* @return the array list
*/
public ArrayList<T> toArrayList(){
ArrayList<T> la = new ArrayList<T>();
for(T value : this){
la.add(value);
}
return la;
}
/**
* 功能: 转为字符串格式 类名：{ a 分隔符 b 分隔符 c }
*
* @param separator 分隔符
* @return string
* @author 李锋
* @since 创建日期 :2022-08-08,最后一次修改日期:2022-08-08
*/
public String toString(String sConnector){
String info = this.getClass() + " :\t";
//info += "{";
int i = 0;
for ( T t : this) {
info += t.toString();
++ i ;
if( i != _count)
info += sConnector;
}
//info += "}";
return info;
}
/**
* 功能: 转为字符串格式 类名：{ a , b , c }
* @return
* @since 创建日期:2022-08-08,最后一次修改日期:2022-08-08
* @author 李锋
*/
@Override
public String toString() {
return toString(",");
}
}
class DListNoteEnum_<T> implements Iterator<T> {
private DListNote_<T> _dnCurr;
private int _index = -1;
public DListNoteEnum_(DListNote_<T> dn){
_dnCurr = dn;
}
@Override
public boolean hasNext() {
return _dnCurr.next != null;
}
@Override
public T next() {
++ _index;
if( _index > 0){
_dnCurr = _dnCurr.next;
}
return _dnCurr.data;
}
}
