[ C 文章收集 ] 2D arrays - dynamic allocation and freeing

來源自 這裡 
Preface: 
If the size is known at compile time; you don't need to allocate anything; let the compiler take care of it (no malloc(), no free()) 

view plaincopy to clipboardprint?

1.  int a[5][5];  
2. ...  
3. ...  
4.   a[i][j] = xxx;  
5. ...  
6. ...  

2D array allocation: 
Now, if you want a 2D array of int, and the dimensions are not known at compile time, here's a way to do it. Suppose we want an array[size_x][size_y] of int, wheresize_x and size_y are variables. The "array" name will be a "pointer to a pointer to an int". 

1. Allocate memory for size_x pointers to int. The address returned by malloc() will be the "array".
2. For each of the pointers, allocate memory for size_y ints.
Then address the individual elements with array[][] notation. When you don't need it any more:
3. Free the memory allocated for the ints.
4. Free the memory allocated for the pointers.

Example: 
Here's an example (I have given size_x and size_y specific values for purposes of illustration, but these could be obtained from user input or from other program calculations, or whatever.) 

view plaincopy to clipboardprint?

1. /* illustration of dynamically allocated 2D array */  
2. #include   
3. #include   
4.   
5. int main()  
6. {  
7.   int i; /* general purpose variable used for loop index */  
8.   int j; /* general purpose variable used for loop index */  
9.   
10.   int **a;     /* this is the array name */  
11.   int size_x; /* this variable will be used for the first  dimension */  
12.   int size_y; /* this variable will be used for the second dimension */  
13.   
14.   /* suppose we want an array of int: a[5][3] */  
15.   size_x = 5;  
16.   size_y = 3;  
17.   
18.   /*  allocate storage for an array of pointers */  
19.   a = malloc(size_x * sizeof(int *));  
20.   
21.   /* for each pointer, allocate storage for an array of ints */  
22.   for (i = 0; i < size_x; i++) {  
23.     a[i] = malloc(size_y * sizeof(int));  
24.   }  
25.   
26.   /* just for kicks, show the addresses (note: not all sequential) */  
27.   /* assign an arbitrary value to each element        */  
28.   for (i = 0; i < size_x; i++) {  
29.     for (j = 0; j < size_y; j++) {  
30.       printf("&a[%d][%d] = %p\n", i, j, &a[i][j]); /* show the addresses */  
31.       a[i][j] = i * size_y + j; /* just some unique number for each element */  
32.     }  
33.     printf ("\n");  
34.   }  
35.   
36.   /* now show the contents that were assigned */  
37.   for (i = 0; i < size_x; i++) {  
38.     for (j = 0; j < size_y; j++) {  
39.       printf("a[%d][%d] = %2d\n", i, j, a[i][j]);  
40.     }  
41.     printf ("\n");  
42.   }  
43.   
44.   /* now for each pointer, free its array of ints */  
45.   for (i = 0; i < size_y; i++) {  
46.     free(a[i]);  
47.   }  
48.   /* now free the array of pointers */  
49.   free(a);  
50.   
51.   return 0;  
52. }  

Remember: always free() everything that you got from malloc(), but never anything else. 
C++ Programmers: Do the same, but use new and delete instead of malloc() and free().

[C 範例代碼] Infix to Postfix translation (Recursive approach)

前言:
Infix 是人類使用的算術表示方法, 下面是 Wiki 對 Infix notation 的說明:

Infix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on (e.g. 2 + 2). It is not as simple to parse by computers as prefix notation ( e.g. + 2 2 ) or postfix notation ( e.g. 2 2 + ), but many programming languages use it due to its familiarity.

問題在於電腦程式要解析 Infix 的表示式有一定的困難度, 因此存在了 Infix -> Postfix 的轉換. 因為相對 Infix 來說, Postfix 對電腦程式來說容易解析.

範例代碼:
下面代碼為 C 語言的 Infix->Postfix 轉換範例代碼:

view plaincopy to clipboardprint?

