顺序表是在计算机内存中以数组的形式保存的线性表。栈和队列都是具有特殊存取方式的顺序表。
线性表采用顺序存储方式存储就称为顺序表。
顺序表比栈和队列更有普遍性，大概有以下功能
1 #ifndef List_hpp 2 #define List_hpp 3 4 class List 5 { 6 public: 7 List(int size); //创建顺序表 8 ~List(); //销毁顺序表 9 void ClearList(); //清空顺序表 10 bool ListFull() const; //顺序表判满 11 bool ListEmpty() const; //顺序表判空 12 int ListLength(); //顺序表长度 13 bool GetElem(int i,char *p);//找到第i个元素 14 int LocateElem(char *p); //找到元素位置 15 bool PriorElem(char *currentElem,char *preElem);//获得目标元素的前驱 16 bool NextElem(char *currentElem,char *nextElem);//获得目标元素的后继 17 bool ListInsert(int i,char *p); //在位置i插入元素 18 bool ListDelete(int i,char *p); //删除位置i元素 19 void ListTraverse(); //遍历顺序表 20 private: 21 char *_pList; 22 int _iSize; 23 int _iListLen; 24 int _Index; 25 }; 26 27 #endif /* List_hpp */
根据需要，加入了一个成员变量_Index用作游标
线性表的通用函数实现(构造，销毁，清空，判满，判空，求长度）
1 List::List(int size) 2 { 3 _iSize=size; 4 _pList=new char[_iSize]; 5 ClearList(); 6 } 7 8 List::~List() 9 { 10 delete[] _pList; 11 _pList=NULL; 12 } 13 14 void List::ClearList() 15 { 16 _iListLen=0; 17 } 18 19 bool List::ListFull() const 20 { 21 if(_iListLen==_iSize) 22 { 23 return true; 24 } 25 else 26 { 27 return false; 28 } 29 } 30 31 bool List::ListEmpty() const 32 { 33 if(_iListLen==0) 34 { 35 return true; 36 } 37 else 38 { 39 return false; 40 } 41 } 42 43 int List::ListLength() 44 { 45 return _iListLen; 46 }
根据位置求元素和已知元素求位置
位置求元素要先判断该位置是否存在元素，根据元素求元素位置同样要判断顺序表中是否存在该元素，想用c++的异常与抛出来做，但是没学好，明天再专门整理异常与抛出的知识。
1 bool List::GetElem(int i,char *p) 2 { 3 if(i<0||i>=_iListLen) 4 { 5 return false; 6 } 7 else 8 { 9 *p=_pList[i]; 10 return true; 11 } 12 } 13 14 int List::LocateElem(char *p) 15 { 16 bool Elem=false; 17 for(_Index=0;_Index<_iListLen;_Index++) 18 { 19 if(*p==_pList[_Index]) 20 { 21 Elem=true; 22 break; 23 } 24 } 25 if(Elem) 26 { 27 return _Index; 28 } 29 else 30 { 31 std::cout<<"error!"<<std::endl; 32 return -1; 33 } 34 }
求目标元素的前驱与后继，要先去的目标元素位置，然后判断是否有前驱或后继。
1 bool List::PriorElem(char *currentElem,char *preElem) 2 { 3 LocateElem(currentElem); 4 if(_Index>0&&_Index<_iListLen) 5 { 6 *preElem=_pList[_Index-1]; 7 return true; 8 } 9 else 10 { 11 return false; 12 } 13 } 14 15 bool List::NextElem(char *currentElem,char *nextElem) 16 { 17 LocateElem(currentElem); 18 if(_Index>=0&&_Index<_iListLen-1) 19 { 20 *nextElem=_pList[_Index+1]; 21 return true; 22 } 23 else 24 { 25 return false; 26 } 27 }
在位置i插入元素是，要判断顺序表是否为满，再判断该位置是否超过了顺序表长
1 bool List::ListInsert(int i,char *p) 2 { 3 if(ListFull()) 4 { 5 return false; 6 } 7 else 8 { 9 if(i<0||i>_iListLen) 10 { 11 return false; 12 } 13 else 14 { 15 for(_Index=_iListLen;_Index>i;_Index--) 16 _pList[_Index]=_pList[_Index-1]; 17 _pList[i]=*p; 18 _iListLen++; 19 return true; 20 } 21 } 22 }
删除元素时，同时将被删除的元素取了出来，同样要先判断是否为空，再判断位置是否超过了表长
1 bool List::ListDelete(int i,char *p) 2 { 3 if(ListEmpty()) 4 { 5 return false; 6 } 7 else 8 { 9 if(i<0||i>=_iListLen) 10 { 11 return false; 12 } 13 else 14 { 15 *p=_pList[i]; 16 for(_Index=i;_Index<_iListLen;_Index++) 17 _pList[_Index]=_pList[_Index+1]; 18 _iListLen--; 19 return true; 20 } 21 } 22 }
最后，通用的遍历收尾
1 void List::ListTraverse() 2 { 3 using namespace std; 4 5 cout<<endl; 6 for(_Index=0;_Index<_iListLen;_Index++) 7 { 8 cout<<_pList[_Index]<<endl; 9 } 10 cout<<endl; 11 }
原文：http://www.cnblogs.com/Bird-of-Paradise/p/6366127.html