• 数据结构与算法3---栈与队

    一、栈

    1、顺序栈

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include   
    3. #include    //开辟空间
    4.  
    5. #define MAXSIZE 50
    6.  
    7. //顺序栈的基本算法
    8. typedef struct {
    9. 	int stack[MAXSIZE];
    10. 	int top;
    11. }SqStack;
    12.  
    13. //初始化
    14. void InitStack(SqStack* S) {
    15. 	S->top = -1;
    16. }
    17.  
    18. //判断栈是否为空
    19. int StackEmpty(SqStack S) {
    20. 	if (S.top == -1) {
    21. 		return 1;
    22. 	}
    23. 	return 0;
    24. }
    25.  
    26. //进栈
    27. void StackPush(SqStack* S,int x) {
    28. 	if (S->top == MAXSIZE - 1) {
    29. 		printf("此时栈满");
    30. 	}
    31. 	else {
    32. 		if (S->top == -1) {
    33. 			S->top += 1;
    34. 			S->stack[S->top] = x;
    35.  
    36. 		}
    37. 		else {
    38. 			S->stack[++S->top] = x;
    39. 		}
    40. 		
    41. 		//printf("入栈成功");
    42. 	}
    43. }
    44.  
    45. //出栈
    46. int StackPop(SqStack* S) {
    47. 	if (S->top == -1) {
    48. 		printf("此时为空栈，无法继续出栈");
    49. 		return - 1;
    50. 	}
    51. 	else {
    52. 		int x = S->stack[S->top];
    53. 		S->top--;
    54. 		return x;
    55. 	}
    56. }
    57.  
    58. //取栈顶元素
    59. int GetStackTop(SqStack* S) {
    60. 	if (S->top == -1) {
    61. 		return -1;
    62. 	}
    63. 	int x = S->stack[S->top];
    64. 	return x;
    65. }
    66.  
    67. void StackPrint(SqStack* S) {
    68. 	int num = S->top;
    69. 	while (num != -1) {
    70. 		printf("%d ", S->stack[num]);
    71. 		num--;
    72. 	}
    73. }
    74.  
    75. int main() {
    76. 	SqStack* S = (SqStack*)malloc(sizeof(SqStack));
    77. 	InitStack(S);
    78. 	int a;
    79. 	scanf("%d", &a);
    80. 	while (a != 0) {
    81. 		StackPush(S, a);
    82. 		scanf("%d", &a);
    83. 	}
    84. 	StackPrint(S);
    85. 	a = StackPop(S);
    86. 	printf("%d",a);
    87. 	StackPrint(S);
    88. 	return 0;
    89. }

    2、链栈

            通过单链表实现

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include   
    3. #include    //开辟空间
    4.  
    5. #define MAXSIZE 50
    6.  
    7. //链栈
    8. typedef struct StackNode {
    9. 	int data;
    10. 	struct StackNode* next;
    11. }StackNode,*LinkStack;
    12.  
    13. //初始化
    14. void InitStack(LinkStack S) {
    15. 	S->next = NULL;
    16. 	S->data = 0;
    17. }
    18.  
    19. //判断链栈是否为空
    20. int EmptyStack(LinkStack S) {
    21. 	if (S->data == 0)
    22. 		return 1;
    23. 	return 0;
    24. }
    25.  
    26. //进栈
    27. void StackPush(LinkStack S, int x) {
    28. 	LinkStack p = (LinkStack)malloc(sizeof(StackNode));
    29. 	p->data = x;
    30. 	p->next = S->next;
    31. 	S->next = p;
    32. 	S->data++;
    33. }
    34.  
    35. //出栈
    36. int StackPop(LinkStack S) {
    37. 	LinkStack p = S->next;
    38. 	if (p == NULL)
    39. 		return -1;
    40. 	S->next = p->next;
    41. 	int a = p->data;
    42. 	free(p);
    43. 	S->data--;
    44. 	return a;
    45. }
    46.  
    47. //打印
    48. void StackPrint(LinkStack S) {
    49. 	LinkStack p = S->next;
    50. 	while (p) {
    51. 		printf("%d ", p->data);
    52. 		p = p->next;
    53. 	}
    54. }
    55.  
    56. int main() {
    57. 	LinkStack S = (LinkStack)malloc(sizeof(StackNode));
    58. 	InitStack(S);
    59. 	StackPush(S, 1);
    60. 	StackPush(S, 2);
    61. 	StackPush(S, 3);
    62. 	StackPrint(S);
    63. 	int x = StackPop(S);
    64. 	printf("%d", x);
    65. 	StackPrint(S);
    66. 	return 0;
    67. }

    3.卡特兰数

    C_{_{n}} = C_{2n}^{n} - C_{2n}^{n-1}

    1. 出栈次序

    一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?


     C_{2n}^{n}下面这个2n是什么意思？

    假如有4个数。那每个数有两个情况一个进栈和出栈两种状态。那就一共有8种状态

    如果有n个数就有2n种状态。


    C_{2n}^{n}上面那个n是什么意思？

    栈进栈再出栈。假如将进栈标记为1。将出栈标记为-1。出栈和进栈是要平衡的和要为0所以代表n个数里面有几种进栈的状态4个数的话就会有4种进栈的状态。

    这里我们记：进栈--- +1        出栈--- -1

    有以下结论：

    1. 合法序列必定总和为0，即num(-1)=num(+1)
    2. 总和为0的序列不一定合法

    有 合法 = C_{2n}^{n} - 非法

            3.“前缀”:包含首个元素往后数

            4.合法序列的特点：对于所有前缀，每一个前缀的和都>=0，且num(-1)=num(+1)

    比如： n=3

    不合法的：+1，-1，-1，+1，-1，+1

    合法的： +1，-1，+1，+1，+1，-1，-1

    对于第一个：将第一个“和小于0”的前缀取反，得到一个新序列

    -1，+1，+1，+1，-1，+1此时就有4个+1，2个-1

    对应n个的话就是将第一个“和小于零”的前缀取反，就得到新序列，且有n+1个+1，n-1个-1

    所以A和B是一一对应的

    4、表达式求值

    【问题描述】栈的应用，给定一个以“#”作为结束符的算式，求出算式的结果

    【输入形式】以“#”结尾的表达式，运算数为正整数。每个表达式占一行。

    【输出形式】输出表达式运算的结果。

    【样例输入1】4+2.53*3-10/5#

    【样例输出1】9.59

    【样例输入2】3*(7.91-2)#

    【样例输出2】17.73

    【样例输入3】2.4*3.6/2#

    【样例输出3】4.32

    【注意】要处理表达式中带小数的数据，不能仅采用getchar去接收数据，请注意查阅资料，看看如何处理。

    另外，输出数据请保留2位小数。

    1. #include 
    2. #define TRUE 1
    3. #define FALSE 0
    4. #define Size 50
    5.  
    6. typedef struct {
    7. 	float elem[Size];
    8. 	int top;
    9. }SeqStack;
    10.  
    11.  
    12. void Init(SeqStack* S) {
    13. 	S->top = -1;
    14. }
    15.  
    16. int Empty(SeqStack* S) {
    17. 	return(S->top == -1 ? TRUE : FALSE);
    18. }
    19.  
    20. int Full(SeqStack* S) {
    21. 	return(S->top == Size - 1 ? TRUE : FALSE);
    22. }
    23.  
    24.  
    25. int Push(SeqStack* S, float x) {
    26. 	if (S->top == Size - 1) {
    27. 		return FALSE;
    28. 	}
    29. 	S->top++;
    30. 	S->elem[S->top] = x;
    31. 	return TRUE;
    32. }
    33.  
    34. int Pop(SeqStack* S, float* x) {
    35. 	if (S->top == -1) {
    36. 		return FALSE;
    37. 	}
    38. 	else {
    39. 		*x = S->elem[S->top];
    40. 		S->top--;
    41. 		return TRUE;
    42. 	}
    43.  
    44. }
    45.  
    46. int Get(SeqStack* S, float* x) {
    47. 	if (S->top == -1) {
    48. 		return FALSE;
    49. 	}
    50. 	else {
    51. 		*x = S->elem[S->top];
    52. 		return TRUE;
    53. 	}
    54. }
    55.  
    56. typedef struct {
    57. 	char elem[Size];
    58. 	int top;
    59. }StrStack;
    60.  
    61.  
    62. void StrInit(StrStack* s) {
    63. 	s->top = -1;
    64. }
    65.  
    66.  
    67. int StrEmpty(StrStack* s) {
    68. 	return(s->top == -1 ? TRUE : FALSE);
    69. }
    70.  
    71. int StrFull(SeqStack* s) {
    72. 	return(s->top == Size - 1 ? TRUE : FALSE);
    73. }
    74.  
    75.  
    76. int StrPush(StrStack* s, char x) {
    77. 	if (s->top == Size - 1) {
    78. 		return FALSE;
    79. 	}
    80. 	s->top++;
    81. 	s->elem[s->top] = x;
    82. 	return TRUE;
    83. }
    84.  
    85. int StrPop(StrStack* s, char* x) {
    86. 	if (s->top == -1) {
    87. 		return FALSE;
    88. 	}
    89. 	else {
    90. 		*x = s->elem[s->top];
    91. 		s->top--;
    92. 		return TRUE;
    93. 	}
    94.  
    95. }
    96.  
    97. int StrGet(StrStack* s, char* x) {
    98. 	if (s->top == -1) {
    99. 		return FALSE;
    100. 	}
    101. 	else {
    102. 		*x = s->elem[s->top];
    103. 		return TRUE;
    104. 	}
    105. }
    106.  
    107. int match(char ch, char str) {
    108. 	if (ch == '(' && str == ')') {
    109. 		return TRUE;
    110. 	}
    111. 	else if (ch == '[' && str == ']') {
    112. 		return TRUE;
    113. 	}
    114. 	else if (ch == '{' && str == '}') {
    115. 		return TRUE;
    116. 	}
    117. 	else return FALSE;
    118. }
    119.  
    120. int In(char ch) {
    121. 	if (ch == '+') {
    122. 		return TRUE;
    123. 	}
    124. 	else if (ch == '-') {
    125. 		return TRUE;
    126. 	}
    127. 	else if (ch == '*') {
    128. 		return TRUE;
    129. 	}
    130. 	else if (ch == '/') {
    131. 		return TRUE;
    132. 	}
    133. 	else if (ch == '(') {
    134. 		return TRUE;
    135. 	}
    136. 	else if (ch == ')') {
    137. 		return TRUE;
    138. 	}
    139. 	else if (ch == '#') {
    140. 		return TRUE;
    141. 	}
    142. 	else return FALSE;
    143. }
    144.  
    145.  
    146. char Comper(char x, char ch) {
    147. 	switch (x)
    148. 	{
    149. 	case'+':
    150. 		if (ch == '+' || ch == '-' || ch == ')' || ch == '#')
    151. 			return '>';
    152. 		else if (ch == '*' || ch == '/' || ch == '(')
    153. 			return '<';
    154. 		break;
    155. 	case'-':
    156. 		if (ch == '+' || ch == '-' || ch == ')' || ch == '#')
    157. 			return '>';
    158. 		else if (ch == '*' || ch == '/' || ch == '(')
    159. 			return '<';
    160. 		break;
    161.  
    162. 	case'*':
    163. 		if (ch == '(') {
    164. 			return '<';
    165. 		}
    166. 		else {
    167. 			return '>';
    168. 		}
    169. 		break;
    170. 	case'/':
    171. 		if (ch == '(') {
    172. 			return '<';
    173. 		}
    174. 		else {
    175. 			return '>';
    176. 		}
    177. 		break;
    178. 	case'(':
    179. 		if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(')
    180. 			return '<';
    181. 		else if (ch == ')')
    182. 			return '=';
    183. 		else if (ch == '#')
    184. 			return '0';
    185. 		break;
    186. 	case')':
    187. 		if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == ')' || ch == '#')
    188. 			return '>';
    189. 		else if (ch == '(')
    190. 			return '0';
    191. 		break;
    192. 	case'#':
    193. 		if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(')
    194. 			return '<';
    195. 		else if (ch == '#')
    196. 			return '=';
    197. 		else if (ch == ')')
    198. 			return '0';
    199. 		break;
    200. 	default:
    201. 		return '0';
    202. 		break;
    203. 	}
    204. }
    205. /*
    206. char Operator(char a, char b) {
    207. 	int i = 0, j = 0;
    208. 	char pre[7][7] = {
    209. 		{'>','>','<','<','<','>','>'},
    210. 		{'>','>','<','<','<','>','>'},
    211. 		{'>','>','>','>','<','>','>'},
    212. 		{'>','>','>','>','<','>','>'},
    213. 		{'<','<','<','<','<','=','0'},
    214. 		{'>','>','>','>','0','>','>'},
    215. 		{'<','<','<','<','<','0','='},
    216. 	};
    217. 	switch (a) {
    218. 	case'+':i = 0; break;
    219. 	case'-':i = 1; break;
    220. 	case'*':i = 2; break;
    221. 	case'/':i = 3; break;
    222. 	case'(':i = 4; break;
    223. 	case')':i = 5; break;
    224. 	case'#':i = 6; break;
    225. 	}
    226. 	switch (b) {
    227. 	case'+':j = 0; break;
    228. 	case'-':j = 1; break;
    229. 	case'*':j = 2; break;
    230. 	case'/':j = 3; break;
    231. 	case'(':j = 4; break;
    232. 	case')':j = 5; break;
    233. 	case'#':j = 6; break;
    234. 	}
    235. 	return pre[i][j];
    236. }
    237. */
    238.  
    239. float Execute(float a, char op, float b) {
    240. 	switch (op) {
    241. 	case'+':
    242. 		return (a + b);
    243. 		break;
    244. 	case'-':
    245. 		return (a - b);
    246. 		break;
    247. 	case'*':
    248. 		return (a * b);
    249. 		break;
    250. 	case'/':
    251. 		if (b != 0)
    252. 			return (a / b);
    253. 		else
    254. 			return 0;
    255. 		break;
    256. 	}
    257. }
    258.  
    259. char ch;
    260. float Evaluation() {
    261. 	char x, y;
    262. 	char op;
    263. 	float a, b, v;
    264.  
    265. 	SeqStack data;
    266. 	StrStack sign;
    267. 	Init(&data);
    268. 	StrInit(&sign);
    269. 	StrPush(&sign, '#');	//提前压一个符号进栈
    270.  
    271. 	//printf("biaodashi:\n");
    272. 	ch = getchar();
    273. 	StrGet(&sign, &y);
    274.  
    275. 	while (ch != '#' || y != '#') {
    276. 		if (!In(ch)) {
    277. 			int temp;
    278. 			int i = 1;
    279. 			float temp2, a[10] = { 0,0.1,0.01,0.001,0.0001,0.00001 };
    280. 			temp = ch - '0'; //转换为数字
    281. 			ch = getchar();
    282. 			while (!In(ch) && ch != '.') {
    283. 				temp = temp * 10 + ch - '0';
    284. 				ch = getchar();
    285. 			}
    286. 			temp2 = temp;
    287. 			if (ch == '.') {
    288. 				ch = getchar();
    289. 				for (i = 1; !In(ch); i++) {
    290. 					temp2 += (ch - '0') * a[i];
    291. 					ch = getchar();
    292. 				}
    293. 			}
    294. 			Push(&data, temp2);
    295. 		}
    296. 		else {
    297. 			switch (Comper(y, ch)) {
    298. 			case'<':
    299. 				StrPush(&sign, ch);
    300. 				ch = getchar();
    301. 				break;
    302. 			case'=':
    303. 				StrPop(&sign, &x);
    304. 				ch = getchar();
    305. 				break;
    306. 			case'>':
    307. 				StrPop(&sign, &op);
    308. 				Pop(&data, &b);
    309. 				Pop(&data, &a);
    310. 				v = Execute(a, op, b);
    311. 				Push(&data, v);
    312. 				break;
    313. 			}
    314. 		}
    315. 		StrGet(&sign, &y);
    316. 	}
    317. 	Get(&data, &v);
    318. 	return(v);
    319. }
    320.  
    321. int main() {
    322. 	float result;
    323. 	result = Evaluation();
    324. 	printf("\n%.2f", result);
    325. 	return 0;
    326. }
    327.  
    328.

    二、队列

    1、链队列

    先进先出

    1. #include 
    2. #include 
    3. typedef struct Node {
    4. 	int data;
    5. 	struct Node* next;
    6. }Node;
    7.  
    8. Node* initQueue() {
    9. 	Node* Q = (Node*)malloc(sizeof(Node));
    10. 	Q->data = 0;
    11. 	Q->next = NULL;
    12. 	return Q;
    13. }
    14.  
    15. void inQueue(Node* Q, int data) {
    16. 	Node* node = (Node*)malloc(sizeof(Node));
    17. 	Node* q = Q;
    18. 	node->data = data;
    19. 	for (int i = 0; i < Q->data; i++) {
    20. 		q = q->next;
    21. 	}
    22. 	node->next = q->next;
    23. 	q->next = node;
    24. 	Q->data++;
    25. }
    26. int isEmpty(Node* Q) {
    27. 	if (Q->data == 0 || Q->next == NULL)
    28. 		return 1;
    29. 	return 0;
    30. }
    31.  
    32. int delQueue(Node* Q) {
    33. 	if (isEmpty(Q))
    34. 		return -1;
    35. 	Node* node = Q->next;
    36. 	int data = node->data;
    37. 	Q->next = node->next;
    38. 	free(node);
    39. 	Q->data--;
    40. 	return data;
    41. }
    42.  
    43.  
    44. void printQueue(Node* Q) {
    45. 	Node* node = Q->next;
    46. 	while(node) {
    47. 		printf("%d ", node->data);
    48. 		node = node->next;
    49. 	}
    50. 	printf("NULL\n");
    51. }
    52.  
    53. int main() {
    54. 	Node* Q = initQueue();
    55. 	inQueue(Q,1);
    56. 	inQueue(Q, 2);
    57. 	inQueue(Q, 3);
    58. 	inQueue(Q, 4);
    59. 	printQueue(Q);
    60. 	int x = delQueue(Q);
    61. 	printQueue(Q);
    62. 	printf("%d", x);
    63. 	return 0;
    64. }

    2、循环队列

    1. #include 
    2. #include 
    3.  
    4. #define MAXSIZE 5
    5. //只能放4个数据，牺牲了一个空间去更好判断是否满队
    6.  
    7. typedef struct Queue {
    8. 	int front;
    9. 	int rear;
    10. 	int data[MAXSIZE];
    11. }Queue;
    12.  
    13. Queue* initQueue() {
    14. 	Queue* Q = (Queue*)malloc(sizeof(Queue));
    15. 	Q->front = Q->rear = 0;
    16. 	return Q;
    17. }
    18.  
    19. int isFull(Queue* Q) {
    20. 	if ((Q->rear + 1) % MAXSIZE == Q->front) {
    21. 		return 1;
    22. 	}
    23. 	return 0;
    24. }
    25.  
    26. int isEmpty(Queue* Q) {
    27. 	if (Q->front == Q->rear)
    28. 		return 1;
    29. 	return 0;
    30. }
    31.  
    32. int inQueue(Queue* Q,int data) {
    33. 	if (isFull(Q)) {
    34. 		return 0;
    35. 	}
    36. 	else {
    37. 		Q->data[Q->rear] = data;
    38. 		Q->rear = (Q->rear + 1) % MAXSIZE;
    39. 		return 1;
    40. 	}
    41. }
    42.  
    43. int delQueue(Queue* Q) {
    44. 	if (isEmpty(Q))
    45. 		return -1;
    46. 	int data = Q->data[Q->front];
    47. 	Q->front = (Q->front + 1) % MAXSIZE;
    48. 	return data;
    49. }
    50.  
    51. void printQueue(Queue* Q) {
    52. 	int length = (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
    53. 	int index = Q->front;
    54. 	for (int i = 0; i < length; i++) {
    55. 		printf("%d->", Q->data[index]);
    56. 		index = (index + 1) % MAXSIZE;
    57. 	}
    58. 	printf("NULL\n");
    59.  
    60. }
    61.  
    62. void main() {
    63. 	Queue* Q = initQueue();
    64. 	inQueue(Q, 1);
    65. 	inQueue(Q, 2);
    66. 	inQueue(Q, 3);
    67. 	inQueue(Q, 4);
    68. 	printQueue(Q);
    69. 	delQueue(Q);
    70. 	printQueue(Q);
    71. 	return 0;
    72. }

    3、杨辉三角

    1. #include 
    2. #define MAX 100
    3. #define FALSE 0
    4. #define TRUE 1
    5. //循环队列
    6. typedef struct {
    7.     int element[MAX];
    8.     int front; //头指针
    9.     int rear;  //尾指针
    10. } SeqQueue;
    11. //初始化循环队列
    12. void InitQueue(SeqQueue* q) { q->front = q->rear = 0; }
    13. //入队
    14. int EnterQueue(SeqQueue* q, int x) {
    15.     if ((q->rear + 1) % MAX == q->front) {
    16.         printf("---队列已满---");
    17.         return FALSE;
    18.     }
    19.     q->element[q->rear] = x;
    20.     q->rear = (q->rear + 1) % MAX;
    21.     return TRUE;
    22. }
    23. //出队
    24. int DeleteQueue(SeqQueue* q, int* x) {
    25.     if (q->front == q->rear) {
    26.         printf("---队列为空---");
    27.         return FALSE;
    28.     }
    29.     *x = q->element[q->front];
    30.     q->front = (q->front + 1) % MAX;
    31.     return TRUE;
    32. }
    33. //取对头元素
    34. int GetHead(SeqQueue* q, int* x) {
    35.     if (q->front == q->rear)
    36.         return FALSE;
    37.     *x = q->element[q->front];
    38.     return TRUE;
    39. }
    40. //判断队列是否为空
    41. int IsEmpty(SeqQueue* q) {
    42.     if (q->front == q->rear)
    43.         return TRUE;
    44.     else
    45.         return FALSE;
    46. }
    47. //打印杨辉三角
    48. void YangHuiTriangle(int N) {
    49.     SeqQueue q;
    50.     InitQueue(&q);
    51.     int n, i, x, temp;
    52.     EnterQueue(&q, 1); //第一行元素入队
    53.     for (n = 2; n <= N; n++) {
    54.         EnterQueue(&q, 1); //第n行第一个元素入队
    55.         // N为打印的行数，n为每行的元素个数
    56.         for (i = 1; i <= n - 2; i++) { //利用队中第n-1行元素产生第n行的中间n-2个元素并入队
    57.             DeleteQueue(&q, &temp);    //出队元素赋给temp
    58.             printf("%d ", temp);       //打印第n-1行的元素
    59.             GetHead(&q, &x);
    60.             temp = temp + x;      //利用第n-1行元素产生第n行元素
    61.             EnterQueue(&q, temp); //可以利用画图理解
    62.         }
    63.         DeleteQueue(&q, &x);
    64.         printf("%d ", x); //打印n-1行最后一个元素
    65.         EnterQueue(&q, 1);
    66.         printf("\n");
    67.     }
    68.     while (!IsEmpty(&q)) { //打印最后一行
    69.         DeleteQueue(&q, &x);
    70.         printf("%d ", x);
    71.     }
    72. }
    73. //主函数： 
    74. int main() {
    75.     int N;
    76.     scanf("%d", &N);
    77.     YangHuiTriangle(N);
    78.     printf("\n");
    79.     return 0;
    80. }
  • 相关阅读:
    软件测试面试复习题（一）
    AnkiPDF Guru软件评测：打开全新学习方式的大门
    这一篇让你彻底搞懂 JAVA 内部类
    信号量、互斥锁、计数信号量
    Typescript 之 快速入门
    CCS3.3烧写说明
    激活函数之ReLU, GeLU, SwiGLU
    14天学习训练营导师课程-Pygame学习笔记-Part2(第九艺术的召唤)
    codeforces:dp专练【关于子数组求和 + 选or不选来dp + 二维dp】
    5.Nginx负载均衡实例
  • 原文地址：https://blog.csdn.net/2303_79741845/article/details/139834730