顺序栈 /*静态分配栈空间,大小固定,不能扩充* #define TRUe #define FALSE 0 #define OK #define Error 0 #define maxleng 10 typedef int Elem Type Elem Type elem maxleng+1]/*栈元素空间* Int top, /*顶指针* qStack 称水称水水布幸本涂水水水水水客容布称水水客水水水涂水涂水水客水水水客水*水水客水客*水涂水本客水 SqStack为结构类型 例: SqStack s:说明s为结构类型变量,可表示一个栈 其中:stop-顶指针;sclm[stop-顶元素 未用元素 selem *客水水本客水客水*客*常水*客水凇客 幸幸幸幸幸*亲幸*幸**亲幸幸*幸/ 功能:测试栈是否为空 *输入:栈对象 *输出:空时返回TRUE,非空时返回 FALSE 水客客*客常 本*本*亲本本*亲*本亭******本本****幸***率***幸*/ int StackEmpty(sqStack S) eturn trUe return False. *水****客****客*水**客****客**水客*客客*幸*客水**水**客**客 功能:进栈操作 输入:栈对象S的指针,数据元素e 输出:成功时返回OK 水水*水**客水**客水*称水水水*幸***水客水*客水*客*水客水*幸*客水水客水**客 int Push(sqstack "S, Elem Type e Int f(S->top== maxing)/*栈溢出*
顺序栈 /* 静态分配栈空间，大小固定，不能扩充*/ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define maxleng 10 typedef int ElemType; typedef struct { ElemType elem[maxleng+1]; /*栈元素空间*/ int top; /*顶指针*/ }SqStack; /****************************************************** SqStack 为结构类型 例：SqStack s；说明 s 为结构类型变量，可表示一个栈 其中: s.top----顶指针；s.elem[s.top]----顶元素 未用元素 s.elem[0] ******************************************************/ /********************************************************** ** 功能：测试栈是否为空 ** ** 输入：栈对象 S ** ** 输出： 空时返回 TRUE, 非空时返回 FALSE ** **********************************************************/ int StackEmpty(SqStack S) { if (S.top==0) return TRUE; else return FALSE; } /********************************************************** ** 功能：进栈操作 ** ** 输入：栈对象 S 的指针，数据元素 e ** ** 输出： 成功时返回 OK ** **********************************************************/ int Push(SqStack *S,ElemType e) { int j; if (S->top==maxleng) /*栈溢出*/ {
printf("OVERFLOW") return ERROR; S->top /*栈顶加1*/ S->elem[S->top]=e;,/*新元素进栈* return o 客水客水*水水水**水*水*称水客客*客水水容*客水*水水布**客水涂水客*水水客水*水*水水市**客水*称水水*客水客幸 **功能:退栈操作 输入:栈对象S的指针 输出:成功时返回OK、通过数据元素指针e返回栈顶元素的值* 空栈时返回 ERROR int Pop(sqstack"S, Elem Type 'e) if( Stack Empty(*S) return ErROR,/*空栈失败返回* e=S-elem[S->top]/*取栈顶元素* S->top=S->top-l;/栈顶减1* return OK. /成功返回* ma int 1; Elem Type elem Sqstacks *定义栈对象s* 初始化栈对象s* SCI for(i=1;i<=5,i++)/*输入5个数据元素并进栈 scanf("%d", &elem) Push(&s, elem) }; for(i=1;i<=7,i++)/退栈操作* f(Pop(&s&elem)=OK)/*正确退栈时,可通过elem输出数据元素* printf("No%d=%d ", i, elem) else/*若栈已空,结束,此时elem的值无意义,* i printf("stack has been empty! ") break
printf("OVERFLOW"); return ERROR; } S->top++; /*栈顶加 1*/ S->elem[S->top]=e; /*新元素进栈*/ return OK; } /******************************************************************* ** 功能：退栈操作 ** ** 输入：栈对象 S 的指针 ** ** 输出： 成功时返回 OK、通过数据元素指针 e 返回栈顶元素的值 ** ** 空栈时返回ＥＲＲＯＲ ** *******************************************************************/ int Pop(SqStack *S,ElemType *e) { if(StackEmpty(*S)) return ERROR; /*空栈,失败返回 */ *e=S->elem[S->top];/*取栈顶元素*/ S->top=S->top-1; /*栈顶减 1*/ return OK; /*成功返回 */ } main() { int i; ElemType elem; SqStack s; /*定义栈对象 s*/ s.top=0; /*初始化栈对象 s*/ clrscr(); for(i=1;i<=5;i++) /*输入 5 个数据元素并进栈*/ { printf("No%d? ",i); scanf("%d",&elem); Push(&s,elem); }; for(i=1;i<=7;i++) /*退栈操作*/ { if (Pop(&s,&elem)==OK) /*正确退栈时，可通过 elem 输出数据元素*/ printf("No%d=%d ",i,elem); else /*若栈已空，结束，此时 elem 的值无意义，*/ { printf("stack has been empty!"); break;} }; }
4链式队列 定义结点类型 (1)存放元素的结点类型 def int elem typedef struct Qnode I ElemType data struct QNode 半next 1 QNode, *QueuePtr /*可理解为定义两个类型: 链式队列结点的结构类型; Queue 链式队列结点指针类型,指向链式队列结点 */ (2)由头、尾指针组成的结点类型 QueuePtr front;/*队头指针* QueuePtr rear;/*队尾指针*/ I LinkQueue /*结构类型 LinkQueue的变量为队列对象*/ 客涂水客水水客水凇客*水*水*客水客涂客水水凇客*客水*水亦水常客水客水客 索功能:初始化队列 输入:队列对象S的指针 输出:成功时返回OK 水水常称*客水客水本水客本亦水常水客水农称水客水客涂*本水*客水客水常水*客客水涂水客*客客水 nt InitQueue(LinkQueue *Q Q->front=Q->rear=(QueuePtr) malloc(sizeof (QNode)) if(Q->front=NULL) return ERROR Q->front->nex t=NULL 涂*水客水水客客水 功能:测试队列是否为空 输入:队列对象Q 输出:空时返回TRUE,非空时返回 FALSE 幸幸*幸幸本幸李幸幸幸幸幸 int QueueEmpty(LinkQueue Q) if (Q. front==Q rear) return TRUE
4 链式队列 定义结点类型 (1)存放元素的结点类型 typedef int ElemType; typedef struct QNode { ElemType data; struct QNode *next; } QNode, *QueuePtr; /*可理解为定义两个类型: QNode ----- 链式队列结点的结构类型; QueuePtr ----- 链式队列结点指针类型，指向链式队列结点, */ (2)由头、尾指针组成的结点类型 typedef struct { QueuePtr front; /*队头指针*/ QueuePtr rear; /*队尾指针*/ } LinkQueue; /*结构类型LinkQueue的变量为队列对象*/ /********************************************************** ** 功能：初始化队列 ** ** 输入：队列对象 S 的指针 ** ** 输出： 成功时返回 OK ** **********************************************************/ int InitQueue(LinkQueue *Q) { Q->front=Q->rear=(QueuePtr) malloc(sizeof(QNode)); if (Q->front==NULL) return ERROR; Q->front->next=NULL; return OK; } /********************************************************** ** 功能：测试队列是否为空 ** ** 输入：队列对象 Q ** ** 输出： 空时返回 TRUE, 非空时返回 FALSE ** **********************************************************/ int QueueEmpty(LinkQueue Q) { if (Q.front==Q.rear) return TRUE;
功能:进队列操作 输入:队列对象Q的指针,数据元素e 输出:成功时返回OK int EnQueue( LinkQueue*Q, ElemType e)/*进队列*/ Q->rear->next=( QueuePtr) malloc( sizeof( QNode));/*创建新结点*/ if(Q->rear->next=nuLL) exit(OVERFLOW) Q-rear=Q-rear-next;/*修改尾结点指针*/ Q-rear->data=e;Q-rear->next=NUL;/*新结点赋值*/ return OK /*本*****幸本幸本*率本***幸*幸布春*幸本**率本幸率布容春***** 六功能:出队操作 输入:队列对象S的指针 索输出:成功时返回OK、通过数据元素指针e返回队首元素的值 空队列时返回 ERROR 客水常水凇客*水水客本客*本水水水水水水凇称水水容水凇*本客水本客容水市客宗 nt DeQueue( Link Queue*Q, ElemType*e)/*出队列*/ QueuePtr p if( QueueEmpty(*Q)) return error;/*空队列,返回错误*/ p=Q- front→>next; /*p指向删除结点*/ >data /*取数据* Q-> front->next=p->next;/*修改队头指针*/ f(Q->rear=p)Q-rear=Q> front;/*若删除结点为队尾结点 设置为空队列*/ free retur maino int 1 ElemType el LinkQ *定义队列对象que*/ InitQueue(&que) /*队列que初始化*/ /*元素1进队列*/
else return FALSE; } /********************************************************** ** 功能：进队列操作 ** ** 输入：队列对象 Q 的指针，数据元素 e ** ** 输出： 成功时返回 OK ** **********************************************************/ int EnQueue(LinkQueue *Q, ElemType e) /*进队列*/ { Q->rear->next=(QueuePtr) malloc(sizeof(QNode)); /*创建新结点*/ if(Q->rear->next==NULL) exit(OVERFLOW); Q->rear=Q->rear->next; /*修改尾结点指针*/ Q->rear->data=e; Q->rear->next=NULL; /*新结点赋值*/ return OK; } /******************************************************************* ** 功能：出队操作 ** ** 输入：队列对象 S 的指针 ** ** 输出： 成功时返回 OK、通过数据元素指针 e 返回队首元素的值 ** ** 空队列时返回ＥＲＲＯＲ ** *******************************************************************/ int DeQueue(LinkQueue *Q, ElemType *e) /*出队列*/ { QueuePtr p; if (QueueEmpty(*Q)) return ERROR; /*空队列，返回错误*/ p=Q->front->next; /*p指向删除结点*/ *e=p->data; /*取数据*/ Q->front->next=p->next; /*修改队头指针*/ if (Q->rear==p) Q->rear=Q->front;/*若删除结点为队尾结点， 设置为空队列*/ free(p); return OK; } _ main() { int i; ElemType elem; LinkQueue que; /*定义队列对象que*/ InitQueue(&que); /*队列que初始化*/ EnQueue(&que,1); /*元素1进队列*/
EnQueue(&que, 2) /*元素2进队列*/ EnQueue(&que, 3) /*元素3进队列*/ DeQueue(&que,&elem); printf("%d",elem);/*1出队列*/ DeQueue(&que,&elem); printf("%d",elem);/*2出队列*/ DeQueue(&que,&elem); printf("%d",elem);/*3出队列*/ DeQueue(&que, &elem): printf(%d", elem) /*队列已空,由于未检查返回结果,取出的还是3,产生错误*/ 5.顺序队列 # define MAXQSIzE100/*首次分配连续存储单元的大小,可存储 MAXQS IZE个元素*/ typedef int elemType typedef struct Sqlist ElemType*base;/*连续存储单元首地址*/ int front /*队列头指针,若队列不空,指向队头元素*/ int rear /*队列尾指针,若队列不空,指向队尾元素的下一个位置*/ /* SqQueue为结构类型,用其说明的变量在程序中作为队列*/ 水客水**水容水常水水水本客水凇水凇水水客水水布客水*客水 功能:初始化队列 输入:队列对象S的指针 输出:成功时返回OK *亲*亲**亲**亲*亲**家本亲*****幸幸**幸*/ int InitQueuesqQueue *Q) Q->base=(Elem Type *)malloc( MAXQSIZE*sizeof (ElemType)) if (!Q->base) exit(OVERFLOW) Q->front=Q->rear=0 return oK **水客水容***水客水*涂水客水*客**客客水***水常客水涂水*水水***水*水*客**水常客水幸客 功能:进队列操作 输入:队列对象Q的指针,数据元素e 输出:成功时返回OK nt EnQueue(SqQueue *Q, Elem Type e) if ((Q->rear+1)%MAXQS IZE==Q->front) return error
EnQueue(&que,2); /*元素2进队列*/ EnQueue(&que,3); /*元素3进队列*/ DeQueue(&que,&elem); printf("%d",elem); /*1 出队列*/ DeQueue(&que,&elem); printf("%d",elem); /*2 出队列*/ DeQueue(&que,&elem); printf("%d",elem); /*3 出队列*/ DeQueue(&que,&elem); printf("%d",elem); /*队列已空，由于未检查返回结果，取出的还是3,产生错误*/ } 5．顺序队列 #define MAXQSIZE 100 /*首次分配连续存储单元的大小，可存储MAXQSIZE个元素*/ typedef int ElemType; typedef struct SqList { ElemType *base; /*连续存储单元首地址*/ int front; /*队列头指针，若队列不空，指向队头元素*/ int rear; /*队列尾指针，若队列不空，指向队尾元素的下一个位置*/ } SqQueue; /*SqQueue为结构类型，用其说明的变量在程序中作为队列*/ /********************************************************** ** 功能：初始化队列 ** ** 输入：队列对象 S 的指针 ** ** 输出： 成功时返回 OK ** **********************************************************/ int InitQueue(SqQueue *Q) { Q->base=(ElemType *) malloc(MAXQSIZE*sizeof(ElemType)); if (!Q->base) exit(OVERFLOW); Q->front=Q->rear=0; return OK; } /********************************************************** ** 功能：进队列操作 ** ** 输入：队列对象 Q 的指针，数据元素 e ** ** 输出： 成功时返回 OK ** **********************************************************/ int EnQueue(SqQueue *Q,ElemType e) { if ((Q->rear+1)%MAXQSIZE==Q->front) return ERROR;