文档章节

《数据结构》第3章-栈与队列的学习总结

o
 osc_w9s1w4o0
发布于 2019/03/31 12:03
字数 1804
阅读 17
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

  我之前有接触过栈和队列,当时就觉得很好奇,那是以怎样的存储结构存储数据的呢?拨开重重迷雾,终于学到基础知识了。

  学习《栈和队列》有两个星期了,有了前面两个章节的思维基础,我觉得栈和队列学习起来还是很好理解的,通过一些实际应用例子,让我有了更进一步的理解。现在我梳理一下知识,下面总结这一章我所学习到的东西。

一、栈(后进先出:LIFO)

 1、顺序栈

这是顺序栈的存储结构:

typedef struct
{
  int *base;//栈底指针
  int *top; //栈顶指针
  int size; //栈容量            
}SqStack;

 

  开始栈底、栈顶指针都为空,之后随着元素的插入,还有栈的特性(只能在栈顶插入删除),base始终指向栈底位置,而top则加1,指向栈顶元素的上一个。对于顺序栈的基本操作,我觉得跟前面顺序表差不多,只需要在栈顶操作,好像更简单些。

  我无意中发现自己现在更喜欢链式存储结构,可能是以前觉得链式比顺序复杂,而学习之后觉得链式更有趣,它的抽象逻辑结构如果捋清楚,就使我豁然开朗,也是这也是一种乐趣吧。

 2、链栈

链栈示意图

这张图很好表示了链栈的存储结构,老师分析,链栈没必要设头结点,因为在这里对于链栈插入删除,只需要在栈顶操作最方便,初始化时直接将头指针置空就行。

//---------链栈存储结构--定义
typedef struct stacknode
{
  int data;  //数据域
  struct stacknode *next; // 指针域   
}stacknode,*linkstack;


1、初始化
void initstack(linkstack &S)
{
  S=NULL;//构造空栈S.栈顶指针置空    
}

2、入栈
void push(linkstack &S,int e)
{
  stacknode p;    //定义变量
  p=new stacknode;//申请变量空间,生成新结点
  p->data=e;    //将数据给新结点
  p->next=S;    //新结点插入栈顶
  S=p;       //修改栈顶指针为p
}

3、出栈
void pop(linkstack &S,int &e) //删除栈顶元素
{
  if(S==NULL) //判断是否栈空
  e=S->data; //栈顶元素数据赋给e
  p=S;    //用p保存栈顶空间,以备释放
  S=S->next;   // 修改栈顶指针
  delete p;      //释放原栈顶空间
}

4、取栈顶元素
int gettop(linkstack &S)
{
  if(S!=NULL)
   return S->data;
}

以上这些代码只是各自的算法,我在打的时候也在思考这一句代码的作用是什么,老师也强调注释的重要性,在这个过程中有时就是找出Bug的关键一步,我在自己做题目的时候或者跟同学讨论时确实感受到注释是检查程序的一个工具。

  我认为我们老师说的很有道理,一个程序的编写,首先要考虑它的逻辑结构,这也是数据结构这门课的关键,其次是算法,最后是存储结构。

比如,我在做PTA上面括号匹配题目时,开始就明确要用线性结构栈,算法我是参考一下课本案例里面,然后用链式存储结构。

二、队列(先进先出:FIFO)

 1、顺序队列(循环队列)

  这种循环队列是为了解决“假溢出”,这是由队列特性:队尾入队,队头出队限制造成的,实现操作一个巧妙方法就是(Q.rear+1)%MAXSIZE==Q.front.

 2、链队

  《银行业务队列简单模拟》那道题,让我对链队有了更深的理解。

设某银行有A、B两个业务窗口,且处理业务的速度不一样,其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时,B窗口处理完1个顾客。给定到达银行的顾客序列,请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔,并且当不同窗口同时处理完2个顾客时,A窗口顾客优先输出。

 

输入格式:

 

输入为一行正整数,其中第1个数字N(≤1000)为顾客总数,后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务,为偶数的顾客则去B窗口。数字间以空格分隔。

 

输出格式:

 

按业务处理完成的顺序输出顾客的编号。数字间以空格分隔,但最后一个编号后不能有多余的空格。

 

输入样例:

8 2 1 3 9 4 11 13 15

输出样例:

1 3 2 9 11 4 13 15

#include<iostream>
using namespace std;

typedef struct qnode  //队列链式存储结构
{
    int data;
    struct qnode *next;
} qnode,*queue;

typedef struct
{
    queue front;//队头和队尾指针
    queue rear;
 } lqueue;
 
void initqueue(lqueue &q)
{    
    q.front=q.rear=new qnode;//生成新结点作为头结点,队头和队尾指向头结点
    q.front->next=NULL;//头结点指针域为空
}

void enqueue(lqueue &q,int e)
{
    qnode *p;//定义结构体指针,并申请变量空间
    p=new qnode;
    p->data=e;//把e存入新结点数据域
    p->next=NULL;q.rear->next=p;//尾指针指针域指向新结点,即插入队尾
    q.rear=p;//将p修改队尾指针
}

void dequeue(lqueue &q)
{
    
      qnode *p;
        p=q.front->next;//指向队头
        cout<<p->data;//出队
        q.front->next=p->next;    //将头结点指针域指向下一个元素
        if(q.rear==p) q.rear=q.front;//最后一个元素出队,将队尾指针指向头结点

    delete p;//释放p的空间
}


