C语言通过链表实现--栈

一、栈注释

1.结构体构建

定义了Item，Item中储存了一个字符串和总的栈数numb。

定义Node节点，节点中有Item，和指向node的指针（用来链接上一项）。

typedef struct
{
	char str[10];
	int numb;
}Item;

typedef struct node
{
	Item item;
	struct node* next;
} Node;

typedef struct
{
	Node* head;
}Stack;

2.初始化

pq传进来的地址是已经确定了的。

void STACKinit(Stack* pq)
{
    pq->head = NULL;
}

3.推入栈

bool PushStack(Item a, Stack* pq)
{
	Node* New;
	Node* pp = pq->head;

	New = (Node*)malloc(sizeof(Node));
	if (New == NULL)
	{
		printf("没分配内存\n");
		return false;
	}

	New->item = a;
	
	if (a.numb == 0)   //判断是否为第一项，是的话New->next = NULL;
	{
		pq->head = New;
		New->next = NULL;
	}
	else
	{
		New->next = pq->head;
		pq->head = New;
	}

	return true;
}

4.推出栈

清空栈可以循环该函数，直到pq->head==NULL,退出循环。

void PopStack(Stack* pq)
{
	Node* old;
	old = pq->head;
	pq->head = pq->head->next;
	free(old);
}

5.输出栈

void Output(const Stack* pq)
{
	if (pq->head == NULL)
	{
		printf("空栈！\n");
		return;
	}

	Node* pp = pq->head;
	printf("栈中的项：\n");
	while (pp != NULL)
	{
		printf("%s\n", pp->item.str);
		pp = pp->next;
	}
	printf("项数：%d\n", pq->head->item.numb);
}

二、完整程序、

该程序缺少栈清空。

STACK.h  函数接口

#ifndef STACK_H_
#define STACK_H_

typedef struct
{
	char str[10];
	int numb;
}Item;

typedef struct node
{
	Item item;
	struct node* next;
} Node;

typedef struct
{
	Node* head;
}Stack;

/* 初始化栈         */
void STACKinit(Stack* pq);

/* 在头部添加栈     */
bool PushStack(Item a, Stack* pq);

/* 在头部推出栈     */
void PopStack(Stack* pq);

/* 遍历栈，输出栈的项*/
void Output(const Stack* pq);

#endif

STACK.cpp  函数实现

#include
#include
#include
#include"STACK.h"

void STACKinit(Stack* pq)
{
	pq->head = NULL;
}

bool PushStack(Item a, Stack* pq)
{
	Node* New;
	Node* pp = pq->head;

	New = (Node*)malloc(sizeof(Node));
	if (New == NULL)
	{
		printf("没分配内存\n");
		return false;
	}

	New->item = a;
	
	if (a.numb == 0)   //判断是否为第一项，是的话New->next = NULL;
	{
		pq->head = New;
		New->next = NULL;
	}
	else
	{
		New->next = pq->head;
		pq->head = New;
	}

	return true;
}

void PopStack(Stack* pq)
{
	Node* old;
	old = pq->head;
	pq->head = pq->head->next;
	free(old);
}

void Output(const Stack* pq)
{
	if (pq->head == NULL)
	{
		printf("空栈！\n");
		return;
	}

	Node* pp = pq->head;
	printf("栈中的项：\n");
	while (pp != NULL)
	{
		printf("%s\n", pp->item.str);
		pp = pp->next;
	}
	printf("项数：%d\n", pq->head->item.numb);
}

栈.cpp 栈应用

#include
#include
#include"STACK.h"

int main(void)
{
	Stack stack;
	Item strn;
	int i = 0;
	
	STACKinit(&stack);

	printf("输入0，退出 | 输入*:推出栈 | 输入l，查看栈\n");

	while (1)
	{
		strn.numb = i;
		scanf_s("%s", strn.str, 9);
		if (strcmp(strn.str, "0") == 0)
		{
			break;
		}
		else if (strcmp(strn.str, "l") == 0)
		{
			strn.numb = i;
			Output(&stack);
			continue;
		}

		if (strcmp(strn.str, "*") != 0)
		{
			i++;
			strn.numb = i;
			PushStack(strn, &stack);
            printf("推入成功！\n);
		}	
		else
		{
			i--;
			PopStack(&stack);
            printf("推出成功！\n);
		}
	}

	puts("Bye!");

	return 0;
}

三、运行结果

 

 Success is not final, failure is not fatal: it is the courage to countine that counts.

成功不是终点，失败不足以致命，最可贵的是继续前进的勇气。