数据结构课程中学的顺序表，在顺序表中进行删除，查找，排序。
第一次编辑，排版什么的可能有不对的地方，但是程序我跑过了，应该是没问题的，这个其实是我期末上机考试的题。
注释还蛮多的，所以我就直接把代码贴上去就行，但是要是有什么问题，可以随时评论或者私信，我 天天都会check消息
大家多多点赞哟，这样我才有更新的动力。谢谢呐
#include<iostream>using namespace std;template <class ElemType>class List//基类{public:virtual bool Append(const ElemType&) = 0;//表尾位置插入virtual void Traverse()=0;//顺序表的遍历//*****************************************************************************************virtual bool Insert(int,const ElemType &)=0;//插入******virtual int BinarySearch(int)=0;//二分查找(折半查找)******virtual int SeSearchWithMonitor(int)=0;//监视哨查找******virtual void InsertSort()=0;//直接插入排序******virtual void BubbleSort()=0;//冒泡排序******virtual void SelectSort()=0;//选择排序******};template <class ElemType>class SqList:public List<ElemType>//公有继承{public:SqList(int m=0);//构造函数~SqList();//析构函数bool Append(const ElemType& e);//表尾插入void Traverse();//顺序表的遍历//****************************************************************************bool Insert(int i,const ElemType &e);//插入******int BinarySearch(int i);//二分查找(折半查找)******int SeSearchWithMonitor(int key);//监视哨查找******void InsertSort();//直接插入排序******void BubbleSort();//冒泡排序******void SelectSort();//选择排序******private:int len;//当前线性表的长度int size;//当前顺序空间的大小ElemType *elem;//顺序空间的基地址指针};//顺序表初始化(不考，老师会写好，我这里写是为了方便输出）//构造函数，分配m个存储单元的顺序空间，线性表为空表template<class ElemType>SqList<ElemType>::SqList(int m){len=0;if (m==0)elem=NULL;elseelem = new ElemType[m];size=m;}template<class ElemType>SqList<ElemType>::~SqList(){delete[] elem;}//在顺序表的表尾插入新的数据元素(不考，老师会写好，我这里写是为了方便输出）template<class ElemType>bool SqList<ElemType>::Append(const ElemType& e){ElemType* newbase;if (len >= size){newbase = new ElemType[size + 10];if (!newbase)return false;for (int j = 0; j < len; j++){newbase[j] = elem[j];}delete[] elem;elem = newbase;size += 10;}elem[len++] = e;//表尾插入e，表的长度增加1return true;}//顺序表的遍历(不考，老师会写好，我这里写是为了方便输出）template<class ElemType>void SqList<ElemType>::Traverse(){ElemType *p=elem;for(int i=0;i<len;i++){cout<<*p++<<" ";}cout<<endl;}//顺序表的插入//在顺序表中序号为i的位置插入数据元素e（0<i<=len)template<class ElemType>bool SqList<ElemType>::Insert(int i,const ElemType &e){if(i<1||i>len+1)return false;//判断插入位置是否合法if(len>=size)//表满则扩展空间{ElemType *newbase;//新建指针newbase=new ElemType[size+10];if(!newbase)//可能系统没有那么大内存了所以可能会不成功建立新的数组{return false;}for(int j=0;j<len;j++){newbase[j]=elem[j];}//把原来数组的数据全部存入新数组delete[] elem;//删除原来数组头指针指向的位置elem=newbase;//将新数组的头指针赋给原数组的头指针，方便操作，不用改变外部的代码size+=10;//把原来的数组的空间增加10}//方法1：我觉得还是方法1好记for(int j=len;j>=i;j--)//先把i后面的元素往后挪一个，别忘了数组是从0开始的{elem[j]=elem[j-1];}elem[i-1]=e;//把第i个元素插入进去++len;return true;}//方法2：这是教材上的方法/*ElemType *p,*q;q=&elem[i-1]for(p=&elem[len-1];p>=q;--p){*(p+1)=*p;}*q=e;//插入e++len;return true;*///顺序表的直接插入排序/*n为待排元素个数整个排序过程为 n-1 趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序*/template<class ElemType>void SqList<ElemType>::InsertSort(){ElemType tmp;int i,j;for(i=1;i<len;i++){if(elem[i]>elem[i-1]){continue;}tmp=elem[i]; //保存待插入的元素elem[i]=elem[i-1];//把待插入的元素放到有序数组中做比较for(j=i-1;j>0&&elem[j-1]>tmp;j--){elem[j]=elem[j-1];//元素一个一个往后挪}elem[j]=tmp;/*插入到正确位置，因为j是在循坏外面定义的，所以j的值没有释放*/}}//顺序表的冒泡排序/*第一个和第二个元素的关键字进行比较，若为逆序，则将两元素互换；接着比较第二个和第三个元素的关键字，依次类推，直至最后两个元素的完成比较*/template<class ElemType>void SqList<ElemType>::BubbleSort(){int lastSwaoIndex=len-1;//记录最后一次交换的下标，int i,j;/*这是优化了的算法，让系统不再去跟已经确定了位置进行比较，不优化的话就是会多进行几次比较而不移动妈的，优化过程把爷整晕了*/for(i=lastSwaoIndex;i>0;i=lastSwaoIndex){lastSwaoIndex=0;for(j=0;j<i;j++){if(elem[j]>elem[j+1]){ElemType tmp;tmp=elem[j];elem[j]=elem[j+1];elem[j+1]=tmp;lastSwaoIndex=j;}}}}//顺序表的选择排序/*第一趟扫描所有待排序元素，找出关键字最小的元素并将它与第一个元素进行交换；第 i 趟，扫描待排序列中剩余 n - i + 1个元素，找出关键字最小的元素与序列中第 i 个位置上的元素交换*/template<class ElemType>void SqList<ElemType>::SelectSort(){int i,j;for(i=0;i<len;i++){int min=i;//标记下标，不标记值for(j=i+1;j<len;j++){//选择data[i+1~length-1]中最小的元素if(elem[j]<elem[min])//由小到大排序{min=j;}}ElemType tmp;tmp=elem[min];elem[min]=elem[i];elem[i]=tmp;}}//顺序表的二分查找（折半查找）/*初始时，令 low = 0, high = n-1, mid = (low + high) / 2，让 k 与 mid 指向的记录比较若k = = r[mid].key，查找成功若k < r[mid].key，则 high = mid - 1若k > r[mid].key，则 low = mid + 1重复上述操作，直至 low > high 时，查找失败*/template<class ElemType>int SqList<ElemType>::BinarySearch(int i){int low=0,high=len-1;//low表示所查区间的界，high表示所查区间的上届while(low<=high){int mid=(low+high)/2;if(elem[mid]==i)return mid;//查找成功else if(elem[mid]>i)high=mid-1;//在前半区间查找else low=mid+1;//在后半区间查找}return -1;//查找失败}//顺序表的监视哨查找template<class ElemType>int SqList<ElemType>::SeSearchWithMonitor(int key){int i=0;elem[len]=key;//给定值key放在最后一个位置作为监视哨while(elem[i]!=key)i++;if(i<len)return i;return -1;}int main(){int b,shuzu[10],op;SqList<int> c(10);//建立对象cout<<"请选择要执行的操作："<<endl;cout<<"操作5，6，7在一次执行中只能选择一个，比如不能在选了5以后再选6，你想想，都排好序了，后面再排序，是不是傻："<<endl;cout<<"**************************************"<<endl;cout<<"***********顺序表的基本操作***********"<<endl;cout<<"1: 建立顺序表"<<endl;cout<<"2: 插入"<<endl;cout<<"3: 二分查找"<<endl;cout<<"4: 监视哨查找"<<endl;cout<<"5: 插入排序"<<endl;cout<<"6: 冒泡排序"<<endl;cout<<"7: 选择排序"<<endl;cout<<"0: 退出"<<endl;cout<<"**************************************"<<endl;cout<<"您选择的操作是：";cin>>op;while(op!=0){switch(op){case 1://建立顺序表{cout<< "请输入10个数:" << endl;for (int i = 0; i < 10; i++){cin >> b;shuzu[i]=b;c.Append(b);}cout<<"现在的顺序表为:";c.Traverse();break;}case 2://插入{cout<<"请输入插入结点位置和数值:";int zhengshu2,zhengshu3;cin>>zhengshu2>>zhengshu3;c.Insert(zhengshu2,zhengshu3);cout<<"现在的顺序表为:";c.Traverse();break;}case 3://二分查找{int x;cout<<"请输入想查找的数:";cin>>x;cout<<"你想查找的数的下标是: "<<c.BinarySearch(x)<<endl;cout<<"现在的顺序表为:";c.Traverse();break;}case 4://监视查找{int y;cout<<"请输入想查找的数:";cin>>y;cout<<"你现在想查找的数的下标是："<<c.SeSearchWithMonitor(y)<<endl;cout<<"现在的顺序表为:";c.Traverse();break;}case 5://插入排序{c.InsertSort();cout<<"现在的顺序表为:";c.Traverse();break;}case 6://冒泡排序{c.BubbleSort();cout<<"现在的顺序表为:";c.Traverse();break;}case 7://选择排序{c.SelectSort();cout<<"现在的顺序表为:";c.Traverse();break;}}system("pause");cout<<"您选择的操作是：";cin>>op;}return 0;}
大家多多点赞哟，这样我才有更新的动力。谢谢啦
