赞
踩
#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"); else printf("该链表不是中心对称\n"); Push(&stack, 'a'); Push(&stack, 'b'); Push(&stack, 'a'); if(match(stack,Length(stack))) printf("该链表为中心对称\n"); else printf("该链表不是中心对称\n"); Push(&stack, 'a'); if(match(stack,Length(stack))) printf("该链表为中心对称\n"); else printf("该链表不是中心对称\n"); //销毁链栈 DestroyStack(&stack); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。