第3章 栈、队列和数组代码
使用建议
- 先配合对应章节阅读：第3章 栈、队列和数组 正文
- 这一页优先提供站内可直接查看的代码版本，适合网页阅读和搜索。
- 这一页主要用于网页阅读，建议结合对应正文与逐行注释版一起使用。
文件位置
- 普通代码版：
第3章普通代码版
- 逐行注释版：
第3章逐行注释版代码
- 兼容编码版：
第3章兼容编码版逐行注释代码
普通代码版
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
#define MAX_SIZE 100
/* 顺序栈：top 指向当前栈顶元素。空栈时 top 为 -1。 */
typedef struct {
ElemType data[MAX_SIZE];
int top;
} SeqStack;
/* 初始化顺序栈。 */
void InitSeqStack(SeqStack *stack) {
if (stack == NULL) {
return;
}
stack->top = -1;
}
/* 判空。 */
bool SeqStackEmpty(const SeqStack *stack) {
return stack == NULL || stack->top == -1;
}
/* 判满。 */
bool SeqStackFull(const SeqStack *stack) {
return stack != NULL && stack->top == MAX_SIZE - 1;
}
/* 入栈：先移动 top，再写入数据。 */
bool PushSeqStack(SeqStack *stack, ElemType value) {
if (stack == NULL || SeqStackFull(stack)) {
return false;
}
stack->data[++stack->top] = value;
return true;
}
/* 出栈：先取栈顶元素，再让 top 回退。 */
bool PopSeqStack(SeqStack *stack, ElemType *value_out) {
if (SeqStackEmpty(stack) || value_out == NULL) {
return false;
}
*value_out = stack->data[stack->top--];
return true;
}
/* 读栈顶元素，但不出栈。 */
bool GetTopSeqStack(const SeqStack *stack, ElemType *value_out) {
if (SeqStackEmpty(stack) || value_out == NULL) {
return false;
}
*value_out = stack->data[stack->top];
return true;
}
/* 打印顺序栈，从栈底到栈顶方便观察。 */
void PrintSeqStack(const SeqStack *stack) {
int i;
if (stack == NULL) {
return;
}
printf("[");
for (i = 0; i <= stack->top; i++) {
if (i > 0) {
printf(", ");
}
printf("%d", stack->data[i]);
}
printf("] top=%d\n", stack->top);
}
/* 共享栈：两个栈共用一个数组，从两端向中间增长。 */
typedef struct {
ElemType data[MAX_SIZE];
int top0;
int top1;
} SharedStack;
/* 初始化共享栈。 */
void InitSharedStack(SharedStack *stack) {
if (stack == NULL) {
return;
}
stack->top0 = -1;
stack->top1 = MAX_SIZE;
}
/* 共享栈判满：两个栈顶指针相邻。 */
bool SharedStackFull(const SharedStack *stack) {
return stack != NULL && stack->top1 - stack->top0 == 1;
}
/* 向 0 号栈入栈。 */
bool PushSharedStack0(SharedStack *stack, ElemType value) {
if (stack == NULL || SharedStackFull(stack)) {
return false;
}
stack->data[++stack->top0] = value;
return true;
}
/* 向 1 号栈入栈。 */
bool PushSharedStack1(SharedStack *stack, ElemType value) {
if (stack == NULL || SharedStackFull(stack)) {
return false;
}
stack->data[--stack->top1] = value;
return true;
}
/* 从 0 号栈出栈。 */
bool PopSharedStack0(SharedStack *stack, ElemType *value_out) {
if (stack == NULL || stack->top0 == -1 || value_out == NULL) {
return false;
}
*value_out = stack->data[stack->top0--];
return true;
}
/* 从 1 号栈出栈。 */
bool PopSharedStack1(SharedStack *stack, ElemType *value_out) {
if (stack == NULL || stack->top1 == MAX_SIZE || value_out == NULL) {
return false;
}
*value_out = stack->data[stack->top1++];
return true;
}
/* 链栈结点定义。 */
typedef struct LinkNode {
ElemType data;
struct LinkNode *next;
} LinkNode;
/* 链栈：top 指向栈顶结点，不带头结点。 */
typedef struct {
LinkNode *top;
} LinkStack;
/* 初始化链栈。 */
void InitLinkStack(LinkStack *stack) {
if (stack == NULL) {
return;
}
stack->top = NULL;
}
/* 判空。 */
bool LinkStackEmpty(const LinkStack *stack) {
return stack == NULL || stack->top == NULL;
}
/* 链栈入栈：新结点插到表头。 */
bool PushLinkStack(LinkStack *stack, ElemType value) {
LinkNode *node;
if (stack == NULL) {
return false;
}
node = (LinkNode *)malloc(sizeof(LinkNode));
if (node == NULL) {
return false;
}
node->data = value;
node->next = stack->top;
stack->top = node;
return true;
}
/* 链栈出栈：删除表头结点。 */
bool PopLinkStack(LinkStack *stack, ElemType *value_out) {
LinkNode *node;
if (LinkStackEmpty(stack) || value_out == NULL) {
return false;
}
node = stack->top;
*value_out = node->data;
stack->top = node->next;
free(node);
return true;
}
/* 读链栈栈顶。 */
bool GetTopLinkStack(const LinkStack *stack, ElemType *value_out) {
if (LinkStackEmpty(stack) || value_out == NULL) {
return false;
}
*value_out = stack->top->data;
return true;
}
/* 销毁链栈。 */
void DestroyLinkStack(LinkStack *stack) {
ElemType discarded;
if (stack == NULL) {
return;
}
while (PopLinkStack(stack, &discarded)) {
/* 不断弹出直到为空即可。 */
}
}
/* 判断括号序列是否匹配，是栈最经典的应用之一。 */
bool IsBracketSequenceBalanced(const char *text) {
SeqStack stack;
char ch;
ElemType top_char;
int i = 0;
if (text == NULL) {
return false;
}
InitSeqStack(&stack);
while ((ch = text[i++]) != '\0') {
if (ch == '(' || ch == '[' || ch == '{') {
if (!PushSeqStack(&stack, (ElemType)ch)) {
return false;
}
} else if (ch == ')' || ch == ']' || ch == '}') {
if (!PopSeqStack(&stack, &top_char)) {
return false;
}
if ((ch == ')' && top_char != '(') ||
(ch == ']' && top_char != '[') ||
(ch == '}' && top_char != '{')) {
return false;
}
}
}
return SeqStackEmpty(&stack);
}
/* 计算运算符优先级：乘除高于加减。 */
int OperatorPrecedence(char op) {
if (op == '*' || op == '/') {
return 2;
}
if (op == '+' || op == '-') {
return 1;
}
return 0;
}
/* 对两个整数执行一次二元运算。 */
bool ApplyBinaryOperator(ElemType left, ElemType right, char op, ElemType *result_out) {
if (result_out == NULL) {
return false;
}
switch (op) {
case '+':
*result_out = left + right;
return true;
case '-':
*result_out = left - right;
return true;
case '*':
*result_out = left * right;
return true;
case '/':
if (right == 0) {
return false;
}
*result_out = left / right;
return true;
default:
return false;
}
}
/* 计算后缀表达式的值：这里假设操作数是 0~9 的单个数字，空格可忽略。 */
bool EvaluatePostfixExpression(const char *expr, ElemType *result_out) {
SeqStack stack;
char ch;
int i = 0;
if (expr == NULL || result_out == NULL) {
return false;
}
InitSeqStack(&stack);
while ((ch = expr[i++]) != '\0') {
if (ch == ' ') {
continue;
}
if (ch >= '0' && ch <= '9') {
if (!PushSeqStack(&stack, ch - '0')) {
return false;
}
} else {
ElemType right;
ElemType left;
ElemType value;
if (!PopSeqStack(&stack, &right) || !PopSeqStack(&stack, &left)) {
return false;
}
if (!ApplyBinaryOperator(left, right, ch, &value)) {
return false;
}
if (!PushSeqStack(&stack, value)) {
return false;
}
}
}
if (!PopSeqStack(&stack, result_out)) {
return false;
}
return SeqStackEmpty(&stack);
}
/* 计算一维数组中第 index 个元素相对首元素的偏移量。 */
int RowMajorIndex1D(int low, int index) {
return index - low;
}
/* 计算二维数组按行优先展开后的线性下标。 */
int RowMajorIndex2D(int row, int col, int row_low, int col_low, int col_count) {
return (row - row_low) * col_count + (col - col_low);
}
/* 计算二维数组按列优先展开后的线性下标。 */
int ColMajorIndex2D(int row, int col, int row_low, int col_low, int row_count) {
return (col - col_low) * row_count + (row - row_low);
}
/* 对称矩阵按行优先压缩存下三角（含主对角线）时的下标。 */
int SymmetricMatrixIndex(int row, int col) {
if (row < col) {
int temp = row;
row = col;
col = temp;
}
return row * (row + 1) / 2 + col;
}
/* 下三角矩阵压缩存储：上三角常量区用最后一个位置表示。 */
int LowerTriangularMatrixIndex(int row, int col, int order) {
if (row >= col) {
return row * (row + 1) / 2 + col;
}
return order * (order + 1) / 2;
}
/* 上三角矩阵压缩存储：下三角常量区用最后一个位置表示。 */
int UpperTriangularMatrixIndex(int row, int col, int order) {
if (row <= col) {
return order * row - row * (row - 1) / 2 + (col - row);
}
return order * (order + 1) / 2;
}
/* 三对角矩阵按行优先压缩时，只允许访问主对角线及其相邻两条对角线。 */
int TridiagonalMatrixIndex(int row, int col) {
if (abs(row - col) > 1) {
return -1;
}
return 2 * row + col;
}
/* 稀疏矩阵三元组：记录行、列和值。 */
typedef struct {
int row;
int col;
ElemType value;
} Triple;
/* 把稠密矩阵里的非零元素提取成三元组表。 */
int DenseMatrixToTriples(const ElemType *matrix, int rows, int cols, Triple *triples, int capacity) {
int row;
int col;
int count = 0;
if (matrix == NULL || triples == NULL || rows <= 0 || cols <= 0 || capacity <= 0) {
return -1;
}
for (row = 0; row < rows; row++) {
for (col = 0; col < cols; col++) {
ElemType value = matrix[row * cols + col];
if (value != 0) {
if (count >= capacity) {
return -1;
}
triples[count].row = row;
triples[count].col = col;
triples[count].value = value;
count++;
}
}
}
return count;
}
/* 打印三元组表，帮助观察稀疏矩阵压缩结果。 */
void PrintTriples(const Triple *triples, int count) {
int i;
if (triples == NULL || count < 0) {
return;
}
printf("[");
for (i = 0; i < count; i++) {
if (i > 0) {
printf(", ");
}
printf("(%d,%d,%d)", triples[i].row, triples[i].col, triples[i].value);
}
printf("]\n");
}
/* 循环队列：front 指向队头元素，rear 指向下一个可插入位置。 */
typedef struct {
ElemType data[MAX_SIZE];
int front;
int rear;
} CircularQueue;
/* 初始化循环队列，让 front 和 rear 都从 0 出发。 */
void InitCircularQueue(CircularQueue *queue) {
if (queue == NULL) {
return;
}
queue->front = 0;
queue->rear = 0;
}
/* 队空时 front 和 rear 重合，说明当前没有任何元素。 */
bool CircularQueueEmpty(const CircularQueue *queue) {
return queue == NULL || queue->front == queue->rear;
}
/* 预留一个空位置来区分“队空”和“队满”。 */
bool CircularQueueFull(const CircularQueue *queue) {
return queue != NULL && (queue->rear + 1) % MAX_SIZE == queue->front;
}
/* 入队：把新元素放到 rear 位置，再让 rear 循环后移。 */
bool EnqueueCircularQueue(CircularQueue *queue, ElemType value) {
if (queue == NULL || CircularQueueFull(queue)) {
return false;
}
queue->data[queue->rear] = value;
queue->rear = (queue->rear + 1) % MAX_SIZE;
return true;
}
/* 出队：先取走队头元素，再让 front 循环后移。 */
bool DequeueCircularQueue(CircularQueue *queue, ElemType *value_out) {
if (CircularQueueEmpty(queue) || value_out == NULL) {
return false;
}
*value_out = queue->data[queue->front];
queue->front = (queue->front + 1) % MAX_SIZE;
return true;
}
/* 读队头元素，但不真正出队。 */
bool GetHeadCircularQueue(const CircularQueue *queue, ElemType *value_out) {
if (CircularQueueEmpty(queue) || value_out == NULL) {
return false;
}
*value_out = queue->data[queue->front];
return true;
}
/* 打印循环队列，从队头一路打印到队尾。 */
void PrintCircularQueue(const CircularQueue *queue) {
int i;
if (queue == NULL) {
return;
}
printf("[");
i = queue->front;
while (i != queue->rear) {
if (i != queue->front) {
printf(", ");
}
printf("%d", queue->data[i]);
i = (i + 1) % MAX_SIZE;
}
printf("] front=%d rear=%d\n", queue->front, queue->rear);
}
/* 链队列结点：每个结点保存一个数据元素和后继指针。 */
typedef struct QueueNode {
ElemType data;
struct QueueNode *next;
} QueueNode;
/* 链队列：front 指向头结点，rear 指向最后一个实际结点。 */
typedef struct {
QueueNode *front;
QueueNode *rear;
} LinkQueue;
/* 初始化链队列：先建立一个空的头结点，方便统一处理。 */
bool InitLinkQueue(LinkQueue *queue) {
QueueNode *head;
if (queue == NULL) {
return false;
}
head = (QueueNode *)malloc(sizeof(QueueNode));
if (head == NULL) {
return false;
}
head->next = NULL;
queue->front = head;
queue->rear = head;
return true;
}
/* 只剩头结点时，说明链队列为空。 */
bool LinkQueueEmpty(const LinkQueue *queue) {
return queue == NULL || queue->front == queue->rear;
}
/* 链队列入队：新结点永远挂到队尾，再更新 rear。 */
bool EnqueueLinkQueue(LinkQueue *queue, ElemType value) {
QueueNode *node;
if (queue == NULL || queue->rear == NULL) {
return false;
}
node = (QueueNode *)malloc(sizeof(QueueNode));
if (node == NULL) {
return false;
}
node->data = value;
node->next = NULL;
queue->rear->next = node;
queue->rear = node;
return true;
}
/* 链队列出队：删除头结点后的第一个实际结点。 */
bool DequeueLinkQueue(LinkQueue *queue, ElemType *value_out) {
QueueNode *node;
if (LinkQueueEmpty(queue) || value_out == NULL) {
return false;
}
node = queue->front->next;
*value_out = node->data;
queue->front->next = node->next;
if (queue->rear == node) {
queue->rear = queue->front;
}
free(node);
return true;
}
/* 读链队列队头，不真正删除。 */
bool GetHeadLinkQueue(const LinkQueue *queue, ElemType *value_out) {
if (LinkQueueEmpty(queue) || value_out == NULL) {
return false;
}
*value_out = queue->front->next->data;
return true;
}
/* 打印链队列，帮助观察先进先出的效果。 */
void PrintLinkQueue(const LinkQueue *queue) {
QueueNode *curr;
bool first = true;
if (queue == NULL || queue->front == NULL) {
return;
}
printf("[");
curr = queue->front->next;
while (curr != NULL) {
if (!first) {
printf(", ");
}
printf("%d", curr->data);
first = false;
curr = curr->next;
}
printf("]\n");
}
/* 销毁链队列：包括头结点在内全部释放。 */
void DestroyLinkQueue(LinkQueue *queue) {
QueueNode *curr;
if (queue == NULL || queue->front == NULL) {
return;
}
curr = queue->front;
while (curr != NULL) {
QueueNode *next = curr->next;
free(curr);
curr = next;
}
queue->front = NULL;
queue->rear = NULL;
}
/* 双端队列：同一端既能进也能出，两端都可以操作。 */
typedef struct {
ElemType data[MAX_SIZE];
int front;
int rear;
} Deque;
/* 初始化双端队列，本质上仍然是一个循环数组。 */
void InitDeque(Deque *deque) {
if (deque == NULL) {
return;
}
deque->front = 0;
deque->rear = 0;
}
/* 双端队列判空。 */
bool DequeEmpty(const Deque *deque) {
return deque == NULL || deque->front == deque->rear;
}
/* 双端队列判满，同样预留一个空位置。 */
bool DequeFull(const Deque *deque) {
return deque != NULL && (deque->rear + 1) % MAX_SIZE == deque->front;
}
/* 从队头一侧插入。 */
bool PushFrontDeque(Deque *deque, ElemType value) {
if (deque == NULL || DequeFull(deque)) {
return false;
}
deque->front = (deque->front - 1 + MAX_SIZE) % MAX_SIZE;
deque->data[deque->front] = value;
return true;
}
/* 从队尾一侧插入。 */
bool PushBackDeque(Deque *deque, ElemType value) {
if (deque == NULL || DequeFull(deque)) {
return false;
}
deque->data[deque->rear] = value;
deque->rear = (deque->rear + 1) % MAX_SIZE;
return true;
}
/* 从队头一侧删除。 */
bool PopFrontDeque(Deque *deque, ElemType *value_out) {
if (DequeEmpty(deque) || value_out == NULL) {
return false;
}
*value_out = deque->data[deque->front];
deque->front = (deque->front + 1) % MAX_SIZE;
return true;
}
/* 从队尾一侧删除。 */
bool PopBackDeque(Deque *deque, ElemType *value_out) {
if (DequeEmpty(deque) || value_out == NULL) {
return false;
}
deque->rear = (deque->rear - 1 + MAX_SIZE) % MAX_SIZE;
*value_out = deque->data[deque->rear];
return true;
}
/* 打印双端队列当前内容。 */
void PrintDeque(const Deque *deque) {
int i;
if (deque == NULL) {
return;
}
printf("[");
i = deque->front;
while (i != deque->rear) {
if (i != deque->front) {
printf(", ");
}
printf("%d", deque->data[i]);
i = (i + 1) % MAX_SIZE;
}
printf("] front=%d rear=%d\n", deque->front, deque->rear);
}
int main(void) {
SeqStack seq_stack;
SharedStack shared_stack;
LinkStack link_stack;
CircularQueue circular_queue;
LinkQueue link_queue;
Deque deque;
ElemType value;
ElemType postfix_value;
ElemType dense_matrix[3][3] = {
{0, 0, 5},
{0, 2, 0},
{7, 0, 0}
};
Triple triples[9];
int triple_count;
InitSeqStack(&seq_stack);
PushSeqStack(&seq_stack, 10);
PushSeqStack(&seq_stack, 20);
PushSeqStack(&seq_stack, 30);
PrintSeqStack(&seq_stack);
if (GetTopSeqStack(&seq_stack, &value)) {
printf("seq top: %d\n", value);
}
if (PopSeqStack(&seq_stack, &value)) {
printf("seq pop: %d\n", value);
}
PrintSeqStack(&seq_stack);
InitSharedStack(&shared_stack);
PushSharedStack0(&shared_stack, 1);
PushSharedStack0(&shared_stack, 2);
PushSharedStack1(&shared_stack, 100);
PushSharedStack1(&shared_stack, 200);
if (PopSharedStack0(&shared_stack, &value)) {
printf("shared stack 0 pop: %d\n", value);
}
if (PopSharedStack1(&shared_stack, &value)) {
printf("shared stack 1 pop: %d\n", value);
}
InitLinkStack(&link_stack);
PushLinkStack(&link_stack, 7);
PushLinkStack(&link_stack, 8);
PushLinkStack(&link_stack, 9);
if (GetTopLinkStack(&link_stack, &value)) {
printf("link top: %d\n", value);
}
if (PopLinkStack(&link_stack, &value)) {
printf("link pop: %d\n", value);
}
if (GetTopLinkStack(&link_stack, &value)) {
printf("link new top: %d\n", value);
}
DestroyLinkStack(&link_stack);
printf("balanced '([{}])' => %s\n",
IsBracketSequenceBalanced("([{}])") ? "true" : "false");
printf("balanced '([)]' => %s\n",
IsBracketSequenceBalanced("([)]") ? "true" : "false");
if (EvaluatePostfixExpression("23*54*+9-", &postfix_value)) {
printf("postfix value: %d\n", postfix_value);
}
InitCircularQueue(&circular_queue);
EnqueueCircularQueue(&circular_queue, 11);
EnqueueCircularQueue(&circular_queue, 22);
EnqueueCircularQueue(&circular_queue, 33);
PrintCircularQueue(&circular_queue);
if (GetHeadCircularQueue(&circular_queue, &value)) {
printf("circular queue head: %d\n", value);
}
if (DequeueCircularQueue(&circular_queue, &value)) {
printf("circular queue dequeue: %d\n", value);
}
PrintCircularQueue(&circular_queue);
if (InitLinkQueue(&link_queue)) {
EnqueueLinkQueue(&link_queue, 101);
EnqueueLinkQueue(&link_queue, 102);
EnqueueLinkQueue(&link_queue, 103);
PrintLinkQueue(&link_queue);
if (GetHeadLinkQueue(&link_queue, &value)) {
printf("link queue head: %d\n", value);
}
if (DequeueLinkQueue(&link_queue, &value)) {
printf("link queue dequeue: %d\n", value);
}
PrintLinkQueue(&link_queue);
DestroyLinkQueue(&link_queue);
}
InitDeque(&deque);
PushBackDeque(&deque, 5);
PushBackDeque(&deque, 6);
PushFrontDeque(&deque, 4);
PushFrontDeque(&deque, 3);
PrintDeque(&deque);
if (PopFrontDeque(&deque, &value)) {
printf("deque pop front: %d\n", value);
}
if (PopBackDeque(&deque, &value)) {
printf("deque pop back: %d\n", value);
}
PrintDeque(&deque);
printf("1D index offset A[5] from A[0]: %d\n", RowMajorIndex1D(0, 5));
printf("row-major index A[2][1] in A[0..2][0..3]: %d\n",
RowMajorIndex2D(2, 1, 0, 0, 4));
printf("col-major index A[2][1] in A[0..2][0..3]: %d\n",
ColMajorIndex2D(2, 1, 0, 0, 3));
printf("symmetric index a[3][1]: %d\n", SymmetricMatrixIndex(3, 1));
printf("lower triangular index a[3][1]: %d\n", LowerTriangularMatrixIndex(3, 1, 4));
printf("upper triangular index a[1][3]: %d\n", UpperTriangularMatrixIndex(1, 3, 4));
printf("tridiagonal index a[3][2]: %d\n", TridiagonalMatrixIndex(3, 2));
triple_count = DenseMatrixToTriples(&dense_matrix[0][0], 3, 3, triples, 9);
if (triple_count >= 0) {
PrintTriples(triples, triple_count);
}
return 0;
}
逐行注释版
/* ????????????????????????????????? */
/* ??????????????????????????????? */
/* ?0001????????????????? `bool`?`true` ? `false`? */
#include <stdbool.h>
/* ?0002??????????????????? `printf` ???????? */
#include <stdio.h>
/* ?0003???????????????? `malloc`?`free`?`abs` ???? */
#include <stdlib.h>
/* ?0004??????????????????????? */
/* ?0005?????????????????????????????? */
typedef int ElemType;
/* ?0006??????????????????????? */
/* ?0007?????????????????????????? */
#define MAX_SIZE 100
/* ?0008??????????????????????? */
/* ?0009????????????????顺序栈：top 指向当前栈顶元素。空栈时 top 为 -1。?? */
/* 顺序栈：top 指向当前栈顶元素。空栈时 top 为 -1。 */
/* ?0010????????????????????????? */
typedef struct {
/* ?0011??????????????????????????? */
ElemType data[MAX_SIZE];
/* ?0012??????????????????????????? */
int top;
/* ?0013?????????????????????? `SeqStack`? */
} SeqStack;
/* ?0014??????????????????????? */
/* ?0015????????????????初始化顺序栈。?? */
/* 初始化顺序栈。 */
/* ?0016???????? `InitSeqStack`????????????? */
void InitSeqStack(SeqStack *stack) {
/* ?0017??????????????????????????? */
if (stack == NULL) {
/* ?0018???????????????????? */
return;
/* ?0019?????????????????? */
}
/* ?0020???????????????????????? */
stack->top = -1;
/* ?0021?????? `InitSeqStack` ???? */
}
/* ?0022??????????????????????? */
/* ?0023????????????????判空。?? */
/* 判空。 */
/* ?0024???????? `SeqStackEmpty`????????????? */
bool SeqStackEmpty(const SeqStack *stack) {
/* ?0025???????????????????????? */
return stack == NULL || stack->top == -1;
/* ?0026?????? `SeqStackEmpty` ???? */
}
/* ?0027??????????????????????? */
/* ?0028????????????????判满。?? */
/* 判满。 */
/* ?0029???????? `SeqStackFull`????????????? */
bool SeqStackFull(const SeqStack *stack) {
/* ?0030???????????????????????? */
return stack != NULL && stack->top == MAX_SIZE - 1;
/* ?0031?????? `SeqStackFull` ???? */
}
/* ?0032??????????????????????? */
/* ?0033????????????????入栈：先移动 top，再写入数据。?? */
/* 入栈：先移动 top，再写入数据。 */
/* ?0034???????? `PushSeqStack`????????????? */
bool PushSeqStack(SeqStack *stack, ElemType value) {
/* ?0035??????????????????????????? */
if (stack == NULL || SeqStackFull(stack)) {
/* ?0036???????????????????????? */
return false;
/* ?0037?????????????????? */
}
/* ?0038???????????????????????? */
stack->data[++stack->top] = value;
/* ?0039???????????????????????? */
return true;
/* ?0040?????? `PushSeqStack` ???? */
}
/* ?0041??????????????????????? */
/* ?0042????????????????出栈：先取栈顶元素，再让 top 回退。?? */
/* 出栈：先取栈顶元素，再让 top 回退。 */
/* ?0043???????? `PopSeqStack`????????????? */
bool PopSeqStack(SeqStack *stack, ElemType *value_out) {
/* ?0044??????????????????????????? */
if (SeqStackEmpty(stack) || value_out == NULL) {
/* ?0045???????????????????????? */
return false;
/* ?0046?????????????????? */
}
/* ?0047???????????????????????? */
*value_out = stack->data[stack->top--];
/* ?0048???????????????????????? */
return true;
/* ?0049?????? `PopSeqStack` ???? */
}
/* ?0050??????????????????????? */
/* ?0051????????????????读栈顶元素，但不出栈。?? */
/* 读栈顶元素，但不出栈。 */
/* ?0052???????? `GetTopSeqStack`????????????? */
bool GetTopSeqStack(const SeqStack *stack, ElemType *value_out) {
/* ?0053??????????????????????????? */
if (SeqStackEmpty(stack) || value_out == NULL) {
/* ?0054???????????????????????? */
return false;
/* ?0055?????????????????? */
}
/* ?0056???????????????????????? */
*value_out = stack->data[stack->top];
/* ?0057???????????????????????? */
return true;
/* ?0058?????? `GetTopSeqStack` ???? */
}
/* ?0059??????????????????????? */
/* ?0060????????????????打印顺序栈，从栈底到栈顶方便观察。?? */
/* 打印顺序栈，从栈底到栈顶方便观察。 */
/* ?0061???????? `PrintSeqStack`????????????? */
void PrintSeqStack(const SeqStack *stack) {
/* ?0062??????????????????????????? */
int i;
/* ?0063??????????????????????? */
/* ?0064??????????????????????????? */
if (stack == NULL) {
/* ?0065???????????????????? */
return;
/* ?0066?????????????????? */
}
/* ?0067??????????????????????? */
printf("[");
/* ?0068???? `for` ?????????????????? */
for (i = 0; i <= stack->top; i++) {
/* ?0069??????????????????????????? */
if (i > 0) {
/* ?0070??????????????????????? */
printf(", ");
/* ?0071?????????????????? */
}
/* ?0072??????????????????????? */
printf("%d", stack->data[i]);
/* ?0073?????????????????? */
}
/* ?0074??????????????????????? */
printf("] top=%d\n", stack->top);
/* ?0075?????? `PrintSeqStack` ???? */
}
/* ?0076??????????????????????? */
/* ?0077????????????????共享栈：两个栈共用一个数组，从两端向中间增长。?? */
/* 共享栈：两个栈共用一个数组，从两端向中间增长。 */
/* ?0078????????????????????????? */
typedef struct {
/* ?0079??????????????????????????? */
ElemType data[MAX_SIZE];
/* ?0080??????????????????????????? */
int top0;
/* ?0081??????????????????????????? */
int top1;
/* ?0082?????????????????????? `SharedStack`? */
} SharedStack;
/* ?0083??????????????????????? */
/* ?0084????????????????初始化共享栈。?? */
/* 初始化共享栈。 */
/* ?0085???????? `InitSharedStack`????????????? */
void InitSharedStack(SharedStack *stack) {
/* ?0086??????????????????????????? */
if (stack == NULL) {
/* ?0087???????????????????? */
return;
/* ?0088?????????????????? */
}
/* ?0089???????????????????????? */
stack->top0 = -1;
/* ?0090???????????????????????? */
stack->top1 = MAX_SIZE;
/* ?0091?????? `InitSharedStack` ???? */
}
/* ?0092??????????????????????? */
/* ?0093????????????????共享栈判满：两个栈顶指针相邻。?? */
/* 共享栈判满：两个栈顶指针相邻。 */
/* ?0094???????? `SharedStackFull`????????????? */
bool SharedStackFull(const SharedStack *stack) {
/* ?0095???????????????????????? */
return stack != NULL && stack->top1 - stack->top0 == 1;
/* ?0096?????? `SharedStackFull` ???? */
}
/* ?0097??????????????????????? */
/* ?0098????????????????向 0 号栈入栈。?? */
/* 向 0 号栈入栈。 */
/* ?0099???????? `PushSharedStack0`????????????? */
bool PushSharedStack0(SharedStack *stack, ElemType value) {
/* ?0100??????????????????????????? */
if (stack == NULL || SharedStackFull(stack)) {
/* ?0101???????????????????????? */
return false;
/* ?0102?????????????????? */
}
/* ?0103???????????????????????? */
stack->data[++stack->top0] = value;
/* ?0104???????????????????????? */
return true;
/* ?0105?????? `PushSharedStack0` ???? */
}
/* ?0106??????????????????????? */
/* ?0107????????????????向 1 号栈入栈。?? */
/* 向 1 号栈入栈。 */
/* ?0108???????? `PushSharedStack1`????????????? */
bool PushSharedStack1(SharedStack *stack, ElemType value) {
/* ?0109??????????????????????????? */
if (stack == NULL || SharedStackFull(stack)) {
/* ?0110???????????????????????? */
return false;
/* ?0111?????????????????? */
}
/* ?0112???????????????????????? */
stack->data[--stack->top1] = value;
/* ?0113???????????????????????? */
return true;
/* ?0114?????? `PushSharedStack1` ???? */
}
/* ?0115??????????????????????? */
/* ?0116????????????????从 0 号栈出栈。?? */
/* 从 0 号栈出栈。 */
/* ?0117???????? `PopSharedStack0`????????????? */
bool PopSharedStack0(SharedStack *stack, ElemType *value_out) {
/* ?0118??????????????????????????? */
if (stack == NULL || stack->top0 == -1 || value_out == NULL) {
/* ?0119???????????????????????? */
return false;
/* ?0120?????????????????? */
}
/* ?0121???????????????????????? */
*value_out = stack->data[stack->top0--];
/* ?0122???????????????????????? */
return true;
/* ?0123?????? `PopSharedStack0` ???? */
}
/* ?0124??????????????????????? */
/* ?0125????????????????从 1 号栈出栈。?? */
/* 从 1 号栈出栈。 */
/* ?0126???????? `PopSharedStack1`????????????? */
bool PopSharedStack1(SharedStack *stack, ElemType *value_out) {
/* ?0127??????????????????????????? */
if (stack == NULL || stack->top1 == MAX_SIZE || value_out == NULL) {
/* ?0128???????????????????????? */
return false;
/* ?0129?????????????????? */
}
/* ?0130???????????????????????? */
*value_out = stack->data[stack->top1++];
/* ?0131???????????????????????? */
return true;
/* ?0132?????? `PopSharedStack1` ???? */
}
/* ?0133??????????????????????? */
/* ?0134????????????????链栈结点定义。?? */
/* 链栈结点定义。 */
/* ?0135??????????????????????????? */
typedef struct LinkNode {
/* ?0136??????????????????????????? */
ElemType data;
/* ?0137?????????????????? */
struct LinkNode *next;
/* ?0138?????????????????????? `LinkNode`? */
} LinkNode;
/* ?0139??????????????????????? */
/* ?0140????????????????链栈：top 指向栈顶结点，不带头结点。?? */
/* 链栈：top 指向栈顶结点，不带头结点。 */
/* ?0141????????????????????????? */
typedef struct {
/* ?0142?????????????????? */
LinkNode *top;
/* ?0143?????????????????????? `LinkStack`? */
} LinkStack;
/* ?0144??????????????????????? */
/* ?0145????????????????初始化链栈。?? */
/* 初始化链栈。 */
/* ?0146???????? `InitLinkStack`????????????? */
void InitLinkStack(LinkStack *stack) {
/* ?0147??????????????????????????? */
if (stack == NULL) {
/* ?0148???????????????????? */
return;
/* ?0149?????????????????? */
}
/* ?0150???????????????????????? */
stack->top = NULL;
/* ?0151?????? `InitLinkStack` ???? */
}
/* ?0152??????????????????????? */
/* ?0153????????????????判空。?? */
/* 判空。 */
/* ?0154???????? `LinkStackEmpty`????????????? */
bool LinkStackEmpty(const LinkStack *stack) {
/* ?0155???????????????????????? */
return stack == NULL || stack->top == NULL;
/* ?0156?????? `LinkStackEmpty` ???? */
}
/* ?0157??????????????????????? */
/* ?0158????????????????链栈入栈：新结点插到表头。?? */
/* 链栈入栈：新结点插到表头。 */
/* ?0159???????? `PushLinkStack`????????????? */
bool PushLinkStack(LinkStack *stack, ElemType value) {
/* ?0160?????????????????? */
LinkNode *node;
/* ?0161??????????????????????? */
/* ?0162??????????????????????????? */
if (stack == NULL) {
/* ?0163???????????????????????? */
return false;
/* ?0164?????????????????? */
}
/* ?0165??????????????????????? */
/* ?0166????????????????????????? */
node = (LinkNode *)malloc(sizeof(LinkNode));
/* ?0167??????????????????????????? */
if (node == NULL) {
/* ?0168???????????????????????? */
return false;
/* ?0169?????????????????? */
}
/* ?0170???????????????????????? */
node->data = value;
/* ?0171???????????????????????? */
node->next = stack->top;
/* ?0172???????????????????????? */
stack->top = node;
/* ?0173???????????????????????? */
return true;
/* ?0174?????? `PushLinkStack` ???? */
}
/* ?0175??????????????????????? */
/* ?0176????????????????链栈出栈：删除表头结点。?? */
/* 链栈出栈：删除表头结点。 */
/* ?0177???????? `PopLinkStack`????????????? */
bool PopLinkStack(LinkStack *stack, ElemType *value_out) {
/* ?0178?????????????????? */
LinkNode *node;
/* ?0179??????????????????????? */
/* ?0180??????????????????????????? */
if (LinkStackEmpty(stack) || value_out == NULL) {
/* ?0181???????????????????????? */
return false;
/* ?0182?????????????????? */
}
/* ?0183??????????????????????? */
/* ?0184???????????????????????? */
node = stack->top;
/* ?0185???????????????????????? */
*value_out = node->data;
/* ?0186???????????????????????? */
stack->top = node->next;
/* ?0187???????????????????????? */
free(node);
/* ?0188???????????????????????? */
return true;
/* ?0189?????? `PopLinkStack` ???? */
}
/* ?0190??????????????????????? */
/* ?0191????????????????读链栈栈顶。?? */
/* 读链栈栈顶。 */
/* ?0192???????? `GetTopLinkStack`????????????? */
bool GetTopLinkStack(const LinkStack *stack, ElemType *value_out) {
/* ?0193??????????????????????????? */
if (LinkStackEmpty(stack) || value_out == NULL) {
/* ?0194???????????????????????? */
return false;
/* ?0195?????????????????? */
}
/* ?0196???????????????????????? */
*value_out = stack->top->data;
/* ?0197???????????????????????? */
return true;
/* ?0198?????? `GetTopLinkStack` ???? */
}
/* ?0199??????????????????????? */
/* ?0200????????????????销毁链栈。?? */
/* 销毁链栈。 */
/* ?0201???????? `DestroyLinkStack`????????????? */
void DestroyLinkStack(LinkStack *stack) {
/* ?0202??????????????????????????? */
ElemType discarded;
/* ?0203??????????????????????? */
/* ?0204??????????????????????????? */
if (stack == NULL) {
/* ?0205???????????????????? */
return;
/* ?0206?????????????????? */
}
/* ?0207???? `while` ????????????????????? */
while (PopLinkStack(stack, &discarded)) {
/* ?0208????????????????不断弹出直到为空即可。?? */
/* 不断弹出直到为空即可。 */
/* ?0209?????????????????? */
}
/* ?0210?????? `DestroyLinkStack` ???? */
}
/* ?0211??????????????????????? */
/* ?0212????????????????判断括号序列是否匹配，是栈最经典的应用之一。?? */
/* 判断括号序列是否匹配，是栈最经典的应用之一。 */
/* ?0213???????? `IsBracketSequenceBalanced`????????????? */
bool IsBracketSequenceBalanced(const char *text) {
/* ?0214??????????????????????????? */
SeqStack stack;
/* ?0215?????????????????? */
char ch;
/* ?0216??????????????????????????? */
ElemType top_char;
/* ?0217?????????????????????????? */
int i = 0;
/* ?0218??????????????????????? */
/* ?0219??????????????????????????? */
if (text == NULL) {
/* ?0220???????????????????????? */
return false;
/* ?0221?????????????????? */
}
/* ?0222??????????????????????? */
/* ?0223???????????????????????????? */
InitSeqStack(&stack);
/* ?0224???? `while` ????????????????????? */
while ((ch = text[i++]) != '\0') {
/* ?0225??????????????????????????? */
if (ch == '(' || ch == '[' || ch == '{') {
/* ?0226??????????????????????????? */
if (!PushSeqStack(&stack, (ElemType)ch)) {
/* ?0227???????????????????????? */
return false;
/* ?0228?????????????????? */
}
/* ?0229???????????????? `else` ?????????? */
} else if (ch == ')' || ch == ']' || ch == '}') {
/* ?0230??????????????????????????? */
if (!PopSeqStack(&stack, &top_char)) {
/* ?0231???????????????????????? */
return false;
/* ?0232?????????????????? */
}
/* ?0233??????????????????????????? */
if ((ch == ')' && top_char != '(') ||
/* ?0234??????????????????????????? */
(ch == ']' && top_char != '[') ||
/* ?0235??????????????????????????? */
(ch == '}' && top_char != '{')) {
/* ?0236???????????????????????? */
return false;
/* ?0237?????????????????? */
}
/* ?0238?????????????????? */
}
/* ?0239?????????????????? */
}
/* ?0240??????????????????????? */
/* ?0241???????????????????????? */
return SeqStackEmpty(&stack);
/* ?0242?????? `IsBracketSequenceBalanced` ???? */
}
/* ?0243??????????????????????? */
/* ?0244????????????????计算运算符优先级：乘除高于加减。?? */
/* 计算运算符优先级：乘除高于加减。 */
/* ?0245???????? `OperatorPrecedence`????????????? */
int OperatorPrecedence(char op) {
/* ?0246??????????????????????????? */
if (op == '*' || op == '/') {
/* ?0247???????????????????????? */
return 2;
/* ?0248?????????????????? */
}
/* ?0249??????????????????????????? */
if (op == '+' || op == '-') {
/* ?0250???????????????????????? */
return 1;
/* ?0251?????????????????? */
}
/* ?0252???????????????????????? */
return 0;
/* ?0253?????? `OperatorPrecedence` ???? */
}
/* ?0254??????????????????????? */
/* ?0255????????????????对两个整数执行一次二元运算。?? */
/* 对两个整数执行一次二元运算。 */
/* ?0256???????? `ApplyBinaryOperator`????????????? */
bool ApplyBinaryOperator(ElemType left, ElemType right, char op, ElemType *result_out) {
/* ?0257??????????????????????????? */
if (result_out == NULL) {
/* ?0258???????????????????????? */
return false;
/* ?0259?????????????????? */
}
/* ?0260??????????????????????? */
/* ?0261??????????????????????????? */
switch (op) {
/* ?0262??????????????????????????? */
case '+':
/* ?0263?????????????????? */
*result_out = left + right;
/* ?0264???????????????????????? */
return true;
/* ?0265??????????????????????????? */
case '-':
/* ?0266?????????????????? */
*result_out = left - right;
/* ?0267???????????????????????? */
return true;
/* ?0268??????????????????????????? */
case '*':
/* ?0269?????????????????? */
*result_out = left * right;
/* ?0270???????????????????????? */
return true;
/* ?0271??????????????????????????? */
case '/':
/* ?0272??????????????????????????? */
if (right == 0) {
/* ?0273???????????????????????? */
return false;
/* ?0274?????????????????? */
}
/* ?0275?????????????????? */
*result_out = left / right;
/* ?0276???????????????????????? */
return true;
/* ?0277??????????????????????????? */
default:
/* ?0278???????????????????????? */
return false;
/* ?0279?????????????????? */
}
/* ?0280?????? `ApplyBinaryOperator` ???? */
}
/* ?0281??????????????????????? */
/* ?0282????????????????计算后缀表达式的值：这里假设操作数是 0~9 的单个数字，空格可忽略。?? */
/* 计算后缀表达式的值：这里假设操作数是 0~9 的单个数字，空格可忽略。 */
/* ?0283???????? `EvaluatePostfixExpression`????????????? */
bool EvaluatePostfixExpression(const char *expr, ElemType *result_out) {
/* ?0284??????????????????????????? */
SeqStack stack;
/* ?0285?????????????????? */
char ch;
/* ?0286?????????????????????????? */
int i = 0;
/* ?0287??????????????????????? */
/* ?0288??????????????????????????? */
if (expr == NULL || result_out == NULL) {
/* ?0289???????????????????????? */
return false;
/* ?0290?????????????????? */
}
/* ?0291??????????????????????? */
/* ?0292???????????????????????????? */
InitSeqStack(&stack);
/* ?0293???? `while` ????????????????????? */
while ((ch = expr[i++]) != '\0') {
/* ?0294??????????????????????????? */
if (ch == ' ') {
/* ?0295????????????????????? */
continue;
/* ?0296?????????????????? */
}
/* ?0297??????????????????????????? */
if (ch >= '0' && ch <= '9') {
/* ?0298??????????????????????????? */
if (!PushSeqStack(&stack, ch - '0')) {
/* ?0299???????????????????????? */
return false;
/* ?0300?????????????????? */
}
/* ?0301???????????????? `else` ?????????? */
} else {
/* ?0302??????????????????????????? */
ElemType right;
/* ?0303??????????????????????????? */
ElemType left;
/* ?0304??????????????????????????? */
ElemType value;
/* ?0305??????????????????????? */
/* ?0306??????????????????????????? */
if (!PopSeqStack(&stack, &right) || !PopSeqStack(&stack, &left)) {
/* ?0307???????????????????????? */
return false;
/* ?0308?????????????????? */
}
/* ?0309??????????????????????????? */
if (!ApplyBinaryOperator(left, right, ch, &value)) {
/* ?0310???????????????????????? */
return false;
/* ?0311?????????????????? */
}
/* ?0312??????????????????????????? */
if (!PushSeqStack(&stack, value)) {
/* ?0313???????????????????????? */
return false;
/* ?0314?????????????????? */
}
/* ?0315?????????????????? */
}
/* ?0316?????????????????? */
}
/* ?0317??????????????????????? */
/* ?0318??????????????????????????? */
if (!PopSeqStack(&stack, result_out)) {
/* ?0319???????????????????????? */
return false;
/* ?0320?????????????????? */
}
/* ?0321???????????????????????? */
return SeqStackEmpty(&stack);
/* ?0322?????? `EvaluatePostfixExpression` ???? */
}
/* ?0323??????????????????????? */
/* ?0324????????????????计算一维数组中第 index 个元素相对首元素的偏移量。?? */
/* 计算一维数组中第 index 个元素相对首元素的偏移量。 */
/* ?0325???????? `RowMajorIndex1D`????????????? */
int RowMajorIndex1D(int low, int index) {
/* ?0326???????????????????????? */
return index - low;
/* ?0327?????? `RowMajorIndex1D` ???? */
}
/* ?0328??????????????????????? */
/* ?0329????????????????计算二维数组按行优先展开后的线性下标。?? */
/* 计算二维数组按行优先展开后的线性下标。 */
/* ?0330???????? `RowMajorIndex2D`????????????? */
int RowMajorIndex2D(int row, int col, int row_low, int col_low, int col_count) {
/* ?0331???????????????????????? */
return (row - row_low) * col_count + (col - col_low);
/* ?0332?????? `RowMajorIndex2D` ???? */
}
/* ?0333??????????????????????? */
/* ?0334????????????????计算二维数组按列优先展开后的线性下标。?? */
/* 计算二维数组按列优先展开后的线性下标。 */
/* ?0335???????? `ColMajorIndex2D`????????????? */
int ColMajorIndex2D(int row, int col, int row_low, int col_low, int row_count) {
/* ?0336???????????????????????? */
return (col - col_low) * row_count + (row - row_low);
/* ?0337?????? `ColMajorIndex2D` ???? */
}
/* ?0338??????????????????????? */
/* ?0339????????????????对称矩阵按行优先压缩存下三角（含主对角线）时的下标。?? */
/* 对称矩阵按行优先压缩存下三角（含主对角线）时的下标。 */
/* ?0340???????? `SymmetricMatrixIndex`????????????? */
int SymmetricMatrixIndex(int row, int col) {
/* ?0341??????????????????????????? */
if (row < col) {
/* ?0342?????????????????????????? */
int temp = row;
/* ?0343?????????????????? */
row = col;
/* ?0344?????????????????? */
col = temp;
/* ?0345?????????????????? */
}
/* ?0346???????????????????????? */
return row * (row + 1) / 2 + col;
/* ?0347?????? `SymmetricMatrixIndex` ???? */
}
/* ?0348??????????????????????? */
/* ?0349????????????????下三角矩阵压缩存储：上三角常量区用最后一个位置表示。?? */
/* 下三角矩阵压缩存储：上三角常量区用最后一个位置表示。 */
/* ?0350???????? `LowerTriangularMatrixIndex`????????????? */
int LowerTriangularMatrixIndex(int row, int col, int order) {
/* ?0351??????????????????????????? */
if (row >= col) {
/* ?0352???????????????????????? */
return row * (row + 1) / 2 + col;
/* ?0353?????????????????? */
}
/* ?0354???????????????????????? */
return order * (order + 1) / 2;
/* ?0355?????? `LowerTriangularMatrixIndex` ???? */
}
/* ?0356??????????????????????? */
/* ?0357????????????????上三角矩阵压缩存储：下三角常量区用最后一个位置表示。?? */
/* 上三角矩阵压缩存储：下三角常量区用最后一个位置表示。 */
/* ?0358???????? `UpperTriangularMatrixIndex`????????????? */
int UpperTriangularMatrixIndex(int row, int col, int order) {
/* ?0359??????????????????????????? */
if (row <= col) {
/* ?0360???????????????????????? */
return order * row - row * (row - 1) / 2 + (col - row);
/* ?0361?????????????????? */
}
/* ?0362???????????????????????? */
return order * (order + 1) / 2;
/* ?0363?????? `UpperTriangularMatrixIndex` ???? */
}
/* ?0364??????????????????????? */
/* ?0365????????????????三对角矩阵按行优先压缩时，只允许访问主对角线及其相邻两条对角线。?? */
/* 三对角矩阵按行优先压缩时，只允许访问主对角线及其相邻两条对角线。 */
/* ?0366???????? `TridiagonalMatrixIndex`????????????? */
int TridiagonalMatrixIndex(int row, int col) {
/* ?0367??????????????????????????? */
if (abs(row - col) > 1) {
/* ?0368???????????????????????? */
return -1;
/* ?0369?????????????????? */
}
/* ?0370???????????????????????? */
return 2 * row + col;
/* ?0371?????? `TridiagonalMatrixIndex` ???? */
}
/* ?0372??????????????????????? */
/* ?0373????????????????稀疏矩阵三元组：记录行、列和值。?? */
/* 稀疏矩阵三元组：记录行、列和值。 */
/* ?0374????????????????????????? */
typedef struct {
/* ?0375??????????????????????????? */
int row;
/* ?0376??????????????????????????? */
int col;
/* ?0377??????????????????????????? */
ElemType value;
/* ?0378?????????????????????? `Triple`? */
} Triple;
/* ?0379??????????????????????? */
/* ?0380????????????????把稠密矩阵里的非零元素提取成三元组表。?? */
/* 把稠密矩阵里的非零元素提取成三元组表。 */
/* ?0381???????? `DenseMatrixToTriples`????????????? */
int DenseMatrixToTriples(const ElemType *matrix, int rows, int cols, Triple *triples, int capacity) {
/* ?0382??????????????????????????? */
int row;
/* ?0383??????????????????????????? */
int col;
/* ?0384?????????????????????????? */
int count = 0;
/* ?0385??????????????????????? */
/* ?0386??????????????????????????? */
if (matrix == NULL || triples == NULL || rows <= 0 || cols <= 0 || capacity <= 0) {
/* ?0387???????????????????????? */
return -1;
/* ?0388?????????????????? */
}
/* ?0389??????????????????????? */
/* ?0390???? `for` ?????????????????? */
for (row = 0; row < rows; row++) {
/* ?0391???? `for` ?????????????????? */
for (col = 0; col < cols; col++) {
/* ?0392?????????????????????????? */
ElemType value = matrix[row * cols + col];
/* ?0393??????????????????????????? */
if (value != 0) {
/* ?0394??????????????????????????? */
if (count >= capacity) {
/* ?0395???????????????????????? */
return -1;
/* ?0396?????????????????? */
}
/* ?0397???????????????????????? */
triples[count].row = row;
/* ?0398???????????????????????? */
triples[count].col = col;
/* ?0399???????????????????????? */
triples[count].value = value;
/* ?0400?????????????????? */
count++;
/* ?0401?????????????????? */
}
/* ?0402?????????????????? */
}
/* ?0403?????????????????? */
}
/* ?0404???????????????????????? */
return count;
/* ?0405?????? `DenseMatrixToTriples` ???? */
}
/* ?0406??????????????????????? */
/* ?0407????????????????打印三元组表，帮助观察稀疏矩阵压缩结果。?? */
/* 打印三元组表，帮助观察稀疏矩阵压缩结果。 */
/* ?0408???????? `PrintTriples`????????????? */
void PrintTriples(const Triple *triples, int count) {
/* ?0409??????????????????????????? */
int i;
/* ?0410??????????????????????? */
/* ?0411??????????????????????????? */
if (triples == NULL || count < 0) {
/* ?0412???????????????????? */
return;
/* ?0413?????????????????? */
}
/* ?0414??????????????????????? */
/* ?0415??????????????????????? */
printf("[");
/* ?0416???? `for` ?????????????????? */
for (i = 0; i < count; i++) {
/* ?0417??????????????????????????? */
if (i > 0) {
/* ?0418??????????????????????? */
printf(", ");
/* ?0419?????????????????? */
}
/* ?0420??????????????????????? */
printf("(%d,%d,%d)", triples[i].row, triples[i].col, triples[i].value);
/* ?0421?????????????????? */
}
/* ?0422??????????????????????? */
printf("]\n");
/* ?0423?????? `PrintTriples` ???? */
}
/* ?0424??????????????????????? */
/* ?0425????????????????循环队列：front 指向队头元素，rear 指向下一个可插入位置。?? */
/* 循环队列：front 指向队头元素，rear 指向下一个可插入位置。 */
/* ?0426????????????????????????? */
typedef struct {
/* ?0427??????????????????????????? */
ElemType data[MAX_SIZE];
/* ?0428??????????????????????????? */
int front;
/* ?0429??????????????????????????? */
int rear;
/* ?0430?????????????????????? `CircularQueue`? */
} CircularQueue;
/* ?0431??????????????????????? */
/* ?0432????????????????初始化循环队列，让 front 和 rear 都从 0 出发。?? */
/* 初始化循环队列，让 front 和 rear 都从 0 出发。 */
/* ?0433???????? `InitCircularQueue`????????????? */
void InitCircularQueue(CircularQueue *queue) {
/* ?0434??????????????????????????? */
if (queue == NULL) {
/* ?0435???????????????????? */
return;
/* ?0436?????????????????? */
}
/* ?0437???????????????????????? */
queue->front = 0;
/* ?0438???????????????????????? */
queue->rear = 0;
/* ?0439?????? `InitCircularQueue` ???? */
}
/* ?0440??????????????????????? */
/* ?0441????????????????队空时 front 和 rear 重合，说明当前没有任何元素。?? */
/* 队空时 front 和 rear 重合，说明当前没有任何元素。 */
/* ?0442???????? `CircularQueueEmpty`????????????? */
bool CircularQueueEmpty(const CircularQueue *queue) {
/* ?0443???????????????????????? */
return queue == NULL || queue->front == queue->rear;
/* ?0444?????? `CircularQueueEmpty` ???? */
}
/* ?0445??????????????????????? */
/* ?0446????????????????预留一个空位置来区分“队空”和“队满”。?? */
/* 预留一个空位置来区分“队空”和“队满”。 */
/* ?0447???????? `CircularQueueFull`????????????? */
bool CircularQueueFull(const CircularQueue *queue) {
/* ?0448???????????????????????? */
return queue != NULL && (queue->rear + 1) % MAX_SIZE == queue->front;
/* ?0449?????? `CircularQueueFull` ???? */
}
/* ?0450??????????????????????? */
/* ?0451????????????????入队：把新元素放到 rear 位置，再让 rear 循环后移。?? */
/* 入队：把新元素放到 rear 位置，再让 rear 循环后移。 */
/* ?0452???????? `EnqueueCircularQueue`????????????? */
bool EnqueueCircularQueue(CircularQueue *queue, ElemType value) {
/* ?0453??????????????????????????? */
if (queue == NULL || CircularQueueFull(queue)) {
/* ?0454???????????????????????? */
return false;
/* ?0455?????????????????? */
}
/* ?0456???????????????????????? */
queue->data[queue->rear] = value;
/* ?0457???????????????????????? */
queue->rear = (queue->rear + 1) % MAX_SIZE;
/* ?0458???????????????????????? */
return true;
/* ?0459?????? `EnqueueCircularQueue` ???? */
}
/* ?0460??????????????????????? */
/* ?0461????????????????出队：先取走队头元素，再让 front 循环后移。?? */
/* 出队：先取走队头元素，再让 front 循环后移。 */
/* ?0462???????? `DequeueCircularQueue`????????????? */
bool DequeueCircularQueue(CircularQueue *queue, ElemType *value_out) {
/* ?0463??????????????????????????? */
if (CircularQueueEmpty(queue) || value_out == NULL) {
/* ?0464???????????????????????? */
return false;
/* ?0465?????????????????? */
}
/* ?0466???????????????????????? */
*value_out = queue->data[queue->front];
/* ?0467???????????????????????? */
queue->front = (queue->front + 1) % MAX_SIZE;
/* ?0468???????????????????????? */
return true;
/* ?0469?????? `DequeueCircularQueue` ???? */
}
/* ?0470??????????????????????? */
/* ?0471????????????????读队头元素，但不真正出队。?? */
/* 读队头元素，但不真正出队。 */
/* ?0472???????? `GetHeadCircularQueue`????????????? */
bool GetHeadCircularQueue(const CircularQueue *queue, ElemType *value_out) {
/* ?0473??????????????????????????? */
if (CircularQueueEmpty(queue) || value_out == NULL) {
/* ?0474???????????????????????? */
return false;
/* ?0475?????????????????? */
}
/* ?0476???????????????????????? */
*value_out = queue->data[queue->front];
/* ?0477???????????????????????? */
return true;
/* ?0478?????? `GetHeadCircularQueue` ???? */
}
/* ?0479??????????????????????? */
/* ?0480????????????????打印循环队列，从队头一路打印到队尾。?? */
/* 打印循环队列，从队头一路打印到队尾。 */
/* ?0481???????? `PrintCircularQueue`????????????? */
void PrintCircularQueue(const CircularQueue *queue) {
/* ?0482??????????????????????????? */
int i;
/* ?0483??????????????????????? */
/* ?0484??????????????????????????? */
if (queue == NULL) {
/* ?0485???????????????????? */
return;
/* ?0486?????????????????? */
}
/* ?0487??????????????????????? */
/* ?0488??????????????????????? */
printf("[");
/* ?0489???????????????????????? */
i = queue->front;
/* ?0490???? `while` ????????????????????? */
while (i != queue->rear) {
/* ?0491??????????????????????????? */
if (i != queue->front) {
/* ?0492??????????????????????? */
printf(", ");
/* ?0493?????????????????? */
}
/* ?0494??????????????????????? */
printf("%d", queue->data[i]);
/* ?0495?????????????????? */
i = (i + 1) % MAX_SIZE;
/* ?0496?????????????????? */
}
/* ?0497??????????????????????? */
printf("] front=%d rear=%d\n", queue->front, queue->rear);
/* ?0498?????? `PrintCircularQueue` ???? */
}
/* ?0499??????????????????????? */
/* ?0500????????????????链队列结点：每个结点保存一个数据元素和后继指针。?? */
/* 链队列结点：每个结点保存一个数据元素和后继指针。 */
/* ?0501??????????????????????????? */
typedef struct QueueNode {
/* ?0502??????????????????????????? */
ElemType data;
/* ?0503?????????????????? */
struct QueueNode *next;
/* ?0504?????????????????????? `QueueNode`? */
} QueueNode;
/* ?0505??????????????????????? */
/* ?0506????????????????链队列：front 指向头结点，rear 指向最后一个实际结点。?? */
/* 链队列：front 指向头结点，rear 指向最后一个实际结点。 */
/* ?0507????????????????????????? */
typedef struct {
/* ?0508?????????????????? */
QueueNode *front;
/* ?0509?????????????????? */
QueueNode *rear;
/* ?0510?????????????????????? `LinkQueue`? */
} LinkQueue;
/* ?0511??????????????????????? */
/* ?0512????????????????初始化链队列：先建立一个空的头结点，方便统一处理。?? */
/* 初始化链队列：先建立一个空的头结点，方便统一处理。 */
/* ?0513???????? `InitLinkQueue`????????????? */
bool InitLinkQueue(LinkQueue *queue) {
/* ?0514?????????????????? */
QueueNode *head;
/* ?0515??????????????????????? */
/* ?0516??????????????????????????? */
if (queue == NULL) {
/* ?0517???????????????????????? */
return false;
/* ?0518?????????????????? */
}
/* ?0519??????????????????????? */
/* ?0520????????????????????????? */
head = (QueueNode *)malloc(sizeof(QueueNode));
/* ?0521??????????????????????????? */
if (head == NULL) {
/* ?0522???????????????????????? */
return false;
/* ?0523?????????????????? */
}
/* ?0524???????????????????????? */
head->next = NULL;
/* ?0525???????????????????????? */
queue->front = head;
/* ?0526???????????????????????? */
queue->rear = head;
/* ?0527???????????????????????? */
return true;
/* ?0528?????? `InitLinkQueue` ???? */
}
/* ?0529??????????????????????? */
/* ?0530????????????????只剩头结点时，说明链队列为空。?? */
/* 只剩头结点时，说明链队列为空。 */
/* ?0531???????? `LinkQueueEmpty`????????????? */
bool LinkQueueEmpty(const LinkQueue *queue) {
/* ?0532???????????????????????? */
return queue == NULL || queue->front == queue->rear;
/* ?0533?????? `LinkQueueEmpty` ???? */
}
/* ?0534??????????????????????? */
/* ?0535????????????????链队列入队：新结点永远挂到队尾，再更新 rear。?? */
/* 链队列入队：新结点永远挂到队尾，再更新 rear。 */
/* ?0536???????? `EnqueueLinkQueue`????????????? */
bool EnqueueLinkQueue(LinkQueue *queue, ElemType value) {
/* ?0537?????????????????? */
QueueNode *node;
/* ?0538??????????????????????? */
/* ?0539??????????????????????????? */
if (queue == NULL || queue->rear == NULL) {
/* ?0540???????????????????????? */
return false;
/* ?0541?????????????????? */
}
/* ?0542??????????????????????? */
/* ?0543????????????????????????? */
node = (QueueNode *)malloc(sizeof(QueueNode));
/* ?0544??????????????????????????? */
if (node == NULL) {
/* ?0545???????????????????????? */
return false;
/* ?0546?????????????????? */
}
/* ?0547???????????????????????? */
node->data = value;
/* ?0548???????????????????????? */
node->next = NULL;
/* ?0549???????????????????????? */
queue->rear->next = node;
/* ?0550???????????????????????? */
queue->rear = node;
/* ?0551???????????????????????? */
return true;
/* ?0552?????? `EnqueueLinkQueue` ???? */
}
/* ?0553??????????????????????? */
/* ?0554????????????????链队列出队：删除头结点后的第一个实际结点。?? */
/* 链队列出队：删除头结点后的第一个实际结点。 */
/* ?0555???????? `DequeueLinkQueue`????????????? */
bool DequeueLinkQueue(LinkQueue *queue, ElemType *value_out) {
/* ?0556?????????????????? */
QueueNode *node;
/* ?0557??????????????????????? */
/* ?0558??????????????????????????? */
if (LinkQueueEmpty(queue) || value_out == NULL) {
/* ?0559???????????????????????? */
return false;
/* ?0560?????????????????? */
}
/* ?0561??????????????????????? */
/* ?0562???????????????????????? */
node = queue->front->next;
/* ?0563???????????????????????? */
*value_out = node->data;
/* ?0564???????????????????????? */
queue->front->next = node->next;
/* ?0565??????????????????????????? */
if (queue->rear == node) {
/* ?0566???????????????????????? */
queue->rear = queue->front;
/* ?0567?????????????????? */
}
/* ?0568???????????????????????? */
free(node);
/* ?0569???????????????????????? */
return true;
/* ?0570?????? `DequeueLinkQueue` ???? */
}
/* ?0571??????????????????????? */
/* ?0572????????????????读链队列队头，不真正删除。?? */
/* 读链队列队头，不真正删除。 */
/* ?0573???????? `GetHeadLinkQueue`????????????? */
bool GetHeadLinkQueue(const LinkQueue *queue, ElemType *value_out) {
/* ?0574??????????????????????????? */
if (LinkQueueEmpty(queue) || value_out == NULL) {
/* ?0575???????????????????????? */
return false;
/* ?0576?????????????????? */
}
/* ?0577???????????????????????? */
*value_out = queue->front->next->data;
/* ?0578???????????????????????? */
return true;
/* ?0579?????? `GetHeadLinkQueue` ???? */
}
/* ?0580??????????????????????? */
/* ?0581????????????????打印链队列，帮助观察先进先出的效果。?? */
/* 打印链队列，帮助观察先进先出的效果。 */
/* ?0582???????? `PrintLinkQueue`????????????? */
void PrintLinkQueue(const LinkQueue *queue) {
/* ?0583?????????????????? */
QueueNode *curr;
/* ?0584?????????????????????????? */
bool first = true;
/* ?0585??????????????????????? */
/* ?0586??????????????????????????? */
if (queue == NULL || queue->front == NULL) {
/* ?0587???????????????????? */
return;
/* ?0588?????????????????? */
}
/* ?0589??????????????????????? */
/* ?0590??????????????????????? */
printf("[");
/* ?0591???????????????????????? */
curr = queue->front->next;
/* ?0592???? `while` ????????????????????? */
while (curr != NULL) {
/* ?0593??????????????????????????? */
if (!first) {
/* ?0594??????????????????????? */
printf(", ");
/* ?0595?????????????????? */
}
/* ?0596??????????????????????? */
printf("%d", curr->data);
/* ?0597?????????????????? */
first = false;
/* ?0598???????????????????????? */
curr = curr->next;
/* ?0599?????????????????? */
}
/* ?0600??????????????????????? */
printf("]\n");
/* ?0601?????? `PrintLinkQueue` ???? */
}
/* ?0602??????????????????????? */
/* ?0603????????????????销毁链队列：包括头结点在内全部释放。?? */
/* 销毁链队列：包括头结点在内全部释放。 */
/* ?0604???????? `DestroyLinkQueue`????????????? */
void DestroyLinkQueue(LinkQueue *queue) {
/* ?0605?????????????????? */
QueueNode *curr;
/* ?0606??????????????????????? */
/* ?0607??????????????????????????? */
if (queue == NULL || queue->front == NULL) {
/* ?0608???????????????????? */
return;
/* ?0609?????????????????? */
}
/* ?0610??????????????????????? */
/* ?0611???????????????????????? */
curr = queue->front;
/* ?0612???? `while` ????????????????????? */
while (curr != NULL) {
/* ?0613???????????????????????? */
QueueNode *next = curr->next;
/* ?0614???????????????????????? */
free(curr);
/* ?0615?????????????????? */
curr = next;
/* ?0616?????????????????? */
}
/* ?0617???????????????????????? */
queue->front = NULL;
/* ?0618???????????????????????? */
queue->rear = NULL;
/* ?0619?????? `DestroyLinkQueue` ???? */
}
/* ?0620??????????????????????? */
/* ?0621????????????????双端队列：同一端既能进也能出，两端都可以操作。?? */
/* 双端队列：同一端既能进也能出，两端都可以操作。 */
/* ?0622????????????????????????? */
typedef struct {
/* ?0623??????????????????????????? */
ElemType data[MAX_SIZE];
/* ?0624??????????????????????????? */
int front;
/* ?0625??????????????????????????? */
int rear;
/* ?0626?????????????????????? `Deque`? */
} Deque;
/* ?0627??????????????????????? */
/* ?0628????????????????初始化双端队列，本质上仍然是一个循环数组。?? */
/* 初始化双端队列，本质上仍然是一个循环数组。 */
/* ?0629???????? `InitDeque`????????????? */
void InitDeque(Deque *deque) {
/* ?0630??????????????????????????? */
if (deque == NULL) {
/* ?0631???????????????????? */
return;
/* ?0632?????????????????? */
}
/* ?0633???????????????????????? */
deque->front = 0;
/* ?0634???????????????????????? */
deque->rear = 0;
/* ?0635?????? `InitDeque` ???? */
}
/* ?0636??????????????????????? */
/* ?0637????????????????双端队列判空。?? */
/* 双端队列判空。 */
/* ?0638???????? `DequeEmpty`????????????? */
bool DequeEmpty(const Deque *deque) {
/* ?0639???????????????????????? */
return deque == NULL || deque->front == deque->rear;
/* ?0640?????? `DequeEmpty` ???? */
}
/* ?0641??????????????????????? */
/* ?0642????????????????双端队列判满，同样预留一个空位置。?? */
/* 双端队列判满，同样预留一个空位置。 */
/* ?0643???????? `DequeFull`????????????? */
bool DequeFull(const Deque *deque) {
/* ?0644???????????????????????? */
return deque != NULL && (deque->rear + 1) % MAX_SIZE == deque->front;
/* ?0645?????? `DequeFull` ???? */
}
/* ?0646??????????????????????? */
/* ?0647????????????????从队头一侧插入。?? */
/* 从队头一侧插入。 */
/* ?0648???????? `PushFrontDeque`????????????? */
bool PushFrontDeque(Deque *deque, ElemType value) {
/* ?0649??????????????????????????? */
if (deque == NULL || DequeFull(deque)) {
/* ?0650???????????????????????? */
return false;
/* ?0651?????????????????? */
}
/* ?0652???????????????????????? */
deque->front = (deque->front - 1 + MAX_SIZE) % MAX_SIZE;
/* ?0653???????????????????????? */
deque->data[deque->front] = value;
/* ?0654???????????????????????? */
return true;
/* ?0655?????? `PushFrontDeque` ???? */
}
/* ?0656??????????????????????? */
/* ?0657????????????????从队尾一侧插入。?? */
/* 从队尾一侧插入。 */
/* ?0658???????? `PushBackDeque`????????????? */
bool PushBackDeque(Deque *deque, ElemType value) {
/* ?0659??????????????????????????? */
if (deque == NULL || DequeFull(deque)) {
/* ?0660???????????????????????? */
return false;
/* ?0661?????????????????? */
}
/* ?0662???????????????????????? */
deque->data[deque->rear] = value;
/* ?0663???????????????????????? */
deque->rear = (deque->rear + 1) % MAX_SIZE;
/* ?0664???????????????????????? */
return true;
/* ?0665?????? `PushBackDeque` ???? */
}
/* ?0666??????????????????????? */
/* ?0667????????????????从队头一侧删除。?? */
/* 从队头一侧删除。 */
/* ?0668???????? `PopFrontDeque`????????????? */
bool PopFrontDeque(Deque *deque, ElemType *value_out) {
/* ?0669??????????????????????????? */
if (DequeEmpty(deque) || value_out == NULL) {
/* ?0670???????????????????????? */
return false;
/* ?0671?????????????????? */
}
/* ?0672???????????????????????? */
*value_out = deque->data[deque->front];
/* ?0673???????????????????????? */
deque->front = (deque->front + 1) % MAX_SIZE;
/* ?0674???????????????????????? */
return true;
/* ?0675?????? `PopFrontDeque` ???? */
}
/* ?0676??????????????????????? */
/* ?0677????????????????从队尾一侧删除。?? */
/* 从队尾一侧删除。 */
/* ?0678???????? `PopBackDeque`????????????? */
bool PopBackDeque(Deque *deque, ElemType *value_out) {
/* ?0679??????????????????????????? */
if (DequeEmpty(deque) || value_out == NULL) {
/* ?0680???????????????????????? */
return false;
/* ?0681?????????????????? */
}
/* ?0682???????????????????????? */
deque->rear = (deque->rear - 1 + MAX_SIZE) % MAX_SIZE;
/* ?0683???????????????????????? */
*value_out = deque->data[deque->rear];
/* ?0684???????????????????????? */
return true;
/* ?0685?????? `PopBackDeque` ???? */
}
/* ?0686??????????????????????? */
/* ?0687????????????????打印双端队列当前内容。?? */
/* 打印双端队列当前内容。 */
/* ?0688???????? `PrintDeque`????????????? */
void PrintDeque(const Deque *deque) {
/* ?0689??????????????????????????? */
int i;
/* ?0690??????????????????????? */
/* ?0691??????????????????????????? */
if (deque == NULL) {
/* ?0692???????????????????? */
return;
/* ?0693?????????????????? */
}
/* ?0694??????????????????????? */
/* ?0695??????????????????????? */
printf("[");
/* ?0696???????????????????????? */
i = deque->front;
/* ?0697???? `while` ????????????????????? */
while (i != deque->rear) {
/* ?0698??????????????????????????? */
if (i != deque->front) {
/* ?0699??????????????????????? */
printf(", ");
/* ?0700?????????????????? */
}
/* ?0701??????????????????????? */
printf("%d", deque->data[i]);
/* ?0702?????????????????? */
i = (i + 1) % MAX_SIZE;
/* ?0703?????????????????? */
}
/* ?0704??????????????????????? */
printf("] front=%d rear=%d\n", deque->front, deque->rear);
/* ?0705?????? `PrintDeque` ???? */
}
/* ?0706??????????????????????? */
/* ?0707???????? `main`????????????? */
int main(void) {
/* ?0708??????????????????????????? */
SeqStack seq_stack;
/* ?0709??????????????????????????? */
SharedStack shared_stack;
/* ?0710??????????????????????????? */
LinkStack link_stack;
/* ?0711??????????????????????????? */
CircularQueue circular_queue;
/* ?0712??????????????????????????? */
LinkQueue link_queue;
/* ?0713??????????????????????????? */
Deque deque;
/* ?0714??????????????????????????? */
ElemType value;
/* ?0715??????????????????????????? */
ElemType postfix_value;
/* ?0716??????????????????????????? */
ElemType dense_matrix[3][3] = {
/* ?0717??????????????????????????? */
{0, 0, 5},
/* ?0718??????????????????????????? */
{0, 2, 0},
/* ?0719??????????????????????????? */
{7, 0, 0}
/* ?0720?????????????????? */
};
/* ?0721??????????????????????????? */
Triple triples[9];
/* ?0722??????????????????????????? */
int triple_count;
/* ?0723??????????????????????? */
/* ?0724???????????????????????????? */
InitSeqStack(&seq_stack);
/* ?0725??????????????????? */
PushSeqStack(&seq_stack, 10);
/* ?0726??????????????????? */
PushSeqStack(&seq_stack, 20);
/* ?0727??????????????????? */
PushSeqStack(&seq_stack, 30);
/* ?0728??????????????????????? */
PrintSeqStack(&seq_stack);
/* ?0729??????????????????????????? */
if (GetTopSeqStack(&seq_stack, &value)) {
/* ?0730??????????????????????? */
printf("seq top: %d\n", value);
/* ?0731?????????????????? */
}
/* ?0732??????????????????????????? */
if (PopSeqStack(&seq_stack, &value)) {
/* ?0733??????????????????????? */
printf("seq pop: %d\n", value);
/* ?0734?????????????????? */
}
/* ?0735??????????????????????? */
PrintSeqStack(&seq_stack);
/* ?0736??????????????????????? */
/* ?0737???????????????????????????? */
InitSharedStack(&shared_stack);
/* ?0738??????????????????? */
PushSharedStack0(&shared_stack, 1);
/* ?0739??????????????????? */
PushSharedStack0(&shared_stack, 2);
/* ?0740??????????????????? */
PushSharedStack1(&shared_stack, 100);
/* ?0741??????????????????? */
PushSharedStack1(&shared_stack, 200);
/* ?0742??????????????????????????? */
if (PopSharedStack0(&shared_stack, &value)) {
/* ?0743??????????????????????? */
printf("shared stack 0 pop: %d\n", value);
/* ?0744?????????????????? */
}
/* ?0745??????????????????????????? */
if (PopSharedStack1(&shared_stack, &value)) {
/* ?0746??????????????????????? */
printf("shared stack 1 pop: %d\n", value);
/* ?0747?????????????????? */
}
/* ?0748??????????????????????? */
/* ?0749???????????????????????????? */
InitLinkStack(&link_stack);
/* ?0750??????????????????? */
PushLinkStack(&link_stack, 7);
/* ?0751??????????????????? */
PushLinkStack(&link_stack, 8);
/* ?0752??????????????????? */
PushLinkStack(&link_stack, 9);
/* ?0753??????????????????????????? */
if (GetTopLinkStack(&link_stack, &value)) {
/* ?0754??????????????????????? */
printf("link top: %d\n", value);
/* ?0755?????????????????? */
}
/* ?0756??????????????????????????? */
if (PopLinkStack(&link_stack, &value)) {
/* ?0757??????????????????????? */
printf("link pop: %d\n", value);
/* ?0758?????????????????? */
}
/* ?0759??????????????????????????? */
if (GetTopLinkStack(&link_stack, &value)) {
/* ?0760??????????????????????? */
printf("link new top: %d\n", value);
/* ?0761?????????????????? */
}
/* ?0762?????????????????????? */
DestroyLinkStack(&link_stack);
/* ?0763??????????????????????? */
/* ?0764??????????????????????? */
printf("balanced '([{}])' => %s\n",
/* ?0765??????????????????? */
IsBracketSequenceBalanced("([{}])") ? "true" : "false");
/* ?0766??????????????????????? */
printf("balanced '([)]' => %s\n",
/* ?0767??????????????????? */
IsBracketSequenceBalanced("([)]") ? "true" : "false");
/* ?0768??????????????????????????? */
if (EvaluatePostfixExpression("23*54*+9-", &postfix_value)) {
/* ?0769??????????????????????? */
printf("postfix value: %d\n", postfix_value);
/* ?0770?????????????????? */
}
/* ?0771??????????????????????? */
/* ?0772???????????????????????????? */
InitCircularQueue(&circular_queue);
/* ?0773??????????????????? */
EnqueueCircularQueue(&circular_queue, 11);
/* ?0774??????????????????? */
EnqueueCircularQueue(&circular_queue, 22);
/* ?0775??????????????????? */
EnqueueCircularQueue(&circular_queue, 33);
/* ?0776??????????????????????? */
PrintCircularQueue(&circular_queue);
/* ?0777??????????????????????????? */
if (GetHeadCircularQueue(&circular_queue, &value)) {
/* ?0778??????????????????????? */
printf("circular queue head: %d\n", value);
/* ?0779?????????????????? */
}
/* ?0780??????????????????????????? */
if (DequeueCircularQueue(&circular_queue, &value)) {
/* ?0781??????????????????????? */
printf("circular queue dequeue: %d\n", value);
/* ?0782?????????????????? */
}
/* ?0783??????????????????????? */
PrintCircularQueue(&circular_queue);
/* ?0784??????????????????????? */
/* ?0785??????????????????????????? */
if (InitLinkQueue(&link_queue)) {
/* ?0786??????????????????? */
EnqueueLinkQueue(&link_queue, 101);
/* ?0787??????????????????? */
EnqueueLinkQueue(&link_queue, 102);
/* ?0788??????????????????? */
EnqueueLinkQueue(&link_queue, 103);
/* ?0789??????????????????????? */
PrintLinkQueue(&link_queue);
/* ?0790??????????????????????????? */
if (GetHeadLinkQueue(&link_queue, &value)) {
/* ?0791??????????????????????? */
printf("link queue head: %d\n", value);
/* ?0792?????????????????? */
}
/* ?0793??????????????????????????? */
if (DequeueLinkQueue(&link_queue, &value)) {
/* ?0794??????????????????????? */
printf("link queue dequeue: %d\n", value);
/* ?0795?????????????????? */
}
/* ?0796??????????????????????? */
PrintLinkQueue(&link_queue);
/* ?0797?????????????????????? */
DestroyLinkQueue(&link_queue);
/* ?0798?????????????????? */
}
/* ?0799??????????????????????? */
/* ?0800???????????????????????????? */
InitDeque(&deque);
/* ?0801??????????????????? */
PushBackDeque(&deque, 5);
/* ?0802??????????????????? */
PushBackDeque(&deque, 6);
/* ?0803??????????????????? */
PushFrontDeque(&deque, 4);
/* ?0804??????????????????? */
PushFrontDeque(&deque, 3);
/* ?0805??????????????????????? */
PrintDeque(&deque);
/* ?0806??????????????????????????? */
if (PopFrontDeque(&deque, &value)) {
/* ?0807??????????????????????? */
printf("deque pop front: %d\n", value);
/* ?0808?????????????????? */
}
/* ?0809??????????????????????????? */
if (PopBackDeque(&deque, &value)) {
/* ?0810??????????????????????? */
printf("deque pop back: %d\n", value);
/* ?0811?????????????????? */
}
/* ?0812??????????????????????? */
PrintDeque(&deque);
/* ?0813??????????????????????? */
/* ?0814??????????????????????? */
printf("1D index offset A[5] from A[0]: %d\n", RowMajorIndex1D(0, 5));
/* ?0815??????????????????????? */
printf("row-major index A[2][1] in A[0..2][0..3]: %d\n",
/* ?0816??????????????????? */
RowMajorIndex2D(2, 1, 0, 0, 4));
/* ?0817??????????????????????? */
printf("col-major index A[2][1] in A[0..2][0..3]: %d\n",
/* ?0818??????????????????? */
ColMajorIndex2D(2, 1, 0, 0, 3));
/* ?0819??????????????????????? */
printf("symmetric index a[3][1]: %d\n", SymmetricMatrixIndex(3, 1));
/* ?0820??????????????????????? */
printf("lower triangular index a[3][1]: %d\n", LowerTriangularMatrixIndex(3, 1, 4));
/* ?0821??????????????????????? */
printf("upper triangular index a[1][3]: %d\n", UpperTriangularMatrixIndex(1, 3, 4));
/* ?0822??????????????????????? */
printf("tridiagonal index a[3][2]: %d\n", TridiagonalMatrixIndex(3, 2));
/* ?0823??????????????????????? */
/* ?0824???????????????????????? */
triple_count = DenseMatrixToTriples(&dense_matrix[0][0], 3, 3, triples, 9);
/* ?0825??????????????????????????? */
if (triple_count >= 0) {
/* ?0826??????????????????????? */
PrintTriples(triples, triple_count);
/* ?0827?????????????????? */
}
/* ?0828??????????????????????? */
/* ?0829???????????????????????? */
return 0;
/* ?0830?????? `main` ???? */
}
继续阅读