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