数据结构-第3章描述.ppt

数据结构 栈和队列是两种特殊的线性结构，特点： 栈： 后进先出 如铁路调度站 队列：先进先出 如购物排队问题 3.1.2 栈的表示和实现 顺序存储结构：顺序栈； 链式存储结构：链栈； 顺序栈,栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时用指针top表示栈顶元素在顺序栈的位置。 栈的表示和实现 顺序栈的结构 顺序表示 #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; 　其中stacksize表示栈当前可以使用的最大容量。Base为栈底，Top为栈顶。栈顶指针指向栈顶元素的下一个位置（即下次压栈时元素所放的位置） 基本操作的实现： 初始化栈 Status InitStack(SqStack S) { //构造一个空栈 S.base = (SElemType *)malloc (STACK_INIT_SIZE*sizeof (SElemType)); if (!S.base) exit (OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } //InitStack 压栈: Status Push(SqStack S, SElemType e) { //元素e插入到栈中，成为新的栈顶 if (S.top-S.base=S.stacksize) //栈满 { S.base=(SElemType *)realloc (S.base, (S.stacksize+STACKINCREMENT) * sizeof(SElemType); if (!S.base) exit (OVERFLOW); S.top = S.base + S.stacksize; S.stacksize+=STACKINCREMENT; } // if *S.top++ = e; return OK; } //Push 弹栈: Status Pop(SqStack S, SElemType e) { //从栈顶读取数据放入e内，栈中下一元素所 //在位置成为新的栈顶 if（S.top = = S.base）return ERROR; //栈空 e = * -- S.top; return OK; } //Pop 注意top的操作顺序和值的变化。 压栈：value?top; top++; 弹栈：top--; top-value; Status GetTop(SqStack S,SElemType e){ if (S.top==S.base) return ERROR; e=*(S.top-1); return OK; } 思考：语句e=*(S.top-1); 改为e=*(--S.top);是否正确？ 压栈的处理： p=malloc(Lnode); p-next = s-next; s-next=p; 补充：一种新的栈的类型定义 # define StackSize 100 typedef char datatype; typedef struct { datatype data[stacksize]; int top; }seqstack; SeqStack *s; 思考：如何判断空栈和满栈 假设现要编制一个满足下列要求的程序：对 于输入的任意一个非负十进制整数，打印输 出与其等值的八进制数。 八进制的各个数位产生的顺序是