当前位置: 首页 > news >正文

网络运维工程师证关键词优化怎么弄

网络运维工程师证,关键词优化怎么弄,厦门网站推广公司,网站建设自学需要多久文章目录 栈的三要素逻辑结构(定义)数据的运算(基本操作)存储结构(物理结构)顺序栈(顺序存储)链栈(链式存储) 队列的三要素逻辑结构(定义&#xf…

文章目录

  • 栈的三要素
    • 逻辑结构(定义)
    • 数据的运算(基本操作)
    • 存储结构(物理结构)
      • 顺序栈(顺序存储)
      • 链栈(链式存储)
  • 队列的三要素
    • 逻辑结构(定义)
    • 数据的运算(基本操作)
    • 存储结构(物理结构)
      • 顺序队列(顺序存储)
      • 链式队列(链式存储)
  • 队列的变种
  • 栈在括号匹配中的应用
  • 栈在表达式求值中的应用
    • 中缀表达式 ------>后缀表达式
    • 后缀表达式的计算
    • 中缀表达式 ------>前缀表达式
    • 前缀表达式的计算
    • 用栈实现中缀表达式的计算


栈的三要素

逻辑结构(定义)

栈是只允许在一端进行插入或删除操作的线性表

特点:后进先出(LIFO)

数据的运算(基本操作)

InitStack(&S)
初始化栈:构造一个空栈S,分配内存空间DestroyStack(&S)
销毁栈:销毁并释放栈S所占用的内存空间Push(&S,x)
进栈:若栈S未满,则将x加入使之成为新栈顶Pop(&S,&x)
出栈:若栈非空,则弹出栈顶元素,并用x返回GetTop(S,&x)
读栈顶元素:若栈S非空,则用x返回栈顶元素StackEmpty(S)
判断一个栈S是否为空,若S为空,则返回true,否则返回false

栈的常考题型
已知进栈顺序,问有哪些合法的出栈顺序?
出栈元素不同排列的个数为卡特兰数

存储结构(物理结构)

顺序栈(顺序存储)

顺序栈的定义

#define MaxSize 10
typedef struct{ELemType data[MaxSize];   // 静态数组存放栈中元素int top;                  // 栈顶指针
}SqStack;

初始化栈

void InitStack(SqStack &S){S.top = 0;
}

判空

bool StackEmpty(SqStack S){if(S.top == -1)return true;elsereturn false;
]

进栈操作

bool Push(SqStack &S,ElemType x){if(S.top == MaxSize - 1)renturn false;S.top = S.top + 1;   // 指针先加1S.data[S.top] = x;   // 新元素入栈return true;
}

出栈操作

bool Pop(SqStack &S, ElemType &x){if(S.top == -1)return false;x = S.data[S.top];S.top = S.top - 1;return true;
}

读栈顶元素

bool GetTop(SqStack S, ElemType &x){if(S.top == -1)return false;x = S.data[S.top];return true;
|

共享栈

#define MaxSize 10
typedef struct{ElemType data[MaxSize];int top0;      // 0号栈栈顶指针int top1;      // 1号栈栈顶指针
} ShStack;// 初始化栈
void InitStack(ShStack &S){S.top0 = -1;S.top1 = MaxSize;
}

栈满的条件: top0 + 1 = top1

链栈(链式存储)

链栈的定义
其操作相当于头插法建立单链表(只从表头进行增加删除操作)

typedef struct LinkNode{ELemType data;   // 数据域struct LinkNode *next;     // 指针域
}*LinkStack;

队列的三要素

逻辑结构(定义)

队列是只允许在一端进行插入,在另一端删除的线性表

特点:先进先出(FIFO)

数据的运算(基本操作)

InitQueue(&Q)
初始化队列:构造一个空队列QDestroyQueue(&Q)
销毁队列:销毁并释队列Q所占用的内存空间EnQueue(&Q,x)
入队:若队列Q未满,则将x加入使之成为新的队尾DeQueue(&Q,&x)
出队:若队列非空,删除队头元素,并用x返回GetHead(Q,&x)
读队头元素:若队列Q非空,则用x返回队头元素QueueEmpty(Q)
判断一个队列Q是否为空,若Q为空,则返回true,否则返回false

存储结构(物理结构)

顺序队列(顺序存储)

队列的顺序实现

#define MaxSize 10
typedef struct{ElemType data[MaxSize];int front,rear;
} SqQueue;

初始化队列

void InitQueue(SqQueue &Q){Q.rear = Q.front = 0;
}

判断队列是否为空

bool QueueEmpty(SqQueue Q){if(Q.rear == Qfront)return true;elsereturn false;
}

入队

bool EnQueue(SqQueue &Q,ElemType x){if((Q.rear + 1) % MaxSize == Q.front)return false;    //队满则报错Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MaxSize;  //队尾指针加一取模return true;
} 

出队

bool DeQueue(SqQueue &Q,ElemType &x){if(Q.rear == Q.front)return false;   // 队空则报错x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;return true;
}

获取队头元素的值,用x返回

bool GetHead(SqQueue Q,ElemType &x){if(Q.rear == Q.front)return false;x = Q.data[Q.front];return true;
}

队列元素的个数:
(rear - front + MaxSzie)% MaxSize

链式队列(链式存储)

队列的链式实现

typedef struct LinkNode{    // 链式队列结点ElemType data;  struct LinkNode *next;
}LinkNode;typedef struct{             // 链式队列LinkNode *front,*rear;  // 队列的队头和队尾指针
}LinkQueue;

初始化(带头结点)

void InitQueue(LinkQueue &Q){// 初始化 front、rear 都指向头结点Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));Q.front->next = NULL;
}

队列是否为空

bool IsEmpty(LinkQueue Q){if(Q.rear == Qfront)return true;elsereturn false;
}

新元素入队(带头结点)

void EnQueue(LinkNode &Q,ElemType x){LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));s->data = x;s->next = null;Q.rear->next = s;Q.rear = s;
}

