云南建设厅网站 安全员,无锡网站公司哪家好,网站空间购买时选择什么脚本语言,混合式教学财务管理网站建设文章目录 栈的三要素逻辑结构#xff08;定义#xff09;数据的运算#xff08;基本操作#xff09;存储结构#xff08;物理结构#xff09;顺序栈#xff08;顺序存储#xff09;链栈#xff08;链式存储#xff09; 队列的三要素逻辑结构#xff08;定义#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、中缀表达式运算符在两个操作数中间 —— ab 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、若表达式合法。则最后栈中只会留下一个元素就是最终结果 用栈实现中缀表达式的计算
中缀表达式 ------后缀表达式 与 后缀表达式的计算 的结合 *初始化两个栈操作数栈 和 运算符栈 若扫描到操作数压入操作数栈 若扫描到运算符或者界限符则按照“中缀转后缀”相同的逻辑压入运算符栈 每当弹出一个运算符时就需要在弹出两个操作数栈的栈顶元素并执行相应的运算运算结果再压回操作数栈中
