数据结构学习第二十二天

16:50:21 2019-09-08

上午交了C++作业。。感觉自己很菜

20:42:29 2019-09-10

已经开学了对于前两章的学习就写在这篇随笔上了今天终于把困扰我的一道简单题写完了..(os:难受)

PTA第23题利用拓扑排序计算关键路径中最短时间及机动时间的问题

注意printf中参数入栈的顺序

  1 #define _CRT_SECURE_NO_WARNINGS  
  2 #include<stdio.h>
  3 #include<malloc.h>
  4 //图的邻接表表示法
  5 #define MaxVerterNum 110    //最大顶点数
  6 #define INFINITY 65535        //
  7 typedef int Vertex;            //顶点下标表示顶点
  8 typedef int WeightType;        //边的权值
  9 typedef char DataType;        //顶点存储的数据类型
 10 
 11 //边的定义
 12 typedef struct ENode* PtrToENode;
 13 typedef PtrToENode Edge;
 14 struct ENode
 15 {
 16     Vertex V1, V2; //有向边<V1,V2>
 17     WeightType Weight;  //权重
 18 };
 19 
 20 //邻接点的定义
 21 typedef struct AdjVNode* PtrToAdjVNode;
 22 struct AdjVNode
 23 {
 24     Vertex AdjV;  //邻接点下标
 25     WeightType Weight; //边权重
 26     PtrToAdjVNode Next; //指向下一个邻接点的指针  //指向出度或入度的节点 具体视头节点而定
 27 };
 28 
 29 //顶点表头节点的定义
 30 typedef struct Vnode
 31 {
 32     PtrToAdjVNode FirstEdge;  //边表头指针 指向出度
 33     PtrToAdjVNode LastEdge;   //边表头指针 指向入度
 34     DataType Data;            //存顶点的数据
 35 }AdjList[MaxVerterNum];        //AdjList是邻接表类型
 36 
 37 //图节点的定义
 38 typedef struct GNode* PtrToGNode;
 39 typedef PtrToGNode LGraph;
 40 struct GNode
 41 {
 42     int Nv;  //顶点数
 43     int Ne;  //边数
 44     AdjList G;  //邻接表
 45 };
 46 
 47 LGraph CreateGraph(int VertexNum)
 48 {//初始化一个有VertexNum个顶点但没有边的图
 49     Vertex V;
 50     LGraph Graph;
 51 
 52     Graph = (LGraph)malloc(sizeof(struct GNode)); //建立图
 53     Graph->Nv = VertexNum;
 54     Graph->Ne = 0;
 55     //初始化邻接表头指针
 56     for (V = 1; V <= Graph->Nv; V++)
 57     {
 58         Graph->G[V].FirstEdge = NULL;
 59         Graph->G[V].LastEdge = NULL;
 60     }
 61     return Graph;
 62 }
 63 void InsertEdge(LGraph Graph, Edge E)
 64 {
 65     PtrToAdjVNode NewNode;
 66     //插入边<V1,V2>  链接出度
 67     NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
 68     NewNode->AdjV = E->V2;
 69     NewNode->Weight = E->Weight;
 70     NewNode->Next = Graph->G[E->V1].FirstEdge;
 71     Graph->G[E->V1].FirstEdge = NewNode;
 72 
 73     //链接入度
 74     NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
 75     NewNode->AdjV = E->V1;
 76     NewNode->Weight = E->Weight;
 77     NewNode->Next = Graph->G[E->V2].LastEdge;
 78     Graph->G[E->V2].LastEdge = NewNode;
 79     //若是无向图 还要插入边<V2,V1>
 80     /*NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
 81     NewNode->AdjV = E->V1;
 82     NewNode->Weight = E->Weight;
 83     NewNode->Next = Graph->G[E->V2].FirstEdge;
 84     Graph->G[E->V2].FirstEdge = NewNode;*/
 85 }
 86 LGraph BuildGraph()
 87 {
 88     LGraph Graph;
 89     Edge E;
 90     Vertex V;
 91     int Nv, i;
 92 
 93     scanf("%d", &Nv);   /* 读入顶点个数 */
 94     Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */
 95     scanf("%d", &(Graph->Ne));  //读入边数
 96     if (Graph->Ne != 0)
 97     {
 98         E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */
 99         /* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */
100         for (i = 1; i <= Graph->Ne; i++)
101         {
102             scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
103             InsertEdge(Graph, E);
104         }
105     }
106     return Graph;
107 }
108 
109 #define Size 110
110 int Queue[Size];
111 int Front = 1;
112 int Rear = 0;
113 int size = 0;
114 int Succ(int Num)
115 {
116     if (Num < Size)
117         return Num;
118     else
119         return 0;
120 }
121 void EnQueue(int Num)
122 {
123     Rear = Succ(Rear + 1);
124     Queue[Rear] = Num;
125     size++;
126 }
127 int DeQueue()
128 {
129     int Num = Queue[Front];
130     Front = Succ(Front + 1);
131     size--;
132     return Num;
133 }
134 int IsEmpty()
135 {
136     return (size == 0) ? 1 : 0;
137 }
138 void Clear()
139 {
140     for (int i = 0; i < Size; i++)
141         Queue[i] = 0;
142     Front = 1;
143     Rear = 0;
144     size = 0;
145 }
146 //利用邻接表实现拓扑排序
147 int TopOrder[110];  //顺序存储排序后的顶点下标
148 int Earliest[110];
149 int Latest[110];
150 int TopSort(LGraph Graph)
151 {        //对Graph进为拓扑排序 ,TopOrder[] 顺序存储排序后的顶点下标
152     int Indegree[110];
153     int cnt = 0;
154     for (int i = 1; i <= Graph->Nv; i++)    //初始化Indegree
155         Indegree[i] = 0;
156     for (int i = 1; i <= Graph->Nv; i++)
157         for (PtrToAdjVNode W = Graph->G[i].FirstEdge; W; W = W->Next)
158         {
159             Indegree[W->AdjV]++;
160         }
161     for (int i = 1; i <= Graph->Nv; i++)
162         if (Indegree[i] == 0)
163         {
164             EnQueue(i);
165             Earliest[i] = 0;
166         }
167     //进入拓扑排序
168     while (!IsEmpty())
169     {
170         int V = DeQueue();
171         TopOrder[cnt++] = V;
172         for (PtrToAdjVNode W = Graph->G[V].FirstEdge; W; W = W->Next)
173         {
174             if ((Earliest[V] + W->Weight) > Earliest[W->AdjV])
175                 Earliest[W->AdjV] = Earliest[V] + W->Weight;
176             if (--Indegree[W->AdjV] == 0)
177             {
178                 EnQueue(W->AdjV);
179             }
180         }
181     }
182     int Max = -1;  //计算最后一个元素的 Earliest
183     int V;            //记录最后一个任务
184     if (cnt != Graph->Nv)
185         return 0;
186     else
187     {
188         for (int i = 1; i <= Graph->Nv; i++)
189         {
190             if (Earliest[i] > Max)
191             {
192                 Max = Earliest[i];
193                 V = i;
194             }
195         }
196     }
197 
198     Clear();  //初始化队列
199     //从末尾开始计算Latest[];
200     int Outdegree[110];  //计算出度
201     for (int i = 1; i <= Graph->Nv; i++)    //最后一个元素的 Earliest与Latest 一样 为了保证任务肯定完成
202         Latest[i] = INFINITY;
203     Latest[V] = Max;
204     for (int i = 1; i <= Graph->Nv; i++)  //初始化出度
205         Outdegree[i] = 0; 
206     for (int i = 1; i <= Graph->Nv; i++)
207         for (PtrToAdjVNode W = Graph->G[i].FirstEdge; W; W = W->Next)
208             Outdegree[i]++;
209     for (int i = Graph->Nv; i > 0; i--)
210         if (Outdegree[i] == 0)  //首先将出度为0的元素 入队列
211             EnQueue(i);
212     //开始计算Latest[]
213     
214 
215     while (!IsEmpty())
216     {
217         int V = DeQueue();
218         for (PtrToAdjVNode W = Graph->G[V].LastEdge; W; W = W->Next)
219         {
220             if (Latest[V] - W->Weight < Latest[W->AdjV])
221                 Latest[W->AdjV] = Latest[V] - W->Weight;
222             if (--Outdegree[W->AdjV] == 0)
223                 EnQueue(W->AdjV);
224         }
225     }
226     //计算完Latest后 再来计算机动时间 并把机动时间为0的一对元素入队列
227     Clear();
228     for(int i=1;i<=Graph->Nv;i++)
229         for (PtrToAdjVNode W = Graph->G[i].FirstEdge; W; W = W->Next)
230         {
231             if (Latest[W->AdjV] - Earliest[i] - W->Weight == 0)
232             {
233                 EnQueue(i);
234                 EnQueue(W->AdjV);
235             }
236         }
237     return Max;
238 }
239 
240 int main()
241 {
242     LGraph Graph = BuildGraph();
243     int Sum;
244     if (!(Sum = TopSort(Graph)))
245         printf("0");
246     else   //找到最大的那个Earliest 并将已经处理好的 队列输出
247     {
248         printf("%d
", Sum);
249         while (!IsEmpty())
250         {
251             printf("%d->", DeQueue());
252             printf("%d
", DeQueue());
253         }
254             //printf("%d->%d
", DeQueue(), DeQueue()); //注意函数读入顺序
255     }
256 }

View Code

把前面的题补一补

PTA 第1题求最大子列和问题

 1 #define _CRT_SECURE_NO_WARNINGS  
 2 #include<stdio.h>
 3 
 4 int main()
 5 {
 6     int N;
 7     int Array[100000] = { 0 };
 8     scanf("%d", &N);
 9     for (int i = 0; i < N; i++)
10         scanf("%d", &Array[i]);
11     int MaxSum, ThisSum;
12     MaxSum = ThisSum = 0;
13     for (int i = 0; i < N; i++)
14     {
15         ThisSum += Array[i];
16         if (ThisSum > MaxSum)
17             MaxSum = ThisSum;
18         if (ThisSum < 0)
19             ThisSum = 0;
20     }
21     printf("%d", MaxSum);
22 }

View Code

PTA 第2题也是求最大子列和问题注意题上要求(os:英语不好是硬伤而且我还有2个测试点没过

 1 #define _CRT_SECURE_NO_WARNINGS  
 2 #include<stdio.h>
 3 
 4 int main()
 5 {
 6     int N;
 7     int Array[10010] = { 0 };
 8     scanf("%d
", &N);
 9     for (int i = 0; i < N; i++)
10         scanf("%d", &Array[i]);
11     int MaxSum, ThisSum;
12     int Have=0;
13     MaxSum = ThisSum = 0;
14     int lo, hi;
15     lo = hi = 0;
16     int low = 0; //用来存储每次子列和开始的位置
17     for (int i = 0; i < N; i++)
18     {
19         if (Array[i] >= 0)
20             Have = 1;
21         ThisSum += Array[i];
22         if (ThisSum >MaxSum)   //如果更新最大元素 也同时更新hi与hi
23         {
24             MaxSum = ThisSum;
25             lo = low;
26             hi = i;
27         }
28         else if (ThisSum <0)   //lo永远从第一个正数开始
29         {
30             ThisSum = 0;
31             low++;            //使lo指向下一个
32         }
33     }
34     if (!Have)
35         printf("%d %d %d", MaxSum, Array[0], Array[N - 1]);
36     else
37         printf("%d %d %d", MaxSum, Array[lo], Array[hi]);
38 }

View Code

(这还可以用动态规划来解现在我还不会)

PTA第3题一元多项式的加法与乘法利用数组实现(os：之后会加上链表实现的)

这道题的本质应该是两个有序序列的合并

其算法与归并排序中的归并算法相似不同的在于对于次数相同时候的处理不同

  1 #define _CRT_SECURE_NO_WARNINGS  
  2 #include<stdio.h>
  3 //第一种方法
  4 //用数组来实现多项式的加与乘 在多项式稠密时候 这样的做法是没问题的(但需要注意数组空间不能开的太大)
  5 //但如果多项式比较稀疏 程序大部分时间都花在了乘以0和单步调试两个输入多项式的大量不存在的部分上
  6 //我下面就开的太大 导致程序爆掉
  7 /*void Mutiply(int Array1[], int Array2[],int N,int M)
  8 {
  9     int MutiArray[1000001] = { 0 };
 10     int num=0; //用来计数
 11     for(int i=0;i<1000000;i++)
 12         for (int j = 0; j < 1000000; j++)
 13         {
 14             MutiArray[i + j] += Array1[i] * Array2[j];
 15         }
 16     for (int i =1000000; i>=0; i--)
 17     {
 18         if (MutiArray[i] != 0)
 19             num++;
 20     }
 21     for (int i = 1000000; i >= 0; i--)
 22     {
 23         if (MutiArray[i] != 0)
 24             if (num != 1)
 25             {
 26                 printf("%d %d ", MutiArray[i], i);
 27                 num--;
 28             }
 29             else
 30                 printf("%d %d", MutiArray[i], i);
 31     }
 32 }
 33 void Sum(int Array1[], int Array2[],int    N,int M)
 34 {
 35     int SumArray[1000001] = { 0 };
 36     int num = 0; //用来计数
 37     for (int i = 0; i < 1001; i++)
 38         SumArray[i] += Array1[i] + Array2[i];
 39     for (int i = 1000000; i >= 0; i--)
 40     {
 41         if (SumArray[i] != 0)
 42             num++;
 43     }
 44     for (int i = 1000000; i >= 0; i--)
 45     {
 46         if (SumArray[i] != 0)
 47             if (num != 1)
 48             {
 49                 printf("%d %d ", SumArray[i], i);
 50                 num--;
 51             }
 52             else
 53                 printf("%d %d", SumArray[i], i);
 54     }
 55 }
 56 int main()
 57 {
 58     int Array1[1000001] = { 0 };
 59     int Array2[1000001] = { 0 };
 60     int N, M;
 61     scanf("%d", &N);
 62     for (int i = 0; i < N; i++)
 63     {
 64         int Coefficient;  //系数
 65         int index;        //指数
 66         scanf("%d %d", &Coefficient, &index);
 67         Array1[index] = Coefficient;
 68     }
 69     scanf("%d", &M);
 70     for (int i = 0; i < M; i++)
 71     {
 72         int Coefficient;  //系数
 73         int index;        //指数
 74         scanf("%d %d", &Coefficient, &index);
 75         Array2[index] = Coefficient;
 76     }
 77     Mutiply(Array1,Array2,N,M);
 78     printf("
");
 79     Sum(Array1, Array2,N,M);
 80     return 0;
 81 }*/
 82 
 83 //第二种方法
 84 //顺序存储结构表示非零项
 85 //利用结构数组
 86 //而使运算方便的要点是 使每一项按照指数大小有序进行存储
 87 
 88 struct Node
 89 {
 90     int Coefficient;    //系数
 91     int Exponent;        //指数
 92 }Polynomial1[100],Polynomial2[100],Polynomial[100],PolynomialM[100];
 93 int N, M;
 94 void Initialize()
 95 {
 96     scanf("%d", &N);
 97     for (int i = 0; i < N; i++)
 98     {
 99         int Coeff, Exp;
100         scanf("%d %d", &Coeff, &Exp);
101         Polynomial1[i].Coefficient = Coeff;
102         Polynomial1[i].Exponent = Exp;
103     }
104     scanf("%d", &M);
105     for (int i = 0; i < M; i++)
106     {
107         int Coeff, Exp;
108         scanf("%d %d", &Coeff, &Exp);
109         Polynomial2[i].Coefficient = Coeff;
110         Polynomial2[i].Exponent = Exp;
111     }
112 }
113 void InsertMuti(int l,int k,int i, int j)
114 {
115     for (int i = k ; i > l;i--)
116         PolynomialM[i] = PolynomialM[i-1];
117     PolynomialM[l].Coefficient = Polynomial1[i].Coefficient * Polynomial2[j].Coefficient;
118     PolynomialM[l].Exponent= Polynomial1[i].Exponent + Polynomial2[j].Exponent;
119 }
120 void Mutiply(int N,int M)
121 {
122     int k = 0;
123     for(int i=0;i<N;i++)
124         for (int j = 0; j < M; j++)
125         {
126             int MutiSum = Polynomial1[i].Exponent + Polynomial2[j].Exponent;
127             if (k == 0)
128             {
129                 PolynomialM[k].Coefficient = Polynomial1[i].Coefficient * Polynomial2[j].Coefficient;
130                 PolynomialM[k++].Exponent = MutiSum;
131             }
132             else
133             {
134                 int l = 0;
135                 int have = 0;
136                 for (; l < k; l++)
137                 {
138                     if (MutiSum == PolynomialM[l].Exponent)
139                     {
140                         have = 1;
141                         PolynomialM[l].Coefficient += Polynomial1[i].Coefficient * Polynomial2[j].Coefficient;
142                         break;
143                     }
144                     else if (MutiSum > PolynomialM[l].Exponent)
145                     {
146                         have = 1;
147                         InsertMuti(l,k,i, j);
148                         k++;
149                         break;
150                     }
151                 }
152                 if (l == k&&!have)
153                 {
154                     InsertMuti(l, k, i, j);
155                     k++;
156                 }
157             }
158         }
159     int have = 0;
160     for(int i=0;i<k;i++)
161     {
162         if (PolynomialM[i].Coefficient == 0)
163             continue;
164         if (i != k - 1)
165         {
166             have = 1;
167             printf("%d %d ", PolynomialM[i].Coefficient, PolynomialM[i].Exponent);
168         }
169         else
170         {
171             have = 1;
172             printf("%d %d
", PolynomialM[i].Coefficient, PolynomialM[i].Exponent);
173         }
174     }
175     if (!have)
176         printf("0 0
");
177 }
178 void Sum(int N,int M)
179 {
180     int i = 0;    //对多项式1进行遍历
181     int j = 0;    //对多项式2进行遍历
182     int k = 0;  //用于总多项式
183     while (i < N||j<M)
184     {
185         if (i < N && (j >= M || Polynomial1[i].Exponent > Polynomial2[j].Exponent))
186         {
187             Polynomial[k++] = Polynomial1[i++];
188         }
189         if (j < M && (i >= N || Polynomial1[i].Exponent < Polynomial2[j].Exponent))
190         {
191             Polynomial[k++] = Polynomial2[j++];
192         }
193         if (i < N && j < M && Polynomial1[i].Exponent == Polynomial2[j].Exponent)
194         {
195             Polynomial[k].Coefficient = Polynomial1[i].Coefficient + Polynomial2[j].Coefficient;
196             Polynomial[k].Exponent = Polynomial1[i].Exponent;
197             if (Polynomial[k].Coefficient != 0)
198                 k++;
199             i++;
200             j++;
201         }
202     }
203     int have=0;
204     for (int i = 0; i < k; i++)
205     {
206         /*if (Polynomial[i].Coefficient == 0)
207             continue;*/
208         if (i != k - 1)
209         {
210             have = 1;
211             printf("%d %d ", Polynomial[i].Coefficient, Polynomial[i].Exponent);
212         }
213         else
214         {
215             have = 1;
216             printf("%d %d", Polynomial[i].Coefficient, Polynomial[i].Exponent);
217         }
218     }
219     if (!have)
220         printf("0 0");
221 }
222 int main()
223 {
224     Initialize();
225     Mutiply(N, M);
226     Sum(N, M);
227 }

View Code

广义表(Generalized List)

　　广义表是线性表的推广

　　对于线性表而言，n个元素都是基本的单元素

　　广义表中，这些元素不仅可以是单元素也可以是另一个广义表

十字链表是一种典型的多重链表----十字链表来存储稀疏矩阵

PTA第5题利用栈混洗来解决 (os：之前看的时候没认值看。。现在又重新看一遍偷懒的下场)

  1 #define _CRT_SECURE_NO_WARNINGS  
  2 #include<stdio.h>
  3 #include<malloc.h>
  4 typedef struct Stack* S;
  5 struct Stack
  6 {
  7     int Top;
  8     int Elements[1000];
  9 };
 10 S A, B, C;
 11 int N, M, K;
 12 void Initialize()
 13 {
 14     A = (S)malloc(sizeof(struct Stack));
 15     B = (S)malloc(sizeof(struct Stack));
 16     C = (S)malloc(sizeof(struct Stack));
 17     for (int i = 0; i < 1000; i++)
 18     {
 19         A->Elements[i] = 0;
 20         B->Elements[i] = 0;
 21         C->Elements[i] = 0;
 22     }
 23     A->Top = -1;
 24     B->Top = -1;
 25     C->Top = -1;
 26 }
 27 
 28 int IsEmpty(S S)
 29 {
 30     return S->Top == -1;
 31 }
 32 
 33 void Push(S S,int Element)
 34 {
 35     S->Elements[++S->Top] = Element;
 36 }
 37 
 38 int Pop(S S)
 39 {
 40     int Element = S->Elements[S->Top];
 41     S->Top--;
 42     return Element;
 43 }
 44 
 45 int Top(S S)
 46 {
 47     return S->Elements[S->Top];
 48 }
 49 
 50 int IsFullOfB()
 51 {
 52     return B->Top+1== M;
 53 }
 54 
 55 void BuildS()
 56 {
 57     scanf("%d %d", &M, &N);
 58     for (int i=N;i>0;i--)
 59         Push(A, i);
 60 }
 61 
 62 void Clear()
 63 {
 64     C->Top = -1;
 65     A->Top = N - 1;
 66     B->Top = -1;
 67 }
 68 
 69 int Judget()
 70 {
 71     Clear();
 72     for (int i = 0; i < N; i++)
 73     {
 74         int num;
 75         scanf("%d", &num);
 76         Push(C, num);
 77     }
 78     int k = 0;  //用来访问C
 79     while(!IsEmpty(B)||!IsEmpty(A))
 80     {
 81         if (IsEmpty(B))
 82             Push(B, Pop(A));
 83         if (Top(B) != C->Elements[k] && IsFullOfB())
 84             return 0;
 85         else if(Top(B)!=C->Elements[k])
 86             Push(B, Pop(A));
 87         else
 88         {
 89             Pop(B);
 90             k++;
 91         }
 92     }
 93     if (k == N)
 94         return 1;
 95     else
 96         return 0;
 97 }
 98 
 99 int main()
100 {
101     Initialize();
102     BuildS();
103     scanf("%d", &K);
104     while(K--)
105         if (Judget())
106             printf("YES
");
107         else
108             printf("NO
");
109     return 0;
110 }

View Code

PTA第4题逆转链表我直接卡在数据输入上了

拿整型变量来存储地址更容易做

下面是在网上找到题解(os:这大佬的思路真的清晰)

放链接:https://blog.csdn.net/liyuanyue2017/article/details/83269991

 1 #include<stdio.h>
 2 #define MaxSize 100005
 3 int main()
 4 {
 5     int Data[MaxSize] = { 0 };
 6     int Next[MaxSize] = { 0 };
 7     int List[MaxSize] = { 0 };
 8     int FirstAddr, N, K;
 9     scanf("%d %d %d", &FirstAddr, &N, &K);
10     for (int i = 0; i < N; i++)        //将元素读入
11     {
12         int TempAddr,TempData,TempNext;
13         scanf("%d %d %d",&TempAddr,&TempData, &TempNext);
14         Data[TempAddr] = TempData;
15         Next[TempAddr] = TempNext;
16     }
17     //对元素进行重新写入
18     int Sum= 0;
19     while (FirstAddr!=-1)
20     {
21         List[Sum++] = FirstAddr;
22         FirstAddr = Next[FirstAddr];
23     }// 读入成功
24     //开始逆转
25     /*for(int i=0;i<(N/K);i++)
26         for (int j = i * K; j < i * K + K / 2; j++)
27         {
28             int tmp = List[j];
29             List[j] = List[(i + 1) * K -1-j-(i*K)];
30             List[(i + 1) * K - 1-j-(i*K)] = tmp;
31         }*/  //这段不能使答案全对
32     for(int i=0;i<Sum-Sum%K;i+=K){  // 每 K 个结点一个区间
33     for(int j=0;j<K/2;j++){  // 反转链表
34             int t = List[i+j];
35             List[i+j] = List[i+K-j-1];
36             List[i+K-j-1] = t;
37         }
38     }
39     for (int i = 0; i < Sum-1; i++)
40     {
41         printf("%05d %d %05d
", List[i], Data[List[i]], List[i+1]);
42     }
43     printf("%05d %d -1",List[Sum-1],Data[List[Sum-1]]);
44     return 0;
45 }