顺序线性表的操作 (4人)

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 using namespace std;
  5 
  6 const int maxlen=1000;//线性表的最大长度
  7 
  8 struct List
  9 {
 10     int Data[maxlen];//存放数据
 11     int CurNum;//当前线性表
 12 };
 13 
 14 void Intialize(    List &A)//线性表初始化
 15 {
 16     A.CurNum = 0;//线性表元素个数为0
 17 }
 18 
 19 int Length(List &A)//求表长度的实现
 20 {
 21     return A.CurNum;
 22 }
 23 
 24 int Insert(    List &A,const int i,const int x)//插入元素运算对应的函数
 25 {
 26     if(A.CurNum==maxlen)printf("溢出!\n");//溢出，不能插入
 27     if(i<1||i>Length(A)+1)printf("插入范围有错!\n");//插入范围有错
 28     else {
 29         for(int j=A.CurNum-1;j>=i-1;j--){
 30             A.Data[j+1]=A.Data[j];
 31         }
 32         A.Data[i-1]=x;
 33         A.CurNum++;
 34         return 0;
 35     }
 36 }
 37 int  Get_int(List &A,const int i,int &x)//按序号取元素运算
 38 {
 39     if(i<=0||i>A.CurNum)printf("序号错误!\n");
 40     else {
 41         x=A.Data[i-1];
 42         return 0;
 43     }
 44 }
 45 
 46 
 47 //两个数组进行比较大小
 48 void  CompareArray(int ArrayA[],int ArrayB[],int N)
 49 {
 50     int i,DataA,DataB;
 51     
 52     int NumA = 0;//线性表A中元素 比线性表B中元素大的个数
 53     int NumB = 0;//线性表A中元素 比线性表B中元素小的个数
 54 
 55     List A,B;
 56 
 57     Intialize(A);//初始化
 58     Intialize(B);//初始化
 59     for(i=0;i<N;i++)
 60     {
 61         Insert(A,i+1,ArrayA[i]);//线性表A存放数据
 62         Insert(B,i+1,ArrayB[i]);//线性表B存放数据
 63     }
 64 
 65     for(i=0;i<N;i++)
 66     {
 67         Get_int(A,i+1,DataA);//取线性表A 中的元素
 68         Get_int(B,i+1,DataB);//取线性表B 中的元素
 69 
 70         //printf("%d  %d\n",DataA,DataB);
 71         if(DataA>DataB)//线性表A 中的元素大
 72         {
 73             NumA++;
 74         }else if(DataA<DataB){//线性表A 中的元素小
 75             NumB++;
 76         }
 77     }
 78     if(NumA>NumB)
 79     {
 80         printf("第一个数组大!\n");
 81     }else if(NumA<NumB){
 82         printf("第二个数组大!\n");
 83     }else printf("两个数组大小相等!\n");
 84 }
 85 
 86 //冒泡排序算法
 87 int Bubble_sort(List &A,bool flags){
 88     bool exchange;
 89     int i,j,temp,data1,data2;
 90     i=1;
 91     if(flags)//升序
 92     {
 93         do{
 94             exchange=false;
 95             for(j=A.CurNum-1;j>=i;j--){
 96                 Get_int(A,j+1,data1);//取线性表A 中的元素
 97                 Get_int(A,j,data2);//取线性表A 中的元素
 98                 if(data1<data2){
 99                     temp=A.Data[j-1];
100                     A.Data[j-1]=A.Data[j];
101                     A.Data[j]=temp;
102                     exchange=true;
103                 }
104             }
105             i++;
106         }while((i<=A.CurNum-1)&&(exchange=true));
107     }else {//降序
108         do{
109             exchange=false;
110             for(j=A.CurNum-1;j>=i;j--){
111                 Get_int(A,j+1,data1);//取线性表A 中的元素
112                 Get_int(A,j,data2);//取线性表A 中的元素
113                 if(data1>data2){
114                     temp=A.Data[j-1];
115                     A.Data[j-1]=A.Data[j];
116                     A.Data[j]=temp;
117                     exchange=true;
118                 }
119             }
120             i++;
121         }while((i<=A.CurNum-1)&&(exchange=true));
122     }
123     printf("排序后的数据为:");
124     for(i=0;i<A.CurNum;i++)printf("  %d",A.Data[i]);
125     printf("\n");
126     return 0;
127 }
128 
129 //对线性表中的数据排序
130 void List_Sort()
131 {
132     int i,N,select,num;
133     List A;
134     Intialize(A);//初始化
135     printf("请输入数据个数:");
136     scanf("%d",&N);
137     printf("请依次输入数据,空格隔开:");
138     for(i=0;i<N;i++)
139     {
140         scanf("%d",&num);
141         Insert(A,i+1,num);//线性表A存放数据
142     }
143 
144     printf("          -------------------------\n");
145     printf("         |-----------1:升序--------|\n");
146     printf("         |-----------0:升序--------|\n");
147     printf("          -------------------------\n");
148     printf("你的选择是:");
149     scanf("%d",&select);
150     switch(select)
151     {
152     case 1:
153         Bubble_sort(A,true);
154         break;
155     default:
156         Bubble_sort(A,false);
157         break;
158     }
159 }
160 
161  
162 /*
163 *List  B 排序完成的，A 未排序，C存放两个合并的结果
164 */
165 void Merge_List(List A,List B, List &C)//顺序表A,B合并
166 {
167     int array[50];//用于记录插入的位置
168 
169     int count=0;//计数
170     int i,j,k;
171     for(i=0;i<Length(B);i++)
172     {
173         Insert(C,i+1,B.Data[i]);
174     }
175     //printf(" %d",Length(A));
176     
177     for(i=0;i<Length(A);i++)//A中数据逐个插入到C中
178     {
179         //printf(" %d\n",A.Data[i]);
180         bool flags = false;
181         for(k=0;k<Length(C);k++)
182         {
183             if(A.Data[i]<=C.Data[k])
184             {
185                 flags = true;
186                 Insert(C,k+1,A.Data[i]);
187                 for(j=0;j<count;j++)
188                 {
189                     if(array[j]>k)array[j]++;
190                 }
191                 array[count] = k;
192                 break;
193             }
194         }
195         if(flags==false)//插在最后面
196         {
197             Insert(C,Length(C)+1,A.Data[i]);
198             array[count] = Length(C);
199         }
200         //printf(" num%d\n",array[count]);
201         count++;
202     }
203 
204     printf("合并后的线性表:");
205     for(int i=0;i<C.CurNum;i++)
206     {
207         printf(" %d",C.Data[i]);
208     }
209     printf("\n");
210 
211     printf("线性表A:");
212     int temp;
213     for(i=0;i<count;i++)
214     {
215         
216         temp = C.Data[array[i]];
217         for(j=i;j<count;j++)
218         {
219             if(temp>C.Data[array[j]])
220             {
221                 temp = C.Data[array[j]];
222             }
223         }
224         for(j=i;j<count;j++)
225         {
226             if(temp ==C.Data[array[j]])
227             {
228                 C.Data[array[j]]= C.Data[array[i]];
229 
230                 printf(" %d",temp);
231                 break;
232             }
233         }
234     }
235     printf("\n");
236 }
237 int main(){
238     List A,B,C;
239     int i,select,con;
240     int ArrayA[]={1,5,9};
241     int ArrayB[]={2,7,13};
242    do{
243         printf("          ---------------------------------\n");
244         printf("         |-----------0:数组比较大小--------|\n");
245         printf("         |-----------1:线性表排序----------|\n");
246         printf("         |-----------2:线性表合并----------|\n");
247         printf("          ---------------------------------\n");
248         printf("你的选择是:");
249         scanf("%d",&select);
250         while(select!=1&&select!=0&&select!=2)
251         {
252                 printf("你的输入不正确，请重新输入:");
253                 scanf("%d",&select);
254         }
255         switch(select){
256         case 0:
257             CompareArray(ArrayA,ArrayB,9);
258             break;
259         case 1:
260             List_Sort();
261             break;
262         case 2:
263             Intialize(A);//初始化
264             Intialize(B);//初始化
265             Intialize(C);//初始化
266             for(i=0;i<3;i++)
267             {
268                 Insert(A,i+1,ArrayA[i]);//线性表A存放数据
269                 Insert(B,i+1,ArrayB[i]);//线性表B存放数据
270             }
271             //Bubble_sort(A,true);
272             Bubble_sort(B,true);
273             Merge_List(A,B,C);
274             break;
275         default:
276             break;
277         }
278         printf("          -------------------------\n");
279         printf("         |-----------1:继续--------|\n");
280         printf("         |-----------0:退出--------|\n");
281         printf("          -------------------------\n");
282         printf("你的选择是:");
283         scanf("%d",&con);
284         while(con!=1&&con!=0)
285         {
286                 printf("你的输入不正确，请重新输入:");
287                 scanf("%d",&con);
288         }
289    }while(con==1);
290     return 0;
291 }