栈与队列数据结构课程设计.doc

实 验 报 告课程名称 数据结构实验及课程设计 实验项目 栈和队列的定义及操作 实验仪器 pc机一台 系 别_信息管理学院_专 业_信息安全_班级/学号 信安0901 2009012225 学生姓名 郭瑞 实验日期 2010-11-19 成 绩 指导教师 _林小茶_北京信息科技大学计算机信息管理学院（课程上机）实验报告实验课程名称: 数据结构实验及课程设计专业: 信息安全 班级: 信安0901 学号: 2009012225 姓名: 郭瑞 成绩: 实验名称线性表操作的实现实验地点小营机房实验时间1. 实验目的：（1）掌握栈的顺序存储和链式存储的概念。（2）掌握队列的顺序存储和链式存储的概念。（3）熟练编写相关的程序。2. 实验内容：编写并调试顺序栈、单链表表示的栈、循环队列、单链表表示的队列的所有操作，并编写主函数对这些函数进行调试。主函数中要有针对解决实际问题的程序，如回文问题和进制转换问题等。3. 实验要求：1、预先写好程序。2、记录调试过程遇到的错误和改正的方法。3、程序完成后提交到学院的服务器上。4、源程序代码粘贴到本报告的最后。4. 实验准备：5. 实验过程：顺序栈 进制转换#includestdio.h#includestdlib.h#define stack_init_size 100#define stackincrement 10#define error 0#define overflow -2#define ok 1typedef int status;typedef int selemtype;typedef struct int *base; int *top; int stacksize; sqstack;int 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; status push(sqstack &s,selemtype 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; *(s.top)=e; s.top+; return ok;status pop(sqstack &s,selemtype &e) if (s.top=s.base) return error; e=*(s.top-1); (s.top)-; return ok; status gettop(sqstack s,selemtype &e) if (s.top=s.base) return error; e=*(s.top-1); return ok;status stackempty(sqstack s) if (s.top=s.base) return ok; return error;void main()sqstack s;int n,e;initstack(s);printf(请输入一个数字:n);scanf(%d,&n);while(n)push(s,n%16);n=n/16;while(!stackempty(s)pop(s,e);printf(%d,e);printf(n);单链表表示的栈#includestdio.h#includestdlib.h#define error 0#define overflow -2#define ok 1#define true 1#define false 0typedef int status;typedef struct snode int data; struct snode *next; *linkstack;void initstack(linkstack &s) s=null;status push(linkstack &s,int e) linkstack p; p=(linkstack) malloc(sizeof(snode); if (p=null) return error; p-data=e; p-next=s; s=p; return ok;status pop(linkstack &s,int &e) linkstack p; if (s=null) return error; p=s; e=s-data; s=s-next; free(p); return ok; status stackempty(linkstack s) if (s=null) return true; return false;void main() int e; linkstack s; int i; initstack(s); for (i=1;i=10;i+) push(s,i); printf(nn); while (!stackempty(s) pop(s,e); printf(%d ,e); printf(n);循环队列#includestdio.h#includestdlib.h#define error 0#define overflow -2#define ok 1#define maxqsize 100typedef int status;typedef int qelemtype;typedef struct int *base; int front; int rear; sqqueue;int initqueue(sqqueue &q) q.base=(qelemtype *)malloc(maxqsize*sizeof(qelemtype); if (!q.base) exit (overflow); q.front=q.rear=0; return ok;status enqueue(sqqueue &q,qelemtype e) if (q.rear+1)%maxqsize=q.front) return error ; q.baseq.rear=e; q.rear=(q.rear+1)%maxqsize; return ok;status dequeue(sqqueue &q,int &e) if (q.rear=q.front) return error; e=q.baseq.front; q.front=(q.front+1)%maxqsize; return ok;void main() int e; sqqueue q; int i; initqueue(q); for (i=1;i20;i+) enqueue(q,i); printf(n);for(i=1;inext=null; return ok;status enqueue(linkqueue &q,qelemtype e) queueptr p; p=(queueptr)malloc(sizeof(qnode); if (!p) exit (overflow); p-data=e;p-next=null; q.rear-next=p; q.rear=p; return ok;status dequeue(linkqueue &q,qelemtype &e) queueptr p; if (q.rear=q.front) return error; p=q.front-next; e=p-data; q.front-next=p-next; if (q.rear=p) q.rear=q.front; free(p); return ok;void main() int i; int x; linkqueue qu; initqueue(qu); for (i=1;i20;i+) enqueue(qu,i); while (dequeue(qu,x)=ok) printf(%dt,x); printf(n);回文#include #include #include #include #define true 1#define false 0#define ok 1#define error 0#define infeasible -1#define overflow -2typedef int status;typedef int boolean;typedef int selemtype;typedef int sqqueue;typedef int qelemtype;#define stack_init_size 100#define stackincrement 10typedef struct int *base; int *top; int stacksize; sqstack;status initstack(sqstack *s) /* 构造一个空栈s */ (*s).base=(selemtype *)malloc(stack_init_size*sizeof(selemtype); if(!(*s).base) exit(error); /* 存储分配失败 */ (*s).top=(*s).base; (*s).stacksize=stack_init_size; return ok; 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(error); /* 存储分配失败 */ (*s).top=(*s).base+(*s).stacksize; (*s).stacksize+=stackincrement; *(*s).top)+=e; return ok; status destroystack(sqstack *s) /* 销毁栈s，s不再存在 */ free(*s).base); (*s).base=null; (*s).top=null; (*s).stacksize=0; return ok; status clearstack(sqstack *s) /* 把s置为空栈 */ (*s).top=(*s).base; return ok; status stackempty(sqstack s) /* 若栈s为空栈，则返回true，否则返回false */ if(s.top=s.base) return true; else return false; status gettop(sqstack s,selemtype *e) /* 若栈不空，则用e返回s的栈顶元素，并返回ok；否则返回error */ if(s.tops.base) *e=*(s.top-1); return ok; else return error; status pop(sqstack *s,selemtype *e) /* 若栈不空，则删除s的栈顶元素，用e返回其值，并返回ok；否则返回error */ if(*s).top=(*s).base) return error; *e=*-(*s).top; return ok; /* 判断一个字符串是否为回文 如果是，返回true. 否则，返回false.*/boolean checkhuiwen(char *s) sqstack s; /* 定义一个顺5序栈 */ sqqueue q; /* 定义一个顺序队列 */ int i = 0; char e1,e2; while(si != 0) push(&s,si); enqueue(&q,si); i+; while(!stackempty(s) pop(&s,&e1); dequeue(&q,&e2); if(e1 != e2) return false; return true; void main() char s30 = abccba; printf(please input a string:n); scanf(%s,s); if(checkhuiwen(s) printf(%s is a