想学做网站学什么教程,广东建设项目备案公示网站,网站动图怎么做,注册一个公司需要多久栈与队列
栈Stack
后进先出
栈的结构体定义及基本操作。
#define MaxSize 50
typedef struct {int data[MaxSize];//栈中存放数据类型为整型int top;//栈顶指针
}Stack;初始化
这里初始化时是将栈顶指针指向-1#xff0c;有些则是指向0#xff0c;因此后续入栈出栈…栈与队列
栈Stack
后进先出
栈的结构体定义及基本操作。
#define MaxSize 50
typedef struct {int data[MaxSize];//栈中存放数据类型为整型int top;//栈顶指针
}Stack;初始化
这里初始化时是将栈顶指针指向-1有些则是指向0因此后续入栈出栈的代码略微有点区别
void InitStack(Stack S) {//初始化栈S.top -1;
}判断栈是否为空
int IsEmpty(Stack S) {//判断栈是否为空if (S.top -1)return 1;elsereturn 0;
}压栈操作
由于初始时栈顶指针指向-1因此需要先变化栈顶指针然后入栈操作且当MaxSize为50时候数据域在data[0]~data[49]因此这里是S.top MaxSize - 1表示栈满第4-5行可以合并为S.data[S.top]x。
int Push(Stack S, int x) {//压栈操作if (S.top MaxSize - 1)//若栈满则无法压栈return 0;S.top;S.data[S.top] x;return 1;
}出栈操作
这里将出栈的元素用x接收出栈时先接收然后栈顶指针自减第4-5行可以合并为xS.data[S.top]
int Pop(Stack S, int x) {//出栈操作if (S.top -1)//若栈空则无法出栈return 0;x S.data[S.top];S.top--;return 1;
}读取栈顶元素
这里将出栈的元素用x接收
int GetTop(Stack S, int x) {//读取栈顶元素if (S.top -1)//若栈空则无栈顶元素return 0;x S.data[S.top];return 1;
} 当然以上的是顺序栈还有链栈和单链表类似带头结点处为栈头另外一边为栈底入栈出栈都在头结点处进行方便操作。
01 有一个带头结点的单链表 L结点结构由 data 和 next 两个域构成其中data 域为字符型。试设计算法判断该链表的全部 n 个字符是否中心对称。例如xyx、xyyx 都是中心对称。
判断这类是否中心对称一般都是用到栈本题中将其分为前后两部分把前半部分依次入栈到后半部分时与出栈元素进行比较比较完后栈顶指针移动。遍历指针移动易错for循环入栈结束后i所在的位置在栈顶元素的后一个位置需要i–将其返回到栈顶位置结点个数为偶数时正常处理个数为奇数时最中间元素不将其压栈处理让遍历指针再走一步绕过中间元素
int central_symmetry(LinkList L, int n) {char S[n / 2];//定义字符型数组来作为一个栈int i;//定义栈顶指针LNode* p L-next;//定义遍历指针//对称轴左边字符依次入栈for (i 0; i n / 2; i) {S[i] p-data;p p-next;}i--;//变量 i 返回栈顶位置if (n % 2 1) {//若字符数为奇数则 p 向后遍历一步因为最中间字符不需考虑p p-next;}while (p ! NULL) {//对称轴右边字符依次与栈顶元素比对if (p-data S[i]) {//与栈顶元素相等则 p 继续遍历与下一出栈元素比较i--;//出栈p p-next;//继续遍历}else//若不等则说明 n 个字符不对称直接返回 0return 0;//非中心对称}return 1;//若正常跳出循环则证明 n 个字符对称返回 1
}02 假设一个算术表达式中包含小括号和中括号 2 种类型的括号编写一个算法来判别表达式中的括号是否配对假设算术表达式存放于字符数组中以字符‘\0’作为算术表达式的结束符。
本题中对于数字和运算符不需要进行操作switch语句从上往下依次执行因此需要break跳出遇到右括号时候首先得判断栈是否为空为空则说明不匹配了若数组遍历完成后栈为空则证明所有左括号全部配对成功
int BracketsCheck(char a[]) {Stack S;InitStack(S);char x;for (int i 0; a[i] ! \0; i) {switch (a[i]) {case(://若数组元素为左括号则压栈继续遍历push(S, a[i]);break;case[:push(S, a[i]);break;case)://若元素为右括号则需考虑是否有左括号与之配对if (IsEmpty(S) {return 0;//若栈空则说明无左括号与之配对}else {Pop(S, x);if (x ! () {//若栈不为空则判断栈顶元素与当前括号是否配对return 0;}//配对上了break;}case]:if (IsEmpty(S)) {return 0;}else {Pop(S, x);if (x ! [) {return 0;}break;}default://若数组元素不是括号则直接继续遍历break;}}if (IsEmpty(S)) {//若数组遍历完成后栈为空则证明所有左括号全部配对成功return 1;}else {//若栈不为空则证明有左括号未配对retun 0;}
}03 两个栈 S1、S2 都采用顺序栈方式并共享一个存储区[0,…,MaxSize-1]为了尽量利用空间减少溢出的可能可采用栈顶相向、迎面增长的存储方式。试设计写出此栈的定义和 S1、S2 有关入栈和出栈的操作算法。
两个栈需要两个栈顶指针这里定义了top数组一个top[0]一个top[1]
#define MaxSize 50
typedef struct{int data[MaxSize];int top[2];//一个top[0]一个top[1]指针
}DStack;初始化
void InitDStack(DStack S) {S.top[0] -1;//初始化 S1 栈顶指针S.top[1] MaxSize;//初始化 S2 栈顶指针
}入栈
因为一个存储空间有两个栈因此需要告诉是对哪个栈进行入栈操作i就是用来区分哪个栈这里S[1]表示下面的栈S[2]表示上面的栈
int push(int i, int x) {if (i 0 || i1) {return 0;//若 i 的输入不合法则无法入栈}if (S.top[1] - S.top[0] 1) {//若存储空间已满则无法进行入栈操作return 0;}switch (i) {case 0:// S1 栈顶指针上移后入栈S.top[0];S.data[S.top[0]] x;//S.data[S.top[0]] x;break;case 1:// S2 栈顶指针下移后入栈S.top[1]--;S.data[S.top[1]] x;//S.data[--S.top[1]] x;break;}return 1;
}出栈
int pop(int i, int x) {if (i 0 || i1) {return 0;}if (S.top[0] -1 || S.top[1] MaxSize) {//空栈return 0;}switch (i) {case 0:x S.data[S.top[0]];S.top[0]--;//下面的栈往下移//x S.data[S.top[0]--];break;case 1:x S.data[S.top[1]];S.top[1];//上面的栈顶指针往上移//x S.data[S.top[1]];break;}return 1;
}队列Queue
先进先出
队列的结构体定义及其基本操作。
#define MaxSize 50
typedef struct {int data[MaxSize];//队列中存放数据类型为整型int front, rear;//队首指针和队尾指针
}Queue;
void InitQueue(Queue Q) {//初始化队列Q.front 0;Q.rear 0;
}
int IsEmpty(Queue Q) {//判断队列是否为空if (Q.front Q.rear)//若队首指针和队尾指针指向同一位置则队列为空return 1;elsereturn 0;
}队列的入队和出队
这里队尾指针指向元素的后一个位置详见入队出队操作
入队争对的是队尾指针需要判断队满Q.rear MaxSize
//顺序队列的入队和出队
//这里队尾指针指向元素的后一个位置
int EnQueue(Queue Q, int x) {//入队操作if (Q.rear MaxSize)//若队满则无法入队return 0;Q.data[Q.rear] x;//变量 x 入队Q.rear;//队尾指针后移return 1;//入队成功
}
出队争对的是队头指针需要判断队空Q.front Q.rear
int DeQueue(Queue Q, int x) {//出队操作if (Q.front Q.rear)//若队空则无法出队return 0;x Q.data[Q.front];//变量 x 接收出队元素Q.front;//队首指针后移return 1;//出队成功
}循环队列
由于之前Q.front Q.rear判断队空若循环则既有判空又有存满的意思因此可以牺牲一个空间使得Q.front Q.rear只能用来判空。
判空Q.front Q.rear
判满(Q.rear 1) % MaxSize Q.frontrear向后移一个是front的话说明满了
队尾指针和队首指针往后移动的时候都需要1取余
//循环队列的入队和出队牺牲一个存储空间
int EnQueue(Queue Q, int x) {//入队操作if ((Q.rear 1) % MaxSize Q.front)//若队满则无法入队return 0;Q.data[Q.rear] x;//变量 x 入队Q.rear (Q.rear 1) % MaxSize;//队尾指针后移return 1;//入队成功
}
int DeQueue(Queue Q, int x) {//出队操作if (Q.front Q.rear)//若队空则无法出队return 0;x Q.data[Q.front];//变量 x 接收出队元素Q.front (Q.front 1) % MaxSize;//队首指针后移return 1;//出队成功
}04 若希望循环队列中的元素都能得到利用则需设置一个标志域 tag并以tag的值为0或1来区分队头指针front和队尾指针rear相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队和出队算法。
循环队列中Q.front Q.rear在原先是能判断队空和队满因此上面牺牲一个空间进行特别处理本题通过设置标志域来判断是队空还是队满这里需要判断队满的只有入队的时候因此每次入队后将tag变成1需要判断队空的只有出队的时候因此每次出队后将tag变成0由于队空队满判断都需要进行Q.front Q.rear的判断因此因此当队首队尾指针不在同一个地方时候不会进入这个判断初始时应该将tag置为0。Q.front Q.rear Q.tag 1和Q.front Q.rear Q.tag 0的条件下挺强的都是需要两个条件同时满足
typedef struct {int data[MaxSize];int front, rear;int tag;
}Queue;
void InitQueue(Queue Q) {//初始化队列Q.front 0;Q.rear 0;Q.tag 0;
}
int EnQueue(Queue Q, int x) {if (Q.front Q.rear Q.tag 1) {//若队满则无法进行入队操作return 0;}Q.data[Q.rear] x;Q.rear (Q.rear 1) % MaxSize;//队尾指针后移Q.tag 1;//入队后可能会出现队满的情况所以将 tag 标志域置为 1return 1;
}
int DeQueue(Queue Q, int x) {if (Q.front Q.rear Q.tag 0) {return 0;//队空}x Q.data[Q.front];Q.front (Q.front 1) % MaxSize;Q.tag 0;//出队后可能会出现队空的情况所以将 tag 标志域置为 0return 1;
}05 Q 是一个队列S 是一个空栈实现将队列中的元素逆置的算法。
队列先进先出栈后进先出要将队列中元素逆置因此可以依次将队列的元素出队入栈当队列为空时然后出栈入队就实现了逆置。
//Q 是一个队列S 是一个空栈实现将队列中的元素逆置的算法。
void Reverse(Queue Q, Stack S) {int x;while (!IsEmpty(Q)) {//出队列入栈DeQueue(Q, x);Push(S, x);}while (!IsEmpty(S)) {//出栈入队列Pop(S, x);EnQueue(Q, x);}
}