在这里插入图片描述

入队(不带头结点)

void EnQueue(LinkQueue &Q,ElemType x){LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));s->data = x;s->next = NULL;if(Q.front == NULL){   // 在空队列中插入第一个元素Q.front = s;       // 修改队头队尾的指针Q.rear = s;} else{Q.rear->next = s;Q.rear = s;}
}

出队(带头结点)

bool DeQueue(LinkQueue &Q,ElemType &x){if(Q.front == Q.rear)return false;    // 空队LinkNode *p = Q.front->next;x = p.data;Q.front->next = p->next;if(Q.rear == p)   // 此次是最后一个结点出队Q.rear = Q.front;free(p);          // 释放结点空间return true;
}

出队(不带头结点)

bool DeQueue(LinkQueue &Q,ElemType &x){if(Q.front == NULL)return false;LinkNode *p = Q.front;x = p->data;Q.front = p->next;if(Q.rear = p)[Q.front = NULL;Q.rear = NULL;}free(p);return true;
}

队列的变种

双端队列:允许从两端插入、两端删除的队列

输入受限的双端队列:允许从两端删除、从一端插入的队列

输出受限的双端队列:允许从两端插入、从一端删除的队列

考点:对输出序列的合法性的判断

栈在括号匹配中的应用

括号匹配流程图

代码实现

#define MaxSize 10
typedef struct{char data[MaxSize];int top;
}SqStack;// 初始化栈
void InitStack(SqStack &S)// 判断栈是否为空
bool StackEmpty(SqStack S)// 新元素入栈
bool Push(SqStack &S,char x)// 栈顶元素出栈,用x返回
bool Pop(SqStack &S,char &x)bool bracketCheck(char str[],int length){SqStack S;InitStack(S);  // 初始化for(int i = 0; i < length; i++){if(str[i] == '(' || str[i] == '[' || str[i] == '{'){Push(S, str[i]);  // 扫描到左括号,入栈} else {if(StackEmpty(S))  // 扫描到右括号,并且当前栈空return false;  // 匹配失败char topElem;Pop(S, topElem);   // 栈顶元素出栈if(str[i] == ')' && topElem != '(')return false;if(str[i] == ']' && topElem != '[')return false;if(str[i] == '}' && topElem != '{')return false;}}return StackEmpty(S);   // 检索完全部括号后,栈空说明匹配成功
} 

栈在表达式求值中的应用

三种算术表达式:
1、中缀表达式:运算符在两个操作数中间 —— a+b
2、后缀表达式(逆波兰表达式):运算符在两个操作数后面 —— ab+
3、前缀表达式(波兰表达式):运算符在两个操作数前面 —— +ab

中缀表达式 ------>后缀表达式

手算

