C++ 顺序表
/***
1顺序表
1、必做题
- 编写程序建立一个数续表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。
- 编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。
如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；
如果不存在，返回－1。编写主函数测试结果。 - 在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。
解题思路：首先查找插入的位置，再移位，最后进行插入操作；
从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；
然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。 - 删除顺序表中所有等于X的数据元素。
2、选做题
已知两个顺序表A和B按元素值递增有序排列，
要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表
（允许表中含有值相同的元素）。
***/
//在头文件中"SeqList.h" /**< writer:FDA_orangebook */ /** \brief: 顺序表 * * int Length(){return length;} //用于获取长度1-N * T Get(int i); //用于获取第I个数据 * T Locate(T value); //用于获取 值为value的位置 * void Insert(T value); //在递增的顺序中，插入value值 * void Insert(int position,T value); //在position这个位置，插入value * void Insert(T *_data,int _length); //将_data与data以递减的顺序合并 * T Delete(int position); //将position这个中的元素删除 * void PrintList(); //打印 data 序列 */ const int MaxSize=100; #define T int //此处修改 数组的类型 class SeqList { public: //定义两个构造函数 SeqList() { length=0; } SeqList(T a[],int n); ~SeqList() {} int Length() { return length; } T Get(int i); T Locate(T value); void Insert(T value); void Insert(int position,T value); void Insert(T *_data,int _length); T Delete(int position); void PrintList(); private: T data[MaxSize]; int length; };
//在SwqList.cpp #ifndef SEQLIST_H_ #define SEQLIST_H_ #include "SeqList.h" #include<iostream> #include<algorithm> using namespace std; SeqList::SeqList(T *a,int n) { if(n>MaxSize) cout<<"Parameters of illegal"<<endl; for(int i=0; i<n; i++) data[i]=a[i]; length=n; } void SeqList::Insert(T value) { int j; sort(data,data+length); cout<<length<<endl; for(j=length; value<=data[j-1]&&j>0; --j) data[j]=data[j-1]; data[j]=value; ++length; cout<<length<<endl; } void SeqList::Insert(int position,int value) { if(length>=MaxSize||position<1||position>length+1) cout<<"input error"<<endl; for(int j=length; j>=position; --j) data[j]=data[j-1]; data[position-1]=value; ++length; } bool myfunction (int i,int j) { return (i>j); } void SeqList::Insert(T *_data,int _length) { //int j=0; sort(data,data+length,myfunction); sort(_data,_data+_length,myfunction); PrintList(); int i=0;int j; for(; i<_length;++i) { for( j=0;_data[i]<data[j]&&j<length;++j); Insert(j+1,_data[i]); } } T SeqList::Delete(int position) { if(length==0||position<1||position>length) cout<<"error"<<endl; else { int x=data[position-1]; for(int j=position; j<length; j++) data[j-1]=data[j]; length--; return x; } return (T)-1; } T SeqList::Get(int i) { if(i<1||i>length) cout<<"error"<<endl;; return data[i-1]; } T SeqList::Locate(T value) { for(int i=0; i<length; i++) if(data[i]==value) return i+1; return -1; } void SeqList::PrintList() { cout<<"\n****************************"<<endl; for(int i=1; i<=length; i++) i%5==0?cout<<data[i-1]<<"\n":cout<<data[i-1]<<"\t"; }; #endif // SwqList_H_
#include"SeqList.h" #include<iostream> #include<stdlib.h> using namespace std; #define MAX 100 int main() { T a[10]= {0,1,2,13,4,5,6,7,8,9}; T bb[7]= {11,12,3,10,9,16,14}; SeqList test(a,9); test.PrintList(); if(test.Locate(a[10])!=-1) cout<<test.Locate(a[7])<<endl; test.Insert(-25); test.PrintList(); test.Delete(test.Locate(-25)); test.PrintList(); test.Insert(bb,7); test.PrintList(); }