C语言实现使用带头结点的单链表来模拟栈结构
程序员文章站
2022-05-13 17:35:21
我在前面两篇博客中分别使用了静态数组、动态数组两种方式来构造栈,实现起来很方便,但总觉得灵活性还不够,因为无论怎样,我们都是要指定数组的长度。这篇博客中我们将会使用带头结点的单链表...
我在前面两篇博客中分别使用了静态数组、动态数组两种方式来构造栈,实现起来很方便,但总觉得灵活性还不够,因为无论怎样,我们都是要指定数组的长度。这篇博客中我们将会使用带头结点的单链表来模拟栈。为什么选用单链表呢?因为对于栈来说,弹出、压入等操作都是对栈顶来操作的。而单链表对第一个节点的操作是最为方便的。两者刚好能对应起来。代码上传至 https://github.com/chenyufeng1991/Stack_LinkedList。
(1)声明节点类型、函数
typedef int elemType; typedef struct NodeList{ int element; struct NodeList *next; }Node; void createStack(Node **pNode); void destroyStack(Node *pNode); void push(Node *pNode,int value); void pop(Node *pNode); void top(Node *pNode); int isEmpty(Node *pNode); int isFull(Node *pNode); void printStack(Node *pNode);
(2)初始化单链表
//初始化带头结点的单链表 void createStack(Node **pNode){ *pNode = (Node *)malloc(sizeof(Node)); if (*pNode == NULL) { printf("%s函数执行,内存分配失败,初始化单链表失败\n",__FUNCTION__); }else{ (*pNode)->next = NULL; printf("%s函数执行,带头结点的单链表初始化完成\n",__FUNCTION__); } }
(3)压入一个元素
//压入一个元素 void push(Node *pNode,int value){ Node *pInsert; pInsert = (Node *)malloc(sizeof(Node));//需要检测分配内存是否成功 pInsert == NULL ? memset(pInsert, 0, sizeof(Node)); pInsert->next = NULL; pInsert->element = value; pInsert->next = pNode->next; pNode->next = pInsert; }
(4)弹出一个元素
//弹出一个元素 void pop(Node *pNode){ if (!isEmpty(pNode)) { Node *pNext; pNext = pNode->next; pNode->next = pNext->next; free(pNext); pNext = NULL; } }
(5)打印栈元素
//打印栈元素 void printStack(Node *pNode){ if (!isEmpty(pNode)) { Node *pMove; pMove = pNode->next; while (pMove != NULL) { printf("%d ",pMove->element); pMove = pMove->next; } printf("\n"); }else{ printf("栈为空,打印失败\n"); } }
(6)清空栈元素
//清空栈元素 void destroyStack(Node *pNode){ Node *pMove; pMove = pNode->next; while (pMove != NULL) { pNode->next = pMove->next; free(pMove); pMove = pNode->next; } }
(7)判断栈是否为空
//判断栈是否为空 int isEmpty(Node *pNode){ /** * 当只有一个头结点的时候,该链表就为空 */ if (pNode->next == NULL) { return 1; } return 0; }
(8)取栈顶元素
//取栈顶元素 void top(Node *pNode){ if (!isEmpty(pNode)) { printf("栈顶元素为%d\n",pNode->next->element); } }
(8)测试代码
int main(int argc, const char * argv[]) { Node *pList; createStack(&pList); push(pList, 3);push(pList, 1);push(pList, 9);push(pList, 4);push(pList, 7); printStack(pList); pop(pList);pop(pList); printf("经过pop后栈的元素为:\n"); printStack(pList); top(pList); destroyStack(pList); printStack(pList); return 0; }