飘云阁数组篇 - Powered by Discuz! Archiver

Nisy 发表于 2009-9-1 19:55:34

数组篇

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

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

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

谢绝转载 Ths~~

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

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

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

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

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

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

这个东西我理解起来比较别扭，因为他是这样的： a[ i ] == i == *(a+i)==> pLast = *(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 发表于 2009-9-1 19:57:21

用我设计的参数来实现顺序表

//----------------------------------
//
// 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;
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=data;          // 这里是浅Copy 无需重载等号 // nLast == *(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=pBuffer;
}
pBuffer=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;
for(int i=nIndex;i<nLength;i++)// Err
   pBuffer=pBuffer;
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;
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 发表于 2009-9-1 20:03:23

用老师课上的参数来实现顺序表

//----------------------------------
//
// 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;
}

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=data;          // 这里是浅Copy 无需重载等号 // nLast == *(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=pFirst;
}
pFirst=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;
for(int i=nIndex;i<pLast-pFirst;i++)// Err
   pFirst=pFirst;
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;
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 --------------------

超然发表于 2009-9-1 21:15:17

我是来坐沙发，顶贴的。

页: [1]

飘云阁's Archiver

数组篇

用我设计的参数来实现顺序表

用老师课上的参数来实现顺序表