---

---

代码实现

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>#define ElemType char//定义链栈结构体，并规定栈顶就是链头，一切操作只能在链头进行
typedef struct LNode {//定义数据，这里一个结构体存储一个数据，所以不需要什么指针啊数组之类的乱七八糟的，就一个变量就够了ElemType data;//定义下一个结点struct LNode *next;
} LNode, *LinkStack;//初始化栈
void InitStack(LinkStack *stack) {//一开始栈里啥也没有，不需要设置头结点*stack = NULL;
}//判断栈空
bool StackEmpty(LinkStack stack) {if (stack == NULL)return true;return false;
}//入栈操作
bool Push(LinkStack *stack, ElemType e) {//因为是链表，所以不用判断是否溢出，基本不可能溢出，直接插入头结点//建立一个新的结构体结点LinkStack new = (LinkStack) malloc(sizeof(LNode));if (new == NULL)//虽然不会溢出，但是内存可能分配失败，还是要顾及一下代码的健壮性的return false;//把数据元素放到结构体里面new->data = e;//让新结构体的下一个指针指向链头new->next = *stack;//把链头移动到新结构体*stack = new;return true;
}//出栈操作
bool Pop(LinkStack *stack, ElemType *e) {//先判断一下栈是否为空if (StackEmpty(*stack))return false;//先将数据元素赋值给E*e = (*stack)->data;//保存一下链头结构体，不然一会儿不好释放内存LinkStack old = *stack;//转移链头到下一个结点位置*stack = (*stack)->next;//释放原来的链头内存空间free(old);return true;
}//获取栈顶元素
bool GetTop(LinkStack stack, ElemType *e) {//先判断栈是否为空if (StackEmpty(stack))return false;//获取栈顶元素*e = stack->data;return true;
}//销毁栈
void DestroyStack(LinkStack *stack) {//不能只销毁链头，要把整个链表全部释放while (*stack != NULL) {LNode *new = *stack;*stack = (*stack)->next;free(new);}
}//-------------------顺便写一道王道课后题代码---------------------
/*P67栈04题;设单链表表头指针为L，结点由data和next两个域构成，其中data域为字符型。
试设计算法判断该链表的全部n个字符是否中心对称。例如xyx、xyyx都是中心对称*/bool match(LinkStack stack, int n) { //n是题目中给出的字符的总数int i;//建立一个字符数组，存储前半个链表中的数据元素，用来对比后半个链表中的元素是否相等char data[n / 2];//for循环将前半个链表存储到data字符数组中for (i = 0; i < n / 2; i++) {data[i] = stack->data;stack = stack->next;}i--;//要区分字符总数是奇数个还是偶数个//如果是偶数个字符if(n%2 == 0){for(;i>0;i--){if(data[i] != stack->data)return false;stack = stack->next;}return true;}//如果是奇数个字符else{for(;i>0;i--){if(data[i] != stack->data)return false;stack = stack->next;}}
}//为了方便后面的实验，写一个计算栈长的函数
int Length(LinkStack stack){int num = 0;while(stack != NULL){num++;stack = stack->next;}return num;
}
int main() {//定义链表LinkStack stack;ElemType Elem;//初始化链表InitStack(&stack);
//
//    //插入元素
//    Push(&stack, 1);
//    Push(&stack, 2);
//    Push(&stack, 3);
//
//    //获取栈顶元素
//    GetTop(stack, &Elem);
//    printf("当前栈顶元素为%d\n", Elem);
//
//    //依次出栈元素
//    printf("出栈元素为:");
//    Pop(&stack, &Elem);
//    printf("%d ", Elem);
//    Pop(&stack, &Elem);
//    printf("%d ", Elem);
//    Pop(&stack, &Elem);
//    printf("%d\n", Elem);//将ElemType改为char后，测试题目代码Push(&stack, 'a');Push(&stack, 'b');Push(&stack, 'a');if(match(stack,Length(stack)))printf("该链表为中心对称\n");elseprintf("该链表不是中心对称\n");Push(&stack, 'a');Push(&stack, 'b');Push(&stack, 'a');if(match(stack,Length(stack)))printf("该链表为中心对称\n");elseprintf("该链表不是中心对称\n");Push(&stack, 'a');if(match(stack,Length(stack)))printf("该链表为中心对称\n");elseprintf("该链表不是中心对称\n");//销毁链栈DestroyStack(&stack);return 0;
}