1. Toy模板网首页
  2. > Toy博客

数据结构与算法系列之习题练习

9月前 作者：小怡同学.. 分类：Toy博客 阅读(46) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构与算法系列之习题练习。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构与算法系列之习题练习

💗 💗 博客:小怡同学
💗 💗 个人简介:编程小萌新
💗 💗 如果博客对大家有用的话，请点赞关注再收藏 🌞

力扣习题

  1. 括号匹配问题。
  2. 用队列实现栈。
  3. 用栈实现队列。
  4. 设计循环队列。

  1. 有效的括号
    //用栈来实现
    //左括号进栈 右括号出栈并销毁如果不匹配则return


#include <stdbool.h>
#include <assert.h> 
#include <stdlib.h>
#include <stdio.h>
typedef char SDatetype;
typedef struct Stack
{
	SDatetype* a;
	int top;
	int capacity;
}Stack;

void StackInit(Stack* pq);
void StackDestory(Stack* pq);
void StackPush(Stack* pq, SDatetype x);
void StackPop(Stack* pq);
bool StackEmpty(Stack* pq);
SDatetype StackTop(Stack* pq);
int StackSize(Stack* pq);
 bool StackEmpty(Stack* pq)
{
	assert(pq);
	return pq->top == 0;
}
void StackInit(Stack* pq)
{
	assert(pq);
	pq->a = NULL;
	pq->capacity = 0;
	pq->top = 0;
}
void StackDestory(Stack* pq)
{
	assert(pq);
	pq->capacity = 0;
	pq->top = 0;
	free(pq->a);
	pq->a =NULL;
}
void StackPush(Stack* pq, SDatetype x)
{
	assert(pq);
	if (pq->top == pq->capacity)
	{
		int newcapacity = (pq->top == 0 ? 4 : (pq->capacity) * 2);
		pq->a = (SDatetype*)realloc(pq->a,sizeof(SDatetype) * newcapacity);
		if (pq->a == NULL)
		{
			perror("malloc fail");
			exit(-1);
		}
		pq->capacity = newcapacity;
	}

	pq->a[pq->top++] = x;

}

void StackPop(Stack* pq)
{
	assert(pq);
	assert(!StackEmpty(pq));
	pq->top--;
}

SDatetype StackTop(Stack* pq)
{
	assert(pq);
	assert(!StackEmpty(pq));
	return pq->a[pq->top-1];
}

int StackSize(Stack* pq)
{
	assert(pq);
	return pq->top;
}
bool isValid(char * s){

Stack pq;
StackInit(&pq);
    while(*s)
    {
        if(*s== '(' || *s == '[' || *s == '{')
        {
           StackPush(&pq, *s);//进栈
        }
        else
        {
			if(StackEmpty(&pq))//如果只有一个左括号 无法匹配则return
			{
				StackDestory(&pq);
				return false;
			}
            char tmp = StackTop(&pq);
			StackPop(&pq);
            if( (tmp != '('  && *s == ')' )||
			    (tmp != '[' && *s == ']'  )||
				(tmp != '{' && *s == '}'))//如果有一对不匹配则return
            {
				StackDestory(&pq);//return之前需要销毁栈 以免内存泄漏
                return false;
            }
        }

        s++;
    }

	bool tmp = StackEmpty(&pq);//当栈里还有元素时则匹配失败
	StackDestory(&pq);
	return tmp;
}

225. 用队列实现栈（力扣）

//设置两个队列，入栈向有元素的队列加入， 出栈（因为栈上后进先出）所以需要把有元素的队列依次移入另一个队列 再删除

typedef int QDatetype;
typedef struct Qnode
{
	int* next;
	QDatetype x;
}Qnode;
typedef struct Queue
{
	Qnode* head;
	Qnode* tail;
}Queue;


typedef struct {
    Queue Qtwo;
    Queue Qone;
} MyStack;


void QueueInit(Queue* pq)
{
	assert(pq);

	pq->tail = pq->head = NULL;

}
void QueueDestory(Queue* pq)
{
	assert(pq);
	while (pq->head)
	{
		Qnode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}

}
void QueuePush(Queue* pq,	QDatetype q)
{
	assert(pq);
	Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
	newnode->next = NULL;
	newnode->x = q;

	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
		
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}


bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if(pq->head  == pq->tail)
	{
		free(pq->head);
		pq->head = pq->tail= NULL;
	}
else
{
Qnode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
}	
}

QDatetype QueueTop(Queue* pq)
{
	assert(pq);
		assert(!QueueEmpty(pq));
	return pq->head->x;
}


int QueueSize(Queue* pq)
{
	assert(pq);
	Qnode* head = pq->head;
	int size = 0;
	while (head)
	{
		size++;
		head =  head->next;
	}
	return size;
}


QDatetype QueueTail(Queue* pq)
{
	assert(pq);
		assert(!QueueEmpty(pq));
	return pq->tail->x;
}