int main()
{
    lqueue P,Q;
    int D;
    initqueue(P);initqueue(Q);//初始化两个链队
    int i,j,k,m=0,n=0;
    cin>>j;
    for(i=0;i<j;i++)
    {
        cin>>D;
        if(D%2)//奇数时入队P
        {
            enqueue(P,D);
            m++;//记录奇数个数
        }
        if(D%2==0)//偶数时入队Q
        {
            enqueue(Q,D);n++;//记录偶数个数
        }
    
    }

    k=(m/2)>=n?m/2:n;//确定循环输出次数

    for(i=0;i<k;i++)
    {    
        if(m>1)//共有三种情况输出
        {
            if(n>0)//P出队2个,Q出队1个
            {
                    if(i!=0)cout<<" ";//第一次打印元素,前面不带空格
                    dequeue(P);cout<<" ";dequeue(P);cout<<" ";dequeue(Q);n--;m-=2;
            }
            if(n<=0)//P出队2个
                {
                    if(i!=0)cout<<" ";
                    dequeue(P);cout<<" ";dequeue(P);m-=2;
                }
            
        }
        else if(m==1) 
        {
            if(n>0)//P出队1个,Q出队1个
            {    if(i!=0)cout<<" ";
                dequeue(P);m--;cout<<" ";dequeue(Q);n--;
            }
            if(n<=0)//P出队1个
                {    
                    if(i!=0)cout<<" ";
                    dequeue(P);m--;n--;
                }
            
        } 
        else if(m==0&&n>0)//Q出队
        {    if(i!=0)cout<<" ";
            dequeue(Q);n--;
        }
     } 

    return 0;
    
} 

这就是我通过许多次debug之后的程序,在处理队列问题时候,我考虑了所有可能出现的情况,程序结构看起来很清晰,我想还有不足之处,可以优化。

在解决这道题目时候,在无数次修正错误,我从中可以明白许多问题,所以多打代码,多尝试、实践,学得会更明白。

上一周也学习到很多,接下来还是要坚持做题目,实践与知识结合,我想这样更加牢固,自己容易犯错误的点也不少,希望在以后学习中能够严谨一些。

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
数据结构(c语言版)代码

第1章 绪论 文档中源码及测试数据存放目录:数据结构▲课本算法实现▲01 绪论 概述 第一章作为绪论,主要介绍了数据结构与算法中的一些基本概念和术语。对于这些概念术语,我个人不推崇死记硬...

osc_set2m6wk
2019/01/07
2
0
《数据结构》课程考试大纲

《数据结构》课程考试大纲 一、考试科目概述 二、考试内容 三、考试方式与试卷结构 四、参考书目 一、考试科目概述 数据结构是计算机程序设计的重要理论技术基础,《数据结构》课程是一门专业...

osc_eoffv2le
06/27
10
0
数据结构C语言版严蔚敏课后答案

数据结构严蔚敏课后习题答案PDF下载 《数据结构》(C语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参数教材。 本书的前半部分从抽象数据类型的角度讨...

学习达人
06/14
0
0
数据结构C语言版严蔚敏课后答案

数据结构严蔚敏课后习题答案PDF下载 《数据结构》(C语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参数教材。 本书的前半部分从抽象数据类型的角度讨...

2020最新java面试题及答案
06/21
3
0
数据结构C语言版严蔚敏课后答案

数据结构严蔚敏课后习题答案PDF下载 《数据结构》(C语言版)是为“数据结构”课程编写的教材,也可作为学习数据结构及其算法的C程序设计的参数教材。 本书的前半部分从抽象数据类型的角度讨...

学习达人
06/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

VB语言基础重要知识点12

我们课程,我们做一些针对于考试的简要讲解。 一、有关考试的几个问题 首先,提问:考试最重要的是什么? 答案其实很简单:得分!!!!! 想要得分,就要做到基本的保存。 保存哪些文件呢?...

刘金玉编程
2019/10/30
5
0
全网最全JAVA、Python电子书!限时领取,过时不候!

给大家整理了最全的入门+进阶书籍!!! 免费领取,无套路! 加微信发送“电子书” 秒通过,秒发资源! 本文分享自微信公众号 - Python进击者(JAVAandPythonJun)。 如有侵权,请联系 supp...

kuls
01/16
18
0
原创356--免费还是付费

最近得有一个星期,被一个录屏软件(record it)烦到了,本来免费版可以无限制录制,只能720p,GIF不支持,高清不支持,没有剪辑功能。 之前调研了好几种,用起来还是这个方便,就一直用了。...

八音弦
04/24
14
0
数字IC技术讨论群,设计和验证、前端和后端,总有你感兴趣的话题。快满了,需要的抓紧加入。

本文分享自微信公众号 - 白山头讲IC(gray_mount)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。...

白山头
04/29
5
0
how to install mongodb in centos7

[root@xtwj88 ~]# cat /etc/yum.repos.d/mongodb-org-4.2.repo [mongodb-org-4.2]name=MongoDB Repositorybaseurl=https://repo.mongodb.org/yum/redhat/$releasever/mongodb-org/4.2/x86......

qwfys
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部