使用堆栈存储模型(后进先出)来挂载链表数据

落日映苍穹つ 2022-05-28 03:05 113阅读 0赞

/*************************************************** * 文件名：ListStack * 文件描述：使用堆栈存储模型(后进先出)来挂载链表数据 * 头部插入链表方式相当于堆栈模型的存储模式 * 编辑人：王廷云 * 编辑日期：2017-11-12 * 修改日期：2018-2-1 ***************************************************/
    
    #include <stdio.h>
    #include <stdlib.h> 
    
    /* 数据节点封装 */
    struct node
    { 
    	char data;
    	struct node *next;
    } stackHead = { .next = NULL};
    
    /* 栈模型函数 */
    void push(char data);               // 压栈
    int pop(void);                      // 出栈
    int top(void);                      // 栈顶
    int isEmptyStack(void);             // 栈空
    int isFullStack(void);              // 栈满
    
    /* 括号匹配检查函数 */
    void check(char left, char right);  
    
    int main(void)
    { 
    	char buff[1024];
    	int i = 0;
    
    	printf("\n=====输入带有括号的字符串=====\n");
    	scanf("%s", buff);
    	
    	/* 循环检查直到检查完毕 */
    	while (buff[i])
    	{ 
    		switch (buff[i])
    		{ 
    			/* 左括号入栈 */
    			case '(':  /* no break */
    			case '[':	
    			case '{':
    			case '<': push(buff[i]);	   break;
    			
    			/* 右括号出栈检查 */
    			case ')': check('(', buff[i]); break;
    			case ']': check('[', buff[i]); break;
    			case '}': check('{', buff[i]); break;
    			case '>': check('<', buff[i]); break;
    		}
    		i++;
    	}
    	
    	/* 检查完所有右括号字符后还有左括号说明不匹配 */
    	while (!isEmptyStack())
    	{ 
    		printf("\'%c\'是多余的括号!\n", pop());
    	}
    
    	return 0;
    }
    
    /** * 函数名：push * 函数功能：数据节点入栈 * 参数：data：入栈的数据 * 返回值：void */
    void push(char data)
    { 
    	struct node *newOne;
    
    	/* 分配新节点数据空间 */
    	newOne = malloc(sizeof(newOne));
    	if (NULL == newOne)
    	{ 
    		printf("Push data error! Maybe stack of memry is full!\n");
    		exit(1);
    	}
    	
    	/* 给新节点赋值数据 */
    	newOne->data = data;
    	
    	/* 链表头插入节点方式模拟入栈 */	
    	newOne->next = stackHead.next;
    	stackHead.next = newOne;
    }
    
    /** * 函数名：pop * 函数功能：数据节点出栈 * 参数：void * 返回值：栈顶数据 */
    int pop(void)
    { 
    	struct node *topNode;
    	char topData; 
    
    	topNode = stackHead.next;			// 先保存栈顶数据地址
    	topData = stackHead.next->data;		// 取栈顶数据
    	
    	stackHead.next = topNode->next;	// 摘掉栈顶节点
    	free(topNode);
    
    	return topData;						// 返回栈顶数据
    }
    
    /** * 函数名：top * 函数功能：获取栈顶数据 * 参数：void * 返回值：栈顶数据 */
    int top(void)
    { 
    	return stackHead.next->data;
    }
    
    /** * 函数名：isEmptyStack * 函数功能：判断栈是否为空 * 参数：void * 返回值：栈为空返回1，不为空返回0 */
    int isEmptyStack(void)
    { 
    	return stackHead.next == NULL;
    }
    
    /** * 函数名：isFullStack * 函数功能：判断栈是否已满 * 参数：void * 返回值：0-链表不存在满的情况 */
    int isFullStack(void)
    { 
    	return 0;
    }
    
    /** * 函数名：check * 函数功能：通过检查括号是否匹配 * 参数：left: 左括号 right: 右括号 * 返回值：void */
    void check(char left, char right)
    { 
    	char temp;
    
    	if (isEmptyStack())
    	{ 
    		printf("%c 是多余的括号\n", right);
    		exit(1);
    	}
    	
    	temp = pop();
    	if (temp != left)
    	{ 
    		printf("\'%c\' 和 \'%c\' 不匹配\n",left,right);
    		exit(1);
    	}
    }