清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter4 Stacks Queues

CHAPTER 4 Stacks and Queues 81 The Stack ADT L ADT A stack is a Last-In-First-Out(LIFO) list, that is an ordered list in which insertions and deletions are made at the top only Objects: A finite ordered list with zero or more elements Operations cInt StackEmpty Stack S) cInt Stack Full( Stack S); cG Stack Init Stack (; G MakeEmpty( Stack S ) Note: A Pop(or Get Top)on CG Push( Element Type X, Stack S) an empty stack is an error in the stack adt Element Type Get Top( Stack S) Push on a full stack is C Pop( Stack S) an implementation error but not an adt error
§1 The Stack ADT 1. ADT 1 2 3 4 5 6 65 6 5 A stack is a Last-In-First-Out (LIFO) list, that is, an ordered list in which insertions and deletions are made at the top only. Objects: A finite ordered list with zero or more elements. Operations: Int StackEmpty( Stack S ); Int StackFull( Stack S ); Stack InitStack( ); MakeEmpty( Stack S ); Push( ElementType X, Stack S ); ElementType GetTop( Stack S ); Pop( Stack S ); Note:A Pop (or GetTop) on an empty stack is an error in the stack ADT. Push on a full stack is an implementation error but not an ADT error. CHAPTER 4 Stacks and Queues

2. Implementations Linked List Implementation typedef int StackData; typedef struct node i StackData data; 结点 struct node xlink;/链指钅 i StackNode; typedef struct t StackNode“top; /栈顶指针 3 Linkstack
2. Implementations ➢ Linked List Implementation typedef int StackData; typedef struct node { StackData data; //结点 struct node *link; //链指针 } StackNode; typedef struct { StackNode *top; //栈顶指针 } LinkStack;

Basic operation of Linked List Implementation a Create void InitStack( LinkStack S)& S->top= NULL ■Push int Push( LinkStack *S, StackData x)t StackNode *p=( StackNode *) malloc sizeof( stackNode )) p->data=X; p->link=S->top S->top= p; return 1
Basic operation of Linked List Implementation ▪ Create void InitStack ( LinkStack *S ) { S->top = NULL; } ▪ Push int Push ( LinkStack *S, StackData x ) { StackNode *p = ( StackNode * ) malloc ( sizeof ( StackNode ) ); p->data = x; p->link = S->top; S->top = p; return 1; }

StackEmpty int Stack Empty (Link Stack *S)( return s->tol p NULL Pop int Pop( linkstack *S, Stack Data &x)t if( Stack Empty(S)) return 0; StackNode *p=S->top S->top=p->link >data free(p) return 1
▪ StackEmpty int StackEmpty (LinkStack *S) { return S->top == NULL; } ▪ Pop int Pop ( LinkStack *S, StackData &x ) { if ( StackEmpty (S) ) return 0; StackNode * p = S->top; S->top = p->link; x = p->data; free (p); return 1; }

GetTop int GetTop( linkStack * S, StackData &x)t if( StackEmpty(S)) return 0; x=S->top->data return 1 Makeempty int MakeEmpty( LinkStack *S)t While(s->top !=NULL StackNode x S->top; S->top=S->top ->links free(p)
▪ GetTop int GetTop ( LinkStack *S, StackData &x ) { if ( StackEmpty (S) ) return 0; x = S->top->data; return 1; } ▪ MakeEmpty int MakeEmpty ( LinkStack *S) { While(S->top!=NULL){ StackNode * p = S->top; S->top = S->top ->link; free(p); } }

Array Implementation #define STacK INiT size 100 #define STacKIncrement 10 typedef char StackData; typedef struct{顺序栈定义 StackData*base;/栈底指针 StackData*top;栈顶指针 int stacksize;/当前已分配的存储空间 3 SeqStack Note: O The stack model must be well encapsulated. That is, no part of your code, except for the stack routines, can attempt to access the Array or Top ofStack variable 2 Error check must be done before Push or Pop(Top)
➢ Array Implementation #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef char StackData; typedef struct { //顺序栈定义 StackData *base; //栈底指针 StackData *top; //栈顶指针 int stacksize;//当前已分配的存储空间 } SeqStack; Note: The stack model must be well encapsulated. That is, no part of your code, except for the stack routines, can attempt to access the Array or TopOfStack variable. Error check must be done before Push or Pop (Top)

Basic operation of Array Implementation Create stack void initstack( Seqstack*S){/置空栈 S->base = StackData *)mallOc(STACK INIT SIZE sizeof( stackData)); if (S->base) exit(OVERFLOW) S->top S->base S->stacksize= STACK INIT SIZE Return ok
Basic operation of Array Implementation ▪ Create stack void InitStack ( SeqStack *S) { //置空栈 S->base =( StackData *)malloc(STACK_INIT_SIZE * sizeof(StackData)); if (!S->base) exit(OVERFLOW); S->top = S->base ; S->stacksize= STACK_INIT_SIZE ; Return ok; }

a StackEmpty int StackEmpty(SeqStack *S)i if(S->top=S->base) return1判栈空空则返回1 else return0;/否则返回0 Makeempty void MakeEmpty(stack S) iS->top==S->base i
▪ StackEmpty int StackEmpty (SeqStack *S) { if( S->top == S->base ) return 1 //判栈空,空则返回1 else return 0; //否则返回0 } ▪ MakeEmpty void MakeEmpty(Stack s) {S->top == S->base ;}

■Push int Push(SeqStack*S, StackData x)i /插入元素x为新的栈顶元素 if( StackFull(S))i S->base = StackData *)malloc(S->base (S->stacksize+ STACKINCREMENT)X sizeof( stackData)); if( S->baseexit(overflow); S->top=S->base+S->stacksize; S-> stacksize+= STACKINCREMENT;/)加存储空间 (S->top)=x; (S->top)++; Return ok
▪ Push int Push (SeqStack *S, StackData x) { //插入元素x为新的栈顶元素 if ( StackFull (S) ){ S->base =( StackData *)malloc(S->base , (S->stacksize+ STACKINCREMENT) * sizeof(StackData)); if(! S->base)exit(overflow); S->top= S->base + S->stacksize; S->stacksize+= STACKINCREMENT; //追加存储空间 } *(S->top)=x; (S->top)++; Return ok }

OD int pop seqstack *S, StackData &x)t /若栈空返回0,否则栈顶元素退出到x并返回1 if( StackEmpty()) return 0; (S->top X=“(S->top) return 1 Gettop int Gettop(SeqStack *S, StackData &x)i /若栈空返回0,否则栈顶元素读到x并返回1 if( StackEmpty()) return 0; (S->top)-; X=“(S->top) return 1:
▪ Pop int pop (SeqStack *S, StackData &x) { //若栈空返回0, 否则栈顶元素退出到x并返回1 if ( StackEmpty(S) ) return 0; --(S->top); x = *(S->top); return 1; } ▪ Gettop int Gettop (SeqStack *S, StackData &x) { //若栈空返回0, 否则栈顶元素读到x并返回1 if ( StackEmpty(S) ) return 0; (S->top)--; x = *(S->top); return 1;}
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter3 Lists.ppt
- 天津大学:《数据结构 Data Structures》课程PPT教学课件(英文版)CHAPTER 2 ALGORITHM ANALYSIS.ppt
- 天津大学:《数据结构 Data Structures》课程PPT教学课件(英文版)CHAPTER 8 THE DISJOINT SET ADT.ppt
- 华中师范大学计算机科学系:《数据结构》第6章 二叉树和树.ppt
- 华中师范大学计算机科学系:《数据结构》第2章 线性表.ppt
- 华中师范大学计算机科学系:《数据结构》第8章 查找表.ppt
- 华中师范大学计算机科学系:《数据结构》第7章 图和广义表.ppt
- 华中师范大学计算机科学系:《数据结构》第5章 串和数组.ppt
- 华中师范大学计算机科学系:《数据结构》第4章 栈与队列.ppt
- 华中师范大学计算机科学系:《数据结构》第3章 排序.ppt
- 华中师范大学计算机科学系:《数据结构》第1章 绪论(王敬华).ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)实验一.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第四章 串.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第六章 树和二叉树.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第五章 数组.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第二章 线性表.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第三章 栈和队列.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第一章 绪论.ppt
- 清华大学:《数据结构》课程教学资源(习题讲义实验)三元组表示的稀疏矩阵加法.doc
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第四章 串.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter5 trees.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter6 Graph Algorithms.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter7 Search.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter8 Sorting.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter9 String.ppt
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验二.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)二叉树试验三.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验一.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验四.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验模板.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验五.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)复习2007级.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)2004级计算机B卷.doc
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第一章 绪论.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第九章 排序.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第1章 绪论.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第2章 线性表.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第3章 栈和队列.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第4章 串.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第五章 数组和广义表.ppt