J数据结构实验报告3_数据结构实验报告三
J数据结构实验报告3由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验报告三”。
《数据结构》实验报告三
栈和队列的操作
班级：
网络工程
学 号：
12013242122
实验日期：
2015.4.20
姓 名：
蒋佳惠
程序文件名及说明：
一、实验内容：
1.采用链栈，判断输入的一个字符串是否具有中心对称关系。
2.两个栈共享向量空间v[m]，它们的栈底分别设在向量的两端，每个元素占一个分量，试写出两个栈公用的栈操作算法：
push(i,x)、pop(i,x)和top(i)，其中i为0或1,用以指示栈号。
3.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（提示：可以设头指针），试编写相应的置、入队和出队算法。4.创设以数据sequ[m]存放循环队列的元素，同时设变量rear 和quelen分别指示循环队列中队尾元素的位置和内含元素的个数。试给出判别此循环队列队列满的条件，并写出相应的入队和出队算法（在出队算法中要返回队头元素）。
二、实验报告必须写明内容
1.程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）2.源程序及注释： 3.运行输出结果：
4.调试和运行程序过程中产生的问题及采取的措施：
5.对算法的程序的讨论、分析，改进设想，其它经验教训。
1、采用链栈，判断输入的一个字符串是否具有中心对称关系。（1）程序如下：
#include “stdio.h” #include “stdlib.h” #include “string.h” typedef char datatype;typedef struct node {datatype data;struct node *next;}linkstack;//定义链栈 //置空链栈
linkstack *setnull(linkstack *top){ top=NULL;
return top;} //判断栈是否为空
int empty(linkstack *top){ if(top==NULL)
return 1;
else
return 0;
} //取栈顶元素
int gettop(linkstack *top,datatype *v){
if(top!=NULL)
{*v=top->data;
return 1;
}
else
return 0;
} //入栈
linkstack *pushlstack(linkstack *top,datatype x){ linkstack *p;
p=(linkstack *)malloc(sizeof(linkstack));
p->data=x;
p->next=top;
return p;} //出栈
linkstack * poplstack(linkstack *top,datatype *v){linkstack *p;if(top==NULL)
{ printf(“under flown”);
return NULL;} else
{*v=top->data;
p=top;
top=top->next;
free(p);
}
return top;
} //3.3 判断该字符串是否有中心对称关系
int symmetry(char *s){linkstack *top;int i,n;char c;top=NULL;n=strlen(s);if(n%2==0)//偶数
for(i=0;i
top=pushlstack(top,*(s+i));
else
for(i=0;i
top=pushlstack(top,*(s+i));
for(i=n/2;i
{
top=poplstack(top,&c);
if(c!=s[i])
{ printf(“不对称n”);
return 0;
}
}
printf(“对称n”);
return 1;
} //3.4判断一个算术表达式的圆括号是否正确配对 int match(char *s){linkstack *top;int i;char c,t;top=NULL;for(i=0;i
char *s;
s=a;
gets(s);
symmetry(s);
gets(s);
match(s);
return 1;
}（2）窗口显示：
2、两个栈共享向量空间v[m]，它们的栈底分别设在向量的两端，每个元素占一个分量，试写出两个栈公用的栈操作算法：
push(i,x)、pop(i,x)和top(i)，其中i为0或1,用以指示栈号。（1）程序如下：
#include“stdio.h” #include “conio.h” typedef int datatype;#define m 6 datatype v[m];//栈所占的向量空间 int ta,tb;//两个栈顶指针 //初始化栈
void initstack(void){ta=0;tb=m-1;
} push(int i,datatype x){ if(ta
{if(i==0)//入ta栈
{v[ta]=x;
ta++;
}
if(i==1)//入tb栈
{ v[tb]=x;
tb--;
}
return 1;
}
else
{printf(“stack overflown”);
return 0;
}
} datatype pop(int i){datatype x;if(i==0)
if((ta>0))
{ ta--;
x=v[ta];
return x;
}
else
return NULL;if(i==1)
if(tb
{ tb++;
x=v[tb];
return x;
}
else
return NULL;return NULL;} datatype top(int i){ datatype x;
if(i==0)
if(ta>0)
{ x=v[ta-1];
return x;
}
else
return NULL;
if(i==1)
if(tb
{ x=v[tb+1];
return x;
}
else
return NULL;
return NULL;
} void prints(int i){int j;printf(“noutput from bottom to top!n”);
if(i==0)for(j=0;i
printf(“%3c”,v[j]);if(i==1)for(j=m-1;j>tb;j--)
printf(“%3c”,v[j]);} void main(){int i;clrscr();for(i=0;i
}
（2）窗口显示：
3、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（提示：可以设头指针），试编写相应的置、入队和出队算法。（1）程序如下： #include “stdio.h” #include “conio.h” #include “stdlib.h” typedef char datatype;
typedef struct node {datatype data;struct node *next;}linklist;//定义链队列结点 //定义链式循环队列 typedef struct {
linklist *rear;//只设尾指针
}linkqueue;//将队列q置空
linkqueue *setnull(linkqueue *q){linklist *h;h=(linklist *)malloc(sizeof(linklist));h->data='*';//头结点标志 h->next=h;q->rear=h;return q;//返回带头结点的空队列 } //在队列q中入队值为x的结点
linkqueue *enlqueue(linkqueue *q,datatype x){linklist *s,*r;r=q->rear;s=(linklist *)malloc(sizeof(linklist));s->data=x;s->next=r->next;r->next=s;q->rear=s;return q;
} //判断队列q是否为空 int empty(linkqueue *q)
{linklist *p;
p=q->rear;
if(p->next==p)return 1;
else return 0;
} //返回从队列q中出队元素 datatype delqueue(linkqueue *q){linklist *p,*s;datatype t;if(empty(q)){printf(“emptyn”);return NULL;} else { p=q->rear->next;s=p->next;
t=s->data;p->next=s->next;free(s);return(t);} } //链队列打印
void qprint(linkqueue *q){linklist *h,*p;h=q->rear->next;p=h->next;while(p!=h){printf(“%c->”,p->data);p=p->next;} printf(“^n”);} int main(void){linkqueue *q;int i;linklist *s,*h;datatype ch;//clrscr();q=setnull(q);ch=getchar();while(ch!='$'){enlqueue(q,ch);ch=getchar();} qprint(q);for(i=0;i
printf(“%c ” ,ch);
} printf(“n”);qprint(q);}
（2）窗口显示：
4、假设以数组data[m]存放循环队列的元素，同时设变量r（队尾）、f（队头）、len（元素个
数）。试给出判别此循环队列的队满条件，并写出相应的入队列、出队操作。(1)程序如下：
#include “stdio.h”
#include “conio.h”
#define m 30
typedef char datatype;
typedef struct
{datatype data[m];//存放数据
int r;//尾指针
int f;//头指针
int len;//队列元素个数
}sequeue;//定义循环队列
/将队列sq置为空队列
sequeue *setnull(sequeue *sq)
{sq->f=m-1;
sq->r=m-1;
sq->len=0;
return sq;
}
//判断队列q是否为空
int empty(sequeue *q)
{if(q->len==0)return 1;
else
return 0;
}
//取队头元素
datatype front(sequeue *q)
{if(empty(q)){printf(“emptyn”);return NULL;}
else
return(q->data[(q->f+1)%m]);
}
//将值为x的元素入队列q
int enqueue(sequeue *q,datatype x)
{if(q->f==(q->r+1)%m)
{printf(“queue is fulln”);return 0;}
else
{q->r=(q->r+1)%m;
q->data[q->r]=x;
q->len++;
return 1;
}
}
//返回从队列q中出队的元素
datatype dequeue(sequeue *q)
{
if(empty(q))
{printf(“queue is emptyn”);return NULL;}
else
{q->f=(q->f+1)%m;
q->len--;
return(q->data[q->f]);
}
}
//打印队列q
void qprint(sequeue *q)
{int i,j;
for(i=1;ilen;i++)
{j=(q->f+i)%m;
printf(“%c ”,q->data[j]);}
printf(“n”);
}
int main(void)
{sequeue *q;
char ch;
int i;
//clrscr();
q=setnull(q);
ch=getchar();
while(ch!='$')
{enqueue(q,ch);
ch=getchar();
}
qprint(q);
for(i=0;i
{ch=dequeue(q);
printf(“%c ”,ch);
}
printf(“n”);
qprint(q);}
(2)窗口显示：
5、调试和运行程序过程中产生的问题及采取的措施：
（1）出队操作时，要考虑除了头结点外，只有一个结点的情况。删去一个结点后就剩下一个头结点了。
（2）键盘输入元素时，遇到问题，询问了同学方才解决。（3）
6、心得体会：
实践才能出真知，在通过了上机操作后，才发现了许多在平时上理论课的没有想到的方方面面，编写程序是发现很多语法的错误，以及很多英语单词的记不熟，记错，程序函数错用等等，我想需要在以后多多练习，才能逐步解决这些问题。
