数据结构实验二实验报告

课程 名称 系部 实验 时间 评语 指导教师： (316667628@qq.com) 数据结构 班级 实验实验二 栈和队列的应用 名称 姓名 学号 地点 机位 成绩 2012 年 11 月 9 日 10 时 00分～ 11时 40 分 注：将实验成果文件（包含实验报告电子文件、程序源代码文件等)，用WinRar打包，以<班级>_<学号>_<实验X>.RAR文件形式交付指导老师。 一、实验目的

1.掌握栈的顺序表示和实现 2.掌握队列的链式表示和实现 二、实验内容

1.编写一个程序实现顺序栈的各种基本运算。 2.实现队列的链式表示和实现。 三、实验步骤

1.初始化顺序栈 2.插入元素 3.删除栈顶元素 4.取栈顶元素 5.遍历顺序栈 6.置空顺序栈

7.初始化并建立链队列 8.入链队列 9.出链队列 10.遍历链队列

四、程序主要语句及作用

程序1的主要代码(附简要注释) #include #include #define MAXNUM 20 #define ElemType int

typedef struct

{ ElemType stack[MAXNUM]; int top; }SqStack;

void InitStack(SqStack *p) { if(!p) printf(\"Eorror\"); p->top=-1; }

void Push(SqStack *p,ElemType x) { if(p->toptop=p->top+1; p->stack[p->top]=x;

} else printf(\"Overflow!\\n\"); }

ElemType Pop(SqStack *p) { ElemType x; if(p->top!=0) { x=p->stack[p->top]; printf(\"yi qian de zhan ding shu ju yuan su %d yi jing bei shan chu ！\\n\>stack[p->top]); p->top=p->top-1; return(x); } else { printf(\"Underflow!\\n\"); return(0); } }

ElemType GetTop(SqStack *p) { ElemType x; if(p->top!=0) { x=p->stack[p->top]; return(x); } else { printf(\"Underflow!\\n\"); return(0); } }

void OutStack(SqStack *p) { int i;

printf(\"\\n\"); if(p->top<0) printf(\"zhe shi yi ge kong zhan ！\"); printf(\"\\n\");

for(i=p->top;i>=0;i--) printf(\"di %d ge shu ju yuan su shi %6d\\n\}

void setEmpty(SqStack *p) {

p->top= -1; }

main()

{ SqStack *q;

int y,cord;ElemType a; do{ printf(\"\\n\"); printf(\"di yi ci shi yong bi xu chu shi hua ！\\n\"); printf(\"\\n\"); printf(\"\\n zhu cai dan \\n\"); printf(\"\\n 1 chu shi hua shun xu zhan \\n\"); printf(\"\\n 2 cha ru yi ge yuan su \\n\");

}

printf(\"\\n 3 shan chu zhan ding yuan su \\n\"); printf(\"\\n 4 qu zhan ding yuan su \\n\"); printf(\"\\n 5 zhi kong shun xu zhan \\n\"); printf(\"\\n 6 jie shu cheng xu yun xing \\n\"); printf(\"\\n--------------------------------\\n\"); printf(\"qing shu ru nin de xuan ze( 1, 2, 3, 4, 5,6)\"); scanf(\"%d\ printf(\"\\n\"); switch(cord) { case 1: { q=(SqStack*)malloc(sizeof(SqStack)); InitStack(q); OutStack(q); }break; case 2: { printf(\"qing shu ru yao cha ru de shu ju yuan su a=\"); scanf(\"%d\ Push(q,a); OutStack(q); }break; case 3: { Pop(q); OutStack(q); }break; case 4: { y=GetTop(q); printf(\"\\n zhan ding yuan su wei ：%d\\n\ OutStack(q); }break; case 5: { setEmpty(q); printf(\"\\n shun xu zhan bei zhi kong ！\\n\"); OutStack(q); }break; case 6: exit(0); }

}while (cord<=6);

程序2的主要代码(附简要注释)

#include #include #define ElemType int typedef struct Qnode { ElemType data; struct Qnode *next; }Qnodetype; typedef struct

{ Qnodetype *front; Qnodetype *rear; }Lqueue;

void Lappend(Lqueue *q,int x) { Qnodetype *s;

s=(Qnodetype*)malloc(sizeof(Qnodetype)); s->data=x;

s->next=NULL; q->rear->next=s; q->rear=s; }

void creat(Lqueue *q) { Qnodetype *h; int i,n,x;

printf(\"shu ru jiang jian li lian dui lie yuan su de ge shu n = \"); scanf(\"%d\

h=(Qnodetype*)malloc(sizeof(Qnodetype)); h->next=NULL; q->front=h; q->rear=h;

for(i=1;i<=n;i++) { printf(\"lian dui lie di %d ge yuan su de zhi wei :\ scanf(\"%d\ Lappend(q,x); } }

ElemType Ldelete(Lqueue *q) { Qnodetype *p; ElemType x;

if(q->front==q->rear) { printf(\"dui lie wei kong ! \\n\"); x=0; } else { p=q->front->next; q->front->next=p->next; if(p->next==NULL) q->rear=q->front; x=p->data; free(p); }

return(x); }

void display(Lqueue *q) { Qnodetype *p;

p=q->front->next;

printf(\"\\n lian dui lie yuan su yi ci wei ：\"); while(p!=NULL) { printf(\"%d-->\ p=p->next; }

printf(\"\\n\\n bian li lian dui lie jie shu ！ \\n\"); }

main()

{ Lqueue *p; int x,cord;

printf(\"\\n*** di yi ci cao zuo qing xuan ze chu shi hua bing jian li lian dui lie ***\\n \"); do

{ printf(\"\\n lian dui lie de ji ben cao zuo \\n \"); printf(\"=========================================\\n\"); printf(\" zhucaidan \\n\");

printf(\"=========================================\\n\"); printf(\" 1 chu shi hua \\n\"); printf(\" 2 ru lian dui lie \\n\"); printf(\" 3 chu lian dui lie \\n\"); printf(\" 4 bian li lian dui lie \\n\"); printf(\" 5 jie shu yun xing \\n\"); printf(\"==========================================\\n\"); scanf(\"%d\ switch(cord) { case 1: { p=(Lqueue *)malloc(sizeof(Lqueue)); creat(p); display(p); }break; case 2: { printf(\"shu ru dui lie yuan su de zhi ： x =\"); scanf(\"%d\ Lappend(p,x); display(p); }break; case 3: { printf(\"chu lian dui lie yuan su ：x = %d\\n\ display(p); }break; case 4: {display(p);}break; case 5: {exit (0);} }

}while (cord<=5); }

五、程序运行结果截图

程序1截图

1．初始化

2．插入3个元素

3 。删除栈顶元素7

4．取栈顶元素

5．置空顺序栈

程序2截图

1．初始化链队列

2．输入链队列的值

3．出链队列元素

4．遍历链队列的元素

六、收获，体会及问题