《数据结构与算法》 |
您所在的位置：网站首页 › linklist的作用 › 《数据结构与算法》 |
《数据结构与算法》
|
《数据结构与算法》——线性表之顺序表（SqList）总结
从前天开始着手复习线性表部分，整了3个下午才用C++对顺序表的部分内容进行了成功实现，下面就简单进行以下总结。 目录 《数据结构与算法》——线性表之顺序表总结 定义 class SqList 方法实现 错误 难点 参考文献 定义线性表：具有线性存储结构的抽象数据类型，它是由n个数据元素组成的有限序列。其中数据元素可以是很多种，int、string、char甚至是自定义类型。 课本上还有个定义是说其他几个名词的关系：若干数据项组成了一条记录（数据元素），含有大量记录的线性表被称为文件。 在书上对抽象数据类型的线性表定义如下图：
线性表分为顺序表和链表，在本文中将对线性表中的顺序表以C++语言的方式，构建SqList类，并对其类方法进行实现。 class SqList class SqList { private: T *data=NULL;//设置成动态的 int len,Max; int step; public: SqList(int Max , T t );//{//构造函数, int step = 50 void InitList(int Max , T t);//初始化 int length(); int LocateElem(T elem);//按值查找 T GetElem(int i); //按位查找 void ListtInsert(int i ,T elem); void ListDelete(T elem);//删除元素 void PrintList(); bool Empty(); void DestroyList(); void MergeList(SqList lb);//合并两个表，有序 ~ SqList();//析构函数 }; 方法实现 /*编译环境： win10专业版 DEV C++ 5.11 TDM-GCC 4.9.2 64bit */ #include #include using namespace std; #define STEP 50 #define OVERFLOW 0 template class SqList { private: T *data=NULL;//设置成动态的 int len,Max; int step; public: SqList(int Max , T t );//{//构造函数, int step = 50 void InitList(int Max , T t);//初始化 int length(); int LocateElem(T elem);//按值查找 T GetElem(int i); //按位查找 void ListtInsert(int i ,T elem); void ListDelete(T elem);//删除元素 void PrintList(); bool Empty(); void DestroyList(); void MergeList(SqList lb);//合并两个表，有序 ~ SqList();//析构函数 }; template SqList::SqList(int Max , T t){//构造函数, int step = 50 /* * 初始化最大容量，元素类型&错误标记，步长 */ T *tt = (T*)malloc(sizeof(T)*Max); if(!tt){ coutlen = 0; this->step = STEP; } template void SqList::InitList(int Max , T t){//初始化 SqList(Max , t); } template int SqList::length(){//返回顺序表长度 return len; } template int SqList::LocateElem(T elem){//按值查找 int i = 0; for( ; ilen && data[i]!= elem;i++); if( i len) return i; return 0;//无此值 } template T SqList::GetElem(int i){ //按位查找 if(ilen && i>0 ) return data[i]; return data[0]; } template void SqList::ListtInsert(int i ,T elem){//按位插值 if (i==0||i>=this->len+2) return ; if(this->len >= this->Max) {//重新分配内存块 T * Temp = (T *) realloc(this->data, sizeof(T)*(this->Max + this->step)); if (Temp == NULL)// { exit(OVERFLOW);//step; } this->len ++;//长度增加 int j = this->len ; for( ; j>i ;j--){ this->data[j] = this->data[j-1]; } this->data[j] = elem; } template void SqList::ListDelete(T elem){//删除元素 int i=0; while(idata[++i]!=elem); if(i==len&&this->data[i]!=elem) return ; else{ while(idata[i] = this->data[i+1]; i++; } this->len--; } } template void SqList::PrintList(){//输出顺序表 coutlen + lb.len ){//空间不足 //对A扩充空间 T *tem = (T*) realloc(this->data, sizeof(T)*(this->Max + lb.Max)); if (!tem) //exit(OVERFLOW); this->data = tem ; flag=0; } else flag = 1; //比较大小合并 j = 1; while(jdata, sizeof(T)*(this->Max + lb.Max)); lb.PrintList(); if (!Temp) exit(OVERFLOW); this->data = Temp; j=1; while(jdata[len+j] = lb.data[j++]; } } this->Max = flag?this->Max :this->Max + lb.Max; this->len = this->len + lb.len; } template SqList::~SqList(){//析构 len=0; free(this->data); this->data = NULL; } int main() { SqList l(50,-1); cout |
【本文地址】