数据结构实验1

  1 //1.线性表顺序表的初始化ok
  2 //2.输出ok，插入ok，删除ok，逆转ok，销毁ok，置空表ok（两种插入，两种删除） 
  3 //3.求表长ok，查找元素ok，判断是否为空ok
  4 //4.实现顺序表元素的逆转并输出结果ok
  5 //5.顺序表合并：动态创建两个有序的顺序表，输出合并后的顺序表
  6 #include<cstdio>
  7 #include<cstdlib>
  8 #include<algorithm>
  9 #include<iostream>
 10 #include<iomanip>
 11 using namespace std;
 12 #define MAXSIZE 100
 13 
 14 typedef int status;//状态
 15 typedef int ElemType;//数据类型 
 16 
 17 //定义函数头 
 18 typedef struct {
 19     ElemType data[MAXSIZE];
 20     int length;
 21 
 22 }SqList;//顺序表 
 23 
 24 //初始化线性表
 25 void InitList(SqList* L)
 26 {
 27     L->length = 0;
 28 }
 29 
 30 //创建线性表 输入初始元素 
 31 void  CreateList(SqList* L, ElemType a[], int n)
 32 {
 33     for (int i = 0; i < n; i++)
 34     {
 35         L->data[i] = a[i];
 36         L->length++;
 37     }
 38 }
 39 
 40  //输出线性表中元素
 41 void PrintList(SqList* L)
 42 {
 43     for (int i = 0; i < L->length; i++)
 44     {
 45         cout << L->data[i] << setw(2);
 46     }
 47     putchar('\n');
 48 }
 49 
 50  //释放线性表（置空）
 51 void Free(SqList* L)
 52 {
 53     free(L);
 54     printf("Have Free!\n");
 55 }
 56 
 57 //删除线性表
 58 status DelList(SqList* L, ElemType n)
 59 {
 60     int i;
 61     if (n<1 || n>L->length)
 62         return 0;
 63     else {
 64         for (i = n - 1; i <= L->length - 2; i++)
 65         {
 66             L->data[i] = L->data[i + 1];
 67         }
 68         L->length--;
 69         return 1;
 70     }
 71 }
 72  //判断表是否为空
 73 status Listempty(SqList* L)
 74 {
 75     return (L->length == 0);
 76 }
 77 //输出线性表长度
 78 void Listlen(SqList* L)
 79 {
 80     cout << (L->length) << endl;
 81 }
 82 //表中插入元素 
 83 status InsList(SqList* L, int j, ElemType k)
 84 {
 85     int i;
 86     if (j > L->length + 1 || j < 0)
 87         return 0;
 88     else
 89     {
 90         for (i = L->length-1;i>=j-1;i--)
 91         {
 92             L->data[i + 1] = L->data[i];
 93         }
 94         L->data[i + 1] = k;  
 95         L->length++;
 96         return 1;
 97     }
 98 }
 99 //线性表元素查找
