第3章 限定性线性表—栈和队列.pptVIP

初始化 InitStack(SqStack S) { S.base = S.top = (SElemType *)malloc(…); if(!S.base) exit(OVERFLOW); S.stacksize = STACK_INIT_SIZE; return OK; } 读栈顶元素 GetTop(SqStack S, SElemTypee) { if(S.top == S.base) return ERROR; e = *(S.top – 1); return OK; } 入栈 Push(SqStack S, SElemType e) { if(S.top–S.base = S.stacksize){ S.base = (SElemType *)realloc(…); if(!S.base) exit(OVERFLOW); S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; //*S.top = e; S.top++; return OK; } 出栈 Pop(SqStack S, SElemType e) { if(S.top == S.base) return ERROR; e = *--S.top; //--S.top ; e = *S.top; return OK; } 链栈 typedef struct STNode{ SElemType data; struct STNode *next; }STNode, *LinkStack; 栈顶结点 栈底结点 栈顶指针：链栈由栈顶指针S唯一确定 链栈本身无容量限制，在用户内存空间的范围内不会出现栈满情况 初始化 InitStack(LinkStack S) { S = NULL; return OK; } 入栈 Push(LinkStack S, SElemType e) { p = (LinkStack) malloc( sizeof( STNode)); if(!p) exit(OVERFLOW); p-data = e; ①p-next = S; ②S = p; return OK; } 出栈 Pop(LinkStack S, SElemType e) { if(S == NULL) return ERROR; e = S-data; ①p = S; ②S = S-next; free(p); return OK; } 5.栈总结 栈是一种具有线性结构的数据结构，是操作受限的线性表； 栈的特点是后进先出，只能在栈顶进行插入和删除操作，分别称为入栈和出栈； 顺序栈中，栈空标志：S.top = S.base; 栈满标志：S.top – S.base = S.stacksize; 链栈中，不设头结点，头指针就是栈顶指针，栈空S = NULL。 练习： 1.已知栈的输入序列为1,2,3,…,n。输出序列为 a1, a2, …, an，如果a2=n，输出序列共有多少种情况？ n-1 种输出序列。 2.已知栈的输入序列为1,2,3,…,n。输出序列为 a1, a2, …, an，若a1=n，问ai=? ai=n-i+1 3. I表示入栈，O表示出栈，若元素入栈顺序为1234，为了得到1342的出栈顺序，相应的I和O的操作串是什么？ I1O1I2I3O3I4O4O2 4.设计一个算法，用栈的基本运算，判定一个字符串是否为对称字符串，若是，则返回1，否则返回0。 int match(char *p) { for(n=0; p[n]!=‘\0’; n++); InitStack(S); for(i=0; in/2; i++) Push(S, p[i]); for(i=(n+1)/2; in; i++){ Pop(S, e); if(e != p[i]) { DestroyStack(S); return 0; } } if(StackEmpty(S)){ DestroyStack(S