顺序表

  1 //2016.9.4
  2 #include <iostream>
  3 #include <cstdio>
  4 
  5 using namespace std;
  6 
  7 const int maxsize = 100;
  8 
  9 template<class T>
 10 class seq_list
 11 {
 12 protected:
 13     T *date;
 14     int max_size;
 15     int last;
 16 public:
 17     seq_list(int ms = maxsize);
 18     seq_list(seq_list<T> &a);
 19     ~seq_list(){delete [] date;}
 20     int Length(){return last;}
 21     bool Empty(){return last == 0;}
 22     bool Full(){return last == maxsize;}
 23     bool getDate(int pos, T &val) const
 24     {if(pos>=0&&pos<last){val = date[pos]; return true;}else return false;}
 25     bool Insert(int pos, T val);
 26     bool Remove(int pos, T& val);
 27     bool Update(int pos, T val);
 28     bool Search(T x);
 29     void output(){
 30         for(int i = 0; i < last; i++)
 31               cout<<date[i]<<" ";
 32         cout<<endl;
 33     }
 34     seq_list<T> operator=(seq_list<T> &a);
 35 };
 36 
 37 template<class T>
 38 seq_list<T>::seq_list(int ms)
 39 {
 40     if(ms > 0)
 41     {
 42         max_size = ms;
 43         last = 0;
 44         date = new T[max_size];
 45         if(date == NULL)exit(1);
 46     }
 47 }
 48 
 49 template<class T>
 50 seq_list<T>::seq_list(seq_list<T> &a)
 51 {
 52     T tmp;
 53     max_size = a.max_size, last = a.last;
 54     date = new T[max_size];
 55     if(date == NULL)exit(1);
 56     for(int i = 0; i < last; i++)
 57     {
 58         a.getDate(i, tmp);
 59         date[i] = tmp;
 60     }
 61 }
 62 
 63 template<class T>
 64 bool seq_list<T>::Insert(int pos, T val)
 65 {
 66     if(last == max_size)return false;
 67     if(pos<0 || pos>last)return false;
 68     for(int i = last; i > pos; i--)
 69           date[i] = date[i-1];
 70     date[pos] = val;
 71     last++;
 72     return true;
 73 }
 74 
 75 template<class T>
 76 bool seq_list<T>::Remove(int pos, T& val)
 77 {
 78     if(pos<0 || pos >= last)return false;
 79     if(last == 0)return false;
 80     val = date[pos];
 81     for(int i = pos; i < last; i++)
 82           date[i] = date[i+1];
 83     last--;
 84 }
 85 
 86 template<class T>
 87 bool seq_list<T>::Update(int pos, T val)
 88 {
 89     if(pos<0 || pos>=last)return false;
 90     date[pos] = val;
 91     return true;
 92 }
 93 
 94 template<class T>
 95 bool seq_list<T>::Search(T x)
 96 {
 97     for(int i = 0; i < last; i++)
 98           if(date[i] == x)
 99             return true;
100     return false;
101 }
102 
103 template<class T>
104 seq_list<T> seq_list<T>::operator=(seq_list<T> &a)
105 {
106     delete [] date;
107     max_size = a.max_size, last = a.last;
108     date = new T[max_size];
109     if(date == NULL)exit(1);
110     T tmp;
111     for(int i = 0; i < last; i++)
112     {
113         a.getDate(i, tmp);
114         date[i] = tmp;
115     }
116 }
117 
118 void Union(seq_list<int> &a, seq_list<int> &b)//两个集合的并
119 {
120     int n = a.Length(), m = b.Length(), tmp;
121     for(int i = 0; i < m; i++)
122     {
123         b.getDate(i, tmp);
124         if(!a.Search(tmp))
125         {
126             a.Insert(n, tmp);
127             n++;
128         }
129     }
130 }
131 
132 void Intersection(seq_list<int> &a, seq_list<int> &b)//两个集合的交
133 {
134     int n = a.Length(), tmp;
135     for(int i = 0; i < n; i++)
136     {
137         a.getDate(i, tmp);
138         if(!b.Search(tmp))
139               a.Remove(i, tmp);
140     }
141 }
142 
143 int main()
144 {
145     int tmp;
146     seq_list<int> a;
147     for(int i = 0; i < 10; i++)
148           a.Insert(i, i);
149     a.output();
150     a.Insert(1, 100);
151     a.output();
152     a.Remove(1, tmp);
153     a.output();
154     if(a.Search(5))cout<<"YES"<<endl;
155     else cout<<"NO"<<endl;
156     seq_list<int> b;
157     b = a;
158     b.output();
159     b.Update(5, 500);
160     b.output();
161     Union(a, b);
162     a.output();
163     Intersection(a, b);
164     a.output();
165     return 0;
166 }