1 -------------------------SqList.h------------------------------------
2 /*構造線性表*/
3 #include<iostream>
4 #ifndef SqList_H_
5 #define SqList_H_//定義頭文件
6 #define initSize 100//初始化大小
7 #define increment 10//增長步長
8 typedef int ElemType;//定義元素類型
9 class SqList
10 {
11 private:
12 ElemType* elem; //聲明元素指針
13 int length;//元素個數
14 int listSize;//表長度
15 public:
16 SqList();//初始化表
17 bool isFull()const;//查看表是否為空
18 bool isEmpty()const;//查看表是否滿
19 ElemType getElem(int)const;//查看特定位置元素
20 bool insert(int,ElemType);//插入特定位置元素
21 bool insert(ElemType);//插入末尾元素
22 void creat();//創建表
23 void merge(SqList&,SqList&);//合并表并排序
24 bool del(int);//刪除表
25 void displayElem();//顯示表情況
26 ~SqList();//析構
27 };
28 #endif
29 -------------------------SqList.cpp------------------------------------
30 #include"SqList.h"
31 using namespace std;
32 SqList::SqList(){
33 elem=new ElemType[initSize];
34 length=0;
35 listSize=initSize;
36 }
37 bool SqList::isEmpty() const{
38 return length==0;
39 }
40 bool SqList::isFull() const{
41 return length==listSize;
42 }
43 ElemType SqList::getElem(int i) const{
44 if(i>length||i<1)
45 {
46 cout<<"i-value is illegal!";
47 return 0;
48 }
49 else
50 return elem[i-1];
51 }
52 bool SqList::insert( int i, ElemType e){
53 if(i>length+1||i<1)
54 {
55 cout<<"i-value is illegal!";
56 return false;
57 }
58 if(isFull())//表滿重新分配內存
59 {
60 ElemType* newBase=new ElemType[listSize+increment];
61 for(int i=0;i<=listSize;i++)
62 newBase[i]=elem[i];
63 delete[] elem;
64 elem=newBase;
65 listSize+=increment;
66 }
67 ElemType* p=&(elem[i-1]);
68 ElemType* q=&(elem[length-1]);
69 for(;q>=p;--q)
70 *(q+1)=*q;
71 *p=e;
72 ++length;
73 return true;
74 }
75 bool SqList::insert(ElemType e){
76 if(isFull())//表滿重新分配內存
77 {
78 ElemType* newBase=new ElemType[listSize+increment];
79 for(int i=0;i<=listSize;i++)
80 newBase[i]=elem[i];
81 delete[] elem;
82 elem=newBase;
83 listSize+=increment;
84 }
85 ElemType* p=&(elem[length]);
86 *p=e;
87 ++length;
88 return true;
89 }
90 void SqList::creat(){
91 cout<<"為表添加元素（輸入0退出！）"<<endl;
92 while(true)
93 {
94 int elem;
95 cin>>elem;
96 if(elem!=0)
97 {
98 insert(elem);
99 }
100 else
101 {
102 cout<<"表創建完成，大小為"<<listSize<<"."<<endl;
103 cout<<"表現有"<<length<<"個元素："<<endl;
104 for(int i=1;i<=length;i++)
105 cout<<getElem(i)<<",";
106 cout<<endl;
107 break;
108 }
109 }
110 }
111 void SqList::merge(SqList &La,SqList &Lb){
112 int i=1,j=1,k=0;
113 while(i<=La.length&&j<=Lb.length)
114 {
115 if(La.getElem(i)<=Lb.getElem(j))
116 {
117 insert(++k,La.getElem(i));
118 ++i;
119 }
120 else
121 {
122 insert(++k,Lb.getElem(j));
123 ++j;
124 }
125 }
126 while(i<=La.length)
127 {
128 insert(++k,La.getElem(i));
129 ++i;
130 }
131 while(j<=Lb.length)
132 {
133 insert(++k,Lb.getElem(j));
134 ++j;
135 }
136 cout<<"合并后元素為："<<endl;
137 for(int i=1;i<=length;i++)
138 cout<<getElem(i)<<endl;
139 }
140 bool SqList::del( int i){
141 if(i>length||i<1)
142 {
143 cout<<"i-value is illegal!";
144 return false;
145 }
146 ElemType* p=&(elem[i-1]);
147 ElemType* q=&(elem[length-1]);
148 for(++p;p<=q;++p)
149 *(p-1)=*p;
150 --length;
151 return true;
152 }
153 void SqList::displayElem(){
154 cout<<"表的大小為"<<listSize<<"."<<endl;
155 cout<<"表現有"<<length<<"個元素："<<endl;
156 for(int i=1;i<=length;i++)
157 cout<<getElem(i)<<",";
158 cout<<endl;
159 }
160 SqList::~SqList(){
161 delete[] elem;
162 }
163 -------------------------useSqList.cpp------------------------------------
164 #include"SqList.h"
165 using namespace std;
166 int main()
167 {
168 cout<<"創建表A："<<endl;
169 SqList sqa;
170 sqa.creat();
171 cout<<"創建表B："<<endl;
172 SqList sqb;
173 sqb.creat();
174 cout<<"合并表A、B的元素，并按從小到大的順序放入表C！"<<endl;
175 SqList sqc;
176 sqc.merge(sqa,sqb);
177 cout<<"操作表C："<<endl;
178 cout<<"選擇操作(Q退出)："<<endl;
179 cout<<"1.查看表情況（A）："<<endl;
180 cout<<"2.查看元素特定元素（C）："<<endl;
181 cout<<"3.插入表尾元素（I）："<<endl;
182 cout<<"4.插入特定位置元素（L）："<<endl;
183 cout<<"5.刪除元素（D）："<<endl;
184 char str;
185 cin>>str;
186 while(toupper(str)!='Q')
187 {
188 switch(toupper(str))
189 {
190 case 'A':
191 sqc.displayElem();
192 break;
193 case 'C':
194 cout<<"請輸入要查看元素位置：";
195 int i;
196 cin>>i;
197 cout<<"表中第"<<i<<"個元素為"<<sqc.getElem(i)<<endl;
198 break;
199 case 'I':
200 cout<<"請輸入要插入元素：";
201 int elem;
202 cin>>elem;
203 sqc.insert(elem);
204 sqc.displayElem();
205 break;
206 case 'L':
207 cout<<"請輸入插入元素位置：";
208 int j;
209 cin>>j;
210 cout<<"請輸入要插入元素：";
211 int jelem;
212 cin>>jelem;
213 sqc.insert(j,jelem);
214 sqc.displayElem();
215 break;
216 case 'D':
217 cout<<"請輸入要刪除元素位置：";
218 int k;
219 cin>>k;
220 sqc.del(k);
221 sqc.displayElem();
222 break;
223 default:
224 cout<<"請輸入正確選項！"<<endl;
225 }
226 cout<<"輸入選項繼續操作：";
227 cin>>str;
228 }
229 cout<<"操作結束！"<<endl;
230 cin.get();
231 cin.get();
232 }
233