文档介绍：第三章实验报告
实验名称:数据结构第三章实验
实验类型:验证性
学号
姓名:红领巾
问题描述
(1)顺序栈
顺序栈的C语言描述
基本运算的算法——置空栈、判栈空、进栈、出栈、读栈顶、输出栈、判栈满
(2)链栈
链栈的C语言描述
基本运算的算法——置空栈、判栈空、进栈、出栈、读栈顶
(3)循环队列
循环队列的C语言描述
基本运算的算法——置空队、判队空、进队、出队、读队头元素、输出循环队列
(4)链队列
链队列的C语言描述
基本运算的算法——置空队、判队空、进队、出队、读队头元素
数据结构设计
(1)顺序栈
要实现顺序栈操作,我们需要一个栈顶指针一个栈底指针,以及说明当前已经分配的存储空间(即当前可使用的最大容量),因此结构中需要定义这三个部分
typedef struct{
char *base;
char *top;
int stacksize;
}Sq;
(2)链栈
对于链栈,每一个人节点需要有data域和next域,分别储存数据以及指向下一个节点,下一个节点也应该是拥有这两个域,所以用到嵌套定义来定义节点的数据结构
typedef struct node
{ char data;
struct node *next;
}node;
(3)循环队列
对于循环队列,需要有头尾指针指向队列头元素和尾元素的下一个位置,所以我们定义front,rear指针,为了说明动态分配的存储空间,我们定义了base,这就是循环队列的存储结构
typedef struct
{ int *base;
int front;
int rear;
}SqQueue;
(4)链队列
根据要求可知,我们运用单链队列即可实现所需要的功能,对于单链队列,我们需要两个指针作为队头队尾指针从而实现队列的操作,所以定义front,rear。对于每一个节点都有data和next域来存储数据和指向下一个节点,所以进行这种节点定义。
typedef struct QNode
{ int data;
QNode *next;
}QNode,*QPtr;
typedef struct Qlink
{ QPtr front;
QPtr rear;
}Qlink;
算法设计
顺序栈
系统规定的功能设计的算法有:置空栈、判栈空、进栈、出栈、读栈顶、输出栈、判栈满
初始化和建立顺序栈
S1:定义数据结构类型
typedef struct{
char *base;
char *top;
int stacksize;
}Sq//定义结构体,其中包含栈顶、栈尾指针和存储空间
S2:初始化这个顺序栈
int InitSq(Sq&S){
=(char *)malloc(STACK_INIT_SIZE*sizeof(Sq));
if(!)exit(OVERFLOW);
=;
=STACK_INIT_SIZE;
return OK;
}//申请存储空间,并且将栈顶栈尾元素指在一个位置,构造空栈
S3:从键盘输入一串字符,根据这些字符构造顺序栈
Sq create(Sq &S){
InitSq(S);
printf("请输入你的栈");
char str[100];
gets(str);//得到字符
int n=strlen(str);
for(int i=0;i<n;i++){
Push(S,str[i]);
}//调用Push函数将每个字符入栈
return S;
}
2)置空栈
编写子函数Clear,使其可以实现置空栈功能
int Clear(Sq&S){
while(!=){
char e;
Pop(S,e);
}
return OK;
}
在主函数里调用Clear子函数,就能达到置空栈的功能
判栈空
S1:编写判断栈空的子函数Empty,使其实现判栈空功能
int Empty(Sq S){
if(==)
return OK;
else return ERROR;
}
S2:在主函数调用时根据子函数返回值判断输出内容
if(Empty(S)) printf("Empty\n");
else printf("NotEmpty");
进栈
S1:从客户端得到所要入栈的元素
printf("进栈元素是:");scanf("%c",&x);
S2:编写子函数Push,使其可以实现将元素入栈功能
int Pu