栈的表示和实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 5
#define LISTINCREMENT 5
typedef int Status;
typedef int ElemType;
typedef struct {
ElemType *firstElem;
ElemType *lastElem;
int stackSize;
}Stack;
Status initStack(Stack &s ){
s.firstElem = (ElemType*) malloc(sizeof (ElemType)*LIST_INIT_SIZE);
if(!s.firstElem) return ERROR;
s.lastElem = s.firstElem;
s.stackSize = LIST_INIT_SIZE;
return OK;
}
Status push(Stack &s, ElemType e){
if(s.stackSize+1>LIST_INIT_SIZE){
s.firstElem = (ElemType*) realloc(s.firstElem,sizeof (ElemType)*(s.stackSize+LISTINCREMENT));
if(!s.firstElem) return ERROR;
s.stackSize += LISTINCREMENT;
}
*(s.lastElem) = e;
s.lastElem++;
return OK;
}
Status pop(Stack &s, ElemType &e){
if(s.lastElem == s.firstElem)
return ERROR;
e = *(s.lastElem-1);
s.lastElem--;
return OK;
}
int main(){
Stack s;
if(initStack(s)!=OK){
printf("init wrong");
return -1;
}
for(int i=0;i<7;i++){
if(push(s,i)==OK) printf("push Ok:%d",i);
else{
printf("push wrong:%d",i);
}
}
ElemType e;
for(int i=0;i<7;i++){
if(pop(s,e)==OK) printf("pop Ok:%d",e);
else{
printf("pop error:%d",i);
}
}
return 0;
}
|
栈的应用
10进制数N转换成8进制的算法
1
2
3
4
5
6
7
8
9
10
11
12
13
| void converse(int N){
Stack S;
initStack(S);
while (N){
push(S,N%8);
N /= 8;
}
while(!isEmpty(S)){
ElemType e;
push(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
21
22
23
24
25
26
27
28
29
30
31
| Status isMatch(char *string){
Stack s;
if(!initStack(s)) return ERROR;
ElemType e;
for(char *p=string;*p;p++){
if(*p == '(' || *p == '{' || *p == '[')
push(s,*p);
if(*p == ')' ){
pop(s,e);
if(e != '(')
return ERROR;
}
if(*p == ']' ){
pop(s,e);
if(e != '[')
return ERROR;
}
if(*p == '{' ){
pop(s,e);
if(e != '}')
return ERROR;
}
}
if(isEmpty(s))
return OK;
return ERROR;
}
|
链队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
using namespace std;
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 5
#define LISTINCREMENT 5
typedef int Status;
typedef int ElemType;
typedef struct QNode{
ElemType data;
struct QNode * next;
}QNode,*Queue;
typedef struct{
Queue frontPtr;
Queue rearPtr;
}LinkQueue;
Status initQueue(LinkQueue &Q){
Q.frontPtr = (QNode*) malloc(sizeof (QNode));
Q.rearPtr = Q.frontPtr;
if(!Q.frontPtr) return ERROR;
Q.frontPtr->next == NULL;
return OK;
}
Status EnQueue(LinkQueue &Q,ElemType e){
QNode *m = (QNode*)malloc(sizeof (QNode));
if(!m) return ERROR;
m->data = e;
m->next = NULL;
Q.rearPtr->next = m;
Q.rearPtr = m;
return OK;
}
Status isEmpty(LinkQueue Q){
if(Q.frontPtr == Q.rearPtr) return ERROR;
else return OK;
}
Status DeQueue(LinkQueue &Q,ElemType &e){
if(isEmpty(Q)) return ERROR;
QNode *m = Q.frontPtr;
Q.frontPtr = Q.frontPtr->next;
e = m->data;
free(m);
return OK;
}
|
顺序队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
using namespace std;
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 5
#define LISTINCREMENT 5
typedef int Status;
typedef int ElemType;
#define MAXQSIZE 10
typedef struct {
ElemType *base;
int front;
int rear;
}Queue;
Status isFull(Queue &Q){
if((Q.rear - Q.front + MAXQSIZE)%MAXQSIZE < MAXQSIZE - 1)
return ERROR;
else return OK;
}
Status initQueue(Queue &Q){
Q.base = (ElemType*) malloc(sizeof (ElemType)*MAXQSIZE);
if(!Q.base) return ERROR;
Q.front = Q.rear = 0;
return OK;
}
Status enQueue(Queue &Q,ElemType e){
if(isFull(Q)) return ERROR;
Q.base[Q.rear] = e;
Q.rear = (++Q.rear)%MAXQSIZE;
return OK;
}
Status deQueue(Queue &Q,ElemType &e){
if(Q.rear == Q.front) return ERROR;
e = Q.base[Q.front];
Q.front = (++Q.front)%MAXQSIZE;
return OK;
}
|
双端队列
双端队列：双端队列是一种特殊的线性表，特殊在限定插入 和删除操作只能在表的两端进行。