8种机械键盘轴体对比
本人程序员，要买一个写代码的键盘，请问红轴和茶轴怎么选？
实验目的与要求
实验步骤与内容
问题与说明
备注
程序清单
实验目的与要求
1.了解栈的逻辑结构
2.熟悉各种方法构建栈
3.实现栈的基本操作
4.实现栈的应用
实验步骤与内容
栈(stack)由两个端点栈顶(top)和栈底(bottom)构成，遵循“先进后出”(FILO)或“后进先出”(LIFO)的规则，即只允许在一端插入或删除元素。
栈的ADT：1
2
3
4
5ADT stack{
数据对象:D={ai|ai∈ElemSet,i=1,2,..,n , n≥0);
数据关系:R={|ai-1,a∈D,i=2,3,..,n};
基本操作:初始化，进栈，出栈，取栈顶元素，判断栈空、栈满等
}ADT stack
栈的顺序存储结构
简称顺序栈，使用一维数组来储存，根据使用环境的不同又分为:静态顺序栈
动态顺序栈
栈的应用数制转化
在2,,8,10进制间转化，遵循n = (n div d) * d + n mod d,出数的顺序是由低位到高位，所以用栈来储存数据，计算完成后弹数即为正序。1
2
3
4
5
6
7
8
9
10
11
12
13
14void (int k,int d){
sqstack S;
int k,*e;
S=Init_stack();
while(n>0){
k=n%d;
push(S,k);
n=n/d;
}
while(S.top!=0){
pop(S,e);
printf("%d",*e);
}
}
括号匹配问题
读左括号入栈，当读到右括号时弹出元素与左括号匹配。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#define FALSE -1
sqstack S;
S=Init_stack();
int Match_Brackets(){
chat ch,x;
scanf("%c",&ch);
while(asc(cj)!=13){
if(ch=='('||ch=='[') push(S,ch);
else if(ch==']') {
x=pop(S);
if(x!='[') return FALSE;
}else if(ch==')'){
x=pop(S);
if(x!='(') return FALSE;
}
if(!S.top) return FALSE;
return TRUE;
}
}
递归调用
递归调用，一般遵循这样的规则:1
2F(n) = | 1 , n=0;
| n*F(n-1) , n>0
递归栈:
(1)栈为空则执行正常返回
(2)栈顶弹出一个工作记录
(3)赋值
(4)返回地址表达式求值
表达式由操作数，操作符和分界符构成。算术表达式分为三种分别是前缀表达式(infix)，中缀表达式(prefix)，后缀表达式(postfix)。所有表达式都遵循以下三个规则：1.优先级高的先计算；
2.优先级相同的从左向右计算；
3.括号从最内层开始计算。
对于中缀表达式我们需要两个栈来求值，而后缀表达式只需要一个栈就可求值。所以计算表达式的值采用后缀表达式比较简单，易于理解。算法1：后缀表达式求值a)如果是运算数直接入栈b)如果是运算符，先计算结果在将结果压栈算法2：利用转将中缀表达式转后缀表达式人工方法(1)首先补全所有括号(A+B)*D-E/(F+A*D)+C=>((((A+B)*D)-(E/(F+(A*D))))+C)
(2)运算符全部提出到对应的括号外面机器方法首先表示出各个运算符的优先级操作符ch#(^* / %+ -)isp栈内优先级017538
icp栈外优先级086421操作符优先级相等的情况只出现在括号匹配或栈底的“#”与输入最后的“#”号匹配时。
操作符初始化，“#”进栈，读入中缀表达式首字符ch直到ch=“#”:
a)若ch是操作数，直接输出，读入下一个字符ch;
b)若ch是操作数，判断ch的优先级和位于栈顶的操作符op优先级，若(ch)>(op)，令ch进栈，读入下一个字符(观察后面后是否有更高级的运算符);若(ch)
问题与说明
C语言实现
CLion 集成开发环境
备注
程序清单
动态顺序栈
bottom表示栈底指针，固定不变；top表示栈顶指针。top==bottom表示栈空；top-bottom=stacksize-1表示栈满。
结点进栈时首先将数据元素保存到栈顶(top所指的当前位置)top+1，使top指向栈顶的下一个储存位置。结点出栈时，先top-1取栈顶元素。动态栈基本操作的实现栈的类型定义1
2
3
4
5
6
7
8#define STACKSIZE 100
#define STACKINCRMENT 10
#typedeff int ElemType
typedef struct sqstack{
ElemType *bottom;
ElemType *top;
int stacksize;
}sqstack;栈的初始化1
2
3
4
5
6
7
8status Init_stack(void){
sqstack S;
s.bottom=(ElemType *)malloc(STACKSIZE*sizeof(ElemType));
if(!s.bottom) return ERROR;
S.top=S.bottom;
S.stacksize=STACKSIZE;
return OK;
}压栈1
2
3
4
5
6
7
8
9
10
11Status push(sqstack s,ElemType e){
if(S.top-S.bottom==s.stacksize-1){
S.bottom=(ElemType *)realloc((S.stacksize+STACKINCRMENT)*sizeof(ElemType));
if(!S.bottom) return ERROR;
S.top=S.bottom+S.stacksize;
S.stacksize += STACKINCRMENT;
}
*S.top=e;
S.top++;
return OK;
}出栈1
2
3
4
5
6Status pop(sqstack S,ElemType e){
if(S.bottom==S.top) return ERROR;
S.top--;
e=*S.top;
return OK;
}
静态顺序栈
一维数组储存，栈底固定不变，而栈顶则随着进栈出栈而变化。top=0表示栈空，top=stacksize-1为栈满。结点进栈，首先执行top+1，是top指向新的栈顶位置，然后将数据元素保存到栈顶。结点出栈，首先取元素，然后执行top-1。为了避免浪费，可以在初始化时将top和bottom都设为-1。基本操作的实现栈的类型定义1
2
3
4
5
6#define MAX_STACK_SIZE 100
#typedef int ElemType;
typedef struct sqstack{
ElemType stack_array[MAX_STAKC_SIZE];
int top;
}sqstack;栈的初始化1
2
3
4
5Status Init_stakc(void){
sqstack S;
S.top=S.bottom=0;
return S;
}入栈1
2
3
4
5
6Status push(sqstack S,ElemType e){
if(S.top>=MAX_STACK_SIZE) return ERROR
S.top++;
S.stack_array[top]=e;
return OK;
}出栈1
2
3
4
5
6Status pop(sqstack S,ElemType e){
if(S.top==0) retunr ERROR;
S.top-1;
e=S.srray_array[S.top];
return OK;
}
栈的链式储存表示
运算受限，其插入和删除只能在表头位置进行，栈顶指针top就是链表的头指针。链表的节点类型1
2
3
4typedef struct Stack_Node{
ElemType data;
struct Stacj_Node *next;
}Stack_Node;基本操作
初始只有一个头节点head，head->next为NULL，栈空的条件为head->next==NULL;由于只有内存溢出时才会出现栈满的情况，通常不考虑这种情况。元素e进栈操作是将包含该元素的一个节点插入作为第一个数据节点，头插入栈删除第一个节点。链栈的初始化1
2
3
4
5
6
7Stack_Node Init_stack(vodi){
Stack_Node *top;
top=(Stack_Node *)malloc(sizeof(Stack_Node));
if(!top) return ERROR;
top->next=NULL;
return top;
}链栈的压栈1
2
3
4
5
6
7
8
9Status push(Stack_Node *top,ElemType e){
Stack_Node *p;
p=(Stack_Node *)malloc(sizeof(Stack_Node));
if(!p) return ERROR;
p->data=e;
p->next=top->next;
top->next=p;
return OK;
}链栈的出栈1
2
3
4
5
6
7
8
9
10Status pop(Stack_Node *top,ElemType *e){
Stack_Node *p;
ElemType e;
if(top->next==NULL) return ERROR;
p=top->next;
e=p->data;
top->next=p->next;
free(p);
return OK;
}
