数组篇

Nisy

//======================================================

总结一下 写给在数结构学习上比较吃力的科瑞学员

我水平有限 总结的不咋地 但总比看热闹的更有意义

谢绝转载 Ths~~

//======================================================

    顺序表和链表统称为顺序表。链表抛开链路层，可以当作顺序表来操作。

    数据结构，就是为了按照我们的想法实现数据在内存的存放和处理。对于同一块内存，我们在建立结构体的时候，需要用几个参数来实现对该内存的管理，比如一块内存，我们用顺序表来存储数据，首先需要知道该内存的起始地址、大小、存储的数据个数。这些参数是我们管理该内存的前提。

顺序表需要实现以下几个功能（必须的）：
//------------------------------------------
//
//  创建 <==> 构造函数
//  清空  
//  销毁 <==> 析构函数
//  再实现：追加、插入、删除、查找
//  最后遍历
//
//------------------------------------------

我们讲课的时候所取的参数为：
class Array  
{
private:
   T * pFirst;
   T * pLast;
   int nSpace;
};

这里管理内存使用量的参数是pLast，这就使我们在追加数据的语句为 pLast[0]=data 来实现。

这个东西我理解起来比较别扭，因为他是这样的： a[ i ] == i[a] == *(a+i)  ==> pLast[0] = *(pLast+0)

所以我取的要素为：
class Array  
{
private:
   T * pBuffer;  // 空间地址
   int nLength;  // 长度 也就是元素的个数
   int nSpace;   // 空间大小（最多可容纳的元素个数）
};

  大家在发帖时 [ i ] 指令 将导致代码的字母变斜
  这时候 只需要在帖子左侧 禁用 Discuz!代码 打上勾即可。

  PS: 不要使用 code 这个代码  如果需要将代码圈起来 请使用 quote 这组指令

//=========================================

//------------------------------------------
//
// Code By : Nisy/KeRui05
// main.c 文件
//
//------------------------------------------

#include "array.h"
#include <iOStream>
using namespace std;

int main(int argc, char* argv[])
{
    char ch0='0';
    char ch1='N';
    char ch2='i';
    char ch3='s';
    char ch4='y';
    Array<char> myarray(3);
    myarray.AppendArray(ch1);
    myarray.AppendArray(ch2);
    myarray.AppendArray(ch3);
    myarray.AppendArray(ch4);
    myarray.InsertArray(2,ch4);
    myarray.DeleteArray(4,ch0);

    Array<char>::iterator AutoPtr = myarray.Begin();
    while(AutoPtr != myarray.End())
    {
        printf("%c",* AutoPtr);
        AutoPtr++;
    }
    cout<<endl;
    return 0;
}

//--------------------- main.c End ---------------------

Nisy

//----------------------------------
//
// Code By: Nisy/KeRui05
// Array.h 文件
//
//----------------------------------


template <typename T>
class Array  
{
private:
   T * pBuffer;
   int nLength;
   int nSpace;
public:
    // 创建、销毁
   Array(int nSize);
   virtual ~Array();
public:
    // 清空、追加、插入、删除、取元素
    void ClearArray();
    int AppendArray(T& data);    // 在添加数据时 如果是浅Copy 则直接赋值 否则重载'='
    int InsertArray(int nIndex,T& data);
    int DeleteArray(int nIndex,T& data);
    int GetElement(int nIndex,T& data);
public:
    // 判空、判满、释放空间、申请空间
    int IsFull();
    int IsEmpty();
    void Release();
    void AllocSpace();
public:
    T * Begin() {return pBuffer;}
    T * End() {return pBuffer+nLength;}
    // 开始模拟迭代器
    class iterator
    {
    private:
        T * pCur;
    public:
        iterator(T * cur)
        {
            pCur=cur;
        }
        T* operator++(int)
        {
            T * pTemp = pCur;
            pCur++;
            return pTemp;
        }
        bool operator!=(T * cur)
        {
            return pCur!=cur;
        }
        T operator*()
        {
            return * pCur;
        }
    };
};

//================================================== 函数的定义

//================================ 实现创建、销毁、清空

template <typename T>
Array<T>::Array(int nSize)
{
    pBuffer = new T[nSpace=nSize];
    nLength = 0;
}

template <typename T>
Array<T>::~Array()
{
    Release();
}

template <typename T>
void Array<T>::ClearArray()
{
    nLength = 0;
}

//================================ 实现追加、插入、删除、查找

template <typename T>
int Array<T>::AppendArray(T& data)
{
    if(IsFull())
        AllocSpace();
    pBuffer[nLength]=data;            // 这里是浅Copy 无需重载等号 // nLast[0] == *(nLast+0)  
    nLength++;
    return 1;
}

template <typename T>
int Array<T>::InsertArray(int nIndex,T& data)
{
    if(IsEmpty())return 0;
    for(int i=nLength;i>=nIndex;i--)
    {
        pBuffer[i]=pBuffer[i-1];
    }
    pBuffer[nIndex-1]=data;
    nLength++;
    return 1;
}