100 void Locate(SqList* L, int y)
101 {
102     int i, j = 0;
103     for (i = 0; i < L->length; i++)
104     {
105         if (L->data[i] == y)j = i + 1;
106     }
107     if (j == 0)printf("没有找到该元素\n");
108     else printf("%d是第%d个元素\n",y,j);
109 }
110 //线性表逆转
111 void Swap(ElemType* a, ElemType* b)
112 {
113     ElemType temp = *a;
114     *a = *b;
115     *b = temp;
116 }
117 void Reverse(SqList* L)
118 {
119     for (int i = 0; i < L->length / 2; i++)
120     {
121         Swap(&L->data[i], &L->data[L->length - 1 - i]);
122     }
123 }
124 //排序
125 void SortList(SqList* L)
126 {
127     for (int i = 0; i < L->length-1; i++)
128     {
129         for (int j = 0; j < L->length -1- i; j++)
130         {
131             if (L->data[j] > L->data[j + 1])
132             {
133                 ElemType temp = L->data[j];
134                 L->data[j] = L->data[j + 1];
135                 L->data[j + 1] = temp;
136             }
137         }
138     }
139 }
140 //主函数
141 int main()
142 {
143     int n;
144     ElemType a[MAXSIZE];
145     printf("输入元素个数：");
146     cin >> n;
147     printf("输入元素：");
148     for (int i = 0; i < n; i++)
149         cin >> a[i];//输入元素 
150     sort(a, a + n);//排序 
151     SqList* L;
152     L = (SqList*)malloc(sizeof(SqList));//申请空间
153     InitList(L);//创建表
154     cout << "空表已创建" << endl;
155     CreateList(L, a, n);//追加元素 
156     printf("元素已加入表中\n");
157     printf("输出元素：\n");
158     PrintList(L);//输出元素 
159     printf("线性表长度：");
160     Listlen(L);//输出线性表长度
161     //插入
162     int loc, flag, member;
163     printf("输入插入位置和元素：");
164     cin >> loc >> member;
165     flag = InsList(L, loc, member);
166     if (flag == 1)
167     {
168         printf("输出元素：\n");
169         PrintList(L);//输出线性表
170         printf("线性表长度：");
171         Listlen(L);//输出线性表长度
172     }
173     if (flag == 0)
174         printf("插入错误！\n");
175     //删除
176     int place;
177     printf("请输入要删除的位置：");
178     cin >> place;
179     flag = DelList(L, place);
180     if (flag == 1)
181     {
182         printf("输出元素：\n");
183         PrintList(L);//输出线性表
184         printf("线性表长度：");
185         Listlen(L);//输出线性表长度
186     }
187     if (flag == 0)
188         printf("删除失败！\n");
189     //判空
190     if (Listempty(L))
191         cout << "Empty" << endl;
192     else
193         cout << "Not Empty" << endl;
194     int y;
195     printf("请输入要查找的数y：");
196     cin >> y;
197     Locate(L, y);//线性表查找
198     //逆转顺序表
199     Reverse(L);
200     printf("逆转输出元素：\n");
201     PrintList(L);//输出线性表
202     printf("线性表长度：");
203     Listlen(L);//输出线性表长度
204     Free(L);//置空
205     SqList* L1,*L2,*L3;
206     L1 = (SqList*)malloc(sizeof(SqList));//申请空间
207     L2 = (SqList*)malloc(sizeof(SqList));//申请空间
208     L3 = (SqList*)malloc(sizeof(SqList));//申请空间
209     InitList(L1);//创建表
210     cout << "空表L1已创建" << endl;
211     printf("输入L1元素，检测到-1停止：");
212     int la=0,num1=0;
213     while (la != -1)
214     {
215         cin >> la;
216         if (la != -1)
217         {
218             L1->data[num1] = la;
219             num1++;
220             L1->length++;
221         }
222     }
223     InitList(L2);//创建表
224     cout << "空表L2已创建" << endl;
225     printf("输入L2元素，检测到-1停止：");
226     int lb = 0, num2 = 0;
227     while (lb != -1)
228     {
229         cin >> lb;
230         if (lb != -1) 
231         {
232             L2->data[num2] = lb;
233             num2++;
234             L2->length++;
235         }
236     }
237     InitList(L3);//创建表
238     cout << "空表L3已创建" << endl;
239     int cnt=0;
240     for (int i = 0; i < L1->length; i++)
241     {
242         L3->data[i] = L1->data[i];
243         L3->length++;
244         cnt++;
245     }
246     for (int i = 0; i < L2->length; i++)
247     {
248         if (cnt > MAXSIZE)
249         {
250             printf("超出！\n");
251             break;
252         }
253         L3->data[cnt] = L2->data[i];
254         cnt++;
255         L3->length++;
256     }
257     //排序
258     SortList(L3);
259     PrintList(L3);//输出线性表
260     //lemType la[MAXSIZE], lb[MAXSIZE], lc[MAXSIZE];
261     return 0;
262 }