1. #include <stdlib.h>
2. #include <stdio.h>
3. #include <string.h>   
4.   
5. #define bool int  
6. #define true 1  
7. #define false 0  
8.   
9. char operators[] = "+-*/^";  
10.   
11. struct Stk_Chr  
12. {  
13.     int pt;  
14.     char buffer[256];  
15. } Stack_Chr;  
16.   
17. int Stack_Chr_Size(struct Stk_Chr *pstack)  
18. {  
19.     return pstack->pt;  
20. }  
21.   
22. void Stack_Chr_Init(struct Stk_Chr *pstack)  
23. {  
24.     pstack->pt =0;  
25.     memset(pstack->buffer,0,sizeof(char)*256);  
26. }  
27.   
28. bool Stack_Chr_Is_Empty(struct Stk_Chr *pstack)  
29. {  
30.     if(pstack->pt ==0)  
31.         return true;  
32.     return false;  
33. }  
34.   
35. bool Stack_Chr_Is_Full(struct Stk_Chr *pstack)  
36. {  
37.     if(pstack->pt >=255)  
38.         return true;  
39.     return false;  
40. }  
41.   
42. bool Stack_Chr_Push(struct Stk_Chr *pstack, char data)  
43. {  
44.     if(Stack_Chr_Is_Full(pstack))  
45.         return false;  
46.     pstack->buffer[pstack->pt] = data;  
47.     pstack->pt++;  
48.     return true;  
49. }  
50.   
51. bool Stack_Chr_Pop(struct Stk_Chr *pstack, char *data)  
52. {  
53.     if(Stack_Chr_Is_Empty(pstack))  
54.         return false;  
55.     pstack->pt--;  
56.     *data = pstack->buffer[pstack->pt];  
57.   
58.     return true;  
59. }  
60.   
61. bool Stack_Chr_PopOut(struct Stk_Chr *pstack)  
62. {  
63.     if(Stack_Chr_Is_Empty(pstack))  
64.         return false;  
65.     pstack->pt--;  
66.   
67.     return true;  
68. }  
69.   
70. bool Stack_Chr_Peer(struct Stk_Chr *pstack, char *data)  
71. {  
72.     if(Stack_Chr_Is_Empty(pstack))  
73.         return false;  
74.     *data = pstack->buffer[(pstack->pt)-1];  
75.     return true;  
76. }  
77.   
78. bool isOperator(char op)  
79. {  
80.     char *pch;  
81.     pch = strchr(operators, op);  
82.     if(pch!=NULL)  
83.     {  
84.         return true;  
85.     }  
86.     else  
87.     {  
88.         return false;  
89.     }  
90. }  
91.   
92. bool isSubexpr(char op)  
93. {  
94.     if(op == '(') return true;  
95.     return false;  
96. }  
97.   
98. int priority(char op)  
99. {  
100.   switch(op) {  
101.   case '+': case '-': return 1;  
102.   case '*': case '/': return 2;  
103.   default:            return 0;  
104.   }  
105. }  
106.   
107. char* InfixToPostfix(char* infixExp, char* opostfixExp, int s, int e)  
108. {  
109.     int i, j, k, idx=0;  
110.     struct Stk_Chr stack;   
111.     Stack_Chr_Init(&stack);  
112.   
113.     char tchr;  
114.     char *postfixExpr = (char*)malloc(100*sizeof(char));  
115.     for(i=s; i
116.     {  
117.         if(infixExp[i]== ' ') continue;  
118.         else if(isOperator(infixExp[i]))  
119.         {  
120.             if(Stack_Chr_Is_Empty(&stack)==1)  
121.             {  
122.                 Stack_Chr_Push(&stack, infixExp[i]);  
123.             }  
124.             else  
125.             {  
126.                 Stack_Chr_Peer(&stack, &tchr);  
127.                 if(priority(infixExp[i]) > priority(tchr))  
128.                 {  
129.                     Stack_Chr_Push(&stack, infixExp[i]);  
130.                 }  
131.                 else  
132.                 {  
133.                     postfixExpr[idx] = tchr;  
134.                     Stack_Chr_PopOut(&stack);  
135.                     idx+=1;  
136.                     Stack_Chr_Push(&stack, infixExp[i]);  
137.                 }  
138.             }  
139.         }  
140.         else if(isSubexpr(infixExp[i]))  
141.         {  
142.             int cnt = 1;  
143.             int si = i+1;  
144.             char ichr;  
145.             while(cnt > 0 && si < strlen(infixExp))  
146.             {  
147.                 ichr = infixExp[si];  
148.                 if(ichr == '(') cnt++;  
149.                 else if(ichr==')') cnt--;  
150.                 si++;  
151.             }  
152.             if(cnt == 0)  
153.             {  
154.                 si--;  
155.                 InfixToPostfix(infixExp, postfixExpr, i+1, si);  
156.                 idx = strlen(postfixExpr);  
157.                 i = si;  
158.             }  
159.             else  
160.             {  
161.                 printf("Illegal infix expression!\n");  
162.                 return;  
163.             }  
164.         }  
165.         else  
166.         {  
167.             postfixExpr[idx]=infixExp[i];  
168.             idx++;  
169.         }  
170.     }  
171.     while(Stack_Chr_Is_Empty(&stack)==0)  
172.     {  
173.         Stack_Chr_Pop(&stack, &tchr);  
174.         postfixExpr[idx] = tchr;  
175.         idx++;  
176.     }  
177.     strcat(opostfixExp, postfixExpr);  
178.     free(postfixExpr);  
179.     return opostfixExp;  
180. }  
181.   
182. int main()  
183. {  
184.     int i, j, k, idx=0;  
185.     char expr[100];  
186.     char *postfixExpr = (char*)malloc(100*sizeof(char));;  
187.     memset(postfixExpr,0,sizeof(char)*100);  
188.     printf("Give Infix expression: ");  
189.     scanf("%s", expr);  
190.     InfixToPostfix(expr, postfixExpr, 0, strlen(expr));  
191.     printf("\t[Info] Postfix=%s\n", postfixExpr);  
192.     free(postfixExpr)
193.     return 0;  
194. }  

執行結果:

Give Infix expression: a*(b+c)+d*e
[Info] Postfix=abc+*de*+

上面再 stdin 輸入 Infix 表示式 "a*(b+c)+d*e" 得到的 Postfix 表示式為 "abc+*de*+". 有關 Java 版本的 Infix->Postfix 轉換可以參考:
[ Data Structures with Java ] Section 14.5 : Infix Expression Evaluation

補充說明:
* Algorithm Gossip: 中序式轉後序式（前序式）

平常所使用的運算式，主要是將運算元放在運算子的兩旁，例如a+b/d這樣的式子，這稱之為中序（Infix）表示式，對於人類來說，這樣的式子很容易理 解，但由於電腦執行指令時是有順序的，遇到中序表示式時，無法直接進行運算，而必須進一步判斷運算的先後順序，所以必須將中序表示式轉換為另一種表示方 法...