文档章节

【数据结构】第三章学习小结

o
 osc_w9s1w4o0
发布于 2019/03/30 23:10
字数 1423
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

第三章知识小结

一.栈(特点是后进先出--LIFO)

1.抽象数据类型(ADT)

ADT:stack

InitStack(Stack &S);

Push(Stack &S);

Pop(Stack &S);

2.按照存储结构可分为:顺序栈,链栈

顺序栈的类型定义:

const int MAXSIZE =100;

typedef int ElemType;/*类型视情况而定,这里定义为int */

typedef struct

{

ElemType data[MAXSIZE];

int top;/*栈顶标志*/

int stacksize;/*栈的最大容量*/

}Sqstack;

链栈的类型定义:

typedef struct StackNode

{

ElemType data;

struct StackNode *next;

}StackNode,*LinkStack;

栈与递归

递归:一个对象部分地包含它自己,换句话说,就是自己给自己定义。

每次递归都会保存的信息:1.返回地址2.参数值3.引用的局部变量

递归优缺点分析:

优点:结构清晰,程序易读

缺点:每次调用要生成工作记录,保存状态信息入栈,返回时要出栈,恢复状态信息,时间开销大

解决递归问题可以用分治法:

void p(参数表)

{

if(递归结束条件成立) 的解/*递归终止条件*/

 else p(较小的参数);/*递归步骤*/

二.队列(先进先出-FIFO,只允许在表的一端进行插入,而在另一端删除元素)

由于顺序队用的比较少,这里主要说说链栈

链队的类型定义:

typedef struct node{
ElemType data;
struct node *next;
}LNode;/*结点*/

typedef struct{
LNode *front;/*头指针*/

LNode *rear;/*尾指针*/
}LinkQueue;

 

在第三章里,我学到了两种重要的线性结构---栈和队列,两者都有顺序结构和链式结构的表达方式,相较于顺序结构,我更青睐于使用链栈和链队,因为顺序栈和顺序表一样,会受到最大空间容量的限制,要想扩大容量,需要的工作量是非常大的,我在上一章内容就学到了,链式结构在进行插入与删除操作时,能省去很大一部分不必要的操作。对于链栈来说,没有必要设置头结点,直接将栈顶置空就行。入栈时直接为入栈的元素分配空间,不需要判断栈满。出栈时需要释放出栈元素的栈顶空间。(尝试过不加这一操作,好像对程序影响不大)

对于链队,我一般都会构造一个带有头结点的空队,并将队尾指针的队头指针都指向该头结点,入队的时候只需为入队的元素分配结点空间,并设置一个指针p指向该结点,将队尾指针修改为p,链队在出队时需要特别注意的是,当队列最后一个元素被删除时,队列尾指针会丢失,这时候需要对队尾指针重新赋值,即将队尾指针指向头结点

完成作业时遇到的困难:

1.在做pta上的实践题时,花了好几天时间DeBug,将一些自己因为粗心打漏几个字符造成的问题解决后,自己在Dev上测试也没问题,就想这一次在pta提交总该会一次过吧。没想到,前三个测试点都过得了,就是在最后一个最大N的时候挂掉了。

解决方法:尝试通过写注释和在关键变量后面设置输出语句,可惜未果。终于,在一次和同学分享自己的思路时,发现了一处疑点,原题目并没有要求将客户编号排好序,只是题目中给的样例让我产生了错觉,非得加一个排序函数。将排序函数删掉后在提交一次,竟然过了!(好几天的疯狂找Bug,竟是因为这小小的细节,果然是细节决定成败)

刻苦铭心的教训:一定要先看清楚题目再做题呀!

2.在做到括号匹配这个问题时,一开始我是参考了书上的例题的代码,定义了一个char型变量来存储字符串,但是这种方法每次只能读入一个字符。

之后在调试的过程中,我又遇到了系统报错,内容是swich语句里的参数必须是一个整型变量。

解决方法:1.果断抛弃只用一个CHAR型变量的方法,改用字符数组(之后可以循环读取数组里的字符)

                  2.将输入的字符统一转化为ASCII码(即为整型变量)

void Match()/*判断输入的一段字符串中所包括的符号是否匹配,如果匹配,输出"yes", 否则输出"no"*/ 
{  
    int length;
    LinkStack S;
    InitStack( S);/*初始化空栈*/ 

    char ch[MAXSIZE];
    cin.getline(ch,MAXSIZE);
    length=strlen(ch);/*获得输入字符串的长度*/ 
    int flag=1;/*标记匹配结果并返回结果*/ 

    for(int i=0;i<length;i++)
    { 
        int temp;/*将字符转化为ASCII码*/ 
        temp=(int)ch[i];
    
        switch(temp)
        {
            case 91:/*"["的ASCII码*/ 
            case 40:/*"("的ASCII码*/ 
            case 123:/*"{"的ASCII码*/ 
            Push(S,temp);/*若是左括号,入栈*/ 
            break;
        case 93 :
            if(!StackEmpty(S)&&GetTop(S)==91) Pop(S);/*若栈非空且符号匹配,则栈顶出栈*/ 
            else flag=0;/*反之,返回0*/ 
            break;
        case 41:
            if(!StackEmpty(S)&&GetTop(S)==40) Pop(S);
            else flag=0;
            break;
        case 125:
            if(!StackEmpty(S)&&GetTop(S)==123) Pop(S);
            else flag=0;
            break;
        }
    }

参考资料:https://www.cnblogs.com/Draymonder/p/6944479.html

                https://blog.csdn.net/qq_39091609/article/details/76618628

目前学习中存在的问题:①不够细心,对题目的理解能力还有所不足

                                      ②不能通过写注释来发现自己代码中存在的问题

接下来的目标:周末认真复习,迎接下周的小测,继续坚持打代码

 

 

 

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
191027时间安排

总结我前几次的安排,太相信自己,过于自信,忘记了自己已不是从前的自己,一下子跨越太大,导致自己这几天焦虑,然而忘记了我还有完完整整的一年,眼光短浅。进而导致学习效率不增反倒低了很...

osc_8vi0tf3q
2019/10/27
2
0
20175215 2018-2019-2 第二周java课程学习总结

###一、学生免费申请使用IDEA下载好IDEA后,设置到最后有一个界面,我们需要到IDEA官网进行IDEA免费试用权的申请,如果有学校的邮箱,使用学校的邮箱注册并证明是自己的就可以直接通过申请。...

osc_6ogjsu3t
2019/03/05
1
0
【数据结构】链式存储——定义

前言   接着上篇博文的介绍,本篇文章我们介绍链式存储下,数据逻辑结构的定义,本文仍然会以线性表为例。 实例 1. 线性表 2. 栈 3. 队列 异同点 (一)同: 通过上面实例的代码,我们可以...

写一封信
04/01
0
0
力学第三版 张汉壮 课后答案 第3版 力学答案

张汉壮 王文全力学第三版习题答案 第3版 力学课后习题详解答案 本书是根据《高等学校物理学本科指导性专业规范》以及《高等学校物理学专业类本科国家标准》的要求,参考国内外多部优秀教材,...

java问道
前天
0
0
力学第三版 张汉壮 课后答案 第3版 力学答案

张汉壮 王文全力学第三版习题答案 第3版 力学课后习题详解答案 本书是根据《高等学校物理学本科指导性专业规范》以及《高等学校物理学专业类本科国家标准》的要求,参考国内外多部优秀教材,...

开源节流1
07/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如何删除使用Python的easy_install安装的软件包? - How do I remove packages installed with Python's easy_install?

问题: Python's easy_install makes installing new packages extremely convenient. Python的easy_install使安装新包非常方便。 However, as far as I can tell, it doesn't implement th......

fyin1314
8分钟前
0
0
如何将逗号分隔的字符串转换为数组? - How to convert a comma separated string to an array?

问题: I have a comma separated string that I want to convert into an array, so I can loop through it. 我有一个逗号分隔的字符串,我想将其转换成数组,因此可以循环遍历它。 Is the...

富含淀粉
38分钟前
13
0
深源恒际:担心个人身份被冒用?不存在!

本文作者:c****t 近日,苟晶被冒名顶替身份参加高考的事件在社会各界掀起广泛热议。事件调查结果公布后,舆论风向逆转,吃瓜群众认为当事人夸大其词消费了公众情绪,一边对当事人所遭遇的不...

百度开发者中心
昨天
5
0
CKEditor 5 + SpringBoot实战(三):SpringData JPA数据持久化

在本系列的文章中,我将介绍如何在Spring Boot Application中使用CKEditor编辑器。介绍的内容包括基本环境的搭建,文件上传,SpringData JPA数据持久化,CKEditor5的安装,CKEditor图片上传,...

树下魅狐
今天
9
0
Confluence 如何查看页面 ID

如果你希望查看页面的 ID 你有 2 个方法。 例如,你希望查看 https://www.cwiki.us/display/CONFLUENCEWIKI/Get+started 页面的 Page ID 的话。 如果你的标题栏没有特殊字符,那么将会使用英...

honeymoose
今天
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部