数据结构第3章讲解.ppt

第三章 栈和队列;3.1 栈;#define STACK_INIT_SIZE 100; //存储空间初始分配量 typedef STACKINCREMENT 10; //存储空间分配增量 typedef struct{ SElemtype *base; //栈底指针，栈构造之前和销毁之后为空值NULL SElemtype *top; //栈顶指针，指向栈顶元素的下一个位置 int stacksize; //当前已分配存储空间，以元素为单位 } SqStack; void InitStack(SqStack S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof( SElemType )); if(! S.base) exit(OVERFLOW); /* 存储分配失败 */ S.top= S.base; /* 栈空标志，top=base */ S.stacksize=STACK_INIT_SIZE; };取栈顶元素GetTop_Sq 参数：顺序栈S、取得的栈顶元素e 分析：由于top指向栈顶元素的下一个位置，因此实际的栈顶元素的位置应是top -1；栈非空时，此操作有效。 Status GetTop_Sq(SqStack S, ElemType e) { /* 判断栈是否为空 */ if ( S.base == S.top) return ERROR; e = *( S.top -1); return OK; };Status Push_Sq( SqStack S, ElemType e ) { /* 判断栈是否为满 */ if ( S.top - S.base = S.stacksize ) { /* 栈满，追加空间 */ newbase = ( ElemType * )  realloc( S.base, ( S.stacksize + STACKINCREMENT ) * sizeof(ElemType)  ); if ( newbase == NULL ) exit(OVERFLOW);  S.base = newbase; S.top = S.base + S.stacksize; /*修改top指针指向*/ S.stacksize += STACKINCREMENT; } *S.top++ = e; return OK; } 算法分析——时间T(n) = O(1);出栈操作Pop_Sq 参数：顺序栈S、删除的栈顶元素e 分析：在栈非空时，删除栈顶元素 Status Pop_Sq( SqStack S, ElemType e) { /* 判断栈是否为空 */ if (S.base == S.top) return ERROR; e = *( --S.top); /* 注意与GetTop( )的区别 */ return OK; } 算法分析——时间T(n) = O(1);3.1 栈–链栈的表示与实现;第三章 栈和队列;3.2 栈的应用举例-行编辑程序 ; void LineEdit() /* 算法3.2 */ { InitStack(s); ch=getchar(); while(ch!=EOF) { /*结束?(EOF为F6键，全文结束符) */ while(ch!=EOFch!=\n) /* 当全文没结束且没到行末*/ { switch(ch) { case #:if(!StackEmpty(s)) Pop(s,ch); /* 仅当栈非空时退栈,c可由ch替代 */ break; case @:ClearStack(s); /* 重置s为空栈 */ break; default :Push(s,ch); /* 其他字符进栈 */ } ch=getchar(); /* 从终端接收下一个字符 */ } ; StackTraverse(s,cop