数据结构_SeqList顺序表（C 实现
前言：此类笔记仅用于个人复习，内容主要在于记录和体现个人理解，详细还请结合bite课件、录播、板书和代码。
[toc]
前言&注意事项
有些函数没有修改成员数据的要求，防止成员函数被修改，将只有读取要求的函数设为常函数（只读函数 用 C 实现，有很多优势，其中一个就是对象可以直接访问并修改数据成员，不用再想要修改的时候再传地址什么的 ==assert果然还是太暴力了，能不用就不用吧，但是一定要记住要判断 表指针 为空的情况==
- ==可以抛出异常信号 (建议用这个，因为运行错误的时候知道原因==
- ==可以直接返回==
- 判断指针head为空的方式
if(!head) // if(!head)等价于if(head==NULL),head==NULL是head为空时等式成立，值为真 // head为空的话head就相当于0（假），非空就是真，所以当head为空的时候，!head就是真 throw nullPointer();//这里使用了抛出异常信号的方式,而且抛出的是一个匿名对象(因为要的是它的类型，没必要给对象命名了) //如果采用直接返回的方式 if(!head) return;//直接返回的话，在有返回类型的函数里面可能会报错 //以上两者都可以终止函数，不过直接return只能用在无返回值函数上，return本质是终止函数运行并返回NULL 其他注意事项在代码注释以及code日记中体现
顺序表实现方法
==注意：这个是带哨兵位的头结点的顺序表！！==
==但是实际上完全没有必要在顺序表上用哨兵位！因为根本不需要找头结点！而且一般情况下顺序表就是不用的，所以用了哨兵位很容易搞混！！！！==
是因为学校的数据结构教材用了才写上的！！教材不好
seqList.h #include<iostream> using namespace std; //专门作为异常信息的类（用于异常处理抛出）; class outofsize { };//用于判断非法访问 class nullPointer { };//用于判断空指针，此处主要用于判断 扩容是否失败 以及 头指针是否为空 template<class slDataType> class seqList { private: slDataType* elem; //用数组实现顺序表 int size; //顺序表实际大小 int capacity; //顺序表容量（能存储的除了哨兵位的头结点之外的实际有效数据的个数 void doubleCapacity(); //扩容函数；不过这里没必要单独写出来，只有在添加数据的时候有可能会调用到，其他时候不会用到，所以不会产生函数的复用，不用单独构建这个函数，直接包含在添加数据的函数里面就行 public: seqList(int Size = 10); //初始化顺序表 bool seqListEmpty() const; //判空，空则返回真，否则返回假 bool seqListFull() const; //判满 void seqListPushHead(slDataType x); //头插 void seqListPushBack(slDataType x); //尾插 void seqListPopHead(); //头删 void seqListPopBack(); //尾删 void seqListInsert(int pos, slDataType& data); //在任意位置pos插入；此处对元素数据运用了引用，不用再构建形参局部变量，可以减少一点空间开辟，不过个人感觉没有也无伤大雅 void seqListErase(int pos); //删除pos的元素 void seqListRemove(int pos, slDataType& e); //删除pos处的元素，并赋值给e（这里才体现引用的用处 slDataType seqListGet(int pos) const; //返回pos处的元素 int seqListFind(slDataType& data) const; //返回值等于data的元素的位置,没有则返回0 int seqListLength() const; //返回顺序表长度 void seqListDestory(); //清除顺序表，使其成为空表 ~seqList() { }; //析构函数 }; seqList.cpp #include"seqList.h" template<class slDataType> seqList<slDataType>::seqList(int Size)//初始化顺序表 { this->elem = new slDataType[Size];//开辟动态数组 if (!elem) throw nullPointer(); this->size = 0; this->capacity = Size-1;//保留第一个元素作为哨兵位的头结点（不过个人认为在顺序表这里没有必要，链表那里才能体现出哨兵位头结点的好处） } template<class slDataType> void seqList<slDataType>::doubleCapacity()//扩容函数 { assert(elem);//感觉判空的时候不如直接用assert，因为为了判空就用异常处理有些大材小用，而且只在判空的时候用assert，这样就直到程序一中断就说明是空指针 //所以关于指针可能为空的情况，我在除了这个函数之外的地方都用的assert，这个用异常处理结构太麻烦了,直接暴力检查就ok slDataType* newElem = new slDataType[capacity * 2]; if (!newElem) throw nullPointer(); for (int i = 1;i <= size; i )//注意，因为是有哨兵位的，所以i的范围是1（头）到size（尾） { newElem[i] = elem[i]; } delete []elem; elem = newElem; capacity = capacity * 2 - 1;//第一个结点要留给哨兵位，capacity是实际能存储的有效数据的个数 //到了这里，感觉写顺序表用哨兵位的头结点真的是，麻烦又没有必要 } template<class slDataType> bool seqList<slDataType>::seqListEmpty()const//判空，空则返回真，否则返回假 { if(!elem) throw nullPointer(); return size == 0; } template<class slDataType> bool seqList<slDataType>::seqListFull()const//判满 { if(!elem) throw nullPointer(); return size == capacity; } template<class slDataType> void seqList<slDataType>::seqListPushHead(slDataType x)//头插 { if(!elem) throw nullPointer(); if (size == capacity) doubleCapacity();//顺序表满了就扩容 for (int i = size 1; i > 1; i --) { elem[i] = elem[i - 1]; } elem[1] = x; size ; } template<class slDataType> void seqList<slDataType>::seqListPushBack(slDataType x)//尾插 { if(!elem) throw nullPointer(); if (size == capacity) doubleCapacity(); size ; elem[size] = x; } template<class slDataType> void seqList<slDataType>::seqListPopHead()//头删 { if(!elem) throw nullPointer(); if (size != 0) { for (int i = 1; i < size; i ) elem[i] = elem[i 1]; size--; } else { throw nullList(); } } template<class slDataType> void seqList<slDataType>::seqListPopBack()//尾删 { if(!elem) throw nullPointer(); if (size != 0) { size--; } else { throw nullList(); } } ==注意是带哨兵位头结点的顺序表！！！== template<class slDataType> void seqList<slDataType>::seqListInsert(int pos, slDataType& data)//在任意位置pos插入 { if(!elem) throw nullPointer(); if (pos > size 1 || pos < 1) //pos=1的时候是头插，=size 1的时候是尾插 throw outofsize(); if (size == capacity) doubleCapacity(); for (int i = size 1; i > pos; i--) { elem[i] = elem[i - 1]; } elem[pos] = data; size ; } template<class slDataType> void seqList<slDataType>::seqListErase(int pos)//删除pos的元素 { if(!elem) throw nullPointer(); if (pos > size 1 || pos < 1) //pos=1的时候是头删，=size 1的时候是尾删 throw outofsize(); if (size != 0 ) { for (int i = pos; i < size; i ) elem[i] = elem[i 1]; size--; } else { throw nullList(); } } template<class slDataType> void seqList<slDataType>::seqListRemove(int pos, slDataType& e)//删除pos处的元素，并赋值给e（这里才体现引用的用处 { if(!elem) throw nullPointer(); if (pos > size 1 || pos < 1) throw outofsize(); e = elem[pos]; seqListErase(pos); } template<class slDataType> slDataType seqList<slDataType>::seqListGet(int pos)const//返回pos处的元素 { if(!elem) throw nullPointer(); if (pos > size 1 || pos < 1) throw outofsize(); return elem[pos]; } template<class slDataType> int seqList<slDataType>::seqListFind(slDataType& data)const//返回值等于data的元素的位置，没有则返回0（这里采用了一个比较有意思的方式 { if(!elem) throw nullPointer(); int i; elem[0] = data; //将需要查找的值赋给哨兵位头结点，哨兵位头结点中的数据不属于顺序表中的数据 for (i = size; i >= 0; i--) //这样的话只需要遍历一遍就好了，没找到的话就会遍历到底，i就直接等于0，比较巧妙 if (elem[i] == data) break; return i; } template<class slDataType> int seqList<slDataType>::seqListLength()const//返回顺序表长度 { if(!elem) throw nullPointer(); return size; } template<class slDataType> void seqList<slDataType>::seqListDestory()//清除顺序表，使其成为空表 { if(!elem) throw nullPointer(); delete[]elem; elem = NULL; size = 0; capacity = 0; }
总结
这里只有一点比较重要，并且关系到以后的C 中关于动态内存释放的处理： 由于C 中有析构函数，所以不必要额外使用函数来进行动态内存的释放，将销毁动态内存的工作交给析构函数就可以，所以可以有别的函数来做别的工作，比如上面的顺序表，除了完全销毁顺序表之外，还可以清空顺序表（clear函数）： 顺序表的头结点也是动态开辟的，但是可以不销毁它，保留下来，这样这个头还在，其他的空间被销毁了，就使得原来的顺序表被清空，再次写入数据的话不用再初始化顺序表，直接用原来的这个头结点就可以 在析构函数中，又可以复用clear函数，然后只需要delete掉头结点就可以
题目
==注意，本次用的是上面写的seqList，所以是带哨兵位头结点的！所以数组权重跟常规情况不太一样！不过思路无碍==
==下面这些函数都是直接在上面
