jtahstu的博客

root@jtahstu.com   Github   英文博客  

最新碎语:以后没事写写小的知识点吧

您的位置:jtahstu的博客 >算法> 数据结构与算法从入门到懵逼 - 栈和队列的链式存储结构

数据结构与算法从入门到懵逼 - 栈和队列的链式存储结构

栈的链式存储结构

// LiStack.cpp : 定义控制台应用程序的入口点。
// 栈的链式存储

#include "stdafx.h"
#include<iostream>
#include<cstring>

using namespace std;

typedef char ElemType;

typedef struct linknode {
	ElemType data;
	struct linknode * next;
}LiStack;

//初始化栈
void InitStack(LiStack *&s) {
	s = (LiStack *)malloc(sizeof(LiStack));
	s->next = NULL;
}

//销毁栈
void DestoryStack(LiStack *&s) {
	LiStack *p = s, *q = s->next;
	while (q!=NULL)	{
		free(p);
		p = q;
		q = p->next;
	}
	free(p);	//此时p指向尾节点,释放其空间
}

//判断栈是否为空
bool StackEmpty(LiStack *&s) {
	return s->next == NULL;
}

//进栈
void Push(LiStack *&s, ElemType e) {
	LiStack *p ;
	p = (LiStack *)malloc(sizeof(LiStack));
	p->data = e;
	p->next = s->next;
	s->next = p;
}

//出栈
ElemType Pop(LiStack *&s) {
	if (s->next == NULL)
		return NULL;
	LiStack *p;
	p = (LiStack *)malloc(sizeof(LiStack));
	p = s->next;
	s->next = p->next;
	ElemType e=p->data;
	free(p);
	return e;
}

//取栈顶元素
ElemType GetTop(LiStack *s) {
	if (s->next == NULL)
		return NULL;
	return s->next->data;
}

//判断输入的表达式中的括号是否配对(假设只含左右括号)
bool Match(char exp[]) {
	int i = 0;
	char e;
	bool flag = true;
	LiStack *s;
	InitStack(s);
	while (i < strlen(exp)&&flag)
	{
		if (exp[i] == '(')
			Push(s,exp[i]);
		else {
			if (GetTop(s) == '(')
				Pop(s);
			else {
				flag = false;
				break;
			}
		}
		i++;
	}
	if (StackEmpty(s)&&flag)
		return true;
	DestoryStack(s);
	return false;
}

int main(){
	char exp1[] = "((()()))";
	char exp2[] = "((((((((((((((((((((((((((((((((((((((((((((((((()))))))))))))))))))))))))))))))))))";
	if (Match(exp1))
		cout << "匹配" << endl;
	else
		cout << "不匹配" << endl;
	if (Match(exp2))
		cout << "匹配" << endl;
	else
		cout << "不匹配" << endl;
	getchar();
    return 0;
}

队列的链式存储结构


// LiQueue.cpp : 定义控制台应用程序的入口点。
// 队列的链式存储

#include "stdafx.h"
#include<iostream>

using namespace std;

typedef int ElemType;

//链队中的数据节点
typedef struct qnode {
	ElemType data;
	struct qnode * next;
}QNode;

//链队头节点
typedef struct {
	QNode * front;
	QNode * rear;
}LiQueue;

//初始化队列
void InitQueue(LiQueue * &q) {
	q = (LiQueue *)malloc(sizeof(LiQueue));
	q->front = q->rear = NULL;
}

//销毁队列
void DestroyQueue(LiQueue * &q) {
	QNode *p = q->front, *r;
	if(p != NULL) {		//队列不为空才销毁
		r = p->next;
		while (r != NULL) {
			free(p);	//删除当前节点
			p = r;		//p后移
			r->next = p;	//下一个删除的元素
		}
	}
	free(p);	//自定义的节点都销毁
	free(q);	//释放队列头节点
}

//判断队列是否为空
bool QueueEmpty(LiQueue *q) {
	return q->rear == NULL;
	//return q->front == NULL;	//两种写法都可以
}

//进队列,从队列的尾部插入
void enQueue(LiQueue * &q, ElemType e) {
	QNode *p;
	p = (QNode *)malloc(sizeof(QNode));
	p->data = e;
	p->next = NULL;
	if (q->front == NULL) {	//如果队列为空,则队头和队尾都指向p节点
		q->front = q->rear = p;
	}else {
		q->rear->next = p;	//最后一个节点的下一个节点设置为p
		q->rear = p;	//队尾指针指向p
	}
}

//出队列,从队列的头部出
ElemType deQueue(LiQueue * &q) {
	if (q->front == NULL)	//空队列,出个啥
		return NULL;
	QNode *p;
	p = (QNode *)malloc(sizeof(QNode));
	p = q->front;
	q->front = p->next;
	if (q->front == NULL)	//如果出了一个节点,队列为空,则队尾指针也要设置为空
		q->rear = NULL;
	ElemType e = p->data;
	free(p);
	return e;
}

//输出队列
void DisQueue(LiQueue *q) {
	QNode *p;
	p = q->front;
	while (p->next!=NULL)	{
		cout << p->data << " ";
		p = p->next;
	}
	cout <<p->data<< endl;	//这里需要输出最后一位
}

int main() {
	LiQueue *q;
	InitQueue(q);
	enQueue(q, 1);
	enQueue(q, 2);
	enQueue(q, 3);
	enQueue(q, 4);
	enQueue(q, 666);
	enQueue(q, 233);
	cout << "当前队列的排列是:";
	DisQueue(q);
	cout << "出一个元素后:";
	deQueue(q);
	DisQueue(q);

	getchar();
	return 0;
}


---

本文章采用 知识共享署名2.5中国大陆许可协议 进行许可,欢迎转载,演绎或用于商业目的。

---

二维码加载中...

扫一扫移动端访问O(∩_∩)O

发表评论

60 + 88 =
路人甲 表情
看不清楚?点图切换 Ctrl+Enter快速提交
正在加载中……