用链表实现栈和队列.doc

数据结构与算法分析 实验二实验报告 姓名：XXXXXXXXXX学号：XXXXXXXXXX班级：CCCCCCCCCC XXXXXXXXXXX 数据结构实验报告实验二 CCCCCCCCCCCCCC 实验二（1） 用链表实现栈一、实验描述用链表实现一个栈。2、 实验设计1 进栈（PUSH）算法 若TOPn时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作）； 置TOP=TOP+1（栈指针加1，指向进栈地址）； S(TOP)=X，结束（X为新进栈的元素）； 2 退栈（POP）算法 若TOP0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作)； X=S(TOP)，（退栈后的元素赋给X）： TOP=TOP-1，结束（栈指针减1，指向栈顶）。3、 实验实现代码#include #include #define DataType int#define MAXSIZE 1024typedef structDataType dataMAXSIZE;int top;SeqStack; /栈初始化 SeqStack *Init_SeqStack() XXXXXXXXXXX 数据结构实验报告实验二 CCCCCCCCCCCCCC SeqStack *s;s=(SeqStack *)malloc(sizeof(SeqStack); if(!s)printf(空间不足n);return NULL;elses-top=-1;return s; /判栈空int Empty_SeqStack(SeqStack *s)if(s-top= -1)return 1;elsereturn 0;/入栈int Push_SeqStack(SeqStack *s,DataType x) if(s-top=MAXSIZE-1)return 0;/栈满不能入栈elses-top+;s-datas-top=x;return 1; XXXXXXXXXXX 数据结构实验报告实验二 CCCCCCCCCCCCCC /出栈int Pop_SeqStack(SeqStack *s,DataType *x)if(Empty_SeqStack(s)return 0;/栈空不能出栈else*x=s-datas-top;s-top-;return 1;/栈顶元素存入*x，返回/取栈顶元素DataType Top_SeqStack(SeqStack *s)if(Empty_SeqStack(s)return 0;/栈空elsereturn s-datas-top;int Print_SeqStack(SeqStack *s)int i;printf(当前栈中的元素:n);for(i=s-top;i=0;i-)printf(%3d,s-datai);printf(n);return 0; XXXXXXXXXXX 数据结构实验报告实验二 CCCCCCCCCCCCCC int main()SeqStack *L;int n,num,m;int i;L=Init_SeqStack();printf(初始化完成n);printf(栈空：%dn,Empty_SeqStack(L);printf(请输入入栈元素个数：n);scanf(%d,&n);printf(请输入要入栈的%d个元素：n,n);for(i=0;in;i+) scanf(%d,&num);Push_SeqStack(L,num);Print_SeqStack(L);printf(栈顶元素：%dn,Top_SeqStack(L);printf(请输入要出栈的元素个数（不能超过%d个）：n,n);scanf(%d,&n);printf(依次出栈的%d个元素：n,n);for(i=0;in;i+)Pop_SeqStack(L,&m);printf(%3d,m);printf(n);Print_SeqStack(L);printf(栈顶元素：%dn,Top_SeqStack(L);return 0; XXXXXXXXXXX 数据结构实验报告实验二 CCCCCCCCCCCCCC 4、 实验结果 XXXXXXXXXXX 数据结构实验报告实验二 CCCCCCCCCCCCCC 实验二（2） 用链表实现队列一、实验描述用链表实现一个队列。2、 实验设计队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将最后被删除的元素，因此队列又称为“先进先出”（FIFOfirst in first out）的线性表。 队列空的条件：front=rear 队列满的条件： rear = MAXSIZE三、实验实现代码#include #include typedef struct QNode int data; struct QNode* next;QNode;typedef struct QList struct QNode* front; struct QNode* end;QList;void InitQL(QList* QL) if(QL=NULL) QL=(QList*)malloc(sizeof(QList); QL-front=NULL; XXXXXXXXXXX 数据结构实验报告实验二 CCCCCCCCCCCCCC QL-end=NULL;void InsertQL(QList* QL,int value) QNode* p; p=(QNode*)malloc(sizeof(QNode); p-data=value; if(QL-front=NULL) QL-front=p; QL-end=p; p-next=NULL; else p-next=NULL; QL-end-next=p; QL-end=p; int DeleteQL(QList* QL) QNode *p; int res; if(QL-front=NULL) return -1; res=QL-front-data; p=QL-front; if(QL-front-next=NULL) QL-front=NULL; QL-end=NULL; else QL-front=p-next; free(p); XXXXXXXXXXX 数据结构实验报告实验二 CCCCCCCCCCCCCC return res;void Print(QList* QL) QNode *p; p=QL-front; while(p) printf(%dt,p-data); p=p-next; int main() QList *ML; int i,val; ML=(QList*)malloc(sizeof(QList); InitQL(ML); for(i=0;i34;i+) InsertQL(ML,i*8+