template <typename T>
int Array<T>::DeleteArray(int nIndex,T& data)
{
    if(nIndex < 1 || nIndex > nLength || IsEmpty()) return 0;
    data=pBuffer[nIndex-1];
    for(int i=nIndex;i<nLength;i++)  // Err
        pBuffer[i-1]=pBuffer[i];
    nLength--;
    return 1;
}

template <typename T>
int Array<T>::GetElement(int nIndex,T& data)
{
    ;
}

//================================ 实现空间释放、空间申请、判空、判满

template <typename T>
void Array<T>::Release()
{
    if(pBuffer)
    {
        delete[] pBuffer;
        pBuffer=NULL;
    }
}

template <typename T>
void Array<T>::AllocSpace()
{
    int nNewSize = nSpace * 2;  // 这里偷个懒 直接* 2操作
    T * pNewSpace = new T[nNewSize];
    if(!pNewSpace) return;      // 申请失败 直接挂掉
    memcpy(pNewSpace,pBuffer,sizeof(T)*nSpace);
    Release();
    pBuffer = pNewSpace;
    nSpace = nNewSize;
}

template <typename T>
int Array<T>::IsFull()
{
    return nLength == nSpace;
}

template <typename T>
int Array<T>::IsEmpty()
{
    return nLength == 0;
}

//-------------- Array.h End --------------------

Nisy

//----------------------------------
//
// Code By: Nisy/KeRui05
// Array.h 文件
//
//----------------------------------


template <typename T>
class Array  
{
private:
   T * pFirst;
   T * pLast;
   int nSpace;
public:
    // 创建、销毁
   Array(int nSize);
   virtual ~Array();
public:
    // 清空、追加、插入、删除、取元素
    void ClearArray();
    int AppendArray(T& data);    // 在添加数据时 如果是浅Copy 则直接赋值 否则重载'='
    int InsertArray(int nIndex,T& data);
    int DeleteArray(int nIndex,T& data);
    int GetElement(int nIndex,T& data);
public:
    // 判空、判满、释放空间、申请空间
    int IsFull();
    int IsEmpty();
    void Release();
    void AllocSpace();
    T * Begin() {return pFirst;}
    T * End() {return pLast;}
public:
    // 开始模拟迭代器
    class iterator
    {
    private:
        T * pCur;
    public:
        iterator(T * cur)
        {
            pCur=cur;
        }
        T* operator++(int)
        {
            T * pTemp = pCur;
            pCur++;
            return pTemp;
        }
        bool operator!=(T * cur)
        {
            return pCur!=cur;
        }
        T operator*()
        {
            return * pCur;
        }
    };
};

//================================================== 函数的定义

//================================ 实现创建、销毁、清空

template <typename T>
Array<T>::Array(int nSize)
{
    pFirst = pLast = new T[nSpace=nSize];
}

template <typename T>
Array<T>::~Array()
{
    Release();
}

template <typename T>
void Array<T>::ClearArray()
{
    pLast = pFirst;
}

//================================ 实现追加、插入、删除、查找

template <typename T>
int Array<T>::AppendArray(T& data)
{
    if(IsFull())
        AllocSpace();
    pLast[0]=data;            // 这里是浅Copy 无需重载等号 // nLast[0] == *(nLast+0)  
    pLast++;
    return 1;
}

template <typename T>
int Array<T>::InsertArray(int nIndex,T& data)
{
    if(IsEmpty())return 0;
    for(int i=pLast-pFirst;i>=nIndex;i--)
    {
        pFirst[i]=pFirst[i-1];
    }
    pFirst[nIndex-1]=data;
    pLast++;
    return 1;
}

template <typename T>
int Array<T>::DeleteArray(int nIndex,T& data)
{
    if(nIndex < 0 || nIndex > pLast - pFirst || IsEmpty()) return 0;
    data=pFirst[nIndex-1];
    for(int i=nIndex;i<pLast-pFirst;i++)  // Err
        pFirst[i-1]=pFirst[i];
    pLast--;
    return 1;
}

template <typename T>
int Array<T>::GetElement(int nIndex,T& data)
{
    ;
}

//================================ 实现空间释放、空间申请、判空、判满

template <typename T>
void Array<T>::Release()
{
    if(pFirst)
    {
        delete[] pFirst;
        pFirst=NULL;
    }
}

template <typename T>
void Array<T>::AllocSpace()
{
    int nNewSize = nSpace * 2;  // 这里偷个懒 直接* 2操作
    T * pNewSpace = new T[nNewSize];
    if(!pNewSpace) return;      // 申请失败 直接挂掉
    memcpy(pNewSpace,pFirst,sizeof(T)*nSpace);
    Release();
    pFirst = pNewSpace;
    pLast = pFirst + nSpace;
    nSpace = nNewSize;
}

template <typename T>
int Array<T>::IsFull()
{
    return pLast == pFirst + nSpace;
}

template <typename T>
int Array<T>::IsEmpty()
{
    return pLast == pFirst;
}

//-------------- Array.h End --------------------

超然

我是来坐沙发，顶贴的。