一 写在开头
1.1 本文内容
数据结构栈的实现。
二 栈的实现
不多说了，请直接看代码。
1 // stack.h 2 3 /* 为了使用bool */ 4 #include <stdbool.h> 5 6 #ifndef _H_STACK_H 7 #define _H_STACK_H 8 9 /* 数据类型 */ 10 typedef char type; 11 12 /* 栈结点 */ 13 typedef struct tsNode 14 { 15 type data; 16 struct tsNode *next; 17 } Node; 18 19 /* 栈类型 */ 20 typedef struct tsStack 21 { 22 Node *top; 23 unsigned int size; 24 } Stack; 25 26 /* 初始化Stack */ 27 Stack * 28 StackInit(void); 29 30 /* 判断栈是否为空。为空返回true，否则返回false */ 31 bool 32 IsEmpty(Stack *); 33 34 /* 入栈操作 */ 35 void 36 StackPush(Stack *, type); 37 38 /* 出栈操作 */ 39 type 40 StackPop(Stack *); 41 42 /* 取得栈顶元素 */ 43 type 44 GetTop(Stack *); 45 #endif
1 // stack.c 2 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <stdbool.h> 6 #include "stack.h" 7 8 /* 功能：栈初始化 9 * 输入：无 10 * 输出：一个指向Stack型的指针，指针所指对象已被初始化 11 */ 12 Stack * 13 StackInit(void) 14 { 15 Stack *s = NULL; 16 17 s = (Stack *)malloc(sizeof(Stack)); 18 if (s == NULL) 19 exit(EXIT_FAILURE); 20 s->top = NULL; 21 s->size = 0; 22 return s; 23 } 24 25 /* 功能：判断栈是否为空。为空返回true，否则返回false 26 * 输入：一个指向Stack型的指针 27 * 输出：一个bool型变量 28 */ 29 bool 30 IsEmpty(Stack *s) 31 { 32 /* s未被初始化 */ 33 if (s == NULL) 34 exit(EXIT_FAILURE); 35 else 36 return ((s->size) == 0); 37 } 38 39 /* 功能：入栈操作 40 * 输入：一个指向Stack型的指针，一个type型待入栈变量 41 * 输出：无 42 */ 43 void 44 StackPush(Stack *s, type x) 45 { 46 Node *temp = (Node *)malloc(sizeof(Node)); 47 48 if (temp == NULL) 49 exit(EXIT_FAILURE); 50 temp->data = x; 51 52 /* 若s未被初始化 */ 53 if (s == NULL) 54 exit(EXIT_FAILURE); 55 temp->next = s->top; 56 s->top = temp; 57 s->size = (s->size) + 1; 58 } 59 60 /* 功能：出栈操作 61 * 输入：一个指向Stack型的指针 62 * 输出：被出栈的元素 63 */ 64 type 65 StackPop(Stack *s) 66 { 67 Node *p = NULL; 68 type r; 69 70 if (IsEmpty(s)) 71 exit(EXIT_FAILURE); 72 p = s->top->next; 73 r = s->top->data; 74 free(s->top); 75 s->top = p; 76 s->size = (s->size) - 1; 77 return r; 78 } 79 80 /* 功能：返回栈顶元素 81 * 输入：一个指向Stack型的指针 82 * 输出：栈顶元素 83 */ 84 type 85 GetTop(Stack *s) 86 { 87 if (IsEmpty(s)) 88 exit(EXIT_FAILURE); 89 return s->top->data; 90 }
1 #include <stdio.h> 2 #include "stack.h" 3 4 int main(int argc, char *argv[]) 5 { 6 Stack *s = StackInit(); 7 8 /* test passed 9 printf("s->top = %pn", s->top); 10 printf("s->size = %un", s->size); 11 printf("s is empty: "); 12 IsEmpty(s) ? printf("yesn") : printf("non"); 13 */ 14 15 /* test passed 16 StackPush(s, 'h'); 17 StackPush(s, 'e'); 18 StackPush(s, 'l'); 19 StackPush(s, 'l'); 20 StackPush(s, 'o'); 21 printf("s is empty: "); 22 IsEmpty(s) ? printf("yesn") : printf("non"); 23 printf("s->size = %un", s->size); 24 25 while ((s->size) > 0) 26 { 27 printf("%cn", StackPop(s)); 28 } 29 printf("s is empty: "); 30 IsEmpty(s) ? printf("yesn") : printf("non"); 31 */ 32 33 /* test passed 34 StackPush(s, 'h'); 35 StackPush(s, 'e'); 36 StackPush(s, 'l'); 37 StackPush(s, 'l'); 38 StackPush(s, 'o'); 39 while (IsEmpty(s) == false) 40 { 41 printf("%cn", GetTop(s)); 42 StackPop(s); 43 } 44 printf("s is empty: "); 45 IsEmpty(s) ? printf("yesn") : printf("non"); 46 */ 47 48 // 栈的内存组织情况 - pass 49 /* 当s为空栈时内存组织情况 50 * p s - 0x602010 51 * p s->top - 0x0 52 * p s->size - 0 53 */ 54 55 StackPush(s, 'h'); 56 /* 当s中有一个值为'h'的元素时内存组织情况 57 * p s - 0x602010 58 * p s->top - 0x602030 59 * p s->size - 1 60 * p s->top->data - 'h' 61 * p s->top->next - 0x0 62 */ 63 64 StackPush(s, 'e'); 65 /* 当s中有两个元素时内存组织情况 66 * p s - 0x602010 67 * p s->top - 0x602050 68 * p s->size - 2 69 * p s->top->data - 'e' 70 * p s->top->next - 0x602030 71 * p s->top->next->data - 'h' 72 * p s->top->next->next - 0x0 73 */ 74 75 StackPop(s); 76 /* 当将栈顶元素弹出后内存组织情况 77 * p s - 0x602010 78 * p s->top - 0x602030 79 * p s->size - 1 80 * p s->top->data - 'h' 81 * p s->top->next - 0x0 82 */ 83 84 return 0; 85 }
注意：为了成功编译包含了stack.h的主程序，你需要使用下面的命令。也即必须将stack.c编译成目标文件，供链接程序链接使用，否则链接程序将报错。不同于C标准库的使用，因为C标准库默认采用动态链接的方式，所用标准库中的函数均已经被编译好了，放在特定的目录下面，链接程序只需去目录中找相对应的目标文件即可。这里我们必须将stack.c编译成目标文件，供主程序链接时使用。
gcc main.c stack.c
三 栈的一个应用实例
来做题吧！题目来源在此。需要说明的是下面的代码质量不好，因为代码是在上面的栈代码基础上拼凑而来的。为了记录每个字符在输入字符串中的位置，在栈结点中添加了一个index字段用于记录结点位置。算法原理很简单：将每一个字符入栈，判断入栈的字符是否为右括号（')'），如果是则将左右括号出栈并将二者在字符串中的位置按题目要求的顺序打印出来即可。
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 #include <stdbool.h> 5 #define ARR_MAX_LEN 128 6 static char array[ARR_MAX_LEN]; 7 8 /* 数据类型 */ 9 typedef char type; 10 11 /* 栈结点 */ 12 typedef struct tsNode 13 { 14 int index; 15 type data; 16 struct tsNode *next; 17 } Node; 18 19 /* 栈类型 */ 20 typedef struct tsStack 21 { 22 Node *top; 23 unsigned int size; 24 } Stack; 25 26 /* 初始化Stack */ 27 Stack * 28 StackInit(void); 29 30 /* 判断栈是否为空。为空返回true，否则返回false */ 31 bool 32 IsEmpty(Stack *); 33 34 /* 入栈操作 */ 35 void 36 StackPush(Stack *, int, type); 37 38 /* 出栈操作 */ 39 type 40 StackPop(Stack *); 41 42 /* 取得栈顶元素 */ 43 Node * 44 GetTop(Stack *); 45 46 /* 功能：栈初始化 47 * 输入：无 48 * 输出：一个指向Stack型的指针，指针所指对象已被初始化 49 */ 50 Stack * 51 StackInit(void) 52 { 53 Stack *s = NULL; 54 55 s = (Stack *)malloc(sizeof(Stack)); 56 if (s == NULL) 57 exit(EXIT_FAILURE); 58 s->top = NULL; 59 s->size = 0; 60 return s; 61 } 62 63 /* 功能：判断栈是否为空。为空返回true，否则返回false 64 * 输入：一个指向Stack型的指针 65 * 输出：一个bool型变量 66 */ 67 bool 68 IsEmpty(Stack *s) 69 { 70 /* s未被初始化 */ 71 if (s == NULL) 72 exit(EXIT_FAILURE); 73 else 74 return ((s->size) == 0); 75 } 76 77 /* 功能：入栈操作 78 * 输入：一个指向Stack型的指针，一个type型待入栈变量 79 * 输出：无 80 */ 81 void 82 StackPush(Stack *s, int index, type x) 83 { 84 Node *temp = (Node *)malloc(sizeof(Node)); 85 86 if (temp == NULL) 87 exit(EXIT_FAILURE); 88 temp->index = index; 89 temp->data = x; 90 91 /* 若s未被初始化 */ 92 if (s == NULL) 93 exit(EXIT_FAILURE); 94 temp->next = s->top; 95 s->top = temp; 96 s->size = (s->size) + 1; 97 } 98 99 /* 功能：出栈操作 100 * 输入：一个指向Stack型的指针 101 * 输出：被出栈的元素 102 */ 103 type 104 StackPop(Stack *s) 105 { 106 Node *p = NULL; 107 type r; 108 109 if (IsEmpty(s)) 110 exit(EXIT_FAILURE); 111 p = s->top->next; 112 r = s->top->data; 113 free(s->top); 114 s->top = p; 115 s->size = (s->size) - 1; 116 return r; 117 } 118 119 /* 功能：返回栈顶元素 120 * 输入：一个指向Stack型的指针 121 * 输出：栈顶元素 122 */ 123 Node * 124 GetTop(Stack *s) 125 { 126 if (IsEmpty(s)) 127 exit(EXIT_FAILURE); 128 return s->top; 129 } 130 131 int 132 main(int argc, char *argv[]) 133 { 134 //freopen("in.txt", "r", stdin); 135 int i, len, temp; 136 Stack *s = StackInit(); 137 138 scanf("%s", array); 139 len = strlen(array); 140 for (i = 0; i < len; i++) 141 { 142 StackPush(s, i, array[i]); 143 if ((GetTop(s))->data == ')') 144 { 145 temp = GetTop(s)->index; 146 StackPop(s); 147 printf("%d %dn", (GetTop(s))->index, temp); 148 StackPop(s); 149 } 150 } 151 152 //fclose(stdin); 153 return 0; 154 }
四 版本二
相较于上面的版本一有细微的改动，增加了函数ClearStack()用于清空栈。
1 /* stack.h */ 2 3 #ifndef _H_STACK_H 4 #define _H_STACK_H 5 6 #include <stdbool.h> 7 8 typedef char dtype; // 数据类型 9 10 typedef struct Node // 节点类型 11 { 12 dtype data; 13 struct Node * next; 14 } tNode; 15 16 typedef struct Stack // 栈类型 17 { 18 tNode * top; 19 unsigned long long size; 20 } tStack; 21 22 /* 栈初始化 */ 23 tStack * 24 StackInit(void); 25 26 /* 判断栈是否为空。为空返回true；否则返回false */ 27 bool 28 IsEmpty(tStack *); 29 30 /* 入栈 */ 31 void 32 StackPush(tStack *, dtype); 33 34 /* 出栈 */ 35 dtype 36 StackPop(tStack *); 37 38 /* 取得栈顶元素 */ 39 dtype 40 GetTop(tStack *); 41 42 /* 清空栈 */ 43 void 44 ClearStack(tStack *); 45 46 #endif
1 /* stack.c */ 2 3 #include <stdlib.h> 4 #include <stdbool.h> 5 #include "stack.h" 6 7 /* 描述：栈初始化 8 * 输入：无 9 * 输出：一个指向tStack型的指针，指针所指向对象已被初始化 10 */ 11 tStack * 12 StackInit(void) 13 { 14 tStack * s = (tStack *)malloc(sizeof(tStack)); 15 if (s == NULL) 16 exit(EXIT_FAILURE); 17 s->top = NULL; 18 s->size = 0; 19 return s; 20 } 21 22 /* 描述：判断栈是否为空。为空返回true，否则返回false 23 * 输入：一个指向tStack型的指针 24 * 输出：true或者false 25 */ 26 bool 27 IsEmpty(tStack * s) 28 { 29 /* s未被初始化 */ 30 if (s == NULL) 31 exit(EXIT_FAILURE); 32 return (s->size) == 0; 33 } 34 35 /* 描述：入栈操作 36 * 输入：一个指向tStack型的指针，一个dtype型待入栈变量 37 * 输出：无 38 */ 39 void 40 StackPush(tStack * s, dtype x) 41 { 42 /* s未被初始化 */ 43 if (s == NULL) 44 exit(EXIT_FAILURE); 45 tNode * temp = (tNode *)malloc(sizeof(tNode)); 46 if (temp == NULL) 47 exit(EXIT_FAILURE); 48 temp->data = x; 49 temp->next = s->top; 50 s->top = temp; 51 s->size = (s->size) + 1; 52 } 53 54 /* 描述：出栈操作 55 * 输入：一个指向tStack型的指针 56 * 输出：一个dtype型的被出栈元素 57 */ 58 dtype 59 StackPop(tStack * s) 60 { 61 tNode * p = NULL; 62 dtype r; 63 64 if (IsEmpty(s)) 65 exit(EXIT_FAILURE); 66 p = s->top->next; 67 r = s->top->data; 68 free(s->top); 69 s->top = p; 70 s->size = (s->size) - 1; 71 return r; 72 } 73 74 /* 描述：取得栈顶元素而不出栈 75 * 输入：一个指向tStack型的指针 76 * 输出：栈顶元素 77 */ 78 dtype 79 GetTop(tStack * s) 80 { 81 if (IsEmpty(s)) 82 exit(EXIT_FAILURE); 83 return s->top->data; 84 } 85 86 /* 描述：清空栈 87 * 输入：一个指向tStack型的指针 88 * 输出：无 89 */ 90 void 91 ClearStack(tStack * s) 92 { 93 /* s未被初始化 */ 94 if (s == NULL) 95 exit(EXIT_FAILURE); 96 while (IsEmpty(s) == false) 97 StackPop(s); 98 free(s); 99 }
1 /* tstack.c */ 2 3 #include <stdio.h> 4 #include "stack.h" 5 6 int main(int argc, char *argv[]) 7 { 8 tStack * s = StackInit(); 9 10 // test pass 11 // printf("s->top = %pn", s->top); 12 // printf("s->size = %llun", s->size); 13 // printf("s is empty: "); 14 // IsEmpty(s) ? printf("yesn") : printf("non"); 15 16 // test pass 17 // StackPush(s, 'h'); 18 // StackPush(s, 'e'); 19 // StackPush(s, 'l'); 20 // StackPush(s, 'l'); 21 // StackPush(s, 'o'); 22 // printf("s is empty: "); 23 // IsEmpty(s) ? printf("yesn") : printf("non"); 24 // printf("s->size = %llun", s->size); 25 // 26 // while ((s->size) > 0) 27 // { 28 // printf("%cn", StackPop(s)); 29 // } 30 // printf("s is empty: "); 31 // IsEmpty(s) ? printf("yesn") : printf("non"); 32 33 // test pass 34 // StackPush(s, 'h'); 35 // StackPush(s, 'e'); 36 // StackPush(s, 'l'); 37 // StackPush(s, 'l'); 38 // StackPush(s, 'o'); 39 // while (IsEmpty(s) == false) 40 // { 41 // printf("%cn", GetTop(s)); 42 // StackPop(s); 43 // } 44 // printf("s is empty: "); 45 // IsEmpty(s) ? printf("yesn") : printf("non"); 46 47 // 栈的内存组织情况 48 /* 当s为空栈时内存组织情况 49 * p s - 0x602010 50 * p s->top - 0x0 51 * p s->size - 0 52 */ 53 54 // StackPush(s, 'h'); 55 /* 当s中有一个值为'h'的元素时内存组织情况 56 * p s - 0x602010 57 * p s->top - 0x602030 58 * p s->size - 1 59 * p s->top->data - 'h' 60 * p s->top->next - 0x0 61 */ 62 63 // StackPush(s, 'e'); 64 /* 当s中有两个元素时内存组织情况 65 * p s - 0x602010 66 * p s->top - 0x602050 67 * p s->size - 2 68 * p s->top->data - 'e' 69 * p s->top->next - 0x602030 70 * p s->top->next->data - 'h' 71 * p s->top->next->next - 0x0 72 */ 73 74 // StackPop(s); 75 /* 当将栈顶元素弹出后内存组织情况 76 * p s - 0x602010 77 * p s->top - 0x602030 78 * p s->size - 1 79 * p s->top->data - 'h' 80 * p s->top->next - 0x0 81 */ 82 83 // StackPop(s); 84 /* 当将栈元素全弹出后内存组织情况 85 * p s - 0x602010 86 * p s->top - 0x0 87 * p s->size - 0 88 */ 89 90 // test pass 91 // StackPush(s, 'h'); 92 // StackPush(s, 'e'); 93 // ClearStack(s); 94 /* 当栈s被清空后，变量s被清除出了上下文中 */ 95 96 return 0; 97 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