//创造一个由队列创建的栈
MyStack* myStackCreate() {

     MyStack* pq = (MyStack*)malloc(sizeof(MyStack)); 
		 //向堆申请空间不会随栈的销毁而销毁
     QueueInit(&pq->Qtwo);
     QueueInit(&pq->Qone);
		 return pq;
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->Qone) && QueueEmpty(&obj->Qtwo);
}

void myStackPush(MyStack* obj, int x) {

Queue* one = &obj-> Qone;
Queue* two = &obj-> Qtwo;

if(!QueueEmpty(one))
{
     QueuePush(one, x);
}
else
{
    QueuePush(two,x);
}
}

int myStackPop(MyStack* obj) {

Queue* noempty = &obj-> Qone;
Queue* empty = &obj-> Qtwo;


if(!QueueEmpty(empty) )
{
	empty = &obj->Qone;
	noempty = &obj->Qtwo;
}

while(QueueSize(noempty) >1)
{
    QueuePush(empty, QueueTop(noempty));
    QueuePop(noempty);
}

int x =  QueueTop(noempty);
 QueuePop(noempty);
return x;


}

int myStackTop(MyStack* obj) {
Queue* one = &obj-> Qone;
Queue* two = &obj-> Qtwo;
if(!QueueEmpty(one))
{
    return QueueTail(one);
}
else
{
    return QueueTail(two);
}
}


void myStackFree(MyStack* obj) {

    QueueDestory(&obj->Qone);
    QueueDestory(&obj->Qtwo);
		free(obj);
    }

myStackPop函数的功能实现图

数据结构与算法系列之习题练习

232. 用栈实现队列（力扣）

//与用队列实现栈的思想不同， 这里的栈分别是push栈 和pop栈 （专门用来插入数据和删除数据）


#include <stdbool.h>
#include <assert.h> 
#include <stdlib.h>
#include <stdio.h>
typedef int SDatetype;
typedef struct Stack
{
	int* a;
	int top;
	int capacity;
}Stack;

 bool StackEmpty(Stack* pq)
{
	return pq->top == 0;
}
int StackSize(Stack* pq)
{
    return pq->top;
}
void StackInit(Stack* pq)
{
	assert(pq);
	pq->a = NULL;
	pq->capacity = 0;
	pq->top = 0;
}
void StackDestory(Stack* pq)
{
	assert(pq);
	pq->capacity = 0;
	pq->top = 0;
	free(pq->a);
}

void StackPush(Stack* pq, SDatetype x)
{
	assert(pq);
	if (pq->top == pq->capacity)
	{
		int newcapacity = (pq->top == 0 ? 4 : (pq->capacity) * 2);
		pq->a = (SDatetype*)realloc(pq->a,sizeof(SDatetype) * newcapacity);
		if (pq->a == NULL)
		{
			perror("malloc fail");
			return;
		}
		pq->capacity = newcapacity;
	}

	pq->a[pq->top++] = x;

}



void StackPop(Stack* pq)
{
	assert(pq);
	assert(!StackEmpty(pq));
	pq->a[pq->top--];
}

SDatetype StackTop(Stack* pq)
{
	assert(pq);
	assert(!StackEmpty(pq));
	return pq->a[pq->top-1];
}
typedef struct {
    Stack push;
    Stack pop;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* pq =(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&pq->push);
    StackInit(&pq->pop);
	return pq;
}


bool myQueueEmpty(MyQueue* obj) {
	return  StackEmpty(&obj->push) && StackEmpty(&obj->pop);
}


void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->push,  x);
}


//这个函数主要功能实现的是 出队的元素是谁
//有两种情况：
//1.pop栈中有元素，直接出队
//2.pop栈中无元素, 需要把push栈中移入到pop栈里
int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
          StackPush(&obj->pop ,StackTop(&obj->push));
          StackPop(&obj->push);
        }
    }
    return StackTop(&obj->pop);  
}



int myQueuePop(MyQueue* obj) {

    int front = myQueuePeek(obj);
    StackPop(&obj->pop);
    return front; 
}

void myQueueFree(MyQueue* obj) {
	StackDestory(&obj->push);
	StackDestory(&obj->pop);
	free(obj);
}

myQueuePop主要功能图

数据结构与算法系列之习题练习

622. 设计循环队列

//主要是用顺序表存储数据
//不用链表实现是因为1.找尾不容易找到，2，链表是否存满不好判断

typedef struct {

int front;
int rear ;
int k;
int* a;
} MyCircularQueue;


//公开辟（k+1）个空间 判断是否判空
MyCircularQueue* myCircularQueueCreate(int k) {
 MyCircularQueue* pq = ( MyCircularQueue*)malloc(sizeof( MyCircularQueue));
 pq->front = pq->rear= 0;
 pq->k = k;
 pq->a = (int*)malloc(sizeof(int)*(k+1));
 return pq;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->rear  == obj->front ;
    
}
//rear+1 = front则链表满了
bool myCircularQueueIsFull(MyCircularQueue* obj) {

return (obj->rear +1) % (obj->k+1) == (obj->front);
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (!myCircularQueueIsFull(obj))
{
    obj->a[obj->rear] = value;
    obj->rear = (++obj->rear % (obj->k+1));//rear++之后下标不能大于k+1，所以%（k+1）
    return true;
}
return false;
}


bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        ++obj->front;
        obj->front = obj->front%(obj->k+1);
        return true;
    }
}

int myCircularQueueFront(MyCircularQueue* obj) {

     if(!myCircularQueueIsEmpty(obj))
{
    return obj->a[obj->front];
}
else
{
    return -1;
}
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(!myCircularQueueIsEmpty(obj))
    {
        return obj->a[(obj->rear-1 + obj->k+1)%(obj->k+1)] ;
        //rear--之后下标不能小于0
    }
    else
    {
        return -1;
    }
}

void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
obj->a = NULL;
free(obj);
obj = NULL;
}

数据结构与算法系列之习题练习
数据结构与算法系列之习题练习文章来源地址https://www.toymoban.com/news/detail-514664.html

到了这里，关于数据结构与算法系列之习题练习的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】第二章课后练习题——线性结构

    【数据结构】第二章课后练习题——线性结构

    1、线性表是 一个有限序列，可以为空 2、链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用 单循环链表 存储方式最节省运算时间 3、若某线性表中最常用的操作实在最后一个元素之后插入一个元素和删除第一个元素，则采用 仅有尾结点的

    2024年02月07日
    浏览(59)
  • 【数据结构】“单链表”的练习题

    【数据结构】“单链表”的练习题

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 ：阿然成长日记 👈点击可跳转 📆 个人专栏： 🔹数据结构与算法🔹C语言进阶 🚩 不能则学，不知则问，耻于问人，决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 题目要求: 给你单链

    2024年02月14日
    浏览(37)
  • 数据结构——二叉树练习题

    数据结构——二叉树练习题

    目录 单值二叉树  相同的树  另一棵树的子树 二叉树的前序遍历  二叉树的构造及遍历 给大家推荐一款刷题，找工作的好网站——牛客网 牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网   思路：根节点跟左子树比较，若相等则继续比，一

    2024年02月11日
    浏览(41)
  • 力扣（LeetCode）数据结构练习题（2）

    力扣（LeetCode）数据结构练习题（2）

    今天又写了两道关于链表的练习题，来给大家分享一下。巩固一下上一篇学到的链表知识，题目可以然我们更清楚的认识链表。 目录 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表 给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中

    2024年02月21日
    浏览(55)
  • 【数据结构（四）】链表经典练习题

    【数据结构（四）】链表经典练习题

    ❣博主主页: 33的博客❣ ▶️文章专栏分类:数据结构◀️ 🚚我的代码仓库: 33的代码仓库🚚 🫵🫵🫵 关注我带你学更多数据结构知识 在上一篇文章中博主已经介绍了链表的基础知识，什么是链表，如何实现一个链表，以及LinkedList的操作方法，那么在这篇文章中通过一些链

    2024年04月22日
    浏览(45)
  • 【数据结构】“单链表”的练习题（二）

    【数据结构】“单链表”的练习题（二）

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 ：阿然成长日记 👈点击可跳转 📆 个人专栏： 🔹数据结构与算法🔹C语言进阶 🚩 不能则学，不知则问，耻于问人，决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 前言： 最近在刷题的

    2024年02月13日
    浏览(47)
  • 【数据结构】“单链表”的练习题（一）

    【数据结构】“单链表”的练习题（一）

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 ：阿然成长日记 👈点击可跳转 📆 个人专栏： 🔹数据结构与算法🔹C语言进阶 🚩 不能则学，不知则问，耻于问人，决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 题目要求: 给你单链

    2024年02月12日
    浏览(51)
  • 数据结构之链表练习与习题详细解析

    数据结构之链表练习与习题详细解析

    个人主页：点我进入主页 专栏分类：C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶 欢迎大家点赞，评论，收藏。 一起努力，一起奔赴大厂。 目录 1.前言 2.习题解析 2.1习题一 2.2习题二 2.3习题三 2.4习题四 2.

    2024年02月05日
    浏览(45)
  • 【数据结构】顺序表详解（附leetcode练习题）

    【数据结构】顺序表详解（附leetcode练习题）

    ☃️个人主页：fighting小泽 🌸作者简介：目前正在学习C语言和数据结构 🌼博客专栏：数据结构 🏵️欢迎关注：评论👊🏻点赞👍🏻留言💪🏻 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺

    2023年04月27日
    浏览(48)
  • 【数据结构】时间复杂度---OJ练习题

    【数据结构】时间复杂度---OJ练习题

    目录 🌴时间复杂度练习 📌面试题---消失的数字 题目描述 题目链接：面试题 17.04. 消失的数字 🌴解题思路 📌思路1： malloc函数用法  📌思路2： 📌思路3： 🙊 如果有不了解时间复杂度的请移步上一篇文章：【数据结构】初识 题目描述 数组 nums 包含从 0 到 n 的所有整数，

    2024年02月16日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包