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