#ifndef _LIST_H__
#define _LIST_H__
//TODO :add header body code here
#include "cassert.h"
#include "node.h"
template<typename T>
class CList{
protected:
int m_nCount;
CNode<T> *m_pNodeHead;
public:
CList();
CList(const T &initdata);
~CList();
public:
int IsEmpty() const;
int GetCount() const;
int InsertBefore(const int pos,const T data);
int InsertAfter(const int pos,const T data);
int AddHead(const T data);
int AddTail(const T data);
void RemoveAt(const int pos);
void RemoveAll();
void RemoveHead();
void RemoveTail();
T& GetTail();
T GetTail() const;
T& GetHead();
T GetHead() const;
T& GetAt(const int pos);
T GetAt(const int pos) const;
void SetAt(const int pos,T data);
int Find(const T data) const; };
//the implement of the function in the class
template<typename T>
inline CList<T>::CList():m_nCount(0),m_pNodeHead(NULL){}
template<typename T>
inline CList<T>::CList(const T &initdata):m_nCount(0),m_pNodeHead(NULL){ AddHead(initdata); }
template<typename T>
inline CList<T>::~CList(){ RemoveAll(); }
template<typename T>
inline int CList<T>::IsEmpty() const{ return 0==m_nCount; }
template<typename T>
inline int CList<T>::GetCount() const { return m_nCount; }
template<typename T>
inline int CList<T>::AddHead(const T data){
//define a new node
CNode<T> *pNewNode;
//allocate
pNewNode=new CNode<T>;
if (pNewNode==NULL) { return 0; }
//loading data
pNewNode->data=data;
pNewNode->next=m_pNodeHead;
m_pNodeHead=pNewNode;
//the number of node
++m_nCount;
return 1;
}
template<typename T>
inline int CList<T>::AddTail(const T data){ return InsertAfter(GetCount(),data); }
//if success ,returning the position of the new node
//if failed ,return 0;
template<typename T>
inline int CList<T>::InsertBefore(const int pos,const T data){
int i;//i:be used to find the insert position
CNode<T> *pNewNode;
CNode<T> *pTemNode1;
CNode<T> *pTemNode2;
pNewNode=new CNode<T>;
if (pNewNode==NULL) { return 0; }
//loading data for the new node
pNewNode->data=data;
//if the list is empty,replace the head-node for the new node
if (NULL==m_pNodeHead) { pNewNode->next=NULL; m_pNodeHead=pNewNode; ++m_nCount; return m_nCount; }
//is the pos valid?
assert(1<=pos);
assert(pos<=m_nCount);
//insert before the head node,pos=1
if (1==pos) { pNewNode->next=m_pNodeHead; m_pNodeHead=pNewNode; ++m_nCount; return pos; }
//if the list is not empty
//seek the position of the list,insert the new node before it
pTemNode1=m_pNodeHead;
for (i=1;i<pos;i++) {
pTemNode2=pTemNode1;
pTemNode1=pTemNode1->next;
}
pNewNode->next=pTemNode1;
pTemNode2->next=pNewNode; return pos;
}
//if success ,returning the position of the new node
//if failed ,return 0
template<typename T>
inline int CList<T>::InsertAfter(const int pos,const T data){
int i;
CNode<T> *pTemNode;
CNode<T> *pNewNode;
pNewNode=new CNode<T>;
if (pNewNode==NULL) { return 0; }
pNewNode->data=data;
//if the list is empty ,replace the head node for the new node
if (NULL==m_pNodeHead) { pNewNode->next=NULL; m_pNodeHead=pNewNode; ++m_nCount; return m_nCount; }
//is the pos valid?
assert(1<=pos); assert(pos<=m_nCount);
//if the list is not empty,
//seek the position of the list ,insert the new node after it
pTemNode=m_pNodeHead;
for (i=1;i<pos;i++) { pTemNode=pTemNode->next; }
pNewNode->next=pTemNode->next;
pTemNode->next=pNewNode;
++m_nCount; return pos+1;
}
template<typename T>
inline void CList<T>::RemoveAt(const int pos){
//if the pos valid?
assert(1<=pos); assert(pos<=m_nCount);
int i;
CNode<T> *pTemNode1;
CNode<T> *pTemNode2;
pTemNode1=m_pNodeHead;
//if remove the head ,pos=1;
if (pos==1) { m_pNodeHead=m_pNodeHead->next; goto EXIT1; }
for (i=1;i<pos;i++) {
//we will get the previous node of the target node after for loop finished,
//it will be stored into pTemNode2
pTemNode2=pTemNode1;
pTemNode1=pTemNode1->next;
}
pTemNode2->next=pTemNode1->next;
EXIT1:
delete pTemNode1;
--m_nCount;
}
template<typename T>
inline void CList<T>::RemoveHead(){ assert(0!=m_nCount); return RemoveAt(1); }
template<typename T>
inline void CList<T>::RemoveTail(){ assert(0!=m_nCount); return RemoveAt(m_nCount); }
template<typename T>
inline void CList<T>::RemoveAll(){
int i;
int mCount;
mCount=m_nCount;
CNode<T> *pTemNode;
for (i=1;i<=mCount;i++) {
pTemNode=m_pNodeHead->next;
delete m_pNodeHead;
m_pNodeHead=pTemNode;
}
m_nCount=0;
}
template<typename T>
inline T& CList<T>::GetTail(){
int i;
int mCount;
mCount=m_nCount;
CNode<T> *pTemNode;
pTemNode=m_pNodeHead;
for (i=1;i<mCount;i++) {
pTemNode=pTemNode->next;
}
return pTemNode->data;
}
template<typename T>
inline T CList<T>::GetTail() const{
int i;
int mCount;
mCount=m_nCount;
CNode<T> *pTemNode;
pTemNode=m_pNodeHead;
for (i=1;i<mCount;i++) {
pTemNode=pTemNode->next;
}
return pTemNode->data;
}
template<typename T>
inline T& CList<T>::GetHead(){ ASSERT(0!=m_nCount); return m_pNodeHead->data; }
template<typename T>
inline T CList<T>::GetHead() const{ ASSERT(0!=m_nCount); return m_pNodeHead->data; }
template<typename T>
inline T& CList<T>::GetAt(const int pos){
ASSERT(1<=pos);
ASSERT(pos<=m_nCount);
int i;
CNode<T> *pTemNode;
pTemNode=m_pNodeHead;
for (i=1;i<pos;i++) {
pTemNode=pTemNode->next;
}
return pTemNode->data;
}
template<typename T>
inline T CList<T>::GetAt(const int pos) const{
ASSERT(1<=pos);
ASSERT(pos<=m_nCount);
int i;
CNode<T> *pTemNode;
pTemNode=m_pNodeHead;
for (i=1;i<pos;i++) { pTemNode=pTemNode->next; }
return pTemNode->data;
}
template<typename T>
inline void CList<T>::SetAt(const int pos,T data){
ASSERT(1<=pos);
ASSERT(pos<=m_nCount);
int i;
CNode<T> *pTemNode;
pTemNode=m_pNodeHead;
for (i=1;i<pos;i++) { pTemNode=pTemNode->next; }
pTemNode->data=data;
}
template<typename T>
inline int CList<T>::Find(const T data) const{
int i;
int mCount;
mCount=m_nCount;
CNode<T> *pTemNode;
pTemNode=m_pNodeHead;
for (i=1;i<=mCount;i++) {
if (data==pTemNode->next)
{ return i+1; }
pTemNode=pTemNode->next;
}
return 0; }
#endif
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef __CNODE_H__
#define __CNODE_H__
template<typename T>
class CNode
{
public:
T data;
CNode<T> *next;
CNode() : data(T()), next(NULL) {}
CNode(const T &initdata) : data(initdata), next(NULL) {}
CNode(const T &initdata, CNode<T> *p) : data(initdata), next(p) {}
};
#endif
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
预编译：
#include 该指令指示编译器将xx文件的全部内容插入此处
1.若用<>括起来，文件在系统的INCLUDE目录中找
2.若用“ ”括起来，文件在当前系统中寻找。
#define
1.定义标识，标识范围是整个程序，
2.定义常数，不建议用宏定义，用const定义常数更好些，编译器在安全检查的时候对const有类型安全检查，但是对宏定义只是字符替换
3.定义函数， ey:#define get_max(a,b) ((a)>(b)?(a):(b)),改变变量值的时候不建议这样用，ey:get_max(a++,b--),
#if ,#else ,#endif,#ifndef,
条件编译
ey:
#ifndef x
#define x
//p
#endif
这样做有什么好处呢，举个例子说：
文件a.h 和b.h 都包含 c.h,通过编译得到d文件，如果没有用#ifndef和#endif,很有可能导致大量的神明冲突。
最后是断言assert，下次再说。