C++顺序表（模板总结）

总结：

1、模板类的实质是什么：让程序员写出和类型无关的代码
2、模板的对象时什么：方法或者类
3、是对类中的一系列操作，提供一个不固定数据类型的方法
用模板做的类的时候要指明对象
Stack<int> intStack; // int 类型的栈
Stack<string> stringStack; // string 类型的栈
我们用的时候必须先指定也就是先把这个参数传给T
4、这里顺序表的实现可以先选择类型然后选择操作，因为一个类就是一个整体，属性+方法。
5、C++动态创建用new关键词，也就是动态指定数组大小
  1 #include<iostream>
  2 
  3 using namespace std;
  4 
  5 int maxSize = 100;
  6 
  7 // 定义
  8 template <class T>
  9 class SqListClass
 10 {
 11     private:
 12         T *data; // 存放顺序表中的元素
 13         int length; // 存放顺序表的长度
 14 
 15     public:
 16         SqListClass(int length); // 构造函数
 17         SqListClass(); // 构造函数
 18         ~SqListClass(); // 析构函数
 19         void CreateList(T a[], int n); // 由a数组中的元素建造顺序表
 20         void DispList(); // 输出顺序表L中的所有元素
 21         int ListLength(); // 求顺序表的长度
 22         bool GetElem(int i, T &e); // 求顺序表中某序列号的元素值
 23         int LocateElem(T e); // 按元素查找其第一个序号位置
 24         bool ListInsert(int i, T e); // 在位置i插入数据元素e
 25         bool ListDelete(int i); // 在位置i删除数据元素
 26         void ReverseList(SqListClass<T> &L); // 翻转顺序表
 27         
 28         //操作时候的函数
 29 //        void CreateList_();
 30 //        void QuitSystem(); 
 31 };
 32 
 33 // 线性表的初始化
 34 template<class T>
 35 SqListClass<T>::SqListClass(int length) // 构造函数
 36 {
 37     data = new T[length];
 38     length = 0;
 39 }
 40 template<class T>
 41 SqListClass<T>::SqListClass() // 构造函数
 42 {
 43     data = new T[maxSize];
 44     length = 0;
 45 }
 46 // 线性表的销毁
 47 template<class T>
 48 SqListClass<T>::~SqListClass() // 析构函数
 49 {
 50     delete [] data;
 51 }
 52 
 53 // 实现
 54 
 55 // 线性表的创建，时间复杂度为O(n)
 56 template<class T>
 57 void SqListClass<T>::CreateList(T a[], int n)
 58 {
 59     int i;
 60     for(i=0; i<n; i++){
 61         data[i] = a[i];
 62     }
 63     length = i;
 64 }
 65 
 66 // 输出线性表的所有元素，时间复杂度为O(n)
 67 template<class T>
 68 void SqListClass<T>::DispList(){
 69     cout << "Out:" << endl;
 70     for(int i=0; i<length; i++){
 71         cout << data[i] << " ";
 72     }
 73     cout << endl;
 74 }
 75 
 76 // 求线性表的长度，时间复杂度为O(1)
 77 template<class T>
 78 int SqListClass<T>::ListLength(){
 79     return length;
 80 }
 81 
 82 // 求顺序表中某序列号的元素值,，时间复杂度为O(1)
 83 template<class T>
 84 bool SqListClass<T>::GetElem(int i, T &e){
 85     if(i<0 || i>length) return false;
 86     e = data[i-1];
 87     return true;
 88 }
 89 
 90 // 按元素查找其第一个序号位置，时间复杂度为O(n)
 91 template<class T>
 92 int SqListClass<T>::LocateElem(T e){
 93     int i = 0;
 94     while(i<length && data[i]!=e) i++;
 95     if(i>=length) return 0;
 96     else return i+1;
 97 }
 98 
 99 // 在位置i插入数据元素e，时间复杂度为O(n)
100 template<class T>
101 bool SqListClass<T>::ListInsert(int i, T e){
102     if(i<0 || i>length) return false;
103     for(int j=length; j>=i; j--){
104         data[j]=data[j-1];
105     }
106     data[i-1] = e;
107     length++;
108     return true;
109 }
110 
111 // 在位置i删除数据元素，时间复杂度为O(n)
112 template<class T>
113 bool SqListClass<T>::ListDelete(int i){
114     if(i<0 || i>length) return false;
115     for(int j=i-1; j< length; j++){
116         data[j] = data[j+1];
117     }
118     length--;
119     return true;
120 }
121 
122 // 翻转顺序表
123 template<class T>
124 void SqListClass<T>::ReverseList(SqListClass<T> &L){
125     T temp;
126     for(int j=0; j<L.length/2; j++){
127         temp = L.data[j];
128         L.data[j] = L.data[length-j-1];
129         L.data[length-j-1] = temp;
130     }
131 }
132 
133 /***********************************分界线***********************************/
134 // 创建顺序表
135 
136 void CreateList_(){
137     cout<<"请输入顺序表长度"<<endl;
138     int length;
139     do{
140         cin>>length;
141         if(length<=0) cout<<"顺序表长度不合法，请重新输入"<<endl;
142     }while(length<=0);
143     cout<<"请选择顺序表类型：输入类型后面的数字"<<endl;
144     int type;
145     do{
146         cout<<"int:1    double:2   string:3"<<endl; 
147         cin>>type;
148         if(type<=0||type>=4) cout<<"类型输入不合法，请重新输入"<<endl;
149     }while(type<=0||type>=4);
150     
151     
152     //创建 
153     SqListClass<int> sqList(length);
154     
155     cout<<"创建线性表成功^_^"<<endl; 
156 }
157 
158 // 退出系统 
159 void QuitSystem(){
160     cout<<"成功退出系统-_-"<<endl; 
161 }
162 
163 // 主函数
164 int main(){
165     int length=10;
166     SqListClass<int> sqList(length);
167     
168     int demand=1;
169     
170     while(demand){
171         cout<<endl;
172         cout<<"---------------------------------顺序表操作指令---------------------------------"<<endl; 
173         cout<<"*、输入数字 1 ，创建顺序表"<<endl; 
174         cout<<"*、输入数字 0 ，退出系统 "<<endl; 
175         cout<<"--------------------------------------------------------------------------------"<<endl;
176         cin>>demand;
177         switch(demand){
178             case 1: CreateList_();break;
179             case 0: QuitSystem();return 0;
180         } 
181     }
182     
183 //    int arr[3] = {3,4,5};
184 //    // 创建线性表
185 //    sqList.CreateList(arr, 3);
186 //    // 输出线性表
187 //    sqList.DispList();
188 //    // 输出线性表的长度
189 //    cout << "sqList length is " << sqList.ListLength() << endl;
190 //    // 求第二个位置的元素
191 //    int a;
192 //    sqList.GetElem(2, a);
193 //    cout <<"The 2 local is elem " << a << endl;
194 //    // 查找元素5的位置
195 //    cout << "The elem 5 local is " << sqList.LocateElem(5) << endl;
196 //    // 在位置4插入元素6
197 //    sqList.ListInsert(2, 6);
198 //    sqList.DispList();
199 //    // 在位置1删除数据元素
200 //    sqList.ListDelete(1);
201 //    sqList.DispList();
202 //    // 翻转顺序表
203 //    sqList.ReverseList(sqList);
204 //    sqList.DispList();
205     return 0;
206 }