1、确定中缀表达式中各个运算符的运算顺序
2、选择下一个运算符,按照【 左操作符 右操作符 运算符 】的方式组合成一个新的操作数
3、如果还有运算符没被处理,就继续2
注意:为了保证手算和机算结果相同,采用“左优先”原则:只有左边的运算符能先运算,就优先算左边(可保证运算顺序唯一)

机算

初始化一个栈,用于保存暂时还不能确定运算顺序的运算符
从左到右处理各个元素,直到末尾,可能遇到三种情况:
1、遇到操作数:直接加入后缀表达式
2、遇到界限符:遇到 “ ( ” 直接入栈,遇到 “ ) ” 则依次弹出栈内运算符并加入后缀表达式,直到弹出 “ ( ” 为止。注意:“ ( ” 不加入后缀表达式
3、遇到运算符:依次弹出栈中优先级高于或者等于当前运算符的所有运算符,并加入后缀表达式,若碰到 “ ( ” 或栈空则停止。之后再把当前的运算符入栈
4、处理完所有字符后,将栈中剩余运算符依次弹出,并加入后缀表达式

后缀表达式的计算

1、从左往右扫描下一个元素,直到处理完所有的元素
2、若扫描到操作数则压入栈,并回到1;否则执行3
3、若扫描到运算符,则弹出两个栈顶元素,执行相应运算(先出栈的是右操作数),运算结果压回栈顶,回到1
4、若表达式合法。则最后栈中只会留下一个元素,就是最终结果

中缀表达式 ------>前缀表达式

1、确定中缀表达式中各个运算符的运算顺序
2、选择下一个运算符,按照【 运算符 左操作符 右操作符 】的方式组合成一个新的操作数
3、如果还有运算符没被处理,就继续2
注意:为了保证手算和机算结果相同,采用“右优先”原则:只有右边的运算符能先运算,就优先算右边(可保证运算顺序唯一)

前缀表达式的计算

1、从右往左扫描下一个元素,直到处理完所有的元素
2、若扫描到操作数则压入栈,并回到1;否则执行3
3、若扫描到运算符,则弹出两个栈顶元素,执行相应运算(先出栈的是左操作数),运算结果压回栈顶,回到1
4、若表达式合法。则最后栈中只会留下一个元素,就是最终结果

用栈实现中缀表达式的计算

中缀表达式 ------>后缀表达式后缀表达式的计算 的结合

*初始化两个栈:操作数栈 和 运算符栈
若扫描到操作数,压入操作数栈
若扫描到运算符或者界限符,则按照“中缀转后缀”相同的逻辑压入运算符栈
每当弹出一个运算符时,就需要在弹出两个操作数栈的栈顶元素并执行相应的运算,运算结果再压回操作数栈中

http://www.dt0577.cn/news/16108.html

相关文章:

  • idc数据中心河北百度竞价优化
  • 网站要怎么做的吗湖南网络营销外包
  • 怎么做简单的企业网站沪深300指数基金排名
  • 网站开发的过程中遇到的难题如何做google推广
  • 保定网站建设冀icp企业推广公司
  • 网站开发与编程的区别最近的新闻事件
  • 网页制作怎么做多个网站建立网站用什么软件
  • 连云港网站建设公司快手作品推广网站
  • wordpress 防复制seo专员工作容易学吗
  • 网页编辑如何添加图片seo网络公司
  • 霸州做网站怎么创建网站平台
  • 做视频网站用哪个软件好网店运营入门基础知识
  • 做代购可以在哪些网站上百度百家号怎么赚钱
  • 网站建设 郑州一键优化清理加速
  • 织梦网站维护深圳百度推广属于哪家公司
  • 福田附近做网站公司发布软文的平台有哪些
  • wordpress标签文章列表seo案例分析
  • 好网站建设网站seo刷排名公司
  • 谁用腾讯风铃做网站的app营销模式有哪些
  • wordpress eva lovia黑帽seo什么意思
  • 网页设计师网站大全h5下一页
  • 一个门户网站需要多大的空间百度首页排名优化公司
  • 潍坊专业网站建设最新报价武汉官网优化公司
  • 太原企业网站搭建太原seo建站
  • 网站入侵怎么做信息如何优化上百度首页
  • 西安网站建设制作价格低长春网站建设 4435
  • 网站建设五大定位仿站定制模板建站
  • wordpress打开非常慢黄山网站seo
  • 如何在微信平台做购买网站百度云登录首页
  • 做网站怎么切psd图热搜榜上能否吃自热火锅